Fix bug #9470 with slow redisplay in huge single-paragraph buffers.

 src/bidi.c (MAX_PARAGRAPH_SEARCH): New macro.
 (bidi_find_paragraph_start): Search back for paragraph beginning
 at most MAX_PARAGRAPH_SEARCH lines; if not found, return BEGV_BYTE.
 (bidi_move_to_visually_next): Only trigger paragraph-related
 computations when the last character is a newline or at EOB, not
 just any NEUTRAL_B.
 src/xdisp.c (reseat_at_next_visible_line_start): Keep information
 about the current paragraph and restore it after the call to
 reseat.

3 files changed, 69 insertions, 4 deletions

diff --git a/src/ChangeLog b/src/ChangeLog
index d09c970bc03..a6d890cd149 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,5 +1,16 @@
 2011-09-17  Eli Zaretskii  <eliz@gnu.org>
 
+        * xdisp.c (reseat_at_next_visible_line_start): Keep information
+        about the current paragraph and restore it after the call to
+        reseat.
+
+        * bidi.c (MAX_PARAGRAPH_SEARCH): New macro.
+        (bidi_find_paragraph_start): Search back for paragraph beginning
+        at most MAX_PARAGRAPH_SEARCH lines; if not found, return BEGV_BYTE.
+        (bidi_move_to_visually_next): Only trigger paragraph-related
+        computations when the last character is a newline or at EOB, not
+        just any NEUTRAL_B.  (Bug#9470)
+
         * xdisp.c (set_cursor_from_row): Don't invoke special treatment of
         truncated lines if point is covered by a display string.  (Bug#9524)
 
diff --git a/src/bidi.c b/src/bidi.c
index bb29647ea88..3efdc1590df 100644
--- a/src/bidi.c
+++ b/src/bidi.c
@@ -1071,15 +1071,25 @@ bidi_at_paragraph_end (EMACS_INT charpos, EMACS_INT bytepos)
   return val;
 }
 
+/* On my 2005-vintage machine, searching back for paragraph start
+   takes ~1 ms per line.  And bidi_paragraph_init is called 4 times
+   when user types C-p.  The number below limits each call to
+   bidi_paragraph_init to about 10 ms.  */
+#define MAX_PARAGRAPH_SEARCH 7500
+
 /* Find the beginning of this paragraph by looking back in the buffer.
-   Value is the byte position of the paragraph's beginning.  */
+   Value is the byte position of the paragraph's beginning, or
+   BEGV_BYTE if paragraph_start_re is still not found after looking
+   back MAX_PARAGRAPH_SEARCH lines in the buffer.  */
 static EMACS_INT
 bidi_find_paragraph_start (EMACS_INT pos, EMACS_INT pos_byte)
 {
   Lisp_Object re = paragraph_start_re;
   EMACS_INT limit = ZV, limit_byte = ZV_BYTE;
+  EMACS_INT n = 0;
 
   while (pos_byte > BEGV_BYTE
+         && n++ < MAX_PARAGRAPH_SEARCH
          && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
     {
       /* FIXME: What if the paragraph beginning is covered by a
@@ -1089,6 +1099,8 @@ bidi_find_paragraph_start (EMACS_INT pos, EMACS_INT pos_byte)
       pos = find_next_newline_no_quit (pos - 1, -1);
       pos_byte = CHAR_TO_BYTE (pos);
     }
+  if (n >= MAX_PARAGRAPH_SEARCH)
+    pos_byte = BEGV_BYTE;
   return pos_byte;
 }
 
@@ -2239,7 +2251,8 @@ bidi_move_to_visually_next (struct bidi_it *bidi_it)
     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)
+  if (!bidi_it->first_elt
+      && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
     bidi_line_init (bidi_it);
 
   /* Prepare the sentinel iterator state, and cache it.  When we bump
@@ -2320,7 +2333,8 @@ 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)
+  if (bidi_it->scan_dir == 1
+      && (bidi_it->ch == '\n' || bidi_it->ch == BIDI_EOB))
     {
       /* The paragraph direction of the entire string, once
          determined, is in effect for the entire string.  Setting the
diff --git a/src/xdisp.c b/src/xdisp.c
index 864734d4b20..3cb9f301bb2 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -5722,6 +5722,9 @@ reseat_at_next_visible_line_start (struct it *it, int on_newline_p)
 {
   int newline_found_p, skipped_p = 0;
   struct bidi_it bidi_it_prev;
+  int new_paragraph, first_elt, disp_prop;
+  EMACS_INT paragraph_end, disp_pos;
+  bidi_dir_t paragraph_dir;
 
   newline_found_p = forward_to_next_line_start (it, &skipped_p, &bidi_it_prev);
 
@@ -5738,6 +5741,23 @@ reseat_at_next_visible_line_start (struct it *it, int on_newline_p)
           forward_to_next_line_start (it, &skipped_p, &bidi_it_prev);
       }
 
+  /* Under bidi iteration, save the attributes of the paragraph we are
+     in, to be restored after the call to `reseat' below.  That's
+     because `reseat' overwrites them, which requires unneeded and
+     potentially expensive backward search for paragraph beginning.
+     This search is unnecessary because we will be `reseat'ed to the
+     same position where we are now, for which we already have all the
+     information we need in the bidi iterator.  */
+  if (it->bidi_p && !STRINGP (it->string))
+    {
+      new_paragraph = it->bidi_it.new_paragraph;
+      first_elt = it->bidi_it.first_elt;
+      paragraph_end = it->bidi_it.separator_limit;
+      paragraph_dir = it->bidi_it.paragraph_dir;
+      disp_pos = it->bidi_it.disp_pos;
+      disp_prop = it->bidi_it.disp_prop;
+    }
+
   /* Position on the newline if that's what's requested.  */
   if (on_newline_p && newline_found_p)
     {
@@ -5777,10 +5797,30 @@ reseat_at_next_visible_line_start (struct it *it, int on_newline_p)
               IT_BYTEPOS (*it) = it->bidi_it.bytepos;
             }
           reseat (it, it->current.pos, 0);
+          if (it->bidi_p)
+            {
+              it->bidi_it.new_paragraph = new_paragraph;
+              it->bidi_it.first_elt = first_elt;
+              it->bidi_it.separator_limit = paragraph_end;
+              it->bidi_it.paragraph_dir = paragraph_dir;
+              it->bidi_it.disp_pos = disp_pos;
+              it->bidi_it.disp_prop = disp_prop;
+            }
         }
     }
   else if (skipped_p)
-    reseat (it, it->current.pos, 0);
+    {
+      reseat (it, it->current.pos, 0);
+      if (it->bidi_p)
+        {
+          it->bidi_it.new_paragraph = new_paragraph;
+          it->bidi_it.first_elt = first_elt;
+          it->bidi_it.separator_limit = paragraph_end;
+          it->bidi_it.paragraph_dir = paragraph_dir;
+          it->bidi_it.disp_pos = disp_pos;
+          it->bidi_it.disp_prop = disp_prop;
+        }
+    }
 
   CHECK_IT (it);
 }