I've been pretty inactive in development recently for a few reasons (I got engaged, then I had a nasty fall from my road bike due to a tyre blowout). I was impressed by the great work that David Nolden continues to do for kdevelop, particularly the behind-the-scenes improvements which make using the program bearable. However as we know it's the new features which are the most 'bloggable'...

The new class wizard is currently pretty basic, but in a few hours I managed to link up the dialog with the definition-use chain, and the results are pretty impressive (for the amount of effort involved):

Here you can see a list of super classes which you're overriding, and the virtual functions which each class contains. The idea is then you can check those functions which you want to implement / override, and kdevelop will create the entry in the new class and the stub in the implementation file. This code is also mostly language-independent, although I need to speak to David about a few details there. BTW, it's not committed yet, pending a bit more polishing.

Another leap forward in KDevelop version 4 is the interface. We've tried to make it both highly flexible (to fit most people's requirements) and reliable (kdev3 suffered from a difficult to maintain ui library, prior to a simplified rewrite), and the current state is pretty good (certainly better than kdev3). Features include:

Features likely to be implemented at some stage include split toolview areas, and drag + drop of tool views.

I've decided to write a series of blogs detailing the work that has gone on behind the scenes for KDevelop version 4, the new IDE that is now 3 years in the making. Like KDE4, KDevelop has seen much work on essential internal mechanisms (much like the pillars of KDE), the power of which will become evident over the next year or so. Progress has been great recently, with the hackathon we had in Munich earlier this year, productive SoC projects and several more/new developers becoming active again, it's looking like we can expect to be releasing a pretty solid beta within about a month. The other developers and I use kdevelop daily to work on kdevelop 4, including writing code; version control; building, executing, debugging, and valgrinding programs; navigating the project with quick open, find in files (grep), etc.

In today's blog I'll concentrate on language support, arguably the most important feature of an IDE. I've previously blogged about the underpinnings of the new language support, which is arguably the most important cornerstone of the technology developed for this release. It consists of an extensive definition-use chain and type system; this means that KDevelop knows accurately where all of your declarations, definitions, types etc. occur, and when you use each of them. Comprehensive code completion, refactoring and other advanced tools will all flow on from this.

Two things have struck me about the definition-use chain (duchain) work recently. Firsty, our code has matured and is working well. When I was last blogging (too long ago, I know), I wrote about how it was difficult to make it all work with multithreading, and that c++ support was incomplete. Now I have learned much more about threading and locking issues, and the scheme that I finally settled on (one global read/write lock for the entire duchain) has solved the problems. This is important not only so that KDev4 can make use of dual/quad core machines, but also so that background parsing occurs without getting in the way of the user. C++ support has matured over the last year (thanks to David Nolden) to include full macro and template support (which are not easy tasks, the complexity of tracking macros accurately throughout include files caused many headaches).

The second is that we've started generalising what code we can to share between different language supports. It now takes very little effort to implement a duchain for a new language, once you have a parser in place. Java, C#, and PHP have all made encouraging starts (python too, but that effort is currently unmaintained), and I've found that the effort required to develop a duchain for a language is much less because of the shared code. All have relatively complete duchains within each file, and the c# duchain took only a few hours for me to implement. I've put some quality time into developer documentation as well, which can be found on api.kde.org. Once a language has a working duchain, it's ready to share in the features which were created initially for c++, such as code model, context browsing, and code completion [already implemented] and the sure to follow refactoring support. If you want to see your favourite language well supported by kdevelop 4, we'd appreciate your help - other than c++ and php, there are no major active maintainers. I believe C# and Java are especially important secondary languages for kdevelop to support.

DUChain performance and reliability has been the focus of David and I for the last few months, especially given David's SoC project on "Rock Solid C++ Support". Memory usage has been dramatically improved, and many bugs have been tracked down, especially with regards to text editor integration. The next step is saving everything to disk ("persistance"), because although the parsing is pretty efficient, enabling complete on the fly duchain support for a project is like trying to compile the project and all of its dependencies every time it is opened otherwise. Once we have duchain persistance, the navigation features already implemented will become much more useful.

If you want to get started using kdevelop now, checkout and compile kdevplatform and kdevelop modules from svn. Bugzilla is open, and we would especially appreciate* any reports of incorrectly parsed c++ code (you'll notice red highlighting, and the problem reporter will detail any errors (*with the exception of the known bug highlighting the first character of a document)) or crashes.

I'm currently at the KDevelop sprint at the Trolltech offices in Munich, Germany. We had a productive weekend of talks to bring everyone up to speed with the current state of KDevelop, and while what's going on under the hood is very exciting, it currently suffers from a kluged together, buggy and incomplete UI. For the first day of the programming several of us are working on improving the user interface, and it's making progress slowly but surely. Stay tuned for a screenshot / screencast when we have it looking just right

I've made it to my second lot of annual leave this year, so I've bought a nice shiny new digital SLR (the Sony a100) and am going to Japan for two weeks for a holiday.

If there are any KDE devs or users who'd like to meet up in Japan (and preferably can speak english, as my japanese is non-existant) drop me a line...

So, the last two days I've been concentrating on introducing locking into the definition-use chain which I've been writing for KDevelop. I've taken quite a coarse-grained approach, with one lock for each document's chain, and with separate object local locks each time that an object can reference another object that is on a different chain.

It took several hours yesterday to complete the basic scheme where the chains weren't referencing each other. I didn't even realise they weren't referencing each other until later, when I recognised that a speedup commit that Matt had contributed had removed some of my code which made this happen before. In fact, it was fortunate, because it allowed me to develop the code in two steps.

So today I've been trying to make the chains play nice while referencing each other. The going hasn't been easy. First I was confronted with some more unprotected accesses - these aren't too hard to fix, thanks to an extensive assert system that I've put in place to detect when locks aren't being held that should be. Second, there was a deadlock in the code completion code which took a little while to figure out - note to anyone using QReadWriteLock: if you ask for a second read lock while someone else is asking for a write lock, you'll deadlock. Third, I hit a race inside katepart where text edits and smart range updates could occur simultaneously, which was also bad. That wasn't too hard to fix. Now, I'm cleaning up some access of deleted memory with the help of Valgrind.

I'm not sure that this code can even be made to be reliable, given its complexity. Adam Treat pointed me at an article recently, The Problem with Threads, and I'm starting to agree. Having multithreaded definition-use parsing and manipulation would be a good goal, but perhaps not more than being stable. So, I plan to give it some time in svn to see if it can be made reliable enough for kdevelop's purposes.

In other news, my latest hardware purchase arrived today - a Dell 30" flat panel screen. At 2560x1600, when you combine it with another large screen (I have 2x 24" already, at 1920x1200), my graphics card can't handle them in xinerama mode, as the virtual screen size maximum is 4096x4096. So, I've been trying it in separate screen mode, but it's not a particularly pleasant setup - problems including the loss of ability to alt-tab between screens, kicker popping up on the other screen to the one that you're working on (and crashing), and of course not being able to drag apps between screens. Anyway, the 30" screen is excellent quality. I took a photo but it doesn't do it justice at night time...

As part of the definition-use chain work that I have been doing for KDevelop, yesterday I wrote a browser for each document's chain. There was just one catch... none of the chain is protected for multithreaded access at the moment.

I'm pretty new to multithreaded programming, so I started with reading the Qt docs. Well, as those of you who have read it know, it is intended for programmers with a familiarity with the issues presented. Nevertheless, it did a fair job of explaining to me the issues.

This got me to where KDevelop is now - that is, it runs, shuts down, and can have its parse jobs interrupted without crashing. However, when I came to the definition-use chain, I knew it would take more than just what I could do with fine-grained mutexes to this point.

The difficulty with designing locking for this group of explicitly shared objects is that at first glance they can cross reference each other wherever they like, thanks to the #include directive. So, I was about to start on fine-grained locking inside each class across all classes. However, it just didn't feel right.

So, the reason I'm blogging now is because I've hopefully found a solution to this problem. In fact, when you look closer at the design of the chain, only certain objects create cross references - top level contexts, definitions which are separate to their declarations, and uses of definitions. Even better, the builders only need to acquire one of each type of lock at any one time, so hopefully this will avoid deadlocks too.

Thus, I'm planning to lock each of these three categories with separate per-object read/write locks. This even has the benefit that the second pass of the chain builder (the use pass) only has to write lock the use locks, and read lock the top context. Wish me luck...

PS: I was saddened to hear of the passing of Steve Irwin today, although he was a little overly Australian, he was unashamedly so...

Firstly, thanks to clee for adding me to the Planet. When I left Trysil I planned to blog more often, and now you too can read about it

So, for the last 2 weeks I've been on annual leave, and have had the fortune to be "on a roll" with my coding. I'm currently concentrating on KDevelop 4. We're privileged to have a new parser framework by Roberto Raggi and Jakob Petsovits. I've been working on extending this good work with a new type system and definition-use chain.

The definition-use chain is a sequence of scopes in a code file, and the associated definitions which occur in those scopes. These are created on the first pass after parsing to an AST (abstract syntax tree), along with the data types. On the second pass, we search for a definition which corresponds to every variable use, and complete the chain. This work is now nearing completion; remaining issues are template support, and better forward declaration and typedef support. I also have to reconsider the use of shared pointers in the type system, because as Roberto pointed out, C++ allows recursive types (which don't work well with shared pointers). Here's a look at some of the highlighting possible with the definition-use chain: (please ignore the bugs

On Thursday, I implemented code completion. This is the first real use of the new model-based code completion that I wrote for Kate. By expressing the possible completions in a model, and properties associated with each (eg. public/protected/private, etc), Kate can then perform some advanced functions such as sorting, filtering, and grouping. I'll post a screenshot when I can undo some recent breakage.

On Friday I implemented a symbol table, which contains a reference to every definition currently in memory (from all files). I should have done this a week ago - it turned out to be quite simple. Now, hopefully the definition searching will scale up to handle the load when we have all includes parsed in.

[Side note: did you know that Print Screen invokes KSnapshot? a neat trick I learned by accident]

Some work has also gone into performance of this new system, which has paid handsome dividends thanks to valgrind/callgrind/KCachegrind. Parsing speed was increased by 80%, thanks to the removal of dependance on QTextStream in the preprocessor, an unused symbol table in the parser, and KUrl comparisons in the definition-use chain (which I was surprised about... I thought it would be much quicker given that they should be implicitly shared). More recently, I've optimised the most heavily used paths in the definition searching algorithms, and was pleasantly surprised at the performance increase when switching a critical foreach loop into a const iterator style. Also, I've discovered QVarLengthArray in optimising our QualifiedIdentifier class; as they are created and destroyed very often, reducing the list overhead was important (note to self: maybe making them implicitly shared would help even more).

So, where to from now? We're reaching a fairly stable api, and one which allows for code refactoring, intelligent navigation, improved automatic code generation (eg. I'm looking forward to "create switch statement"), context-sensitive code completion, integration of documentation, debugger integration, a code structure view, call graph, static code analysis etc. If you're interested in helping, we'd love to hear from you [as manyoso would say, especially if you have QGraphicsView mad skillz].

Yesterday I did some more work on KDevelop's c++ parser, specificially the definition-use chain (duchain). This was in response to some bugs that were being revealled by using it as the basis of advanced code highlighting.

I'd been struggling with a problem surrounding contexts where definitions are made (eg. in a funtion's parameter list, and then uses ocurring after that context has been closed (ie., using the open/close brackets as the context); also, in for and if statements). Previously I had been making those contexts span the whole function definition which didn't feel quite right, but allowed the context structure to remain a simple tree design.

Finally I realised that I had already implemented the solution; as I was using a directed acyclic graph (DAG), I could close the contexts as seemed right, then import them as subsequent parent contexts for the function body, etc. Indeed, this is probably what Roberto meant when he suggested I use the DAG design to start with, but it had taken me until now to realise it. I was thinking that he had meant to use the DAG features to incorporate other chains from #include-d files which had already been processed.

So, the duchain work is now more complete and correct. Improving it further now relies on proper importing of definitions from other files, and speeding it up by getting incremental parsing working. I've started on the former by separating the objects required for persisting the AST into a clean encapsulation in the parser, and separating the preprocessing from the parsing in the c++ parser. Next, I am going to make use of Threadweaver's job dependancy feature to order parsing such that when #include statements are encountered, the information from those included files will be available when it comes time to parse the file.

On the performance side, although Roberto's parser is quite fast, there is a noticable delay between changing a document and updating of the highlighting. I suspect that it's not all parsing time, but as there are many passes (preprocess, parse, code model binding, duchain creation (which probably needs to be two passes itself)) it's going to be important that we use incremental parsing (ie only reparsing changed text) as much as possible.

So, there are still many challenges in the way of the complete KDevelop4 experience, but the project continues to gain momentum...

For those of you who might not be aware, KDevelop v4 is starting to take shape, at least behind the scenes. For some time now we have had Roberto's new c++ parser in the code base but not doing very much. Then Matt and Adam worked hard on improving project management support (including native support for CMake) and the background parser / code model, so now we have a functional code model (even if not in the final state).

More recently, Jakob's Java and C# parsers (along the lines of the c++ parser) have been added to the codebase. They are just beginning to get codemodel integration.

While this was happening, I took over Roberto's work on creating definition-use chains. These are trees which represent contexts or scopes in which definitions are made, and then links from each definition to all of its uses. This turned out to be relatively easy once I had spoken in person to Roberto about it at kde four core in Norway (for some reason I didn't really understand what they were about when we talked online).

Yesterday, I managed to apply syntax highlighting to the katepart editor, based off the definition-use chain. This means that kdevelop will have separate highlights for variables defined in different ways, eg. local / function / class member / global, and also unrecognised variable usage. Here's a screenshot:

(yes, there are bugs visible there) This work is still quite raw and several major crashes need fixing, but this work has much potential. I'll save the details for my next blog entry...