AUG
18
2006

Breakthroughs in programming

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...