Text Editor: Data Structures

In a low-level design, your editing operations would be poking at the data structure directly. There, the simplicity of a gap buffer is a pretty big win. I agree in this environment ropes are too complicated. However, I don't see any good reason to architect a text editor in this way. Use abstractions.

The linked article contains a factual error, the referenced Crowley paper does not consider ropes. Thus it cannot be used in support of the argument that piece tables outperform ropes.

There's one other important concern with piece tables I didn't see addressed. It depends on the file contents on disk not changing. If your file system supported locking or the ability to get a read-only snapshot, this would be fine, but in practice most don't. It's very common, say, to checkout a different git branch while the file is open in the editor. Thus, the editor must store its own copy to avoid corruption. In the long term, I would like to see this solved by offering read-only access to files, but that's a deeper change that can be made piecewise.

The authors of the dozens of tiny editors using this "structure", which were quite popular on the PC in the late 80s through early 90s, would disagree. A memcpy/memove() runs at many GB/s on a typical machine today, so you would have to be editing absolutely huge files to notice. Even back then, memory bandwidth was a few MB/s --- still plenty fast, considering that the typical files of the time were also much smaller.

I can remember a time when I was attempting to write my own editor and at first spending a lot of time obsessing over the data structures (it was harder to find such information at the time) --- only to realise that a lot of the editors I'd tried, including the one I was using the most at the time --- were working perfectly well with just one big buffer.

I've opened files of a few hundred MB in Windows' Notepad, which also belongs to this family of editors; and on a machine a few years old, opening the file takes the longest because it has to be read into memory --- once it's opened, moving around and editing lines doesn't show much lag at all. "Worse is better", indeed.

The upsides are the same as for a piece table (really simple undo/redo) but with the downside of not being able to just mmap a file. You also get basically zero memory usage when you do cut and paste (you can paste a file into itself until it is bigger than RAM without problems, since you are actually not copying the contents, just the pointer)

Look at the YouTube video as well. It is all very cool, at least if you are not already spoiled by using clojure :)

https://github.com/arximboldi/immer/blob/master/README.rst

Edit: Forgot to mention: Ewig can be found among Immer's author Arximboldi's repos. On my phone right now on GPRS connection, so maybe another friendly soul can provide the link.

Even though we do load the entire file into memory (as opposed to mmap-ing the file), the piece table design is still very useful. It makes it very cheap to compute the buffer's current unsaved change set, which is a value that we periodically serialize for crash recovery purposes (similar to vim's `.swp` files).

It's also just a very compact way to store a large chunk of text, which is good from a cache-locality and memory usage perspective.

[0] https://github.com/atom/superstring/blob/master/src/core/tex...

Basically the idea is, the inner nodes are a 2-3 tree which track the size of each child like a rope does. The leaves are gap buffers of a fixed size (a few cache lines), which, when full, split into two like leaves of a B+tree. So you get the dense-ish packing of a gap buffer with the O(log n) performance guarantee of a 2-3 tree, while avoiding the potential linear copies associated with ropes and gap buffers.

(I know this is overkill for a toy text editor but it wouldn't be a side project if it weren't!)

1. Multi-line regular expressions. Typically the regex library is given an array of text to search in (). We have no such buffer to give.

2. Line wrap. Adding or removing a single character near the top of the file might require the entire file to be re-wrapped. You need to complete the wrapping process before you know how many lines are in the buffer and therefore can update the size and position of the vertical scroll bar's handle.

3. Column mode editing of text containing tabs.

Beyond those features, these data structures (gap buffer and piece table) don't seem well suited to operations that effect the entire buffer, such as convert-tabs-to-spaces.

At least when I used PCRE, it seemed to require this.

Buffer of X is a BackwardsList of X, Cursor X, ForwardsList of X

So if you make Line a Buffer of char and your document a Buffer of Line you can easily insert and remove characters on a line or lines in the document.

If you wanted to move the cursor forwards you could just place the cursor onto the head of the backwards list behind you and take the head off the forwards list in front of you to be your cursor.

Probably because there's no elegant way to support all the potential edge cases of that default behavior. For instance, if you introduced a reference with that format, you can't refer to it later - if you use the static number and it changes, you're now pointing to the wrong reference. So it reduces to using names, and the hassle of coming up with a name for each new link or footnote reduces to just using numbers - so the only thing that needs to be supported is manually named or numbered items.

The author correctly describes the ideal solution - a plugin that replaces unnamed links before saving or such - but likely fails to understand why that (as opposed to adding behavioral cruft to a markup language) is the correct level of abstraction for such a solution. Imagine if a project like wikipedia was riddled with the ambiguity of dozens of people's various attempts to wrangle the autonumbering to their writing.

  #include <stdlib.h>
  #include <string>
  using namespace std;
  
  int main(int argc, char **argv)
  {
    size_t size = (size_t)atol(argv[1]);
    string editor_buffer(size, 'x');
  
    for (int iter=0; iter<100; iter++) {
      editor_buffer.insert(5, "foo");
    }
  }

It's two stacks head to head. Moving the cursor is popping on one and and pushing on the other. All the other operations were given too. There were the category diagrams and everything -- the meat of which I've forgotten but I might be able to find if anyone is interested.

My particular use case required that I parse whatever was written in the editor in a few ways: a lexer pass for syntax highlighting and a full parse for semantic feedback (much of which is provided somewhat unpredictably from AJAX calls, for various reasons). And I knew that touching the DOM (which I'd have to do to keep the syntax highlighting/semantic feedback up to date) is typically going to be a lot slower than doing a few thousand loop comparisons in JS.

I looked into structures like ropes and whatnot that would enable fast edits, but I realized that in the end I wasn't going to do better than linear in the worst case, for a few reasons, e.g.: 1. Suppose the user enters an open quote at the first character: every other character just flipped from outside a quote to inside or vice versa and I'm going to have to re-parse the whole document to update my semantic analysis (and syntax highlighting, though that would only require a partial re-parse). 2. Edits that change the line number associated with errors are going to require me to update that display and you can make a document with a number of errors that grow linearly, so entering a newline at the first character was potentially linear...

So I ended up just using a doubly linked list of tokens (as returned by the lexer) and re-lexing tiny sections around a cursor when the user enters text. Collectively the whole thing turns out linear and but it saves a ton of work by re-using the same structure when I'm doing parsing and semantic analysis. Doing it this way let me do my own DOM reconciliation and update the absolute minimum number of DOM nodes for every edit, which ultimately has a huge effect on performance because touching the DOM is expensive. And one can set this up so that (at least from the lexer's perspective) undo involves just snipping the old middle segments of the list back into place.

So it turned out that higher level requirements (eventually having to actually parse the text and update the display in various ways) made it so I wouldn't really save any work optimizing at the low level.

    -- A Piece is a String, start, and end.
    data Piece a = Piece { list :: [a] -- 'a' will be 'Char' later, but we can support any type here.
                         , start :: Int
                         , size :: Int
                         } deriving (Show)

    -- Pieces are Monoids, like Lists, Trees, etc.
    --  note that the type declarations here are not allowed (Monoid defines them already). I put them there for your leisure.
    instance Monoid (Piece a) where
        -- mempty is an empty Piece.
        mempty :: Piece
        mempty = Piece mempty 0 0
        -- mconcat takes a list of Pieces, and condenses them into one Piece.
        mconcat :: [Piece] -> Piece
        mconcat = foldl mappend mempty
        -- mappend takes two Pieces, and puts them together, resulting in one Piece.
        mappend :: Piece -> Piece -> Piece
        mappend (Piece firstList firstStart firstSize)
                (Piece nextList nextStart nextSize) =
                    let start = fst $ splitAt nextStart firstList
                        middle = nextList
                        end = snd $ splitAt nextSize firstList
                    in Piece (concat [start, middle, end]) firstStart firstSize

    type Buffer = [Piece Char]

    -- replace creates a new Piece, and appends it to the Buffer.
    replace :: String -> Int -> Int -> Buffer -> Buffer
    replace text from to buffer = buffer ++ [(Piece text from to)]

    insert :: String -> Int -> Buffer -> Buffer
    insert text at = replace text at 0

    delete :: Int -> Int -> Buffer -> Buffer
    delete from to = replace "" from to

    bufferText :: Buffer -> String
    -- mconcat folds our Pieces together, resulting in one Piece
    -- list gets the Piece's "list" (String = [Char] in Haskell)
    bufferText = list . mconcat

    >>> buffer = replace "Hello" 0 7
               $ insert ", world!" 7
               $ insert "Goodbye" 0
               $ mempty

    >>> bufferText buffer
    "Hello, world!"

At that time I used a double link list like structure with a line cursor to help with list traversal.

While this was not one of the formal text editor design patterns, I found that pattern very worked well.

I’m sure there is something very wrong with using mmap and I can probably find the answer with just a google search but it would have been great if it was covered by the article.