Re: line buffer as Red Black Trees instead of linear

[Alin Soare]

2014-05-21 18:17 GMT+03:00 Eli Zaretskii <address@hidden>:

> Date: Wed, 21 May 2014 11:34:10 +0300

> From: Alin Soare <address@hidden>
> Cc: Stefan Monnier <address@hidden>, address@hidden
>

> Ideally, at each node all the text should have the same properties (marks,
> fonts, etc), and chaging 1 such property can be implemented by splitting
> the node or removing a few nodes, and their text be preserved in 1 node
> (only the field owner must be changed when a few nodes are joined in only
> 1).

That would mean we will need to rearrange the tree each time text
properties or overlays change, something we avoid today.

Yes, each time ! But however, a simple mental computation is still much faster than now, because the computation is made only 1 for each change, and there will be lots of simple pre-computations that never repeat. Not all the attributes will be pre-computed at the creation of the node. Some attributes, like # of newlines on the text at the left of the node and on the self will be precomputed at the creation. The Node->marks will be perhaps precomputed when some mark is added in the text within the node. Display props are pre-computed when the redisplay-internal requires it, so kind of lazy.

Also please note that 'display' properties can specify that Emacs
displays something entirely different from buffer text, so the display
engine will still need to consult Lisp strings, in addition to the
text.  (Yes, it's lots of fun.)

What is displayed will be all the time pre-computed for each node, and this will never be re-computed for that node before modifications. The attribute NODE->what-to-display-data perhaps will be evaluated at the 1st display, not at the node creation.

Note also that I will do such that each node keeps not a block of text, but a linked list of blocks of text, such that to be fast to manipulate operations like join and split.

Apart from search in buffer and reading the text at a given offset(point), that will be a little slower because the problem of page cache, all the other functions will be faster (at a first sight).

We will see. When i start working, I will send you private message to ask you to read what I did. Try since October on to do it.