[emacs-bidi] Re: bidi prototype in elisp

[Eli Zaretskii]

> From: Alex Schroeder <address@hidden>
> Date: Tue, 06 Nov 2001 12:02:36 +0100
> 
> "Eli Zaretskii" <address@hidden> writes:
> 
> > Given that the C implementation of the sequential reordering is
> > already done (that's the code I've been working on until now), what
> > would be the purpose of writing another implementation in Lisp?
> > Sounds like a waste of your time.
> 
> It seemed like a good way of doing some coding, just looking at code
> doesn't work for me.  If your implementation is already done, great!
> Let's have it.  :) I wasn't sure wether it already worked, wether it
> was "done" or wether it was in the very early stages only.

Let me say a few words about the current design of the bidi display.
I hope this will make the overall picture a bit more clear,
specifically wrt the place and role of the code I wrote until now.

As some of you might know, the Emacs display engine works in 3
phases.  First, the glyph matrix is generated from the buffer
contents; then this matrix is compared with a similar matrix
constructed during the previous redisplay; and finally the
differences between these two matrices are used to redraw the
portions of display that were changed.

The bidi algorithm is designed to be called by the code which
constructs the glyph matrix, during the first phase.  The non-bidi
code walks the buffer in the logical order (using the iterator
structure that Alex mentioned earlier), fetches each character in
sequence, and fills the glyph matrix element with information required
to draw that character on the screen; then it advances to the next
character by incrementing the buffer position by one.

This description is intentionally simplistic; for example, it ignores
complications with images, overlays, etc.  If we forget about those
complications, the current code advances through the buffer linearly.

When the bidi code is added, the only significant change will be that
the code which constructs the glyph matrices will advance through the
buffer *non-linearly*.  Namely, in a simple example like this:

       abcdeABCDExyz

(where UPPER-case letters are, as usual, strong RTL characters), the
iterator will advance from a to e, then jump all the way to E, back
thru D, C, and B up to A, then jump to x, and continue advancing to
z.

In other words, the glyph matrices are constructed by fetching the
next character in the _visual_order_.  To do that, instead of
incrementing the buffer position, the code which constructs the glyph
matrix will call the function bidi_get_next_char_visually, which is
the main entry into the code I wrote.  That function will return the
next character (and its buffer position) which follows the current
character _in_the_visual_order_.

Such a design has a significant advantage of leaving the structure of
the current display engine almost intact.  (Well, that's also extremely
over-simplified, but I can dream, can't I? ;-)  The bulk of the
display code knows nothing about bidi, it just has the buffer
position miraculously bumped as needed so that the characters are
delivered in the visual order.

An additional advantage of this design is that any other code in Emacs
that needs to rearrange logical order into visual can simply call the
same function bidi_get_next_char_visually, and use its result for
whatever they need to do with it.  Sending text to a printer is a case
in point; producing a visual-order file is another.

The challenge with this design is that it requires a sequential
implementation of the algorithm defined by UAX#9, because
bidi_get_next_char_visually is called once for each character, and
needs to do all its work for that character before it returns.  By
contrast, all the implementations of UAX#9 are batch-style: they take
a paragraph and return it after reordering.  (In fact, the algorithm
defined by UAX#9 itself has a very strong bias towards batch-style
implementation.)

Writing such an implementation was not very easy, but it's done, and
the resulting code compares well, both in size and in speed with
FriBidi, for example (it's a bit slower than FriBidi, according to
some preliminary measurements).

One other display engine modification should be done in the parts of
Emacs which actually redraw screen portions: there, for a
right-to-left paragraph, we need to draw the glyphs starting from the
right margin and going to the left.  This is because, for a buffer
whose contents is

      ABCDEFGH

(i.e. all characters are RTL), the algorithm doesn't reorder the text
at all, but instead sets a flag telling the terminal interface code
that the glyphs should be drawn from right to left.

This part of the code is terminal-specific, so we need at least 2
variations: on for the GUI versions (X, Windows and the Mac), the
other for the character terminals.  I didn't yet start working on
this; any takers?

I hope this description is useful.  If you have any questions, please
ask.