Friday, November 14, 2008

Kate Internals: The Undo/Redo System

The Kate Editor Component (also called KatePart) has its own undo/redo system. It did not change much since KDE2 and basically it is very simple. Meanwhile there are classes for undo/redo support in Qt as well. In fact both systems are very similar. Let's focus on KatePart's system for now.

Text Operations

First we have to take a look at what actions need to be saved. In KatePart this basically comes down to
  • insert text or line
  • remove text or line
  • selection changes
  • (and a few others like wrapping a line)
When typing text, each keystroke inserts a character. This is exactly one undo/redo item. As example, typing a character 'x' creates a new undo item:
  • the content is 'x'
  • the type is 'insert text'
Undo in this case means 'remove x'. Redo means 'insert x (again)'. The undo/redo history is just a list (more like a stack to be precise) of simple edit actions.

KateUndo Items

In KatePart, an undo item is represented by the class KateUndo:
class KateUndo {
KateUndo (KateUndoGroup::UndoType type, uint line,
uint col, uint len, const QString &text);
~KateUndo ();

bool merge(KateUndo* u);

void undo (KateDocument *doc);
void redo (KateDocument *doc);

inline KateUndoGroup::UndoType type() const;

inline uint line () const;
inline uint col () const;
inline uint len() const;

inline const QString& text() const { return m_text; }

Item Merging

Note the function KateUndo::merge(KateUndo* u); This functions merges two undo items of the same type if possible. For instance, typing 'hello world' inserts one undo item for every character, i.e. 11 undo items of type 'insert text'. Kate merges those 11 items into only 1 item with the string 'hello world'. Merging leads to less KateUndo items (less memory) and faster undo/redo replaying.

Item Grouping

What's still missing is the possibility to group several undo items together. Imagine you have selected the text 'hello world' and paste the text 'cheers' from the clipboard. What happens is this
  1. remove selected text
  2. insert text from clipboard
So there are two undo items of different type. They cannot be merged into only one KateUndo item. Though, we want to support undoing both items in one go, that's why we add several undo items into undo groups. In KatePart, this is done by the class KateUndoGroup:
class KateUndoGroup
explicit KateUndoGroup (KateDocument *doc);
~KateUndoGroup ();

void undo ();
void redo ();

enum UndoType { ... };

void addItem (KateUndoGroup::UndoType type, uint line, uint col, uint len, const QString &text);

void setUndoSelection (const KTextEditor::Range &selection);
void setRedoSelection (const KTextEditor::Range &selection);

void setUndoCursor(const KTextEditor::Cursor &cursor);
void setRedoCursor(const KTextEditor::Cursor &cursor);

bool merge(KateUndoGroup* newGroup,bool complex);

void safePoint (bool safePoint=true);
Every KateUndo item belongs to one KateUndoGroup. A KateUndoGroup can have an arbitrary count of KateUndo items. In the example above we want to group 'remove selected text' and 'insert text' together. Grouping can be explicitely done in the code as follows (simplified version):
void KateDocument::paste ( KateView* view, QClipboard::Mode mode )
QString s = QApplication::clipboard()->text(mode);

insertText(pos, s, view->blockSelectionMode());

Grouping: editStart()/editEnd()

The call of editStart() tells the document that an edit operation is running. All text operations are added to the current KateUndoGroup, until editEnd() is called. editStart() and editEnd() do reference counting, i.e. editStart() can be called nested as long as for each call of editStart() there is (finally) a call of editEnd().

Grouping: Cursors and Selections

Undoing the paste-action above should restore the selection if there was one previously. Redo (i.e. paste again) should remove the selection again. So there are two different types of selections: one before the undo group, and one after. That's why each undo group has the functions setUndoSelection() and setRedoSelection(). The same applies for the cursor position: We have to store two different cursor positions, one for undo and one for redo.
For instance, imagine we removed the text 'world'. Undo (i.e. insert 'hello') should set the cursor position to the end of 'hello'. Redo (i.e. remove 'hello') should set the cursor position to the start of it.

Luckily a programmer does not have to set the undo/redo cursor positions and text selections manually. undoStart() is called the first time editStart() is called. The closing editEnd() finally calls undoEnd(). So undoStart() sets the undo cursor position and undo text selection, while undoEnd() sets the redo cursor position and redo text selection.

Group Merging

The careful reader might have noticed KateUndoGroup::merge(). So merging of two groups is also supported. Whether text operations should be merged into an existing undo group can be controlled with KateDocument::setUndoDontMerge(). Pasting text for example set's this flag.

Undo and Redo

Every document in KatePart has two lists: An undo list, and a redo list. Suppose we have 10 KateUndoGroups in the undo list and the user invokes undo 4 times. Then the undo list only contains 6 items and the redo list 4. Now it is also possible to redo. However, typing text clears the redo list.

Document Modified Flag

KateDocument::updateModifed() is called to update the modified flag of a file. This update also relies on the current active undo group. Saving the file saves a pointer to the current undo group, and later we simply can check whether the current undo group is the active one. Pretty simple mechanism. However, there right now seems to be a bug you can reproduce as follows:
  1. save doc [not modified]
  2. type a character [modified]
  3. undo [not modified]
  4. type a character [modified]
  5. undo [still modified]
Step 5 is incorrect, as the document is not modified here. Maybe now you have enough knowledge to fix this. Any takers? :)

Thursday, August 14, 2008

Akademy 08: Kate Flashback

This Akademy's Kate changes include
  • fix: drag & drop of text
  • code completion: only show group header if the group name is not empty
  • reintroduction of buffer blocks in Kate's document buffer (one buffer contains up to 4096 lines). The blocks build a linked list. Editing a 500 MB file kind of works now again. It's still rather slow, though.
  • more speedup in Kate's document buffer
  • Kate is using KEncodingProber instead of KEncodingDetector now
  • generate internal version of KatePart automatically, so developers don't have to adapt it manually each release
  • python encoding detection plugin that warns if encoding is not correct while saving
  • new plugin: Backtrace browser, mainly for developers
  • find in files: several speed optimizations
  • find in files: progress indicator while search is active
  • find in files: redesign of workflow. Search happens with non-modal dialog and results are shown in toolviews.
  • lots of vi mode changes
  • lots of bugs closed, mainly old ones
  • some real bug fixes...
  • things I forgot

Tuesday, August 12, 2008

Kate: Fast backtrace navigation

I've added a new plugin to kdesdk/kate/plugin: a backtrace browser. It's meant for developers and probably of no use for users. What does it do? It shows a backtrace delivered by gdb in a listview in a Kate toolview. Clicking on an item opens the selected file and jumps to the correct line number. It works for backtraces generated on your own machine, but it will also work for backtraces from other people, i.e. with /home/dummy/qt-copy/.../qwidget.cpp will still be found on other machines. For that to work, you have to index the directories where the source code is located.
Sometimes there are several files with the same name, e.g.
  • trunk/kdegraphics/okular/generators/dvi/config.h
  • trunk/kdepim/mimelib/mimelib/config.h
To pick the right choice, the plugin picks the last two parts of the url, in this case this would be
  • dvi/config.h
  • mimelib/config.h
and then usually finds the correct one. Indexing trunk/KDE and branches/KDE/4.1 of course will lead to a clash, now way to fix it. Maybe I could present a list of valid files to the user and let the user pick the right one. I don't think that's necessary though for now.

How to configure
  1. Enable the plugin: go to Settings > Configure Kate > Application Plugins and enable 'Kate Backtrace Browser'
  2. A config page appeared, so click on it and add the directories containing the source code
  3. Clicking OK will start indexing. It will take some time (the index of kdesupport + kdelibs + kdepimlibs + kdebase + kdesdk + playground/plasma + plasma-addons + kdevplatform + kdegraphics is about 6MB)
When indexing is finished, open the toolview "Backtrace Browser". Now you can load a backtrace from the clipboard (e.g. when you clicked "Copy to Clipboard" in Dr. Konqi) or from a file.

Hope it's useful :)

Sunday, July 06, 2008

C++ Template magic

Now that Johan talked about why the STL simply rocks I have to add a quick note about C++ templates in general, to be precise about template specialization. I've recently written a ring buffer template, something like
template <class T, int TSize>
class RingBuffer
// ...
void append(int count, T* first);
std::vector<T> buffer;
int start;
int end;

template <class T, int TSize>
start = 0;
end = 0;

template <class T, int TSize>
void RingBuffer<T,TSize>::append(int count, T* first)
// code omitted: make sure count elements fit, otherwise return
// now there are two cases: either count elements fit completely,
// or we have to wrap around at the end of the ring buffer.
// the case of a wrap around is ignored here, too

copyHelper(&buffer[start], first, count);
Now the function copyHelper looks like this:
template <class T, int TSize>
static inline void copyHelper(T* dest, T* src, int count)
while (count--) {
*dest++ = *src++;
copyHelper simply assigns count elements with the operator=(), as T can also be a class. But in the case of T being e.g. a simple char this code part performs really bad. However, there is a solution: Template specialization. That means, we add another function copyHelper() and the compiler then is clever enough to pick the correct one:
template <>
static inline void copyHelper<char>(char* dest, char* src, int count)
memcpy(dest, src, count);
Now the code is really fast in the case of char. In other words, with template specialization we can heavily tune template code in a lot of cases. And ideally, STL implementations do exactly this, don't they? Does Qt use template specialization for its template classes?

Saturday, May 31, 2008

"I miss the applet which shows system usage" one of the comments on Sune's blog. "I won’t call it a a must-have, but I’d love to have it back :D". Well, I call it a must have, that's why I've ported it to KDE4 a week ago:The code is not in svn yet (here is the code for now). I still had issues with correct resizing and believe there was also a bug in the plasma lib when I developed it which seems to be fixed now. I didn't have time for more testing, but finally this has to go in for KDE 4.2 :)
Besides that, I'm not yet content with how the data engine publishs data. The situation is that all system monitor data is extracted in one tick, but I still would like to publish it in three categories: cpu, mem and swap. But if I do so, an applet's dataUpdated() function is called 3 times and that's not what I want. So for now I put the data into the category systemmonitor and named the items cpu-total, cpu-kernel, ..., swap-total, swap-used, mem-total, mem-kernel, mem-cached, ... However the other way of categorization would be better :) Any ideas?

Tuesday, April 22, 2008

Offline for 3 months

I don't have internet the next 3 months. Maybe here and there at some point. That means I can not review the techbase changes. Also, I'll be rather silent wrt kate/kwrite.

Wednesday, April 16, 2008

Do you understand the word HTML?

During the Kate developer meeting we also thought about simplifying KWrite and how to make the decision whether KWrite should be launched in full featured mode or in a stripped version. ...well, and we found a really funny idea:

Note, that this would even work, the question would be rather annoying, though :) The solution right now is to always start KWrite in a simple mode. Mostly only actions are hidden in the menus (@distributors: kdelibs/kate/data/katepartsimpleui.rc), but you can also change c++ code at Kate part level, as there are some functions:
  • bool KateDocument::simpleMode() (kate part internal), and
  • bool KTextEditor::Editor::simpleMode() (along with setSimpleMode())
This way config dialogs can be adapted depending on the mode as well. Ah, and if you want the normal mode back, go into the KWrite settings and enable [x] Enable Developer Mode. Then restart KWrite.

PS: Tackat, we came up with this image before our phone call. That's why it was really funny when you said HTML is something that should not be removed. hehe... :)

Tuesday, April 15, 2008

Kate Meeting: Day 1 and 2

The Kate Developer Meeting was a productive weekend and once more shows how important the developer sprints are. The summary will be on the dot shortly. Work already started on several topics. As everyone want screenshots, here we go: The new annotation interface available now in KTextEditor can be use to e.g. show svn annotations directly in kate:
basysKom's coffee maching is simply the best: It can do everything, you just have to press the right key combos:

Friday, April 11, 2008

Kate Meeting: Day 0

Finally it all begins: Anders and Joseph arrived at basysKom and we've started to discuss some things we want to do for KDE 4.1. Later, we are going to meet with the rest of the attendees in a restaurant to get to know each other. The official start of the meeting is tomorrow morning. If you are interested in contributing to Kate, just join #kate on I'm looking forward to the next two days :)

Wednesday, March 19, 2008

How to compile and run KDE4

...or rather how to setup a KDE4 development environment. There already is a howto on techbase, but I'm using my own scripts since years, and they work just fine. I've made them public in my user space on techbase: User:Dhaumann/Compiling KDE4. The howto is very short but complete. It does not have any troubleshooting sections. This is intentional: If you have any errors, fix them and rerun the scripts. Happy compiling :)

Wednesday, January 30, 2008

Feature Plan on TechBase

The Planned Features list is up and running again. It just needs to be filled. If you are a KDE developer you should consider to add your planned features to the list :) There are three templates you can use:
  • {{FeatureDone|project|description|email-address|first-name name}}
  • {{FeatureInProgress|project|description|email-address|first-name name}}
  • {{FeatureTodo|project|description|email-address|first-name name}}
Another todo-item now is to merge the old feature lists into techbase.

Monday, January 28, 2008

Growing articles on TechBase

Right now TechBase has content in 19 languages. Sometimes articles grow bigger over time. How to build KDE4 is the prefect example. Here is a list of pages about building KDE4 (not counting translations):
  • Getting Started/Build/KDE4
  • Getting Started/Build/KDE4/Arch Linux
  • Getting Started/Build/KDE4/Ark Linux
  • Getting Started/Build/KDE4/Cygwin
  • Getting Started/Build/KDE4/Fedora
  • Getting Started/Build/KDE4/FreeBSD
  • Getting Started/Build/KDE4/Gentoo
  • Getting Started/Build/KDE4/Kubuntu and Debian
  • Getting Started/Build/KDE4/Mac OS X
  • Getting Started/Build/KDE4/Mac OS X 10.5 issues
  • Getting Started/Build/KDE4/Mandriva
  • Getting Started/Build/KDE4/Prerequisites
  • Getting Started/Build/KDE4/Troubleshooting
  • Getting Started/Build/KDE4/Windows
  • Getting Started/Build/KDE4/Windows/3rd-party libraries
  • Getting Started/Build/KDE4/Windows/Building DBus
  • Getting Started/Build/KDE4/Windows/Building KDESupport Libraries
  • Getting Started/Build/KDE4/Windows/Building Qt 4
  • Getting Started/Build/KDE4/Windows/Environment
  • Getting Started/Build/KDE4/Windows/GCC And MinGW
  • Getting Started/Build/KDE4/Windows/Littlecms.patch
  • Getting Started/Build/KDE4/Windows/MS Visual Studio
  • Getting Started/Build/KDE4/Windows/MinGW Build Tips
  • Getting Started/Build/KDE4/Windows/Windows Vista
  • Getting Started/Build/KDE4/Windows/additional libraries
  • Getting Started/Build/KDE4/Windows/emerge
  • Getting Started/Build/KDE4/kdesvn-build
  • Getting Started/Build/KDE4/openSUSE
  • Getting Started/Build/KDE4 Alpha 1
  • Getting Started/Build/KDE4 Alpha 2
That makes 30 pages. Some thoughts about this. Splitting up articles makes translation more difficult. There are more pages that have to be synced. It can be unclear where to find the information you are looking for. It's messy. What about
  • 1 page »Distribution Specials«, instead of 11 separated pages?
  • a cleanup instead of a split, if the page grows more and more?
  • talk pages sometimes fit better?
Agreed, if pages really get long, a meaningful split makes sense. But sometimes it does not!? Thoughts? :)

Sunday, January 27, 2008

TechBase: Contributing...

How you can help to make maintaining TechBase easier:
  • login before you edit pages. Reviewing an edit of a logged in user is often as easy as "ah, user X, his content is ok anyway, next one..."
  • do not use the "I-form". Who is 'I'? Noone knows. Especially not years later. Using 'I' in talk pages is perfectly fine. But please avoid it in articles :)

Monday, January 07, 2008

Reviewing TechBase Changes

KDE's techbase wiki is pretty much alive and I'm especially surprised that the translation system works really well. Of course there is some maintenance work to do and I'm reviewing every change so far.
I was away from Dec. 27th until 4th of January. Unfortunately, the "recent changes" feature allows me to see only the changes from 1st January till today. So if you have the RSS/Atom feed please review the changes from 27th until 31th of December and fix spam/typos/whatever you think needs to be fixed! :)