Merge branch 'feature/fix-the-long-lines-display-bug'

11 files changed, 153 insertions, 37 deletions

diff --git a/src/buffer.c b/src/buffer.c
index 4994a310438..a55af906e26 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -985,6 +985,7 @@ reset_buffer (register struct buffer *b)
   /* It is more conservative to start out "changed" than "unchanged".  */
   b->clip_changed = 0;
   b->prevent_redisplay_optimizations_p = 1;
+  b->long_line_optimizations_p = 0;
   bset_backed_up (b, Qnil);
   bset_local_minor_modes (b, Qnil);
   BUF_AUTOSAVE_MODIFF (b) = 0;
@@ -1501,7 +1502,7 @@ state of the current buffer.  Use with care.  */)
          decrease SAVE_MODIFF and auto_save_modified or increase
          MODIFF.  */
       if (SAVE_MODIFF >= MODIFF)
-        SAVE_MODIFF = modiff_incr (&MODIFF);
+        SAVE_MODIFF = modiff_incr (&MODIFF, 1);
       if (EQ (flag, Qautosaved))
         BUF_AUTOSAVE_MODIFF (b) = MODIFF;
     }
@@ -2446,6 +2447,7 @@ results, see Info node `(elisp)Swapping Text'.  */)
   swapfield (bidi_paragraph_cache, struct region_cache *);
   current_buffer->prevent_redisplay_optimizations_p = 1;
   other_buffer->prevent_redisplay_optimizations_p = 1;
+  swapfield (long_line_optimizations_p, bool_bf);
   swapfield (overlays_before, struct Lisp_Overlay *);
   swapfield (overlays_after, struct Lisp_Overlay *);
   swapfield (overlay_center, ptrdiff_t);
@@ -2465,12 +2467,12 @@ results, see Info node `(elisp)Swapping Text'.  */)
   bset_point_before_scroll (current_buffer, Qnil);
   bset_point_before_scroll (other_buffer, Qnil);
 
-  modiff_incr (&current_buffer->text->modiff);
-  modiff_incr (&other_buffer->text->modiff);
-  modiff_incr (&current_buffer->text->chars_modiff);
-  modiff_incr (&other_buffer->text->chars_modiff);
-  modiff_incr (&current_buffer->text->overlay_modiff);
-  modiff_incr (&other_buffer->text->overlay_modiff);
+  modiff_incr (&current_buffer->text->modiff, 1);
+  modiff_incr (&other_buffer->text->modiff, 1);
+  modiff_incr (&current_buffer->text->chars_modiff, 1);
+  modiff_incr (&other_buffer->text->chars_modiff, 1);
+  modiff_incr (&current_buffer->text->overlay_modiff, 1);
+  modiff_incr (&other_buffer->text->overlay_modiff, 1);
   current_buffer->text->beg_unchanged = current_buffer->text->gpt;
   current_buffer->text->end_unchanged = current_buffer->text->gpt;
   other_buffer->text->beg_unchanged = other_buffer->text->gpt;
@@ -4009,7 +4011,7 @@ modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
 
   bset_redisplay (buf);
 
-  modiff_incr (&BUF_OVERLAY_MODIFF (buf));
+  modiff_incr (&BUF_OVERLAY_MODIFF (buf), 1);
 }
 
 /* Remove OVERLAY from LIST.  */
@@ -6427,6 +6429,14 @@ Since `clone-indirect-buffer' calls `make-indirect-buffer', this hook
 will run for `clone-indirect-buffer' calls as well.  */);
   Vclone_indirect_buffer_hook = Qnil;
 
+  DEFVAR_LISP ("long-line-threshold", Vlong_line_threshold,
+               doc: /* Line length above which specific display optimizations are used.
+Display optimizations for long lines will automatically be enabled in
+buffers which contain one or more lines whose length is above that
+threshold.
+When nil, these display optimizations are disabled.  */);
+  XSETFASTINT (Vlong_line_threshold, 10000);
+
   defsubr (&Sbuffer_live_p);
   defsubr (&Sbuffer_list);
   defsubr (&Sget_buffer);
diff --git a/src/buffer.h b/src/buffer.h
index 135eaf72d30..47b4bdf749b 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -237,9 +237,10 @@ struct buffer_text
     ptrdiff_t z_byte;           /* Byte pos of end of buffer.  */
     ptrdiff_t gap_size;         /* Size of buffer's gap.  */
     modiff_count modiff;        /* This counts buffer-modification events
-                                   for this buffer.  It is incremented for
-                                   each such event, and never otherwise
-                                   changed.  */
+                                   for this buffer.  It is increased
+                                   logarithmically to the extent of the
+                                   modification for each such event,
+                                   and never otherwise changed.  */
     modiff_count chars_modiff;  /* This is modified with character change
                                    events for this buffer.  It is set to
                                    modiff for each such event, and never
@@ -681,6 +682,10 @@ struct buffer
      defined, as well as by with-temp-buffer, for example.  */
   bool_bf inhibit_buffer_hooks : 1;
 
+  /* Non-zero when the buffer contains long lines and specific
+     display optimizations must be used.  */
+  bool_bf long_line_optimizations_p : 1;
+
   /* List of overlays that end at or before the current center,
      in order of end-position.  */
   struct Lisp_Overlay *overlays_before;
diff --git a/src/composite.c b/src/composite.c
index 2dee42b5503..b04d34337b4 100644
--- a/src/composite.c
+++ b/src/composite.c
@@ -1580,6 +1580,7 @@ find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit, ptrdiff_t backlim,
   Lisp_Object window;
   struct window *w;
   bool need_adjustment = 0;
+  ptrdiff_t narrowed_begv;
 
   window = Fget_buffer_window (Fcurrent_buffer (), Qnil);
   if (NILP (window))
@@ -1596,6 +1597,11 @@ find_automatic_composition (ptrdiff_t pos, ptrdiff_t limit, ptrdiff_t backlim,
         }
       else
         head = backlim;
+      /* In buffers with very long lines, this function becomes very
+         slow.  Pretend that the buffer is narrowed to make it fast.  */
+      narrowed_begv = get_narrowed_begv (w);
+      if (narrowed_begv && pos > narrowed_begv)
+        head = narrowed_begv;
       tail = ZV;
       stop = GPT;
       cur.pos_byte = CHAR_TO_BYTE (cur.pos);
diff --git a/src/dispextern.h b/src/dispextern.h
index 916dba53198..1cdfdca74c0 100644
--- a/src/dispextern.h
+++ b/src/dispextern.h
@@ -2332,6 +2332,10 @@ struct it
      with which display_string was called.  */
   ptrdiff_t end_charpos;
 
+  /* Alternate begin position of the buffer that may be used to
+     optimize display (see the SET_WITH_NARROWED_BEGV macro).  */
+  ptrdiff_t narrowed_begv;
+
   /* C string to iterate over.  Non-null means get characters from
      this string, otherwise characters are read from current_buffer
      or it->string.  */
@@ -3396,6 +3400,7 @@ void mark_window_display_accurate (Lisp_Object, bool);
 void redisplay_preserve_echo_area (int);
 void init_iterator (struct it *, struct window *, ptrdiff_t,
                     ptrdiff_t, struct glyph_row *, enum face_id);
+ptrdiff_t get_narrowed_begv (struct window *w);
 void init_iterator_to_row_start (struct it *, struct window *,
                                  struct glyph_row *);
 void start_display (struct it *, struct window *, struct text_pos);
diff --git a/src/insdel.c b/src/insdel.c
index 9b292398537..38d5fbda002 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -909,7 +909,7 @@ insert_1_both (const char *string,
      the insertion.  This, together with recording the insertion,
      will add up to the right stuff in the undo list.  */
   record_insert (PT, nchars);
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars);
   CHARS_MODIFF = MODIFF;
 
   memcpy (GPT_ADDR, string, nbytes);
@@ -1037,7 +1037,7 @@ insert_from_string_1 (Lisp_Object string, ptrdiff_t pos, ptrdiff_t pos_byte,
 #endif
 
   record_insert (PT, nchars);
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars);
   CHARS_MODIFF = MODIFF;
 
   GAP_SIZE -= outgoing_nbytes;
@@ -1122,7 +1122,7 @@ insert_from_gap (ptrdiff_t nchars, ptrdiff_t nbytes, bool text_at_gap_tail)
      of this dance.  */
   invalidate_buffer_caches (current_buffer, GPT, GPT);
   record_insert (GPT, nchars);
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars);
   CHARS_MODIFF = MODIFF;
 
   insert_from_gap_1 (nchars, nbytes, text_at_gap_tail);
@@ -1251,7 +1251,7 @@ insert_from_buffer_1 (struct buffer *buf,
 #endif
 
   record_insert (PT, nchars);
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars);
   CHARS_MODIFF = MODIFF;
 
   GAP_SIZE -= outgoing_nbytes;
@@ -1352,7 +1352,7 @@ adjust_after_replace (ptrdiff_t from, ptrdiff_t from_byte,
 
   if (len == 0)
     evaporate_overlays (from);
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars_del + len);
   CHARS_MODIFF = MODIFF;
 }
 
@@ -1547,7 +1547,7 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object new,
 
   check_markers ();
 
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars_del + inschars);
   CHARS_MODIFF = MODIFF;
 
   if (adjust_match_data)
@@ -1681,7 +1681,7 @@ replace_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
 
   check_markers ();
 
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars_del + inschars);
   CHARS_MODIFF = MODIFF;
 }
 
@@ -1856,7 +1856,7 @@ del_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
      at the end of the text before the gap.  */
   adjust_markers_for_delete (from, from_byte, to, to_byte);
 
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, nchars_del);
   CHARS_MODIFF = MODIFF;
 
   /* Relocate point as if it were a marker.  */
@@ -1910,7 +1910,7 @@ modify_text (ptrdiff_t start, ptrdiff_t end)
   BUF_COMPUTE_UNCHANGED (current_buffer, start - 1, end);
   if (MODIFF <= SAVE_MODIFF)
     record_first_change ();
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, end - start);
   CHARS_MODIFF = MODIFF;
 
   bset_point_before_scroll (current_buffer, Qnil);
diff --git a/src/lisp.h b/src/lisp.h
index dc496cc1658..2afe135674d 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -3911,10 +3911,14 @@ integer_to_uintmax (Lisp_Object num, uintmax_t *n)
 typedef intmax_t modiff_count;
 
 INLINE modiff_count
-modiff_incr (modiff_count *a)
-{
-  modiff_count a0 = *a;
-  bool modiff_overflow = INT_ADD_WRAPV (a0, 1, a);
+modiff_incr (modiff_count *a, ptrdiff_t len)
+{
+  modiff_count a0 = *a; int incr = len ? 1 : 0;
+  /* Increase the counter more for a large modification and less for a
+     small modification.  Increase it logarithmically to avoid
+     increasing it too much.  */
+  while (len >>= 1) incr++;
+  bool modiff_overflow = INT_ADD_WRAPV (a0, incr, a);
   eassert (!modiff_overflow && *a >> 30 >> 30 == 0);
   return a0;
 }
@@ -4762,6 +4766,8 @@ extern ptrdiff_t fast_c_string_match_ignore_case (Lisp_Object, const char *,
                                                   ptrdiff_t);
 extern ptrdiff_t fast_looking_at (Lisp_Object, ptrdiff_t, ptrdiff_t,
                                   ptrdiff_t, ptrdiff_t, Lisp_Object);
+extern ptrdiff_t find_newline1 (ptrdiff_t, ptrdiff_t, ptrdiff_t, ptrdiff_t,
+                               ptrdiff_t, ptrdiff_t *, ptrdiff_t *, bool);
 extern ptrdiff_t find_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t, ptrdiff_t,
                                ptrdiff_t, ptrdiff_t *, ptrdiff_t *, bool);
 extern void scan_newline (ptrdiff_t, ptrdiff_t, ptrdiff_t, ptrdiff_t,
diff --git a/src/search.c b/src/search.c
index 9d6bd074e1b..b5d6a442c0f 100644
--- a/src/search.c
+++ b/src/search.c
@@ -3192,7 +3192,7 @@ DEFUN ("regexp-quote", Fregexp_quote, Sregexp_quote, 1, 1, 0,
 }
 
 /* Like find_newline, but doesn't use the cache, and only searches forward.  */
-static ptrdiff_t
+ptrdiff_t
 find_newline1 (ptrdiff_t start, ptrdiff_t start_byte, ptrdiff_t end,
                ptrdiff_t end_byte, ptrdiff_t count, ptrdiff_t *counted,
                ptrdiff_t *bytepos, bool allow_quit)
diff --git a/src/textprop.c b/src/textprop.c
index 96d07b44be8..c91a2b729c6 100644
--- a/src/textprop.c
+++ b/src/textprop.c
@@ -88,7 +88,7 @@ modify_text_properties (Lisp_Object buffer, Lisp_Object start, Lisp_Object end)
   BUF_COMPUTE_UNCHANGED (buf, b - 1, e);
   if (MODIFF <= SAVE_MODIFF)
     record_first_change ();
-  modiff_incr (&MODIFF);
+  modiff_incr (&MODIFF, 1);
 
   bset_point_before_scroll (current_buffer, Qnil);
 
diff --git a/src/window.c b/src/window.c
index 10373f8a2bf..8f889585582 100644
--- a/src/window.c
+++ b/src/window.c
@@ -1028,7 +1028,7 @@ window_body_unit_from_symbol (Lisp_Object unit)
 /* Return the number of lines/pixels of W's body.  Don't count any mode
    or header line or horizontal divider of W.  Rounds down to nearest
    integer when not working pixelwise. */
-static int
+int
 window_body_height (struct window *w, enum window_body_unit pixelwise)
 {
   int height = (w->pixel_height
diff --git a/src/window.h b/src/window.h
index 298a80a5366..c63b1b24d4f 100644
--- a/src/window.h
+++ b/src/window.h
@@ -1193,6 +1193,7 @@ enum window_body_unit
     WINDOW_BODY_IN_REMAPPED_CHARS
   };
 extern int window_body_width (struct window *w, enum window_body_unit);
+extern int window_body_height (struct window *w, enum window_body_unit);
 enum margin_unit { MARGIN_IN_LINES, MARGIN_IN_PIXELS };
 extern int window_scroll_margin (struct window *, enum margin_unit);
 extern void temp_output_buffer_show (Lisp_Object);
diff --git a/src/xdisp.c b/src/xdisp.c
index b693df4adb8..ebeaf2a3dab 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -3425,6 +3425,9 @@ init_iterator (struct it *it, struct window *w,
         }
     }
 
+  if (current_buffer->long_line_optimizations_p)
+    it->narrowed_begv = get_narrowed_begv (w);
+
   /* If a buffer position was specified, set the iterator there,
      getting overlays and face properties from that position.  */
   if (charpos >= BUF_BEG (current_buffer))
@@ -3491,6 +3494,45 @@ init_iterator (struct it *it, struct window *w,
   CHECK_IT (it);
 }
 
+/* Compute a suitable alternate value for BEGV that may be used
+   temporarily to optimize display if the buffer in window W contains
+   long lines.  */
+
+ptrdiff_t
+get_narrowed_begv (struct window *w)
+{
+  int len, fact; ptrdiff_t begv;
+  /* In a character-only terminal, only one font size is used, so we
+     can use a smaller factor.  */
+  fact = EQ (Fterminal_live_p (Qnil), Qt) ? 2 : 3;
+  len = fact * (window_body_width (w, WINDOW_BODY_IN_CANONICAL_CHARS) *
+                window_body_height (w, WINDOW_BODY_IN_CANONICAL_CHARS));
+  begv = max ((window_point (w) / len - 1) * len, BEGV);
+  return begv == BEGV ? 0 : begv;
+}
+
+static void
+unwind_narrowed_begv (Lisp_Object point_min)
+{
+  SET_BUF_BEGV (current_buffer, XFIXNUM (point_min));
+}
+
+/* Set DST to EXPR.  When IT indicates that BEGV should temporarily be
+   updated to optimize display, evaluate EXPR with an updated BEGV.  */
+
+#define SET_WITH_NARROWED_BEGV(IT,DST,EXPR)                             \
+  do {                                                                  \
+    if (IT->narrowed_begv)                                              \
+      {                                                                 \
+        specpdl_ref count = SPECPDL_INDEX ();                           \
+        record_unwind_protect (unwind_narrowed_begv, Fpoint_min ());    \
+        SET_BUF_BEGV (current_buffer, IT->narrowed_begv);               \
+        DST = EXPR;                                                     \
+        unbind_to (count, Qnil);                                        \
+      }                                                                 \
+    else                                                                \
+      DST = EXPR;                                                       \
+  } while (0)
 
 /* Initialize IT for the display of window W with window start POS.  */
 
@@ -6992,7 +7034,8 @@ back_to_previous_line_start (struct it *it)
   ptrdiff_t cp = IT_CHARPOS (*it), bp = IT_BYTEPOS (*it);
 
   dec_both (&cp, &bp);
-  IT_CHARPOS (*it) = find_newline_no_quit (cp, bp, -1, &IT_BYTEPOS (*it));
+  SET_WITH_NARROWED_BEGV (it, IT_CHARPOS (*it),
+                          find_newline_no_quit (cp, bp, -1, &IT_BYTEPOS (*it)));
 }
 
 
@@ -7210,7 +7253,8 @@ back_to_previous_visible_line_start (struct it *it)
   it->continuation_lines_width = 0;
 
   eassert (IT_CHARPOS (*it) >= BEGV);
-  eassert (IT_CHARPOS (*it) == BEGV
+  eassert (it->narrowed_begv > BEGV
+           || IT_CHARPOS (*it) == BEGV
            || FETCH_BYTE (IT_BYTEPOS (*it) - 1) == '\n');
   CHECK_IT (it);
 }
@@ -8623,7 +8667,12 @@ get_visually_first_element (struct it *it)
 {
   bool string_p = STRINGP (it->string) || it->s;
   ptrdiff_t eob = (string_p ? it->bidi_it.string.schars : ZV);
-  ptrdiff_t bob = (string_p ? 0 : BEGV);
+  ptrdiff_t bob;
+  ptrdiff_t obegv = BEGV;
+
+  SET_WITH_NARROWED_BEGV (it, bob,
+                          string_p ? 0 :
+                          IT_BYTEPOS (*it) < BEGV ? obegv : BEGV);
 
   if (STRINGP (it->string))
     {
@@ -8663,9 +8712,10 @@ get_visually_first_element (struct it *it)
       if (string_p)
         it->bidi_it.charpos = it->bidi_it.bytepos = 0;
       else
-        it->bidi_it.charpos = find_newline_no_quit (IT_CHARPOS (*it),
-                                                    IT_BYTEPOS (*it), -1,
-                                                    &it->bidi_it.bytepos);
+        SET_WITH_NARROWED_BEGV (it, it->bidi_it.charpos,
+                                find_newline_no_quit (IT_CHARPOS (*it),
+                                                      IT_BYTEPOS (*it), -1,
+                                                      &it->bidi_it.bytepos));
       bidi_paragraph_init (it->paragraph_embedding, &it->bidi_it, true);
       do
         {
@@ -10583,7 +10633,8 @@ move_it_vertically_backward (struct it *it, int dy)
           ptrdiff_t cp = IT_CHARPOS (*it), bp = IT_BYTEPOS (*it);
 
           dec_both (&cp, &bp);
-          cp = find_newline_no_quit (cp, bp, -1, NULL);
+          SET_WITH_NARROWED_BEGV (it, cp,
+                                  find_newline_no_quit (cp, bp, -1, NULL));
           move_it_to (it, cp, -1, -1, -1, MOVE_TO_POS);
         }
       bidi_unshelve_cache (it3data, true);
@@ -18879,11 +18930,25 @@ set_vertical_scroll_bar (struct window *w)
           && NILP (echo_area_buffer[0])))
     {
       struct buffer *buf = XBUFFER (w->contents);
+      ptrdiff_t window_end_pos = w->window_end_pos;
+
+      /* If w->window_end_pos cannot be trusted, recompute it "the
+         hard way".  */
+      if (!w->window_end_valid)
+        {
+          struct it it;
+          struct text_pos start_pos;
+
+          SET_TEXT_POS_FROM_MARKER (start_pos, w->start);
+          start_display (&it, w, start_pos);
+          move_it_to (&it, -1, it.last_visible_x, window_box_height (w), -1,
+                      MOVE_TO_X | MOVE_TO_Y);
+          window_end_pos = BUF_Z (buf) - IT_CHARPOS (it);
+        }
+
       whole = BUF_ZV (buf) - BUF_BEGV (buf);
       start = marker_position (w->start) - BUF_BEGV (buf);
-      /* I don't think this is guaranteed to be right.  For the
-         moment, we'll pretend it is.  */
-      end = BUF_Z (buf) - w->window_end_pos - BUF_BEGV (buf);
+      end = BUF_Z (buf) - window_end_pos - BUF_BEGV (buf);
 
       if (end < start)
         end = start;
@@ -19232,6 +19297,24 @@ redisplay_window (Lisp_Object window, bool just_this_one_p)
         }
     }
 
+  /* Check whether the buffer to be displayed contains long lines.  */
+  if (!NILP (Vlong_line_threshold)
+      && !current_buffer->long_line_optimizations_p
+      && MODIFF - UNCHANGED_MODIFIED > 8)
+    {
+      ptrdiff_t cur, next, found, max = 0, threshold;
+      threshold = XFIXNUM (Vlong_line_threshold);
+      for (cur = 1; cur < Z; cur = next)
+        {
+          next = find_newline1 (cur, CHAR_TO_BYTE (cur), 0, -1, 1,
+                                &found, NULL, true);
+          if (next - cur > max) max = next - cur;
+          if (!found || max > threshold) break;
+        }
+      if (max > threshold)
+        current_buffer->long_line_optimizations_p = true;
+    }
+
   /* If window-start is screwed up, choose a new one.  */
   if (XMARKER (w->start)->buffer != current_buffer)
     goto recenter;