# HG changeset patch # User Ken Raeburn # Date 953761445 0 # Node ID fd13be8ae190f9d37ca4514959e6e4775bcdb52d # Parent 33f65d22f2a85231175dfbf0c54542cf624296a9 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. diff -r 33f65d22f2a8 -r fd13be8ae190 src/ChangeLog Binary file src/ChangeLog has changed diff -r 33f65d22f2a8 -r fd13be8ae190 src/alloc.c --- 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--; } diff -r 33f65d22f2a8 -r fd13be8ae190 src/intervals.c --- 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; } diff -r 33f65d22f2a8 -r fd13be8ae190 src/intervals.h --- 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; \ diff -r 33f65d22f2a8 -r fd13be8ae190 src/syntax.c --- 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;