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 !

You, KDE!

For me, it (still) feels very unnatural to talk about us as KDE. I’m still thinking in terms of the KDE community; and the KDE Project releases the KDE Desktop (or just KDE). I’m also fine with the KDE Workspace and other specialized variants. However, the login manager now also shows the term KDE Plasma Workspace. In my very own humble opinion, this is already too much of buzz words.

At university, I’m helping out with system administration. And since I’m very familiar with KDE, I fix all KDE related issues (and usually enjoy doing so). We have lots of colleagues that never used KDE. Now, try to explain the term Plasma… Well, it’s a desktop shell – also too complex. It’s the desktop, with all the icons and panels. That’s more understandable 🙂 But next, a dialog pops up with some status messages: Akonadi. Well, try to explain the term Akonadi. It’s similar with other technologies. Explain what Nepomuk is doing with the difference to Strigi… When I try to explain what’s happening, and what all these components do, I sometimes feel pretty much stupid uncomfortable using these words.

It is similar with the term KDE SC. As part of the rebranding, the KDE Software Compilation or short KDE SC was introduced. I can understand that we build a platform and our target is more than just the Desktop. But talking to other people, I feel stupid saying KDE SC. For me, it simply is (and probably will always be) a no-go. But it changed already, to the KDE platform, or maybe I misunderstood that ? 🙂

Funnily, I think it’s fine to use application names such as dolphin, kate, amarok and what not. So to some degree, I’m certainly simply used to these terms. But still, it feels right, also when talking to other users. We have to be very careful to use fancy names in very prominent places. Ah, and with respect to naming applications, there is a similar discussion on kde-core-devel right now 😉

GSoC 2011 – Kate Code Folding – (Try Kate’s new code folding)

Hi everyone!

Kate’s new code folding was merged with the master branch. 🙂
You can try it by yourself. If you do find any bugs, please send a bug report on KDE’s bug tracker or leave a comment here.
I will use a test unit to solve those bugs, so I will need a full backtrace and some info to help me replicate it.
Please notice that there are no new features added yet – just the basic code folding.

I’m waiting for your feedback!