Catch22

Neatpad https://www.catch22.net/tuts/neatpad This is a series that I used to follow as I too wanted to implement my own text editor to learn the underlying architecture.

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.

> 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'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/

That reminds me of this tutorial for writing a text editor (in win32 land): http://www.catch22.net/tuts/piece-chains

You could check out http://www.catch22.net/tuts/neatpad It is Windows specific but very informative.

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

I also tried to figure out how some parts of the editor work and why they are so fast, but I couldn’t figure out much from the assembly. Those who are interested in text editor design may find this series and the links therein useful: http://www.catch22.net/tuts/neatpad

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

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

Catch22 has an article about this that goes pretty in-depth. http://www.catch22.net/tuts/piece-chains I would guess that the rope data structure has probably displaced the piece chain in new projects.