Retrospective commit from 2009-12-12.

Begin working on faces support.  First version of handle_stop_backwards.
Rearrange struct bidi_it for more efficient push/pop ops.

 dispextern.h (struct it): New members prev_stop and
 base_level_stop.

 xdisp.c (handle_stop_backwards): New function.
 (next_element_from_buffer): Handle the situation where we
 overstepped stop_charpos due to non-linearity of the bidi
 iteration.  Likewise for when we back up beyond the previous
 stop_charpos.
 (reseat_1, pop_it, push_it): Set prev_stop and base_level_stop.

 dispextern.h (BIDI_AT_BASE_LEVEL): New macro.

 bidi.c (bidi_copy_it): Fix compiler warning due to cast of a
 pointer to `int'.  Don't preserve the first_elt member, as it is
 no longer copied, because its position in the structure was
 changed, see below.

 dispextern.h (struct bidi_it): Move first_elt, new_paragraph,
 separator_limit, and paragraph_dir to after bidi_stack.  Add a
 note that anything beyond the level stack is not preserved when
 the bidi iterator state is copied/saved.

4 files changed, 133 insertions, 29 deletions

diff --git a/src/ChangeLog.bidi b/src/ChangeLog.bidi
index e3e1eddab75..ef911354df8 100644
--- a/src/ChangeLog.bidi
+++ b/src/ChangeLog.bidi
@@ -1,3 +1,27 @@
+2009-12-12  Eli Zaretskii  <eliz@gnu.org>
+
+        * dispextern.h (struct it): New members prev_stop and
+        base_level_stop.
+
+        * xdisp.c (handle_stop_backwards): New function.
+        (next_element_from_buffer): Handle the situation where we
+        overstepped stop_charpos due to non-linearity of the bidi
+        iteration.  Likewise for when we back up beyond the previous
+        stop_charpos.
+        (reseat_1, pop_it, push_it): Set prev_stop and base_level_stop.
+
+        * dispextern.h (BIDI_AT_BASE_LEVEL): New macro.
+
+        * bidi.c (bidi_copy_it): Fix compiler warning due to cast of a
+        pointer to `int'.  Don't preserve the first_elt member, as it is
+        no longer copied, because its position in the structure was
+        changed, see below.
+
+        * dispextern.h (struct bidi_it): Move first_elt, new_paragraph,
+        separator_limit, and paragraph_dir to after bidi_stack.  Add a
+        note that anything beyond the level stack is not preserved when
+        the bidi iterator state is copied/saved.
+
 2009-11-21  Eli Zaretskii  <eliz@gnu.org>
 
         * xdisp.c (set_cursor_from_row): Fix cursor positioning on empty
diff --git a/src/bidi.c b/src/bidi.c
index e8b7b2a8c56..102326b41e8 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -528,15 +528,10 @@ bidi_mirror_char (int c)
 static inline void
 bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
 {
-  int save_first_elt = to->first_elt;
   int i;
 
-  /* Copy everything except the level stack.  */
-  memcpy (to, from, ((int)&((struct bidi_it *)0)->level_stack[0]));
-  /* Don't copy FIRST_ELT flag.  */
-  to->first_elt = save_first_elt;
-  if (to->first_elt != 0 && to->first_elt != 1)
-    to->first_elt = 0;
+  /* Copy everything except the level stack and beyond.  */
+  memcpy (to, from, ((size_t)&((struct bidi_it *)0)->level_stack[0]));
 
   /* Copy the active part of the level stack.  */
   to->level_stack[0] = from->level_stack[0]; /* level zero is always in use */
diff --git a/src/dispextern.h b/src/dispextern.h
index 19e3f13fd87..58e6ff91338 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -370,7 +370,7 @@ struct glyph
   /* Non-zero means don't display cursor here.  */
   unsigned avoid_cursor_p : 1;
 
-  /* Resolved bidirection level of the characters [0..63].  */
+  /* Resolved bidirectional level of this character [0..63].  */
   unsigned resolved_level : 5;
 
   /* Resolved bidirectional type of this character, see enum
@@ -750,8 +750,8 @@ struct glyph_row
      overlay position information etc, where the display of this row
      started, and can thus be less the position of the first glyph
      (e.g. due to invisible text or horizontal scrolling).  BIDI Note:
-     This is the smallest character position in the row, i.e. not
-     necessarily the character that is displayed the leftmost.  */
+     This is the smallest character position in the row, but not
+     necessarily the character that is the leftmost on the display.  */
   struct display_pos start;
 
   /* Text position at the end of this row.  This is the position after
@@ -759,8 +759,8 @@ struct glyph_row
      glyph position + 1, due to truncation, invisible text etc.  In an
      up-to-date display, this should always be equal to the start
      position of the next row.  BIDI Note: this is the character whose
-     buffer position is the largest, not necessarily the one displayed
-     the rightmost.  */
+     buffer position is the largest, but not necessarily the rightmost
+     one on the display.  */
   struct display_pos end;
 
   /* Non-zero means the overlay arrow bitmap is on this line.
@@ -1726,7 +1726,7 @@ struct face_cache
 
 extern int face_change_count;
 
-/* For BIDI */
+/* For reordering of bidirectional text.  */
 #define BIDI_MAXLEVEL 64
 
 /* Data type for describing the bidirectional character types.  The
@@ -1777,7 +1777,6 @@ struct bidi_stack {
 
 /* Data type for iterating over bidi text.  */
 struct bidi_it {
-  int first_elt;                /* if non-zero, examine current char first */
   EMACS_INT bytepos;            /* iterator's position in buffer */
   EMACS_INT charpos;
   int ch;                       /* character itself */
@@ -1789,9 +1788,6 @@ struct bidi_it {
   int resolved_level;           /* final resolved level of this character */
   int invalid_levels;           /* how many PDFs to ignore */
   int invalid_rl_levels;        /* how many PDFs from RLE/RLO to ignore */
-  int new_paragraph;            /* if non-zero, we expect a new paragraph */
-  EMACS_INT separator_limit;    /* where paragraph separator should end */
-  bidi_dir_t paragraph_dir;     /* current paragraph direction */
   int prev_was_pdf;             /* if non-zero, previous char was PDF */
   struct bidi_saved_info prev;  /* info about previous character */
   struct bidi_saved_info last_strong; /* last-seen strong directional char */
@@ -1803,10 +1799,20 @@ struct bidi_it {
   bidi_dir_t sor;               /* direction of start-of-run in effect */
   int scan_dir;                 /* direction of text scan */
   int stack_idx;                /* index of current data on the stack */
+  /* Note: Everything from here is not copied/saved when the bidi
+     iterator state is saved, pushed, or popped.  So only put here
+     stuff that is not part of the bidi iterator's state!  */
   struct bidi_stack level_stack[BIDI_MAXLEVEL]; /* stack of embedding levels */
+  int first_elt;                /* if non-zero, examine current char first */
+  bidi_dir_t paragraph_dir;     /* current paragraph direction */
+  int new_paragraph;            /* if non-zero, we expect a new paragraph */
+  EMACS_INT separator_limit;    /* where paragraph separator should end */
 };
 
-
+/* Value is non-zero when the bidi iterator is at base paragraph
+   embedding level.  */
+#define BIDI_AT_BASE_LEVEL(BIDI_IT) \
+  (BIDI_IT).resolved_level == (BIDI_IT).level_stack[0].level
 
 
 /***********************************************************************
@@ -2006,6 +2012,13 @@ struct it
      text, overlay strings, end of text etc., which see.  */
   EMACS_INT stop_charpos;
 
+  /* Previous stop position, i.e. the last one before the current
+     buffer position.  */
+  EMACS_INT prev_stop;
+
+  /* Last stop_pos at the current paragraph's embedding level.  */
+  EMACS_INT base_level_stop;
+
   /* Maximum string or buffer position + 1.  ZV when iterating over
      current_buffer.  */
   EMACS_INT end_charpos;
@@ -2112,6 +2125,8 @@ struct it
     int string_nchars;
     EMACS_INT end_charpos;
     EMACS_INT stop_charpos;
+    EMACS_INT prev_stop;
+    EMACS_INT base_level_stop;
     struct composition_it cmp_it;
     int face_id;
 
diff --git a/src/xdisp.c b/src/xdisp.c
index 2d5314c7f83..ddd18d502a0 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -2659,7 +2659,7 @@ init_iterator (it, w, charpos, bytepos, row, base_face_id)
   /* Are multibyte characters enabled in current_buffer?  */
   it->multibyte_p = !NILP (current_buffer->enable_multibyte_characters);
 
-  /* Do we need to reorded bidirectional text?  */
+  /* Do we need to reorder bidirectional text?  */
   it->bidi_p = !NILP (current_buffer->bidi_display_reordering);
 
   /* Non-zero if we should highlight the region.  */
@@ -5143,6 +5143,8 @@ push_it (it)
   p = it->stack + it->sp;
 
   p->stop_charpos = it->stop_charpos;
+  p->prev_stop = it->prev_stop;
+  p->base_level_stop = it->base_level_stop;
   p->cmp_it = it->cmp_it;
   xassert (it->face_id >= 0);
   p->face_id = it->face_id;
@@ -5193,6 +5195,8 @@ pop_it (it)
   --it->sp;
   p = it->stack + it->sp;
   it->stop_charpos = p->stop_charpos;
+  it->prev_stop = p->prev_stop;
+  it->base_level_stop = p->base_level_stop;
   it->cmp_it = p->cmp_it;
   it->face_id = p->face_id;
   it->current = p->current;
@@ -5569,7 +5573,10 @@ reseat_1 (it, pos, set_stop_p)
     it->bidi_it.first_elt = 1;
 
   if (set_stop_p)
-    it->stop_charpos = CHARPOS (pos);
+    {
+      it->stop_charpos = CHARPOS (pos);
+      it->base_level_stop = CHARPOS (pos);
+    }
 }
 
 
@@ -5673,7 +5680,7 @@ reseat_to_string (it, s, string, charpos, precision, field_width, multibyte)
 
 /***********************************************************************
                               Iteration
- ***********************************************************************/
+***********************************************************************/
 
 /* Map enum it_method value to corresponding next_element_from_* function.  */
 
@@ -5746,7 +5753,7 @@ get_next_display_element (it)
           Lisp_Object dv;
           struct charset *unibyte = CHARSET_FROM_ID (charset_unibyte);
           enum { char_is_other = 0, char_is_nbsp, char_is_soft_hyphen }
-               nbsp_or_shy = char_is_other;
+          nbsp_or_shy = char_is_other;
           int decoded = it->c;
 
           if (it->dp
@@ -5964,12 +5971,12 @@ get_next_display_element (it)
                        happen actually, but due to bugs it may
                        happen.  Let's print the char as is, there's
                        not much meaningful we can do with it.  */
-                      str[0] = it->c;
-                      str[1] = it->c >> 8;
-                      str[2] = it->c >> 16;
-                      str[3] = it->c >> 24;
-                      len = 4;
-                    }
+                    str[0] = it->c;
+                    str[1] = it->c >> 8;
+                    str[2] = it->c >> 16;
+                    str[3] = it->c >> 24;
+                    len = 4;
+                  }
 
                 for (i = 0; i < len; i++)
                   {
@@ -6306,7 +6313,7 @@ next_element_from_display_vector (it)
   it->face_id = it->saved_face_id;
 
   /* KFS: This code used to check ip->dpvec[0] instead of the current element.
-          That seemed totally bogus - so I changed it...  */
+     That seemed totally bogus - so I changed it...  */
   gc = it->dpvec[it->current.dpvec_index];
 
   if (GLYPH_CODE_P (gc) && GLYPH_CODE_CHAR_VALID_P (gc))
@@ -6541,6 +6548,36 @@ next_element_from_stretch (it)
   return 1;
 }
 
+/* Scan forward from CHARPOS in the current buffer, until we find a
+   stop position > current IT's position, handling all the stop
+   positions in between.
+
+   This is called when we are reordering bidirectional text.  The
+   caller should save and restore IT and in particular the bidi_p
+   flag, because this function modifies them.  */
+
+static void
+handle_stop_backwards (it, charpos)
+     struct it *it;
+     EMACS_INT charpos;
+{
+  struct text_pos pos1;
+  EMACS_INT where_we_are = IT_CHARPOS (*it);
+
+  /* Scan in strict logical order.  */
+  it->bidi_p = 0;
+  do
+    {
+      it->prev_stop = charpos;
+      SET_TEXT_POS (pos1, charpos, CHAR_TO_BYTE (charpos));
+      reseat_1 (it, pos1, 0);
+      handle_stop (it);
+      /* We must advance forward, right?  */
+      if (it->stop_charpos <= it->prev_stop)
+        abort ();
+    }
+  while (it->stop_charpos <= where_we_are);
+}
 
 /* Load IT with the next display element from current_buffer.  Value
    is zero if end of buffer reached.  IT->stop_charpos is the next
@@ -6631,12 +6668,45 @@ next_element_from_buffer (it)
               success_p = 0;
             }
         }
+      else if (it->bidi_p && !BIDI_AT_BASE_LEVEL (it->bidi_it))
+        {
+          /* With bidi non-linear iteration, we could find ourselves
+             far beyond the last computed stop_charpos, with several
+             other stop positions in between that we missed.  Scan
+             them all now, in buffer's logical order.  */
+          struct it save_it = *it;
+
+          handle_stop_backwards (it, it->stop_charpos);
+          save_it.stop_charpos = it->stop_charpos;
+          save_it.prev_stop = it->prev_stop;
+          *it = save_it;
+          return GET_NEXT_DISPLAY_ELEMENT (it);
+        }
       else
         {
           handle_stop (it);
+          /* We are at base paragraph embedding level, so take note of
+             the last stop_pos seen at this level.  */
+          it->base_level_stop = it->stop_charpos;
           return GET_NEXT_DISPLAY_ELEMENT (it);
         }
     }
+  else if (it->bidi_p && IT_CHARPOS (*it) < it->prev_stop)
+    {
+      struct it save_it = *it;
+
+      if (it->base_level_stop <= 0)
+        abort ();
+      if (IT_CHARPOS (*it) < it->base_level_stop)
+        abort ();
+      if (BIDI_AT_BASE_LEVEL (it->bidi_it))
+        abort ();
+      handle_stop_backwards (it, it->base_level_stop);
+      save_it.stop_charpos = it->stop_charpos;
+      save_it.prev_stop = it->prev_stop;
+      *it = save_it;
+      return GET_NEXT_DISPLAY_ELEMENT (it);
+    }
   else
     {
       /* No face changes, overlays etc. in sight, so just return a