Reported by: Daniel Lopez <daniel.lopez999 <at> gmail.com>
Date: Mon, 18 Feb 2019 08:31:01 UTC
Severity: normal
Done: Alan Mackenzie <acm <at> muc.de>
Bug is archived. No further changes may be made.
Message #134 received at 34525 <at> debbugs.gnu.org (full text, mbox):
From: Alan Mackenzie <acm <at> muc.de> To: Eli Zaretskii <eliz <at> gnu.org> Cc: daniel.lopez999 <at> gmail.com, monnier <at> IRO.UMontreal.CA, 34525 <at> debbugs.gnu.org Subject: Re: bug#34525: replace-regexp missing some matches Date: Thu, 28 Feb 2019 21:54:14 +0000
Hello, Eli.
On Thu, Feb 28, 2019 at 19:41:12 +0200, Eli Zaretskii wrote:
> > Date: Thu, 28 Feb 2019 10:50:25 +0000
> > Cc: daniel.lopez999 <at> gmail.com, 34525 <at> debbugs.gnu.org
> > From: Alan Mackenzie <acm <at> muc.de>
> > (i) Calculate ->position's in previous_interval and next_interval, as my
> > tentative patch already does.
> > (ii) Calculate the ->position's in update_interval, on moving to
> > parents.
> > (iii) Do away with update_interval, replacing it in syntax.c with
> > previous/next_interval in while loops.
> > In (i), the convention for ->position would be that it is valid for the
> > target interval together with all its parents. In (ii) and (iii), it
> > would only be valid in the final target intervals found by navigation.
> > I think this should be explicitly stated in a comment in struct
> > interval.
Done.
> > So, where do we go from here? If it were up to me, I would probably
> > chose (i), simply because it's already been done, but I've no strong
> > feelings over it.
> I prefer not to do (i) because it has much wider implications than
> needed. Either (ii) or (iii) are okay with me. The former seems to
> be simpler, so I tend to favor it slightly.
OK, I enclose a patch which codes up (ii). As a matter of interest, it
seems to run a little faster on my benchmark of scrolling through
xdisp.c than the version without the fix.
And it fixes the OP's bug. :-)
diff --git a/src/intervals.c b/src/intervals.c
index 524bb944e5..2ed913d5fb 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -713,11 +713,21 @@ previous_interval (register INTERVAL interval)
return NULL;
}
-/* Find the interval containing POS given some non-NULL INTERVAL
- in the same tree. Note that we need to update interval->position
- if we go down the tree.
- To speed up the process, we assume that the ->position of
- I and all its parents is already uptodate. */
+/* Set the ->position field of I's parent, based on I->position. */
+#define SET_PARENT_POSITION(i) \
+ if (AM_LEFT_CHILD (i)) \
+ INTERVAL_PARENT (i)->position = \
+ i->position + TOTAL_LENGTH (i) - LEFT_TOTAL_LENGTH (i); \
+ else \
+ INTERVAL_PARENT (i)->position = \
+ i->position - LEFT_TOTAL_LENGTH (i) \
+ - LENGTH (INTERVAL_PARENT (i))
+
+/* Find the interval containing POS given some non-NULL INTERVAL in
+ the same tree. Note that we update interval->position in each
+ interval we traverse, assuming it is already correctly set for the
+ argument I. We don't assume that any other interval already has a
+ correctly set ->position. */
INTERVAL
update_interval (register INTERVAL i, ptrdiff_t pos)
{
@@ -738,7 +748,10 @@ update_interval (register INTERVAL i, ptrdiff_t pos)
else if (NULL_PARENT (i))
error ("Point before start of properties");
else
- i = INTERVAL_PARENT (i);
+ {
+ SET_PARENT_POSITION (i);
+ i = INTERVAL_PARENT (i);
+ }
continue;
}
else if (pos >= INTERVAL_LAST_POS (i))
@@ -753,7 +766,10 @@ update_interval (register INTERVAL i, ptrdiff_t pos)
else if (NULL_PARENT (i))
error ("Point %"pD"d after end of properties", pos);
else
- i = INTERVAL_PARENT (i);
+ {
+ SET_PARENT_POSITION (i);
+ i = INTERVAL_PARENT (i);
+ }
continue;
}
else
diff --git a/src/intervals.h b/src/intervals.h
index 9c5adf33a1..7608800116 100644
--- a/src/intervals.h
+++ b/src/intervals.h
@@ -31,11 +31,15 @@ struct interval
/* The first group of entries deal with the tree structure. */
ptrdiff_t total_length; /* Length of myself and both children. */
ptrdiff_t position; /* Cache of interval's character position. */
- /* This field is usually updated
- simultaneously with an interval
- traversal, there is no guarantee
- that it is valid for a random
- interval. */
+ /* This field is valid for the final
+ target interval returned by
+ find_interval, next_interval,
+ previous_interval and
+ update_interval. It cannot be
+ depended upon for any intermediate
+ intevals traversed by these
+ functions, or any other
+ interval. */
struct interval *left; /* Intervals which precede me. */
struct interval *right; /* Intervals which succeed me. */
diff --git a/src/pdumper.c b/src/pdumper.c
index f9638d4357..3aea4ab0d6 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2065,7 +2065,7 @@ dump_interval_tree (struct dump_context *ctx,
INTERVAL tree,
dump_off parent_offset)
{
-#if CHECK_STRUCTS && !defined (HASH_interval_9110163DA0)
+#if CHECK_STRUCTS && !defined (HASH_interval_70865541E2)
# error "interval changed. See CHECK_STRUCTS comment."
#endif
// TODO: output tree breadth-first?
diff --git a/src/syntax.c b/src/syntax.c
index 4616ae296f..faea1432cb 100644
--- a/src/syntax.c
+++ b/src/syntax.c
@@ -340,20 +340,6 @@ update_syntax_table (ptrdiff_t charpos, EMACS_INT count, bool init,
invalidate = false;
if (!i)
return;
- /* interval_of updates only ->position of the return value, so
- update the parents manually to speed up update_interval. */
- while (!NULL_PARENT (i))
- {
- if (AM_RIGHT_CHILD (i))
- INTERVAL_PARENT (i)->position = i->position
- - LEFT_TOTAL_LENGTH (i) + TOTAL_LENGTH (i) /* right end */
- - TOTAL_LENGTH (INTERVAL_PARENT (i))
- + LEFT_TOTAL_LENGTH (INTERVAL_PARENT (i));
- else
- INTERVAL_PARENT (i)->position = i->position - LEFT_TOTAL_LENGTH (i)
- + TOTAL_LENGTH (i);
- i = INTERVAL_PARENT (i);
- }
i = gl_state.forward_i;
gl_state.b_property = i->position - gl_state.offset;
gl_state.e_property = INTERVAL_LAST_POS (i) - gl_state.offset;
I've just noticed a typo in one of the comments in intervals.h, so the
above can't be final. Sorry.
--
Alan Mackenzie (Nuremberg, Germany).
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.