bug#34525: replace-regexp missing some matches

[Alan Mackenzie]

Hello, again, Eli.

On Tue, Feb 26, 2019 at 13:50:48 +0000, Alan Mackenzie wrote:
> On Mon, Feb 25, 2019 at 22:11:57 +0200, Eli Zaretskii wrote:
> > > Date: Sun, 24 Feb 2019 21:00:58 +0000
> > > Cc: daniel.lopez999@gmail.com, 34525@debbugs.gnu.org, 
> > > monnier@iro.umontreal.ca
> > > From: Alan Mackenzie <acm@muc.de>

> > > > > Sadly, UPDATE_SYNTAX_TABLE sets its internal structure gl_state not 
> > > > > for
> > > > > the current contents of position 1948, but the contents of 1948 before
> > > > > the change at the top of the buffer (Bitmap -> SharedBitmap) was made.
> > > > > So it picks up the syntax for the "<" rather than the "B".

> > > > Are you saying that we've modified buffer text, but
> > > > re_match_2_internal still holds to a C pointer to buffer text before
> > > > the change?

> > > I don't think that's the case.  The relevant buffer pointers/sizes are
> > > calculated (in search_buffer_re) as

> > >     p1 = BEGV_ADDR;
> > >     s1 = GPT_BYTE - BEGV_BYTE;
> > >     p2 = GAP_END_ADDR;
> > >     s2 = ZV_BYTE - GPT_BYTE;

> > > each time before a search.

> > So you are saying that gl_state uses a stale offset, which should have
> > been updated due to the previous replacements?

> More precisely, I think that the interval containing "Bitmap<" has not
> been adjusted after the replacement of "Bitmap.h" by "SharedBitmap.h"
> early in the .h file.

> After this buffer change, adjust_intervals_for_insertion gets called.
> This adds 6 onto the ->position field of each interval "adjusting all of
> its ancestors by adding LENGTH to them", according to the comment at the
> head of adjust_intervals_for_insertion.

> Note this only adjusts the ancestors of that interval early in the .h
> file, not all intervals in the tree.

> gl_state contains a cached interval, gl_state->backward_i, and there is
> no guarantee that its ->position will have been updated by
> adjust_intervals_for_insertion.  In the current bug, I believe it hasn't
> been adjusted.

> The function update_syntax_table uses gl_state->backward_i to manoevre
> its way to the current interval using update_interval.  If
> gl_state->backward_i->position hasn't already been adjusted for the
> insertion, the interval update_interval returns won't have been adjusted
> either.

> I'm reasonably sure this is what's happening:
> adjust_intervals_for_insertion is failing to adjust the cached intervals
> in gl_state.  It's a nasty cache invalidation problem.

> I don't know how best to fix this.  Maybe a_i_f_insertion/deletion could
> set a global flag which would signal to update_syntax_table that its
> intervals are not reliable.  But that's horribly ugly.

How about the following idea:
(i) We introduce a new boolean flag `adjusted' into struct interval.
(ii) When we adjust ->position in an interval in
  adjust_intervals_for_insertion/deletion, we set `adjusted' there.
(iii) At the end of a_i_f_insertion/deletion, we adjust gl_state's
  intervals, going to the parent as long as `adjusted' is not yet true.
(iv) We clear all the set `adjusted' flags.

A simpler, but slower, alternative would be to set gl_state's intervals
to NULL on any buffer change earlier in the buffer.

-- 
Alan Mackenzie (Nuremberg, Germany).