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.
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.