Category Archives: Common

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

Kate Vi Input Mode – GSoC 2011

I want to introduce you my GSoC-2011 project. I was working on improvement the vi input mode for the Kate part.

There are a lot of improvements for normal mode. Now it’s able to use jump list by pressing ctrl-i/ctrl-o in normal mode like in vim. And now not only registers but also marks, and jumps stored in the config of the session. H, M and L commands moves cursor to the first(Home), Middle and Last line of the screen. To go to the any percent of the document you can use the % command by typing the number of percent(1-100) before it. gk and gj motions will make you able to go visual(display) lines up and down. It’s useful when you using line wrap.

You can split the screen vertically and horizontally by ctrl-s and ctrl-v shortcuts and move around them in different directions using ctrl-w{h,j,k,l,w} or also ctrl-w{←,↑,↓,→}.

In insert mode added commands ctrl-r+[register] to insert the contents of a register and ctrl-o to switch to the normal mode only for a one command and automatically get back to insert. The ctrl-a, ctrl-x command now increase and decrease the negative numbers too.

There are also some new command-line features. Now you can use the marks for a command ranges. It’s possible to add and subtract line numbers in the ranges many times. For example command :.+3d will delete the third line after current position and the command :’a,’b-1y will yank the line-wise range between the line of mark ‘a’ and the one line before the line of ‘b‘ mark.

Also there a some new basic vim commands:

  • :d or :delete – delete range;
  • :c or :change – change range;
  • :j – join all the lines in range;
  • :> – indent range;
  • :< – unindent range;
  • :y or :yank – yank range;
  • :ma or :mark or :k – set mark;
  • :bn – switch to next buffer(document);
  • :bp – switch to previous buffer(document);
  • :bf – to first buffer;
  • :bl – to last buffer;
  • :b [N] or :buffer [N] – to Nth buffer

Text objects are also improved and fixed. There are new objects: ( a{ , i{ , a< , i< , a` , i` ). And now they normally works with nested objects. So for now the i( object (for position of multiply symbol *) will be “(1*2/(2+3)–4)” instead of “(1*2/(2+3)–4)”. Some of the objects like (),{},[],<> works with several lines.

Visual mode now is integrated with mouse, so the mouse dragging starts the visual mode. All kind of Kate-way selection is also starts the visual mode. For example if you use “Select all” menu line or shortcut ctrl-a(by default) this will starts visual mode with the selected text and waits you for a command to execute :) . One point mouse click will exit the visual mode. Kate selection and vi mode selection is actually the same thing now. So you can, say, to select a bloc by using the Visual Block mode (ctrl-v), to do a context menu on them and to copy them to a clipboard :). When you exit visual mode the ‘< and ‘> marks have a start and end position of selection. It useful when you want to execute some command line command on the selected text. Just press the “:” when you select something and it automatically fill the command line with “‘<,’>” to have a quick access to selected area.

Vi marks and Kate bookmarks are integrated too. If you set the mark then this line becomes bookmarked by Kate. And vice versa: if you set a Kate’s bookmark and there no vi marks on this like vi mode sets the vim mark on this line and zero column, and shows you what letter for this mark is used.You can see the position of all vi marks in the bookmark menu in the menu bar or also in the context menu.

I hope this features will make you feel even more comfortable while using Kate. You can try it now in the git version of Kate.
Any notice or bug report are welcome !

Kate progress, Git and happy new year ;)

As Dominik already points out in his blog, Kate has made nice progress for KDE 4.6.

Some of the latest fixes, like for some nasty search bug didn’t make it in RC1, btw., I was too lame with Git -> SVN syncs.
Anyway, I have now synced and backported to KDE 4.6 branch all pending fixes.

For the next KDE SC release 4.7 (here you go, I wrote SC :)), I hope this syncing will no longer be necessary.
At least Kate app + part + KWrite should then be only in the kate.git.
I can live with ktexteditor remaining in kdelibs, if removing that and still keeping BC and SC would be too much work. But part and app are at most runtime dependencies anyway.

Last but not least, I wish you all a good start into a happy new year ;)