GSoC – Kate Code Folding (Bug-less)

Hi everyone!

Another season of Google Summer of Code is approaching its end. 🙁

I feel pretty bad about that, because I enjoy it and I love working on Kate.

I used the last two weeks to solve all the bugs and requests (folding related) from bugs.kde.org. If you find any folded related bugs, please send the report using bugs.kde.org and I will solve them (the warranty period is unlimited, so you don’t have to worry about that 😉 )

The next two weeks (the time remained until the dead line) will be used to write the documentation and to do some look changes, according to the code reviews received from the Kate community. Also, I will write some tests. Writing automatic tests for the folding is not such an easy task because you have to check a lot of stuff: the highlight, the folding sign, the folded lines, the line that remains visible and other things. And there are so many languages that act differently. That’s why I preferred to do the tests manually, so far. Anyway, I will write some units that will test the bases of the code folding, like number of lines left after a folding or some delete/insert operations occurred.

I consider this project a success and I hope that the Kate team has no regrets for choosing me for this GSoC season. 🙂

Enjoy Kate’s new code folding! 😉

Adrian

Kate Vi Mode Test Suite – GSoC 2011

This summer vi mode has a new test suite. Now there are over 250 tests and the number of them still growing.
It’s very easy to add a new test. All you need is just to add the
DoTest(“Original text”,”Vi command”,”Expected text after doing vi command”);
line to part/tests/vimode_test.cpp.
Format for command with CTRL – modifier: \\ctrl-x, for command -mode command: \\:command\\.
There are little restriction: you can’t input text while being in input mode.

Exampls:
DoTest(“foobar”,”Vypp”,”foobar\nfoobar\nfoobar”);
DoTest(“foo\nbar”,”\\ctrl-vjl~”,”FOo\nBAr”);
DoTest(“foo\nbar\nbaz”,”\\:2,3delete\\”,”foo”);

It’s also a good format for bug report or for feature wish for vi-mode.

Code Folding Updates

As you may know the Kate code folding implementation gets some love these days. The last days, several bug fixes dropped in by our GSoC student. And the good news is that if all works well, we’ll be able to backport these fixes so that the code folding is much more robust in our beloved Kate even in KDE 4.7.x. These changes probably fix several crashes that were around since 2005 as well. I believe the word we’re looking for is: owned! 🙂

GSoC – Kate Code Folding (some more details about folding)

Hi!

Yesterday I received a comment on my previous blog post that it would be nice to give some more technical details about the folding.

Initially, this was a comment response, but because it proved to be pretty interesting and more of you read the articles than the comments, I decided to post it as an article 🙂

Here are some details that you could find interesting:

Kate’s folding is based on a real / virtual line system. All the folded block’s lines have the same virtual line (they are literally folded under the first block’s line).
But how are these blocks defined?
Kate uses the file extension to determine what defines a block (special characters like “{“ or “}”, text alignment and so on). Kate’s highlight sends some info about these to Kate’s code folding. Let’s call them “document’s anchors”. This info is rudimentary. It is mentioned only the type of anchor (encoded as a number greater than 0 if it is a start anchor and lower than 0 if it is an end anchor) and its position in the document (real position). I use this info to build the “folding nodes” (I will detail them later) and to keep their position updated as well. So, here we have the first data structure: the “line mapping”. Line mapping is a QMap <line_number, QVector > and contains an entry for each document line that has at least one anchor I was talking about earlier. If this structure is updated correctly, then I am sure that all the folding nodes have their position set correctly and I don’t need to worry about that.

Now, I know where the document anchors are. But that isn’t enough – I need to form folding blocks with them.
I found two solutions for this “matching” problem:
1. Use a stack and rebuild (using the line mapping) the folding tree from scratch every time something is changing. The algorithm was very simple (parenthesis matching problem), but I found it pretty ugly (and slow) to rebuild the entire tree so often. I didn’t discard the idea either. The algorithm was perfect to be used as a term of comparison for the other algorithm.
2. Use a tree algorithm that changes itself dynamically. This was the solution I chose. I developed an entire project (see my previous posts) that helped me improve this algorithm and I believe it works pretty well. :)
The folding tree is made of folding nodes. These nodes contain info about their position (actually the document’s anchor that they represent), parent, type, matching node – all the info needed to define the folding blocks. If this tree is correct, then the blocks are defined correctly.

If you have the folding blocks defined, then you can fold them. To do this I use the third (and the last) data structures: a QList with the folded nodes. You might ask why we needed another(!) data structure. There are 3 methods that are called very, very often: getRealLine (virtualLine), getVirtualLine(realLine) and getHiddenLines(). Search through all the folding nodes (using the folding tree or the line mapping) is slow. Imagine if we do this search for every line of the document (actually there are about 2 or 3 calls per line every time something changes in the document!). I have also made one more improvement here: if a folded block contains another folded block, then the inner folded block is removed from this structure (it won’t help us discover the virtual or real lines).

Basically, these 3 methods are the code folding – the real / virtual line system I was talking about in the beginning. But.. there is a long way and lot of work to be able to answer these 3 questions fast and correctly. :)