Subject: bug#76538: 31.0.50; 31.0.50; 31.0.50; feature/igc: using magit-section-cycle-global (S-TAB) and magit-section-toggle (TAB) in some random ways blocks GNU Emacs.

From: Pip Cet <[email-masked]>
Date: Fri, 28 Feb 2025 16:07:18 +0000

On Friday, February 28th, 2025 at 08:19, Eli Zaretskii <[email-masked]> wrote:
> > From: Gerd Möllmann [email-masked]
> 
> > Cc: Ihor Radchenko [email-masked], Eli Zaretskii [email-masked],
> > [email-masked], [email-masked], [email-masked],
> > [email-masked]
> > Date: Fri, 28 Feb 2025 06:19:34 +0100
> > 
> > Gerd Möllmann [email-masked] writes:
> > 
> > > In any case, I think I would try to change DO_MARKERS to start at the
> > > end of the marker vector. If fix_marker_vector runs often enough one
> > > could also "straighten" the free-list there, maybe.
> > 
> > Or one could build a doubly-linked list of markers in most-recently
> > created order. But that would mean 3 array slots per marker in the
> > marker vector. Don't know.
> 
> How about not relying on buffer markers too much for this job? And in
> particular, not adding any ephemeral markers when we don't find a
> close-enough existing marker? We could instead build our own data
> structure, and make it so we could use efficient search methods.

I can't really contribute much to the general discussion, but, if I understand correctly, in this specific case the problem is that magit causes redisplay to skip over a large invisible region, finding each newline in it, calculating its charpos, then advancing to the next one because the newline is invisible.

So I've tried applying the attached patch, and that seems to avoid the specific problem here: we simply skip to the beginning of the invisible region, which means only one charpos<->bytepos lookup for the entire region, and it doesn't matter too much that it's a slow one.

Of course there are still problems caused by the heuristic nature of the charpos<->bytepos caching mechanism, which simply doesn't have very good worst-time complexity, but I think the right solution there is to continue working on storing buffer text in a number of chunks (and saving the correct bytepos/charpos change for each chunk).  I have some code for that and I'd rather continue working on it for a while before giving up and spending time on different implementations of the marker array.  That would give us predictable and acceptable worst-case performance, I think, and we wouldn't need to go out hunting for use cases that come close to the worst case.

Pip

diff --git a/src/xdisp.c b/src/xdisp.c
index 17e320079d4..c6ca56f6527 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -7693,7 +7693,19 @@ back_to_previous_visible_line_start (struct it *it)
 	prop = Fget_char_property (make_fixnum (IT_CHARPOS (*it) - 1),
 				   Qinvisible, it->window);
 	if (TEXT_PROP_MEANS_INVISIBLE (prop) != 0)
-	  continue;
+	  {
+	    Lisp_Object charpos =
+	      Fprevious_single_char_property_change (make_fixnum (IT_CHARPOS (*it) - 1),
+						     Qinvisible,
+						     Qnil,
+						     Qnil);
+	    if (FIXNUMP (charpos) && XFIXNUM (charpos) < IT_CHARPOS (*it))
+	      {
+		IT_CHARPOS (*it) = XFIXNUM (charpos);
+		IT_BYTEPOS (*it) = buf_charpos_to_bytepos (current_buffer, XFIXNUM (charpos));
+	      }
+	    continue;
+	  }
       }
 
       if (IT_CHARPOS (*it) <= BEGV)