Wednesday, April 28, 2010

Kate Internals: Smart Cursors and Smart Ranges

SmartCursors and SmartRanges in KDE 4.0 - KDE 4.4

Since KDE 4.0 the KTextEditor interfaces have so called SmartCursors and SmartRanges. A SmartCursor is a text cursor (i.e. a line/column tuple) , which is bound to a text document. When editing the text document, the cursor is automatically moved such that it maintains its position. You need this for the displayed text cursor in a view for instance. If you type text, the cursor automatically moves.
A SmartRange consists of two SmartCursors: start and end. We use that for instance for the text selection or the inline spell checking, or KDevelop uses it to add arbitrary highlighting to parsed C/C++ code. Again, if you modify text in the document, the text range automatically moves, expands or shrinks.

The concept of SmartCursors and SmartRanges is doubtless very useful. However, for KDE 4.5 the Kate developers came up with an alternative implementation that will even deprecate the SmartCursors and SmartRanges in KDE 4.6. The reason for this is that the current implementation has several problems, which we will discuss in the following.

API Usage

The SmartRanges API can be used in very wrong ways. For instance, the SmartInterface has the two functions deleteCursors() and deleteRanges(). Besides that, a document reload also deletes all SmartCursors and SmartRanges. Both cases lead to a dangling pointer if you use SmartCursors or SmartRanges. Hence, whenever you use them, you always need a so-called SmartCursorWatcher / SmartCursorNotifier and SmartRangeWatcher / SmartRangeNotifier, which tell you that your SmartCursor or SmartRange is about to be deleted. Watcher and Notifier basically do the same thing. Besides deletion notification, they also tell you more e.g. that the SmartCursor position changed. If you use a notifier, those notifications are sent via signals. If you use a watcher, you have to overwrite virtuals. That is, we have two different concepts that basically do the same thing. If you use thousands of SmartRanges e.g. for arbitrary highlighting, we have possibly thousands of those emits, which does not really scale.

The API also allows to have parent/child relations, i.e. a SmartRange can have children and a parent. It is possible to traverse this hierarchy, and again since you get the pointers you can delete arbitrary SmartRanges or SmartCursors. Another reason why you always need a notifier or watcher. And if you have a notifier/watcher, you always have the signals emitted when e.g. a cursor changes, as explained above.

Further, we have lots of places where we use reference object KTextEditor::Cursor& as parameter. This const reference-object signals that it does not change. But due to SmartRange deriving from KTextEditor::Cursor, this object might also be a SmartCursor. So despite of being declared as a const object, it may change its position behind your back. This may lead to unexpected behaviours in e.g. loops where the line or column of the cursor is assumed to be constant. This is a problem in almost all functions in KatePart, so passing SmartCursors as Cursors is a very bad idea, but of course allowed.

Scaleability Problems

As mentioned above, you always need a Notifier or Watcher for all SmartCursors and SmartRanges. This will emit lots of signals you probably rarely need. Still, there is no way around it. This is a huge overhead, it simply does not scale.

Implementation

The implementation is really complex and rather undocumented in most areas. Unfortunately, only very few (or maybe even no one) really understand the code. Besides that, it is very fragile. If you change something, you might break the code. Hence, we often heard similar comments like "don't touch the code, otherwise it will break". Such comments alone already indicate that the current implementation is not maintainable. Unmaintainable code is bad, especially in open source projects (this is not a good way to gain new developers at all). There are other downsides of the current implementation: SmartCursors need a lot of memory for each instance; there are lots of features like animations for SmartRanges, which make the code even more complex; redundancy of watchers and notifiers bloat the code and influence the runtime behavior.

Threading

It seems there was the idea of making the KTextEditor interfaces thread safe. The SmartRanges interact with the content of the document, e.g. querying lines count and line length of lines in the text buffer. As this is done by other threads we need correct locking in all places: in document content changes, in smart cursors, in smart ranges, in the painting routines, etc. The current state in KatePart is that not all functions do the right locking. That's why we have lots of asserts/crashs. KatePart already has more than 150 lockings at the moment, but they still do not voer problems. And very few developers (or no one?) really know when to lock and when not to. This is especially complex since we want to ensure that the locks are not hold while emitting signals or calling functions provided from the outside as callbacks, this is still not done completely right, too.

If you think about Qt, the GUI widgets are also not thread-safe, they all live in the main thread. And if you need data in other threads, you always use queued signals. This is pretty much what we experience in KatePart now. Not enough locking? Too much locking? In other words: It's far too complex to make the KTextEditor interfaces thread-safe...

Threading and Revisions

Now to another issue in the implementation. KDevelop uses KTextEditor::Ranges in the parsing thread. Think of the following use case: KDevelop gets all the document text in the current revision (or version, if you prefer). Now it takes some time until the parsing is finished. When it's finished, KDevelop uses the Ranges (which initially belong to the old revision of the document), and then translates those ranges to the current version of the text document (this is simple: Just track all edits inside KatePart (delete, insert, wrap, unwrap) and apply those transformations to the ranges). Now we transformed ranges from an old text revision to the current text revision. This means KDevelop does not have to parse everything again, as it knows exactly which parts changed. Awesome indeed :) However, now comes the problem: To transform Cursors and Ranges between revisions, you have to tell the SmartInterface about the revision you are working with. This is done via SmartInterface::useRevision(int). The API documentation says: Tell the smart interface to work against the given revision when creating cursors and ranges. That is, if you call useRevision() once, all succeeding calls like newSmartRange() etc are working in the past (at that revision). Also kind of cool, since useRevision() works locally in each thread. That is different threads don't influence each other. But there is huge problem with this: Think of a KTextEditor user (KDevelop, Kile, ...) uses useRevision() in the main thread. Then all succeding calls of e.g. newSmartRange() use an old revision instead of the current one. Hence, KatePart itself is completely broken in that case. (This case is now catched via a qFatal() in KatePart). But again this shows that multi-threading simply complicates the matter a lot. It would have been much easier to say transformRange(int fromRevision, int toRevision) instead of just one translateFromRevision() that translates the given range against the revision specified through useRevision(). Hence, the current API is unfortunately pretty much broken by design.

A necessary Step?

Often it's hard to get things done right in the first try. So maybe the issues above are a necessary step to a much better implementation. And that is exactly what happened in the last two months: We have new interfaces called MovingInterface, MovingCursor and MovingRange. For feedback there is MovingRangeFeedback, which uses callbacks for notification (no signals by intention). All those classes have unit tests. KatePart in KDE 4.6 will not implement any Smart* interface anymore. Hence, KatePart will be completely single threaded again. We already started to remove several thousands of lines Smart* code that was never used/finished. Much more will follow immediately after the KDE 4.5 release. This means all developers using Smart* from the KTextEditor interfaces should migrate to the Moving* pendents for KDE 4.5 already, if possible.

I'll provide very detailed information about the Moving* implementation in further blogs during the next month.

17 comments:

Fri13 said...

[Offtopic] Please use KDE SC from software and KDE from the community. It just makes it much easier for new users and existing users to follow the technology (but not those who refuse blindly from it) in future. Thanks [/Offtopic]

Diederik said...

Wow quite an interesting read, and learning how things work internally.

All this enumerating makes it sound like Kate is a pretty bad editor, which I think is a bit misleading. So great to see it's getter even better! :)

dhaumann said...

@Fri13: I refuse to say KDE SC simply because it's inconvenient. It sounds stupid. KDE is KDE. And that's that. Sorry ;) (PS: I *knew* that such a comment would come. ;) )

@Diederik: Well, as a developer one certainly has a different perspective anyway. All in all, Kate indeed is quite good imo. And for KDE 4.5 it will simply be sooo much better... :) Certainly much more stable!

maelcum said...

Interesting read!
I'm looking forward to the solution to the scalability problem. It is a universal problem really: When some change happens that invalidates a huge amount of data, do you update it right away, when it's used, or something in between?
The third solution pretty much always involves analysis of typical use cases.
I use Kate for all my coding, by the way :)

Misbachul said...

i wonder if kdevelop 4.0 will already use it..

Niko Sams said...

While it really sucks to remove the Smart interfaces and break compatibility, I fully understand the reasons for that. And once kdevelop is ported to Moving* all will profit from that. (maintained code, stability, performance)

dhaumann said...

@Misbachul: probably not, at least it's unlikely to replace Smart* so fast, because of the multi-threading afaik.

@Niko: I agree here. Removing Smart* is one of the worst things for KDevelop. On the other hand if KDevelop migrates to Moving*, it has a very solid base for the next years. So I really hope this is doable!

Kevin Kofler said...

This kind of compatibility breakage is just plain not allowed in a library which is part of kdelibs (which the KatePart is). I see why you want to do these changes, but they're completely inappropriate for any 4.x release, they need to wait for KDE SC 5 (whenever that will be, may be years from now).

dhaumann said...

@Kevin: You are completely wrong here. We are entirely binary compatible. Kate Part will just not implement some classes anymore. Which is totally fine. In the API docs you can read everywhere that you first have to check with qobject_cast, whether an interface is supported or not.

So this is not breakage at all, probably this got not clear. And what probably also got not clear is the fact that this Smart* stuff is killing Kate.

We will remove it. We have discussed about it on our mailing lists for more than 2 years now about it.

It's still broken. Unmaintained and what not.

It will be removed, there will not be any further discussions. Sorry ;)

Kevin Kofler said...

No matter what you component maintainers decide on your mailing list, you have to follow global KDE compatibility policies.

This will break some applications. A smart cursor is something you use in your code because you need it, it makes no sense to "maybe, if it happens to be supported" use a smart cursor. So this recommendation of checking and only using it if available is just wishful thinking, apps will either be degraded or just error out entirely even if they did follow it, and I'm pretty sure many will just crash entirely, because apps which explicitly request a KatePart expect to be able to use all its interfaces, nobody expects an interface to get removed like this. (I have one such application which is going to just crash, though there is no release of the KDE 4 version yet, so this particular application is not going to have many affected users. And BTW, that app is also not setting any Notifier or Watcher on the smart cursor.)

I'm really worried about the impact of this change on third-party applications using on the KDE platform. You can't really expect them to follow the kind of best practices you assume (third-party apps do all sorts of crazy things), and even if they do, they'll still have degraded functionality.

I'm sure this problem could be solved in a compatible way, e.g. by starting the "update smart cursors" thread the first time a smart cursor is requested, or possibly by changing the implementation within the constraints of the interface.

dhaumann said...

What you say is true, and we are aware of that. If an application is using e.g. a SmartCursor and does not check whether the interface is supported, it indeed will crash sooner or later.

On the other hand, the API is so much broken (see kwrite-devel archives for more information), it's simply near to impossible to fix the implementation correctly. The correct fix in this case are the Moving* classes.

KatePart really has a lot of crashes right now (maybe some users do not experience them, but they exist), and almost all backtraces lead to Smart* handling. We have again and again tried to fix it ourselves, but we simply don't understand all the code (no, we are not too dumb :) )
We also wrote mails to the developer who wrote all that Smart* stuff. I almost never got a reply...

Having said that, the current state is simply not bearable either.

The decision to drop Smart* is not something we did just by random choice. It came to that because of the reasons mentioned above, after years of discussions...

I'm not happy either with the solution. Technically it's a clean solution. But you are indeed right: As KTextEditor interface user you might have to say: This version works up to KDE 4.5. Then KDE 4.6 with the new version is required.

This is suboptimal, indeed it sucks. But this is how it will be.

> I'm sure this problem could be solved
> in a compatible way [...]

We tried. For years. The answer is most probably "no"... I did not write "this might kill Kate" just for fun.

panzi said...

The question is who uses the KTextEditor interface? My guess would be just a hand full of FOSS KDE apps. Kate, KWrite, KDevelop. Does Eric4 use it or is it pure Qt? So it might even be possible to write an email to each and every developer who uses the interface.

I ask, who here uses this interface including the Smart* stuff?

dhaumann said...

http://lxr.kde.org. Search for SmartRange, SmartCursor and SmartInterface.

- kdevplatform (full of Smart*)
- kile (SmartRange in CodeCompletion interface. Very easy to switch.)
- kte_linter (playground, easy to switch)

Cullmann said...

@kevin:
There was never ever documented, that KatePart will implement the smart interface in the first place. If developers of 3rd party apps don't check for that, little can be done.

About fixing: I tried hard, but look at the API of it in ktexteditor, the original author exposed the complete internal structure, there is no way to fix anything. If you application doesn't use any watchers/notifiers but smart* stuff, than already that will lead to endless crashs in normal use, even if single threaded. That is for me unacceptable and atm the state of art for KDevelop: it somehow works, most times, but sometimes just eats your document and crashs, because the smart* stuff can't be used right.

The whole interfaces stuff was designed to exactly allow this: BC extension and changing of the stuff the editor component exports to the outside world. If that is not allowed, the whole sense of the interfaces is really not there anymore.

Kevin Kofler said...

lxr.kde.org is not going to catch stuff outside KDE SVN. We all have no idea how much code uses these APIs outside of KDE SVN. KatePart is LGPL, not GPL, so the source code of the affected apps might not even be available. And where it is, you might not have found it. E.g. you haven't found the KTIGCC 2 development tree (which is the app I was talking about), even though it's sitting on SourceForge. But that app is a big API abuser (I'd recommend not looking at the code, you might undergo a heart attack if you do ;-) ) and the KDE 4 version (KTIGCC 2) is not released yet anyway, so I wouldn't worry too much about that one if it's the only one. I'm more worried about e.g. KDevelop/kdevplatform and Kile. There's also (among the stuff packaged in Fedora, which is easy to query for) Rkward and Kobby which use libktexteditor.so.4, but I haven't checked whether they're using Smart* interfaces.

dhaumann said...

Kobby: no Smart* at all
RKWard: Uses SmartRanges, without checking whether the SmartInterface is valid. Have already contacted the authors.

Btw, while it's indeed not possible to catch all KTE users, I'm pretty sure that the KTE interfaces are not used that much, especially not Smart*. Kind of unfortunate, but in this case even an advantage ;)

Btw, thanks for pointing me to RKWard.

dhaumann said...

Ah forgot: KDevelop and Kile developers are aware of it.

Kile only uses it in the CompletionInterface, which btw just indicates that the design of the CompletionInterface is also flawed ;)