Re: [emacs-bidi] Mixed L2R and R2L paragraphs and horizontal scroll

[Beni Cherniavsky]

On Thu, Feb 4, 2010 at 18:21, Ehud Karni <address@hidden> wrote:
> I wish more users who uses Hebrew routinely will take part in this
> discussion.
>
That'd be my clue ;-).  Hi.  New here, sufficiently retro-lurked.

[Sorry, long mail.  In the first half I'm whining about why I don't
like Eli's solution; but I also reply with technical ideas below...]


First, I want to draw attention to the distinction between line
wrapping and truncation/scrolling.

- Line wrapping (aka continuation lines) in visual order is bad!
  It violates the deep axiom that reading order between *lines*
  is downward regardless of bidi.

- Truncation in visual order is OK!  It fits the rigid scrolling
  model of a small window horizontally moving over a wide page.

  This is the only model of truncation that I've seen in other
  programs.  You either have the "Web" model where lines wrap at
  window boundary and there is no truncation, or the "Page" model
  where lines are layed out onto an underlying page, and you see
  a physical window onto it.

  (It does require a lot of horizontal scrolling to read mixed
  direction text, but that's the user's problem.)

- Truncation in logical order might(?) be OK if coupled with
  logical-order "mirrored" scrolling.

  I've never seen such a program, so I don't know if it would be
  usable.  I believe we can easily try it out by running a plain
  L2R emacs in a bidi terminal, e.g. mlterm.  I'll try to work with
  that a bit to see how it feels...

In all the following, I'm only talking about wrapped continuation
lines.  I got the impression Ehud is also mostly concerned about
contintinuation lines - correct me if I'm wrong.


Second, allow me to sum up Ehud's arguments.

- It's the Right Thing to do.  Books, papers, and correct software have
  always done it this way, and that's what the Unicode standard says.

- Convenience: Doing it the wrong way requires discontinued reading,
  which is annoying.

and add 2 more angles to the issue:

- Mental model, or why imperfect bidi is painful:

  As an R2L user, I constantly maintain a mental model of the logical
  order.  I've got some deep habits and assumptions about the mapping
  from logical to visual.  *Any* deviation will completely confuse my
  poor brain about the logical order of the buffer.

  Worse yet, if I now proceed to *edit* the buffer, I'll modify it in
  completely wrong places, and even when I realize that, fixing it will
  be even harder!  I'll need to *simultaneously* reverse-engineer your
  deviant bidi algorithm and figure out the real logical order, and
  then very carefully fix my edits, all the time getting strangely
  permuted feedback for my actions.

  This involves concentration, a lot of forward/backward-char movement
  to visualize the logical order, and expletives under my breath :-(

  This is the *real* reason we hate broken bidi support.  No bidi at all
  is frequently better - ain't pretty but at least has 1:1 mental model.

- Emotional: this kind of broken bottom-up line wrapping is precisely
  the problem with visual-order Hebrew.  Reduce the browser window width
  on any visual-order site, and you'll see it.  We (Hebrew readers)
  had to live with it until logical-order support arrived in browsers,
  have cursed too many sites that use visual-order to this very day,
  and by now we hate it with a burning passion!

  It's none of your fault, but getting line wrapping wrong will step on
  very sore spots with many users...

To be fair, we're talking about rare situations where embedded text is
broken across lines.  But note that a wrong base direction can inflict
this on whole paragraphs (more on that below).


On Fri, Feb 5, 2010 at 11:50, Eli Zaretskii <address@hidden> wrote:
> Like Ehud, I think that it would be swell to have what he wants.  But,
> possibly unlike Ehud, I think that what I have now it not a disaster,
> and we can live with it for the time being, maybe even longer.
>
> The reasons for my decision to implement truncation and continuation
> as I did are:
>
>  . It is the only reasonable way to go that does not call for a very
>    serious surgery, perhaps even a total rewrite, of the display
>    engine code.
>
>  . I saw no other editor that supports truncation and behaves
>    otherwise.  (I don't know about any editors that support
>    continuation lines like Emacs does.)  See below.
>
Truncation is OK, but the issue is continuation.

Not following your claim about editors that support continuation -
all these do and behave otherwise (i.e. as Ehud wants):
Notepad, gedit, firefox/webkit, OpenOffice.

>  . The issue pops up only in relatively rare situations: mixed
>    L2R/R2L text that gets truncated/continued within a stretch of
>    text whose directionality is against the paragraph direction.
>
Indeed, embedded text tends to be short.

But I'm afraid it's bigger than you think, because if the base direction
of a paragraph is incorrect, *the whole paragraph* will wrap in this
broken bottom-up manner.  Since base direction guessing is never perfect,
and users don't always have the option - or patience - to fix it manually,
this makes the otherwise minor problem more visible.

Also, changing the base direction of any paragraph will behave funny:
Instead of (mostly) just jumping horizontally, it'll also reverse the
order of lines!

                                                            !of lines
Instead of (mostly) just jumping horizontally, it'll also reverse the
:Also, changing the base direction of any paragraph will behave funny

See?  [estimated, some punctuation might be off]

This also means that forcing all paragraphs to R2L or L2R base direction
(which would be a handy way to momentarily work around wrong imperfect
guessing) would break line order in half the paragraphs in a mixed buffer!


>> If it's just "difficult", then (just like rigid scrolling), it can be
>> kept as a known shortcoming.
>
> It is either VERY difficult or very slow.
>
> The current display code lays out glyphs in each ``glyph row'' one by
> one, in the visual order.  Thus, for the portion of text that is
> reversed from its logical order, the bidi reordering code effectively
> delivers the characters backwards to this glyph layout code, in the
> decreasing order of buffer positions.  That is, the glyphs assembled
> first are the last ones to be read.  Then you hit the window margin,
> and know that there isn't enough place for the whole line.  Only then
> you know how many characters will fit on this line.  But you know that
> in terms of the last portion of the text in the reading order, which
> tells you very little about how many characters at the beginning of
> this stretch of text you could display instead.  (Remember that Emacs
> supports variable size characters and different fonts on the same
> line, so just counting characters will not do.)
>
> What would be nice is to scan the text to be reversed in the logical
> order, and find the part of it that will fit on this screen line.
> Then we could reorder only that part.

Right.  Line breaking must be done in logical order.

> But to do that, we need to try
> every possibility by actually doing most of the display work behind
> the scenes, because of the complications with different font sizes,
> faces, composite characters and issues like ligatures and the like,
> which change the amount of screen estate taken by a portion of a line,
> even if you just juxtapose the same two characters.
>
Right, this is a known annoying property of bidi interacting with
typographic features.  Note however that you have a new trade-off here:
if you could compromise precision of line breaking to get correct bidi
behaviour (with fast redisplay), users would be happy.

See below for a concrete attempt.

> With a newline marking the end of the line, it's easy: the bidi
> reordering ends at the newline, then restarts after it.

So if only the line breaking points were static, you'd have no
performance problem!

=> Could you maybe cache this information and recompute it only when
the line is edited?  I understand part of the whole point of your
implementation was to avoid any caching of bidi ordering; but caching
of line breaking points sounds much less intrusive...

[XEmacs already has a "Line Start Cache" according to its Internals Manual.
I didn't find a similar overview for Emacs.  Is there anything I can read
to understand Emacs redisplay before I attempt to approach the source?]

> By contrast,
> to support ``bidi-smart continuation'', we need to find the place
> where to break the line, and that is impossible without actually
> trying to display it.
>
> In the example below
>
>  word1 word2 WORD1 WORD2
>
> to be displayed as
>
>  word1 word2 2DROW 1DROW
>
> if the window is only wide enough to display
>
>  word1 word2  1DROW
>
> we need to try displaying in order
>
>  word1 word2 1
>  word1 word2 1D
>  word1 word2 1DR
>  word1 word2 1DRO
>  word1 word2 1DROW
>  word1 word2  1DROW
>  word1 word2 W 1DROW
>
> until we discover where we should stop.  (We could do a binary search,
> of course, but that's details.)  I don't think that's reasonable, and
> I have no idea what will this do to the redisplay speed.
>
Binary search is a big improvement!  In 10 attempts you can handle lines
of 1K chars, in 20 - 1M.  On my computer Emacs presently handles 100k
smoothly, 1M already feels sluggish.  By crude (and probably wrong)
computation, binary search would still be fast enough up to 10K...

Also, I presume that the heavy part of a redisplay is normally the actual
output to screen (if not, why do such a complex job minimizing it?).  This
means that "dry" running the engine without actual output 10 times should
result in much less that 10x slowdown.

To top this, I think you can do several times better if you allow some
imprecision in line breaking of mixed-direction paragraphs.  Naturally,
you must not overshoot the screen, but some undershooting is OK.  So it
seems to me that you could reasonably do it with a greedy approach:

(1) Add characters in *logical order* as long as they fit.
(2) Try it in visual order to account for precise typographic stuff.
(3) As long as it doesn't fit, strip one a char and retry (2).
(4) When OK, repeat with actual output display to the screen.

If (1) overestimates, you're left with a shorter line than ideal; if
it underestimates, you do extra iterations.  But I guess that it
normally won't be off by more than one character, so it will look OK
and run fast.

[One pathological case that springs to mind is Arabic shaping.  Doing
(1) in logical order would result in all the wrong ligatures, risking
the estimation being seriously off.  It's still much better than wrong
line order, so I'd ignore that for now; but an Arabic expert opinion
would be welcome...]

Note that this scheme runs the display engine at least 3 times, even
for pure-L2R short lines!  We'd have to optimize the common cases before
a release; I can see how it might work, but I don't want to complicate
the picture at this stage.

As long as we conclude that SOME such scheme is workable, we can
leave the detailed implementation for the future.


Finally, I want to propose a feature that I think will be handy,
and also happens to support efficient wrapping.  The truth is that any
way to wrap an embedding accross lines is ugly!  I'd like a mode where
any embedding either fits completely on a line or starts and ends on a
lines by itself:

+----------------------------------------+
|some latin text followed by            \|
|\          ROF TXET GNOL TAHWEMOS WERBEH|
|\                     SIHT GNITARTSNOMED|
|followed by latin tail                  |
+----------------------------------------+

This is relatively easy to implement efficiently - you add embedded
characters in *visual* order as you propose, but if the embedding
doesn't fit entirely, you just fall back to the breaking where the
embedding started!  You don't even need a stack - I'm talking one
"primary" level for each visual line.

If you don't like any of the other ideas, this seems like a minimally
intrusive way to make your approach more usable.

-- 
Beni Cherniavsky-Paskin <address@hidden>