Tutorials on Windows programming, including a Win32 text editor series, piece chain data structures, device drivers and small utilities.
HN commenters recommend its Neatpad and piece chain tutorials as a good way to learn text editor internals, including undo and redo.
> Furthermore in ropes every leaf spans one character,
The Boehm paper on ropes[1] (which is about the only academic literature on the subject that I know of) does not do that (and explicitly suggests one should not), nor does any real-world implementation, (e.g., the Boehm implementation, SGI's impl) do that. It would be incredibly inefficient, and for no real gain.
A good rope implementation will store an array of characters/bytes in the leaves, up to some threshold.
> Furthermore with ropes, every operation returns a new rope data structure, that means ropes are immutable.
There is nothing inherently immutable about ropes, and it is certainly possible to mutate a rope. (For example, appending a single character to a leaf with space is much quicker if the rope as a whole is mutable.)
Look at the SGI implementation for an example here; their reference docs[2] contain sufficient details to see that the rope itself is mutable.
Now, a rope typically just describes a sequence of characters. It is entirely possible for a leaf node in a specialized rope to reference on-disk content, and other leaves to reference in-memory content. In that regards, it can be like a piece table. Implementing an undo/redo on top of a rope is less straight-forward; whereas a piece table's undo history can essentially share large portions of the linked list (see the lovely diagrams here[3]) I'm not sure the same can be done on a Rope's tree, due to the tree's need to balance and re-balance. That…
I think implementing a simple text editor with undo/redo support is a worthwhile exercise for everyone to do at least once in their career. It's a great example of something that on first glance seems simple, but has quite a bit of subtlety especially when you get into styled text.
Piece chains are another good data structure to know for this application, though their implementation is more complex than a gap buffer. See http://www.catch22.net/tuts/piece-chains for a nice tutorial.
Also worth reading for insight and motivation is the 1985 CACM article "Concepts of the text editor Lara" by J. Gutknecht.
The article is missing one of the important but commonly overlooked structures: a "piece chain" [1] (aka "piece table"). Not easy to find editors using it, especially among the popular ones, but:
- from what I've read somewhere, MS Word was/is (?) using it internally [http://1017.songtrellisopml.com/whatsBeenWroughtUsingPieceTables, ]
- AbiWord [1]
- [1]: http://www.catch22.net/tuts/piece-chains
- https://github.com/martanne/vis
- the text editor of the Oberon OS used it [1]
One of its most intevesting advantages is that it trivially supports fast unlimited and persistent undo/redo
I really enjoyed typing along with this 3-part series: https://www.youtube.com/watch?v=oDv6DfQxhtQ
Per writes the beginnings of an emacs-inspired Windows (directwrite) text editor.
I want to continue developing it, but have no idea what to do regarding design... I'm considering using Sublime's themes.
Another interesting tutorial: http://www.catch22.net/tuts/neatpad
I'm surprised there isn't much discussion of data structures here, as that would inform an undo algorithm.
I infer from 'PieceTree'
That this is a binary tree based piece chain.
That makes undo really easy, especially character by character.
Nice explantation of piece chains
https://www.catch22.net/tuts/neatpad/piece-chains/
Sysinternals has a Windows equivalent[1]. Although most of the hex editors[2][3] have an in-built strings dumping functionality.
[1] https://technet.microsoft.com/en-us/sysinternals/strings.aspx
[2] https://www.safer-networking.org/products/filealyzer/
[3] http://www.catch22.net/software/hexedit