X-Git-Url: https://git.hcoop.net/bpt/emacs.git/blobdiff_plain/fb9f7146677ca0d6f03ca88dd8cd39bc3733682d..026b174672c427b035009911de305992a94098d6:/src/intervals.c diff --git a/src/intervals.c b/src/intervals.c index db38c86c00..842e0c20c4 100644 --- a/src/intervals.c +++ b/src/intervals.c @@ -1,5 +1,5 @@ /* Code for doing intervals. - Copyright (C) 1993-1995, 1997-1998, 2001-2013 Free Software + Copyright (C) 1993-1995, 1997-1998, 2001-2014 Free Software Foundation, Inc. This file is part of GNU Emacs. @@ -40,8 +40,6 @@ along with GNU Emacs. If not, see . */ #include -#define INTERVALS_INLINE EXTERN_INLINE - #include #include "lisp.h" #include "intervals.h" @@ -62,16 +60,7 @@ static INTERVAL reproduce_tree (INTERVAL, INTERVAL); /* Utility functions for intervals. */ -/* Use these functions to set Lisp_Object - or pointer slots of struct interval. */ - -static void -set_interval_object (INTERVAL i, Lisp_Object obj) -{ - eassert (BUFFERP (obj) || STRINGP (obj)); - i->up_obj = 1; - i->up.obj = obj; -} +/* Use these functions to set pointer slots of struct interval. */ static void set_interval_left (INTERVAL i, INTERVAL left) @@ -110,24 +99,25 @@ create_root_interval (Lisp_Object parent) { new->total_length = (BUF_Z (XBUFFER (parent)) - BUF_BEG (XBUFFER (parent))); - eassert (0 <= TOTAL_LENGTH (new)); + eassert (TOTAL_LENGTH (new) >= 0); set_buffer_intervals (XBUFFER (parent), new); new->position = BEG; } else if (STRINGP (parent)) { new->total_length = SCHARS (parent); - eassert (0 <= TOTAL_LENGTH (new)); + eassert (TOTAL_LENGTH (new) >= 0); set_string_intervals (parent, new); new->position = 0; } - + eassert (LENGTH (new) > 0); + set_interval_object (new, parent); return new; } -/* Make the interval TARGET have exactly the properties of SOURCE */ +/* Make the interval TARGET have exactly the properties of SOURCE. */ void copy_properties (register INTERVAL source, register INTERVAL target) @@ -187,10 +177,10 @@ intervals_equal (INTERVAL i0, INTERVAL i1) Lisp_Object i1_cdr, i1_val; if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1)) - return 1; + return true; if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1)) - return 0; + return false; i0_cdr = i0->plist; i1_cdr = i1->plist; @@ -199,31 +189,31 @@ intervals_equal (INTERVAL i0, INTERVAL i1) i0_sym = XCAR (i0_cdr); i0_cdr = XCDR (i0_cdr); if (!CONSP (i0_cdr)) - return 0; + return false; i1_val = i1->plist; while (CONSP (i1_val) && !EQ (XCAR (i1_val), i0_sym)) { i1_val = XCDR (i1_val); if (!CONSP (i1_val)) - return 0; + return false; i1_val = XCDR (i1_val); } /* i0 has something i1 doesn't. */ if (EQ (i1_val, Qnil)) - return 0; + return false; /* i0 and i1 both have sym, but it has different values in each. */ if (!CONSP (i1_val) || (i1_val = XCDR (i1_val), !CONSP (i1_val)) || !EQ (XCAR (i1_val), XCAR (i0_cdr))) - return 0; + return false; i0_cdr = XCDR (i0_cdr); i1_cdr = XCDR (i1_cdr); if (!CONSP (i1_cdr)) - return 0; + return false; i1_cdr = XCDR (i1_cdr); } @@ -343,39 +333,43 @@ root_interval (INTERVAL interval) */ static INTERVAL -rotate_right (INTERVAL interval) +rotate_right (INTERVAL A) { - INTERVAL i; - INTERVAL B = interval->left; - ptrdiff_t old_total = interval->total_length; + INTERVAL B = A->left; + INTERVAL c = B->right; + ptrdiff_t old_total = A->total_length; + + eassert (old_total > 0); + eassert (LENGTH (A) > 0); + eassert (LENGTH (B) > 0); /* Deal with any Parent of A; make it point to B. */ - if (! ROOT_INTERVAL_P (interval)) + if (! ROOT_INTERVAL_P (A)) { - if (AM_LEFT_CHILD (interval)) - set_interval_left (INTERVAL_PARENT (interval), B); + if (AM_LEFT_CHILD (A)) + set_interval_left (INTERVAL_PARENT (A), B); else - set_interval_right (INTERVAL_PARENT (interval), B); + set_interval_right (INTERVAL_PARENT (A), B); } - copy_interval_parent (B, interval); + copy_interval_parent (B, A); - /* Make B the parent of A */ - i = B->right; - set_interval_right (B, interval); - set_interval_parent (interval, B); + /* Make B the parent of A. */ + set_interval_right (B, A); + set_interval_parent (A, 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 (A, c); + if (c) + set_interval_parent (c, A); /* 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 (0 <= TOTAL_LENGTH (interval)); + A->total_length -= B->total_length - TOTAL_LENGTH (c); + eassert (TOTAL_LENGTH (A) > 0); + eassert (LENGTH (A) > 0); /* B must have the same total length of A. */ B->total_length = old_total; - eassert (0 <= TOTAL_LENGTH (B)); + eassert (LENGTH (B) > 0); return B; } @@ -390,39 +384,43 @@ rotate_right (INTERVAL interval) */ static INTERVAL -rotate_left (INTERVAL interval) +rotate_left (INTERVAL A) { - INTERVAL i; - INTERVAL B = interval->right; - ptrdiff_t old_total = interval->total_length; + INTERVAL B = A->right; + INTERVAL c = B->left; + ptrdiff_t old_total = A->total_length; + + eassert (old_total > 0); + eassert (LENGTH (A) > 0); + eassert (LENGTH (B) > 0); /* Deal with any parent of A; make it point to B. */ - if (! ROOT_INTERVAL_P (interval)) + if (! ROOT_INTERVAL_P (A)) { - if (AM_LEFT_CHILD (interval)) - set_interval_left (INTERVAL_PARENT (interval), B); + if (AM_LEFT_CHILD (A)) + set_interval_left (INTERVAL_PARENT (A), B); else - set_interval_right (INTERVAL_PARENT (interval), B); + set_interval_right (INTERVAL_PARENT (A), B); } - copy_interval_parent (B, interval); + copy_interval_parent (B, A); - /* Make B the parent of A */ - i = B->left; - set_interval_left (B, interval); - set_interval_parent (interval, B); + /* Make B the parent of A. */ + set_interval_left (B, A); + set_interval_parent (A, 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 (A, c); + if (c) + set_interval_parent (c, A); /* 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 (0 <= TOTAL_LENGTH (interval)); + A->total_length -= B->total_length - TOTAL_LENGTH (c); + eassert (TOTAL_LENGTH (A) > 0); + eassert (LENGTH (A) > 0); /* B must have the same total length of A. */ B->total_length = old_total; - eassert (0 <= TOTAL_LENGTH (B)); + eassert (LENGTH (B) > 0); return B; } @@ -435,6 +433,9 @@ balance_an_interval (INTERVAL i) { register ptrdiff_t old_diff, new_diff; + eassert (LENGTH (i) > 0); + eassert (TOTAL_LENGTH (i) >= LENGTH (i)); + while (1) { old_diff = LEFT_TOTAL_LENGTH (i) - RIGHT_TOTAL_LENGTH (i); @@ -471,16 +472,16 @@ static INTERVAL balance_possible_root_interval (INTERVAL interval) { Lisp_Object parent; - bool have_parent = 0; - - if (!INTERVAL_HAS_OBJECT (interval) && !INTERVAL_HAS_PARENT (interval)) - return interval; + bool have_parent = false; if (INTERVAL_HAS_OBJECT (interval)) { - have_parent = 1; + have_parent = true; GET_INTERVAL_OBJECT (parent, interval); } + else if (!INTERVAL_HAS_PARENT (interval)) + return interval; + interval = balance_an_interval (interval); if (have_parent) @@ -556,7 +557,7 @@ split_interval_right (INTERVAL interval, ptrdiff_t offset) { set_interval_right (interval, new); new->total_length = new_length; - eassert (0 <= TOTAL_LENGTH (new)); + eassert (LENGTH (new) > 0); } else { @@ -565,7 +566,6 @@ split_interval_right (INTERVAL interval, ptrdiff_t offset) set_interval_parent (interval->right, new); set_interval_right (interval, new); new->total_length = new_length + new->right->total_length; - eassert (0 <= TOTAL_LENGTH (new)); balance_an_interval (new); } @@ -601,7 +601,7 @@ split_interval_left (INTERVAL interval, ptrdiff_t offset) { set_interval_left (interval, new); new->total_length = new_length; - eassert (0 <= TOTAL_LENGTH (new)); + eassert (LENGTH (new) > 0); } else { @@ -610,7 +610,6 @@ split_interval_left (INTERVAL interval, ptrdiff_t offset) set_interval_parent (new->left, new); set_interval_left (interval, new); new->total_length = new_length + new->left->total_length; - eassert (0 <= TOTAL_LENGTH (new)); balance_an_interval (new); } @@ -678,6 +677,7 @@ find_interval (register INTERVAL tree, register ptrdiff_t position) while (1) { + eassert (tree); if (relative_position < LEFT_TOTAL_LENGTH (tree)) { tree = tree->left; @@ -793,12 +793,12 @@ update_interval (register INTERVAL i, ptrdiff_t pos) { if (pos < i->position) { - /* Move left. */ + /* Move left. */ if (pos >= i->position - TOTAL_LENGTH (i->left)) { i->left->position = i->position - TOTAL_LENGTH (i->left) + LEFT_TOTAL_LENGTH (i->left); - i = i->left; /* Move to the left child */ + i = i->left; /* Move to the left child. */ } else if (NULL_PARENT (i)) error ("Point before start of properties"); @@ -808,12 +808,12 @@ update_interval (register INTERVAL i, ptrdiff_t pos) } else if (pos >= INTERVAL_LAST_POS (i)) { - /* Move right. */ + /* Move right. */ if (pos < INTERVAL_LAST_POS (i) + TOTAL_LENGTH (i->right)) { i->right->position = INTERVAL_LAST_POS (i) + LEFT_TOTAL_LENGTH (i->right); - i = i->right; /* Move to the right child */ + i = i->right; /* Move to the right child. */ } else if (NULL_PARENT (i)) error ("Point %"pD"d after end of properties", pos); @@ -960,7 +960,6 @@ adjust_intervals_for_insertion (INTERVAL tree, for (temp = prev ? prev : i; temp; temp = INTERVAL_PARENT_OR_NULL (temp)) { temp->total_length += length; - eassert (0 <= TOTAL_LENGTH (temp)); temp = balance_possible_root_interval (temp); } @@ -1016,7 +1015,6 @@ adjust_intervals_for_insertion (INTERVAL tree, for (temp = i; temp; temp = INTERVAL_PARENT_OR_NULL (temp)) { temp->total_length += length; - eassert (0 <= TOTAL_LENGTH (temp)); temp = balance_possible_root_interval (temp); } } @@ -1218,9 +1216,10 @@ delete_node (register INTERVAL i) this = this->left; this->total_length += migrate_amt; } - eassert (0 <= TOTAL_LENGTH (this)); set_interval_left (this, migrate); set_interval_parent (migrate, this); + eassert (LENGTH (this) > 0); + eassert (LENGTH (i->right) > 0); return i->right; } @@ -1300,7 +1299,7 @@ interval_deletion_adjustment (register INTERVAL tree, register ptrdiff_t from, relative_position, amount); tree->total_length -= subtract; - eassert (0 <= TOTAL_LENGTH (tree)); + eassert (LENGTH (tree) > 0); return subtract; } /* Right branch. */ @@ -1315,7 +1314,7 @@ interval_deletion_adjustment (register INTERVAL tree, register ptrdiff_t from, relative_position, amount); tree->total_length -= subtract; - eassert (0 <= TOTAL_LENGTH (tree)); + eassert (LENGTH (tree) > 0); return subtract; } /* Here -- this node. */ @@ -1330,7 +1329,7 @@ interval_deletion_adjustment (register INTERVAL tree, register ptrdiff_t from, amount = my_amount; tree->total_length -= amount; - eassert (0 <= TOTAL_LENGTH (tree)); + eassert (LENGTH (tree) >= 0); if (LENGTH (tree) == 0) delete_interval (tree); @@ -1372,7 +1371,7 @@ adjust_intervals_for_deletion (struct buffer *buffer, if (ONLY_INTERVAL_P (tree)) { tree->total_length -= length; - eassert (0 <= TOTAL_LENGTH (tree)); + eassert (LENGTH (tree) > 0); return; } @@ -1406,10 +1405,7 @@ offset_intervals (struct buffer *buffer, ptrdiff_t start, ptrdiff_t length) adjust_intervals_for_insertion (buffer_intervals (buffer), start, length); else - { - lint_assume (- TYPE_MAXIMUM (ptrdiff_t) <= length); - adjust_intervals_for_deletion (buffer, start, -length); - } + adjust_intervals_for_deletion (buffer, start, -length); } /* Merge interval I with its lexicographic successor. The resulting @@ -1435,19 +1431,19 @@ merge_interval_right (register INTERVAL i) while (! NULL_LEFT_CHILD (successor)) { successor->total_length += absorb; - eassert (0 <= TOTAL_LENGTH (successor)); + eassert (LENGTH (successor) > 0); successor = successor->left; } successor->total_length += absorb; - eassert (0 <= TOTAL_LENGTH (successor)); + eassert (LENGTH (successor) > 0); delete_interval (i); return successor; } /* Zero out this interval. */ i->total_length -= absorb; - eassert (0 <= TOTAL_LENGTH (i)); + eassert (TOTAL_LENGTH (i) >= 0); successor = i; while (! NULL_PARENT (successor)) /* It's above us. Subtract as @@ -1462,7 +1458,7 @@ merge_interval_right (register INTERVAL i) successor = INTERVAL_PARENT (successor); successor->total_length -= absorb; - eassert (0 <= TOTAL_LENGTH (successor)); + eassert (LENGTH (successor) > 0); } /* This must be the rightmost or last interval and cannot @@ -1491,19 +1487,19 @@ merge_interval_left (register INTERVAL i) while (! NULL_RIGHT_CHILD (predecessor)) { predecessor->total_length += absorb; - eassert (0 <= TOTAL_LENGTH (predecessor)); + eassert (LENGTH (predecessor) > 0); predecessor = predecessor->right; } predecessor->total_length += absorb; - eassert (0 <= TOTAL_LENGTH (predecessor)); + eassert (LENGTH (predecessor) > 0); delete_interval (i); return predecessor; } /* Zero out this interval. */ i->total_length -= absorb; - eassert (0 <= TOTAL_LENGTH (i)); + eassert (TOTAL_LENGTH (i) >= 0); predecessor = i; while (! NULL_PARENT (predecessor)) /* It's above us. Go up, @@ -1518,7 +1514,7 @@ merge_interval_left (register INTERVAL i) predecessor = INTERVAL_PARENT (predecessor); predecessor->total_length -= absorb; - eassert (0 <= TOTAL_LENGTH (predecessor)); + eassert (LENGTH (predecessor) > 0); } /* This must be the leftmost or first interval and cannot @@ -1533,6 +1529,8 @@ reproduce_interval (INTERVAL source) { register INTERVAL target = make_interval (); + eassert (LENGTH (source) > 0); + target->total_length = source->total_length; target->position = source->position; @@ -1543,6 +1541,7 @@ reproduce_interval (INTERVAL source) if (! NULL_RIGHT_CHILD (source)) set_interval_right (target, reproduce_tree (source->right, target)); + eassert (LENGTH (target) > 0); return target; } @@ -1771,7 +1770,7 @@ lookup_char_property (Lisp_Object plist, Lisp_Object prop, bool textprop) if (! NILP (fallback)) return fallback; - /* Check for alternative properties */ + /* Check for alternative properties. */ tail = Fassq (prop, Vchar_property_alias_alist); if (! NILP (tail)) { @@ -1794,8 +1793,7 @@ temp_set_point_both (struct buffer *buffer, ptrdiff_t charpos, ptrdiff_t bytepos) { /* In a single-byte buffer, the two positions must be equal. */ - if (BUF_ZV (buffer) == BUF_ZV_BYTE (buffer)) - eassert (charpos == bytepos); + eassert (BUF_ZV (buffer) != BUF_ZV_BYTE (buffer) || charpos == bytepos); eassert (charpos <= bytepos); eassert (charpos <= BUF_ZV (buffer) || BUF_BEGV (buffer) <= charpos); @@ -1821,6 +1819,18 @@ set_point (ptrdiff_t charpos) set_point_both (charpos, buf_charpos_to_bytepos (current_buffer, charpos)); } +/* Set PT from MARKER's clipped position. */ + +void +set_point_from_marker (Lisp_Object marker) +{ + if (XMARKER (marker)->buffer != current_buffer) + signal_error ("Marker points into wrong buffer", marker); + set_point_both + (clip_to_bounds (BEGV, marker_position (marker), ZV), + clip_to_bounds (BEGV_BYTE, marker_byte_position (marker), ZV_BYTE)); +} + /* If there's an invisible character at position POS + TEST_OFFS in the current buffer, and the invisible property has a `stickiness' such that inserting a character at position POS would inherit the property it, @@ -2196,20 +2206,15 @@ get_property_and_range (ptrdiff_t pos, Lisp_Object prop, Lisp_Object *val, /* Return the proper local keymap TYPE for position POSITION in BUFFER; TYPE should be one of `keymap' or `local-map'. Use the map specified by the PROP property, if any. Otherwise, if TYPE is - `local-map' use BUFFER's local map. - - POSITION must be in the accessible part of BUFFER. */ + `local-map' use BUFFER's local map. */ Lisp_Object -get_local_map (register ptrdiff_t position, register struct buffer *buffer, - Lisp_Object type) +get_local_map (ptrdiff_t position, struct buffer *buffer, Lisp_Object type) { Lisp_Object prop, lispy_position, lispy_buffer; ptrdiff_t old_begv, old_zv, old_begv_byte, old_zv_byte; - /* Perhaps we should just change `position' to the limit. */ - if (position > BUF_ZV (buffer) || position < BUF_BEGV (buffer)) - emacs_abort (); + position = clip_to_bounds (BUF_BEGV (buffer), position, BUF_ZV (buffer)); /* Ignore narrowing, so that a local map continues to be valid even if the visible region contains no characters and hence no properties. */ @@ -2231,7 +2236,7 @@ get_local_map (register ptrdiff_t position, register struct buffer *buffer, editing a field with a `local-map' property, we want insertion at the end to obey the `local-map' property. */ if (NILP (prop)) - prop = get_pos_property (lispy_position, type, lispy_buffer); + prop = Fget_pos_property (lispy_position, type, lispy_buffer); SET_BUF_BEGV_BOTH (buffer, old_begv, old_begv_byte); SET_BUF_ZV_BOTH (buffer, old_zv, old_zv_byte); @@ -2272,7 +2277,7 @@ copy_intervals (INTERVAL tree, ptrdiff_t start, ptrdiff_t length) new->position = 0; got = (LENGTH (i) - (start - i->position)); new->total_length = length; - eassert (0 <= TOTAL_LENGTH (new)); + eassert (TOTAL_LENGTH (new) >= 0); copy_properties (i, new); t = new; @@ -2355,7 +2360,7 @@ set_intervals_multibyte_1 (INTERVAL i, bool multi_flag, i->total_length = end - start; else i->total_length = end_byte - start_byte; - eassert (0 <= TOTAL_LENGTH (i)); + eassert (TOTAL_LENGTH (i) >= 0); if (TOTAL_LENGTH (i) == 0) { @@ -2433,7 +2438,7 @@ set_intervals_multibyte_1 (INTERVAL i, bool multi_flag, end, end_byte); } - /* Rounding to char boundaries can theoretically ake this interval + /* Rounding to char boundaries can theoretically make this interval spurious. If so, delete one child, and copy its property list to this interval. */ if (LEFT_TOTAL_LENGTH (i) + RIGHT_TOTAL_LENGTH (i) >= TOTAL_LENGTH (i))