changeset 28269:fd13be8ae190

Changes towards better type safety regarding intervals, primarily regarding the "parent" handle. These just separate out the different usages based on the type of parent (interval vs lisp object); later changes will do type checking and enforcement. * intervals.h (NULL_INTERVAL): Cast to INTERVAL type. (INT_LISPLIKE): New macro. (NULL_INTERVAL_P): Use it. (INTERVAL_HAS_PARENT, INTERVAL_HAS_OBJECT, SET_INTERVAL_PARENT, SET_INTERVAL_OBJECT, INTERVAL_PARENT, COPY_INTERVAL_PARENT, GET_INTERVAL_OBJECT, INTERVAL_PARENT_OR_NULL): New macros. * alloc.c (make_interval, gc_sweep): Use new macros; eliminate all explicit references to "parent" field of struct interval and associated unclean type conversions. * intervals.c (create_root_interval, root_interval, rotate_right, rotate_left, balance_possible_root_interval, split_interval_right, split_interval_left, interval_start_pos, find_interval, next_interval, previous_interval, update_interval, adjust_intervals_for_insertion, delete_node, delete_interval, adjust_intervals_for_deletion, merge_interval_right, merge_interval_left, reproduce_tree, graft_intervals_into_buffer, copy_intervals_to_string): Likewise. * intervals.h (AM_LEFT_CHILD, AM_RIGHT_CHILD, RESET_INTERVAL): Likewise. * syntax.c (update_syntax_table): Likewise. * intervals.c (reproduce_tree_obj): New function, like reproduce_tree but takes a Lisp_Object for the parent. Declare with prototype. (graft_intervals_into_buffer): Use it when appropriate. (reproduce_tree): Declare with prototype. (balance_possible_root_interval): Check that the parent is a lisp object before trying to examine its type.

Binary file src/ChangeLog has changed

--- a/src/alloc.c	Wed Mar 22 14:25:38 2000 +0000
+++ b/src/alloc.c	Wed Mar 22 21:44:05 2000 +0000
@@ -711,7 +711,7 @@
   if (interval_free_list)
     {
       val = interval_free_list;
-      interval_free_list = interval_free_list->parent;
+      interval_free_list = INTERVAL_PARENT (interval_free_list);
     }
   else
     {
@@ -4215,7 +4215,7 @@
 	  {
 	    if (! XMARKBIT (iblk->intervals[i].plist))
 	      {
-		iblk->intervals[i].parent = interval_free_list;
+		SET_INTERVAL_PARENT (&iblk->intervals[i], interval_free_list);
 		interval_free_list = &iblk->intervals[i];
 		this_free++;
 	      }
@@ -4233,7 +4233,7 @@
 	  {
 	    *iprev = iblk->next;
 	    /* Unhook from the free list.  */
-	    interval_free_list = iblk->intervals[0].parent;
+	    interval_free_list = INTERVAL_PARENT (&iblk->intervals[0]);
 	    lisp_free (iblk);
 	    n_interval_blocks--;
 	  }

--- a/src/intervals.c	Wed Mar 22 14:25:38 2000 +0000
+++ b/src/intervals.c	Wed Mar 22 21:44:05 2000 +0000
@@ -54,6 +54,8 @@
 #define min(x, y) ((x) < (y) ? (x) : (y))
 
 Lisp_Object merge_properties_sticky ();
+static INTERVAL reproduce_tree P_ ((INTERVAL, INTERVAL));
+static INTERVAL reproduce_tree_obj P_ ((INTERVAL, Lisp_Object));
 
 /* Utility functions for intervals.  */
 
@@ -84,7 +86,7 @@
       new->position = 0;
     }
 
-  new->parent = (INTERVAL) XFASTINT (parent);
+  SET_INTERVAL_OBJECT (new, parent);
 
   return new;
 }
@@ -269,7 +271,7 @@
   register INTERVAL i = interval;
 
   while (! ROOT_INTERVAL_P (i))
-    i = i->parent;
+    i = INTERVAL_PARENT (i);
 
   return i;
 }
@@ -296,21 +298,21 @@
   if (! ROOT_INTERVAL_P (interval))
     {
       if (AM_LEFT_CHILD (interval))
-	interval->parent->left = B;
+	INTERVAL_PARENT (interval)->left = B;
       else
-	interval->parent->right = B;
+	INTERVAL_PARENT (interval)->right = B;
     }
-  B->parent = interval->parent;
+  COPY_INTERVAL_PARENT (B, interval);
 
   /* Make B the parent of A */
   i = B->right;
   B->right = interval;
-  interval->parent = B;
+  SET_INTERVAL_PARENT (interval, B);
 
   /* Make A point to c */
   interval->left = i;
   if (! NULL_INTERVAL_P (i))
-    i->parent = interval;
+    SET_INTERVAL_PARENT (i, 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);
@@ -342,21 +344,21 @@
   if (! ROOT_INTERVAL_P (interval))
     {
       if (AM_LEFT_CHILD (interval))
-	interval->parent->left = B;
+	INTERVAL_PARENT (interval)->left = B;
       else
-	interval->parent->right = B;
+	INTERVAL_PARENT (interval)->right = B;
     }
-  B->parent = interval->parent;
+  COPY_INTERVAL_PARENT (B, interval);
 
   /* Make B the parent of A */
   i = B->left;
   B->left = interval;
-  interval->parent = B;
+  SET_INTERVAL_PARENT (interval, B);
 
   /* Make A point to c */
   interval->right = i;
   if (! NULL_INTERVAL_P (i))
-    i->parent = interval;
+    SET_INTERVAL_PARENT (i, 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);
@@ -411,17 +413,25 @@
      register INTERVAL interval;
 {
   Lisp_Object parent;
+  int have_parent = 0;
 
-  if (interval->parent == NULL_INTERVAL)
+  if (!INTERVAL_HAS_OBJECT (interval) && !INTERVAL_HAS_PARENT (interval))
     return interval;
 
-  XSETFASTINT (parent, (EMACS_INT) interval->parent);
+  if (INTERVAL_HAS_OBJECT (interval))
+    {
+      have_parent = 1;
+      GET_INTERVAL_OBJECT (parent, interval);
+    }
   interval = balance_an_interval (interval);
 
-  if (BUFFERP (parent))
-    BUF_INTERVALS (XBUFFER (parent)) = interval;
-  else if (STRINGP (parent))
-    XSTRING (parent)->intervals = interval;
+  if (have_parent)
+    {
+      if (BUFFERP (parent))
+	BUF_INTERVALS (XBUFFER (parent)) = interval;
+      else if (STRINGP (parent))
+	XSTRING (parent)->intervals = interval;
+    }
 
   return interval;
 }
@@ -476,7 +486,7 @@
   int new_length = LENGTH (interval) - offset;
 
   new->position = position + offset;
-  new->parent = interval;
+  SET_INTERVAL_PARENT (new, interval);
 
   if (NULL_RIGHT_CHILD (interval))
     {
@@ -487,7 +497,7 @@
     {
       /* Insert the new node between INTERVAL and its right child.  */
       new->right = interval->right;
-      interval->right->parent = new;
+      SET_INTERVAL_PARENT (interval->right, new);
       interval->right = new;
       new->total_length = new_length + new->right->total_length;
       balance_an_interval (new);
@@ -521,7 +531,7 @@
 
   new->position = interval->position;
   interval->position = interval->position + offset;
-  new->parent = interval;
+  SET_INTERVAL_PARENT (new, interval);
 
   if (NULL_LEFT_CHILD (interval))
     {
@@ -532,7 +542,7 @@
     {
       /* Insert the new node between INTERVAL and its left child.  */
       new->left = interval->left;
-      new->left->parent = new;
+      SET_INTERVAL_PARENT (new->left, new);
       interval->left = new;
       new->total_length = new_length + new->left->total_length;
       balance_an_interval (new);
@@ -560,7 +570,7 @@
   if (NULL_INTERVAL_P (source))
     return 0;
 
-  XSETFASTINT (parent, (EMACS_INT) source->parent);
+  GET_INTERVAL_OBJECT (parent, source);
   if (BUFFERP (parent))
     return BUF_BEG (XBUFFER (parent));
   return 0;
@@ -584,15 +594,18 @@
   /* The distance from the left edge of the subtree at TREE
                     to POSITION.  */
   register int relative_position;
-  Lisp_Object parent;
 
   if (NULL_INTERVAL_P (tree))
     return NULL_INTERVAL;
 
-  XSETFASTINT (parent, (EMACS_INT) tree->parent);
   relative_position = position;
-  if (BUFFERP (parent))
-    relative_position -= BUF_BEG (XBUFFER (parent));
+  if (INTERVAL_HAS_OBJECT (tree))
+    {
+      Lisp_Object parent;
+      GET_INTERVAL_OBJECT (parent, tree);
+      if (BUFFERP (parent))
+	relative_position -= BUF_BEG (XBUFFER (parent));
+    }
 
   if (relative_position > TOTAL_LENGTH (tree))
     abort ();			/* Paranoia */
@@ -653,12 +666,12 @@
     {
       if (AM_LEFT_CHILD (i))
 	{
-	  i = i->parent;
+	  i = INTERVAL_PARENT (i);
 	  i->position = next_position;
 	  return i;
 	}
 
-      i = i->parent;
+      i = INTERVAL_PARENT (i);
     }
 
   return NULL_INTERVAL;
@@ -692,12 +705,12 @@
     {
       if (AM_RIGHT_CHILD (i))
 	{
-	  i = i->parent;
+	  i = INTERVAL_PARENT (i);
 
 	  i->position = interval->position - LENGTH (i);
 	  return i;
 	}
-      i = i->parent;
+      i = INTERVAL_PARENT (i);
     }
 
   return NULL_INTERVAL;
@@ -728,7 +741,7 @@
 	  else if (NULL_PARENT (i)) 
 	    error ("Point before start of properties");
 	  else  
-	      i = i->parent;
+	      i = INTERVAL_PARENT (i);
 	  continue;
 	}
       else if (pos >= INTERVAL_LAST_POS (i))
@@ -743,7 +756,7 @@
 	  else if (NULL_PARENT (i)) 
 	    error ("Point after end of properties");
 	  else 
-	      i = i->parent;
+	      i = INTERVAL_PARENT (i);
 	  continue;
 	}
       else 
@@ -838,7 +851,7 @@
   if (TOTAL_LENGTH (tree) == 0)	/* Paranoia */
     abort ();
 
-  XSETFASTINT (parent, (EMACS_INT) tree->parent);
+  GET_INTERVAL_OBJECT (parent, tree);
   offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
 
   /* If inserting at point-max of a buffer, that position will be out
@@ -944,7 +957,7 @@
       /* Even if we are positioned between intervals, we default
 	 to the left one if it exists.  We extend it now and split
 	 off a part later, if stickiness demands it.  */
-      for (temp = prev ? prev : i;! NULL_INTERVAL_P (temp); temp = temp->parent)
+      for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
 	{
 	  temp->total_length += length;
 	  temp = balance_possible_root_interval (temp);
@@ -1000,7 +1013,7 @@
   /* Otherwise just extend the interval.  */
   else
     {
-      for (temp = i; ! NULL_INTERVAL_P (temp); temp = temp->parent)
+      for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp))
 	{
 	  temp->total_length += length;
 	  temp = balance_possible_root_interval (temp);
@@ -1208,7 +1221,7 @@
       this->total_length += migrate_amt;
     }
   this->left = migrate;
-  migrate->parent = this;
+  SET_INTERVAL_PARENT (migrate, this);
 
   return i->right;
 }
@@ -1232,10 +1245,10 @@
   if (ROOT_INTERVAL_P (i))
     {
       Lisp_Object owner;
-      XSETFASTINT (owner, (EMACS_INT) i->parent);
+      GET_INTERVAL_OBJECT (owner, i);
       parent = delete_node (i);
       if (! NULL_INTERVAL_P (parent))
-	parent->parent = (INTERVAL) XFASTINT (owner);
+	SET_INTERVAL_OBJECT (parent, owner);
 
       if (BUFFERP (owner))
 	BUF_INTERVALS (XBUFFER (owner)) = parent;
@@ -1247,18 +1260,18 @@
       return;
     }
 
-  parent = i->parent;
+  parent = INTERVAL_PARENT (i);
   if (AM_LEFT_CHILD (i))
     {
       parent->left = delete_node (i);
       if (! NULL_INTERVAL_P (parent->left))
-	parent->left->parent = parent;
+	SET_INTERVAL_PARENT (parent->left, parent);
     }
   else
     {
       parent->right = delete_node (i);
       if (! NULL_INTERVAL_P (parent->right))
-	parent->right->parent = parent;
+	SET_INTERVAL_PARENT (parent->right, parent);
     }
 }
 
@@ -1343,7 +1356,7 @@
   Lisp_Object parent;
   int offset;
 
-  XSETFASTINT (parent, (EMACS_INT) tree->parent);
+  GET_INTERVAL_OBJECT (parent, tree);
   offset = (BUFFERP (parent) ? BUF_BEG (XBUFFER (parent)) : 0);
 
   if (NULL_INTERVAL_P (tree))
@@ -1440,12 +1453,12 @@
     {
       if (AM_LEFT_CHILD (successor))
 	{
-	  successor = successor->parent;
+	  successor = INTERVAL_PARENT (successor);
 	  delete_interval (i);
 	  return successor;
 	}
 
-      successor = successor->parent;
+      successor = INTERVAL_PARENT (successor);
       successor->total_length -= absorb;
     }
 
@@ -1493,12 +1506,12 @@
     {
       if (AM_RIGHT_CHILD (predecessor))
 	{
-	  predecessor = predecessor->parent;
+	  predecessor = INTERVAL_PARENT (predecessor);
 	  delete_interval (i);
 	  return predecessor;
 	}
 
-      predecessor = predecessor->parent;
+      predecessor = INTERVAL_PARENT (predecessor);
       predecessor->total_length -= absorb;
     }
 
@@ -1520,7 +1533,25 @@
 
   bcopy (source, t, INTERVAL_SIZE);
   copy_properties (source, t);
-  t->parent = parent;
+  SET_INTERVAL_PARENT (t, parent);
+  if (! NULL_LEFT_CHILD (source))
+    t->left = reproduce_tree (source->left, t);
+  if (! NULL_RIGHT_CHILD (source))
+    t->right = reproduce_tree (source->right, t);
+
+  return t;
+}
+
+static INTERVAL
+reproduce_tree_obj (source, parent)
+     INTERVAL source;
+     Lisp_Object parent;
+{
+  register INTERVAL t = make_interval ();
+
+  bcopy (source, t, INTERVAL_SIZE);
+  copy_properties (source, t);
+  SET_INTERVAL_OBJECT (t, parent);
   if (! NULL_LEFT_CHILD (source))
     t->left = reproduce_tree (source->left, t);
   if (! NULL_RIGHT_CHILD (source))
@@ -1654,7 +1685,7 @@
 	{
 	  Lisp_Object buf;
 	  XSETBUFFER (buf, buffer);
-	  BUF_INTERVALS (buffer) = reproduce_tree (source, buf);
+	  BUF_INTERVALS (buffer) = reproduce_tree_obj (source, buf);
 	  BUF_INTERVALS (buffer)->position = 1;
 
 	  /* Explicitly free the old tree here?  */
@@ -1676,7 +1707,7 @@
        some zero length intervals.  Eventually, do something clever
        about inserting properly.  For now, just waste the old intervals.  */
     {
-      BUF_INTERVALS (buffer) = reproduce_tree (source, tree->parent);
+      BUF_INTERVALS (buffer) = reproduce_tree (source, INTERVAL_PARENT (tree));
       BUF_INTERVALS (buffer)->position = 1;
       /* Explicitly free the old tree here.  */
 
@@ -2236,7 +2267,7 @@
   if (NULL_INTERVAL_P (interval_copy))
     return;
 
-  interval_copy->parent = (INTERVAL) XFASTINT (string);
+  SET_INTERVAL_OBJECT (interval_copy, string);
   XSTRING (string)->intervals = interval_copy;
 }
 

--- a/src/intervals.h	Wed Mar 22 14:25:38 2000 +0000
+++ b/src/intervals.h	Wed Mar 22 21:44:05 2000 +0000
@@ -22,7 +22,7 @@
 #include "dispextern.h"
 #endif
 
-#define NULL_INTERVAL 0
+#define NULL_INTERVAL ((INTERVAL)0)
 #define INTERVAL_DEFAULT NULL_INTERVAL
 
 /* These are macros for dealing with the interval tree. */
@@ -37,14 +37,13 @@
    Lisp_String pointer (meaning it points to the owner of this
    interval tree). */
 #ifdef NO_UNION_TYPE
-#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL           \
-			    || BUFFERP ((Lisp_Object)(i)) \
-			    || STRINGP ((Lisp_Object)(i)))
+#define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object)(i)) \
+			 || STRINGP ((Lisp_Object)(i)))
 #else
-#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL           \
-			    || BUFFERP ((Lisp_Object){(EMACS_INT)(i)}) \
-			    || STRINGP ((Lisp_Object){(EMACS_INT)(i)}))
+#define INT_LISPLIKE(i) (BUFFERP ((Lisp_Object){(EMACS_INT)(i)}) \
+			 || STRINGP ((Lisp_Object){(EMACS_INT)(i)}))
 #endif
+#define NULL_INTERVAL_P(i) ((i) == NULL_INTERVAL || INT_LISPLIKE (i))
 
 /* True if this interval has no right child. */
 #define NULL_RIGHT_CHILD(i) ((i)->right == NULL_INTERVAL)
@@ -56,12 +55,12 @@
 #define NULL_PARENT(i) (NULL_INTERVAL_P ((i)->parent))
 
 /* True if this interval is the left child of some other interval. */
-#define AM_LEFT_CHILD(i) (! NULL_INTERVAL_P ((i)->parent) \
-			  && (i)->parent->left == (i))
+#define AM_LEFT_CHILD(i) (! NULL_PARENT (i) \
+			  && INTERVAL_PARENT (i)->left == (i))
 
 /* True if this interval is the right child of some other interval. */
-#define AM_RIGHT_CHILD(i) (! NULL_INTERVAL_P ((i)->parent) \
-			   && (i)->parent->right == (i))
+#define AM_RIGHT_CHILD(i) (! NULL_PARENT (i) \
+			   && INTERVAL_PARENT (i)->right == (i))
 
 /* True if this interval has no children. */
 #define LEAF_INTERVAL_P(i) ((i)->left == NULL_INTERVAL \
@@ -103,12 +102,38 @@
    or having no properties. */
 #define DEFAULT_INTERVAL_P(i) (NULL_INTERVAL_P (i) || EQ ((i)->plist, Qnil))
 
+/* Test what type of parent we have.  Three possibilities: another
+   interval, a buffer or string object, or NULL_INTERVAL.  */
+#define INTERVAL_HAS_PARENT(i) ((i)->parent && ! INT_LISPLIKE ((i)->parent))
+#define INTERVAL_HAS_OBJECT(i) ((i)->parent &&   INT_LISPLIKE ((i)->parent))
+
+/* Set/get parent of an interval.
+
+   The choice of macros is dependent on the type needed.  Don't add
+   casts to get around this, it will break some development work in
+   progress.  */
+#define SET_INTERVAL_PARENT(i,p) ((i)->parent = (p))
+#define SET_INTERVAL_OBJECT(i,o) ((i)->parent = (INTERVAL) XFASTINT (o))
+#define INTERVAL_PARENT(i) ((i)->parent)
+/* Because XSETFASTINT has to be used, this can't simply be
+   value-returning.  */
+#define GET_INTERVAL_OBJECT(d,s) XSETFASTINT((d), (EMACS_INT) (s)->parent)
+
+/* Make the parent of D be whatever the parent of S is, regardless of
+   type.  This is used when balancing an interval tree.  */
+#define COPY_INTERVAL_PARENT(d,s) ((d)->parent = (s)->parent)
+
+/* Get the parent interval, if any, otherwise a null pointer.  Useful
+   for walking up to the root in a "for" loop; use this to get the
+   "next" value, and test the result to see if it's NULL_INTERVAL.  */
+#define INTERVAL_PARENT_OR_NULL(i) (INTERVAL_HAS_PARENT (i) ? INTERVAL_PARENT (i) : 0)
+
 /* Reset this interval to its vanilla, or no-property state. */
 #define RESET_INTERVAL(i) \
 { \
     (i)->total_length = (i)->position = 0;    \
     (i)->left = (i)->right = NULL_INTERVAL;   \
-    (i)->parent = NULL_INTERVAL;              \
+    SET_INTERVAL_PARENT (i, NULL_INTERVAL);	      \
     (i)->write_protect = 0;                   \
     (i)->visible = 0;                         \
     (i)->front_sticky = (i)->rear_sticky = 0; \

--- a/src/syntax.c	Wed Mar 22 14:25:38 2000 +0000
+++ b/src/syntax.c	Wed Mar 22 21:44:05 2000 +0000
@@ -140,14 +140,14 @@
       while (!NULL_PARENT (i)) 
 	{
 	  if (AM_RIGHT_CHILD (i))
-	    i->parent->position = i->position
+	    INTERVAL_PARENT (i)->position = i->position
 	      - LEFT_TOTAL_LENGTH (i) + TOTAL_LENGTH (i) /* right end */
-	      - TOTAL_LENGTH (i->parent)
-	      + LEFT_TOTAL_LENGTH (i->parent);
+	      - TOTAL_LENGTH (INTERVAL_PARENT (i))
+	      + LEFT_TOTAL_LENGTH (INTERVAL_PARENT (i));
 	  else
-	    i->parent->position = i->position - LEFT_TOTAL_LENGTH (i)
+	    INTERVAL_PARENT (i)->position = i->position - LEFT_TOTAL_LENGTH (i)
 	      + TOTAL_LENGTH (i);
-	  i = i->parent;
+	  i = INTERVAL_PARENT (i);
 	}
       i = gl_state.forward_i;
       gl_state.b_property = i->position - 1 - gl_state.offset;