bug#57266: Maintaining the base_line_number cache

[Stefan Monnier]

> All in all, I'd be much happier if you didn't attempt any "cleanups"
> whose value is questionable in this area, only added the missing
> invalidations.  (It is okay to replace identical or similar tests with
> a macro, of course.)

I think the `!just_this_one_p` is important enough since the test isn't
needed, and it otherwise prevents caching the base_line when a buffer is
displayed in more than 1 window, which can slow down redisplay noticeably
in such a case.

I added more comments to explain how the cache works.  It doesn't
explain why we tested `just_this_one_p`, tho, so maybe I'm still
missing something.  The Git history shows this test has been there ever
since 1993 but I haven't seen (nor figured) any explanation for it :-(
My best guess is that the original code basically only tried to be
"clever" when a single window needed refresh and otherwise redid
everything from scratch and that design also applied to the
base_line cache, without thinking too hard about whether it's
truly needed.

>> @@ -4093,6 +4093,8 @@ set_window_buffer (Lisp_Object window, Lisp_Object 
>> buffer,
>>                           buffer);
>>        w->start_at_line_beg = false;
>>        w->force_start = false;
>> +      /* Flush the base_line cache since it applied to another buffer.  */
>> +      w->base_line_number = 0;
>>      }
>
> This is harmless, but IMO unnecessary, because wset_buffer already
> takes care of that, via adjust_window_count.

Indeed, thanks.  In the new patch I moved this from
`adjust_window_count` to `wset_buffer` (otherwise it's always executed
twice in `wset_buffer` and even three times in the other function that
calls `adjust_window_count`, since that one also calls `wset_buffer`).

>> +/* The freshness of the w->base_line_number cache is only ensured at every
>> +   redisplay cycle, so the cache can be used only if there's been
>> +   no relevant changes to the buffer since the last redisplay.  */
>> +#define BASE_LINE_NUMBER_VALID_P(w)                      \
>> +   (eassert (current_buffer == XBUFFER ((w)->contents)), \
>> +    !current_buffer->clip_changed                        \
>> +    && BEG_UNCHANGED < (w)->base_line_number)
>
> The assertion there is unnecessary: instead of using current_buffer,
> you can use XBUFFER ((w)->contents).  It is also safer.

Duh, indeed, thanks.

> Recently I learned that in some corners of redisplay_window, the
> condition
>
>   current_buffer == XBUFFER ((w)->contents)
>
> is not necessarily tru.

Indeed, this happens for example when calling `format-mode-line` from
a buffer different from the window's buffer.

> Also, at least one place where you want to use this macro check
> window_outdated, which this macro doesn't do.  If you know the reason
> why that call is unnecessary, please explain it.

It's not necessary because the only way the cache can be out of date
if when either clipping or buffer text or w->contents is changed and
that is already taken into account.

>>        /* Maybe forget recorded base line for line number display.  */
>> -      if (!just_this_one_p
>> -      || current_buffer->clip_changed
>> -      || BEG_UNCHANGED < CHARPOS (startp))
>> +      /* FIXME: Why do we need this?  `try_scrolling` can only be called 
>> from
>> +         `redisplay_window` which should have flushed this cache already 
>> when
>> +         eeded.  */
>> +      if (!BASE_LINE_NUMBER_VALID_P (w))
>>      w->base_line_number = 0;
>
> About the FIXME: please analyze the control flow inside
> redisplay_window and post your conclusions here, if not include them
> in the log message.

The above code is in `try_scrolling` which is only called by
`redisplay_window` and my patch changes `redisplay_window` so it always
flushes the cache if needed, right from the start, so by the time we get
to `try_scrolling` we know the cache has already been flushed if needed
so this code is redundant.

> Some of the optimizations that redisplay_window attempts early on, if
> they succeed, do "goto done;", bypassing the rest of the code,
> including try_scrolling and whatnot.

The dependency goes the other way around.

>> @@ -20000,12 +20001,6 @@ redisplay_window (Lisp_Object window, bool 
>> just_this_one_p)
>>  
>>        if (w->cursor.vpos >= 0)
>>      {
>> -      if (!just_this_one_p
>> -          || current_buffer->clip_changed
>> -          || BEG_UNCHANGED < CHARPOS (startp))
>> -        /* Forget any recorded base line for line number display.  */
>> -        w->base_line_number = 0;
>
> Sorry, I don't buy your "reason" for removing just_this_one_p.  And
> the deletion itself needs that analysis I mentioned.

Maybe the !just_this_one_p was needed at some point in the past.
Now it's not any more, but I don't know when/where/how that changed.

>> @@ -27949,6 +27947,17 @@ decode_mode_spec (struct window *w, register int c, 
>> int field_width,
>>      startpos = marker_position (w->start);
>>      startpos_byte = marker_byte_position (w->start);
>>      height = WINDOW_TOTAL_LINES (w);
>> +
>> +    if (!BASE_LINE_NUMBER_VALID_P (w))
>
> Here your macro assumes the buffer is current_buffer, whereas the rest
> of the code doesn't.  See my comment about that assertion in the macro.

Indeed, thanks.

>> @@ -27962,8 +27971,6 @@ decode_mode_spec (struct window *w, register int c, 
>> int field_width,
>>        {
>>          startpos = BUF_BEGV (b);
>>          startpos_byte = BUF_BEGV_BYTE (b);
>> -        w->base_line_pos = 0;
>> -        w->base_line_number = 0;
>
> Here you assume that current_buffer->clip_changed detects the
> condition
>
>       if (!(BUF_BEGV_BYTE (b) <= startpos_byte
>             && startpos_byte <= BUF_ZV_BYTE (b)))
>
> But I see no particular reason to think that assumption is always
> valid.

No, the reason those lines are redundant is that the base_line cache is
not affected by startpos: the value stored there is does not depend on startpos.
This said, in my patch I reverted this change because setting `w->base_line_pos 
= 0;`
has another side effect which is to reconsider whether to display line
numbers or not.

>> +        /* NOTE: if current_buffer->clip_changed is set or
>> +               if BEG_UNCHANGED is < position, this new cached value
>> +               may be unusable, because we can't reset BEG_UNCHANGED
>> +               or `clip_changed` from here (since they reflect the
>> +               changes since the last redisplay do they can only be reset
>> +               from `mark_window_display_accurate_1`).  */
>
> The part of the comment in parentheses has some sort of typo, because
> it doesn't parse.

Indeed.  I think it's fixed now.


        Stefan


diff --git a/src/window.c b/src/window.c
index 2bce4c9723d..a6e3ad904f1 100644
--- a/src/window.c
+++ b/src/window.c
@@ -282,9 +282,6 @@ adjust_window_count (struct window *w, int arg)
        b = b->base_buffer;
       b->window_count += arg;
       eassert (b->window_count >= 0);
-      /* These should be recalculated by redisplay code.  */
-      w->window_end_valid = false;
-      w->base_line_pos = 0;
     }
 }
 
@@ -301,6 +298,9 @@ wset_buffer (struct window *w, Lisp_Object val)
     eassert (MARKERP (w->start) && MARKERP (w->pointm));
   w->contents = val;
   adjust_window_count (w, 1);
+  /* These should be recalculated by redisplay code.  */
+  w->window_end_valid = false;
+  w->base_line_pos = 0;
 }
 
 static void
diff --git a/src/xdisp.c b/src/xdisp.c
index 03c43be5bc0..d9052c067f0 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -18341,6 +18341,39 @@ cursor_row_fully_visible_p (struct window *w, bool 
force_p,
    `scroll-conservatively' and the Emacs manual.  */
 #define SCROLL_LIMIT 100
 
+/* The freshness of the w->base_line_number cache is only ensured at every
+   redisplay cycle, so the cache can be used only if there's been
+   no relevant changes to the buffer since the last redisplay.  */
+static bool
+base_line_number_valid_p (struct window *w)
+{
+  /* The base_line cache stores a value which depends on:
+       A. w->contents (AKA `b`)
+       B. BUF_BEGV (b);
+       C. the contents of b->text
+     We flush the cache (in `wset_buffer`) when we set `w->contents`.
+     But for (B) and (C) we don't eagerly flush the cache when those get
+     changed, instead we rely on the `b->clip_changed` bit for (B) and on
+     BUF_BEG_UNCHANGED (b) for (C), and we check them here before making use
+     of the cache.
+     Both of those pieces of info are (re)set by redisplay.  This means that
+     after a modification which invalidates the cache, the cache will stay
+     invalid until the next redisplay, even if we recompute the value anew.
+     Worse: clip_changed and BUF_BEG_UNCHANGED only get reset at the end of a
+     redisplay cycle (after all the windows have been redisplayed), so the
+     base_lines we computed during redisplay are put into the cache
+     at a time when `base_line_number_valid_p` can return false.
+     In order to avoid throwing away this useful info, the cache is flushed
+     as needed at the beginning of redisplay (in `redisplay_window`) so that
+     during redisplay we can presume that the cache is valid (even if
+     `base_line_number_valid_p` is false).
+     It also means we can have a problem if the clipping or the b->text is
+     modified *during* redisplay.  */
+  struct buffer *b = XBUFFER ((w)->contents);
+  return !b->clip_changed
+         && BUF_BEG_UNCHANGED (b) >= (w)->base_line_pos;
+}
+
 static int
 try_scrolling (Lisp_Object window, bool just_this_one_p,
               intmax_t arg_scroll_conservatively, intmax_t scroll_step,
@@ -18639,12 +18672,6 @@ try_scrolling (Lisp_Object window, bool 
just_this_one_p,
     }
   else
     {
-      /* Maybe forget recorded base line for line number display.  */
-      if (!just_this_one_p
-         || current_buffer->clip_changed
-         || BEG_UNCHANGED < CHARPOS (startp))
-       w->base_line_number = 0;
-
       /* If cursor ends up on a partially visible line,
         treat that as being off the bottom of the screen.  */
       if (! cursor_row_fully_visible_p (w, extra_scroll_margin_lines <= 1,
@@ -19404,9 +19431,6 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
   /* Record it now because it's overwritten.  */
   bool current_matrix_up_to_date_p = false;
   bool used_current_matrix_p = false;
-  /* This is less strict than current_matrix_up_to_date_p.
-     It indicates that the buffer contents and narrowing are unchanged.  */
-  bool buffer_unchanged_p = false;
   bool temp_scroll_step = false;
   specpdl_ref count = SPECPDL_INDEX ();
   int rc;
@@ -19447,6 +19471,15 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
        cleverly elsewhere.  */
     w->must_be_updated_p = true;
 
+  if (!base_line_number_valid_p (w))
+    /* Forget any recorded base line for line number display.
+       We do it:
+       - after calling `reconsider_clip_changes` which may discover
+         that the clipping hasn't changed after all.
+       - early enough that we're sure it's done (the code below has
+         various `goto` which could otherwise skip this operation).  */
+    w->base_line_number = 0;
+
   if (MINI_WINDOW_P (w))
     {
       if (w == XWINDOW (echo_area_window)
@@ -19505,11 +19538,6 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
 
   specbind (Qinhibit_point_motion_hooks, Qt);
 
-  buffer_unchanged_p
-    = (w->window_end_valid
-       && !current_buffer->clip_changed
-       && !window_outdated (w));
-
   /* When windows_or_buffers_changed is non-zero, we can't rely
      on the window end being valid, so set it to zero there.  */
   if (windows_or_buffers_changed)
@@ -19668,10 +19696,6 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
       w->preserve_vscroll_p = false;
       w->window_end_valid = false;
 
-      /* Forget any recorded base line for line number display.  */
-      if (!buffer_unchanged_p)
-       w->base_line_number = 0;
-
       /* Redisplay the mode line.  Select the buffer properly for that.
         Also, run the hook window-scroll-functions
         because we have scrolled.  */
@@ -20000,12 +20024,6 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
 
       if (w->cursor.vpos >= 0)
        {
-         if (!just_this_one_p
-             || current_buffer->clip_changed
-             || BEG_UNCHANGED < CHARPOS (startp))
-           /* Forget any recorded base line for line number display.  */
-           w->base_line_number = 0;
-
          if (!cursor_row_fully_visible_p (w, true, false, false))
            {
              clear_glyph_matrix (w->desired_matrix);
@@ -20076,10 +20094,6 @@ redisplay_window (Lisp_Object window, bool 
just_this_one_p)
   debug_method_add (w, "recenter");
 #endif
 
-  /* Forget any previously recorded base line for line number display.  */
-  if (!buffer_unchanged_p)
-    w->base_line_number = 0;
-
   /* Determine the window start relative to point.  */
   init_iterator (&it, w, PT, PT_BYTE, NULL, DEFAULT_FACE_ID);
   it.current_y = it.last_visible_y;
@@ -24211,6 +24225,14 @@ maybe_produce_line_number (struct it *it)
       if (!last_line)
        {
          /* If possible, reuse data cached by line-number-mode.  */
+         /* NOTE: We use `base_line_number` without checking
+            `base_line_number_valid_p` because we assume that
+             `redisplay_window` has already flushed this cache for us when
+             needed.
+            Checking `base_line_number_valid_p` here would be
+            overly pessimistic because it might say that the cache
+            was invalid before entering `redisplay_window` yet the
+            value has just been refreshed.  */
          if (it->w->base_line_number > 0
              && it->w->base_line_pos > 0
              && it->w->base_line_pos <= IT_CHARPOS (*it)
@@ -27523,10 +27545,24 @@ DEFUN ("format-mode-line", Fformat_mode_line, 
Sformat_mode_line,
        = NILP (face) ? Qnil : list2 (Qface, face);
     }
 
+  if (!EQ (buffer, w->contents) || !base_line_number_valid_p (w))
+    /* decode_mode_spec/display_mode_element presume that the base_line
+       cache has been flushed if needed.  They don't flush it themselves,
+       because that could flush a value they just computed, e.g. when
+       %l appears twice in the mode line (or once in the mode line and
+       once in the frame title, ...).  */
+    w->base_line_number = 0;
+
   push_kboard (FRAME_KBOARD (it.f));
   display_mode_element (&it, 0, 0, 0, format, Qnil, false);
   pop_kboard ();
 
+  if (!EQ (buffer, w->contents) || !base_line_number_valid_p (w))
+    /* Flush any new base_line we may have computed while the clipping was
+       changed (or while operating on another buffer), since
+       `reconsider_clip_changes` may reset clip_changes to false later on.  */
+    w->base_line_number = 0;
+
   if (no_props)
     {
       len = MODE_LINE_NOPROP_LEN (string_start);
@@ -28044,6 +28080,12 @@ decode_mode_spec (struct window *w, register int c, 
int field_width,
                goto no_value;
              }
 
+           /* NOTE: if current_buffer->clip_changed is set or
+               if BEG_UNCHANGED is < position, this new cached value
+               may be unusable, because we can't reset BEG_UNCHANGED
+               or `clip_changed` from here (since they reflect the
+               changes since the last redisplay, they can only be reset
+               from `mark_window_display_accurate_1`).  */
            w->base_line_number = topline - nlines;
            w->base_line_pos = BYTE_TO_CHAR (position);
          }