bug#17298: 24.4.50; emacs_backtrace

[Stefan Monnier <monnier@IRO.UMontreal.CA>]

> I really wish someone who knows those parts of Emacs would look into
> this problem.

I don't know those parts very well, but it seems that the patch below
might make sense.

I have a hard time believing that we've lived with such a bug for so
many years, but this makes the code agree with the comment, and if you
look at the diagram before the function, I think the comment is right
and the code is wrong.

Just to clarify the crucial part of the patch is:

-  interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
+  interval->total_length -= B->total_length - TOTAL_LENGTH (c);


-- Stefan


=== modified file 'src/intervals.c'
--- src/intervals.c	2014-01-21 02:28:57 +0000
+++ src/intervals.c	2014-04-19 17:51:01 +0000
@@ -334,10 +334,16 @@
 static INTERVAL
 rotate_right (INTERVAL interval)
 {
-  INTERVAL i;
+  INTERVAL c;
   INTERVAL B = interval->left;
   ptrdiff_t old_total = interval->total_length;
 
+  eassert (TOTAL_LENGTH (interval) > 0);
+  eassert (TOTAL_LENGTH (interval)
+	   > TOTAL_LENGTH (B) + TOTAL_LENGTH (interval->right));
+  eassert (TOTAL_LENGTH (B)
+	   > TOTAL_LENGTH (B->left) + TOTAL_LENGTH (B->right));
+
   /* Deal with any Parent of A;  make it point to B.  */
   if (! ROOT_INTERVAL_P (interval))
     {
@@ -348,23 +354,23 @@
     }
   copy_interval_parent (B, interval);
 
-  /* Make B the parent of A */
-  i = B->right;
+  /* Make B the parent of A.  */
+  c = B->right;
   set_interval_right (B, interval);
   set_interval_parent (interval, B);
 
-  /* Make A point to c */
-  set_interval_left (interval, i);
-  if (i)
-    set_interval_parent (i, interval);
+  /* Make A point to c.  */
+  set_interval_left (interval, c);
+  if (c)
+    set_interval_parent (c, interval);
 
   /* A's total length is decreased by the length of B and its left child.  */
-  interval->total_length -= B->total_length - LEFT_TOTAL_LENGTH (interval);
-  eassert (TOTAL_LENGTH (interval) >= 0);
+  interval->total_length -= B->total_length - TOTAL_LENGTH (c);
+  eassert (TOTAL_LENGTH (interval) > 0);
 
   /* B must have the same total length of A.  */
   B->total_length = old_total;
-  eassert (TOTAL_LENGTH (B) >= 0);
+  eassert (TOTAL_LENGTH (B) > 0);
 
   return B;
 }
@@ -381,7 +387,7 @@
 static INTERVAL
 rotate_left (INTERVAL interval)
 {
-  INTERVAL i;
+  INTERVAL c;
   INTERVAL B = interval->right;
   ptrdiff_t old_total = interval->total_length;
 
@@ -395,23 +401,23 @@
     }
   copy_interval_parent (B, interval);
 
-  /* Make B the parent of A */
-  i = B->left;
+  /* Make B the parent of A.  */
+  c = B->left;
   set_interval_left (B, interval);
   set_interval_parent (interval, B);
 
-  /* Make A point to c */
-  set_interval_right (interval, i);
-  if (i)
-    set_interval_parent (i, interval);
+  /* Make A point to c.  */
+  set_interval_right (interval, c);
+  if (c)
+    set_interval_parent (c, interval);
 
   /* A's total length is decreased by the length of B and its right child.  */
-  interval->total_length -= B->total_length - RIGHT_TOTAL_LENGTH (interval);
-  eassert (TOTAL_LENGTH (interval) >= 0);
+  interval->total_length -= B->total_length - TOTAL_LENGTH (c);
+  eassert (TOTAL_LENGTH (interval) > 0);
 
   /* B must have the same total length of A.  */
   B->total_length = old_total;
-  eassert (TOTAL_LENGTH (B) >= 0);
+  eassert (TOTAL_LENGTH (B) > 0);
 
   return B;
 }