Re: Future of display engine and lines

[Alexandre Garreau]

Le jeudi 28 octobre 2021, 14:19:41 CEST Richard Stallman a écrit :
> [[[ To any NSA and FBI agents reading my email: please consider    ]]]
> [[[ whether defending the US Constitution against all enemies,     ]]]
> [[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> 
>   >   > > It could have multiple segments for each display line, and
>   >   > > fill up
>   >   > > one series of segments going vertically down from point A,
>   >   > > then the next series of segments going vertically down from
>   >   > > point B,
>   >   > > and so on.

> I am thinking about non-graphics terminals.  For graphics terminals,
> the data structure will have to be different.  (They already use a
> different data structure.)

I think both need to use a tree, afaik even ncurses uses a tree for such 
things.

> The point is, there is no need to change the representation of buffers.
> 
> 
> In principle there might be a more efficient representation of
> buffers.  But I am skeptical about that.  When I tried to look for a
> better representation that would allow for multiple gaps, I couldn't
> see a good answer about how to use them and gain any benefits.

The question is not to have multiple gaps (although that would actually be 
useful for some extensions like multiple-cursors (which btw is pretty nice 
and emacs is the only editor to support that)), but to fragment the buffer 
differently than as a stream.

We’re talking about making it a tree.  It does not have to be a binary 
tree of course (most graphical trees aren’t), and insertion as well as 
lookup should be as fast as possible, since it’s for editing, so a gapped-
array is still useful, what would be useful is instead to store chars in 
that array, rather store some recursive datastructure that could be either 
again this gapped-array (possibly with metadata such as vertical/
horizontal direction), either something else (a character, an image, any 
kind of weird-behaving space/glue, etc. like TeX, like TeXmacs, like any 
web engine, like LibreOffice).

So it would be recursive gapped-arrays, that’s different from a gapped-
array of chars, but there still is one gap, and it works similarly, but 
the functionality is different: it also stores some fragmentation of the 
content (possibly none, in the case of plain text).

> I am simply trying to argue that the buffer representation and the
> redisplay algorithm are modularly separate.  We can keep the issues
> separate and this issue much simpler.

Modularly in the sense our problem is solvable without having to change 
the buffer datastructure.  But that’s merely because the improvement 
proposed doesn’t change functionality but efficience, they would merely 
provide a sort of “cache” for certain functions.  It would theorically 
possible to keep everything modular by “advicing” (not with elisp advices, 
sorry for the confusion, but the comparison comes to my mind) the C 
datastructure of the buffer with some other separate (hence “modular”) 
datastructure that’s only used by redisplay, and stores some computation 
whose value is strictly related to the buffer’s content and its semantic.

But that’s rather hairy and academic to do.  We could just as well 
complexify a little the buffer datastructure, or, like I proposed, 
introduce some new datastructure *in addition* to the legacy buffer, that 
could be used instead, and be more efficient for graphical redisplay, 
notably for tree layouts (something non-linear and more complicated than a 
2D grid of columns × line).

And anyway we should store some semantical information (= functionality), 
somewhere… but where would you want to store that? within text properties? 
with markers (aren’t they slow?)? we’re not anymore talking about 
something that’s inconvenient splitting and then rejoining ambiguously, 
such as face, but a real tree (because we could have (that’s hairy but 
imaginable) a multicolumn at the middle of one column of a multicolumn), 
here emacs need a tree, just as a DOM, just as with overlays, but efficient, 
and very very important to redisplay.