Merge from trunk.

10 files changed, 2004 insertions, 608 deletions

diff --git a/src/.gdbinit b/src/.gdbinit
index 2cf5663df91..0f51a00ea76 100644
--- a/src/.gdbinit
+++ b/src/.gdbinit
@@ -677,7 +677,7 @@ end
 
 define xvectype
   xgetptr $
-  set $size = ((struct Lisp_Vector *) $ptr)->size
+  set $size = ((struct Lisp_Vector *) $ptr)->header.size
   output ($size & PVEC_FLAG) ? (enum pvec_type) ($size & PVEC_TYPE_MASK) : $size & ~gdb_array_mark_flag
   echo \n
 end
@@ -818,7 +818,7 @@ end
 define xvector
   xgetptr $
   print (struct Lisp_Vector *) $ptr
-  output ($->size > 50) ? 0 : ($->contents[0])@($->size & ~gdb_array_mark_flag)
+  output ($->header.size > 50) ? 0 : ($->contents[0])@($->header.size & ~gdb_array_mark_flag)
 echo \n
 end
 document xvector
@@ -853,7 +853,7 @@ end
 define xcompiled
   xgetptr $
   print (struct Lisp_Vector *) $ptr
-  output ($->contents[0])@($->size & 0xff)
+  output ($->contents[0])@($->header.size & 0xff)
 end
 document xcompiled
 Print $ as a compiled function pointer.
@@ -903,7 +903,7 @@ define xchartable
   print (struct Lisp_Char_Table *) $ptr
   printf "Purpose: "
   xprintsym $->purpose
-  printf "  %d extra slots", ($->size & 0x1ff) - 68
+  printf "  %d extra slots", ($->header.size & 0x1ff) - 68
   echo \n
 end
 document xchartable
@@ -927,7 +927,7 @@ end
 define xboolvector
   xgetptr $
   print (struct Lisp_Bool_Vector *) $ptr
-  output ($->size > 256) ? 0 : ($->data[0])@((($->size & ~gdb_array_mark_flag) + 7)/ 8)
+  output ($->header.size > 256) ? 0 : ($->data[0])@((($->header.size & ~gdb_array_mark_flag) + 7)/ 8)
   echo \n
 end
 document xboolvector
@@ -1093,7 +1093,7 @@ define xpr
 #    end
   end
   if $type == Lisp_Vectorlike
-    set $size = ((struct Lisp_Vector *) $ptr)->size
+    set $size = ((struct Lisp_Vector *) $ptr)->header.size
     if ($size & PVEC_FLAG)
       set $vec = (enum pvec_type) ($size & PVEC_TYPE_MASK)
       if $vec == PVEC_NORMAL_VECTOR
@@ -1202,7 +1202,7 @@ end
 
 define xfont
   xgetptr $
-  set $size = (((struct Lisp_Vector *) $ptr)->size & 0x1FF)
+  set $size = (((struct Lisp_Vector *) $ptr)->header.size & 0x1FF)
   if $size == FONT_SPEC_MAX
     print (struct font_spec *) $ptr
   else
@@ -1229,7 +1229,7 @@ define xbacktrace
       printf "0x%x ", $ptr
       if $type == Lisp_Vectorlike
         xgetptr (*$bt->function)
-        set $size = ((struct Lisp_Vector *) $ptr)->size
+        set $size = ((struct Lisp_Vector *) $ptr)->header.size
         output ($size & PVEC_FLAG) ? (enum pvec_type) ($size & PVEC_TYPE_MASK) : $size & ~gdb_array_mark_flag
       else
         printf "Lisp type %d", $type
diff --git a/src/ChangeLog b/src/ChangeLog
index 0977b12ab38..ce080f6b239 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -182,6 +182,226 @@
 
 2011-07-14  Lars Magne Ingebrigtsen  <larsi@gnus.org>
 
+        * data.c (Fcdr, Fcar): Revert the last change, since it didn't
+        really clarify much.
+
+        * search.c (Fre_search_backward): Mention `case-fold-search' in
+        all the re_search_* functions (bug#8138).
+
+        * keyboard.c (Fopen_dribble_file): Document when the file is
+        closed (bug#8056).
+
+2011-07-14  Eli Zaretskii  <eliz@gnu.org>
+
+        * bidi.c (bidi_dump_cached_states): Fix format of displaying
+        bidi_cache_idx.
+
+        Support bidi reordering of display and overlay strings.
+        * xdisp.c (compute_display_string_pos)
+        (compute_display_string_end): Accept additional argument STRING.
+        (init_iterator, reseat_1): Initialize bidi_it->string.s to NULL.
+        (reseat_to_string): Initialize bidi_it->string.s and
+        bidi_it->string.schars.
+        (Fcurrent_bidi_paragraph_direction): Initialize itb.string.s to
+        NULL (avoids a crash in bidi_paragraph_init).  Initialize
+        itb.string.lstring.
+        (init_iterator): Call bidi_init_it only of a valid
+        buffer position was specified.  Initialize paragraph_embedding to
+        L2R.
+        (reseat_to_string): Initialize the bidi iterator.
+        (display_string): If we need to ignore text properties of
+        LISP_STRING, set IT->stop_charpos to IT->end_charpos.  (The
+        original value of -1 will not work with bidi.)
+        (compute_display_string_pos): First arg is now struct
+        `text_pos *'; all callers changed.  Support display properties on
+        Lisp strings.
+        (compute_display_string_end): Support display properties on Lisp
+        strings.
+        (init_iterator, reseat_1, reseat_to_string): Initialize the
+        string.bufpos member to 0 (zero, for compatibility with IT_CHARPOS
+        when iterating on a string not from display properties).
+        (compute_display_string_pos, compute_display_string_end): Fix
+        calculation of the object to scan.  Fixes an error when using
+        arrow keys.
+        (next_element_from_buffer): Don't abort when IT_CHARPOS is before
+        base_level_stop; instead, set base_level_stop to BEGV.  Fixes
+        crashes in vertical-motion.
+        (next_element_from_buffer): Improve commentary for when
+        the iterator is before prev_stop.
+        (init_iterator): Initialize bidi_p from the default value of
+        bidi-display-reordering, not from buffer-local value.  Use the
+        buffer-local value only if initializing for buffer iteration.
+        (handle_invisible_prop): Support invisible properties on strings
+        that are being bidi-reordered.
+        (set_iterator_to_next): Support bidi reordering of C strings and
+        Lisp strings.
+        (next_element_from_string): Support bidi reordering of Lisp
+        strings.
+        (handle_stop_backwards): Support Lisp strings as well.
+        (display_string): Support display of R2L glyph rows.  Use
+        IT_STRING_CHARPOS when displaying from a Lisp string.
+        (init_iterator): Don't initialize it->bidi_p for strings
+        here.
+        (reseat_to_string): Initialize it->bidi_p for strings here.
+        (next_element_from_string, next_element_from_c_string)
+        (next_element_from_buffer): Add xassert's for correspondence
+        between IT's object being iterated and it->bidi_it.string
+        structure.
+        (face_before_or_after_it_pos): Support bidi iteration.
+        (next_element_from_c_string): Handle the case of the first string
+        character that is not the first one in the visual order.
+        (get_visually_first_element): New function, refactored from common
+        parts of next_element_from_buffer, next_element_from_string, and
+        next_element_from_c_string.
+        (tool_bar_lines_needed, redisplay_tool_bar)
+        (display_menu_bar): Force left-to-right direction.  Add a FIXME
+        comment for making that be controlled by a user option.
+        (push_it, pop_it): Save and restore the state of the
+        bidi iterator.  Save and restore the bidi_p flag.
+        (pop_it): Iterate out of display property for string iteration as
+        well.
+        (iterate_out_of_display_property): Support iteration over strings.
+        (handle_single_display_spec): Set up it->bidi_it for iteration
+        over a display string, and call bidi_init_it.
+        (handle_single_display_spec, next_overlay_string)
+        (get_overlay_strings_1, push_display_prop): Set up the bidi
+        iterator for displaying display or overlay strings.
+        (forward_to_next_line_start): Don't use the shortcut if
+        bidi-iterating.
+        (back_to_previous_visible_line_start): If handle_display_prop
+        pushed the iterator stack, restore the internal state of the bidi
+        iterator by calling bidi_pop_it same number of times.
+        (reseat_at_next_visible_line_start): If ON_NEWLINE_P is non-zero,
+        and we are bidi-iterating, don't decrement the iterator position;
+        instead, set the first_elt flag in the bidi iterator, to produce
+        the same effect.
+        (reseat_1): Remove redundant setting of string_from_display_prop_p.
+        (push_display_prop): xassert that we are iterating a buffer.
+        (push_it, pop_it): Save and restore paragraph_embedding member.
+        (handle_single_display_spec, next_overlay_string)
+        (get_overlay_strings_1, reseat_1, reseat_to_string)
+        (push_display_prop): Set up the `unibyte' member of bidi_it.string
+        correctly.  Don't assume unibyte strings are not bidi-reordered.
+        (compute_display_string_pos)
+        (compute_display_string_end): Fix handling the case of C string.
+        (push_it, pop_it): Save and restore from_disp_prop_p.
+        (handle_single_display_spec, push_display_prop): Set the
+        from_disp_prop_p flag.
+        (get_overlay_strings_1): Reset the from_disp_prop_p flag.
+        (pop_it): Call iterate_out_of_display_property only if we are
+        popping after iteration over a string that came from a display
+        property.  Fix a typo in popping stretch info.  Add an assertion
+        for verifying that the iterator position is in sync with the bidi
+        iterator.
+        (handle_single_display_spec, get_overlay_strings_1)
+        (push_display_prop): Fix initialization of paragraph direction for
+        string when that of the parent object is not yet determined.
+        (reseat_1): Call bidi_init_it to resync the bidi
+        iterator with IT's position.  (Bug#7616)
+        (find_row_edges): If ROW->start.pos gives position
+        smaller than min_pos, use it as ROW->minpos.  (Bug#7616)
+        (handle_stop, back_to_previous_visible_line_start, reseat_1):
+        Reset the from_disp_prop_p flag.
+        (SAVE_IT, RESTORE_IT): New macros.
+        (pos_visible_p, face_before_or_after_it_pos)
+        (back_to_previous_visible_line_start)
+        (move_it_in_display_line_to, move_it_in_display_line)
+        (move_it_to, move_it_vertically_backward, move_it_by_lines)
+        (try_scrolling, redisplay_window, display_line): Use them when
+        saving a temporary copy of the iterator and restoring it back.
+        (back_to_previous_visible_line_start, reseat_1)
+        (init_iterator): Empty the bidi cache "stack".
+        (move_it_in_display_line_to): If iterator ended up at
+        EOL, but we never saw any buffer positions smaller than
+        to_charpos, return MOVE_POS_MATCH_OR_ZV.  Fixes vertical cursor
+        motion in bidi-reordered lines.
+        (move_it_in_display_line_to): Record prev_method and prev_pos
+        immediately before the call to set_iterator_to_next.  Fixes cursor
+        motion in bidi-reordered lines with stretch glyphs and strings
+        displayed in margins.  (Bug#8133) (Bug#8867)
+        Return MOVE_POS_MATCH_OR_ZV only if iterator position is past
+        TO_CHARPOS.
+        (pos_visible_p): Support positions in bidi-reordered lines.  Save
+        and restore bidi cache.
+
+        * bidi.c (bidi_level_of_next_char): clen should be EMACS_NT, not int.
+        (bidi_paragraph_info): Delete unused struct.
+        (bidi_cache_idx, bidi_cache_last_idx): Declare EMACS_INT.
+        (bidi_cache_start): New variable.
+        (bidi_cache_reset): Reset bidi_cache_idx to bidi_cache_start, not
+        to zero.
+        (bidi_cache_fetch_state, bidi_cache_search)
+        (bidi_cache_find_level_change, bidi_cache_iterator_state)
+        (bidi_cache_find, bidi_peek_at_next_level)
+        (bidi_level_of_next_char, bidi_find_other_level_edge)
+        (bidi_move_to_visually_next): Compare cache index with
+        bidi_cache_start rather than with zero.
+        (bidi_fetch_char): Accept new argument STRING; all callers
+        changed.  Support iteration over a string.  Support strings with
+        display properties.  Support unibyte strings.  Fix the type of
+        `len' according to what STRING_CHAR_AND_LENGTH expects.
+        (bidi_paragraph_init, bidi_resolve_explicit_1)
+        (bidi_resolve_explicit, bidi_resolve_weak)
+        (bidi_level_of_next_char, bidi_move_to_visually_next): Support
+        iteration over a string.
+        (bidi_set_sor_type, bidi_resolve_explicit_1)
+        (bidi_resolve_explicit, bidi_type_of_next_char): ignore_bn_limit
+        can now be zero (for strings); special values 0 and -1 were
+        changed to -1 and -2, respectively.
+        (bidi_char_at_pos): New function.
+        (bidi_paragraph_init, bidi_resolve_explicit, bidi_resolve_weak):
+        Call it instead of FETCH_MULTIBYTE_CHAR.
+        (bidi_move_to_visually_next): Abort if charpos or bytepos were not
+        initialized to valid values.
+        (bidi_init_it): Don't initialize charpos and bytepos with invalid
+        values.
+        (bidi_level_of_next_char): Allow the sentinel "position" to pass
+        the test for valid cached positions.  Fix the logic for looking up
+        the sentinel state in the cache.  GCPRO the Lisp string we are
+        iterating.
+        (bidi_push_it, bidi_pop_it): New functions.
+        (bidi_initialize): Initialize the bidi cache start stack pointer.
+        (bidi_cache_ensure_space): New function, refactored from part of
+        bidi_cache_iterator_state.  Don't assume the required size is just
+        one BIDI_CACHE_CHUNK away.
+        (bidi_cache_start_stack, bidi_push_it): Use IT_STACK_SIZE.
+        (bidi_count_bytes, bidi_char_at_pos): New functions.
+        (bidi_cache_search): Don't assume bidi_cache_last_idx is
+        always valid if bidi_cache_idx is valid.
+        (bidi_cache_find_level_change): xassert that bidi_cache_last_idx
+        is valid if it's going to be used.
+        (bidi_shelve_cache, bidi_unshelve_cache): New functions.
+        (bidi_cache_fetch_state, bidi_cache_search)
+        (bidi_cache_find_level_change, bidi_cache_ensure_space)
+        (bidi_cache_iterator_state, bidi_cache_find)
+        (bidi_find_other_level_edge, bidi_cache_start_stack): All
+        variables related to cache indices are now EMACS_INT.
+
+        * dispextern.h (struct bidi_string_data): New structure.
+        (struct bidi_it): New member `string'.  Make flag members be 1-bit
+        fields, and put them last in the struct.
+        (compute_display_string_pos, compute_display_string_end): Update
+        prototypes.
+        (bidi_push_it, bidi_pop_it): Add prototypes.
+        (struct iterator_stack_entry): New members bidi_p,
+        paragraph_embedding, and from_disp_prop_p.
+        (struct it): Member bidi_p is now a bit field 1 bit wide.
+        (bidi_shelve_cache, bidi_unshelve_cache): Declare
+        prototypes.
+
+        * .gdbinit (xvectype, xvector, xcompiled, xchartable, xboolvector)
+        (xpr, xfont, xbacktrace): Use "header.size" when accessing vectors
+        and vector-like objects.
+
+        * dispnew.c (buffer_posn_from_coords): Save and restore the bidi
+        cache around display iteration.
+
+        * window.c (Fwindow_end, window_scroll_pixel_based)
+        (displayed_window_lines, Frecenter): Save and restore the bidi
+        cache around display iteration.
+
+2011-07-14  Lars Magne Ingebrigtsen  <larsi@gnus.org>
+
         * editfns.c (Fdelete_region): Clarify the use of the named
         parameters (bug#6788).
 
diff --git a/src/bidi.c b/src/bidi.c
index 469afdb3819..22a5f0829cd 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -1,4 +1,4 @@
-/* Low-level bidirectional buffer-scanning functions for GNU Emacs.
+/* Low-level bidirectional buffer/string-scanning functions for GNU Emacs.
    Copyright (C) 2000-2001, 2004-2005, 2009-2011
    Free Software Foundation, Inc.
 
@@ -20,7 +20,7 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
 /* Written by Eli Zaretskii <eliz@gnu.org>.
 
    A sequential implementation of the Unicode Bidirectional algorithm,
-   as per UAX#9, a part of the Unicode Standard.
+   (UBA) as per UAX#9, a part of the Unicode Standard.
 
    Unlike the reference and most other implementations, this one is
    designed to be called once for every character in the buffer or
@@ -35,11 +35,16 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
    details about its algorithm that finds the next visual-order
    character by resolving their levels on the fly.
 
-   The two other entry points are bidi_paragraph_init and
+   Two other entry points are bidi_paragraph_init and
    bidi_mirror_char.  The first determines the base direction of a
    paragraph, while the second returns the mirrored version of its
    argument character.
 
+   A few auxiliary entry points are used to initialize the bidi
+   iterator for iterating an object (buffer or string), push and pop
+   the bidi iterator state, and save and restore the state of the bidi
+   cache.
+
    If you want to understand the code, you will have to read it
    together with the relevant portions of UAX#9.  The comments include
    references to UAX#9 rules, for that very reason.
@@ -66,16 +71,6 @@ static Lisp_Object bidi_type_table, bidi_mirror_table;
 #define RLM_CHAR   0x200F
 #define BIDI_EOB   -1
 
-/* Local data structures.  (Look in dispextern.h for the rest.)  */
-
-/* What we need to know about the current paragraph.  */
-struct bidi_paragraph_info {
-  EMACS_INT start_bytepos;      /* byte position where it begins */
-  EMACS_INT end_bytepos;        /* byte position where it ends */
-  int       embedding_level;    /* its basic embedding level */
-  bidi_dir_t base_dir;          /* its base direction */
-};
-
 /* Data type for describing the bidirectional character categories.  */
 typedef enum {
   UNKNOWN_BC,
@@ -90,43 +85,10 @@ int bidi_ignore_explicit_marks_for_paragraph_level = 1;
 static Lisp_Object paragraph_start_re, paragraph_separate_re;
 static Lisp_Object Qparagraph_start, Qparagraph_separate;
 
-static void
-bidi_initialize (void)
-{
-
-#include "biditype.h"
-#include "bidimirror.h"
-
-  int i;
-
-  bidi_type_table = Fmake_char_table (Qnil, make_number (STRONG_L));
-  staticpro (&bidi_type_table);
-
-  for (i = 0; i < sizeof bidi_type / sizeof bidi_type[0]; i++)
-    char_table_set_range (bidi_type_table, bidi_type[i].from, bidi_type[i].to,
-                          make_number (bidi_type[i].type));
-
-  bidi_mirror_table = Fmake_char_table (Qnil, Qnil);
-  staticpro (&bidi_mirror_table);
-
-  for (i = 0; i < sizeof bidi_mirror / sizeof bidi_mirror[0]; i++)
-    char_table_set (bidi_mirror_table, bidi_mirror[i].from,
-                    make_number (bidi_mirror[i].to));
-
-  Qparagraph_start = intern ("paragraph-start");
-  staticpro (&Qparagraph_start);
-  paragraph_start_re = Fsymbol_value (Qparagraph_start);
-  if (!STRINGP (paragraph_start_re))
-    paragraph_start_re = build_string ("\f\\|[ \t]*$");
-  staticpro (&paragraph_start_re);
-  Qparagraph_separate = intern ("paragraph-separate");
-  staticpro (&Qparagraph_separate);
-  paragraph_separate_re = Fsymbol_value (Qparagraph_separate);
-  if (!STRINGP (paragraph_separate_re))
-    paragraph_separate_re = build_string ("[ \t\f]*$");
-  staticpro (&paragraph_separate_re);
-  bidi_initialized = 1;
-}
+
+/***********************************************************************
+                        Utilities
+ ***********************************************************************/
 
 /* Return the bidi type of a character CH, subject to the current
    directional OVERRIDE.  */
@@ -243,6 +205,77 @@ bidi_mirror_char (int c)
   return c;
 }
 
+/* Determine the start-of-run (sor) directional type given the two
+   embedding levels on either side of the run boundary.  Also, update
+   the saved info about previously seen characters, since that info is
+   generally valid for a single level run.  */
+static inline void
+bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
+{
+  int higher_level = level_before > level_after ? level_before : level_after;
+
+  /* The prev_was_pdf gork is required for when we have several PDFs
+     in a row.  In that case, we want to compute the sor type for the
+     next level run only once: when we see the first PDF.  That's
+     because the sor type depends only on the higher of the two levels
+     that we find on the two sides of the level boundary (see UAX#9,
+     clause X10), and so we don't need to know the final embedding
+     level to which we descend after processing all the PDFs.  */
+  if (!bidi_it->prev_was_pdf || level_before < level_after)
+    /* FIXME: should the default sor direction be user selectable?  */
+    bidi_it->sor = (higher_level & 1) != 0 ? R2L : L2R;
+  if (level_before > level_after)
+    bidi_it->prev_was_pdf = 1;
+
+  bidi_it->prev.type = UNKNOWN_BT;
+  bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1 =
+    bidi_it->last_strong.orig_type = UNKNOWN_BT;
+  bidi_it->prev_for_neutral.type = bidi_it->sor == R2L ? STRONG_R : STRONG_L;
+  bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
+  bidi_it->prev_for_neutral.bytepos = bidi_it->bytepos;
+  bidi_it->next_for_neutral.type = bidi_it->next_for_neutral.type_after_w1 =
+    bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
+  bidi_it->ignore_bn_limit = -1; /* meaning it's unknown */
+}
+
+/* Push the current embedding level and override status; reset the
+   current level to LEVEL and the current override status to OVERRIDE.  */
+static inline void
+bidi_push_embedding_level (struct bidi_it *bidi_it,
+                           int level, bidi_dir_t override)
+{
+  bidi_it->stack_idx++;
+  xassert (bidi_it->stack_idx < BIDI_MAXLEVEL);
+  bidi_it->level_stack[bidi_it->stack_idx].level = level;
+  bidi_it->level_stack[bidi_it->stack_idx].override = override;
+}
+
+/* Pop the embedding level and directional override status from the
+   stack, and return the new level.  */
+static inline int
+bidi_pop_embedding_level (struct bidi_it *bidi_it)
+{
+  /* UAX#9 says to ignore invalid PDFs.  */
+  if (bidi_it->stack_idx > 0)
+    bidi_it->stack_idx--;
+  return bidi_it->level_stack[bidi_it->stack_idx].level;
+}
+
+/* Record in SAVED_INFO the information about the current character.  */
+static inline void
+bidi_remember_char (struct bidi_saved_info *saved_info,
+                    struct bidi_it *bidi_it)
+{
+  saved_info->charpos = bidi_it->charpos;
+  saved_info->bytepos = bidi_it->bytepos;
+  saved_info->type = bidi_it->type;
+  bidi_check_type (bidi_it->type);
+  saved_info->type_after_w1 = bidi_it->type_after_w1;
+  bidi_check_type (bidi_it->type_after_w1);
+  saved_info->orig_type = bidi_it->orig_type;
+  bidi_check_type (bidi_it->orig_type);
+}
+
 /* Copy the bidi iterator from FROM to TO.  To save cycles, this only
    copies the part of the level stack that is actually in use.  */
 static inline void
@@ -259,22 +292,37 @@ bidi_copy_it (struct bidi_it *to, struct bidi_it *from)
     to->level_stack[i] = from->level_stack[i];
 }
 
-/* Caching the bidi iterator states.  */
+
+/***********************************************************************
+                        Caching the bidi iterator states
+ ***********************************************************************/
 
 #define BIDI_CACHE_CHUNK 200
 static struct bidi_it *bidi_cache;
 static size_t bidi_cache_size = 0;
 static size_t elsz = sizeof (struct bidi_it);
-static int bidi_cache_idx;      /* next unused cache slot */
-static int bidi_cache_last_idx; /* slot of last cache hit */
-
+static EMACS_INT bidi_cache_idx;        /* next unused cache slot */
+static EMACS_INT bidi_cache_last_idx;   /* slot of last cache hit */
+static EMACS_INT bidi_cache_start = 0;  /* start of cache for this
+                                           "stack" level */
+
+/* Reset the cache state to the empty state.  We only reset the part
+   of the cache relevant to iteration of the current object.  Previous
+   objects, which are pushed on the display iterator's stack, are left
+   intact.  This is called when the cached information is no more
+   useful for the current iteration, e.g. when we were reseated to a
+   new position on the same object.  */
 static inline void
 bidi_cache_reset (void)
 {
-  bidi_cache_idx = 0;
+  bidi_cache_idx = bidi_cache_start;
   bidi_cache_last_idx = -1;
 }
 
+/* Shrink the cache to its minimal size.  Called when we init the bidi
+   iterator for reordering a buffer or a string that does not come
+   from display properties, because that means all the previously
+   cached info is of no further use.  */
 static inline void
 bidi_cache_shrink (void)
 {
@@ -288,11 +336,11 @@ bidi_cache_shrink (void)
 }
 
 static inline void
-bidi_cache_fetch_state (int idx, struct bidi_it *bidi_it)
+bidi_cache_fetch_state (EMACS_INT idx, struct bidi_it *bidi_it)
 {
   int current_scan_dir = bidi_it->scan_dir;
 
-  if (idx < 0 || idx >= bidi_cache_idx)
+  if (idx < bidi_cache_start || idx >= bidi_cache_idx)
     abort ();
 
   bidi_copy_it (bidi_it, &bidi_cache[idx]);
@@ -304,13 +352,15 @@ bidi_cache_fetch_state (int idx, struct bidi_it *bidi_it)
    level less or equal to LEVEL.  if LEVEL is -1, disregard the
    resolved levels in cached states.  DIR, if non-zero, means search
    in that direction from the last cache hit.  */
-static inline int
+static inline EMACS_INT
 bidi_cache_search (EMACS_INT charpos, int level, int dir)
 {
-  int i, i_start;
+  EMACS_INT i, i_start;
 
-  if (bidi_cache_idx)
+  if (bidi_cache_idx > bidi_cache_start)
     {
+      if (bidi_cache_last_idx == -1)
+        bidi_cache_last_idx = bidi_cache_idx - 1;
       if (charpos < bidi_cache[bidi_cache_last_idx].charpos)
         {
           dir = -1;
@@ -333,7 +383,7 @@ bidi_cache_search (EMACS_INT charpos, int level, int dir)
       if (dir < 0)
         {
           /* Linear search for now; FIXME!  */
-          for (i = i_start; i >= 0; i--)
+          for (i = i_start; i >= bidi_cache_start; i--)
             if (bidi_cache[i].charpos <= charpos
                 && charpos < bidi_cache[i].charpos + bidi_cache[i].nchars
                 && (level == -1 || bidi_cache[i].resolved_level <= level))
@@ -355,8 +405,9 @@ bidi_cache_search (EMACS_INT charpos, int level, int dir)
 /* Find a cached state where the resolved level changes to a value
    that is lower than LEVEL, and return its cache slot index.  DIR is
    the direction to search, starting with the last used cache slot.
-   BEFORE, if non-zero, means return the index of the slot that is
-   ``before'' the level change in the search direction.  That is,
+   If DIR is zero, we search backwards from the last occupied cache
+   slot.  BEFORE, if non-zero, means return the index of the slot that
+   is ``before'' the level change in the search direction.  That is,
    given the cached levels like this:
 
          1122333442211
@@ -366,14 +417,16 @@ bidi_cache_search (EMACS_INT charpos, int level, int dir)
    C, searching backwards (DIR = -1) for LEVEL = 2 will return the
    index of slot B or A, depending whether BEFORE is, respectively,
    non-zero or zero.  */
-static int
+static EMACS_INT
 bidi_cache_find_level_change (int level, int dir, int before)
 {
   if (bidi_cache_idx)
     {
-      int i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
+      EMACS_INT i = dir ? bidi_cache_last_idx : bidi_cache_idx - 1;
       int incr = before ? 1 : 0;
 
+      xassert (!dir || bidi_cache_last_idx >= 0);
+
       if (!dir)
         dir = -1;
       else if (!incr)
@@ -381,7 +434,7 @@ bidi_cache_find_level_change (int level, int dir, int before)
 
       if (dir < 0)
         {
-          while (i >= incr)
+          while (i >= bidi_cache_start + incr)
             {
               if (bidi_cache[i - incr].resolved_level >= 0
                   && bidi_cache[i - incr].resolved_level < level)
@@ -405,9 +458,22 @@ bidi_cache_find_level_change (int level, int dir, int before)
 }
 
 static inline void
+bidi_cache_ensure_space (EMACS_INT idx)
+{
+  /* Enlarge the cache as needed.  */
+  if (idx >= bidi_cache_size)
+    {
+      while (idx >= bidi_cache_size)
+        bidi_cache_size += BIDI_CACHE_CHUNK;
+      bidi_cache =
+        (struct bidi_it *) xrealloc (bidi_cache, bidi_cache_size * elsz);
+    }
+}
+
+static inline void
 bidi_cache_iterator_state (struct bidi_it *bidi_it, int resolved)
 {
-  int idx;
+  EMACS_INT idx;
 
   /* We should never cache on backward scans.  */
   if (bidi_it->scan_dir == -1)
@@ -417,23 +483,17 @@ bidi_cache_iterator_state (struct bidi_it *bidi_it, int resolved)
   if (idx < 0)
     {
       idx = bidi_cache_idx;
-      /* Enlarge the cache as needed.  */
-      if (idx >= bidi_cache_size)
-        {
-          bidi_cache_size += BIDI_CACHE_CHUNK;
-          bidi_cache =
-            (struct bidi_it *) xrealloc (bidi_cache, bidi_cache_size * elsz);
-        }
+      bidi_cache_ensure_space (idx);
       /* Character positions should correspond to cache positions 1:1.
          If we are outside the range of cached positions, the cache is
          useless and must be reset.  */
-      if (idx > 0 &&
+      if (idx > bidi_cache_start &&
           (bidi_it->charpos > (bidi_cache[idx - 1].charpos
                                + bidi_cache[idx - 1].nchars)
-           || bidi_it->charpos < bidi_cache[0].charpos))
+           || bidi_it->charpos < bidi_cache[bidi_cache_start].charpos))
         {
           bidi_cache_reset ();
-          idx = 0;
+          idx = bidi_cache_start;
         }
       if (bidi_it->nchars <= 0)
         abort ();
@@ -468,9 +528,9 @@ bidi_cache_iterator_state (struct bidi_it *bidi_it, int resolved)
 static inline bidi_type_t
 bidi_cache_find (EMACS_INT charpos, int level, struct bidi_it *bidi_it)
 {
-  int i = bidi_cache_search (charpos, level, bidi_it->scan_dir);
+  EMACS_INT i = bidi_cache_search (charpos, level, bidi_it->scan_dir);
 
-  if (i >= 0)
+  if (i >= bidi_cache_start)
     {
       bidi_dir_t current_scan_dir = bidi_it->scan_dir;
 
@@ -488,69 +548,245 @@ bidi_cache_find (EMACS_INT charpos, int level, struct bidi_it *bidi_it)
 static inline int
 bidi_peek_at_next_level (struct bidi_it *bidi_it)
 {
-  if (bidi_cache_idx == 0 || bidi_cache_last_idx == -1)
+  if (bidi_cache_idx == bidi_cache_start || bidi_cache_last_idx == -1)
     abort ();
   return bidi_cache[bidi_cache_last_idx + bidi_it->scan_dir].resolved_level;
 }
 
-/* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
-   Value is the non-negative length of the paragraph separator
-   following the buffer position, -1 if position is at the beginning
-   of a new paragraph, or -2 if position is neither at beginning nor
-   at end of a paragraph.  */
-static EMACS_INT
-bidi_at_paragraph_end (EMACS_INT charpos, EMACS_INT bytepos)
+
+/***********************************************************************
+             Pushing and popping the bidi iterator state
+ ***********************************************************************/
+/* 5-slot stack for saving the start of the previous level of the
+   cache.  xdisp.c maintains a 5-slot stack for its iterator state,
+   and we need the same size of our stack.  */
+static EMACS_INT bidi_cache_start_stack[IT_STACK_SIZE];
+static int bidi_cache_sp;
+
+/* Push the bidi iterator state in preparation for reordering a
+   different object, e.g. display string found at certain buffer
+   position.  Pushing the bidi iterator boils down to saving its
+   entire state on the cache and starting a new cache "stacked" on top
+   of the current cache.  */
+void
+bidi_push_it (struct bidi_it *bidi_it)
 {
-  Lisp_Object sep_re;
-  Lisp_Object start_re;
-  EMACS_INT val;
+  /* Save the current iterator state in its entirety after the last
+     used cache slot.  */
+  bidi_cache_ensure_space (bidi_cache_idx);
+  memcpy (&bidi_cache[bidi_cache_idx++], bidi_it, sizeof (struct bidi_it));
 
-  sep_re = paragraph_separate_re;
-  start_re = paragraph_start_re;
+  /* Push the current cache start onto the stack.  */
+  xassert (bidi_cache_sp < IT_STACK_SIZE);
+  bidi_cache_start_stack[bidi_cache_sp++] = bidi_cache_start;
 
-  val = fast_looking_at (sep_re, charpos, bytepos, ZV, ZV_BYTE, Qnil);
-  if (val < 0)
+  /* Start a new level of cache, and make it empty.  */
+  bidi_cache_start = bidi_cache_idx;
+  bidi_cache_last_idx = -1;
+}
+
+/* Restore the iterator state saved by bidi_push_it and return the
+   cache to the corresponding state.  */
+void
+bidi_pop_it (struct bidi_it *bidi_it)
+{
+  if (bidi_cache_start <= 0)
+    abort ();
+
+  /* Reset the next free cache slot index to what it was before the
+     call to bidi_push_it.  */
+  bidi_cache_idx = bidi_cache_start - 1;
+
+  /* Restore the bidi iterator state saved in the cache.  */
+  memcpy (bidi_it, &bidi_cache[bidi_cache_idx], sizeof (struct bidi_it));
+
+  /* Pop the previous cache start from the stack.  */
+  if (bidi_cache_sp <= 0)
+    abort ();
+  bidi_cache_start = bidi_cache_start_stack[--bidi_cache_sp];
+
+  /* Invalidate the last-used cache slot data.  */
+  bidi_cache_last_idx = -1;
+}
+
+/* Stash away a copy of the cache and its control variables.  */
+void *
+bidi_shelve_cache (void)
+{
+  unsigned char *databuf;
+
+  if (bidi_cache_idx == 0)
+    return NULL;
+
+  databuf = xmalloc (sizeof (bidi_cache_idx)
+                     + bidi_cache_idx * sizeof (struct bidi_it)
+                     + sizeof (bidi_cache_start_stack)
+                     + sizeof (bidi_cache_sp) + sizeof (bidi_cache_start)
+                     + sizeof (bidi_cache_last_idx));
+  memcpy (databuf, &bidi_cache_idx, sizeof (bidi_cache_idx));
+  memcpy (databuf + sizeof (bidi_cache_idx),
+          bidi_cache, bidi_cache_idx * sizeof (struct bidi_it));
+  memcpy (databuf + sizeof (bidi_cache_idx)
+          + bidi_cache_idx * sizeof (struct bidi_it),
+          bidi_cache_start_stack, sizeof (bidi_cache_start_stack));
+  memcpy (databuf + sizeof (bidi_cache_idx)
+          + bidi_cache_idx * sizeof (struct bidi_it)
+          + sizeof (bidi_cache_start_stack),
+          &bidi_cache_sp, sizeof (bidi_cache_sp));
+  memcpy (databuf + sizeof (bidi_cache_idx)
+          + bidi_cache_idx * sizeof (struct bidi_it)
+          + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
+          &bidi_cache_start, sizeof (bidi_cache_start));
+  memcpy (databuf + sizeof (bidi_cache_idx)
+          + bidi_cache_idx * sizeof (struct bidi_it)
+          + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
+          + sizeof (bidi_cache_start),
+          &bidi_cache_last_idx, sizeof (bidi_cache_last_idx));
+
+  return databuf;
+}
+
+/* Restore the cache state from a copy stashed away by bidi_shelve_cache.  */
+void
+bidi_unshelve_cache (void *databuf)
+{
+  unsigned char *p = databuf;
+
+  if (!p)
     {
-      if (fast_looking_at (start_re, charpos, bytepos, ZV, ZV_BYTE, Qnil) >= 0)
-        val = -1;
-      else
-        val = -2;
+      /* A NULL pointer means an empty cache.  */
+      bidi_cache_start = 0;
+      bidi_cache_sp = 0;
+      bidi_cache_reset ();
     }
+  else
+    {
+      memcpy (&bidi_cache_idx, p, sizeof (bidi_cache_idx));
+      bidi_cache_ensure_space (bidi_cache_idx);
+      memcpy (bidi_cache, p + sizeof (bidi_cache_idx),
+              bidi_cache_idx * sizeof (struct bidi_it));
+      memcpy (bidi_cache_start_stack,
+              p + sizeof (bidi_cache_idx)
+              + bidi_cache_idx * sizeof (struct bidi_it),
+              sizeof (bidi_cache_start_stack));
+      memcpy (&bidi_cache_sp,
+              p + sizeof (bidi_cache_idx)
+              + bidi_cache_idx * sizeof (struct bidi_it)
+              + sizeof (bidi_cache_start_stack),
+              sizeof (bidi_cache_sp));
+      memcpy (&bidi_cache_start,
+              p + sizeof (bidi_cache_idx)
+              + bidi_cache_idx * sizeof (struct bidi_it)
+              + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp),
+              sizeof (bidi_cache_start));
+      memcpy (&bidi_cache_last_idx,
+              p + sizeof (bidi_cache_idx)
+              + bidi_cache_idx * sizeof (struct bidi_it)
+              + sizeof (bidi_cache_start_stack) + sizeof (bidi_cache_sp)
+              + sizeof (bidi_cache_start),
+              sizeof (bidi_cache_last_idx));
+
+      xfree (p);
+    }
+}
 
-  return val;
+
+/***********************************************************************
+                        Initialization
+ ***********************************************************************/
+static void
+bidi_initialize (void)
+{
+
+#include "biditype.h"
+#include "bidimirror.h"
+
+  int i;
+
+  bidi_type_table = Fmake_char_table (Qnil, make_number (STRONG_L));
+  staticpro (&bidi_type_table);
+
+  for (i = 0; i < sizeof bidi_type / sizeof bidi_type[0]; i++)
+    char_table_set_range (bidi_type_table, bidi_type[i].from, bidi_type[i].to,
+                          make_number (bidi_type[i].type));
+
+  bidi_mirror_table = Fmake_char_table (Qnil, Qnil);
+  staticpro (&bidi_mirror_table);
+
+  for (i = 0; i < sizeof bidi_mirror / sizeof bidi_mirror[0]; i++)
+    char_table_set (bidi_mirror_table, bidi_mirror[i].from,
+                    make_number (bidi_mirror[i].to));
+
+  Qparagraph_start = intern ("paragraph-start");
+  staticpro (&Qparagraph_start);
+  paragraph_start_re = Fsymbol_value (Qparagraph_start);
+  if (!STRINGP (paragraph_start_re))
+    paragraph_start_re = build_string ("\f\\|[ \t]*$");
+  staticpro (&paragraph_start_re);
+  Qparagraph_separate = intern ("paragraph-separate");
+  staticpro (&Qparagraph_separate);
+  paragraph_separate_re = Fsymbol_value (Qparagraph_separate);
+  if (!STRINGP (paragraph_separate_re))
+    paragraph_separate_re = build_string ("[ \t\f]*$");
+  staticpro (&paragraph_separate_re);
+
+  bidi_cache_sp = 0;
+
+  bidi_initialized = 1;
 }
 
-/* Determine the start-of-run (sor) directional type given the two
-   embedding levels on either side of the run boundary.  Also, update
-   the saved info about previously seen characters, since that info is
-   generally valid for a single level run.  */
+/* Do whatever UAX#9 clause X8 says should be done at paragraph's
+   end.  */
 static inline void
-bidi_set_sor_type (struct bidi_it *bidi_it, int level_before, int level_after)
+bidi_set_paragraph_end (struct bidi_it *bidi_it)
 {
-  int higher_level = level_before > level_after ? level_before : level_after;
-
-  /* The prev_was_pdf gork is required for when we have several PDFs
-     in a row.  In that case, we want to compute the sor type for the
-     next level run only once: when we see the first PDF.  That's
-     because the sor type depends only on the higher of the two levels
-     that we find on the two sides of the level boundary (see UAX#9,
-     clause X10), and so we don't need to know the final embedding
-     level to which we descend after processing all the PDFs.  */
-  if (!bidi_it->prev_was_pdf || level_before < level_after)
-    /* FIXME: should the default sor direction be user selectable?  */
-    bidi_it->sor = (higher_level & 1) != 0 ? R2L : L2R;
-  if (level_before > level_after)
-    bidi_it->prev_was_pdf = 1;
+  bidi_it->invalid_levels = 0;
+  bidi_it->invalid_rl_levels = -1;
+  bidi_it->stack_idx = 0;
+  bidi_it->resolved_level = bidi_it->level_stack[0].level;
+}
 
-  bidi_it->prev.type = UNKNOWN_BT;
+/* Initialize the bidi iterator from buffer/string position CHARPOS.  */
+void
+bidi_init_it (EMACS_INT charpos, EMACS_INT bytepos, int frame_window_p,
+              struct bidi_it *bidi_it)
+{
+  if (! bidi_initialized)
+    bidi_initialize ();
+  if (charpos >= 0)
+    bidi_it->charpos = charpos;
+  if (bytepos >= 0)
+    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;
+  bidi_it->separator_limit = -1;
+  bidi_it->type = NEUTRAL_B;
+  bidi_it->type_after_w1 = NEUTRAL_B;
+  bidi_it->orig_type = NEUTRAL_B;
+  bidi_it->prev_was_pdf = 0;
+  bidi_it->prev.type = bidi_it->prev.type_after_w1 =
+    bidi_it->prev.orig_type = UNKNOWN_BT;
   bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1 =
     bidi_it->last_strong.orig_type = UNKNOWN_BT;
-  bidi_it->prev_for_neutral.type = bidi_it->sor == R2L ? STRONG_R : STRONG_L;
-  bidi_it->prev_for_neutral.charpos = bidi_it->charpos;
-  bidi_it->prev_for_neutral.bytepos = bidi_it->bytepos;
-  bidi_it->next_for_neutral.type = bidi_it->next_for_neutral.type_after_w1 =
+  bidi_it->next_for_neutral.charpos = -1;
+  bidi_it->next_for_neutral.type =
+    bidi_it->next_for_neutral.type_after_w1 =
     bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
-  bidi_it->ignore_bn_limit = 0; /* meaning it's unknown */
+  bidi_it->prev_for_neutral.charpos = -1;
+  bidi_it->prev_for_neutral.type =
+    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 */
+  /* We can only shrink the cache if we are at the bottom level of its
+     "stack".  */
+  if (bidi_cache_start == 0)
+    bidi_cache_shrink ();
+  else
+    bidi_cache_reset ();
 }
 
 /* Perform initializations for reordering a new line of bidi text.  */
@@ -571,6 +807,57 @@ bidi_line_init (struct bidi_it *bidi_it)
   bidi_cache_reset ();
 }
 
+
+/***********************************************************************
+                        Fetching characters
+ ***********************************************************************/
+
+/* Count bytes in string S between BEG/BEGBYTE and END.  BEG and END
+   are zero-based character positions in S, BEGBYTE is byte position
+   corresponding to BEG.  UNIBYTE, if non-zero, means S is a unibyte
+   string.  */
+static inline EMACS_INT
+bidi_count_bytes (const unsigned char *s, const EMACS_INT beg,
+                  const EMACS_INT begbyte, const EMACS_INT end, int unibyte)
+{
+  EMACS_INT pos = beg;
+  const unsigned char *p = s + begbyte, *start = p;
+
+  if (unibyte)
+    p = s + end;
+  else
+    {
+      if (!CHAR_HEAD_P (*p))
+        abort ();
+
+      while (pos < end)
+        {
+          p += BYTES_BY_CHAR_HEAD (*p);
+          pos++;
+        }
+    }
+
+  return p - start;
+}
+
+/* Fetch and returns the character at byte position BYTEPOS.  If S is
+   non-NULL, fetch the character from string S; otherwise fetch the
+   character from the current buffer.  UNIBYTE non-zero means S is a
+   unibyte string.  */
+static inline int
+bidi_char_at_pos (EMACS_INT bytepos, const unsigned char *s, int unibyte)
+{
+  if (s)
+    {
+      if (unibyte)
+        return s[bytepos];
+      else
+        return STRING_CHAR (s + bytepos);
+    }
+  else
+    return FETCH_MULTIBYTE_CHAR (bytepos);
+}
+
 /* 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
@@ -578,26 +865,34 @@ bidi_line_init (struct bidi_it *bidi_it)
    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.  */
+   string.  STRING->s is the C string to iterate, or NULL if iterating
+   over a buffer or a Lisp string; in the latter case, STRING->lstring
+   is the Lisp string.  */
 static inline int
 bidi_fetch_char (EMACS_INT bytepos, EMACS_INT charpos, EMACS_INT *disp_pos,
+                 struct bidi_string_data *string,
                  int frame_window_p, EMACS_INT *ch_len, EMACS_INT *nchars)
 {
   int ch;
+  EMACS_INT endpos =
+    (string->s || STRINGP (string->lstring)) ? string->schars : ZV;
+  struct text_pos pos;
 
-  /* 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);
+     the position of the next one.  That position could be at CHARPOS.  */
+  if (charpos < endpos && charpos > *disp_pos)
+    {
+      SET_TEXT_POS (pos, charpos, bytepos);
+      *disp_pos = compute_display_string_pos (&pos, string, frame_window_p);
+    }
 
   /* Fetch the character at BYTEPOS.  */
-  if (bytepos >= ZV_BYTE)
+  if (charpos >= endpos)
     {
       ch = BIDI_EOB;
       *ch_len = 1;
       *nchars = 1;
-      *disp_pos = ZV;
+      *disp_pos = endpos;
     }
   else if (charpos >= *disp_pos)
     {
@@ -608,28 +903,105 @@ bidi_fetch_char (EMACS_INT bytepos, EMACS_INT charpos, EMACS_INT *disp_pos,
       if (charpos > *disp_pos)
         abort ();
       /* Return the Unicode Object Replacement Character to represent
-         the entire run of characters covered by the display
-         string.  */
+         the entire run of characters covered by the display string.  */
       ch = 0xFFFC;
-      disp_end_pos = compute_display_string_end (*disp_pos);
+      disp_end_pos = compute_display_string_end (*disp_pos, string);
       *nchars = disp_end_pos - *disp_pos;
-      *ch_len = CHAR_TO_BYTE (disp_end_pos) - bytepos;
+      if (*nchars <= 0)
+        abort ();
+      if (string->s)
+        *ch_len = bidi_count_bytes (string->s, *disp_pos, bytepos,
+                                    disp_end_pos, string->unibyte);
+      else if (STRINGP (string->lstring))
+        *ch_len = bidi_count_bytes (SDATA (string->lstring), *disp_pos,
+                                    bytepos, disp_end_pos, string->unibyte);
+      else
+        *ch_len = CHAR_TO_BYTE (disp_end_pos) - bytepos;
     }
   else
     {
-      ch = FETCH_MULTIBYTE_CHAR (bytepos);
+      if (string->s)
+        {
+          int len;
+
+          if (!string->unibyte)
+            {
+              ch = STRING_CHAR_AND_LENGTH (string->s + bytepos, len);
+              *ch_len = len;
+            }
+          else
+            {
+              ch = UNIBYTE_TO_CHAR (string->s[bytepos]);
+              *ch_len = 1;
+            }
+        }
+      else if (STRINGP (string->lstring))
+        {
+          int len;
+
+          if (!string->unibyte)
+            {
+              ch = STRING_CHAR_AND_LENGTH (SDATA (string->lstring) + bytepos,
+                                           len);
+              *ch_len = len;
+            }
+          else
+            {
+              ch = UNIBYTE_TO_CHAR (SREF (string->lstring, bytepos));
+              *ch_len = 1;
+            }
+        }
+      else
+        {
+          ch = FETCH_MULTIBYTE_CHAR (bytepos);
+          *ch_len = CHAR_BYTES (ch);
+        }
       *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);
+  if (charpos + *nchars <= endpos && charpos + *nchars > *disp_pos)
+    {
+      SET_TEXT_POS (pos, charpos + *nchars, bytepos + *ch_len);
+      *disp_pos = compute_display_string_pos (&pos, string, frame_window_p);
+    }
 
   return ch;
 }
 
+
+/***********************************************************************
+                        Determining paragraph direction
+ ***********************************************************************/
+
+/* Check if buffer position CHARPOS/BYTEPOS is the end of a paragraph.
+   Value is the non-negative length of the paragraph separator
+   following the buffer position, -1 if position is at the beginning
+   of a new paragraph, or -2 if position is neither at beginning nor
+   at end of a paragraph.  */
+static EMACS_INT
+bidi_at_paragraph_end (EMACS_INT charpos, EMACS_INT bytepos)
+{
+  Lisp_Object sep_re;
+  Lisp_Object start_re;
+  EMACS_INT val;
+
+  sep_re = paragraph_separate_re;
+  start_re = paragraph_start_re;
+
+  val = fast_looking_at (sep_re, charpos, bytepos, ZV, ZV_BYTE, Qnil);
+  if (val < 0)
+    {
+      if (fast_looking_at (start_re, charpos, bytepos, ZV, ZV_BYTE, Qnil) >= 0)
+        val = -1;
+      else
+        val = -2;
+    }
+
+  return val;
+}
+
 /* 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
@@ -670,13 +1042,19 @@ void
 bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
 {
   EMACS_INT bytepos = bidi_it->bytepos;
+  int string_p = bidi_it->string.s != NULL || STRINGP (bidi_it->string.lstring);
   EMACS_INT pstartbyte;
+  /* Note that begbyte is a byte position, while end is a character
+     position.  Yes, this is ugly, but we are trying to avoid costly
+     calls to BYTE_TO_CHAR and its ilk.  */
+  EMACS_INT begbyte = string_p ? 0 : BEGV_BYTE;
+  EMACS_INT end = string_p ? bidi_it->string.schars : ZV;
 
   /* Special case for an empty buffer. */
-  if (bytepos == BEGV_BYTE && bytepos == ZV_BYTE)
+  if (bytepos == begbyte && bidi_it->charpos == end)
     dir = L2R;
   /* We should never be called at EOB or before BEGV.  */
-  else if (bytepos >= ZV_BYTE || bytepos < BEGV_BYTE)
+  else if (bidi_it->charpos >= end || bytepos < begbyte)
     abort ();
 
   if (dir == L2R)
@@ -695,6 +1073,7 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
       EMACS_INT ch_len, nchars;
       EMACS_INT pos, disp_pos = -1;
       bidi_type_t type;
+      const unsigned char *s;
 
       if (!bidi_initialized)
         bidi_initialize ();
@@ -712,7 +1091,10 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
          we are potentially in a new paragraph that doesn't yet
          exist.  */
       pos = bidi_it->charpos;
-      if (bytepos > BEGV_BYTE && FETCH_CHAR (bytepos) == '\n')
+      s = STRINGP (bidi_it->string.lstring) ?
+        SDATA (bidi_it->string.lstring) : bidi_it->string.s;
+      if (bytepos > begbyte
+          && bidi_char_at_pos (bytepos, s, bidi_it->string.unibyte) == '\n')
         {
           bytepos++;
           pos++;
@@ -720,17 +1102,25 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
 
       /* We are either at the beginning of a paragraph or in the
          middle of it.  Find where this paragraph starts.  */
-      pstartbyte = bidi_find_paragraph_start (pos, bytepos);
+      if (string_p)
+        {
+          /* We don't support changes of paragraph direction inside a
+             string.  It is treated as a single paragraph.  */
+          pstartbyte = 0;
+        }
+      else
+        pstartbyte = bidi_find_paragraph_start (pos, bytepos);
       bidi_it->separator_limit = -1;
       bidi_it->new_paragraph = 0;
 
       /* The following loop is run more than once only if NO_DEFAULT_P
-         is non-zero.  */
+         is non-zero, and only if we are iterating on a buffer.  */
       do {
         bytepos = pstartbyte;
-        pos = BYTE_TO_CHAR (bytepos);
-        ch = bidi_fetch_char (bytepos, pos, &disp_pos, bidi_it->frame_window_p,
-                              &ch_len, &nchars);
+        if (!string_p)
+          pos = BYTE_TO_CHAR (bytepos);
+        ch = bidi_fetch_char (bytepos, pos, &disp_pos, &bidi_it->string,
+                              bidi_it->frame_window_p, &ch_len, &nchars);
         type = bidi_get_type (ch, NEUTRAL_DIR);
 
         for (pos += nchars, bytepos += ch_len;
@@ -744,17 +1134,19 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
                        || type == LRE || type == LRO));
              type = bidi_get_type (ch, NEUTRAL_DIR))
           {
-            if (bytepos >= ZV_BYTE)
+            if (pos >= end)
               {
                 /* Pretend there's a paragraph separator at end of
-                   buffer.  */
+                   buffer/string.  */
                 type = NEUTRAL_B;
                 break;
               }
-            if (type == NEUTRAL_B && bidi_at_paragraph_end (pos, bytepos) >= -1)
+            if (!string_p
+                && type == NEUTRAL_B
+                && bidi_at_paragraph_end (pos, bytepos) >= -1)
               break;
             /* Fetch next character and advance to get past it.  */
-            ch = bidi_fetch_char (bytepos, pos, &disp_pos,
+            ch = bidi_fetch_char (bytepos, pos, &disp_pos, &bidi_it->string,
                                   bidi_it->frame_window_p, &ch_len, &nchars);
             pos += nchars;
             bytepos += ch_len;
@@ -763,7 +1155,8 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
           bidi_it->paragraph_dir = R2L;
         else if (type == STRONG_L)
           bidi_it->paragraph_dir = L2R;
-        if (no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR)
+        if (!string_p
+            && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR)
           {
             /* If this paragraph is at BEGV, default to L2R.  */
             if (pstartbyte == BEGV_BYTE)
@@ -786,7 +1179,8 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
                 pstartbyte = prevpbyte;
               }
           }
-      } while (no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR);
+      } while (!string_p
+               && no_default_p && bidi_it->paragraph_dir == NEUTRAL_DIR);
     }
   else
     abort ();
@@ -804,110 +1198,11 @@ bidi_paragraph_init (bidi_dir_t dir, struct bidi_it *bidi_it, int no_default_p)
   bidi_line_init (bidi_it);
 }
 
-/* Do whatever UAX#9 clause X8 says should be done at paragraph's
-   end.  */
-static inline void
-bidi_set_paragraph_end (struct bidi_it *bidi_it)
-{
-  bidi_it->invalid_levels = 0;
-  bidi_it->invalid_rl_levels = -1;
-  bidi_it->stack_idx = 0;
-  bidi_it->resolved_level = bidi_it->level_stack[0].level;
-}
-
-/* Initialize the bidi iterator from buffer/string position CHARPOS.  */
-void
-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;
-  bidi_it->separator_limit = -1;
-  bidi_it->type = NEUTRAL_B;
-  bidi_it->type_after_w1 = NEUTRAL_B;
-  bidi_it->orig_type = NEUTRAL_B;
-  bidi_it->prev_was_pdf = 0;
-  bidi_it->prev.type = bidi_it->prev.type_after_w1 =
-    bidi_it->prev.orig_type = UNKNOWN_BT;
-  bidi_it->last_strong.type = bidi_it->last_strong.type_after_w1 =
-    bidi_it->last_strong.orig_type = UNKNOWN_BT;
-  bidi_it->next_for_neutral.charpos = -1;
-  bidi_it->next_for_neutral.type =
-    bidi_it->next_for_neutral.type_after_w1 =
-    bidi_it->next_for_neutral.orig_type = UNKNOWN_BT;
-  bidi_it->prev_for_neutral.charpos = -1;
-  bidi_it->prev_for_neutral.type =
-    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 ();
-}
-
-/* Push the current embedding level and override status; reset the
-   current level to LEVEL and the current override status to OVERRIDE.  */
-static inline void
-bidi_push_embedding_level (struct bidi_it *bidi_it,
-                           int level, bidi_dir_t override)
-{
-  bidi_it->stack_idx++;
-  if (bidi_it->stack_idx >= BIDI_MAXLEVEL)
-    abort ();
-  bidi_it->level_stack[bidi_it->stack_idx].level = level;
-  bidi_it->level_stack[bidi_it->stack_idx].override = override;
-}
-
-/* Pop the embedding level and directional override status from the
-   stack, and return the new level.  */
-static inline int
-bidi_pop_embedding_level (struct bidi_it *bidi_it)
-{
-  /* UAX#9 says to ignore invalid PDFs.  */
-  if (bidi_it->stack_idx > 0)
-    bidi_it->stack_idx--;
-  return bidi_it->level_stack[bidi_it->stack_idx].level;
-}
-
-/* Record in SAVED_INFO the information about the current character.  */
-static inline void
-bidi_remember_char (struct bidi_saved_info *saved_info,
-                    struct bidi_it *bidi_it)
-{
-  saved_info->charpos = bidi_it->charpos;
-  saved_info->bytepos = bidi_it->bytepos;
-  saved_info->type = bidi_it->type;
-  bidi_check_type (bidi_it->type);
-  saved_info->type_after_w1 = bidi_it->type_after_w1;
-  bidi_check_type (bidi_it->type_after_w1);
-  saved_info->orig_type = bidi_it->orig_type;
-  bidi_check_type (bidi_it->orig_type);
-}
-
-/* Resolve the type of a neutral character according to the type of
-   surrounding strong text and the current embedding level.  */
-static inline bidi_type_t
-bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
-{
-  /* N1: European and Arabic numbers are treated as though they were R.  */
-  if (next_type == WEAK_EN || next_type == WEAK_AN)
-    next_type = STRONG_R;
-  if (prev_type == WEAK_EN || prev_type == WEAK_AN)
-    prev_type = STRONG_R;
-
-  if (next_type == prev_type)   /* N1 */
-    return next_type;
-  else if ((lev & 1) == 0)      /* N2 */
-    return STRONG_L;
-  else
-    return STRONG_R;
-}
+
+/***********************************************************************
+                 Resolving explicit and implicit levels.
+  The rest of this file constitutes the core of the UBA implementation.
+ ***********************************************************************/
 
 static inline int
 bidi_explicit_dir_char (int ch)
@@ -934,19 +1229,35 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
   int current_level;
   int new_level;
   bidi_dir_t override;
+  int string_p = bidi_it->string.s != NULL || STRINGP (bidi_it->string.lstring);
 
   /* 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
+  if (bidi_it->bytepos < (string_p ? 0 : BEGV_BYTE)
       || bidi_it->first_elt)
     {
       bidi_it->first_elt = 0;
-      if (bidi_it->charpos < BEGV)
-        bidi_it->charpos = BEGV;
-      bidi_it->bytepos = CHAR_TO_BYTE (bidi_it->charpos);
+      if (string_p)
+        {
+          const unsigned char *p =
+            STRINGP (bidi_it->string.lstring)
+            ? SDATA (bidi_it->string.lstring) : bidi_it->string.s;
+
+          if (bidi_it->charpos < 0)
+            bidi_it->charpos = 0;
+          bidi_it->bytepos = bidi_count_bytes (p, 0, 0, bidi_it->charpos,
+                                               bidi_it->string.unibyte);
+        }
+      else
+        {
+          if (bidi_it->charpos < BEGV)
+            bidi_it->charpos = BEGV;
+          bidi_it->bytepos = CHAR_TO_BYTE (bidi_it->charpos);
+        }
     }
-  else if (bidi_it->bytepos < ZV_BYTE)  /* don't move at ZV */
+  /* Don't move at end of buffer/string.  */
+  else if (bidi_it->charpos < (string_p ? bidi_it->string.schars : ZV))
     {
       /* Advance to the next character, skipping characters covered by
          display strings (nchars > 1).  */
@@ -962,12 +1273,12 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
   override = bidi_it->level_stack[bidi_it->stack_idx].override;
   new_level = current_level;
 
-  if (bidi_it->bytepos >= ZV_BYTE)
+  if (bidi_it->charpos >= (string_p ? bidi_it->string.schars : ZV))
     {
       curchar = BIDI_EOB;
       bidi_it->ch_len = 1;
       bidi_it->nchars = 1;
-      bidi_it->disp_pos = ZV;
+      bidi_it->disp_pos = (string_p ? bidi_it->string.schars : ZV);
     }
   else
     {
@@ -975,7 +1286,8 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
          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->disp_pos, &bidi_it->string,
+                                 bidi_it->frame_window_p,
                                  &bidi_it->ch_len, &bidi_it->nchars);
     }
   bidi_it->ch = curchar;
@@ -1000,7 +1312,7 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
         bidi_it->type_after_w1 = type;
         bidi_check_type (bidi_it->type_after_w1);
         type = WEAK_BN; /* X9/Retaining */
-        if (bidi_it->ignore_bn_limit <= 0)
+        if (bidi_it->ignore_bn_limit <= -1)
           {
             if (current_level <= BIDI_MAXLEVEL - 4)
               {
@@ -1033,7 +1345,7 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
         bidi_it->type_after_w1 = type;
         bidi_check_type (bidi_it->type_after_w1);
         type = WEAK_BN; /* X9/Retaining */
-        if (bidi_it->ignore_bn_limit <= 0)
+        if (bidi_it->ignore_bn_limit <= -1)
           {
             if (current_level <= BIDI_MAXLEVEL - 5)
               {
@@ -1068,7 +1380,7 @@ bidi_resolve_explicit_1 (struct bidi_it *bidi_it)
         bidi_it->type_after_w1 = type;
         bidi_check_type (bidi_it->type_after_w1);
         type = WEAK_BN; /* X9/Retaining */
-        if (bidi_it->ignore_bn_limit <= 0)
+        if (bidi_it->ignore_bn_limit <= -1)
           {
             if (!bidi_it->invalid_rl_levels)
               {
@@ -1111,13 +1423,17 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
 {
   int prev_level = bidi_it->level_stack[bidi_it->stack_idx].level;
   int new_level  = bidi_resolve_explicit_1 (bidi_it);
+  EMACS_INT eob = bidi_it->string.s ? bidi_it->string.schars : ZV;
+  const unsigned char *s = STRINGP (bidi_it->string.lstring)
+    ? SDATA (bidi_it->string.lstring) : bidi_it->string.s;
 
   if (prev_level < new_level
       && 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_MULTIBYTE_CHAR (bidi_it->bytepos
-                                                       + bidi_it->ch_len)))
+      && bidi_it->ignore_bn_limit == -1 /* only if not already known */
+      && bidi_it->charpos < eob         /* not already at EOB */
+      && bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
+                                                   + bidi_it->ch_len, s,
+                                                   bidi_it->string.unibyte)))
     {
       /* Avoid pushing and popping embedding levels if the level run
          is empty, as this breaks level runs where it shouldn't.
@@ -1129,12 +1445,17 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
 
       bidi_copy_it (&saved_it, bidi_it);
 
-      while (bidi_explicit_dir_char (FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
-                                                           + bidi_it->ch_len)))
+      while (bidi_explicit_dir_char (bidi_char_at_pos (bidi_it->bytepos
+                                                       + bidi_it->ch_len, s,
+                                                       bidi_it->string.unibyte)))
         {
           /* This advances to the next character, skipping any
              characters covered by display strings.  */
           level = bidi_resolve_explicit_1 (bidi_it);
+          /* If string.lstring was relocated inside bidi_resolve_explicit_1,
+             a pointer to its data is no longer valid.  */
+          if (STRINGP (bidi_it->string.lstring))
+            s = SDATA (bidi_it->string.lstring);
         }
 
       if (bidi_it->nchars <= 0)
@@ -1142,10 +1463,10 @@ bidi_resolve_explicit (struct bidi_it *bidi_it)
       if (level == prev_level)  /* empty embedding */
         saved_it.ignore_bn_limit = bidi_it->charpos + bidi_it->nchars;
       else                      /* this embedding is non-empty */
-        saved_it.ignore_bn_limit = -1;
+        saved_it.ignore_bn_limit = -2;
 
       bidi_copy_it (bidi_it, &saved_it);
-      if (bidi_it->ignore_bn_limit > 0)
+      if (bidi_it->ignore_bn_limit > -1)
         {
           /* We pushed a level, but we shouldn't have.  Undo that. */
           if (!bidi_it->invalid_rl_levels)
@@ -1188,6 +1509,9 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
   int next_char;
   bidi_type_t type_of_next;
   struct bidi_it saved_it;
+  EMACS_INT eob =
+    (STRINGP (bidi_it->string.lstring) || bidi_it->string.s)
+    ? bidi_it->string.schars : ZV;
 
   type = bidi_it->type;
   override = bidi_it->level_stack[bidi_it->stack_idx].override;
@@ -1254,10 +1578,15 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
                         && bidi_it->prev.orig_type == WEAK_EN)
                        || bidi_it->prev.type_after_w1 == WEAK_AN)))
         {
+          const unsigned char *s =
+            STRINGP (bidi_it->string.lstring)
+            ? SDATA (bidi_it->string.lstring) : bidi_it->string.s;
+
           next_char =
-            bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
-            ? BIDI_EOB : FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
-                                               + bidi_it->ch_len);
+            bidi_it->charpos + bidi_it->nchars >= eob
+            ? BIDI_EOB
+            : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len, s,
+                                bidi_it->string.unibyte);
           type_of_next = bidi_get_type (next_char, override);
 
           if (type_of_next == WEAK_BN
@@ -1306,13 +1635,17 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
           else                  /* W5: ET/BN with EN after it.  */
             {
               EMACS_INT en_pos = bidi_it->charpos + bidi_it->nchars;
+              const unsigned char *s =
+                STRINGP (bidi_it->string.lstring)
+                ? SDATA (bidi_it->string.lstring) : bidi_it->string.s;
 
               if (bidi_it->nchars <= 0)
                 abort ();
               next_char =
-                bidi_it->bytepos + bidi_it->ch_len >= ZV_BYTE
-                ? BIDI_EOB : FETCH_MULTIBYTE_CHAR (bidi_it->bytepos
-                                                   + bidi_it->ch_len);
+                bidi_it->charpos + bidi_it->nchars >= eob
+                ? BIDI_EOB
+                : bidi_char_at_pos (bidi_it->bytepos + bidi_it->ch_len, s,
+                                    bidi_it->string.unibyte);
               type_of_next = bidi_get_type (next_char, override);
 
               if (type_of_next == WEAK_ET
@@ -1373,6 +1706,25 @@ bidi_resolve_weak (struct bidi_it *bidi_it)
   return type;
 }
 
+/* Resolve the type of a neutral character according to the type of
+   surrounding strong text and the current embedding level.  */
+static inline bidi_type_t
+bidi_resolve_neutral_1 (bidi_type_t prev_type, bidi_type_t next_type, int lev)
+{
+  /* N1: European and Arabic numbers are treated as though they were R.  */
+  if (next_type == WEAK_EN || next_type == WEAK_AN)
+    next_type = STRONG_R;
+  if (prev_type == WEAK_EN || prev_type == WEAK_AN)
+    prev_type = STRONG_R;
+
+  if (next_type == prev_type)   /* N1 */
+    return next_type;
+  else if ((lev & 1) == 0)      /* N2 */
+    return STRONG_L;
+  else
+    return STRONG_R;
+}
+
 static bidi_type_t
 bidi_resolve_neutral (struct bidi_it *bidi_it)
 {
@@ -1509,11 +1861,11 @@ bidi_type_of_next_char (struct bidi_it *bidi_it)
 
   /* Reset the limit until which to ignore BNs if we step out of the
      area where we found only empty levels.  */
-  if ((bidi_it->ignore_bn_limit > 0
+  if ((bidi_it->ignore_bn_limit > -1
        && bidi_it->ignore_bn_limit <= bidi_it->charpos)
-      || (bidi_it->ignore_bn_limit == -1
+      || (bidi_it->ignore_bn_limit == -2
           && !bidi_explicit_dir_char (bidi_it->ch)))
-    bidi_it->ignore_bn_limit = 0;
+    bidi_it->ignore_bn_limit = -1;
 
   type = bidi_resolve_neutral (bidi_it);
 
@@ -1530,12 +1882,16 @@ 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;
+  EMACS_INT next_char_pos = -2;
 
   if (bidi_it->scan_dir == 1)
     {
+      EMACS_INT eob =
+        (bidi_it->string.s || STRINGP (bidi_it->string.lstring))
+        ? bidi_it->string.schars : ZV;
+
       /* There's no sense in trying to advance if we hit end of text.  */
-      if (bidi_it->bytepos >= ZV_BYTE)
+      if (bidi_it->charpos >= eob)
         return bidi_it->resolved_level;
 
       /* Record the info about the previous character.  */
@@ -1575,17 +1931,27 @@ bidi_level_of_next_char (struct bidi_it *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_cache_idx > bidi_cache_start && !bidi_it->first_elt)
     {
+      int bob =
+        (bidi_it->string.s || STRINGP (bidi_it->string.lstring)) ? 0 : 1;
+
       if (bidi_it->scan_dir > 0)
         {
           if (bidi_it->nchars <= 0)
             abort ();
           next_char_pos = bidi_it->charpos + bidi_it->nchars;
         }
-      else
+      else if (bidi_it->charpos >= bob)
+        /* Implementation note: we allow next_char_pos to be as low as
+           0 for buffers or -1 for strings, and that is okay because
+           that's the "position" of the sentinel iterator state we
+           cached at the beginning of the iteration.  */
         next_char_pos = bidi_it->charpos - 1;
-      type = bidi_cache_find (next_char_pos, -1, bidi_it);
+      if (next_char_pos >= bob - 1)
+        type = bidi_cache_find (next_char_pos, -1, bidi_it);
+      else
+        type = UNKNOWN_BT;
     }
   else
     type = UNKNOWN_BT;
@@ -1652,13 +2018,14 @@ bidi_level_of_next_char (struct bidi_it *bidi_it)
       EMACS_INT cpos = bidi_it->charpos;
       EMACS_INT disp_pos = bidi_it->disp_pos;
       EMACS_INT nc = bidi_it->nchars;
+      struct bidi_string_data bs = bidi_it->string;
       bidi_type_t chtype;
       int fwp = bidi_it->frame_window_p;
 
       if (bidi_it->nchars <= 0)
         abort ();
       do {
-        ch = bidi_fetch_char (bpos += clen, cpos += nc, &disp_pos, fwp,
+        ch = bidi_fetch_char (bpos += clen, cpos += nc, &disp_pos, &bs, fwp,
                               &clen, &nc);
         if (ch == '\n' || ch == BIDI_EOB /* || ch == LINESEP_CHAR */)
           chtype = NEUTRAL_B;
@@ -1756,10 +2123,11 @@ static void
 bidi_find_other_level_edge (struct bidi_it *bidi_it, int level, int end_flag)
 {
   int dir = end_flag ? -bidi_it->scan_dir : bidi_it->scan_dir;
-  int idx;
+  EMACS_INT idx;
 
   /* Try the cache first.  */
-  if ((idx = bidi_cache_find_level_change (level, dir, end_flag)) >= 0)
+  if ((idx = bidi_cache_find_level_change (level, dir, end_flag))
+      >= bidi_cache_start)
     bidi_cache_fetch_state (idx, bidi_it);
   else
     {
@@ -1781,12 +2149,21 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
 {
   int old_level, new_level, next_level;
   struct bidi_it sentinel;
+  struct gcpro gcpro1;
+
+  if (bidi_it->charpos < 0 || bidi_it->bytepos < 0)
+    abort ();
 
   if (bidi_it->scan_dir == 0)
     {
       bidi_it->scan_dir = 1;    /* default to logical order */
     }
 
+  /* The code below can call eval, and thus cause GC.  If we are
+     iterating a Lisp string, make sure it won't be GCed.  */
+  if (STRINGP (bidi_it->string.lstring))
+    GCPRO1 (bidi_it->string.lstring);
+
   /* If we just passed a newline, initialize for the next line.  */
   if (!bidi_it->first_elt && bidi_it->orig_type == NEUTRAL_B)
     bidi_line_init (bidi_it);
@@ -1794,7 +2171,7 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
   /* Prepare the sentinel iterator state, and cache it.  When we bump
      into it, scanning backwards, we'll know that the last non-base
      level is exhausted.  */
-  if (bidi_cache_idx == 0)
+  if (bidi_cache_idx == bidi_cache_start)
     {
       bidi_copy_it (&sentinel, bidi_it);
       if (bidi_it->first_elt)
@@ -1869,26 +2246,34 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
      reordering, whereas we _must_ know the paragraph base direction
      _before_ we process the paragraph's text, since the base
      direction affects the reordering.  */
-  if (bidi_it->scan_dir == 1
-      && bidi_it->orig_type == NEUTRAL_B
-      && bidi_it->bytepos < ZV_BYTE)
+  if (bidi_it->scan_dir == 1 && bidi_it->orig_type == NEUTRAL_B)
     {
-      EMACS_INT sep_len =
-        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)
+      /* The paragraph direction of the entire string, once
+         determined, is in effect for the entire string.  Setting the
+         separator limit to the end of the string prevents
+         bidi_paragraph_init from being called automatically on this
+         string.  */
+      if (bidi_it->string.s || STRINGP (bidi_it->string.lstring))
+        bidi_it->separator_limit = bidi_it->string.schars;
+      else if (bidi_it->bytepos < ZV_BYTE)
         {
-          bidi_it->new_paragraph = 1;
-          /* Record the buffer position of the last character of the
-             paragraph separator.  */
-          bidi_it->separator_limit =
-            bidi_it->charpos + bidi_it->nchars + sep_len;
+          EMACS_INT sep_len =
+            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 + bidi_it->nchars + sep_len;
+            }
         }
     }
 
-  if (bidi_it->scan_dir == 1 && bidi_cache_idx)
+  if (bidi_it->scan_dir == 1 && bidi_cache_idx > bidi_cache_start)
     {
       /* If we are at paragraph's base embedding level and beyond the
          last cached position, the cache's job is done and we can
@@ -1904,6 +2289,9 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
       else
         bidi_cache_iterator_state (bidi_it, 1);
     }
+
+  if (STRINGP (bidi_it->string.lstring))
+    UNGCPRO;
 }
 
 /* This is meant to be called from within the debugger, whenever you
@@ -1920,7 +2308,7 @@ bidi_dump_cached_states (void)
       fprintf (stderr, "The cache is empty.\n");
       return;
     }
-  fprintf (stderr, "Total of %d state%s in cache:\n",
+  fprintf (stderr, "Total of  %"pD"d state%s in cache:\n",
            bidi_cache_idx, bidi_cache_idx == 1 ? "" : "s");
 
   for (i = bidi_cache[bidi_cache_idx - 1].charpos; i > 0; i /= 10)
diff --git a/src/dispextern.h b/src/dispextern.h
index c0a67690a5c..dc44c698164 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -1820,9 +1820,21 @@ struct bidi_stack {
   bidi_dir_t override;
 };
 
+/* Data type for storing information about a string being iterated on.  */
+struct bidi_string_data {
+  Lisp_Object lstring;          /* Lisp string to reorder, or nil */
+  const unsigned char *s;       /* string data, or NULL if reordering buffer */
+  EMACS_INT schars;             /* the number of characters in the string,
+                                   excluding the terminating null */
+  EMACS_INT bufpos;             /* buffer position of lstring, or 0 if N/A */
+  unsigned from_disp_str : 1;   /* 1 means the string comes from a
+                                   display property */
+  unsigned unibyte : 1;         /* 1 means the string is unibyte */
+};
+
 /* Data type for reordering bidirectional text.  */
 struct bidi_it {
-  EMACS_INT bytepos;            /* iterator's position in buffer */
+  EMACS_INT bytepos;            /* iterator's position in buffer/string */
   EMACS_INT charpos;
   int ch;                       /* character at that position, or u+FFFC
                                    ("object replacement character") for a run
@@ -1852,12 +1864,13 @@ struct bidi_it {
      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 */
+  struct bidi_string_data string;       /* string to reorder */
   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 */
+  unsigned first_elt : 1;       /* if non-zero, examine current char first */
+  unsigned new_paragraph : 1;   /* if non-zero, we expect a new paragraph */
+  unsigned frame_window_p : 1;  /* non-zero if displaying on a GUI frame */
 };
 
 /* Value is non-zero when the bidi iterator is at base paragraph
@@ -2134,6 +2147,10 @@ struct it
      Don't handle some `display' properties in these strings.  */
   unsigned string_from_display_prop_p : 1;
 
+  /* 1 means we are iterating an object that came from a value of a
+     `display' property.  */
+  unsigned from_disp_prop_p : 1;
+
   /* When METHOD == next_element_from_display_vector,
      this is 1 if we're doing an ellipsis.  Otherwise meaningless.  */
   unsigned ellipsis_p : 1;
@@ -2153,7 +2170,9 @@ struct it
   Lisp_Object *dpvec, *dpend;
 
   /* Length in bytes of the char that filled dpvec.  A value of zero
-     means that no such character is involved.  */
+     means that no such character is involved.  A negative value means
+     the rest of the line from the current iterator position onwards
+     is hidden by selective display or ellipsis.  */
   int dpvec_char_len;
 
   /* Face id to use for all characters in display vector.  -1 if unused. */
@@ -2245,10 +2264,13 @@ struct it
     Lisp_Object from_overlay;
     enum glyph_row_area area;
     enum it_method method;
+    bidi_dir_t paragraph_embedding;
     unsigned multibyte_p : 1;
     unsigned string_from_display_prop_p : 1;
     unsigned display_ellipsis_p : 1;
     unsigned avoid_cursor_p : 1;
+    unsigned bidi_p:1;
+    unsigned from_disp_prop_p : 1;
     enum line_wrap_method line_wrap;
 
     /* properties from display property that are reset by another display property. */
@@ -2469,7 +2491,7 @@ struct it
 
   /* Non-zero means we need to reorder bidirectional text for display
      in the visual order.  */
-  int bidi_p;
+  unsigned bidi_p : 1;
 
   /* For iterating over bidirectional text.  */
   struct bidi_it bidi_it;
@@ -2951,6 +2973,10 @@ 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);
+extern void bidi_push_it (struct bidi_it *);
+extern void bidi_pop_it (struct bidi_it *);
+extern void *bidi_shelve_cache (void);
+extern void bidi_unshelve_cache (void *);
 
 /* Defined in xdisp.c */
 
@@ -3008,8 +3034,10 @@ 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);
+extern EMACS_INT compute_display_string_pos (struct text_pos *,
+                                             struct bidi_string_data *, int);
+extern EMACS_INT compute_display_string_end (EMACS_INT,
+                                             struct bidi_string_data *);
 
 #ifdef HAVE_WINDOW_SYSTEM
 
diff --git a/src/dispnew.c b/src/dispnew.c
index d52bbdf1d3e..b2f416701c3 100644
--- a/src/dispnew.c
+++ b/src/dispnew.c
@@ -5243,10 +5243,12 @@ buffer_posn_from_coords (struct window *w, int *x, int *y, struct display_pos *p
   struct image *img = 0;
 #endif
   int x0, x1, to_x;
+  void *itdata = NULL;
 
   /* We used to set current_buffer directly here, but that does the
      wrong thing with `face-remapping-alist' (bug#2044).  */
   Fset_buffer (w->buffer);
+  itdata = bidi_shelve_cache ();
   SET_TEXT_POS_FROM_MARKER (startp, w->start);
   CHARPOS (startp) = min (ZV, max (BEGV, CHARPOS (startp)));
   BYTEPOS (startp) = min (ZV_BYTE, max (BEGV_BYTE, BYTEPOS (startp)));
@@ -5280,6 +5282,7 @@ buffer_posn_from_coords (struct window *w, int *x, int *y, struct display_pos *p
      argument is ZV to prevent move_it_in_display_line from matching
      based on buffer positions.  */
   move_it_in_display_line (&it, ZV, to_x, MOVE_TO_X);
+  bidi_unshelve_cache (itdata);
 
   Fset_buffer (old_current_buffer);
 
diff --git a/src/indent.c b/src/indent.c
index 02eeb7f17d4..c36b83daa02 100644
--- a/src/indent.c
+++ b/src/indent.c
@@ -1989,6 +1989,7 @@ whether or not it is currently displayed in some window.  */)
   struct gcpro gcpro1, gcpro2, gcpro3;
   Lisp_Object lcols = Qnil;
   double cols IF_LINT (= 0);
+  void *itdata = NULL;
 
   /* Allow LINES to be of the form (HPOS . VPOS) aka (COLUMNS . LINES).  */
   if (CONSP (lines) && (NUMBERP (XCAR (lines))))
@@ -2029,6 +2030,7 @@ whether or not it is currently displayed in some window.  */)
       EMACS_INT it_start;
       int first_x, it_overshoot_expected IF_LINT (= 0);
 
+      itdata = bidi_shelve_cache ();
       SET_TEXT_POS (pt, PT, PT_BYTE);
       start_display (&it, w, pt);
       first_x = it.first_visible_x;
@@ -2133,6 +2135,7 @@ whether or not it is currently displayed in some window.  */)
         }
 
       SET_PT_BOTH (IT_CHARPOS (it), IT_BYTEPOS (it));
+      bidi_unshelve_cache (itdata);
     }
 
   if (BUFFERP (old_buffer))
diff --git a/src/keyboard.c b/src/keyboard.c
index 926ebc30b71..7e144b80a09 100644
--- a/src/keyboard.c
+++ b/src/keyboard.c
@@ -10643,7 +10643,8 @@ DEFUN ("recursion-depth", Frecursion_depth, Srecursion_depth, 0, 0, 0,
 DEFUN ("open-dribble-file", Fopen_dribble_file, Sopen_dribble_file, 1, 1,
        "FOpen dribble file: ",
        doc: /* Start writing all keyboard characters to a dribble file called FILE.
-If FILE is nil, close any open dribble file.  */)
+If FILE is nil, close any open dribble file.
+The file will be closed when Emacs exits.  */)
   (Lisp_Object file)
 {
   if (dribble)
diff --git a/src/search.c b/src/search.c
index d29a51c695b..a56df784cd2 100644
--- a/src/search.c
+++ b/src/search.c
@@ -2284,6 +2284,10 @@ The match found must start at or after that position.
 Optional third argument, if t, means if fail just return nil (no error).
   If not nil and not t, move to limit of search and return nil.
 Optional fourth argument is repeat count--search for successive occurrences.
+
+Search case-sensitivity is determined by the value of the variable
+`case-fold-search', which see.
+
 See also the functions `match-beginning', `match-end', `match-string',
 and `replace-match'.  */)
   (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
@@ -2300,6 +2304,10 @@ The match found must not extend after that position.
 Optional third argument, if t, means if fail just return nil (no error).
   If not nil and not t, move to limit of search and return nil.
 Optional fourth argument is repeat count--search for successive occurrences.
+
+Search case-sensitivity is determined by the value of the variable
+`case-fold-search', which see.
+
 See also the functions `match-beginning', `match-end', `match-string',
 and `replace-match'.  */)
   (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
@@ -2319,6 +2327,10 @@ The match found must start at or after that position.
 Optional third argument, if t, means if fail just return nil (no error).
   If not nil and not t, move to limit of search and return nil.
 Optional fourth argument is repeat count--search for successive occurrences.
+
+Search case-sensitivity is determined by the value of the variable
+`case-fold-search', which see.
+
 See also the functions `match-beginning', `match-end', `match-string',
 and `replace-match'.  */)
   (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
@@ -2336,6 +2348,10 @@ The match found must not extend after that position.
 Optional third argument, if t, means if fail just return nil (no error).
   If not nil and not t, move to limit of search and return nil.
 Optional fourth argument is repeat count--search for successive occurrences.
+
+Search case-sensitivity is determined by the value of the variable
+`case-fold-search', which see.
+
 See also the functions `match-beginning', `match-end', `match-string',
 and `replace-match'.  */)
   (Lisp_Object regexp, Lisp_Object bound, Lisp_Object noerror, Lisp_Object count)
diff --git a/src/window.c b/src/window.c
index e390c13dce0..3f5a743f5c6 100644
--- a/src/window.c
+++ b/src/window.c
@@ -1351,6 +1351,7 @@ if it isn't already recorded.  */)
       struct text_pos startp;
       struct it it;
       struct buffer *old_buffer = NULL;
+      void *itdata = NULL;
 
       /* Cannot use Fvertical_motion because that function doesn't
          cope with variable-height lines.  */
@@ -1372,11 +1373,13 @@ if it isn't already recorded.  */)
       else
         SET_TEXT_POS_FROM_MARKER (startp, w->start);
 
+      itdata = bidi_shelve_cache ();
       start_display (&it, w, startp);
       move_it_vertically (&it, window_box_height (w));
       if (it.current_y < it.last_visible_y)
         move_it_past_eol (&it);
       value = make_number (IT_CHARPOS (it));
+      bidi_unshelve_cache (itdata);
 
       if (old_buffer)
         set_buffer_internal (old_buffer);
@@ -4238,6 +4241,7 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
   /* True if we fiddled the window vscroll field without really scrolling.  */
   int vscrolled = 0;
   int x, y, rtop, rbot, rowh, vpos;
+  void *itdata = NULL;
 
   SET_TEXT_POS_FROM_MARKER (start, w->start);
 
@@ -4248,6 +4252,7 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
 
   if (!pos_visible_p (w, PT, &x, &y, &rtop, &rbot, &rowh, &vpos))
     {
+      itdata = bidi_shelve_cache ();
       /* Move backward half the height of the window.  Performance note:
          vmotion used here is about 10% faster, but would give wrong
          results for variable height lines.  */
@@ -4268,6 +4273,7 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
         }
 
       start = it.current.pos;
+      bidi_unshelve_cache (itdata);
     }
   else if (auto_window_vscroll_p)
     {
@@ -4330,6 +4336,7 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
       Fset_window_vscroll (window, make_number (0), Qt);
     }
 
+  itdata = bidi_shelve_cache ();
   /* If scroll_preserve_screen_position is non-nil, we try to set
      point in the same window line as it is now, so get that line.  */
   if (!NILP (Vscroll_preserve_screen_position))
@@ -4408,12 +4415,16 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
                             - it.current_y + it.max_ascent + it.max_descent);
               adjust_glyphs (it.f);
             }
-          else if (noerror)
-            return;
-          else if (n < 0)       /* could happen with empty buffers */
-            xsignal0 (Qbeginning_of_buffer);
           else
-            xsignal0 (Qend_of_buffer);
+            {
+              bidi_unshelve_cache (itdata);
+              if (noerror)
+                return;
+              else if (n < 0)   /* could happen with empty buffers */
+                xsignal0 (Qbeginning_of_buffer);
+              else
+                xsignal0 (Qend_of_buffer);
+            }
         }
       else
         {
@@ -4421,10 +4432,14 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
             /* The first line was only partially visible, make it fully
                visible. */
             w->vscroll = 0;
-          else if (noerror)
-            return;
           else
-            xsignal0 (Qbeginning_of_buffer);
+            {
+              bidi_unshelve_cache (itdata);
+              if (noerror)
+                return;
+              else
+                xsignal0 (Qbeginning_of_buffer);
+            }
         }
 
       /* If control gets here, then we vscrolled.  */
@@ -4568,6 +4583,7 @@ window_scroll_pixel_based (Lisp_Object window, int n, int whole, int noerror)
             SET_PT_BOTH (charpos, bytepos);
         }
     }
+  bidi_unshelve_cache (itdata);
 }
 
 
@@ -4970,6 +4986,7 @@ displayed_window_lines (struct window *w)
   int height = window_box_height (w);
   struct buffer *old_buffer;
   int bottom_y;
+  void *itdata = NULL;
 
   if (XBUFFER (w->buffer) != current_buffer)
     {
@@ -4989,9 +5006,11 @@ displayed_window_lines (struct window *w)
   else
     SET_TEXT_POS_FROM_MARKER (start, w->start);
 
+  itdata = bidi_shelve_cache ();
   start_display (&it, w, start);
   move_it_vertically (&it, height);
   bottom_y = line_bottom_y (&it);
+  bidi_unshelve_cache (itdata);
 
   /* rms: On a non-window display,
      the value of it.vpos at the bottom of the screen
@@ -5090,12 +5109,14 @@ and redisplay normally--don't erase and redraw the frame.  */)
         {
           struct it it;
           struct text_pos pt;
+          void *itdata = bidi_shelve_cache ();
 
           SET_TEXT_POS (pt, PT, PT_BYTE);
           start_display (&it, w, pt);
           move_it_vertically_backward (&it, window_box_height (w) / 2);
           charpos = IT_CHARPOS (it);
           bytepos = IT_BYTEPOS (it);
+          bidi_unshelve_cache (itdata);
         }
       else if (iarg < 0)
         {
@@ -5104,6 +5125,7 @@ and redisplay normally--don't erase and redraw the frame.  */)
           int nlines = -iarg;
           int extra_line_spacing;
           int h = window_box_height (w);
+          void *itdata = bidi_shelve_cache ();
 
           iarg = - max (-iarg, this_scroll_margin);
 
@@ -5141,7 +5163,10 @@ and redisplay normally--don't erase and redraw the frame.  */)
               h -= nlines * (FRAME_LINE_HEIGHT (it.f) + extra_line_spacing);
             }
           if (h <= 0)
-            return Qnil;
+            {
+              bidi_unshelve_cache (itdata);
+              return Qnil;
+            }
 
           /* Now find the new top line (starting position) of the window.  */
           start_display (&it, w, pt);
@@ -5161,6 +5186,8 @@ and redisplay normally--don't erase and redraw the frame.  */)
 
           charpos = IT_CHARPOS (it);
           bytepos = IT_BYTEPOS (it);
+
+          bidi_unshelve_cache (itdata);
         }
       else
         {
diff --git a/src/xdisp.c b/src/xdisp.c
index 123d2fa984c..2aa70d29ff1 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -129,9 +129,13 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
    argument.
 
    Iteration over things to be displayed is then simple.  It is
-   started by initializing an iterator with a call to init_iterator.
-   Calls to get_next_display_element fill the iterator structure with
-   relevant information about the next thing to display.  Calls to
+   started by initializing an iterator with a call to init_iterator,
+   passing it the buffer position where to start iteration.  For
+   iteration over strings, pass -1 as the position to init_iterator,
+   and call reseat_to_string when the string is ready, to initialize
+   the iterator for that string.  Thereafter, calls to
+   get_next_display_element fill the iterator structure with relevant
+   information about the next thing to display.  Calls to
    set_iterator_to_next move the iterator to the next thing.
 
    Besides this, an iterator also contains information about the
@@ -590,6 +594,29 @@ int current_mode_line_height, current_header_line_height;
 
 #define TEXT_PROP_DISTANCE_LIMIT 100
 
+/* SAVE_IT and RESTORE_IT are called when we save a snapshot of the
+   iterator state and later restore it.  This is needed because the
+   bidi iterator on bidi.c keeps a stacked cache of its states, which
+   is really a singleton.  When we use scratch iterator objects to
+   move around the buffer, we can cause the bidi cache to be pushed or
+   popped, and therefore we need to restore the cache state when we
+   return to the original iterator.  */
+#define SAVE_IT(ITCOPY,ITORIG,CACHE)            \
+  do {                                          \
+    if (CACHE)                                  \
+      xfree (CACHE);                            \
+    ITCOPY = ITORIG;                            \
+    CACHE = bidi_shelve_cache();                \
+  } while (0)
+
+#define RESTORE_IT(pITORIG,pITCOPY,CACHE)       \
+  do {                                          \
+    if (pITORIG != pITCOPY)                     \
+      *(pITORIG) = *(pITCOPY);                  \
+    bidi_unshelve_cache (CACHE);                \
+    CACHE = NULL;                               \
+  } while (0)
+
 #if GLYPH_DEBUG
 
 /* Non-zero means print traces of redisplay if compiled with
@@ -1195,6 +1222,7 @@ pos_visible_p (struct window *w, EMACS_INT charpos, int *x, int *y,
                int *rtop, int *rbot, int *rowh, int *vpos)
 {
   struct it it;
+  void *itdata = bidi_shelve_cache ();
   struct text_pos top;
   int visible_p = 0;
   struct buffer *old_buffer = NULL;
@@ -1225,13 +1253,21 @@ pos_visible_p (struct window *w, EMACS_INT charpos, int *x, int *y,
   move_it_to (&it, charpos, -1, it.last_visible_y-1, -1,
               (charpos >= 0 ? MOVE_TO_POS : 0) | MOVE_TO_Y);
 
-  if (charpos >= 0 && IT_CHARPOS (it) >= charpos)
+  if (charpos >= 0
+      && (((!it.bidi_p || it.bidi_it.scan_dir == 1)
+           && IT_CHARPOS (it) >= charpos)
+          /* When scanning backwards under bidi iteration, move_it_to
+             stops at or _before_ CHARPOS, because it stops at or to
+             the _right_ of the character at CHARPOS. */
+          || (it.bidi_p && it.bidi_it.scan_dir == -1
+              && IT_CHARPOS (it) <= charpos)))
     {
       /* We have reached CHARPOS, or passed it.  How the call to
-         move_it_to can overshoot: (i) If CHARPOS is on invisible
-         text, move_it_to stops at the end of the invisible text,
-         after CHARPOS.  (ii) If CHARPOS is in a display vector,
-         move_it_to stops on its last glyph.  */
+         move_it_to can overshoot: (i) If CHARPOS is on invisible text
+         or covered by a display property, move_it_to stops at the end
+         of the invisible text, to the right of CHARPOS.  (ii) If
+         CHARPOS is in a display vector, move_it_to stops on its last
+         glyph.  */
       int top_x = it.current_x;
       int top_y = it.current_y;
       enum it_method it_method = it.method;
@@ -1280,15 +1316,18 @@ pos_visible_p (struct window *w, EMACS_INT charpos, int *x, int *y,
     }
   else
     {
+      /* We were asked to provide info about WINDOW_END.  */
       struct it it2;
+      void *it2data = NULL;
 
-      it2 = it;
+      SAVE_IT (it2, it, it2data);
       if (IT_CHARPOS (it) < ZV && FETCH_BYTE (IT_BYTEPOS (it)) != '\n')
         move_it_by_lines (&it, 1);
       if (charpos < IT_CHARPOS (it)
           || (it.what == IT_EOB && charpos == IT_CHARPOS (it)))
         {
           visible_p = 1;
+          RESTORE_IT (&it2, &it2, it2data);
           move_it_to (&it2, charpos, -1, -1, -1, MOVE_TO_POS);
           *x = it2.current_x;
           *y = it2.current_y + it2.max_ascent - it2.ascent;
@@ -1301,7 +1340,10 @@ pos_visible_p (struct window *w, EMACS_INT charpos, int *x, int *y,
                                   WINDOW_HEADER_LINE_HEIGHT (w))));
           *vpos = it2.vpos;
         }
+      else
+        xfree (it2data);
     }
+  bidi_unshelve_cache (itdata);
 
   if (old_buffer)
     set_buffer_internal_1 (old_buffer);
@@ -2339,6 +2381,10 @@ init_iterator (struct it *it, struct window *w,
   it->base_face_id = remapped_base_face_id;
   it->string = Qnil;
   IT_STRING_CHARPOS (*it) = IT_STRING_BYTEPOS (*it) = -1;
+  it->paragraph_embedding = L2R;
+  it->bidi_it.string.lstring = Qnil;
+  it->bidi_it.string.s = NULL;
+  it->bidi_it.string.bufpos = 0;
 
   /* The window in which we iterate over current_buffer:  */
   XSETWINDOW (it->window, w);
@@ -2395,13 +2441,6 @@ init_iterator (struct it *it, struct window *w,
   /* Are multibyte characters enabled in current_buffer?  */
   it->multibyte_p = !NILP (BVAR (current_buffer, enable_multibyte_characters));
 
-  /* Do we need to reorder bidirectional text?  Not if this is a
-     unibyte buffer: by definition, none of the single-byte characters
-     are strong R2L, so no reordering is needed.  And bidi.c doesn't
-     support unibyte buffers anyway.  */
-  it->bidi_p
-    = !NILP (BVAR (current_buffer, bidi_display_reordering)) && it->multibyte_p;
-
   /* Non-zero if we should highlight the region.  */
   highlight_region_p
     = (!NILP (Vtransient_mark_mode)
@@ -2551,21 +2590,6 @@ init_iterator (struct it *it, struct window *w,
         it->start_of_box_run_p = 1;
     }
 
-  /* If we are to reorder bidirectional text, init the bidi
-     iterator.  */
-  if (it->bidi_p)
-    {
-      /* Note the paragraph direction that this buffer wants to
-         use.  */
-      if (EQ (BVAR (current_buffer, bidi_paragraph_direction), Qleft_to_right))
-        it->paragraph_embedding = L2R;
-      else if (EQ (BVAR (current_buffer, bidi_paragraph_direction), Qright_to_left))
-        it->paragraph_embedding = R2L;
-      else
-        it->paragraph_embedding = NEUTRAL_DIR;
-      bidi_init_it (charpos, bytepos, FRAME_WINDOW_P (it->f), &it->bidi_it);
-    }
-
   /* If a buffer position was specified, set the iterator there,
      getting overlays and face properties from that position.  */
   if (charpos >= BUF_BEG (current_buffer))
@@ -2581,6 +2605,32 @@ init_iterator (struct it *it, struct window *w,
         IT_BYTEPOS (*it) = bytepos;
 
       it->start = it->current;
+      /* Do we need to reorder bidirectional text?  Not if this is a
+         unibyte buffer: by definition, none of the single-byte
+         characters are strong R2L, so no reordering is needed.  And
+         bidi.c doesn't support unibyte buffers anyway.  */
+      it->bidi_p =
+        !NILP (BVAR (current_buffer, bidi_display_reordering))
+        && it->multibyte_p;
+
+      /* If we are to reorder bidirectional text, init the bidi
+         iterator.  */
+      if (it->bidi_p)
+        {
+          /* Note the paragraph direction that this buffer wants to
+             use.  */
+          if (EQ (BVAR (current_buffer, bidi_paragraph_direction),
+                  Qleft_to_right))
+            it->paragraph_embedding = L2R;
+          else if (EQ (BVAR (current_buffer, bidi_paragraph_direction),
+                       Qright_to_left))
+            it->paragraph_embedding = R2L;
+          else
+            it->paragraph_embedding = NEUTRAL_DIR;
+          bidi_unshelve_cache (NULL);
+          bidi_init_it (charpos, IT_BYTEPOS (*it), FRAME_WINDOW_P (it->f),
+                        &it->bidi_it);
+        }
 
       /* Compute faces etc.  */
       reseat (it, it->current.pos, 1);
@@ -2902,6 +2952,7 @@ handle_stop (struct it *it)
                 {
                   it->ignore_overlay_strings_at_pos_p = 1;
                   it->string_from_display_prop_p = 0;
+                  it->from_disp_prop_p = 0;
                   handle_overlay_change_p = 0;
                 }
               handled = HANDLED_RECOMPUTE_PROPS;
@@ -3083,37 +3134,50 @@ 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
+/* Return the character position of a display string at or after
+   position specified by POSITION.  If no display string exists at or
+   after POSITION, 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.  STRING is data about the
+   string to iterate; if STRING->lstring is nil, we are iterating a
+   buffer.  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)
+compute_display_string_pos (struct text_pos *position,
+                            struct bidi_string_data *string, int frame_window_p)
 {
-  /* FIXME: Support display properties on strings (object = Qnil means
-     current buffer).  */
-  Lisp_Object object = Qnil;
+  /* OBJECT = nil means current buffer.  */
+  Lisp_Object object =
+    (string && STRINGP (string->lstring)) ? string->lstring : Qnil;
   Lisp_Object pos, spec;
-  struct text_pos position;
-  EMACS_INT bufpos;
-
-  if (charpos >= ZV)
-    return ZV;
+  int string_p = (string && (STRINGP (string->lstring) || string->s));
+  EMACS_INT eob = string_p ? string->schars : ZV;
+  EMACS_INT begb = string_p ? 0 : BEGV;
+  EMACS_INT bufpos, charpos = CHARPOS (*position);
+  struct text_pos tpos;
+
+  if (charpos >= eob
+      /* We don't support display properties whose values are strings
+         that have display string properties.  */
+      || string->from_disp_str
+      /* C strings cannot have display properties.  */
+      || (string->s && !STRINGP (object)))
+    return eob;
 
   /* 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 (STRINGP (object))
+    bufpos = string->bufpos;
+  else
+    bufpos = charpos;
+  tpos = *position;
   if (!NILP (spec = Fget_char_property (pos, Qdisplay, object))
-      && (charpos <= BEGV
+      && (charpos <= begb
           || !EQ (Fget_char_property (make_number (charpos - 1), Qdisplay,
                                       object),
                   spec))
-      && handle_display_spec (NULL, spec, object, Qnil, &position, bufpos,
+      && handle_display_spec (NULL, spec, object, Qnil, &tpos, bufpos,
                               frame_window_p))
     return charpos;
 
@@ -3121,17 +3185,21 @@ compute_display_string_pos (EMACS_INT charpos, int frame_window_p)
      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)
+    CHARPOS (tpos) = XFASTINT (pos);
+    if (STRINGP (object))
+      BYTEPOS (tpos) = string_char_to_byte (object, CHARPOS (tpos));
+    else
+      BYTEPOS (tpos) = CHAR_TO_BYTE (CHARPOS (tpos));
+    if (CHARPOS (tpos) >= eob)
       break;
     spec = Fget_char_property (pos, Qdisplay, object);
-    bufpos = CHARPOS (position);        /* FIXME! support strings as well */
+    if (!STRINGP (object))
+      bufpos = CHARPOS (tpos);
   } while (NILP (spec)
-           || !handle_display_spec (NULL, spec, object, Qnil, &position, bufpos,
+           || !handle_display_spec (NULL, spec, object, Qnil, &tpos, bufpos,
                                     frame_window_p));
 
-  return CHARPOS (position);
+  return CHARPOS (tpos);
 }
 
 /* Return the character position of the end of the display string that
@@ -3139,15 +3207,17 @@ compute_display_string_pos (EMACS_INT charpos, int frame_window_p)
    `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)
+compute_display_string_end (EMACS_INT charpos, struct bidi_string_data *string)
 {
-  /* FIXME: Support display properties on strings (object = Qnil means
-     current buffer).  */
-  Lisp_Object object = Qnil;
+  /* OBJECT = nil means current buffer.  */
+  Lisp_Object object =
+    (string && STRINGP (string->lstring)) ? string->lstring : Qnil;
   Lisp_Object pos = make_number (charpos);
+  EMACS_INT eob =
+    (STRINGP (object) || (string && string->s)) ? string->schars : ZV;
 
-  if (charpos >= ZV)
-    return ZV;
+  if (charpos >= eob || (string->s && !STRINGP (object)))
+    return eob;
 
   if (NILP (Fget_char_property (pos, Qdisplay, object)))
     abort ();
@@ -3440,21 +3510,23 @@ underlying_face_id (struct it *it)
 
 
 /* Compute the face one character before or after the current position
-   of IT.  BEFORE_P non-zero means get the face in front of IT's
-   position.  Value is the id of the face.  */
+   of IT, in the visual order.  BEFORE_P non-zero means get the face
+   in front (to the left in L2R paragraphs, to the right in R2L
+   paragraphs) of IT's screen position.  Value is the ID of the face.  */
 
 static int
 face_before_or_after_it_pos (struct it *it, int before_p)
 {
   int face_id, limit;
   EMACS_INT next_check_charpos;
-  struct text_pos pos;
+  struct it it_copy;
+  void *it_copy_data = NULL;
 
   xassert (it->s == NULL);
 
   if (STRINGP (it->string))
     {
-      EMACS_INT bufpos;
+      EMACS_INT bufpos, charpos;
       int base_face_id;
 
       /* No face change past the end of the string (for the case
@@ -3464,16 +3536,59 @@ face_before_or_after_it_pos (struct it *it, int before_p)
           || (IT_STRING_CHARPOS (*it) == 0 && before_p))
         return it->face_id;
 
-      /* Set pos to the position before or after IT's current position.  */
-      if (before_p)
-        pos = string_pos (IT_STRING_CHARPOS (*it) - 1, it->string);
+      if (!it->bidi_p)
+        {
+          /* Set charpos to the position before or after IT's current
+             position, in the logical order, which in the non-bidi
+             case is the same as the visual order.  */
+          if (before_p)
+            charpos = IT_STRING_CHARPOS (*it) - 1;
+          else if (it->what == IT_COMPOSITION)
+            /* For composition, we must check the character after the
+               composition.  */
+            charpos = IT_STRING_CHARPOS (*it) + it->cmp_it.nchars;
+          else
+            charpos = IT_STRING_CHARPOS (*it) + 1;
+        }
       else
-        /* For composition, we must check the character after the
-           composition.  */
-        pos = (it->what == IT_COMPOSITION
-               ? string_pos (IT_STRING_CHARPOS (*it)
-                             + it->cmp_it.nchars, it->string)
-               : string_pos (IT_STRING_CHARPOS (*it) + 1, it->string));
+        {
+          if (before_p)
+            {
+              /* With bidi iteration, the character before the current
+                 in the visual order cannot be found by simple
+                 iteration, because "reverse" reordering is not
+                 supported.  Instead, we need to use the move_it_*
+                 family of functions.  */
+              /* Ignore face changes before the first visible
+                 character on this display line.  */
+              if (it->current_x <= it->first_visible_x)
+                return it->face_id;
+              SAVE_IT (it_copy, *it, it_copy_data);
+              /* Implementation note: Since move_it_in_display_line
+                 works in the iterator geometry, and thinks the first
+                 character is always the leftmost, even in R2L lines,
+                 we don't need to distinguish between the R2L and L2R
+                 cases here.  */
+              move_it_in_display_line (&it_copy, SCHARS (it_copy.string),
+                                       it_copy.current_x - 1, MOVE_TO_X);
+              charpos = IT_STRING_CHARPOS (it_copy);
+              RESTORE_IT (it, it, it_copy_data);
+            }
+          else
+            {
+              /* Set charpos to the string position of the character
+                 that comes after IT's current position in the visual
+                 order.  */
+              int n = (it->what == IT_COMPOSITION ? it->cmp_it.nchars : 1);
+
+              it_copy = *it;
+              while (n--)
+                bidi_move_to_visually_next (&it_copy.bidi_it);
+
+              charpos = it_copy.bidi_it.charpos;
+            }
+        }
+      xassert (0 <= charpos && charpos <= SCHARS (it->string));
 
       if (it->current.overlay_string_index >= 0)
         bufpos = IT_CHARPOS (*it);
@@ -3485,7 +3600,7 @@ face_before_or_after_it_pos (struct it *it, int before_p)
       /* Get the face for ASCII, or unibyte.  */
       face_id = face_at_string_position (it->w,
                                          it->string,
-                                         CHARPOS (pos),
+                                         charpos,
                                          bufpos,
                                          it->region_beg_charpos,
                                          it->region_end_charpos,
@@ -3497,16 +3612,19 @@ face_before_or_after_it_pos (struct it *it, int before_p)
          suitable for unibyte text if IT->string is unibyte.  */
       if (STRING_MULTIBYTE (it->string))
         {
-          const unsigned char *p = SDATA (it->string) + BYTEPOS (pos);
+          struct text_pos pos1 = string_pos (charpos, it->string);
+          const unsigned char *p = SDATA (it->string) + BYTEPOS (pos1);
           int c, len;
           struct face *face = FACE_FROM_ID (it->f, face_id);
 
           c = string_char_and_length (p, &len);
-          face_id = FACE_FOR_CHAR (it->f, face, c, CHARPOS (pos), it->string);
+          face_id = FACE_FOR_CHAR (it->f, face, c, charpos, it->string);
         }
     }
   else
     {
+      struct text_pos pos;
+
       if ((IT_CHARPOS (*it) >= ZV && !before_p)
           || (IT_CHARPOS (*it) <= BEGV && before_p))
         return it->face_id;
@@ -3514,17 +3632,63 @@ face_before_or_after_it_pos (struct it *it, int before_p)
       limit = IT_CHARPOS (*it) + TEXT_PROP_DISTANCE_LIMIT;
       pos = it->current.pos;
 
-      if (before_p)
-        DEC_TEXT_POS (pos, it->multibyte_p);
+      if (!it->bidi_p)
+        {
+          if (before_p)
+            DEC_TEXT_POS (pos, it->multibyte_p);
+          else
+            {
+              if (it->what == IT_COMPOSITION)
+                {
+                  /* For composition, we must check the position after
+                     the composition.  */
+                  pos.charpos += it->cmp_it.nchars;
+                  pos.bytepos += it->len;
+                }
+              else
+                INC_TEXT_POS (pos, it->multibyte_p);
+            }
+        }
       else
         {
-          if (it->what == IT_COMPOSITION)
-            /* For composition, we must check the position after the
-               composition.  */
-            pos.charpos += it->cmp_it.nchars, pos.bytepos += it->len;
+          if (before_p)
+            {
+              /* With bidi iteration, the character before the current
+                 in the visual order cannot be found by simple
+                 iteration, because "reverse" reordering is not
+                 supported.  Instead, we need to use the move_it_*
+                 family of functions.  */
+              /* Ignore face changes before the first visible
+                 character on this display line.  */
+              if (it->current_x <= it->first_visible_x)
+                return it->face_id;
+              SAVE_IT (it_copy, *it, it_copy_data);
+              /* Implementation note: Since move_it_in_display_line
+                 works in the iterator geometry, and thinks the first
+                 character is always the leftmost, even in R2L lines,
+                 we don't need to distinguish between the R2L and L2R
+                 cases here.  */
+              move_it_in_display_line (&it_copy, ZV,
+                                       it_copy.current_x - 1, MOVE_TO_X);
+              pos = it_copy.current.pos;
+              RESTORE_IT (it, it, it_copy_data);
+            }
           else
-            INC_TEXT_POS (pos, it->multibyte_p);
+            {
+              /* Set charpos to the buffer position of the character
+                 that comes after IT's current position in the visual
+                 order.  */
+              int n = (it->what == IT_COMPOSITION ? it->cmp_it.nchars : 1);
+
+              it_copy = *it;
+              while (n--)
+                bidi_move_to_visually_next (&it_copy.bidi_it);
+
+              SET_TEXT_POS (pos,
+                            it_copy.bidi_it.charpos, it_copy.bidi_it.bytepos);
+            }
         }
+      xassert (BEGV <= CHARPOS (pos) && CHARPOS (pos) <= ZV);
 
       /* Determine face for CHARSET_ASCII, or unibyte.  */
       face_id = face_at_buffer_position (it->w,
@@ -3575,6 +3739,8 @@ handle_invisible_prop (struct it *it)
       if (!NILP (prop)
           && IT_STRING_CHARPOS (*it) < it->end_charpos)
         {
+          EMACS_INT endpos;
+
           handled = HANDLED_RECOMPUTE_PROPS;
 
           /* Get the position at which the next change of the
@@ -3589,12 +3755,37 @@ handle_invisible_prop (struct it *it)
              change in the property is at position end_charpos.
              Move IT's current position to that position.  */
           if (INTEGERP (end_charpos)
-              && XFASTINT (end_charpos) < XFASTINT (limit))
+              && (endpos = XFASTINT (end_charpos)) < XFASTINT (limit))
             {
               struct text_pos old;
+              EMACS_INT oldpos;
+
               old = it->current.string_pos;
-              IT_STRING_CHARPOS (*it) = XFASTINT (end_charpos);
-              compute_string_pos (&it->current.string_pos, old, it->string);
+              oldpos = CHARPOS (old);
+              if (it->bidi_p)
+                {
+                  if (it->bidi_it.first_elt
+                      && it->bidi_it.charpos < SCHARS (it->string))
+                    bidi_paragraph_init (it->paragraph_embedding,
+                                         &it->bidi_it, 1);
+                  /* Bidi-iterate out of the invisible text.  */
+                  do
+                    {
+                      bidi_move_to_visually_next (&it->bidi_it);
+                    }
+                  while (oldpos <= it->bidi_it.charpos
+                         && it->bidi_it.charpos < endpos);
+
+                  IT_STRING_CHARPOS (*it) = it->bidi_it.charpos;
+                  IT_STRING_BYTEPOS (*it) = it->bidi_it.bytepos;
+                  if (IT_CHARPOS (*it) >= endpos)
+                    it->prev_stop = endpos;
+                }
+              else
+                {
+                  IT_STRING_CHARPOS (*it) = XFASTINT (end_charpos);
+                  compute_string_pos (&it->current.string_pos, old, it->string);
+                }
             }
           else
             {
@@ -4244,6 +4435,7 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
           it->method = GET_FROM_IMAGE;
           it->from_overlay = Qnil;
           it->face_id = face_id;
+          it->from_disp_prop_p = 1;
 
           /* Say that we haven't consumed the characters with
              `display' property yet.  The call to pop_it in
@@ -4316,6 +4508,7 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
          when we are finished with the glyph property value.  */
       push_it (it, position);
       it->from_overlay = overlay;
+      it->from_disp_prop_p = 1;
 
       if (NILP (location))
         it->area = TEXT_AREA;
@@ -4333,12 +4526,34 @@ handle_single_display_spec (struct it *it, Lisp_Object spec, Lisp_Object object,
           it->end_charpos = it->string_nchars = SCHARS (it->string);
           it->method = GET_FROM_STRING;
           it->stop_charpos = 0;
+          it->prev_stop = 0;
+          it->base_level_stop = 0;
           it->string_from_display_prop_p = 1;
           /* 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.  */
           if (BUFFERP (object))
             *position = start_pos;
+
+          /* Force paragraph direction to be that of the parent
+             object.  If the parent object's paragraph direction is
+             not yet determined, default to L2R.  */
+          if (it->bidi_p && it->bidi_it.paragraph_dir == R2L)
+            it->paragraph_embedding = it->bidi_it.paragraph_dir;
+          else
+            it->paragraph_embedding = L2R;
+
+          /* Set up the bidi iterator for this display string.  */
+          if (it->bidi_p)
+            {
+              it->bidi_it.string.lstring = it->string;
+              it->bidi_it.string.s = NULL;
+              it->bidi_it.string.schars = it->end_charpos;
+              it->bidi_it.string.bufpos = bufpos;
+              it->bidi_it.string.from_disp_str = 1;
+              it->bidi_it.string.unibyte = !it->multibyte_p;
+              bidi_init_it (0, 0, FRAME_WINDOW_P (it->f), &it->bidi_it);
+            }
         }
       else if (CONSP (value) && EQ (XCAR (value), Qspace))
         {
@@ -4695,6 +4910,20 @@ next_overlay_string (struct it *it)
       it->stop_charpos = 0;
       if (it->cmp_it.stop_pos >= 0)
         it->cmp_it.stop_pos = 0;
+      it->prev_stop = 0;
+      it->base_level_stop = 0;
+
+      /* Set up the bidi iterator for this overlay string.  */
+      if (it->bidi_p)
+        {
+          it->bidi_it.string.lstring = it->string;
+          it->bidi_it.string.s = NULL;
+          it->bidi_it.string.schars = SCHARS (it->string);
+          it->bidi_it.string.bufpos = it->overlay_strings_charpos;
+          it->bidi_it.string.from_disp_str = it->string_from_display_prop_p;
+          it->bidi_it.string.unibyte = !it->multibyte_p;
+          bidi_init_it (0, 0, FRAME_WINDOW_P (it->f), &it->bidi_it);
+        }
     }
 
   CHECK_IT (it);
@@ -4961,8 +5190,32 @@ get_overlay_strings_1 (struct it *it, EMACS_INT charpos, int compute_stop_p)
       it->stop_charpos = 0;
       xassert (STRINGP (it->string));
       it->end_charpos = SCHARS (it->string);
+      it->prev_stop = 0;
+      it->base_level_stop = 0;
       it->multibyte_p = STRING_MULTIBYTE (it->string);
       it->method = GET_FROM_STRING;
+      it->from_disp_prop_p = 0;
+
+      /* Force paragraph direction to be that of the parent
+         buffer.  */
+      if (it->bidi_p && it->bidi_it.paragraph_dir == R2L)
+        it->paragraph_embedding = it->bidi_it.paragraph_dir;
+      else
+        it->paragraph_embedding = L2R;
+
+      /* Set up the bidi iterator for this overlay string.  */
+      if (it->bidi_p)
+        {
+          EMACS_INT pos = (charpos > 0 ? charpos : IT_CHARPOS (*it));
+
+          it->bidi_it.string.lstring = it->string;
+          it->bidi_it.string.s = NULL;
+          it->bidi_it.string.schars = SCHARS (it->string);
+          it->bidi_it.string.bufpos = pos;
+          it->bidi_it.string.from_disp_str = it->string_from_display_prop_p;
+          it->bidi_it.string.unibyte = !it->multibyte_p;
+          bidi_init_it (0, 0, FRAME_WINDOW_P (it->f), &it->bidi_it);
+        }
       return 1;
     }
 
@@ -5037,19 +5290,30 @@ push_it (struct it *it, struct text_pos *position)
   p->string_from_display_prop_p = it->string_from_display_prop_p;
   p->display_ellipsis_p = 0;
   p->line_wrap = it->line_wrap;
+  p->bidi_p = it->bidi_p;
+  p->paragraph_embedding = it->paragraph_embedding;
+  p->from_disp_prop_p = it->from_disp_prop_p;
   ++it->sp;
+
+  /* Save the state of the bidi iterator as well. */
+  if (it->bidi_p)
+    bidi_push_it (&it->bidi_it);
 }
 
 static void
 iterate_out_of_display_property (struct it *it)
 {
+  int buffer_p = BUFFERP (it->object);
+  EMACS_INT eob = (buffer_p ? ZV : it->end_charpos);
+  EMACS_INT bob = (buffer_p ? BEGV : 0);
+
   /* Maybe initialize paragraph direction.  If we are at the beginning
      of a new paragraph, next_element_from_buffer may not have a
      chance to do that.  */
-  if (it->bidi_it.first_elt && it->bidi_it.charpos < ZV)
+  if (it->bidi_it.first_elt && it->bidi_it.charpos < eob)
     bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, 1);
   /* prev_stop can be zero, so check against BEGV as well.  */
-  while (it->bidi_it.charpos >= BEGV
+  while (it->bidi_it.charpos >= bob
          && it->prev_stop <= it->bidi_it.charpos
          && it->bidi_it.charpos < CHARPOS (it->position))
     bidi_move_to_visually_next (&it->bidi_it);
@@ -5063,7 +5327,10 @@ iterate_out_of_display_property (struct it *it)
     {
       SET_TEXT_POS (it->position,
                     it->bidi_it.charpos, it->bidi_it.bytepos);
-      it->current.pos = it->position;
+      if (buffer_p)
+        it->current.pos = it->position;
+      else
+        it->current.string_pos = it->position;
     }
 }
 
@@ -5077,6 +5344,7 @@ static void
 pop_it (struct it *it)
 {
   struct iterator_stack_entry *p;
+  int from_display_prop = it->from_disp_prop_p;
 
   xassert (it->sp > 0);
   --it->sp;
@@ -5101,22 +5369,10 @@ pop_it (struct it *it)
       it->slice = p->u.image.slice;
       break;
     case GET_FROM_STRETCH:
-      it->object = p->u.comp.object;
+      it->object = p->u.stretch.object;
       break;
     case GET_FROM_BUFFER:
       it->object = it->w->buffer;
-      if (it->bidi_p)
-        {
-          /* Bidi-iterate until we get out of the portion of text, if
-             any, covered by a `display' text property or an overlay
-             with `display' property.  (We cannot just jump there,
-             because the internal coherency of the bidi iterator state
-             can not be preserved across such jumps.)  We also must
-             determine the paragraph base direction if the overlay we
-             just processed is at the beginning of a new
-             paragraph.  */
-          iterate_out_of_display_property (it);
-        }
       break;
     case GET_FROM_STRING:
       it->object = it->string;
@@ -5142,6 +5398,30 @@ pop_it (struct it *it)
   it->voffset = p->voffset;
   it->string_from_display_prop_p = p->string_from_display_prop_p;
   it->line_wrap = p->line_wrap;
+  it->bidi_p = p->bidi_p;
+  it->paragraph_embedding = p->paragraph_embedding;
+  it->from_disp_prop_p = p->from_disp_prop_p;
+  if (it->bidi_p)
+    {
+      bidi_pop_it (&it->bidi_it);
+      /* Bidi-iterate until we get out of the portion of text, if any,
+         covered by a `display' text property or by an overlay with
+         `display' property.  (We cannot just jump there, because the
+         internal coherency of the bidi iterator state can not be
+         preserved across such jumps.)  We also must determine the
+         paragraph base direction if the overlay we just processed is
+         at the beginning of a new paragraph.  */
+      if (from_display_prop
+          && (it->method == GET_FROM_BUFFER || it->method == GET_FROM_STRING))
+        iterate_out_of_display_property (it);
+
+      xassert ((BUFFERP (it->object)
+                && IT_CHARPOS (*it) == it->bidi_it.charpos
+                && IT_BYTEPOS (*it) == it->bidi_it.bytepos)
+               || (STRINGP (it->object)
+                   && IT_STRING_CHARPOS (*it) == it->bidi_it.charpos
+                   && IT_STRING_BYTEPOS (*it) == it->bidi_it.bytepos));
+    }
 }
 
 
@@ -5225,15 +5505,16 @@ forward_to_next_line_start (struct it *it, int *skipped_p)
 
       xassert (!STRINGP (it->string));
 
-      /* If there isn't any `display' property in sight, and no
-         overlays, we can just use the position of the newline in
-         buffer text.  */
-      if (it->stop_charpos >= limit
-          || ((pos = Fnext_single_property_change (make_number (start),
-                                                   Qdisplay,
-                                                   Qnil, make_number (limit)),
-               NILP (pos))
-              && next_overlay_change (start) == ZV))
+      /* If we are not bidi-reordering, and there isn't any `display'
+         property in sight, and no overlays, we can just use the
+         position of the newline in buffer text.  */
+      if (!it->bidi_p
+          && (it->stop_charpos >= limit
+              || ((pos = Fnext_single_property_change (make_number (start),
+                                                       Qdisplay, Qnil,
+                                                       make_number (limit)),
+                   NILP (pos))
+                  && next_overlay_change (start) == ZV)))
         {
           IT_CHARPOS (*it) = limit;
           IT_BYTEPOS (*it) = CHAR_TO_BYTE (limit);
@@ -5291,10 +5572,13 @@ back_to_previous_visible_line_start (struct it *it)
 
       {
         struct it it2;
+        void *it2data = NULL;
         EMACS_INT pos;
         EMACS_INT beg, end;
         Lisp_Object val, overlay;
 
+        SAVE_IT (it2, *it, it2data);
+
         /* If newline is part of a composition, continue from start of composition */
         if (find_composition (IT_CHARPOS (*it), -1, &beg, &end, &val, Qnil)
             && beg < IT_CHARPOS (*it))
@@ -5302,20 +5586,25 @@ back_to_previous_visible_line_start (struct it *it)
 
         /* If newline is replaced by a display property, find start of overlay
            or interval and continue search from that point.  */
-        it2 = *it;
         pos = --IT_CHARPOS (it2);
         --IT_BYTEPOS (it2);
         it2.sp = 0;
+        bidi_unshelve_cache (NULL);
         it2.string_from_display_prop_p = 0;
+        it2.from_disp_prop_p = 0;
         if (handle_display_prop (&it2) == HANDLED_RETURN
             && !NILP (val = get_char_property_and_overlay
                       (make_number (pos), Qdisplay, Qnil, &overlay))
             && (OVERLAYP (overlay)
                 ? (beg = OVERLAY_POSITION (OVERLAY_START (overlay)))
                 : get_property_and_range (pos, Qdisplay, &val, &beg, &end, Qnil)))
-          goto replaced;
+          {
+            RESTORE_IT (it, it, it2data);
+            goto replaced;
+          }
 
         /* Newline is not replaced by anything -- so we are done.  */
+        RESTORE_IT (it, it, it2data);
         break;
 
       replaced:
@@ -5382,14 +5671,29 @@ reseat_at_next_visible_line_start (struct it *it, int on_newline_p)
         {
           if (IT_STRING_CHARPOS (*it) > 0)
             {
-              --IT_STRING_CHARPOS (*it);
-              --IT_STRING_BYTEPOS (*it);
+              if (!it->bidi_p)
+                {
+                  --IT_STRING_CHARPOS (*it);
+                  --IT_STRING_BYTEPOS (*it);
+                }
+              else
+                /* Setting this flag will cause
+                   bidi_move_to_visually_next not to advance, but
+                   instead deliver the current character (newline),
+                   which is what the ON_NEWLINE_P flag wants.  */
+                it->bidi_it.first_elt = 1;
             }
         }
       else if (IT_CHARPOS (*it) > BEGV)
         {
-          --IT_CHARPOS (*it);
-          --IT_BYTEPOS (*it);
+          if (!it->bidi_p)
+            {
+              --IT_CHARPOS (*it);
+              --IT_BYTEPOS (*it);
+            }
+          /* With bidi iteration, the call to `reseat' will cause
+             bidi_move_to_visually_next deliver the current character,
+             the newline, instead of advancing.  */
           reseat (it, it->current.pos, 0);
         }
     }
@@ -5471,19 +5775,24 @@ reseat_1 (struct it *it, struct text_pos pos, int set_stop_p)
   IT_STRING_CHARPOS (*it) = -1;
   IT_STRING_BYTEPOS (*it) = -1;
   it->string = Qnil;
-  it->string_from_display_prop_p = 0;
   it->method = GET_FROM_BUFFER;
   it->object = it->w->buffer;
   it->area = TEXT_AREA;
   it->multibyte_p = !NILP (BVAR (current_buffer, enable_multibyte_characters));
   it->sp = 0;
   it->string_from_display_prop_p = 0;
+  it->from_disp_prop_p = 0;
   it->face_before_selective_p = 0;
   if (it->bidi_p)
     {
-      it->bidi_it.first_elt = 1;
+      bidi_init_it (IT_CHARPOS (*it), IT_BYTEPOS (*it), FRAME_WINDOW_P (it->f),
+                    &it->bidi_it);
+      bidi_unshelve_cache (NULL);
       it->bidi_it.paragraph_dir = NEUTRAL_DIR;
-      it->bidi_it.disp_pos = -1;
+      it->bidi_it.string.s = NULL;
+      it->bidi_it.string.lstring = Qnil;
+      it->bidi_it.string.bufpos = 0;
+      it->bidi_it.string.unibyte = 0;
     }
 
   if (set_stop_p)
@@ -5534,6 +5843,10 @@ reseat_to_string (struct it *it, const char *s, Lisp_Object string,
   if (multibyte >= 0)
     it->multibyte_p = multibyte > 0;
 
+  /* Bidirectional reordering of strings is controlled by the default
+     value of bidi-display-reordering.  */
+  it->bidi_p = !NILP (BVAR (&buffer_defaults, bidi_display_reordering));
+
   if (s == NULL)
     {
       xassert (STRINGP (string));
@@ -5542,6 +5855,18 @@ reseat_to_string (struct it *it, const char *s, Lisp_Object string,
       it->end_charpos = it->string_nchars = SCHARS (string);
       it->method = GET_FROM_STRING;
       it->current.string_pos = string_pos (charpos, string);
+
+      if (it->bidi_p)
+        {
+          it->bidi_it.string.lstring = string;
+          it->bidi_it.string.s = NULL;
+          it->bidi_it.string.schars = it->end_charpos;
+          it->bidi_it.string.bufpos = 0;
+          it->bidi_it.string.from_disp_str = 0;
+          it->bidi_it.string.unibyte = !it->multibyte_p;
+          bidi_init_it (charpos, IT_STRING_BYTEPOS (*it),
+                        FRAME_WINDOW_P (it->f), &it->bidi_it);
+        }
     }
   else
     {
@@ -5562,13 +5887,28 @@ reseat_to_string (struct it *it, const char *s, Lisp_Object string,
           it->end_charpos = it->string_nchars = strlen (s);
         }
 
+      if (it->bidi_p)
+        {
+          it->bidi_it.string.lstring = Qnil;
+          it->bidi_it.string.s = s;
+          it->bidi_it.string.schars = it->end_charpos;
+          it->bidi_it.string.bufpos = 0;
+          it->bidi_it.string.from_disp_str = 0;
+          it->bidi_it.string.unibyte = !it->multibyte_p;
+          bidi_init_it (charpos, IT_BYTEPOS (*it), FRAME_WINDOW_P (it->f),
+                        &it->bidi_it);
+        }
       it->method = GET_FROM_C_STRING;
     }
 
   /* PRECISION > 0 means don't return more than PRECISION characters
      from the string.  */
   if (precision > 0 && it->end_charpos - charpos > precision)
-    it->end_charpos = it->string_nchars = charpos + precision;
+    {
+      it->end_charpos = it->string_nchars = charpos + precision;
+      if (it->bidi_p)
+        it->bidi_it.string.schars = it->end_charpos;
+    }
 
   /* FIELD_WIDTH > 0 means pad with spaces until FIELD_WIDTH
      characters have been returned.  FIELD_WIDTH == 0 means don't pad,
@@ -5576,6 +5916,9 @@ reseat_to_string (struct it *it, const char *s, Lisp_Object string,
      padding with `-' at the end of a mode line.  */
   if (field_width < 0)
     field_width = INFINITY;
+  /* Implementation note: We deliberately don't enlarge
+     it->bidi_it.string.schars here to fit it->end_charpos, because
+     the bidi iterator cannot produce characters out of thin air.  */
   if (field_width > it->end_charpos - charpos)
     it->end_charpos = charpos + field_width;
 
@@ -5584,6 +5927,14 @@ reseat_to_string (struct it *it, const char *s, Lisp_Object string,
     it->dp = XCHAR_TABLE (Vstandard_display_table);
 
   it->stop_charpos = charpos;
+  it->prev_stop = charpos;
+  it->base_level_stop = 0;
+  if (it->bidi_p)
+    {
+      it->bidi_it.first_elt = 1;
+      it->bidi_it.paragraph_dir = NEUTRAL_DIR;
+      it->bidi_it.disp_pos = -1;
+    }
   if (s == NULL && it->multibyte_p)
     {
       EMACS_INT endpos = SCHARS (it->string);
@@ -6218,8 +6569,22 @@ set_iterator_to_next (struct it *it, int reseat_p)
 
     case GET_FROM_C_STRING:
       /* Current display element of IT is from a C string.  */
-      IT_BYTEPOS (*it) += it->len;
-      IT_CHARPOS (*it) += 1;
+      if (!it->bidi_p
+          /* If the string position is beyond string's end, it means
+             next_element_from_c_string is padding the string with
+             blanks, in which case we bypass the bidi iterator,
+             because it cannot deal with such virtual characters.  */
+          || IT_CHARPOS (*it) >= it->bidi_it.string.schars)
+        {
+          IT_BYTEPOS (*it) += it->len;
+          IT_CHARPOS (*it) += 1;
+        }
+      else
+        {
+          bidi_move_to_visually_next (&it->bidi_it);
+          IT_BYTEPOS (*it) = it->bidi_it.bytepos;
+          IT_CHARPOS (*it) = it->bidi_it.charpos;
+        }
       break;
 
     case GET_FROM_DISPLAY_VECTOR:
@@ -6273,23 +6638,95 @@ set_iterator_to_next (struct it *it, int reseat_p)
       xassert (it->s == NULL && STRINGP (it->string));
       if (it->cmp_it.id >= 0)
         {
-          IT_STRING_CHARPOS (*it) += it->cmp_it.nchars;
-          IT_STRING_BYTEPOS (*it) += it->cmp_it.nbytes;
-          if (it->cmp_it.to < it->cmp_it.nglyphs)
-            it->cmp_it.from = it->cmp_it.to;
+          int i;
+
+          if (! it->bidi_p)
+            {
+              IT_STRING_CHARPOS (*it) += it->cmp_it.nchars;
+              IT_STRING_BYTEPOS (*it) += it->cmp_it.nbytes;
+              if (it->cmp_it.to < it->cmp_it.nglyphs)
+                it->cmp_it.from = it->cmp_it.to;
+              else
+                {
+                  it->cmp_it.id = -1;
+                  composition_compute_stop_pos (&it->cmp_it,
+                                                IT_STRING_CHARPOS (*it),
+                                                IT_STRING_BYTEPOS (*it),
+                                                it->end_charpos, it->string);
+                }
+            }
+          else if (! it->cmp_it.reversed_p)
+            {
+              for (i = 0; i < it->cmp_it.nchars; i++)
+                bidi_move_to_visually_next (&it->bidi_it);
+              IT_STRING_BYTEPOS (*it) = it->bidi_it.bytepos;
+              IT_STRING_CHARPOS (*it) = it->bidi_it.charpos;
+
+              if (it->cmp_it.to < it->cmp_it.nglyphs)
+                it->cmp_it.from = it->cmp_it.to;
+              else
+                {
+                  EMACS_INT stop = it->end_charpos;
+                  if (it->bidi_it.scan_dir < 0)
+                    stop = -1;
+                  composition_compute_stop_pos (&it->cmp_it,
+                                                IT_STRING_CHARPOS (*it),
+                                                IT_STRING_BYTEPOS (*it), stop,
+                                                it->string);
+                }
+            }
           else
             {
-              it->cmp_it.id = -1;
-              composition_compute_stop_pos (&it->cmp_it,
-                                            IT_STRING_CHARPOS (*it),
-                                            IT_STRING_BYTEPOS (*it),
-                                            it->end_charpos, it->string);
+              for (i = 0; i < it->cmp_it.nchars; i++)
+                bidi_move_to_visually_next (&it->bidi_it);
+              IT_STRING_BYTEPOS (*it) = it->bidi_it.bytepos;
+              IT_STRING_CHARPOS (*it) = it->bidi_it.charpos;
+              if (it->cmp_it.from > 0)
+                it->cmp_it.to = it->cmp_it.from;
+              else
+                {
+                  EMACS_INT stop = it->end_charpos;
+                  if (it->bidi_it.scan_dir < 0)
+                    stop = -1;
+                  composition_compute_stop_pos (&it->cmp_it,
+                                                IT_STRING_CHARPOS (*it),
+                                                IT_STRING_BYTEPOS (*it), stop,
+                                                it->string);
+                }
             }
         }
       else
         {
-          IT_STRING_BYTEPOS (*it) += it->len;
-          IT_STRING_CHARPOS (*it) += 1;
+          if (!it->bidi_p
+              /* If the string position is beyond string's end, it
+                 means next_element_from_string is padding the string
+                 with blanks, in which case we bypass the bidi
+                 iterator, because it cannot deal with such virtual
+                 characters.  */
+              || IT_STRING_CHARPOS (*it) >= it->bidi_it.string.schars)
+            {
+              IT_STRING_BYTEPOS (*it) += it->len;
+              IT_STRING_CHARPOS (*it) += 1;
+            }
+          else
+            {
+              int prev_scan_dir = it->bidi_it.scan_dir;
+
+              bidi_move_to_visually_next (&it->bidi_it);
+              IT_STRING_BYTEPOS (*it) = it->bidi_it.bytepos;
+              IT_STRING_CHARPOS (*it) = it->bidi_it.charpos;
+              if (prev_scan_dir != it->bidi_it.scan_dir)
+                {
+                  EMACS_INT stop = it->end_charpos;
+
+                  if (it->bidi_it.scan_dir < 0)
+                    stop = -1;
+                  composition_compute_stop_pos (&it->cmp_it,
+                                                IT_STRING_CHARPOS (*it),
+                                                IT_STRING_BYTEPOS (*it), stop,
+                                                it->string);
+                }
+            }
         }
 
     consider_string_end:
@@ -6395,6 +6832,107 @@ next_element_from_display_vector (struct it *it)
   return 1;
 }
 
+/* Get the first element of string/buffer in the visual order, after
+   being reseated to a new position in a string or a buffer.  */
+static void
+get_visually_first_element (struct it *it)
+{
+  int string_p = STRINGP (it->string) || it->s;
+  EMACS_INT eob = (string_p ? it->bidi_it.string.schars : ZV);
+  EMACS_INT bob = (string_p ? 0 : BEGV);
+
+  if (STRINGP (it->string))
+    {
+      it->bidi_it.charpos = IT_STRING_CHARPOS (*it);
+      it->bidi_it.bytepos = IT_STRING_BYTEPOS (*it);
+    }
+  else
+    {
+      it->bidi_it.charpos = IT_CHARPOS (*it);
+      it->bidi_it.bytepos = IT_BYTEPOS (*it);
+    }
+
+  if (it->bidi_it.charpos == eob)
+    {
+      /* Nothing to do, but reset the FIRST_ELT flag, like
+         bidi_paragraph_init does, because we are not going to
+         call it.  */
+      it->bidi_it.first_elt = 0;
+    }
+  else if (it->bidi_it.charpos == bob
+           || (!string_p
+               /* FIXME: Should support all Unicode line separators.  */
+               && (FETCH_CHAR (it->bidi_it.bytepos - 1) == '\n'
+                   || FETCH_CHAR (it->bidi_it.bytepos) == '\n')))
+    {
+      /* If we are at the beginning of a line/string, we can produce
+         the next element right away.  */
+      bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, 1);
+      bidi_move_to_visually_next (&it->bidi_it);
+    }
+  else
+    {
+      EMACS_INT orig_bytepos = it->bidi_it.bytepos;
+
+      /* We need to prime the bidi iterator starting at the line's or
+         string's beginning, before we will be able to produce the
+         next element.  */
+      if (string_p)
+        it->bidi_it.charpos = it->bidi_it.bytepos = 0;
+      else
+        {
+          it->bidi_it.charpos = find_next_newline_no_quit (IT_CHARPOS (*it),
+                                                           -1);
+          it->bidi_it.bytepos = CHAR_TO_BYTE (it->bidi_it.charpos);
+        }
+      bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, 1);
+      do
+        {
+          /* Now return to buffer/string position where we were asked
+             to get the next display element, and produce that.  */
+          bidi_move_to_visually_next (&it->bidi_it);
+        }
+      while (it->bidi_it.bytepos != orig_bytepos
+             && it->bidi_it.charpos < eob);
+    }
+
+  /*  Adjust IT's position information to where we ended up.  */
+  if (STRINGP (it->string))
+    {
+      IT_STRING_CHARPOS (*it) = it->bidi_it.charpos;
+      IT_STRING_BYTEPOS (*it) = it->bidi_it.bytepos;
+    }
+  else
+    {
+      IT_CHARPOS (*it) = it->bidi_it.charpos;
+      IT_BYTEPOS (*it) = it->bidi_it.bytepos;
+    }
+
+  if (STRINGP (it->string) || !it->s)
+    {
+      EMACS_INT stop, charpos, bytepos;
+
+      if (STRINGP (it->string))
+        {
+          xassert (!it->s);
+          stop = SCHARS (it->string);
+          if (stop > it->end_charpos)
+            stop = it->end_charpos;
+          charpos = IT_STRING_CHARPOS (*it);
+          bytepos = IT_STRING_BYTEPOS (*it);
+        }
+      else
+        {
+          stop = it->end_charpos;
+          charpos = IT_CHARPOS (*it);
+          bytepos = IT_BYTEPOS (*it);
+        }
+      if (it->bidi_it.scan_dir < 0)
+        stop = -1;
+      composition_compute_stop_pos (&it->cmp_it, charpos, bytepos, stop,
+                                    it->string);
+    }
+}
 
 /* Load IT with the next display element from Lisp string IT->string.
    IT->current.string_pos is the current position within the string.
@@ -6407,18 +6945,79 @@ next_element_from_string (struct it *it)
   struct text_pos position;
 
   xassert (STRINGP (it->string));
+  xassert (!it->bidi_p || it->string == it->bidi_it.string.lstring);
   xassert (IT_STRING_CHARPOS (*it) >= 0);
   position = it->current.string_pos;
 
+  /* With bidi reordering, the character to display might not be the
+     character at IT_STRING_CHARPOS.  BIDI_IT.FIRST_ELT non-zero means
+     that we were reseat()ed to a new string, whose paragraph
+     direction is not known.  */
+  if (it->bidi_p && it->bidi_it.first_elt)
+    {
+      get_visually_first_element (it);
+      SET_TEXT_POS (position, IT_STRING_CHARPOS (*it), IT_STRING_BYTEPOS (*it));
+    }
+
   /* Time to check for invisible text?  */
-  if (IT_STRING_CHARPOS (*it) < it->end_charpos
-      && IT_STRING_CHARPOS (*it) == it->stop_charpos)
+  if (IT_STRING_CHARPOS (*it) < it->end_charpos)
     {
-      handle_stop (it);
+      if (IT_STRING_CHARPOS (*it) >= it->stop_charpos)
+        {
+          if (!(!it->bidi_p
+                || BIDI_AT_BASE_LEVEL (it->bidi_it)
+                || IT_STRING_CHARPOS (*it) == it->stop_charpos))
+            {
+              /* 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, until we find and handle the last stop_charpos
+                 that precedes our current position.  */
+              handle_stop_backwards (it, it->stop_charpos);
+              return GET_NEXT_DISPLAY_ELEMENT (it);
+            }
+          else
+            {
+              if (it->bidi_p)
+                {
+                  /* Take note of the stop position we just moved
+                     across, for when we will move back across it.  */
+                  it->prev_stop = it->stop_charpos;
+                  /* If we are at base paragraph embedding level, take
+                     note of the last stop position seen at this
+                     level.  */
+                  if (BIDI_AT_BASE_LEVEL (it->bidi_it))
+                    it->base_level_stop = it->stop_charpos;
+                }
+              handle_stop (it);
 
-      /* Since a handler may have changed IT->method, we must
-         recurse here.  */
-      return GET_NEXT_DISPLAY_ELEMENT (it);
+              /* Since a handler may have changed IT->method, we must
+                 recurse here.  */
+              return GET_NEXT_DISPLAY_ELEMENT (it);
+            }
+        }
+      else if (it->bidi_p
+               /* If we are before prev_stop, we may have overstepped
+                  on our way backwards a stop_pos, and if so, we need
+                  to handle that stop_pos.  */
+               && IT_STRING_CHARPOS (*it) < it->prev_stop
+               /* We can sometimes back up for reasons that have nothing
+                  to do with bidi reordering.  E.g., compositions.  The
+                  code below is only needed when we are above the base
+                  embedding level, so test for that explicitly.  */
+               && !BIDI_AT_BASE_LEVEL (it->bidi_it))
+        {
+          /* If we lost track of base_level_stop, we have no better place
+             for handle_stop_backwards to start from than BEGV.  This
+             happens, e.g., when we were reseated to the previous
+             screenful of text by vertical-motion.  */
+          if (it->base_level_stop <= 0
+              || IT_STRING_CHARPOS (*it) < it->base_level_stop)
+            it->base_level_stop = 0;
+          handle_stop_backwards (it, it->base_level_stop);
+          return GET_NEXT_DISPLAY_ELEMENT (it);
+        }
     }
 
   if (it->current.overlay_string_index >= 0)
@@ -6432,7 +7031,10 @@ next_element_from_string (struct it *it)
           return 0;
         }
       else if (CHAR_COMPOSED_P (it, IT_STRING_CHARPOS (*it),
-                                IT_STRING_BYTEPOS (*it), SCHARS (it->string))
+                                IT_STRING_BYTEPOS (*it),
+                                it->bidi_it.scan_dir < 0
+                                ? -1
+                                : SCHARS (it->string))
                && next_element_from_composition (it))
         {
           return 1;
@@ -6467,7 +7069,10 @@ next_element_from_string (struct it *it)
           CHARPOS (position) = BYTEPOS (position) = -1;
         }
       else if (CHAR_COMPOSED_P (it, IT_STRING_CHARPOS (*it),
-                                IT_STRING_BYTEPOS (*it), it->string_nchars)
+                                IT_STRING_BYTEPOS (*it),
+                                it->bidi_it.scan_dir < 0
+                                ? -1
+                                : it->string_nchars)
                && next_element_from_composition (it))
         {
           return 1;
@@ -6506,12 +7111,20 @@ next_element_from_c_string (struct it *it)
   int success_p = 1;
 
   xassert (it->s);
+  xassert (!it->bidi_p || it->s == it->bidi_it.string.s);
   it->what = IT_CHARACTER;
   BYTEPOS (it->position) = CHARPOS (it->position) = 0;
   it->object = Qnil;
 
-  /* IT's position can be greater IT->string_nchars in case a field
-     width or precision has been specified when the iterator was
+  /* With bidi reordering, the character to display might not be the
+     character at IT_CHARPOS.  BIDI_IT.FIRST_ELT non-zero means that
+     we were reseated to a new string, whose paragraph direction is
+     not known.  */
+  if (it->bidi_p && it->bidi_it.first_elt)
+    get_visually_first_element (it);
+
+  /* IT's position can be greater than IT->string_nchars in case a
+     field width or precision has been specified when the iterator was
      initialized.  */
   if (IT_CHARPOS (*it) >= it->end_charpos)
     {
@@ -6586,18 +7199,19 @@ next_element_from_stretch (struct it *it)
   return 1;
 }
 
-/* Scan forward from CHARPOS in the current buffer, until we find a
-   stop position > current IT's position.  Then handle the stop
+/* Scan forward from CHARPOS in the current buffer/string, until we
+   find a stop position > current IT's position.  Then handle the stop
    position before that.  This is called when we bump into a stop
    position while reordering bidirectional text.  CHARPOS should be
-   the last previously processed stop_pos (or BEGV, if none were
+   the last previously processed stop_pos (or BEGV/0, if none were
    processed yet) whose position is less that IT's current
    position.  */
 
 static void
 handle_stop_backwards (struct it *it, EMACS_INT charpos)
 {
-  EMACS_INT where_we_are = IT_CHARPOS (*it);
+  int bufp = !STRINGP (it->string);
+  EMACS_INT where_we_are = (bufp ? IT_CHARPOS (*it) : IT_STRING_CHARPOS (*it));
   struct display_pos save_current = it->current;
   struct text_pos save_position = it->position;
   struct text_pos pos1;
@@ -6608,8 +7222,13 @@ handle_stop_backwards (struct it *it, EMACS_INT charpos)
   do
     {
       it->prev_stop = charpos;
-      SET_TEXT_POS (pos1, charpos, CHAR_TO_BYTE (charpos));
-      reseat_1 (it, pos1, 0);
+      if (bufp)
+        {
+          SET_TEXT_POS (pos1, charpos, CHAR_TO_BYTE (charpos));
+          reseat_1 (it, pos1, 0);
+        }
+      else
+        it->current.string_pos = string_pos (charpos, it->string);
       compute_stop_pos (it);
       /* We must advance forward, right?  */
       if (it->stop_charpos <= it->prev_stop)
@@ -6638,6 +7257,10 @@ next_element_from_buffer (struct it *it)
   int success_p = 1;
 
   xassert (IT_CHARPOS (*it) >= BEGV);
+  xassert (NILP (it->string) && !it->s);
+  xassert (!it->bidi_p
+           || (it->bidi_it.string.lstring == Qnil
+               && it->bidi_it.string.s == NULL));
 
   /* With bidi reordering, the character to display might not be the
      character at IT_CHARPOS.  BIDI_IT.FIRST_ELT non-zero means that
@@ -6645,59 +7268,8 @@ next_element_from_buffer (struct it *it)
      a different paragraph.  */
   if (it->bidi_p && it->bidi_it.first_elt)
     {
-      it->bidi_it.charpos = IT_CHARPOS (*it);
-      it->bidi_it.bytepos = IT_BYTEPOS (*it);
-      if (it->bidi_it.bytepos == ZV_BYTE)
-        {
-          /* Nothing to do, but reset the FIRST_ELT flag, like
-             bidi_paragraph_init does, because we are not going to
-             call it.  */
-          it->bidi_it.first_elt = 0;
-        }
-      else if (it->bidi_it.bytepos == BEGV_BYTE
-          /* FIXME: Should support all Unicode line separators.  */
-          || FETCH_CHAR (it->bidi_it.bytepos - 1) == '\n'
-          || FETCH_CHAR (it->bidi_it.bytepos) == '\n')
-        {
-          /* If we are at the beginning of a line, we can produce the
-             next element right away.  */
-          bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, 1);
-          bidi_move_to_visually_next (&it->bidi_it);
-        }
-      else
-        {
-          EMACS_INT orig_bytepos = IT_BYTEPOS (*it);
-
-          /* We need to prime the bidi iterator starting at the line's
-             beginning, before we will be able to produce the next
-             element.  */
-          IT_CHARPOS (*it) = find_next_newline_no_quit (IT_CHARPOS (*it), -1);
-          IT_BYTEPOS (*it) = CHAR_TO_BYTE (IT_CHARPOS (*it));
-          it->bidi_it.charpos = IT_CHARPOS (*it);
-          it->bidi_it.bytepos = IT_BYTEPOS (*it);
-          bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, 1);
-          do
-            {
-              /* Now return to buffer position where we were asked to
-                 get the next display element, and produce that.  */
-              bidi_move_to_visually_next (&it->bidi_it);
-            }
-          while (it->bidi_it.bytepos != orig_bytepos
-                 && it->bidi_it.bytepos < ZV_BYTE);
-        }
-
-      it->bidi_it.first_elt = 0; /* paranoia: bidi.c does this */
-      /*  Adjust IT's position information to where we ended up.  */
-      IT_CHARPOS (*it) = it->bidi_it.charpos;
-      IT_BYTEPOS (*it) = it->bidi_it.bytepos;
+      get_visually_first_element (it);
       SET_TEXT_POS (it->position, IT_CHARPOS (*it), IT_BYTEPOS (*it));
-      {
-        EMACS_INT stop = it->end_charpos;
-        if (it->bidi_it.scan_dir < 0)
-          stop = -1;
-        composition_compute_stop_pos (&it->cmp_it, IT_CHARPOS (*it),
-                                      IT_BYTEPOS (*it), stop, Qnil);
-      }
     }
 
   if (IT_CHARPOS (*it) >= it->stop_charpos)
@@ -6756,17 +7328,23 @@ next_element_from_buffer (struct it *it)
         }
     }
   else if (it->bidi_p
+           /* If we are before prev_stop, we may have overstepped on
+              our way backwards a stop_pos, and if so, we need to
+              handle that stop_pos.  */
+           && IT_CHARPOS (*it) < it->prev_stop
            /* We can sometimes back up for reasons that have nothing
               to do with bidi reordering.  E.g., compositions.  The
               code below is only needed when we are above the base
               embedding level, so test for that explicitly.  */
-           && !BIDI_AT_BASE_LEVEL (it->bidi_it)
-           && IT_CHARPOS (*it) < it->prev_stop)
-    {
-      if (it->base_level_stop <= 0)
+           && !BIDI_AT_BASE_LEVEL (it->bidi_it))
+    {
+      /* If we lost track of base_level_stop, we have no better place
+         for handle_stop_backwards to start from than BEGV.  This
+         happens, e.g., when we were reseated to the previous
+         screenful of text by vertical-motion.  */
+      if (it->base_level_stop <= 0
+          || IT_CHARPOS (*it) < it->base_level_stop)
         it->base_level_stop = BEGV;
-      if (IT_CHARPOS (*it) < it->base_level_stop)
-        abort ();
       handle_stop_backwards (it, it->base_level_stop);
       return GET_NEXT_DISPLAY_ELEMENT (it);
     }
@@ -6970,9 +7548,11 @@ move_it_in_display_line_to (struct it *it,
   enum move_it_result result = MOVE_UNDEFINED;
   struct glyph_row *saved_glyph_row;
   struct it wrap_it, atpos_it, atx_it;
+  void *wrap_data = NULL, *atpos_data = NULL, *atx_data = NULL;
   int may_wrap = 0;
   enum it_method prev_method = it->method;
   EMACS_INT prev_pos = IT_CHARPOS (*it);
+  int saw_smaller_pos = prev_pos < to_charpos;
 
   /* Don't produce glyphs in produce_glyphs.  */
   saved_glyph_row = it->glyph_row;
@@ -7013,15 +7593,16 @@ move_it_in_display_line_to (struct it *it,
   ((IT)->current_x = x, (IT)->max_ascent = ascent,      \
    (IT)->max_descent = descent)
 
-      /* Stop if we move beyond TO_CHARPOS (after an image or stretch
-         glyph).  */
+      /* Stop if we move beyond TO_CHARPOS (after an image or a
+         display string or stretch glyph).  */
       if ((op & MOVE_TO_POS) != 0
           && BUFFERP (it->object)
           && it->method == GET_FROM_BUFFER
           && ((!it->bidi_p && IT_CHARPOS (*it) > to_charpos)
               || (it->bidi_p
                   && (prev_method == GET_FROM_IMAGE
-                      || prev_method == GET_FROM_STRETCH)
+                      || prev_method == GET_FROM_STRETCH
+                      || prev_method == GET_FROM_STRING)
                   /* Passed TO_CHARPOS from left to right.  */
                   && ((prev_pos < to_charpos
                        && IT_CHARPOS (*it) > to_charpos)
@@ -7038,12 +7619,9 @@ move_it_in_display_line_to (struct it *it,
             /* If wrap_it is valid, the current position might be in a
                word that is wrapped.  So, save the iterator in
                atpos_it and continue to see if wrapping happens.  */
-            atpos_it = *it;
+            SAVE_IT (atpos_it, *it, atpos_data);
         }
 
-      prev_method = it->method;
-      if (it->method == GET_FROM_BUFFER)
-        prev_pos = IT_CHARPOS (*it);
       /* Stop when ZV reached.
          We used to stop here when TO_CHARPOS reached as well, but that is
          too soon if this glyph does not fit on this line.  So we handle it
@@ -7075,18 +7653,18 @@ move_it_in_display_line_to (struct it *it,
                      already found, we are done.  */
                   if (atpos_it.sp >= 0)
                     {
-                      *it = atpos_it;
+                      RESTORE_IT (it, &atpos_it, atpos_data);
                       result = MOVE_POS_MATCH_OR_ZV;
                       goto done;
                     }
                   if (atx_it.sp >= 0)
                     {
-                      *it = atx_it;
+                      RESTORE_IT (it, &atx_it, atx_data);
                       result = MOVE_X_REACHED;
                       goto done;
                     }
                   /* Otherwise, we can wrap here.  */
-                  wrap_it = *it;
+                  SAVE_IT (wrap_it, *it, wrap_data);
                   may_wrap = 0;
                 }
             }
@@ -7107,6 +7685,9 @@ move_it_in_display_line_to (struct it *it,
 
       if (it->area != TEXT_AREA)
         {
+          prev_method = it->method;
+          if (it->method == GET_FROM_BUFFER)
+            prev_pos = IT_CHARPOS (*it);
           set_iterator_to_next (it, 1);
           if (IT_CHARPOS (*it) < CHARPOS (this_line_min_pos))
             SET_TEXT_POS (this_line_min_pos,
@@ -7154,7 +7735,7 @@ move_it_in_display_line_to (struct it *it,
                         goto buffer_pos_reached;
                       if (atpos_it.sp < 0)
                         {
-                          atpos_it = *it;
+                          SAVE_IT (atpos_it, *it, atpos_data);
                           IT_RESET_X_ASCENT_DESCENT (&atpos_it);
                         }
                     }
@@ -7168,7 +7749,7 @@ move_it_in_display_line_to (struct it *it,
                         }
                       if (atx_it.sp < 0)
                         {
-                          atx_it = *it;
+                          SAVE_IT (atx_it, *it, atx_data);
                           IT_RESET_X_ASCENT_DESCENT (&atx_it);
                         }
                     }
@@ -7212,12 +7793,15 @@ move_it_in_display_line_to (struct it *it,
                               if (it->line_wrap == WORD_WRAP
                                   && atpos_it.sp < 0)
                                 {
-                                  atpos_it = *it;
+                                  SAVE_IT (atpos_it, *it, atpos_data);
                                   atpos_it.current_x = x_before_this_char;
                                   atpos_it.hpos = hpos_before_this_char;
                                 }
                             }
 
+                          prev_method = it->method;
+                          if (it->method == GET_FROM_BUFFER)
+                            prev_pos = IT_CHARPOS (*it);
                           set_iterator_to_next (it, 1);
                           if (IT_CHARPOS (*it) < CHARPOS (this_line_min_pos))
                             SET_TEXT_POS (this_line_min_pos,
@@ -7257,7 +7841,7 @@ move_it_in_display_line_to (struct it *it,
 
                   if (wrap_it.sp >= 0)
                     {
-                      *it = wrap_it;
+                      RESTORE_IT (it, &wrap_it, wrap_data);
                       atpos_it.sp = -1;
                       atx_it.sp = -1;
                     }
@@ -7274,7 +7858,7 @@ move_it_in_display_line_to (struct it *it,
                     goto buffer_pos_reached;
                   if (it->line_wrap == WORD_WRAP && atpos_it.sp < 0)
                     {
-                      atpos_it = *it;
+                      SAVE_IT (atpos_it, *it, atpos_data);
                       IT_RESET_X_ASCENT_DESCENT (&atpos_it);
                     }
                 }
@@ -7311,10 +7895,20 @@ move_it_in_display_line_to (struct it *it,
       /* Is this a line end?  If yes, we're done.  */
       if (ITERATOR_AT_END_OF_LINE_P (it))
         {
-          result = MOVE_NEWLINE_OR_CR;
+          /* If we are past TO_CHARPOS, but never saw any character
+             positions smaller than TO_CHARPOS, return
+             MOVE_POS_MATCH_OR_ZV, like the unidirectional display
+             did.  */
+          if ((op & MOVE_TO_POS) != 0
+              && !saw_smaller_pos
+              && IT_CHARPOS (*it) > to_charpos)
+            result = MOVE_POS_MATCH_OR_ZV;
+          else
+            result = MOVE_NEWLINE_OR_CR;
           break;
         }
 
+      prev_method = it->method;
       if (it->method == GET_FROM_BUFFER)
         prev_pos = IT_CHARPOS (*it);
       /* The current display element has been consumed.  Advance
@@ -7322,6 +7916,8 @@ move_it_in_display_line_to (struct it *it,
       set_iterator_to_next (it, 1);
       if (IT_CHARPOS (*it) < CHARPOS (this_line_min_pos))
         SET_TEXT_POS (this_line_min_pos, IT_CHARPOS (*it), IT_BYTEPOS (*it));
+      if (IT_CHARPOS (*it) < to_charpos)
+        saw_smaller_pos = 1;
 
       /* Stop if lines are truncated and IT's current x-position is
          past the right edge of the window now.  */
@@ -7354,12 +7950,19 @@ move_it_in_display_line_to (struct it *it,
   /* If we scanned beyond to_pos and didn't find a point to wrap at,
      restore the saved iterator.  */
   if (atpos_it.sp >= 0)
-    *it = atpos_it;
+    RESTORE_IT (it, &atpos_it, atpos_data);
   else if (atx_it.sp >= 0)
-    *it = atx_it;
+    RESTORE_IT (it, &atx_it, atx_data);
 
  done:
 
+  if (atpos_data)
+    xfree (atpos_data);
+  if (atx_data)
+    xfree (atx_data);
+  if (wrap_data)
+    xfree (wrap_data);
+
   /* Restore the iterator settings altered at the beginning of this
      function.  */
   it->glyph_row = saved_glyph_row;
@@ -7375,8 +7978,12 @@ move_it_in_display_line (struct it *it,
   if (it->line_wrap == WORD_WRAP
       && (op & MOVE_TO_X))
     {
-      struct it save_it = *it;
-      int skip = move_it_in_display_line_to (it, to_charpos, to_x, op);
+      struct it save_it;
+      void *save_data = NULL;
+      int skip;
+
+      SAVE_IT (save_it, *it, save_data);
+      skip = move_it_in_display_line_to (it, to_charpos, to_x, op);
       /* When word-wrap is on, TO_X may lie past the end
          of a wrapped line.  Then it->current is the
          character on the next line, so backtrack to the
@@ -7384,10 +7991,12 @@ move_it_in_display_line (struct it *it,
       if (skip == MOVE_LINE_CONTINUED)
         {
           int prev_x = max (it->current_x - 1, 0);
-          *it = save_it;
+          RESTORE_IT (it, &save_it, save_data);
           move_it_in_display_line_to
             (it, -1, prev_x, MOVE_TO_X);
         }
+      else
+        xfree (save_data);
     }
   else
     move_it_in_display_line_to (it, to_charpos, to_x, op);
@@ -7402,14 +8011,15 @@ move_it_in_display_line (struct it *it,
    description of enum move_operation_enum.
 
    If TO_CHARPOS is in invisible text, e.g. a truncated part of a
-   screen line, this function will set IT to the next position >
-   TO_CHARPOS.  */
+   screen line, this function will set IT to the next position that is
+   displayed to the right of TO_CHARPOS on the screen.  */
 
 void
 move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos, int op)
 {
   enum move_it_result skip, skip2 = MOVE_X_REACHED;
   int line_height, line_start_x = 0, reached = 0;
+  void *backup_data = NULL;
 
   for (;;)
     {
@@ -7462,7 +8072,7 @@ move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos
           struct it it_backup;
 
           if (it->line_wrap == WORD_WRAP)
-            it_backup = *it;
+            SAVE_IT (it_backup, *it, backup_data);
 
           /* TO_Y specified means stop at TO_X in the line containing
              TO_Y---or at TO_CHARPOS if this is reached first.  The
@@ -7496,7 +8106,7 @@ move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos
                   reached = 6;
                   break;
                 }
-              it_backup = *it;
+              SAVE_IT (it_backup, *it, backup_data);
               TRACE_MOVE ((stderr, "move_it: from %d\n", IT_CHARPOS (*it)));
               skip2 = move_it_in_display_line_to (it, to_charpos, -1,
                                                   op & MOVE_TO_POS);
@@ -7510,7 +8120,7 @@ move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos
                   /* If TO_Y is in this line and TO_X was reached
                      above, we scanned too far.  We have to restore
                      IT's settings to the ones before skipping.  */
-                  *it = it_backup;
+                  RESTORE_IT (it, &it_backup, backup_data);
                   reached = 6;
                 }
               else
@@ -7537,7 +8147,7 @@ move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos
                       && it->line_wrap == WORD_WRAP)
                     {
                       int prev_x = max (it->current_x - 1, 0);
-                      *it = it_backup;
+                      RESTORE_IT (it, &it_backup, backup_data);
                       skip = move_it_in_display_line_to
                         (it, -1, prev_x, MOVE_TO_X);
                     }
@@ -7644,6 +8254,9 @@ move_it_to (struct it *it, EMACS_INT to_charpos, int to_x, int to_y, int to_vpos
       last_max_ascent = it->max_ascent;
     }
 
+  if (backup_data)
+    xfree (backup_data);
+
   TRACE_MOVE ((stderr, "move_it_to: reached %d\n", reached));
 }
 
@@ -7661,6 +8274,7 @@ move_it_vertically_backward (struct it *it, int dy)
 {
   int nlines, h;
   struct it it2, it3;
+  void *it2data = NULL, *it3data = NULL;
   EMACS_INT start_pos;
 
  move_further_back:
@@ -7689,7 +8303,7 @@ move_it_vertically_backward (struct it *it, int dy)
      start of the next line so that we get its height.  We need this
      height to be able to tell whether we reached the specified
      y-distance.  */
-  it2 = *it;
+  SAVE_IT (it2, *it, it2data);
   it2.max_ascent = it2.max_descent = 0;
   do
     {
@@ -7698,7 +8312,7 @@ move_it_vertically_backward (struct it *it, int dy)
     }
   while (!IT_POS_VALID_AFTER_MOVE_P (&it2));
   xassert (IT_CHARPOS (*it) >= BEGV);
-  it3 = it2;
+  SAVE_IT (it3, it2, it3data);
 
   move_it_to (&it2, start_pos, -1, -1, -1, MOVE_TO_POS);
   xassert (IT_CHARPOS (*it) >= BEGV);
@@ -7717,8 +8331,10 @@ move_it_vertically_backward (struct it *it, int dy)
     {
       /* DY == 0 means move to the start of the screen line.  The
          value of nlines is > 0 if continuation lines were involved.  */
+      RESTORE_IT (it, it, it2data);
       if (nlines > 0)
         move_it_by_lines (it, nlines);
+      xfree (it3data);
     }
   else
     {
@@ -7726,9 +8342,13 @@ move_it_vertically_backward (struct it *it, int dy)
          Note that H has been subtracted in front of the if-statement.  */
       int target_y = it->current_y + h - dy;
       int y0 = it3.current_y;
-      int y1 = line_bottom_y (&it3);
-      int line_height = y1 - y0;
+      int y1;
+      int line_height;
 
+      RESTORE_IT (&it3, &it3, it3data);
+      y1 = line_bottom_y (&it3);
+      line_height = y1 - y0;
+      RESTORE_IT (it, it, it2data);
       /* If we did not reach target_y, try to move further backward if
          we can.  If we moved too far backward, try to move forward.  */
       if (target_y < it->current_y
@@ -7855,6 +8475,7 @@ move_it_by_lines (struct it *it, int dvpos)
   else
     {
       struct it it2;
+      void *it2data = NULL;
       EMACS_INT start_charpos, i;
 
       /* Start at the beginning of the screen line containing IT's
@@ -7890,7 +8511,7 @@ move_it_by_lines (struct it *it, int dvpos)
 
       /* Above call may have moved too far if continuation lines
          are involved.  Scan forward and see if it did.  */
-      it2 = *it;
+      SAVE_IT (it2, *it, it2data);
       it2.vpos = it2.current_y = 0;
       move_it_to (&it2, start_charpos, -1, -1, -1, MOVE_TO_POS);
       it->vpos -= it2.vpos;
@@ -7901,12 +8522,18 @@ move_it_by_lines (struct it *it, int dvpos)
       if (it2.vpos > -dvpos)
         {
           int delta = it2.vpos + dvpos;
-          it2 = *it;
+
+          RESTORE_IT (&it2, &it2, it2data);
+          SAVE_IT (it2, *it, it2data);
           move_it_to (it, -1, -1, -1, it->vpos + delta, MOVE_TO_VPOS);
           /* Move back again if we got too far ahead.  */
           if (IT_CHARPOS (*it) >= start_charpos)
-            *it = it2;
+            RESTORE_IT (it, &it2, it2data);
+          else
+            xfree (it2data);
         }
+      else
+        RESTORE_IT (it, it, it2data);
     }
 }
 
@@ -10393,7 +11020,7 @@ display_tool_bar_line (struct it *it, int height)
           ++i;
         }
 
-      /* Stop at line ends.  */
+      /* Stop at line end.  */
       if (ITERATOR_AT_END_OF_LINE_P (it))
         break;
 
@@ -10476,6 +11103,7 @@ tool_bar_lines_needed (struct frame *f, int *n_rows)
   it.first_visible_x = 0;
   it.last_visible_x = FRAME_TOTAL_COLS (f) * FRAME_COLUMN_WIDTH (f);
   reseat_to_string (&it, NULL, f->desired_tool_bar_string, 0, 0, 0, -1);
+  it.paragraph_embedding = L2R;
 
   while (!ITERATOR_AT_END_P (&it))
     {
@@ -10558,6 +11186,14 @@ redisplay_tool_bar (struct frame *f)
   /* Build a string that represents the contents of the tool-bar.  */
   build_desired_tool_bar_string (f);
   reseat_to_string (&it, NULL, f->desired_tool_bar_string, 0, 0, 0, -1);
+  /* FIXME: This should be controlled by a user option.  But it
+     doesn't make sense to have an R2L tool bar if the menu bar cannot
+     be drawn also R2L, and making the menu bar R2L is tricky due
+     toolkit-specific code that implements it.  If an R2L tool bar is
+     ever supported, display_tool_bar_line should also be augmented to
+     call unproduce_glyphs like display_line and display_string
+     do.  */
+  it.paragraph_embedding = L2R;
 
   if (f->n_tool_bar_rows == 0)
     {
@@ -13245,14 +13881,18 @@ try_scrolling (Lisp_Object window, int just_this_one_p,
              which was computed as distance from window bottom to
              point.  This matters when lines at window top and lines
              below window bottom have different height.  */
-          struct it it1 = it;
+          struct it it1;
+          void *it1data = NULL;
           /* We use a temporary it1 because line_bottom_y can modify
              its argument, if it moves one line down; see there.  */
-          int start_y = line_bottom_y (&it1);
+          int start_y;
 
+          SAVE_IT (it1, it, it1data);
+          start_y = line_bottom_y (&it1);
           do {
+            RESTORE_IT (&it, &it, it1data);
             move_it_by_lines (&it, 1);
-            it1 = it;
+            SAVE_IT (it1, it, it1data);
           } while (line_bottom_y (&it1) - start_y < amount_to_scroll);
         }
 
@@ -14360,10 +15000,13 @@ redisplay_window (Lisp_Object window, int just_this_one_p)
           && BEGV <= CHARPOS (startp) && CHARPOS (startp) <= ZV)
         {
           struct it it1;
+          void *it1data = NULL;
 
+          SAVE_IT (it1, it, it1data);
           start_display (&it1, w, startp);
           move_it_vertically (&it1, margin);
           margin_pos = IT_CHARPOS (it1);
+          RESTORE_IT (&it, &it, it1data);
         }
       scrolling_up = PT > margin_pos;
       aggressive =
@@ -17229,6 +17872,8 @@ cursor_row_p (struct glyph_row *row)
 static int
 push_display_prop (struct it *it, Lisp_Object prop)
 {
+  xassert (it->method == GET_FROM_BUFFER);
+
   push_it (it, NULL);
 
   if (STRINGP (prop))
@@ -17246,6 +17891,29 @@ push_display_prop (struct it *it, Lisp_Object prop)
       it->end_charpos = it->string_nchars = SCHARS (it->string);
       it->method = GET_FROM_STRING;
       it->stop_charpos = 0;
+      it->prev_stop = 0;
+      it->base_level_stop = 0;
+      it->string_from_display_prop_p = 1;
+      it->from_disp_prop_p = 1;
+
+      /* Force paragraph direction to be that of the parent
+         buffer.  */
+      if (it->bidi_p && it->bidi_it.paragraph_dir == R2L)
+        it->paragraph_embedding = it->bidi_it.paragraph_dir;
+      else
+        it->paragraph_embedding = L2R;
+
+      /* Set up the bidi iterator for this display string.  */
+      if (it->bidi_p)
+        {
+          it->bidi_it.string.lstring = it->string;
+          it->bidi_it.string.s = NULL;
+          it->bidi_it.string.schars = it->end_charpos;
+          it->bidi_it.string.bufpos = IT_CHARPOS (*it);
+          it->bidi_it.string.from_disp_str = 1;
+          it->bidi_it.string.unibyte = !it->multibyte_p;
+          bidi_init_it (0, 0, FRAME_WINDOW_P (it->f), &it->bidi_it);
+        }
     }
   else if (CONSP (prop) && EQ (XCAR (prop), Qspace))
     {
@@ -17292,6 +17960,7 @@ static void
 handle_line_prefix (struct it *it)
 {
   Lisp_Object prefix;
+
   if (it->continuation_lines_width > 0)
     {
       prefix = get_it_property (it, Qwrap_prefix);
@@ -17317,9 +17986,9 @@ handle_line_prefix (struct it *it)
 
 
 /* Remove N glyphs at the start of a reversed IT->glyph_row.  Called
-   only for R2L lines from display_line, when it decides that too many
-   glyphs were produced by PRODUCE_GLYPHS, and the line needs to be
-   continued.  */
+   only for R2L lines from display_line and display_string, when they
+   decide that too many glyphs were produced by PRODUCE_GLYPHS, and
+   the line/string needs to be continued on the next glyph row.  */
 static void
 unproduce_glyphs (struct it *it, int n)
 {
@@ -17349,12 +18018,13 @@ find_row_edges (struct it *it, struct glyph_row *row,
      lines' rows is implemented for bidi-reordered rows.  */
 
   /* ROW->minpos is the value of min_pos, the minimal buffer position
-     we have in ROW.  */
-  if (min_pos <= ZV)
+     we have in ROW, or ROW->start.pos if that is smaller.  */
+  if (min_pos <= ZV && min_pos < row->start.pos.charpos)
     SET_TEXT_POS (row->minpos, min_pos, min_bpos);
   else
-    /* We didn't find _any_ valid buffer positions in any of the
-       glyphs, so we must trust the iterator's computed positions.  */
+    /* We didn't find buffer positions smaller than ROW->start, or
+       didn't find _any_ valid buffer positions in any of the glyphs,
+       so we must trust the iterator's computed positions.  */
       row->minpos = row->start.pos;
   if (max_pos <= 0)
     {
@@ -17429,6 +18099,7 @@ display_line (struct it *it)
   struct glyph_row *row = it->glyph_row;
   Lisp_Object overlay_arrow_string;
   struct it wrap_it;
+  void *wrap_data = NULL;
   int may_wrap = 0, wrap_x IF_LINT (= 0);
   int wrap_row_used = -1;
   int wrap_row_ascent IF_LINT (= 0), wrap_row_height IF_LINT (= 0);
@@ -17583,7 +18254,7 @@ display_line (struct it *it)
                 may_wrap = 1;
               else if (may_wrap)
                 {
-                  wrap_it = *it;
+                  SAVE_IT (wrap_it, *it, wrap_data);
                   wrap_x = x;
                   wrap_row_used = row->used[TEXT_AREA];
                   wrap_row_ascent = row->ascent;
@@ -17753,7 +18424,7 @@ display_line (struct it *it)
                       if (row->reversed_p)
                         unproduce_glyphs (it,
                                           row->used[TEXT_AREA] - wrap_row_used);
-                      *it = wrap_it;
+                      RESTORE_IT (it, &wrap_it, wrap_data);
                       it->continuation_lines_width += wrap_x;
                       row->used[TEXT_AREA] = wrap_row_used;
                       row->ascent = wrap_row_ascent;
@@ -18159,6 +18830,8 @@ See also `bidi-paragraph-direction'.  */)
       itb.charpos = pos;
       itb.bytepos = bytepos;
       itb.nchars = -1;
+      itb.string.s = NULL;
+      itb.string.lstring = Qnil;
       itb.frame_window_p = FRAME_WINDOW_P (SELECTED_FRAME ()); /* guesswork */
       itb.first_elt = 1;
       itb.separator_limit = -1;
@@ -18248,6 +18921,11 @@ display_menu_bar (struct window *w)
     }
 #endif /* not USE_X_TOOLKIT */
 
+  /* FIXME: This should be controlled by a user option.  See the
+     comments in redisplay_tool_bar and display_mode_line about
+     this.  */
+  it.paragraph_embedding = L2R;
+
   if (! mode_line_inverse_video)
     /* Force the menu-bar to be displayed in the default face.  */
     it.base_face_id = it.face_id = DEFAULT_FACE_ID;
@@ -18425,6 +19103,11 @@ display_mode_line (struct window *w, enum face_id face_id, Lisp_Object format)
     /* Force the mode-line to be displayed in the default face.  */
     it.base_face_id = it.face_id = DEFAULT_FACE_ID;
 
+  /* FIXME: This should be controlled by a user option.  But
+     supporting such an option is not trivial, since the mode line is
+     made up of many separate strings.  */
+  it.paragraph_embedding = L2R;
+
   record_unwind_protect (unwind_format_mode_line,
                          format_mode_line_unwind_data (NULL, Qnil, 0));
 
@@ -19970,6 +20653,7 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
   int hpos_at_start = it->hpos;
   int saved_face_id = it->face_id;
   struct glyph_row *row = it->glyph_row;
+  EMACS_INT it_charpos;
 
   /* Initialize the iterator IT for iteration over STRING beginning
      with index START.  */
@@ -19978,10 +20662,10 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
   if (string && STRINGP (lisp_string))
     /* LISP_STRING is the one returned by decode_mode_spec.  We should
        ignore its text properties.  */
-    it->stop_charpos = -1;
+    it->stop_charpos = it->end_charpos;
 
-  /* If displaying STRING, set up the face of the iterator
-     from LISP_STRING, if that's given.  */
+  /* If displaying STRING, set up the face of the iterator from
+     FACE_STRING, if that's given.  */
   if (STRINGP (face_string))
     {
       EMACS_INT endptr;
@@ -20015,6 +20699,11 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
   row->phys_height = it->max_phys_ascent + it->max_phys_descent;
   row->extra_line_spacing = it->max_extra_line_spacing;
 
+  if (STRINGP (it->string))
+    it_charpos = IT_STRING_CHARPOS (*it);
+  else
+    it_charpos = IT_CHARPOS (*it);
+
   /* This condition is for the case that we are called with current_x
      past last_visible_x.  */
   while (it->current_x < max_x)
@@ -20027,10 +20716,10 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
 
       /* Produce glyphs.  */
       x_before = it->current_x;
-      n_glyphs_before = it->glyph_row->used[TEXT_AREA];
+      n_glyphs_before = row->used[TEXT_AREA];
       PRODUCE_GLYPHS (it);
 
-      nglyphs = it->glyph_row->used[TEXT_AREA] - n_glyphs_before;
+      nglyphs = row->used[TEXT_AREA] - n_glyphs_before;
       i = 0;
       x = x_before;
       while (i < nglyphs)
@@ -20044,12 +20733,18 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
               if (CHAR_GLYPH_PADDING_P (*glyph))
                 {
                   /* A wide character is unbreakable.  */
-                  it->glyph_row->used[TEXT_AREA] = n_glyphs_before;
+                  if (row->reversed_p)
+                    unproduce_glyphs (it, row->used[TEXT_AREA]
+                                      - n_glyphs_before);
+                  row->used[TEXT_AREA] = n_glyphs_before;
                   it->current_x = x_before;
                 }
               else
                 {
-                  it->glyph_row->used[TEXT_AREA] = n_glyphs_before + i;
+                  if (row->reversed_p)
+                    unproduce_glyphs (it, row->used[TEXT_AREA]
+                                      - (n_glyphs_before + i));
+                  row->used[TEXT_AREA] = n_glyphs_before + i;
                   it->current_x = x;
                 }
               break;
@@ -20059,7 +20754,7 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
               /* Glyph is at least partially visible.  */
               ++it->hpos;
               if (x < it->first_visible_x)
-                it->glyph_row->x = x - it->first_visible_x;
+                row->x = x - it->first_visible_x;
             }
           else
             {
@@ -20091,6 +20786,10 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
         }
 
       set_iterator_to_next (it, 1);
+      if (STRINGP (it->string))
+        it_charpos = IT_STRING_CHARPOS (*it);
+      else
+        it_charpos = IT_CHARPOS (*it);
 
       /* Stop if truncating at the right edge.  */
       if (it->line_wrap == TRUNCATE
@@ -20098,7 +20797,7 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
         {
           /* Add truncation mark, but don't do it if the line is
              truncated at a padding space.  */
-          if (IT_CHARPOS (*it) < it->string_nchars)
+          if (it_charpos < it->string_nchars)
             {
               if (!FRAME_WINDOW_P (it->f))
                 {
@@ -20106,9 +20805,20 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
 
                   if (it->current_x > it->last_visible_x)
                     {
-                      for (ii = row->used[TEXT_AREA] - 1; ii > 0; --ii)
-                        if (!CHAR_GLYPH_PADDING_P (row->glyphs[TEXT_AREA][ii]))
-                          break;
+                      if (!row->reversed_p)
+                        {
+                          for (ii = row->used[TEXT_AREA] - 1; ii > 0; --ii)
+                            if (!CHAR_GLYPH_PADDING_P (row->glyphs[TEXT_AREA][ii]))
+                              break;
+                        }
+                      else
+                        {
+                          for (ii = 0; ii < row->used[TEXT_AREA]; ii++)
+                            if (!CHAR_GLYPH_PADDING_P (row->glyphs[TEXT_AREA][ii]))
+                              break;
+                          unproduce_glyphs (it, ii + 1);
+                          ii = row->used[TEXT_AREA] - (ii + 1);
+                        }
                       for (n = row->used[TEXT_AREA]; ii < n; ++ii)
                         {
                           row->used[TEXT_AREA] = ii;
@@ -20117,7 +20827,7 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
                     }
                   produce_special_glyphs (it, IT_TRUNCATION);
                 }
-              it->glyph_row->truncated_on_right_p = 1;
+              row->truncated_on_right_p = 1;
             }
           break;
         }
@@ -20125,11 +20835,11 @@ display_string (const char *string, Lisp_Object lisp_string, Lisp_Object face_st
 
   /* Maybe insert a truncation at the left.  */
   if (it->first_visible_x
-      && IT_CHARPOS (*it) > 0)
+      && it_charpos > 0)
     {
       if (!FRAME_WINDOW_P (it->f))
         insert_left_trunc_glyphs (it);
-      it->glyph_row->truncated_on_left_p = 1;
+      row->truncated_on_left_p = 1;
     }
 
   it->face_id = saved_face_id;