GSoC 2011 – Kate Code Folding – week 2 (Architectural design)


Last week I focused on analyzing the interface of the actual implementation. Now, it’s time to develop the new interface.

As I mentioned in my proposal, one of my project’s goals is compatibility: I want to make as few changes as possible in the other sources. This is the reason why I studied the previous implementation for a whole week.

Another goal of my project is classes diagramsimplicity. The interface will be implemented in an abstract class. This class will be inherited by two other classes: one for C style languages (those who use elements like “{}”) and one for Python style languages (those who use indentation level to define the code blocks), as you can see from the diagram. I believe the code will be simpler and clearer if it is more specialized.

Because this part of the projects it’s about design, I would also like to define my data structures. Of course, there will be a Tree, the code folding tree, and some Nodes. It is very important to know where those Nodes are placed in document (row and column). This info needs to be updated when something changes in your document (e.g.: you add a new line, so all the Nodes change their rows). Because it is very time consuming to search through the folding tree, I suggest adding a second data structure.

For this part, I have a dilemma: whether to use a Vector of Vector<Nodes>, or a Set<row,Vector<Nodes>>.

Let’s make it clear: I want to use a Vector of Nodes (actually pointers of Nodes) for each line (because we might have more than one Node per line). But how will be those Vectors stored?

The first option is to use another Vector. The size of this Vector will be the same with the number of rows of the document and Vector[i] = all the nodes placed on the line “i”. This method is easy to be implemented and very fast. The complexity of the updates will be constant and that’s great. So, where is the problem? Memory usage: If we have a 10.000 document lines, then we have about 40 KB of data reserved for this data structure (even though there are no folding nodes at all).

The second option is to use a Set<row,Vector>. For each row, that has at least one folding node, there will be a single entry into this set. This method uses the memory very optimally, but update functions will have a logarithmic (if the set is kept sorted) or linear complexity (much slower than the previous method).

If you have any ideas, feel free to leave some feedback to this article. 😉


GSoC 2011 – Kate Code Folding

Hi everybody!

I am Adrian and, as Erlend already mentioned in a previous post, I will rewrite Kate’s code folding algorithm on this GSoC edition.

Starting from this week, I will post a weekly report of my work. At the end of each week I will post some info about the project’s progress and some details about what I have scheduled for the next week (according to my presented timeline).

I know that GSoC coding started for about 3 weeks, but, as you will see in my timeline, I had school exams until yesterday so I couldn’t work during this time. This won’t be a problem. I knew about that from the beginning and I scheduled my timeline starting with June 13th. Also, this was mentioned in my proposal, so all the mentors are aware of it.

My objective for the next week (13 June – 19 June) is to get familiar with Kate project and QT. I already downloaded the source files, compiled them and took a look through them, so I will do that again (more carefully) and build a list of questions which will be sent to my mentor or posted on the mailing list. This way I will be able to focus later on what I will write and not on how I will do it.

One more thing: Because this is my first post, I will also post my full timeline so that everyone knows what my next move will be. Here it is (pasted from my proposal):

Tentative Timeline

May 23 – June 12 – I won’t be able to work during this period because I will have some school exams during this time.

Weeks 1-2 (13 June – 26 June) – Plan on how to fit all the “puzzle pieces” (algorithms, data structure and other objects used); implementing the abstract class that will ensure backwards compatibility; take an overall picture of Kate code folding.

Weeks 3-4 (27 June – 10 July) – I will implement and test my tree-algorithms, which is the base of the code folding. The algorithms will be implemented in C++ using QT objects but as a separate project in order to test them as much (and easily) as possible.

Weeks 5-6 (11 July – 24 July) – Implementing the two classes that extend the abstract class using all the information gained in previous weeks.

Weeks 7-8 (25 June – 7 August) – Implementing a new feature for Kate code folding – “Code folding preview” (presented above)

Weeks 9-10 (8 August – 22 August) – Lots of testing and some documentation (I saw that Kate source files have a little lack of code documentation, but I think some explanations about the implementation would be great).

I am open to proposals about this project, so if you have any ideas that can make it better let me know and we will talk about them.

Wish me good luck! 🙂

Getting Involved

Recently we’ve had several feature requests in comments of a blog post. If you are interested, you can easily implement this and contribute to Kate. And I’ll even show you how to get started for the following feature. First, build Kate according to

Adding support for ctrl+w {left, right, up, down} to switch the active view.

Kate has a vi input mode. This way, vim users can still use their default work flow but still use Kate at the same time. What’s missing in the current vi input mode implementation is support for view navigation. In vim, to move between different windows, press ctrl-w <arrow keys> to switch to the neighboring view. Implementing this is rather easy – the following steps need to be taken care of:

  1. Add vim bindings (=vim shortcuts) to the Kate’s implementation of the ‘normal mode’.
  2. In the implementation, find all visible KateViews.
  3. Compare the global coordinates of the window geometry by using QWidget::mapToGlobal(const QPoint& pos) (for QPoint(0, 0) and QPoint(width(), height()) of all KateViews)
  4. Call setFocus to the nearest matching of the visible views.

Patches are welcome 🙂

Kate’s Folding Code and Vi Mode to be improved by GSoC students

This year’s Google Summer of Code (GSoC) has started and the Kate project has been lucky to get two students who will work on improving Kate’s folding code and Vi input mode.


Adrian will work on improving the folding code which is in need of an overhaul:

My name is Adrian. I’m studying in Bucharest, Romania, but my hometown is Constanta, a seaside town from Romania as well. I am a 3rd year student at “Politehnica” University of Bucharest, majoring in Computer Science and Engineering. I have developed a passion for algorithms since High school when I participate in many programming competitions and took things to a new level during college.

My GSoC project is called “Kate Code Folding” and I believe its name is quite explicit.  I chose this project because I am very familiar with the editor, as well as its code folding bugs. 🙂  Besides that, I am pretty excited that I have to develop a new algorithm for this project and I must say I find this task very challenging. For a better understanding of my project, here there are 2 paragraphs from my proposal, with no details, just the main ideas:

My project idea is based on two elements. The first one is a new approach of the problem: transform one more complex problem into two simpler problems. To be more specific, as far as I know there are two types of programming languages: there are languages that use syntactical elements like {} or any other begin/end constructions (e.g.: C/C++) and there are languages that use indentation level to define their code blocks (e.g.: Python).

The second idea is to have the new implementations compatible with the current one. What I mean is that most of the actual public functions will still be used in the new implementation (some of them will suffer a few modifications), to solve the dependencies problem in a smart and simple way. So there won’t be too many changes in the other source files.


Svyatoslav will work on improving the Vi input mode in Kate:

I am Svyatoslav Kuzmich. I’m a 2nd year student of Moscow Institute of Physics and Technology, department of Radioengineering and Computer Science.I usually write something like emulators and compilers but this Summer I am doing GSoC for KDE. I want to improve Vi input mode for Kate kpart. There are a lot of features already implemented. In some ways they works rather good. But there are some commands do not work like commands in Vim. So I want to fix them and to expand the list of commands by adding some insert and command mode’s commands for working with Kate’s tabs, window splits and bookmarks.

In more behind-the-scenes work, Svyatoslav will also write an extensive test suite for the Kate Vi Mode to make it easier to introduce new features without at the same time introducing regressions. This work has already begun.

We will try to keep you updated throughout the summer. Please wish our GSoC students good luck! 🙂

The Kate Editor Homepage