Okteta turned into Construction site for Undo/Redo

Almost done, almost done, just the missing final 5 %. Which are quite tough. And never decreasing, one thing done opens a new one, hey.

But still what has been done meanwhile is quite pleasing: After many years wanting to do it I finally simply started and tried a first primitive implementation of the data struture concept called “piece table” as the backend for the undo/redo mechanism of the bytearray model. Piece tables are also used by Abiword and QTextDocument. If you are interested for a start read e.g. the page Part 17 – Editing Text with Piece Chains by some James Brown, so I can omit any experiments in describing it myself.

The code is now with Okteta in KDE’s repository. It is pretty rough and has flaws. Like the cursor forgetting where it has been at the previous changes. That is one of the tough problems, because with multiple views there are multiple cursors, the bytearray document does not know about views, views can come and go, so who is in charge to care for the cursor positions and/or how to calculate them?

And dependencies. I tried to make the piecetable code unaware of the basic data structure (byte array for me), worked so far. Because others might want to make use of the code, too (interested? contact me). But now I see that there are data structures which travel more than one module boundary, like the list of changes (e.g. on multiple undo), which is emitted by the piecetable via the bytearay model to the bytearray view, so the later can do the cursor jumping calculations. Repacking lists is not what I like. And encapsulating by wrapping iterators looks like too much work. Sigh 😦

But other than that, things are looking good. There are already two controllers for undo/redo (or versioning), one classical, which embeds into menu and toolbar, and a (readonly) monitor, which sits in the sidebar and shows all versions. Both operate on the Versionable interface of the libkakao framework, so other document classes implementing this interface can share them (one day when libkakao is ready). The KByteArrayDocument class at least does now, and wraps things to the experimental KPieceTableByteArrayModel. That one still loads files completely in working memory. But once everything works the loading will be switched to memory mapping, so working with GB-sized files should be possible 🙂

For now: Stay away from editing with Okteta, it is broken again. Parents are in care for their children.

Standard screenshot following, presenting the latest achievements as described:
Happily undo and redo with Okteta, just not currently.

Update: Nick’s question made me dig a little. And I found it was almost exactly 4 years ago that I decided to try the piecetable approach, see this thread on the mailinglist koffice-devel. But it stayed on my TODO list until a week ago. Oh, and the PDF document of the paper by Charles Crowley in now available directly at his homepage, too.


3 thoughts on “Okteta turned into Construction site for Undo/Redo

  1. why do you think PT pattern is used for QTextDocument? if i’m not wrong, PT is useful when the file isn’t loaded into memory completely, which is not the case for QTD.

    The only reason I could think of is that it decreases number of reallocs.

  2. @nick: I think it is used for QTextDocument because I was told so some years ago. And indeed, they just call it QFragmentMap: http://websvn.kde.org/trunk/qt-copy/src/gui/text/qfragmentmap_p.h?view=markup

    Why PT pattern is useful also for completely-in-memory sequential data? Some years ago I got convinced by
    http://www.cs.unm.edu/~crowley/papers/sds/sds.html (Update: misses all graphics, better use PDF mentioned above in the text) and since then have not thought about it 😉

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s