Subject: Re: bug#34525: replace-regexp missing some matches

From: Stefan Monnier <[email-masked]>
Date: Wed, 27 Feb 2019 12:41:04 -0500

> next_interval and previous_interval are used extensively, so I'm
> having hard time believing that they have such a blatant bug.

I'm also wondering why this hasn't bitten us long ago, but the behavior
in the original bug-report is definitely weird.

E.g. I reproduced the bug using the lower-level (while
(re-search-forward RE) (replace-match)), and then added (how-many RE)
calls before re-search-forward and before replace-match: these should
always differ by 1 (since one occurrence of RE was skipped by
re-search-forward), but they often didn't (even though there was no
buffer modifications between the two how-many calls).

AFAICT the only place where the missing updates can bite us is when we
call update_interval, since it seems to be the only function that relies
on all parents having the ->position field correctly set.

update_interval is only called from update_syntax_table.

I'm actually wondering whether we should keep update_interval at all:
AFAICT update_syntax_table is almost always called "sequentially".
I.e. the new `charpos` is right next to the old one.  So a while loop
with next_interval/previous_interval should be just as efficient in
practice: a loop of next_interval/previous_interval has basically
a complexity O(n) where `n` is the distance we move, whereas
update_interval has complexity O(log n), so if `n` is almost always
1 the difference doesn't matter.

        Stefan