Support bidi reordering of text covered by display properties.

 src/bidi.c (bidi_copy_it): Use offsetof instead of emulating it.
 (bidi_fetch_char, bidi_fetch_char_advance): New functions.
 (bidi_cache_search, bidi_cache_iterator_state)
 (bidi_paragraph_init, bidi_resolve_explicit, bidi_resolve_weak)
 (bidi_level_of_next_char, bidi_move_to_visually_next): Support
 character positions inside a run of characters covered by a
 display string.
 (bidi_paragraph_init, bidi_resolve_explicit_1)
 (bidi_level_of_next_char): Call bidi_fetch_char and
 bidi_fetch_char_advance instead of FETCH_CHAR and
 FETCH_CHAR_ADVANCE.
 (bidi_init_it): Initialize new members.
 (LRE_CHAR, RLE_CHAR, PDF_CHAR, LRO_CHAR, RLO_CHAR): Remove macro
 definitions.
 (bidi_explicit_dir_char): Lookup character type in bidi_type_table,
 instead of using explicit *_CHAR codes.
 (bidi_resolve_explicit, bidi_resolve_weak): Use
 FETCH_MULTIBYTE_CHAR instead of FETCH_CHAR, as reordering of
 bidirectional text is supported only in multibyte buffers.
 (bidi_init_it): Accept additional argument FRAME_WINDOW_P and use
 it to initialize the frame_window_p member of struct bidi_it.
 (bidi_cache_iterator_state, bidi_resolve_explicit_1)
 (bidi_resolve_explicit, bidi_resolve_weak)
 (bidi_level_of_next_char, bidi_move_to_visually_next): Abort if
 bidi_it->nchars is non-positive.
 (bidi_level_of_next_char): Don't try to lookup the cache for the
 next/previous character if nothing is cached there yet, or if we
 were just reseat()'ed to a new position.
 src/xdisp.c (set_cursor_from_row): Set start and stop points
 according to the row's direction when priming the loop that looks
 for the glyph on which to display cursor.
 (single_display_spec_intangible_p): Function deleted.
 (display_prop_intangible_p): Reimplement to call
 handle_display_spec instead of single_display_spec_intangible_p.
 Accept 3 additional arguments needed by handle_display_spec.  This
 fixes incorrect cursor motion across display property with complex
 values: lists, `(when COND...)' forms, etc.
 (single_display_spec_string_p): Support property values that are
 lists with the argument STRING its top-level element.
 (display_prop_string_p): Fix the condition for processing a
 property that is a list to be consistent with handle_display_spec.
 (handle_display_spec): New function, refactored from the
 last portion of handle_display_prop.
 (compute_display_string_pos): Accept additional argument
 FRAME_WINDOW_P.  Call handle_display_spec to determine whether the
 value of a `display' property is a "replacing spec".
 (handle_single_display_spec): Accept 2 additional arguments BUFPOS
 and FRAME_WINDOW_P.  If IT is NULL, don't set up the iterator from
 the display property, but just return a value indicating whether
 the display property will replace the characters it covers.
 (Fcurrent_bidi_paragraph_direction): Initialize the nchars and
 frame_window_p members of struct bidi_it.
 (compute_display_string_pos, compute_display_string_end): New
 functions.
 (push_it): Accept second argument POSITION, where pop_it should
 jump to continue iteration.
 (reseat_1): Initialize bidi_it.disp_pos.
 src/keyboard.c (adjust_point_for_property): Adjust the call to
 display_prop_intangible_p to its new signature.
 src/dispextern.h (struct bidi_it): New member frame_window_p.
 (bidi_init_it): Update prototypes.
 (display_prop_intangible_p): Update prototype.
 (compute_display_string_pos, compute_display_string_end): Declare
 prototypes.
 (struct bidi_it): New members nchars and disp_pos.  ch_len is now
 EMACS_INT.

5 files changed, 649 insertions, 318 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index 45d8e38738a..4c33bcc4e67 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,77 @@
+2011-06-03  Eli Zaretskii  <eliz@gnu.org>
+
+        Support bidi reordering of text covered by display properties.
+
+        * bidi.c (bidi_copy_it): Use offsetof instead of emulating it.
+        (bidi_fetch_char, bidi_fetch_char_advance): New functions.
+        (bidi_cache_search, bidi_cache_iterator_state)
+        (bidi_paragraph_init, bidi_resolve_explicit, bidi_resolve_weak)
+        (bidi_level_of_next_char, bidi_move_to_visually_next): Support
+        character positions inside a run of characters covered by a
+        display string.
+        (bidi_paragraph_init, bidi_resolve_explicit_1)
+        (bidi_level_of_next_char): Call bidi_fetch_char and
+        bidi_fetch_char_advance instead of FETCH_CHAR and
+        FETCH_CHAR_ADVANCE.
+        (bidi_init_it): Initialize new members.
+        (LRE_CHAR, RLE_CHAR, PDF_CHAR, LRO_CHAR, RLO_CHAR): Remove macro
+        definitions.
+        (bidi_explicit_dir_char): Lookup character type in bidi_type_table,
+        instead of using explicit *_CHAR codes.
+        (bidi_resolve_explicit, bidi_resolve_weak): Use
+        FETCH_MULTIBYTE_CHAR instead of FETCH_CHAR, as reordering of
+        bidirectional text is supported only in multibyte buffers.
+        (bidi_init_it): Accept additional argument FRAME_WINDOW_P and use
+        it to initialize the frame_window_p member of struct bidi_it.
+        (bidi_cache_iterator_state, bidi_resolve_explicit_1)
+        (bidi_resolve_explicit, bidi_resolve_weak)
+        (bidi_level_of_next_char, bidi_move_to_visually_next): Abort if
+        bidi_it->nchars is non-positive.
+        (bidi_level_of_next_char): Don't try to lookup the cache for the
+        next/previous character if nothing is cached there yet, or if we
+        were just reseat()'ed to a new position.
+
+        * xdisp.c (set_cursor_from_row): Set start and stop points
+        according to the row's direction when priming the loop that looks
+        for the glyph on which to display cursor.
+        (single_display_spec_intangible_p): Function deleted.
+        (display_prop_intangible_p): Reimplement to call
+        handle_display_spec instead of single_display_spec_intangible_p.
+        Accept 3 additional arguments needed by handle_display_spec.  This
+        fixes incorrect cursor motion across display property with complex
+        values: lists, `(when COND...)' forms, etc.
+        (single_display_spec_string_p): Support property values that are
+        lists with the argument STRING its top-level element.
+        (display_prop_string_p): Fix the condition for processing a
+        property that is a list to be consistent with handle_display_spec.
+        (handle_display_spec): New function, refactored from the
+        last portion of handle_display_prop.
+        (compute_display_string_pos): Accept additional argument
+        FRAME_WINDOW_P.  Call handle_display_spec to determine whether the
+        value of a `display' property is a "replacing spec".
+        (handle_single_display_spec): Accept 2 additional arguments BUFPOS
+        and FRAME_WINDOW_P.  If IT is NULL, don't set up the iterator from
+        the display property, but just return a value indicating whether
+        the display property will replace the characters it covers.
+        (Fcurrent_bidi_paragraph_direction): Initialize the nchars and
+        frame_window_p members of struct bidi_it.
+        (compute_display_string_pos, compute_display_string_end): New
+        functions.
+        (push_it): Accept second argument POSITION, where pop_it should
+        jump to continue iteration.
+        (reseat_1): Initialize bidi_it.disp_pos.
+
+        * keyboard.c (adjust_point_for_property): Adjust the call to
+        display_prop_intangible_p to its new signature.
+
+        * dispextern.h (struct bidi_it): New member frame_window_p.
+        (bidi_init_it): Update prototypes.
+        (display_prop_intangible_p): Update prototype.
+        (compute_display_string_pos, compute_display_string_end): Declare
+        prototypes.
+        (struct bidi_it): New members nchars and disp_pos.  ch_len is now
+        EMACS_INT.
+
 2011-06-02  Paul Eggert  <eggert@cs.ucla.edu>
 
         Malloc failure behavior now depends on size of allocation.
diff --git a/src/bidi.c b/src/bidi.c
index b05fd21e5b6..a41f50d9ca5 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -62,15 +62,8 @@ static int bidi_initialized = 0;
 
 static Lisp_Object bidi_type_table, bidi_mirror_table;
 
-/* FIXME: Remove these when bidi_explicit_dir_char uses a lookup table.  */
 #define LRM_CHAR   0x200E
 #define RLM_CHAR   0x200F
-#define LRE_CHAR   0x202A
-#define RLE_CHAR   0x202B
-#define PDF_CHAR   0x202C
-#define LRO_CHAR   0x202D
-#define RLO_CHAR   0x202E
-
 #define BIDI_EOB   -1
 
 /* Local data structures.  (Look in dispextern.h for the rest.)  */
@@ -258,7 +251,7 @@ bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
   int i;
 
   /* Copy everything except the level stack and beyond.  */
-  memcpy (to, from, ((size_t)&((struct bidi_it *)0)->level_stack[0]));
+  memcpy (to, from, offsetof (struct bidi_it, 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 */
@@ -319,10 +312,17 @@ bidi_cache_search (EMACS_INT charpos, int level, int dir)
   if (bidi_cache_idx)
     {
       if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
-        dir = -1;
-      else if (charpos > bidi_cache[bidi_cache_last_idx].charpos)
-        dir = 1;
-      if (dir)
+        {
+          dir = -1;
+          i_start = bidi_cache_last_idx - 1;
+        }
+      else if (charpos > (bidi_cache[bidi_cache_last_idx].charpos
+                          + bidi_cache[bidi_cache_last_idx].nchars - 1))
+        {
+          dir = 1;
+          i_start = bidi_cache_last_idx + 1;
+        }
+      else if (dir)
         i_start = bidi_cache_last_idx;
       else
         {
@@ -334,14 +334,16 @@ bidi_cache_search (EMACS_INT charpos, int level, int dir)
         {
           /* Linear search for now; FIXME!  */
           for (i = i_start; i >= 0; i--)
-            if (bidi_cache[i].charpos == charpos
+            if (bidi_cache[i].charpos <= charpos
+                && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
                 && (level == -1 || bidi_cache[i].resolved_level <= level))
               return i;
         }
       else
         {
           for (i = i_start; i < bidi_cache_idx; i++)
-            if (bidi_cache[i].charpos == charpos
+            if (bidi_cache[i].charpos <= charpos
+                && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
                 && (level == -1 || bidi_cache[i].resolved_level <= level))
               return i;
         }
@@ -426,12 +428,15 @@ bidi_cache_iterator_state (struct bidi_it *bidi_it, int resolved)
          If we are outside the range of cached positions, the cache is
          useless and must be reset.  */
       if (idx > 0 &&
-          (bidi_it->charpos > bidi_cache[idx - 1].charpos + 1
+          (bidi_it->charpos > (bidi_cache[idx - 1].charpos
+                               + bidi_cache[idx - 1].nchars)
            || bidi_it->charpos < bidi_cache[0].charpos))
         {
           bidi_cache_reset ();
           idx = 0;
         }
+      if (bidi_it->nchars <= 0)
+        abort ();
       bidi_copy_it (&bidi_cache[idx], bidi_it);
       if (!resolved)
         bidi_cache[idx].resolved_level = -1;
@@ -548,6 +553,7 @@ bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
   bidi_it->ignore_bn_limit = 0; /* meaning it's unknown */
 }
 
+/* Perform initializations for reordering a new line of bidi text.  */
 static void
 bidi_line_init (struct bidi_it *bidi_it)
 {
@@ -565,6 +571,65 @@ bidi_line_init (struct bidi_it *bidi_it)
   bidi_cache_reset ();
 }
 
+/* Fetch and return the character at BYTEPOS/CHARPOS.  If that
+   character is covered by a display string, treat the entire run of
+   covered characters as a single character u+FFFC, and return their
+   combined length in CH_LEN and NCHARS.  DISP_POS specifies the
+   character position of the next display string, or -1 if not yet
+   computed.  When the next character is at or beyond that position,
+   the function updates DISP_POS with the position of the next display
+   string.  */
+static inline int
+bidi_fetch_char (EMACS_INT bytepos, EMACS_INT charpos, EMACS_INT *disp_pos,
+                 int frame_window_p, EMACS_INT *ch_len, EMACS_INT *nchars)
+{
+  int ch;
+
+  /* FIXME: Support strings in addition to buffers.  */
+  /* If we got past the last known position of display string, compute
+     the position of the next one.  That position could be at BYTEPOS.  */
+  if (charpos < ZV && charpos > *disp_pos)
+    *disp_pos = compute_display_string_pos (charpos, frame_window_p);
+
+  /* Fetch the character at BYTEPOS.  */
+  if (bytepos >= ZV_BYTE)
+    {
+      ch = BIDI_EOB;
+      *ch_len = 1;
+      *nchars = 1;
+      *disp_pos = ZV;
+    }
+  else if (charpos >= *disp_pos)
+    {
+      EMACS_INT disp_end_pos;
+
+      /* We don't expect to find ourselves in the middle of a display
+         property.  Hopefully, it will never be needed.  */
+      if (charpos > *disp_pos)
+        abort ();
+      /* Return the Unicode Object Replacement Character to represent
+         the entire run of characters covered by the display
+         string.  */
+      ch = 0xFFFC;
+      disp_end_pos = compute_display_string_end (*disp_pos);
+      *nchars = disp_end_pos - *disp_pos;
+      *ch_len = CHAR_TO_BYTE (disp_end_pos) - bytepos;
+    }
+  else
+    {
+      ch = FETCH_MULTIBYTE_CHAR (bytepos);
+      *nchars = 1;
+      *ch_len = CHAR_BYTES (ch);
+    }
+
+  /* If we just entered a run of characters covered by a display
+     string, compute the position of the next display string.  */
+  if (charpos + *nchars <= ZV && charpos + *nchars > *disp_pos)
+    *disp_pos = compute_display_string_pos (charpos + *nchars, frame_window_p);
+
+  return ch;
+}
+
 /* Find the beginning of this paragraph by looking back in the buffer.
    Value is the byte position of the paragraph's beginning.  */
 static EMACS_INT
@@ -576,6 +641,10 @@ bidi_find_paragraph_start (EMACS_INT pos, EMACS_INT pos_byte)
   while (pos_byte > BEGV_BYTE
          && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
     {
+      /* FIXME: What if the paragraph beginning is covered by a
+         display string?  And what if a display string covering some
+         of the text over which we scan back includes
+         paragraph_start_re?  */
       pos = find_next_newline_no_quit (pos - 1, -1);
       pos_byte = CHAR_TO_BYTE (pos);
     }
@@ -587,7 +656,7 @@ bidi_find_paragraph_start (EMACS_INT pos, EMACS_INT pos_byte)
    R2L, just use that.  Otherwise, determine the paragraph direction
    from the first strong directional character of the paragraph.
 
-   NO_DEFAULT_P non-nil means don't default to L2R if the paragraph
+   NO_DEFAULT_P non-zero means don't default to L2R if the paragraph
    has no strong directional characters and both DIR and
    bidi_it->paragraph_dir are NEUTRAL_DIR.  In that case, search back
    in the buffer until a paragraph is found with a strong character,
@@ -622,8 +691,9 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
     }
   else if (dir == NEUTRAL_DIR)  /* P2 */
     {
-      int ch, ch_len;
-      EMACS_INT pos;
+      int ch;
+      EMACS_INT ch_len, nchars;
+      EMACS_INT pos, disp_pos = -1;
       bidi_type_t type;
 
       if (!bidi_initialized)
@@ -658,12 +728,12 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
          is non-zero.  */
       do {
         bytepos = pstartbyte;
-        ch = FETCH_CHAR (bytepos);
-        ch_len = CHAR_BYTES (ch);
         pos = BYTE_TO_CHAR (bytepos);
+        ch = bidi_fetch_char (bytepos, pos, &disp_pos, bidi_it->frame_window_p,
+                              &ch_len, &nchars);
         type = bidi_get_type (ch, NEUTRAL_DIR);
 
-        for (pos++, bytepos += ch_len;
+        for (pos += nchars, bytepos += ch_len;
              /* NOTE: UAX#9 says to search only for L, AL, or R types
                 of characters, and ignore RLE, RLO, LRE, and LRO.
                 However, I'm not sure it makes sense to omit those 4;
@@ -683,7 +753,11 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
                 type = NEUTRAL_B;
                 break;
               }
-            FETCH_CHAR_ADVANCE (ch, pos, bytepos);
+            /* Fetch next character and advance to get past it.  */
+            ch = bidi_fetch_char (bytepos, pos, &disp_pos,
+                                  bidi_it->frame_window_p, &ch_len, &nchars);
+            pos += nchars;
+            bytepos += ch_len;
           }
         if (type == STRONG_R || type == STRONG_AL) /* P3 */
           bidi_it->paragraph_dir = R2L;
@@ -702,6 +776,9 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
                 /* Find the beginning of the previous paragraph, if any.  */
                 while (pbyte > BEGV_BYTE && prevpbyte >= pstartbyte)
                   {
+                    /* FXIME: What if p is covered by a display
+                       string?  See also a FIXME inside
+                       bidi_find_paragraph_start.  */
                     p--;
                     pbyte = CHAR_TO_BYTE (p);
                     prevpbyte = bidi_find_paragraph_start (p, pbyte);
@@ -738,14 +815,17 @@ bidi_set_paragraph_end (struct bidi_it *bidi_it)
   bidi_it->resolved_level = bidi_it->level_stack[0].level;
 }
 
-/* Initialize the bidi iterator from buffer position CHARPOS.  */
+/* Initialize the bidi iterator from buffer/string position CHARPOS.  */
 void
-bidi_init_it (EMACS_INT charpos, EMACS_INT bytepos, struct bidi_it *bidi_it)
+bidi_init_it (EMACS_INT charpos, EMACS_INT bytepos, int frame_window_p,
+              struct bidi_it *bidi_it)
 {
   if (! bidi_initialized)
     bidi_initialize ();
   bidi_it->charpos = charpos;
   bidi_it->bytepos = bytepos;
+  bidi_it->frame_window_p = frame_window_p;
+  bidi_it->nchars = -1; /* to be computed in bidi_resolve_explicit_1 */
   bidi_it->first_elt = 1;
   bidi_set_paragraph_end (bidi_it);
   bidi_it->new_paragraph = 1;
@@ -767,6 +847,7 @@ bidi_init_it (EMACS_INT charpos, EMACS_INT bytepos, struct bidi_it *bidi_it)
     bidi_it->prev_for_neutral.type_after_w1 =
     bidi_it->prev_for_neutral.orig_type = UNKNOWN_BT;
   bidi_it->sor = L2R;    /* FIXME: should it be user-selectable? */
+  bidi_it->disp_pos = -1;       /* invalid/unknown */
   bidi_cache_shrink ();
 }
 
@@ -829,12 +910,16 @@ bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
 }
 
 static inline int
-bidi_explicit_dir_char (int c)
+bidi_explicit_dir_char (int ch)
 {
-  /* FIXME: this should be replaced with a lookup table with suitable
-     bits set, like standard C ctype macros do.  */
-  return (c == LRE_CHAR || c == LRO_CHAR
-          || c == RLE_CHAR || c == RLO_CHAR || c == PDF_CHAR);
+  bidi_type_t ch_type;
+
+  if (!bidi_initialized)
+    abort ();
+  ch_type = (bidi_type_t) XINT (CHAR_TABLE_REF (bidi_type_table, ch));
+  return (ch_type == LRE || ch_type == LRO
+          || ch_type == RLE || ch_type == RLO
+          || ch_type == PDF);
 }
 
 /* A helper function for bidi_resolve_explicit.  It advances to the
@@ -850,7 +935,10 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
   int new_level;
   bidi_dir_t override;
 
-  if (bidi_it->bytepos < BEGV_BYTE      /* after reseat to BEGV? */
+  /* If reseat()'ed, don't advance, so as to start iteration from the
+     position where we were reseated.  bidi_it->bytepos can be less
+     than BEGV_BYTE after reseat to BEGV.  */
+  if (bidi_it->bytepos < BEGV_BYTE
       || bidi_it->first_elt)
     {
       bidi_it->first_elt = 0;
@@ -860,7 +948,11 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
     }
   else if (bidi_it->bytepos < ZV_BYTE)  /* don't move at ZV */
     {
-      bidi_it->charpos++;
+      /* Advance to the next character, skipping characters covered by
+         display strings (nchars > 1).  */
+      if (bidi_it->nchars <= 0)
+        abort ();
+      bidi_it->charpos += bidi_it->nchars;
       if (bidi_it->ch_len == 0)
         abort ();
       bidi_it->bytepos += bidi_it->ch_len;
@@ -870,17 +962,21 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
   override = bidi_it->level_stack[bidi_it->stack_idx].override;
   new_level = current_level;
 
-  /* in case it is a unibyte character (not yet implemented) */
-  /* _fetch_multibyte_char_len = 1; */
   if (bidi_it->bytepos >= ZV_BYTE)
     {
       curchar = BIDI_EOB;
       bidi_it->ch_len = 1;
+      bidi_it->nchars = 1;
+      bidi_it->disp_pos = ZV;
     }
   else
     {
-      curchar = FETCH_CHAR (bidi_it->bytepos);
-      bidi_it->ch_len = CHAR_BYTES (curchar);
+      /* Fetch the character at BYTEPOS.  If it is covered by a
+         display string, treat the entire run of covered characters as
+         a single character u+FFFC.  */
+      curchar = bidi_fetch_char (bidi_it->bytepos, bidi_it->charpos,
+                                 &bidi_it->disp_pos, bidi_it->frame_window_p,
+                                 &bidi_it->ch_len, &bidi_it->nchars);
     }
   bidi_it->ch = curchar;
 
@@ -1006,10 +1102,10 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
 }
 
 /* Given an iterator state in BIDI_IT, advance one character position
-   in the buffer to the next character (in the logical order), resolve
-   any explicit embeddings and directional overrides, and return the
-   embedding level of the character after resolving explicit
-   directives and ignoring empty embeddings.  */
+   in the buffer/string to the next character (in the logical order),
+   resolve any explicit embeddings and directional overrides, and
+   return the embedding level of the character after resolving
+   explicit directives and ignoring empty embeddings.  */
 static int
 bidi_resolve_explicit (struct bidi_it *bidi_it)
 {
@@ -1020,8 +1116,8 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
       && bidi_it->type == WEAK_BN
       && bidi_it->ignore_bn_limit == 0 /* only if not already known */
       && bidi_it->bytepos < ZV_BYTE    /* not already at EOB */
-      && bidi_explicit_dir_char (FETCH_CHAR (bidi_it->bytepos
-                                             + bidi_it->ch_len)))
+      && bidi_explicit_dir_char (FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
+                                                       + bidi_it->ch_len)))
     {
       /* Avoid pushing and popping embedding levels if the level run
          is empty, as this breaks level runs where it shouldn't.
@@ -1033,14 +1129,18 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
 
       bidi_copy_it (&saved_it, bidi_it);
 
-      while (bidi_explicit_dir_char (FETCH_CHAR (bidi_it->bytepos
-                                                 + bidi_it->ch_len)))
+      while (bidi_explicit_dir_char (FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
+                                                           + bidi_it->ch_len)))
         {
+          /* This advances to the next character, skipping any
+             characters covered by display strings.  */
           level = bidi_resolve_explicit_1 (bidi_it);
         }
 
+      if (bidi_it->nchars <= 0)
+        abort ();
       if (level == prev_level)  /* empty embedding */
-        saved_it.ignore_bn_limit = bidi_it->charpos + 1;
+        saved_it.ignore_bn_limit = bidi_it->charpos + bidi_it->nchars;
       else                      /* this embedding is non-empty */
         saved_it.ignore_bn_limit = -1;
 
@@ -1076,8 +1176,8 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
   return new_level;
 }
 
-/* Advance in the buffer, resolve weak types and return the type of
-   the next character after weak type resolution.  */
+/* Advance in the buffer/string, resolve weak types and return the
+   type of the next character after weak type resolution.  */
 static bidi_type_t
 bidi_resolve_weak (struct bidi_it *bidi_it)
 {
@@ -1156,7 +1256,8 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
         {
           next_char =
             bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
-            ? BIDI_EOB : FETCH_CHAR (bidi_it->bytepos + bidi_it->ch_len);
+            ? BIDI_EOB : FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
+                                               + bidi_it->ch_len);
           type_of_next = bidi_get_type (next_char, override);
 
           if (type_of_next == WEAK_BN
@@ -1204,11 +1305,14 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
             type = WEAK_EN;
           else                  /* W5: ET/BN with EN after it.  */
             {
-              EMACS_INT en_pos = bidi_it->charpos + 1;
+              EMACS_INT en_pos = bidi_it->charpos + bidi_it->nchars;
 
+              if (bidi_it->nchars <= 0)
+                abort ();
               next_char =
                 bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
-                ? BIDI_EOB : FETCH_CHAR (bidi_it->bytepos + bidi_it->ch_len);
+                ? BIDI_EOB : FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
+                                                   + bidi_it->ch_len);
               type_of_next = bidi_get_type (next_char, override);
 
               if (type_of_next == WEAK_ET
@@ -1299,8 +1403,8 @@ bidi_resolve_neutral (struct bidi_it *bidi_it)
           /* Arrrgh!!  The UAX#9 algorithm is too deeply entrenched in
              the assumption of batch-style processing; see clauses W4,
              W5, and especially N1, which require to look far forward
-             (as well as back) in the buffer.  May the fleas of a
-             thousand camels infest the armpits of those who design
+             (as well as back) in the buffer/string.  May the fleas of
+             a thousand camels infest the armpits of those who design
              supposedly general-purpose algorithms by looking at their
              own implementations, and fail to consider other possible
              implementations!  */
@@ -1391,8 +1495,9 @@ bidi_resolve_neutral (struct bidi_it *bidi_it)
 }
 
 /* Given an iterator state in BIDI_IT, advance one character position
-   in the buffer to the next character (in the logical order), resolve
-   the bidi type of that next character, and return that type.  */
+   in the buffer/string to the next character (in the logical order),
+   resolve the bidi type of that next character, and return that
+   type.  */
 static bidi_type_t
 bidi_type_of_next_char (struct bidi_it *bidi_it)
 {
@@ -1416,15 +1521,16 @@ bidi_type_of_next_char (struct bidi_it *bidi_it)
 }
 
 /* Given an iterator state BIDI_IT, advance one character position in
-   the buffer to the next character (in the logical order), resolve
-   the embedding and implicit levels of that next character, and
-   return the resulting level.  */
+   the buffer/string to the next character (in the current scan
+   direction), resolve the embedding and implicit levels of that next
+   character, and return the resulting level.  */
 static int
 bidi_level_of_next_char (struct bidi_it *bidi_it)
 {
   bidi_type_t type;
   int level, prev_level = -1;
   struct bidi_saved_info next_for_neutral;
+  EMACS_INT next_char_pos;
 
   if (bidi_it->scan_dir == 1)
     {
@@ -1466,8 +1572,23 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
     }
   next_for_neutral = bidi_it->next_for_neutral;
 
-  /* Perhaps it is already cached.  */
-  type = bidi_cache_find (bidi_it->charpos + bidi_it->scan_dir, -1, bidi_it);
+  /* Perhaps the character we want is already cached.  If it is, the
+     call to bidi_cache_find below will return a type other than
+     UNKNOWN_BT.  */
+  if (bidi_cache_idx && !bidi_it->first_elt)
+    {
+      if (bidi_it->scan_dir > 0)
+        {
+          if (bidi_it->nchars <= 0)
+            abort ();
+          next_char_pos = bidi_it->charpos + bidi_it->nchars;
+        }
+      else
+        next_char_pos = bidi_it->charpos - 1;
+      type = bidi_cache_find (next_char_pos, -1, bidi_it);
+    }
+  else
+    type = UNKNOWN_BT;
   if (type != UNKNOWN_BT)
     {
       /* Don't lose the information for resolving neutrals!  The
@@ -1529,14 +1650,16 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
       int clen = bidi_it->ch_len;
       EMACS_INT bpos = bidi_it->bytepos;
       EMACS_INT cpos = bidi_it->charpos;
+      EMACS_INT disp_pos = bidi_it->disp_pos;
+      EMACS_INT nc = bidi_it->nchars;
       bidi_type_t chtype;
+      int fwp = bidi_it->frame_window_p;
 
+      if (bidi_it->nchars <= 0)
+        abort ();
       do {
-        /*_fetch_multibyte_char_len = 1;*/
-        ch = bpos + clen >= ZV_BYTE ? BIDI_EOB : FETCH_CHAR (bpos + clen);
-        bpos += clen;
-        cpos++;
-        clen = (ch == BIDI_EOB ? 1 : CHAR_BYTES (ch));
+        ch = bidi_fetch_char (bpos += clen, cpos += nc, &disp_pos, fwp,
+                              &clen, &nc);
         if (ch == '\n' || ch == BIDI_EOB /* || ch == LINESEP_CHAR */)
           chtype = NEUTRAL_B;
         else
@@ -1615,8 +1738,8 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
 
    If this level's other edge is cached, we simply jump to it, filling
    the iterator structure with the iterator state on the other edge.
-   Otherwise, we walk the buffer until we come back to the same level
-   as LEVEL.
+   Otherwise, we walk the buffer or string until we come back to the
+   same level as LEVEL.
 
    Note: we are not talking here about a ``level run'' in the UAX#9
    sense of the term, but rather about a ``level'' which includes
@@ -1680,6 +1803,7 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
           sentinel.bytepos--;
           sentinel.ch = '\n';   /* doesn't matter, but why not? */
           sentinel.ch_len = 1;
+          sentinel.nchars = 1;
         }
       bidi_cache_iterator_state (&sentinel, 1);
     }
@@ -1750,14 +1874,17 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
       && bidi_it->bytepos < ZV_BYTE)
     {
       EMACS_INT sep_len =
-        bidi_at_paragraph_end (bidi_it->charpos + 1,
+        bidi_at_paragraph_end (bidi_it->charpos + bidi_it->nchars,
                                bidi_it->bytepos + bidi_it->ch_len);
+      if (bidi_it->nchars <= 0)
+        abort ();
       if (sep_len >= 0)
         {
           bidi_it->new_paragraph = 1;
           /* Record the buffer position of the last character of the
              paragraph separator.  */
-          bidi_it->separator_limit = bidi_it->charpos + 1 + sep_len;
+          bidi_it->separator_limit =
+            bidi_it->charpos + bidi_it->nchars + sep_len;
         }
     }
 
@@ -1767,7 +1894,8 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
          last cached position, the cache's job is done and we can
          discard it.  */
       if (bidi_it->resolved_level == bidi_it->level_stack[0].level
-          && bidi_it->charpos > bidi_cache[bidi_cache_idx - 1].charpos)
+          && bidi_it->charpos > (bidi_cache[bidi_cache_idx - 1].charpos
+                                 + bidi_cache[bidi_cache_idx - 1].nchars - 1))
         bidi_cache_reset ();
         /* But as long as we are caching during forward scan, we must
            cache each state, or else the cache integrity will be
diff --git a/src/dispextern.h b/src/dispextern.h
index e612a8b1eba..15e44e0286e 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -1816,12 +1816,16 @@ struct bidi_stack {
   bidi_dir_t override;
 };
 
-/* Data type for iterating over bidi text.  */
+/* Data type for reordering bidirectional text.  */
 struct bidi_it {
   EMACS_INT bytepos;            /* iterator's position in buffer */
   EMACS_INT charpos;
-  int ch;                       /* character itself */
-  int ch_len;                   /* length of its multibyte sequence */
+  int ch;                       /* character at that position, or u+FFFC
+                                   ("object replacement character") for a run
+                                   of characters covered by a display string */
+  EMACS_INT nchars;             /* its "length", usually 1; it's > 1 for a run
+                                   of characters covered by a display string */
+  EMACS_INT ch_len;             /* its length in bytes */
   bidi_type_t type;             /* bidi type of this character, after
                                    resolving weak and neutral types */
   bidi_type_t type_after_w1;    /* original type, after overrides and W1 */
@@ -1847,7 +1851,9 @@ struct bidi_it {
   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 */
+  int frame_window_p;           /* non-zero if displaying on a GUI frame */
   EMACS_INT separator_limit;    /* where paragraph separator should end */
+  EMACS_INT disp_pos;           /* position of display string after ch */
 };
 
 /* Value is non-zero when the bidi iterator is at base paragraph
@@ -2944,7 +2950,7 @@ enum tool_bar_item_image
 
 /* Defined in bidi.c */
 
-extern void bidi_init_it (EMACS_INT, EMACS_INT, struct bidi_it *);
+extern void bidi_init_it (EMACS_INT, EMACS_INT, int, struct bidi_it *);
 extern void bidi_move_to_visually_next (struct bidi_it *);
 extern void bidi_paragraph_init (bidi_dir_t, struct bidi_it *, int);
 extern int  bidi_mirror_char (int);
@@ -2955,7 +2961,7 @@ struct glyph_row *row_containing_pos (struct window *, EMACS_INT,
                                       struct glyph_row *,
                                       struct glyph_row *, int);
 int line_bottom_y (struct it *);
-int display_prop_intangible_p (Lisp_Object);
+int display_prop_intangible_p (Lisp_Object, Lisp_Object, EMACS_INT, EMACS_INT);
 void resize_echo_area_exactly (void);
 int resize_mini_window (struct window *, int);
 #if defined USE_TOOLKIT_SCROLL_BARS && !defined USE_GTK
@@ -3005,6 +3011,8 @@ extern void reseat_at_previous_visible_line_start (struct it *);
 extern Lisp_Object lookup_glyphless_char_display (int, struct it *);
 extern int calc_pixel_width_or_height (double *, struct it *, Lisp_Object,
                                        struct font *, int, int *);
+extern EMACS_INT compute_display_string_pos (EMACS_INT, int);
+extern EMACS_INT compute_display_string_end (EMACS_INT);
 
 #ifdef HAVE_WINDOW_SYSTEM
 
diff --git a/src/keyboard.c b/src/keyboard.c
index 7bc406aab31..6eb3773af99 100644
--- a/src/keyboard.c
+++ b/src/keyboard.c
@@ -1729,7 +1729,7 @@ adjust_point_for_property (EMACS_INT last_pt, int modified)
           && PT > BEGV && PT < ZV
           && !NILP (val = get_char_property_and_overlay
                               (make_number (PT), Qdisplay, Qnil, &overlay))
-          && display_prop_intangible_p (val)
+          && display_prop_intangible_p (val, overlay, PT, PT_BYTE)
           && (!OVERLAYP (overlay)
               ? get_property_and_range (PT, Qdisplay, &val, &beg, &end, Qnil)
               : (beg = OVERLAY_POSITION (OVERLAY_START (overlay)),
diff --git a/src/xdisp.c b/src/xdisp.c
index d67cc63be79..958e7510e1d 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -812,7 +812,7 @@ static int try_scrolling (Lisp_Object, int, EMACS_INT, EMACS_INT, int, int);
 static int try_cursor_movement (Lisp_Object, struct text_pos, int *);
 static int trailing_whitespace_p (EMACS_INT);
 static unsigned long int message_log_check_duplicate (EMACS_INT, EMACS_INT);
-static void push_it (struct it *);
+static void push_it (struct it *, struct text_pos *);
 static void pop_it (struct it *);
 static void sync_frame_with_window_matrix_rows (struct window *);
 static void select_frame_for_redisplay (Lisp_Object);
@@ -884,9 +884,11 @@ static void compute_string_pos (struct text_pos *, struct text_pos,
                                 Lisp_Object);
 static int face_before_or_after_it_pos (struct it *, int);
 static EMACS_INT next_overlay_change (EMACS_INT);
+static int handle_display_spec (struct it *, Lisp_Object, Lisp_Object,
+                                Lisp_Object, struct text_pos *, EMACS_INT, int);
 static int handle_single_display_spec (struct it *, Lisp_Object,
                                        Lisp_Object, Lisp_Object,
-                                       struct text_pos *, int);
+                                       struct text_pos *, EMACS_INT, int, int);
 static int underlying_face_id (struct it *);
 static int in_ellipses_for_invisible_text_p (struct display_pos *,
                                              struct window *);
@@ -2564,7 +2566,7 @@ init_iterator (struct it *it, struct window *w,
         it->paragraph_embedding = R2L;
       else
         it->paragraph_embedding = NEUTRAL_DIR;
-      bidi_init_it (charpos, bytepos, &it->bidi_it);
+      bidi_init_it (charpos, bytepos, FRAME_WINDOW_P (it->f), &it->bidi_it);
     }
 
   /* If a buffer position was specified, set the iterator there,
@@ -3085,6 +3087,82 @@ next_overlay_change (EMACS_INT pos)
   return endpos;
 }
 
+/* Return the character position of a display string at or after CHARPOS.
+   If no display string exists at or after CHARPOS, return ZV.  A
+   display string is either an overlay with `display' property whose
+   value is a string, or a `display' text property whose value is a
+   string.  FRAME_WINDOW_P is non-zero when we are displaying a window
+   on a GUI frame.  */
+EMACS_INT
+compute_display_string_pos (EMACS_INT charpos, int frame_window_p)
+{
+  /* FIXME: Support display properties on strings (object = Qnil means
+     current buffer).  */
+  Lisp_Object object = Qnil;
+  Lisp_Object pos, spec;
+  struct text_pos position;
+  EMACS_INT bufpos;
+
+  if (charpos >= ZV)
+    return ZV;
+
+  /* If the character at CHARPOS is where the display string begins,
+     return CHARPOS.  */
+  pos = make_number (charpos);
+  CHARPOS (position) = charpos;
+  BYTEPOS (position) = CHAR_TO_BYTE (charpos);
+  bufpos = charpos;     /* FIXME! support strings as well */
+  if (!NILP (spec = Fget_char_property (pos, Qdisplay, object))
+      && (charpos <= BEGV
+          || !EQ (Fget_char_property (make_number (charpos - 1), Qdisplay,
+                                      object),
+                  spec))
+      && handle_display_spec (NULL, spec, object, Qnil, &position, bufpos,
+                              frame_window_p))
+    return charpos;
+
+  /* Look forward for the first character with a `display' property
+     that will replace the underlying text when displayed.  */
+  do {
+    pos = Fnext_single_char_property_change (pos, Qdisplay, object, Qnil);
+    CHARPOS (position) = XFASTINT (pos);
+    BYTEPOS (position) = CHAR_TO_BYTE (CHARPOS (position));
+    if (CHARPOS (position) >= ZV)
+      break;
+    spec = Fget_char_property (pos, Qdisplay, object);
+    bufpos = CHARPOS (position);        /* FIXME! support strings as well */
+  } while (NILP (spec)
+           || !handle_display_spec (NULL, spec, object, Qnil, &position, bufpos,
+                                    frame_window_p));
+
+  return CHARPOS (position);
+}
+
+/* Return the character position of the end of the display string that
+   started at CHARPOS.  A display string is either an overlay with
+   `display' property whose value is a string or a `display' text
+   property whose value is a string.  */
+EMACS_INT
+compute_display_string_end (EMACS_INT charpos)
+{
+  /* FIXME: Support display properties on strings (object = Qnil means
+     current buffer).  */
+  Lisp_Object object = Qnil;
+  Lisp_Object pos = make_number (charpos);
+
+  if (charpos >= ZV)
+    return ZV;
+
+  if (NILP (Fget_char_property (pos, Qdisplay, object)))
+    abort ();
+
+  /* Look forward for the first character where the `display' property
+     changes.  */
+  pos = Fnext_single_char_property_change (pos, Qdisplay, object, Qnil);
+
+  return XFASTINT (pos);
+}
+
 
 
 /***********************************************************************
@@ -3743,8 +3821,9 @@ setup_for_ellipsis (struct it *it, int len)
 static enum prop_handled
 handle_display_prop (struct it *it)
 {
-  Lisp_Object prop, object, overlay;
+  Lisp_Object propval, object, overlay;
   struct text_pos *position;
+  EMACS_INT bufpos;
   /* Nonzero if some property replaces the display of the text itself.  */
   int display_replaced_p = 0;
 
@@ -3752,11 +3831,13 @@ handle_display_prop (struct it *it)
     {
       object = it->string;
       position = &it->current.string_pos;
+      bufpos = CHARPOS (it->current.pos);
     }
   else
     {
       XSETWINDOW (object, it->w);
       position = &it->current.pos;
+      bufpos = CHARPOS (*position);
     }
 
   /* Reset those iterator values set from display property values.  */
@@ -3771,9 +3852,9 @@ handle_display_prop (struct it *it)
   if (!it->string_from_display_prop_p)
     it->area = TEXT_AREA;
 
-  prop = get_char_property_and_overlay (make_number (position->charpos),
-                                        Qdisplay, object, &overlay);
-  if (NILP (prop))
+  propval = get_char_property_and_overlay (make_number (position->charpos),
+                                           Qdisplay, object, &overlay);
+  if (NILP (propval))
     return HANDLED_NORMALLY;
   /* Now OVERLAY is the overlay that gave us this property, or nil
      if it was a text property.  */
@@ -3781,59 +3862,88 @@ handle_display_prop (struct it *it)
   if (!STRINGP (it->string))
     object = it->w->buffer;
 
-  if (CONSP (prop)
-      /* Simple properties.  */
-      && !EQ (XCAR (prop), Qimage)
-      && !EQ (XCAR (prop), Qspace)
-      && !EQ (XCAR (prop), Qwhen)
-      && !EQ (XCAR (prop), Qslice)
-      && !EQ (XCAR (prop), Qspace_width)
-      && !EQ (XCAR (prop), Qheight)
-      && !EQ (XCAR (prop), Qraise)
+  display_replaced_p = handle_display_spec (it, propval, object, overlay,
+                                            position, bufpos,
+                                            FRAME_WINDOW_P (it->f));
+
+  return display_replaced_p ? HANDLED_RETURN : HANDLED_NORMALLY;
+}
+
+/* Subroutine of handle_display_prop.  Returns non-zero if the display
+   specification in SPEC is a replacing specification, i.e. it would
+   replace the text covered by `display' property with something else,
+   such as an image or a display string.
+
+   See handle_single_display_spec for documentation of arguments.
+   frame_window_p is non-zero if the window being redisplayed is on a
+   GUI frame; this argument is used only if IT is NULL, see below.
+
+   IT can be NULL, if this is called by the bidi reordering code
+   through compute_display_string_pos, which see.  In that case, this
+   function only examines SPEC, but does not otherwise "handle" it, in
+   the sense that it doesn't set up members of IT from the display
+   spec.  */
+static int
+handle_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
+                     Lisp_Object overlay, struct text_pos *position,
+                     EMACS_INT bufpos, int frame_window_p)
+{
+  int replacing_p = 0;
+
+  if (CONSP (spec)
+      /* Simple specerties.  */
+      && !EQ (XCAR (spec), Qimage)
+      && !EQ (XCAR (spec), Qspace)
+      && !EQ (XCAR (spec), Qwhen)
+      && !EQ (XCAR (spec), Qslice)
+      && !EQ (XCAR (spec), Qspace_width)
+      && !EQ (XCAR (spec), Qheight)
+      && !EQ (XCAR (spec), Qraise)
       /* Marginal area specifications.  */
-      && !(CONSP (XCAR (prop)) && EQ (XCAR (XCAR (prop)), Qmargin))
-      && !EQ (XCAR (prop), Qleft_fringe)
-      && !EQ (XCAR (prop), Qright_fringe)
-      && !NILP (XCAR (prop)))
+      && !(CONSP (XCAR (spec)) && EQ (XCAR (XCAR (spec)), Qmargin))
+      && !EQ (XCAR (spec), Qleft_fringe)
+      && !EQ (XCAR (spec), Qright_fringe)
+      && !NILP (XCAR (spec)))
     {
-      for (; CONSP (prop); prop = XCDR (prop))
+      for (; CONSP (spec); spec = XCDR (spec))
         {
-          if (handle_single_display_spec (it, XCAR (prop), object, overlay,
-                                          position, display_replaced_p))
+          if (handle_single_display_spec (it, XCAR (spec), object, overlay,
+                                          position, bufpos, replacing_p,
+                                          frame_window_p))
             {
-              display_replaced_p = 1;
+              replacing_p = 1;
               /* If some text in a string is replaced, `position' no
                  longer points to the position of `object'.  */
-              if (STRINGP (object))
+              if (!it || STRINGP (object))
                 break;
             }
         }
     }
-  else if (VECTORP (prop))
+  else if (VECTORP (spec))
     {
       int i;
-      for (i = 0; i < ASIZE (prop); ++i)
-        if (handle_single_display_spec (it, AREF (prop, i), object, overlay,
-                                        position, display_replaced_p))
+      for (i = 0; i < ASIZE (spec); ++i)
+        if (handle_single_display_spec (it, AREF (spec, i), object, overlay,
+                                        position, bufpos, replacing_p,
+                                        frame_window_p))
           {
-            display_replaced_p = 1;
+            replacing_p = 1;
             /* If some text in a string is replaced, `position' no
                longer points to the position of `object'.  */
-            if (STRINGP (object))
+            if (!it || STRINGP (object))
               break;
           }
     }
   else
     {
-      if (handle_single_display_spec (it, prop, object, overlay,
-                                      position, 0))
-        display_replaced_p = 1;
+      if (handle_single_display_spec (it, spec, object, overlay,
+                                      position, bufpos, 0, frame_window_p))
+        replacing_p = 1;
     }
 
-  return display_replaced_p ? HANDLED_RETURN : HANDLED_NORMALLY;
+  return replacing_p;
 }
 
-
 /* Value is the position of the end of the `display' property starting
    at START_POS in OBJECT.  */
 
@@ -3857,10 +3967,12 @@ display_prop_end (struct it *it, Lisp_Object object, struct text_pos start_pos)
 
 /* Set up IT from a single `display' property specification SPEC.  OBJECT
    is the object in which the `display' property was found.  *POSITION
-   is the position at which it was found.  DISPLAY_REPLACED_P non-zero
-   means that we previously saw a display specification which already
-   replaced text display with something else, for example an image;
-   we ignore such properties after the first one has been processed.
+   is the position in OBJECT at which the `display' property was found.
+   BUFPOS is the buffer position of OBJECT (different from POSITION if
+   OBJECT is not a buffer).  DISPLAY_REPLACED_P non-zero means that we
+   previously saw a display specification which already replaced text
+   display with something else, for example an image; we ignore such
+   properties after the first one has been processed.
 
    OVERLAY is the overlay this `display' property came from,
    or nil if it was a text property.
@@ -3869,17 +3981,22 @@ display_prop_end (struct it *it, Lisp_Object object, struct text_pos start_pos)
    cases too, set *POSITION to the position where the `display'
    property ends.
 
+   If IT is NULL, only examine the property specification in SPEC, but
+   don't set up IT.  In that case, FRAME_WINDOW_P non-zero means SPEC
+   is intended to be displayed in a window on a GUI frame.
+
    Value is non-zero if something was found which replaces the display
    of buffer or string text.  */
 
 static int
 handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
                             Lisp_Object overlay, struct text_pos *position,
-                            int display_replaced_p)
+                            EMACS_INT bufpos, int display_replaced_p,
+                            int frame_window_p)
 {
   Lisp_Object form;
   Lisp_Object location, value;
-  struct text_pos start_pos, save_pos;
+  struct text_pos start_pos = *position;
   int valid_p;
 
   /* If SPEC is a list of the form `(when FORM . VALUE)', evaluate FORM.
@@ -3903,11 +4020,12 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
          buffer or string.  Bind `position' to the position in the
          object where the property was found, and `buffer-position'
          to the current position in the buffer.  */
+
+      if (NILP (object))
+        XSETBUFFER (object, current_buffer);
       specbind (Qobject, object);
       specbind (Qposition, make_number (CHARPOS (*position)));
-      specbind (Qbuffer_position,
-                make_number (STRINGP (object)
-                             ? IT_CHARPOS (*it) : CHARPOS (*position)));
+      specbind (Qbuffer_position, make_number (bufpos));
       GCPRO1 (form);
       form = safe_eval (form);
       UNGCPRO;
@@ -3922,63 +4040,66 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
       && EQ (XCAR (spec), Qheight)
       && CONSP (XCDR (spec)))
     {
-      if (!FRAME_WINDOW_P (it->f))
-        return 0;
-
-      it->font_height = XCAR (XCDR (spec));
-      if (!NILP (it->font_height))
+      if (it)
         {
-          struct face *face = FACE_FROM_ID (it->f, it->face_id);
-          int new_height = -1;
+          if (!FRAME_WINDOW_P (it->f))
+            return 0;
 
-          if (CONSP (it->font_height)
-              && (EQ (XCAR (it->font_height), Qplus)
-                  || EQ (XCAR (it->font_height), Qminus))
-              && CONSP (XCDR (it->font_height))
-              && INTEGERP (XCAR (XCDR (it->font_height))))
+          it->font_height = XCAR (XCDR (spec));
+          if (!NILP (it->font_height))
             {
-              /* `(+ N)' or `(- N)' where N is an integer.  */
-              int steps = XINT (XCAR (XCDR (it->font_height)));
-              if (EQ (XCAR (it->font_height), Qplus))
-                steps = - steps;
-              it->face_id = smaller_face (it->f, it->face_id, steps);
-            }
-          else if (FUNCTIONP (it->font_height))
-            {
-              /* Call function with current height as argument.
-                 Value is the new height.  */
-              Lisp_Object height;
-              height = safe_call1 (it->font_height,
-                                   face->lface[LFACE_HEIGHT_INDEX]);
-              if (NUMBERP (height))
-                new_height = XFLOATINT (height);
-            }
-          else if (NUMBERP (it->font_height))
-            {
-              /* Value is a multiple of the canonical char height.  */
-              struct face *f;
+              struct face *face = FACE_FROM_ID (it->f, it->face_id);
+              int new_height = -1;
+
+              if (CONSP (it->font_height)
+                  && (EQ (XCAR (it->font_height), Qplus)
+                      || EQ (XCAR (it->font_height), Qminus))
+                  && CONSP (XCDR (it->font_height))
+                  && INTEGERP (XCAR (XCDR (it->font_height))))
+                {
+                  /* `(+ N)' or `(- N)' where N is an integer.  */
+                  int steps = XINT (XCAR (XCDR (it->font_height)));
+                  if (EQ (XCAR (it->font_height), Qplus))
+                    steps = - steps;
+                  it->face_id = smaller_face (it->f, it->face_id, steps);
+                }
+              else if (FUNCTIONP (it->font_height))
+                {
+                  /* Call function with current height as argument.
+                     Value is the new height.  */
+                  Lisp_Object height;
+                  height = safe_call1 (it->font_height,
+                                       face->lface[LFACE_HEIGHT_INDEX]);
+                  if (NUMBERP (height))
+                    new_height = XFLOATINT (height);
+                }
+              else if (NUMBERP (it->font_height))
+                {
+                  /* Value is a multiple of the canonical char height.  */
+                  struct face *f;
 
-              f = FACE_FROM_ID (it->f,
-                                lookup_basic_face (it->f, DEFAULT_FACE_ID));
-              new_height = (XFLOATINT (it->font_height)
-                            * XINT (f->lface[LFACE_HEIGHT_INDEX]));
-            }
-          else
-            {
-              /* Evaluate IT->font_height with `height' bound to the
-                 current specified height to get the new height.  */
-              int count = SPECPDL_INDEX ();
+                  f = FACE_FROM_ID (it->f,
+                                    lookup_basic_face (it->f, DEFAULT_FACE_ID));
+                  new_height = (XFLOATINT (it->font_height)
+                                * XINT (f->lface[LFACE_HEIGHT_INDEX]));
+                }
+              else
+                {
+                  /* Evaluate IT->font_height with `height' bound to the
+                     current specified height to get the new height.  */
+                  int count = SPECPDL_INDEX ();
 
-              specbind (Qheight, face->lface[LFACE_HEIGHT_INDEX]);
-              value = safe_eval (it->font_height);
-              unbind_to (count, Qnil);
+                  specbind (Qheight, face->lface[LFACE_HEIGHT_INDEX]);
+                  value = safe_eval (it->font_height);
+                  unbind_to (count, Qnil);
 
-              if (NUMBERP (value))
-                new_height = XFLOATINT (value);
-            }
+                  if (NUMBERP (value))
+                    new_height = XFLOATINT (value);
+                }
 
-          if (new_height > 0)
-            it->face_id = face_with_height (it->f, it->face_id, new_height);
+              if (new_height > 0)
+                it->face_id = face_with_height (it->f, it->face_id, new_height);
+            }
         }
 
       return 0;
@@ -3989,12 +4110,15 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
       && EQ (XCAR (spec), Qspace_width)
       && CONSP (XCDR (spec)))
     {
-      if (!FRAME_WINDOW_P (it->f))
-        return 0;
+      if (it)
+        {
+          if (!FRAME_WINDOW_P (it->f))
+            return 0;
 
-      value = XCAR (XCDR (spec));
-      if (NUMBERP (value) && XFLOATINT (value) > 0)
-        it->space_width = value;
+          value = XCAR (XCDR (spec));
+          if (NUMBERP (value) && XFLOATINT (value) > 0)
+            it->space_width = value;
+        }
 
       return 0;
     }
@@ -4005,20 +4129,23 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
     {
       Lisp_Object tem;
 
-      if (!FRAME_WINDOW_P (it->f))
-        return 0;
-
-      if (tem = XCDR (spec), CONSP (tem))
+      if (it)
         {
-          it->slice.x = XCAR (tem);
-          if (tem = XCDR (tem), CONSP (tem))
+          if (!FRAME_WINDOW_P (it->f))
+            return 0;
+
+          if (tem = XCDR (spec), CONSP (tem))
             {
-              it->slice.y = XCAR (tem);
+              it->slice.x = XCAR (tem);
               if (tem = XCDR (tem), CONSP (tem))
                 {
-                  it->slice.width = XCAR (tem);
+                  it->slice.y = XCAR (tem);
                   if (tem = XCDR (tem), CONSP (tem))
-                    it->slice.height = XCAR (tem);
+                    {
+                      it->slice.width = XCAR (tem);
+                      if (tem = XCDR (tem), CONSP (tem))
+                        it->slice.height = XCAR (tem);
+                    }
                 }
             }
         }
@@ -4031,36 +4158,43 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
       && EQ (XCAR (spec), Qraise)
       && CONSP (XCDR (spec)))
     {
-      if (!FRAME_WINDOW_P (it->f))
-        return 0;
+      if (it)
+        {
+          if (!FRAME_WINDOW_P (it->f))
+            return 0;
 
 #ifdef HAVE_WINDOW_SYSTEM
-      value = XCAR (XCDR (spec));
-      if (NUMBERP (value))
-        {
-          struct face *face = FACE_FROM_ID (it->f, it->face_id);
-          it->voffset = - (XFLOATINT (value)
-                           * (FONT_HEIGHT (face->font)));
-        }
+          value = XCAR (XCDR (spec));
+          if (NUMBERP (value))
+            {
+              struct face *face = FACE_FROM_ID (it->f, it->face_id);
+              it->voffset = - (XFLOATINT (value)
+                               * (FONT_HEIGHT (face->font)));
+            }
 #endif /* HAVE_WINDOW_SYSTEM */
+        }
 
       return 0;
     }
 
   /* Don't handle the other kinds of display specifications
      inside a string that we got from a `display' property.  */
-  if (it->string_from_display_prop_p)
+  if (it && it->string_from_display_prop_p)
     return 0;
 
   /* Characters having this form of property are not displayed, so
      we have to find the end of the property.  */
-  start_pos = *position;
-  *position = display_prop_end (it, object, start_pos);
+  if (it)
+    {
+      start_pos = *position;
+      *position = display_prop_end (it, object, start_pos);
+    }
   value = Qnil;
 
   /* Stop the scan at that end position--we assume that all
      text properties change there.  */
-  it->stop_charpos = position->charpos;
+  if (it)
+    it->stop_charpos = position->charpos;
 
   /* Handle `(left-fringe BITMAP [FACE])'
      and `(right-fringe BITMAP [FACE])'.  */
@@ -4069,12 +4203,16 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
           || EQ (XCAR (spec), Qright_fringe))
       && CONSP (XCDR (spec)))
     {
-      int face_id = lookup_basic_face (it->f, DEFAULT_FACE_ID);
       int fringe_bitmap;
 
-      if (!FRAME_WINDOW_P (it->f))
-        /* If we return here, POSITION has been advanced
-           across the text with this property.  */
+      if (it)
+        {
+          if (!FRAME_WINDOW_P (it->f))
+            /* If we return here, POSITION has been advanced
+               across the text with this property.  */
+            return 0;
+        }
+      else if (!frame_window_p)
         return 0;
 
 #ifdef HAVE_WINDOW_SYSTEM
@@ -4085,46 +4223,47 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
            across the text with this property.  */
         return 0;
 
-      if (CONSP (XCDR (XCDR (spec))))
+      if (it)
         {
-          Lisp_Object face_name = XCAR (XCDR (XCDR (spec)));
-          int face_id2 = lookup_derived_face (it->f, face_name,
-                                              FRINGE_FACE_ID, 0);
-          if (face_id2 >= 0)
-            face_id = face_id2;
-        }
+          int face_id = lookup_basic_face (it->f, DEFAULT_FACE_ID);;
 
-      /* Save current settings of IT so that we can restore them
-         when we are finished with the glyph property value.  */
+          if (CONSP (XCDR (XCDR (spec))))
+            {
+              Lisp_Object face_name = XCAR (XCDR (XCDR (spec)));
+              int face_id2 = lookup_derived_face (it->f, face_name,
+                                                  FRINGE_FACE_ID, 0);
+              if (face_id2 >= 0)
+                face_id = face_id2;
+            }
 
-      save_pos = it->position;
-      it->position = *position;
-      push_it (it);
-      it->position = save_pos;
+          /* Save current settings of IT so that we can restore them
+             when we are finished with the glyph property value.  */
+          push_it (it, position);
 
-      it->area = TEXT_AREA;
-      it->what = IT_IMAGE;
-      it->image_id = -1; /* no image */
-      it->position = start_pos;
-      it->object = NILP (object) ? it->w->buffer : object;
-      it->method = GET_FROM_IMAGE;
-      it->from_overlay = Qnil;
-      it->face_id = face_id;
+          it->area = TEXT_AREA;
+          it->what = IT_IMAGE;
+          it->image_id = -1; /* no image */
+          it->position = start_pos;
+          it->object = NILP (object) ? it->w->buffer : object;
+          it->method = GET_FROM_IMAGE;
+          it->from_overlay = Qnil;
+          it->face_id = face_id;
 
-      /* Say that we haven't consumed the characters with
-         `display' property yet.  The call to pop_it in
-         set_iterator_to_next will clean this up.  */
-      *position = start_pos;
+          /* Say that we haven't consumed the characters with
+             `display' property yet.  The call to pop_it in
+             set_iterator_to_next will clean this up.  */
+          *position = start_pos;
 
-      if (EQ (XCAR (spec), Qleft_fringe))
-        {
-          it->left_user_fringe_bitmap = fringe_bitmap;
-          it->left_user_fringe_face_id = face_id;
-        }
-      else
-        {
-          it->right_user_fringe_bitmap = fringe_bitmap;
-          it->right_user_fringe_face_id = face_id;
+          if (EQ (XCAR (spec), Qleft_fringe))
+            {
+              it->left_user_fringe_bitmap = fringe_bitmap;
+              it->left_user_fringe_face_id = face_id;
+            }
+          else
+            {
+              it->right_user_fringe_bitmap = fringe_bitmap;
+              it->right_user_fringe_face_id = face_id;
+            }
         }
 #endif /* HAVE_WINDOW_SYSTEM */
       return 1;
@@ -4167,18 +4306,19 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
 
   valid_p = (STRINGP (value)
 #ifdef HAVE_WINDOW_SYSTEM
-             || (FRAME_WINDOW_P (it->f) && valid_image_p (value))
+             || ((it ? FRAME_WINDOW_P (it->f) : frame_window_p)
+                 && valid_image_p (value))
 #endif /* not HAVE_WINDOW_SYSTEM */
              || (CONSP (value) && EQ (XCAR (value), Qspace)));
 
   if (valid_p && !display_replaced_p)
     {
+      if (!it)
+        return 1;
+
       /* Save current settings of IT so that we can restore them
          when we are finished with the glyph property value.  */
-      save_pos = it->position;
-      it->position = *position;
-      push_it (it);
-      it->position = save_pos;
+      push_it (it, position);
       it->from_overlay = overlay;
 
       if (NILP (location))
@@ -4235,83 +4375,31 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
   return 0;
 }
 
-
-/* Check if SPEC is a display sub-property value whose text should be
-   treated as intangible.  */
-
-static int
-single_display_spec_intangible_p (Lisp_Object prop)
-{
-  /* Skip over `when FORM'.  */
-  if (CONSP (prop) && EQ (XCAR (prop), Qwhen))
-    {
-      prop = XCDR (prop);
-      if (!CONSP (prop))
-        return 0;
-      prop = XCDR (prop);
-    }
-
-  if (STRINGP (prop))
-    return 1;
-
-  if (!CONSP (prop))
-    return 0;
-
-  /* Skip over `margin LOCATION'.  If LOCATION is in the margins,
-     we don't need to treat text as intangible.  */
-  if (EQ (XCAR (prop), Qmargin))
-    {
-      prop = XCDR (prop);
-      if (!CONSP (prop))
-        return 0;
-
-      prop = XCDR (prop);
-      if (!CONSP (prop)
-          || EQ (XCAR (prop), Qleft_margin)
-          || EQ (XCAR (prop), Qright_margin))
-        return 0;
-    }
-
-  return (CONSP (prop)
-          && (EQ (XCAR (prop), Qimage)
-              || EQ (XCAR (prop), Qspace)));
-}
-
-
 /* Check if PROP is a display property value whose text should be
-   treated as intangible.  */
+   treated as intangible.  OVERLAY is the overlay from which PROP
+   came, or nil if it came from a text property.  CHARPOS and BYTEPOS
+   specify the buffer position covered by PROP.  */
 
 int
-display_prop_intangible_p (Lisp_Object prop)
+display_prop_intangible_p (Lisp_Object prop, Lisp_Object overlay,
+                           EMACS_INT charpos, EMACS_INT bytepos)
 {
-  if (CONSP (prop)
-      && CONSP (XCAR (prop))
-      && !EQ (Qmargin, XCAR (XCAR (prop))))
-    {
-      /* A list of sub-properties.  */
-      while (CONSP (prop))
-        {
-          if (single_display_spec_intangible_p (XCAR (prop)))
-            return 1;
-          prop = XCDR (prop);
-        }
-    }
-  else if (VECTORP (prop))
-    {
-      /* A vector of sub-properties.  */
-      int i;
-      for (i = 0; i < ASIZE (prop); ++i)
-        if (single_display_spec_intangible_p (AREF (prop, i)))
-          return 1;
-    }
-  else
-    return single_display_spec_intangible_p (prop);
+  int frame_window_p = FRAME_WINDOW_P (XFRAME (selected_frame));
+  struct text_pos position;
 
-  return 0;
+  SET_TEXT_POS (position, charpos, bytepos);
+  return handle_display_spec (NULL, prop, Qnil, overlay,
+                              &position, charpos, frame_window_p);
 }
 
 
-/* Return 1 if PROP is a display sub-property value containing STRING.  */
+/* Return 1 if PROP is a display sub-property value containing STRING.
+
+   Implementation note: this and the following function are really
+   special cases of handle_display_spec and
+   handle_single_display_spec, and should ideally use the same code.
+   Until they do, these two pairs must be consistent and must be
+   modified in sync.  */
 
 static int
 single_display_spec_string_p (Lisp_Object prop, Lisp_Object string)
@@ -4325,6 +4413,16 @@ single_display_spec_string_p (Lisp_Object prop, Lisp_Object string)
       prop = XCDR (prop);
       if (!CONSP (prop))
         return 0;
+      /* Actually, the condition following `when' should be eval'ed,
+         like handle_single_display_spec does, and we should return
+         zero if it evaluates to nil.  However, this function is
+         called only when the buffer was already displayed and some
+         glyph in the glyph matrix was found to come from a display
+         string.  Therefore, the condition was already evaluated, and
+         the result was non-nil, otherwise the display string wouldn't
+         have been displayed and we would have never been called for
+         this property.  Thus, we can skip the evaluation and assume
+         its result is non-nil.  */
       prop = XCDR (prop);
     }
 
@@ -4341,7 +4439,7 @@ single_display_spec_string_p (Lisp_Object prop, Lisp_Object string)
           return 0;
       }
 
-  return CONSP (prop) && EQ (XCAR (prop), string);
+  return EQ (prop, string) || (CONSP (prop) && EQ (XCAR (prop), string));
 }
 
 
@@ -4351,8 +4449,8 @@ static int
 display_prop_string_p (Lisp_Object prop, Lisp_Object string)
 {
   if (CONSP (prop)
-      && CONSP (XCAR (prop))
-      && !EQ (Qmargin, XCAR (XCAR (prop))))
+      && !EQ (XCAR (prop), Qwhen)
+      && !(CONSP (XCAR (prop)) && EQ (Qmargin, XCAR (XCAR (prop)))))
     {
       /* A list of sub-properties.  */
       while (CONSP (prop))
@@ -4852,7 +4950,7 @@ get_overlay_strings_1 (struct it *it, EMACS_INT charpos, int compute_stop_p)
       /* When called from handle_stop, there might be an empty display
          string loaded.  In that case, don't bother saving it.  */
       if (!STRINGP (it->string) || SCHARS (it->string))
-        push_it (it);
+        push_it (it, NULL);
 
       /* Set up IT to deliver display elements from the first overlay
          string.  */
@@ -4894,10 +4992,11 @@ get_overlay_strings (struct it *it, EMACS_INT charpos)
 /* Save current settings of IT on IT->stack.  Called, for example,
    before setting up IT for an overlay string, to be able to restore
    IT's settings to what they were after the overlay string has been
-   processed.  */
+   processed.  If POSITION is non-NULL, it is the position to save on
+   the stack instead of IT->position.  */
 
 static void
-push_it (struct it *it)
+push_it (struct it *it, struct text_pos *position)
 {
   struct iterator_stack_entry *p;
 
@@ -4924,7 +5023,7 @@ push_it (struct it *it)
       p->u.stretch.object = it->object;
       break;
     }
-  p->position = it->position;
+  p->position = position ? *position : it->position;
   p->current = it->current;
   p->end_charpos = it->end_charpos;
   p->string_nchars = it->string_nchars;
@@ -5382,6 +5481,7 @@ reseat_1 (struct it *it, struct text_pos pos, int set_stop_p)
     {
       it->bidi_it.first_elt = 1;
       it->bidi_it.paragraph_dir = NEUTRAL_DIR;
+      it->bidi_it.disp_pos = -1;
     }
 
   if (set_stop_p)
@@ -12688,11 +12788,30 @@ set_cursor_from_row (struct window *w, struct glyph_row *row,
              GLYPH_BEFORE and GLYPH_AFTER, and it came from a string
              positioned between POS_BEFORE and POS_AFTER in the
              buffer.  */
-          struct glyph *stop = glyph_after;
+          struct glyph *start, *stop;
           EMACS_INT pos = pos_before;
 
           x = -1;
-          for (glyph = glyph_before + incr;
+
+          /* GLYPH_BEFORE and GLYPH_AFTER are the glyphs that
+             correspond to POS_BEFORE and POS_AFTER, respectively.  We
+             need START and STOP in the order that corresponds to the
+             row's direction as given by its reversed_p flag.  If the
+             directionality of characters between POS_BEFORE and
+             POS_AFTER is the opposite of the row's base direction,
+             these characters will have been reordered for display,
+             and we need to reverse START and STOP.  */
+          if (!row->reversed_p)
+            {
+              start = min (glyph_before, glyph_after);
+              stop = max (glyph_before, glyph_after);
+            }
+          else
+            {
+              start = max (glyph_before, glyph_after);
+              stop = min (glyph_before, glyph_after);
+            }
+          for (glyph = start + incr;
                row->reversed_p ? glyph > stop : glyph < stop; )
             {
 
@@ -17111,7 +17230,7 @@ cursor_row_p (struct glyph_row *row)
 static int
 push_display_prop (struct it *it, Lisp_Object prop)
 {
-  push_it (it);
+  push_it (it, NULL);
 
   if (STRINGP (prop))
     {
@@ -18040,6 +18159,8 @@ See also `bidi-paragraph-direction'.  */)
         bytepos--;
       itb.charpos = pos;
       itb.bytepos = bytepos;
+      itb.nchars = -1;
+      itb.frame_window_p = FRAME_WINDOW_P (SELECTED_FRAME ()); /* guesswork */
       itb.first_elt = 1;
       itb.separator_limit = -1;
       itb.paragraph_dir = NEUTRAL_DIR;