Re: Subtle bug in intervals code

[Andreas Schwab]

Dmitry Antipov <address@hidden> writes:

> Commit 109118 (by me) introduces the following change in src/intervals.c, 
> function delete_interval:
>
> @@ -1262,8 +1198,7 @@
>    register INTERVAL parent;
>    ptrdiff_t amt = LENGTH (i);
>
> -  if (amt > 0)                       /* Only used on zero-length intervals 
> now.  */
> -    abort ();
> +  eassert (amt == 0);                /* Only used on zero-length intervals 
> now.  */
>
>    if (ROOT_INTERVAL_P (i))
>      {
>
> Now this eassert traps at interval with negative length. I'm not familiar with
> this subsystem enough to find (possible) bug quickly, so any help is 
> appreciated.

I think this will fix it.  The total length of an interval doesn't
change when it is absorbed by its children.

diff --git a/src/intervals.c b/src/intervals.c
index 5b8d44e..cd1254b 100644
--- a/src/intervals.c
+++ b/src/intervals.c
@@ -1391,10 +1391,6 @@ merge_interval_right (register INTERVAL i)
   register ptrdiff_t absorb = LENGTH (i);
   register INTERVAL successor;
 
-  /* Zero out this interval.  */
-  i->total_length -= absorb;
-  CHECK_TOTAL_LENGTH (i);
-
   /* Find the succeeding interval.  */
   if (! NULL_RIGHT_CHILD (i))      /* It's below us.  Add absorb
                                      as we descend.  */
@@ -1413,6 +1409,10 @@ merge_interval_right (register INTERVAL i)
       return successor;
     }
 
+  /* Zero out this interval.  */
+  i->total_length -= absorb;
+  CHECK_TOTAL_LENGTH (i);
+
   successor = i;
   while (! NULL_PARENT (successor))       /* It's above us.  Subtract as
                                              we ascend.  */
@@ -1447,10 +1447,6 @@ merge_interval_left (register INTERVAL i)
   register ptrdiff_t absorb = LENGTH (i);
   register INTERVAL predecessor;
 
-  /* Zero out this interval.  */
-  i->total_length -= absorb;
-  CHECK_TOTAL_LENGTH (i);
-
   /* Find the preceding interval.  */
   if (! NULL_LEFT_CHILD (i))   /* It's below us. Go down,
                                   adding ABSORB as we go.  */
@@ -1469,9 +1465,13 @@ merge_interval_left (register INTERVAL i)
       return predecessor;
     }
 
+  /* Zero out this interval.  */
+  i->total_length -= absorb;
+  CHECK_TOTAL_LENGTH (i);
+
   predecessor = i;
   while (! NULL_PARENT (predecessor))  /* It's above us.  Go up,
-                                  subtracting ABSORB.  */
+                                          subtracting ABSORB.  */
     {
       if (AM_RIGHT_CHILD (predecessor))
        {

Andreas.

-- 
Andreas Schwab, address@hidden
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."