Re: Lua and text-representation

[Mark Hamburg <mark@...>]

On Mar 1, 2010, at 9:35 AM, Gavin Wraith wrote:

> In message <20100301131708.A27240@lua.tecgraf.puc-rio.br> you wrote:
> 
>> Try ropes: http://en.wikipedia.org/wiki/Rope_(computer_science)
> 
> A bit expensive for this purpose I think :).
> What got me thinking was that "Edit", a texteditor which Acorn
> Computers Ltd built into the ROM of the Archimedes back in the 80s,
> used the double (before/after cursor) buffer datastructure, together
> with a sliding heap. If Lua is to be embedded in such an application
> it would be nice to use the memory allocation that comes with Lua.
> In that case one might use two lists, one indexing forward from the first
> character to the last before the cursor, the other indexing backwards
> from the last character of the text to the one immediately following the
> cursor. Moving the cursor then means sloshing top elements from one
> list to the other. I had thought of trying to avoid reallocating new
> lists by adding in a bit of laziness to the sloshing process. Have
> lists-with-index, replace removal from the list by decrementing the
> index, and allow list-items above the index to be overwritten before
> the index is incremented.
> Thanks for the references provided. This is all probably a standard
> computer science exercise, but then I never did a degree in computer
> science; there was no such beast when I was a student.

I think that approach is basically known as a gap buffer. You store your text in one big buffer with a chunk of text, a gap, and the remainder of the text. Insertion at the beginning of the gap is cheap. If you aren't at the beginning of the gap, then you need to slide some text from one side of the gap to the other. If the gap closes up, you need to grow the buffer. Conceptually, it's simple and fairly easy to manage. You can get by with a C API that looks something like:

	Err Buffer_insert( Buffer* b, int offset, const char* data, size_t length );
	Err Buffer_delete( Buffer* b, int offset, size_t length );

You can also do this with a single replace operation.

When reading out text, you need to take some care at the gap (which is unfortunately right where you are probably most interested in display).

Text markers can be stored as a mapping from marker ID to offset. A totally naive implementation just scans the list on every insert or delete and adjusts the offsets appropriately. The cursor is just another marker.

Sorting the list of markers can reduce the amount of update work to do, however, you probably want to then keep the cursor separate.

If the markers are sorted, you can also just store the distance from one to the next thereby reducing the update work when adding or removing a marker but making the logic more complicated.

The other thing you need to figure out with markers is whether they point to characters -- in which case what happens on a delete -- or do they point between characters -- in which case you need to specify whether they bind to the left or the right if there is an insertion at that location.

And then there's the matter of formatting the text which will generally require caching paragraphs and/or line breaks and may up the marker count faster than one would have otherwise expected thereby pushing away from the simple "scan all the markers and adjust the offsets" option to more complicated data structures.

One thing you could certainly do is build a gap buffer in C as userdata and then do all of the other logic in Lua. If that proves too slow, then start moving other pieces to C.

Mark