Future of display engine and lines

Future of display engine and lines

[Alexandre Garreau]

I’ve a question.

Given these time I see some discussions about the display engine (notably 
faces, svg, pointer drawing, and more in-emacs GUI discussion, etc.), and 
I’ve already seen ---without prior work--- ambitious suggestions seriously 
made here before (like to make emacs a text processor on par with 
LibreOffice (or, who knows, GNU TeXmacs ;))), as well as ---without 
ambitious suggestion--- ambitious work seriously made such as integrating 
gtk widgets…

Given eww is pretty advanced for what it is (an one-man browser made as an 
extension (instead of the opposite) and likely one of the most advanced 
textual www browsers out there)…

How difficult would it be for emacs to support in-buffer multiple columns? 
such as LibreOffice would be able to.  Such as it is necessary for a more 
readable and usable web browser (eww actually supports columns but the 
same line of two different columns is on the same line of the buffer, so you 
cannot move linearly with text nor select consistently linear text (like 
on some broken pdf viewers)).  Such as it would make waaay more usable 
multiple-lines row in the org-mode tables.  Such as it would make reading 
on emacs, without having to use several windows, way more efficient compared 
with the useful usage ratio of the screen surface (given an optimal line 
is 66 chars or (unless reading boustrophedonly) moving eyes at each time 
because more tiring and make more time lost)?

Would it even be relevant? or would something such as “displaying one 
window/buffer inside another buffer/window” be more useful?

And how would it be to support multiple-lines inside one line, such as 
with fractions?  The concept looks similar to me: you need to cut a 
graphical line in the first case, and a logical one in the later.  I don’t 
know how the line/column/point-pos would be calculated in such a 
situation.  What I’d like is the ability to see a well-layouted fraction 
and at the same time moving the cursor inside it and editing/selecting 
parts of the text at the numerator or denominator, such as on scientifical 
calculators.  Currently that’s not possible even with org-mode latex-
fragments previews.

I have really hardly an idea of how would such a thing look, so I’m very 
curious about what more experienced and aknowledged-about-emacs-core 
people would think about it…

Re: Future of display engine and lines

[Lars Ingebrigtsen]

Alexandre Garreau <galex-713@galex-713.eu> writes:

> How difficult would it be for emacs to support in-buffer multiple columns? 

Having support for multiple columns in Emacs would be cool, but it would
be a major undertaking -- it's hard to see how it'd work sensibly
without basically making each buffer somehow consist of many smaller
buffers that are then somehow arranged to be displayed as one window.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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. ]]]

Powerful extensions in what can be displayed would be very important.

Can you design a data structure for it that can represent TeX-style
formatted output as well as LibreOffice formatting?  Or one that could
be extended to reach that point?

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Future of display engine and lines

[Alexandre Garreau]

Le vendredi 22 octobre 2021, 00:43:05 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. ]]]
>
> Can you design a data structure for it that can represent TeX-style
> formatted output as well as LibreOffice formatting?  Or one that could
> be extended to reach that point?

I really don’t know how LibreOffice formatting works, and LibreOffice looks 
like a pretty complex and inelegant piece of software.  However TeX is a 
general-purpose layout engine and I’m persuaded it’s superior and can 
emulate anything possible with LibreOffice.  I didn’t read know the precise 
C implementation, but afair, having read the TeXbook a long time ago 
(unfortunately since it’s proprietary it’s sometimes hard to find again and 
sometimes esoteric to compile) I know the fundamental elements of TeX 
formatting are hbox (h for horizontal) and vbox (v for vertical), and have 
an important concept of glue (both stretchable and shrinkable, including 
values of various levels of infinity) and depth (distinct from height, to 
determine the baseline).  That would result in a graph, and that’s 
fundamentally different of emacs’ way… which is only a line-divided 
sequence of chars… only a 2D graph.

Where is best documented the graphical engine of Emacs (the C part then), 
because it always made me curious…

> Powerful extensions in what can be displayed would be very important.

I wonder if something as powerful as TeX existed in relation with emacs, 
given its hackability, userbase and momentum (and those of lisp in 
general), emacs could quickly become a fully-fledged browser on par with 
firefox.

I also had a long dream of seeing a hackable-as-emacs TeX-style engine to 
make GUIs, especially as TeX is currently still the state of the art of 
how to make *correct* typography (but suffering of an esoteric, poor and 
hardly known programming language (they have macros, but no real functions 
yet, except in the yet-to-come LaTeX 3)), that would easily become better 
than anything currently made with a browser (which are still considered of 
bad quality compared to TeX or anything from standard DAO (like Scribus)), 
but for GUIs in general.

But that was an idea already existing for instance in the genesis of 
TeXmacs I believe, except it’s less ambitious (just a (actually heavy, 
more than emacs) word processor, not a GUI, IDE, browser, etc. while emacs 
do those).

I’m also afraid it may make emacs slower or heavier…

Re: Future of display engine and lines

[Eli Zaretskii]

> From: Alexandre Garreau <galex-713@galex-713.eu>
> Date: Fri, 22 Oct 2021 13:56:35 +0200
> 
> Where is best documented the graphical engine of Emacs (the C part then), 
> because it always made me curious…

In the large comment at the beginning of xdisp.c.

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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. ]]]

  > Having support for multiple columns in Emacs would be cool, but it would
  > be a major undertaking -- it's hard to see how it'd work sensibly
  > without basically making each buffer somehow consist of many smaller
  > buffers that are then somehow arranged to be displayed as one window.

I think it's not as hard as thet.

Buffer display currently works with a structure which is a series of
display lines.  On a graphics display, each window has its own set of
display lines, Redisplay fills in the window's display lines top to
botton based on the text in the buffer.

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.

It would be considerable work, but it would not require much change
in the data structure of a buffer itself.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Future of display engine and lines

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Date: Fri, 22 Oct 2021 19:47:13 -0400
> Cc: galex-713@galex-713.eu, emacs-devel@gnu.org
> 
> Buffer display currently works with a structure which is a series of
> display lines.  On a graphics display, each window has its own set of
> display lines, Redisplay fills in the window's display lines top to
> botton based on the text in the buffer.

That's correct.

> 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.

Perhaps I misunderstand what "multiple columns" mean, then.  Doesn't
it mean that buffer text is displayed in separate rectangular
portions, like this:

   aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
   dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
   hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz

where buffer position of the first "xxx" follows the buffer position
of the last "kkkk"?  If so, where in the above picture are your points
A and B?

> It would be considerable work, but it would not require much change
> in the data structure of a buffer itself.

Actually, I believe that any significant improvement in the Emacs
display engine would almost certainly need a redesign of the buffer
text data structure, because most current limitations of redisplay
basically follow from the fact that buffer text is a single
unstructured stream of bytes (forget about the gap, it's immaterial
for this purpose).  So if we are going to enhance the display engine,
I'd be for redesigning the buffer text first and foremost, and in that
redesign allow up front intrinsic support for some display features
such as this one.

Re: Future of display engine and lines

[Alexandre Garreau]

Le jeudi 21 octobre 2021, 05:16:30 CEST Lars Ingebrigtsen a écrit :
> Alexandre Garreau <galex-713@galex-713.eu> writes:
> > How difficult would it be for emacs to support in-buffer multiple
> > columns?
> Having support for multiple columns in Emacs would be cool, but it would
> be a major undertaking -- it's hard to see how it'd work sensibly
> without basically making each buffer somehow consist of many smaller
> buffers that are then somehow arranged to be displayed as one window.

Oh that’s exactly what I thought initially!

But somehow, when I try to explain what I imagine to be necessary, I have 
a hard time justifying subbuffers like this.  Like it’s more a question of 
subwindows than subbuffers… columns are a purely graphical feature, while 
buffers are a semantical one… of course the somewhat semantic question of 
line/column related to point would have to be questioned in that graphical 
disruption, and until now it has been linearly (and modularly, 
respectively) related to point’s position as a number… but we can still 
consider that, in the special specific respect of columns (such as css 
columns), the line/column is a purely graphical feature as well.

But a buffer displayed inside another buffer is something I have long-
desired as well for different semantic reasons… namely: more ergonomic org 
source-edit mode, and cleaner implementation of multimodes… such as needed 
in polyglot files such as php… that could *as well* be useful as well for 
displaying mime parts in gnus/rmail and displaying web pages in eww, where 
columns were historically often implemented with frames (for instance our 
chief gnuisance’s one, well THAT would ideally use a subbuffer), hence the 
confusion maybe… unless there is another true reason to reason recursively 
about buffers?

I mean, the change we are talking about is not purely columns, we should 
be more ambitious and if we gravitate toward something less linear, we 
could just as well provide the basis for any layout engine in lisp.

I mean… we’re not gonna allow only one set of columns per buffer right? 
that’d already be totally doable with a special set of windows splitting + 
follow-mode and some meta-mode modifying and keeping track of the frame’s 
windows set (I’m sure a dominant such mode already exists)… but that’d be 
semantically ugly because that’s a workaround involving many modelines… 
even removing (as already possible) scrollbars, hinges, and reducing the 
font-size and spacing, I guess that would not be an acceptable way of 
layoutting a workflow todays (or it would already be done… right? has it? …
maybe?)

So we’re gonna want to be able to have a set of columns inside a buffer, 
and another subset of columns inside another column, with several 
divisions per part of the buffer, and some columns in different font-size 
than others, hence the line-count in one column wouldn’t match the one in 
other ones, and then we would also want to be able to do vertical 
centering… that’s a pretty big overthrow, and not just a matter of greatly 
complexifying the current display engine just to allow eww to display, 
select, copy and treat several columns nicely in the simplest setting… 
right?

Re: Future of display engine and lines

[Ihor Radchenko]

Alexandre Garreau <galex-713@galex-713.eu> writes:

> I wonder if something as powerful as TeX existed in relation with emacs, 
> given its hackability, userbase and momentum (and those of lisp in 
> general), emacs could quickly become a fully-fledged browser on par with 
> firefox.

There is TeXmacs [1].  Probably, we can take some ideas from TeXmacs
graphical system.  As I recall, TeXmacs represents buffers as tree data
structures.  Maybe Chapter 6 Extending the graphical user interface of
TeXmacs dev manual [2] may be of interest.

[1] https://www.texmacs.org/tmweb/home/welcome.en.html
[2] https://www.texmacs.org/tmweb/documents/manuals/texmacs-scheme.en.pdf

Best,
Ihor

Re: Future of display engine and lines

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> Perhaps I misunderstand what "multiple columns" mean, then.  Doesn't
> it mean that buffer text is displayed in separate rectangular
> portions, like this:
>
>    aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
>    dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
>    hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz
>
> where buffer position of the first "xxx" follows the buffer position
> of the last "kkkk"? 

Well, it depends.  Perhaps these the next point after "xxx" is before
"where".  Or perhaps if you enter more text after "kkk", that box should
get a scroll bar, or perhaps it should extend downwards.

We're basically in the same design territory that HTML + CSS 3 covers,
and It's Just Very Difficult.  And as you say, the main problem isn't
displaying the glyphs on the screen -- but it's defining the semantics
about how the blocks interoperate, and making a command like `M-q' do
something sensible within a block.

Within the current Emacs structure, it would have to look like a bunch
of buffers that we glue together as sub-panes inside one window, where
your example ("xxx" follows "kkkk") would be as two sub-panes from one
of these sub-buffers, and where the second sub-pane displays the text
after line 3, with the layout in question.

I mean...  it'd be great, but I think we're basically talking about a
different editor.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

Re: Future of display engine and lines

[Alan Mackenzie]

Hello, Lars.

On Sun, Oct 24, 2021 at 14:38:07 +0200, Lars Ingebrigtsen wrote:
> Eli Zaretskii <eliz@gnu.org> writes:

> > Perhaps I misunderstand what "multiple columns" mean, then.  Doesn't
> > it mean that buffer text is displayed in separate rectangular
> > portions, like this:

> >    aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
> >    dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
> >    hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz

> > where buffer position of the first "xxx" follows the buffer position
> > of the last "kkkk"? 

> Well, it depends.  Perhaps these the next point after "xxx" is before
> "where".  Or perhaps if you enter more text after "kkk", that box should
> get a scroll bar, or perhaps it should extend downwards.

> We're basically in the same design territory that HTML + CSS 3 covers,
> and It's Just Very Difficult.  And as you say, the main problem isn't
> displaying the glyphs on the screen -- but it's defining the semantics
> about how the blocks interoperate, and making a command like `M-q' do
> something sensible within a block.

Err, aren't we talking about Follow Mode, here?  Follow Mode has been
around for a year or two now, and works very well (apart from the fact
there are no standard key bindings to enable it in 1/2/3 columns, or
disable it).  The semantics of the interoperating windows is indeed
somewhat involved, and unfortunately also somewhat slow, since
follow-mode is fighting the display engine over what goes where.

> Within the current Emacs structure, it would have to look like a bunch
> of buffers that we glue together as sub-panes inside one window, where
> your example ("xxx" follows "kkkk") would be as two sub-panes from one
> of these sub-buffers, and where the second sub-pane displays the text
> after line 3, with the layout in question.

> I mean...  it'd be great, but I think we're basically talking about a
> different editor.

> -- 
> (domestic pets only, the antidote for overdose, milk.)
>    bloggy blog: http://lars.ingebrigtsen.no

-- 
Alan Mackenzie (Nuremberg, Germany).

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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.

  > Perhaps I misunderstand what "multiple columns" mean, then.  Doesn't
  > it mean that buffer text is displayed in separate rectangular
  > portions, like this:

  >    aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
  >    dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
  >    hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz

  > where buffer position of the first "xxx" follows the buffer position
  > of the last "kkkk"?

That's exactly what I had in mind.  But we should not assume that xxx
are consecutive with kkkk.  We could be looking at the middle, vertically,
of the two columns; their top and bottom could be off-screen.

                         If so, where in the above picture are your points
  > A and B?

IF xxx immediately follows kkkk, then point A is at the start of aaaaaaaaaaaa
and point B is at the start of xxx.

But suppose that these two columns actually start 5 libes above
aaaaaaaaaaaa and xxx, and those lines are scrolled off the top of the
window.  This means that xxx does not follow kkkk in the buffer text.
Rather, kkkk is followed by some more lines below (off the window below)
and a few more lines that are above xxx... (off the window above).

In that case point A is at the start of the five lines above aaaaaaaaaaaa,
abd point B is at the start of the five lines above xxx.

  > Actually, I believe that any significant improvement in the Emacs
  > display engine would almost certainly need a redesign of the buffer
  > text data structure, because most current limitations of redisplay
  > basically follow from the fact that buffer text is a single
  > unstructured stream of bytes

I can't prove we don't need to do that, but I really hope so.
Changing the display structure would be a rather local change,
while changing the buffer format would be enormous.

I have hope it will be possible to do this without changing the buffer
format, so I suggest trying that first.


-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Future of display engine and lines

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Cc: larsi@gnus.org, galex-713@galex-713.eu, emacs-devel@gnu.org
> Date: Sun, 24 Oct 2021 22:18:40 -0400
> 
>   >    aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
>   >    dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
>   >    hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz
> 
>   > where buffer position of the first "xxx" follows the buffer position
>   > of the last "kkkk"?
> 
> That's exactly what I had in mind.  But we should not assume that xxx
> are consecutive with kkkk.  We could be looking at the middle, vertically,
> of the two columns; their top and bottom could be off-screen.

Why would that make sense?  You will be unable to read the text
without scrolling the window.

> 
>                          If so, where in the above picture are your points
>   > A and B?
> 
> IF xxx immediately follows kkkk, then point A is at the start of aaaaaaaaaaaa
> and point B is at the start of xxx.

But then what did you mean by this:

  > > 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.

The "going vertically from A, then vertically from B" is the part I
don't understand: what did you mean by "fill up segments by going
vertically" here?

>   > Actually, I believe that any significant improvement in the Emacs
>   > display engine would almost certainly need a redesign of the buffer
>   > text data structure, because most current limitations of redisplay
>   > basically follow from the fact that buffer text is a single
>   > unstructured stream of bytes
> 
> I can't prove we don't need to do that, but I really hope so.
> Changing the display structure would be a rather local change,
> while changing the buffer format would be enormous.

Why enormous?  The internals of buffer text are known to relatively
small number of low-level primitives.

Making buffer text smarter than a linear byte stream could allow us to
know where to jump if the user moves point from "kkk" to the right,
with the intent of going to "zzzzzzzzzz", without costly scanning of
the buffer while simulating display.

IOW, I believe that leaving the buffer text design intact will make
redisplay that is already relatively slow in complex situations even
slower.  That is no way to move Emacs into the future.

> I have hope it will be possible to do this without changing the buffer
> format, so I suggest trying that first.

Well, for starters, how would you record the starting point of the
visible portion of each column? wouldn't that already need some change
in the window object, if not in the buffer text?

Re: Future of display engine and lines

[Alexandre Garreau]

Le lundi 25 octobre 2021, 14:05:29 CEST Eli Zaretskii a écrit :
> > From: Richard Stallman <rms@gnu.org>
> > Cc: larsi@gnus.org, galex-713@galex-713.eu, emacs-devel@gnu.org
> > Date: Sun, 24 Oct 2021 22:18:40 -0400
> > 
> >   >    aaaaaaaaaaaa bbbbbbbb ccccccc    xxx xxxxxxxx xxxxxxxxxxxx
> >   >    dddddddd eeeeeeee fffffff ggg    yyyyyy yyyyyyyyy yyyyyyyy
> >   >    hhhhhhhh iiiiiiiiii jjjj kkkk    zzzzzzzzz zzzzzzzzzz zzzz
> >   > 
> >   > where buffer position of the first "xxx" follows the buffer
> >   > position
> >   > of the last "kkkk"?
> > 
> > That's exactly what I had in mind.  But we should not assume that xxx
> > are consecutive with kkkk.  We could be looking at the middle,
> > vertically, of the two columns; their top and bottom could be
> > off-screen.
> 
> Why would that make sense?  You will be unable to read the text
> without scrolling the window.

In the way you imagine it, that is directly unpractical for reading, but 
practical for the one usage that I re-suggested initially: enabling a 
WYSIWYG text processor inside emacs.  You may want to visualize pages 
bigger than what fits on your screen, because it will be rendered on other, 
bigger screen, or unzoomed, or printed.

In a way you may not be imagining: both column contents could be 
unrelated, such as on stallman.org, and yet the most right column would be 
considered to be “after” the most left column, there, it wouldn’t be 
unpractical, because maybe you want to read only one column.

Re: Future of display engine and lines

[Eli Zaretskii]

> From: Alexandre Garreau <galex-713@galex-713.eu>
> Cc: rms@gnu.org, larsi@gnus.org, emacs-devel@gnu.org
> Date: Mon, 25 Oct 2021 14:20:35 +0200
> 
> In a way you may not be imagining: both column contents could be 
> unrelated

If they are unrelated, you are talking about a different use case,
where each column comes from a different buffer.

Re: Future of display engine and lines

[Alexandre Garreau]

Le lundi 25 octobre 2021, 14:50:48 CEST Eli Zaretskii a écrit :
> > From: Alexandre Garreau <galex-713@galex-713.eu>
> > Cc: rms@gnu.org, larsi@gnus.org, emacs-devel@gnu.org
> > Date: Mon, 25 Oct 2021 14:20:35 +0200
> > 
> > In a way you may not be imagining: both column contents could be
> > unrelated
> 
> If they are unrelated, you are talking about a different use case,
> where each column comes from a different buffer.

not necessarily, you could also be willing to read only a part of the 
buffer, and calculated how the columns were so that to have each of them 
have a different topic/semantic: the buffer is not the only semantic 
division available (but I see that like Lars you like to see buffers used 
in that way, like I initially thought… but aren’t buffers essentially meant 
to be used to represent files? or anything uniquely serializable, for the 
matter)

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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. ]]]

  > In the way you imagine it, that is directly unpractical for reading, but 
  > practical for the one usage that I re-suggested initially: enabling a 
  > WYSIWYG text processor inside emacs.  You may want to visualize pages 
  > bigger than what fits on your screen, because it will be rendered on other, 
  > bigger screen, or unzoomed, or printed.

Indeed, that's exactly the case I had in mind.  It's possible in Emacs
to edit a page of single-column text (delimited by ^L characters, of
course) that is too tall to fit on the screen.  When Emacs displays
multicolumn text, that too should allow scrolling through pages that
are too tall.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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.

  > The "going vertically from A, then vertically from B" is the part I
  > don't understand: what did you mean by "fill up segments by going
  > vertically" here?

I am struggling to find precise words about this abstract point.

Imagine that one region of the buffer is displayed in two side-by-side
columns.  The top of the window is in that region.  To redisplay it,
display needs to know where in the buffer each column starts.
For the second column, it also needs to know how many screen lines (or
how much screen height) is off the top of the window.

It can fill up the first column's rectangle by processing text linearly
from the window start, line by line, and putting the result into the
correct part of each screen line.

It can fill up the second column's rectangle by processing text
linearly from the proper place in the buffer (where the right column
text should start), line by line, and putting the result into the
correct part of each screen line.

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.)

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.

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.


-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: Future of display engine and lines

[Eli Zaretskii]

> From: Richard Stallman <rms@gnu.org>
> Cc: larsi@gnus.org, galex-713@galex-713.eu, emacs-devel@gnu.org
> Date: Thu, 28 Oct 2021 08:19:41 -0400
> 
> Imagine that one region of the buffer is displayed in two side-by-side
> columns.  The top of the window is in that region.  To redisplay it,
> display needs to know where in the buffer each column starts.
> For the second column, it also needs to know how many screen lines (or
> how much screen height) is off the top of the window.
> 
> It can fill up the first column's rectangle by processing text linearly
> from the window start, line by line, and putting the result into the
> correct part of each screen line.
> 
> It can fill up the second column's rectangle by processing text
> linearly from the proper place in the buffer (where the right column
> text should start), line by line, and putting the result into the
> correct part of each screen line.
> 
> 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.)
> 
> The point is, there is no need to change the representation of buffers.

You are describing the initial thorough display of a window, whereby
the display engine produces the display of the entire window from
scratch.  That is indeed a relatively easy job, but it is quite an
infrequent use case in practice.  Most of the jobs that the display
engine needs to do have to do with redrawing only small parts of the
window, or scrolling the window by a small number of lines, or even
with just moving point via cursor-motion commands.  For these
situations, it is very important to be able to find the buffer
position that corresponds to some screen coordinates, or vice versa.
We currently do that by simulating redisplay, i.e. by performing all
the layout decisions without actually storing the produced glyphs.

The problem is that all those jobs need to start from some well-known
point in the buffer, where we can know the corresponding screen
coordinates.  And having the buffer text as an unstructured stream of
bytes makes it hard to find such places.  More often than not, we use
the beginnings of some physical line, where at least the X coordinate
is known to be zero.  We then go through the buffer, one character at
a time, performing layout calculations to track the X and Y
coordinates, until we come to the place we need -- either where some
condition about the buffer position becomes true, or some condition
regarding the screen coordinates becomes true.  This painstaking
iteration from a well-known point is what makes redisplay slow in some
situations, for example if the lines are very long (which means the
beginning of the previous line could be very far away, and we need to
examine a large fraction of the buffer).  It also makes movement back
in the buffer much slower (and here the variable-length internal
encoding of characters joins the previous problem to make it harder).

For example, imagine that the user moves the cursor to the right of
the rightmost character of the first column, with the intent to move
to the second column.  We'd now need to find the buffer position that
corresponds to that screen position, and the only way we have now is
to start from the window-start of the second column and go all the way
down until we reach the same Y coordinate.  Imagine how much faster we
could do that job if we kept record of the beginning of each screen
line.

So for those other jobs that redisplay must do, which in practice are
much more important and frequent than redrawing the entire window, the
current implementation of buffer text puts a limit on the speed, and
IME we have all but exhausted all the potential for speeding that up
without changing the buffer representation.  Which is why I think we
should change the buffer text representation if we want a faster
redisplay, especially if we want to introduce complications like
multiple columns etc, and still have reasonably performant redisplay.

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.

Re: Future of display engine and lines

[chad]

[-- Attachment #1: Type: text/plain, Size: 1427 bytes --]

On Thu, Oct 28, 2021 at 8:04 AM Alexandre Garreau <galex-713@galex-713.eu>
wrote:

>
> 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)),


I think I might misunderstand you, because, if I recall correctly, Emacs'
multiple-cursor support is a port of the concept from Atom, which borrowed
it from Sublime Text. In any case, at this point multiple-cursor support
(perhaps under varying names) exists in several commonly used editors,
including gedit and vscode.

On Thu, Oct 28, 2021 at 5:21 AM Richard Stallman <rms@gnu.org> wrote:

>
> 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.
>

It's been a few years since I last looked at this, but if anyone is
{seriously,academically} interested in changing Emacs' underlying buffer
representation, I recommend looking closely at ropes:

  https://en.wikipedia.org/wiki/Rope_(data_structure)

I've been away from these academic circles for a while now, so it's
possible that this recommendation is out of date; I would love to see (a
pointer to) an update if anyone has such a thing.

Hope this helps,
~Chad

[-- Attachment #2: Type: text/html, Size: 2206 bytes --]

Re: Future of display engine and lines

[Eli Zaretskii]

> From: chad <yandros@gmail.com>
> Date: Tue, 9 Nov 2021 15:13:28 -0800
> Cc: Richard Stallman <rms@gnu.org>, Eli Zaretskii <eliz@gnu.org>, Lars Ingebrigtsen <larsi@gnus.org>, 
> 	EMACS development team <emacs-devel@gnu.org>
> 
>  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)), 
> 
> I think I might misunderstand you, because, if I recall correctly, Emacs' multiple-cursor support is a port of
> the concept from Atom, which borrowed it from Sublime Text. In any case, at this point multiple-cursor
> support (perhaps under varying names) exists in several commonly used editors, including gedit and
> vscode.

In any case, I don't think multiple-cursors have necessarily anything
to do with the way we store and process buffer text.  It's a display
feature, not necessarily a text-editing feature.

>  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.
> 
> It's been a few years since I last looked at this, but if anyone is {seriously,academically} interested in
> changing Emacs' underlying buffer representation, I recommend looking closely at ropes:
> 
>   https://en.wikipedia.org/wiki/Rope_(data_structure) 
>  
> I've been away from these academic circles for a while now, so it's possible that this recommendation is out
> of date; I would love to see (a pointer to) an update if anyone has such a thing.

I think if we ever seriously consider changing the representation of
buffer text, we should consider first what will benefit faster display
operations, not the efficiency of insertions and deletions.  Because
without well-known display problems, we won't have a good enough
reason to change the buffer text representation in the first place.
And it must be a very good reason, because the job of changing that
representation is not a trivial one.

Re: Future of display engine and lines

[Richard Stallman]

[[[ 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. ]]]

  > In any case, I don't think multiple-cursors have necessarily anything
  > to do with the way we store and process buffer text.  It's a display
  > feature, not necessarily a text-editing feature.

I agree.

  > I think if we ever seriously consider changing the representation of
  > buffer text, we should consider first what will benefit faster display
  > operations, not the efficiency of insertions and deletions.  Because
  > without well-known display problems, we won't have a good enough
  > reason to change the buffer text representation in the first place.
  > And it must be a very good reason, because the job of changing that
  > representation is not a trivial one.

I agree with that too.

BTW, I think the data format used for text properties is similar to a
rope.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)