From 7cbeeabc7e6271948e7bb93020c2e4e50c65f384 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Sun, 9 Oct 2022 19:45:26 -0400 Subject: [PATCH] Tighten up handling of `otick` Move args between `build_overlay` and `add_buffer_overlay`, to try and keep buffer positions together with their buffer. Be more strict in the `otick` values passed to `interval_tree_insert`. Move a few things around to try and reduce dependencies through `.h` files. Fix a thinko bug in `check_tree`. * src/alloc.c (build_overlay): Remove `begin` and `end` args. * src/buffer.c (add_buffer_overlay): Move from `buffer.h`. Add `begin` and `end` args. (copy_overlays): Adjust accordingly. (Fmake_overlay): Use BUF_BEG and BUF_Z; adjust call to `build_overlay` and `add_buffer_overlay`. (Fmove_overlay): Use BUF_BEG and BUF_Z; Use the new `begin` and `end` args of `add_buffer_overlay` so we don't need to use `interval_node_set_region` when moving to a new buffer. (remove_buffer_overlay, set_overlay_region): Move from `buffer.h`. * src/buffer.h (set_overlay_region, add_buffer_overlay) (remove_buffer_overlay): Move to `buffer.c`. (build_overlay): Move from `lisp.h`. (maybe_alloc_buffer_overlays): Delete function (inline into its only caller). * src/itree.c (interval_tree_insert): Move declaration `from buffer.h`. (check_tree): Fix initial offset in call to `recurse_check_tree`. Remove redundant check of the `limit` value. (interval_node_init): Remove `begin` and `end` args. (interval_tree_insert): Mark it as static. Assert that the new node's `otick` should already be uptodate and its new parent as well. (itree_insert_node): New function. (interval_tree_insert_gap): Assert the otick of the removed+added nodes were uptodate and mark them as uptodate again after adjusting their positions. (interval_tree_inherit_offset): Check that the parent is at least as uptodate as the child. * src/lisp.h (build_overlay): Move to `buffer.h`. * src/itree.h (interval_node_init): Adjust accordingly. (interval_tree_insert): Remove declaration. (itree_insert_node): New declaration. --- src/alloc.c | 8 +++----- src/buffer.c | 58 +++++++++++++++++++++++++++++++++++++--------------- src/buffer.h | 35 +------------------------------ src/itree.c | 55 ++++++++++++++++++++++++++++++------------------- src/itree.h | 5 +++-- src/lisp.h | 1 - 6 files changed, 83 insertions(+), 79 deletions(-) diff --git a/src/alloc.c b/src/alloc.c index 50968b7e121..00f2991f250 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -3702,19 +3702,17 @@ build_symbol_with_pos (Lisp_Object symbol, Lisp_Object position) return val; } -/* Return a new overlay with specified START, END and PLIST. */ +/* Return a new (deleted) overlay with PLIST. */ Lisp_Object -build_overlay (ptrdiff_t begin, ptrdiff_t end, - bool front_advance, bool rear_advance, +build_overlay (bool front_advance, bool rear_advance, Lisp_Object plist) { struct Lisp_Overlay *p = ALLOCATE_PSEUDOVECTOR (struct Lisp_Overlay, plist, PVEC_OVERLAY); Lisp_Object overlay = make_lisp_ptr (p, Lisp_Vectorlike); struct interval_node *node = xmalloc (sizeof (*node)); - interval_node_init (node, begin, end, front_advance, - rear_advance, overlay); + interval_node_init (node, front_advance, rear_advance, overlay); p->interval = node; p->buffer = NULL; set_overlay_plist (overlay, plist); diff --git a/src/buffer.c b/src/buffer.c index f59fddcbdeb..e1303f2a880 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -638,6 +638,16 @@ even if it is dead. The return value is never nil. */) return buffer; } +static void +add_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov, + ptrdiff_t begin, ptrdiff_t end) +{ + eassert (! ov->buffer); + if (! b->overlays) + b->overlays = interval_tree_create (); + ov->buffer = b; + itree_insert_node (b->overlays, ov->interval, begin, end); +} /* Copy overlays of buffer FROM to buffer TO. */ @@ -650,11 +660,10 @@ copy_overlays (struct buffer *from, struct buffer *to) ITREE_FOREACH (node, from->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) { Lisp_Object ov = node->data; - Lisp_Object copy = build_overlay (node->begin, node->end, - node->front_advance, + Lisp_Object copy = build_overlay (node->front_advance, node->rear_advance, Fcopy_sequence (OVERLAY_PLIST (ov))); - add_buffer_overlay (to, XOVERLAY (copy)); + add_buffer_overlay (to, XOVERLAY (copy), node->begin, node->end); } } @@ -897,6 +906,15 @@ does not run the hooks `kill-buffer-hook', return buf; } +static void +remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov) +{ + eassert (b->overlays); + eassert (ov->buffer == b); + interval_tree_remove (ov->buffer->overlays, ov->interval); + ov->buffer = NULL; +} + /* Mark OV as no longer associated with its buffer. */ static void @@ -3486,12 +3504,11 @@ for the rear of the overlay advance when text is inserted there temp = beg; beg = end; end = temp; } - ptrdiff_t obeg = clip_to_bounds (BEG, XFIXNUM (beg), b->text->z); - ptrdiff_t oend = clip_to_bounds (obeg, XFIXNUM (end), b->text->z); - ov = build_overlay (obeg, oend, - ! NILP (front_advance), + ptrdiff_t obeg = clip_to_bounds (BUF_BEG (b), XFIXNUM (beg), BUF_Z (b)); + ptrdiff_t oend = clip_to_bounds (obeg, XFIXNUM (end), BUF_Z (b)); + ov = build_overlay (! NILP (front_advance), ! NILP (rear_advance), Qnil); - add_buffer_overlay (b, XOVERLAY (ov)); + add_buffer_overlay (b, XOVERLAY (ov), obeg, oend); /* We don't need to redisplay the region covered by the overlay, because the overlay has no properties at the moment. */ @@ -3518,6 +3535,15 @@ modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end) modiff_incr (&BUF_OVERLAY_MODIFF (buf), 1); } +INLINE void +set_overlay_region (struct Lisp_Overlay *ov, ptrdiff_t begin, ptrdiff_t end) +{ + eassert (ov->buffer); + begin = clip_to_bounds (BEG, begin, ov->buffer->text->z); + end = clip_to_bounds (begin, end, ov->buffer->text->z); + interval_node_set_region (ov->buffer->overlays, ov->interval, begin, end); +} + DEFUN ("move-overlay", Fmove_overlay, Smove_overlay, 3, 4, 0, doc: /* Set the endpoints of OVERLAY to BEG and END in BUFFER. If BUFFER is omitted, leave OVERLAY in the same buffer it inhabits now. @@ -3528,7 +3554,6 @@ buffer. */) struct buffer *b, *ob = 0; Lisp_Object obuffer; specpdl_ref count = SPECPDL_INDEX (); - ptrdiff_t n_beg, n_end; ptrdiff_t o_beg UNINIT, o_end UNINIT; CHECK_OVERLAY (overlay); @@ -3555,11 +3580,14 @@ buffer. */) temp = beg; beg = end; end = temp; } - specbind (Qinhibit_quit, Qt); + specbind (Qinhibit_quit, Qt); /* FIXME: Why? */ obuffer = Foverlay_buffer (overlay); b = XBUFFER (buffer); + ptrdiff_t n_beg = clip_to_bounds (BUF_BEG (b), XFIXNUM (beg), BUF_Z (b)); + ptrdiff_t n_end = clip_to_bounds (n_beg, XFIXNUM (end), BUF_Z (b)); + if (!NILP (obuffer)) { ob = XBUFFER (obuffer); @@ -3572,13 +3600,11 @@ buffer. */) { if (! NILP (obuffer)) remove_buffer_overlay (XBUFFER (obuffer), XOVERLAY (overlay)); - add_buffer_overlay (XBUFFER (buffer), XOVERLAY (overlay)); + add_buffer_overlay (XBUFFER (buffer), XOVERLAY (overlay), n_beg, n_end); } - /* Set the overlay boundaries, which may clip them. */ - set_overlay_region (XOVERLAY (overlay), XFIXNUM (beg), XFIXNUM (end)); - - n_beg = OVERLAY_START (overlay); - n_end = OVERLAY_END (overlay); + else + interval_node_set_region (b->overlays, XOVERLAY (overlay)->interval, + n_beg, n_end); /* If the overlay has changed buffers, do a thorough redisplay. */ if (!BASE_EQ (buffer, obuffer)) diff --git a/src/buffer.h b/src/buffer.h index a4e3934cad2..288acd4f5ee 100644 --- a/src/buffer.h +++ b/src/buffer.h @@ -1189,6 +1189,7 @@ extern void fix_overlays_before (struct buffer *, ptrdiff_t, ptrdiff_t); extern void mmap_set_vars (bool); extern void restore_buffer (Lisp_Object); extern void set_buffer_if_live (Lisp_Object); +extern Lisp_Object build_overlay (bool, bool, Lisp_Object); /* Return B as a struct buffer pointer, defaulting to the current buffer. */ @@ -1408,40 +1409,6 @@ overlay_end (struct Lisp_Overlay *ov) return interval_node_end (ov->buffer->overlays, ov->interval); } -INLINE void -set_overlay_region (struct Lisp_Overlay *ov, ptrdiff_t begin, ptrdiff_t end) -{ - eassert (ov->buffer); - begin = clip_to_bounds (BEG, begin, ov->buffer->text->z); - end = clip_to_bounds (begin, end, ov->buffer->text->z); - interval_node_set_region (ov->buffer->overlays, ov->interval, begin, end); -} - -INLINE void -maybe_alloc_buffer_overlays (struct buffer *b) -{ - if (! b->overlays) - b->overlays = interval_tree_create (); -} - -INLINE void -add_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov) -{ - eassert (! ov->buffer); - maybe_alloc_buffer_overlays (b); - ov->buffer = b; - interval_tree_insert (b->overlays, ov->interval); -} - -INLINE void -remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov) -{ - eassert (b->overlays); - eassert (ov->buffer == b); - interval_tree_remove (ov->buffer->overlays, ov->interval); - ov->buffer = NULL; -} - /* Return the start of OV in its buffer, or -1 if OV is not associated with any buffer. */ diff --git a/src/itree.c b/src/itree.c index b57c3cc656f..bbab70dac7c 100644 --- a/src/itree.c +++ b/src/itree.c @@ -142,6 +142,7 @@ static void interval_tree_rotate_right (struct interval_tree *, struct interval_ static void interval_tree_insert_fix (struct interval_tree *, struct interval_node *); static void interval_tree_transplant (struct interval_tree *, struct interval_node *, struct interval_node *); static struct interval_generator* interval_generator_create (struct interval_tree *); +static void interval_tree_insert (struct interval_tree *, struct interval_node *); /* The sentinel node, the null node. */ struct interval_node itree_null; @@ -260,11 +261,8 @@ check_tree (struct interval_tree *tree) return true; intmax_t size = 0; - ptrdiff_t offset = tree->root->offset; - ptrdiff_t limit - = recurse_check_tree (tree->root, tree->otick, offset, - PTRDIFF_MIN, PTRDIFF_MAX, &size); - eassert (limit == tree->root->limit + offset); + recurse_check_tree (tree->root, tree->otick, 0, + PTRDIFF_MIN, PTRDIFF_MAX, &size); return true; } @@ -375,12 +373,11 @@ interval_stack_pop (struct interval_stack *stack) void interval_node_init (struct interval_node *node, - ptrdiff_t begin, ptrdiff_t end, bool front_advance, bool rear_advance, Lisp_Object data) { - node->begin = begin; - node->end = max (begin, end); + node->begin = -1; + node->end = -1; node->front_advance = front_advance; node->rear_advance = rear_advance; node->data = data; @@ -488,7 +485,7 @@ interval_tree_size (struct interval_tree *tree) Note, that inserting a node twice results in undefined behaviour. */ -void +static void interval_tree_insert (struct interval_tree *tree, struct interval_node *node) { eassert (node && node->begin <= node->end && node != ITREE_NULL); @@ -497,6 +494,9 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) struct interval_node *parent = ITREE_NULL; struct interval_node *child = tree->root; uintmax_t otick = tree->otick; + /* It's the responsability of the caller to set `otick` on the node, + to "confirm" that the begin/end fields are uptodate. */ + eassert (node->otick == otick); /* Find the insertion point, accumulate node's offset and update ancestors limit values. */ @@ -526,7 +526,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) node->red = true; node->offset = 0; node->limit = node->end; - node->otick = otick; + eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick); /* Fix/update the tree */ ++tree->size; @@ -534,6 +534,16 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) interval_tree_insert_fix (tree, node); } +void +itree_insert_node (struct interval_tree *tree, struct interval_node *node, + ptrdiff_t begin, ptrdiff_t end) +{ + node->begin = begin; + node->end = end; + node->otick = tree->otick; + interval_tree_insert (tree, node); +} + /* Return true, if NODE is a member of TREE. */ static bool @@ -849,6 +859,7 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l { if (length <= 0 || tree->root == ITREE_NULL) return; + uintmax_t ootick = tree->otick; /* FIXME: Don't allocate generator/stack anew every time. */ @@ -907,13 +918,16 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l } /* Reinsert nodes starting at POS having front-advance. */ + uintmax_t notick = tree->otick; nodeptr_and_flag nav; while ((nav = interval_stack_pop (saved), node = nav_nodeptr (nav))) { + eassert (node->otick == ootick); node->begin += length; if (node->end != pos || node->rear_advance) node->end += length; + node->otick = notick; interval_tree_insert (tree, node); } @@ -1123,12 +1137,19 @@ interval_tree_update_limit (struct interval_node *node) static void interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node) { + eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick); if (node->otick == otick) { eassert (node->offset == 0); return; } + /* Offsets can be inherited from dirty nodes (with out of date + otick) during insert and remove. Offsets aren't inherited + downward from the root for these operations so rotations are + performed on potentially "dirty" nodes, where we only make sure + the *local* offsets are all zero. */ + if (node->offset) { node->begin += node->offset; @@ -1140,17 +1161,9 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node) node->right->offset += node->offset; node->offset = 0; } - /* FIXME: I wonder when/why this condition can be false, and more - generally why we'd want to propagate offsets that may not be - fully up-to-date. --stef - - Offsets can be inherited from dirty nodes (with out of date - otick) during insert and remove. Offsets aren't inherited - downward from the root for these operations so rotations are - performed on potentially "dirty" nodes. We could fix this by - always inheriting offsets downward from the root for every insert - and remove. --matt - */ + /* The only thing that matters about `otick` is whether it's equal to + that of the tree. We could also "blindly" inherit from parent->otick, + but we need to tree's `otick` anyway for when there's no parent. */ if (node->parent == ITREE_NULL || node->parent->otick == otick) node->otick = otick; } diff --git a/src/itree.h b/src/itree.h index 7fdc9c07c93..5733ec15305 100644 --- a/src/itree.h +++ b/src/itree.h @@ -112,7 +112,7 @@ enum interval_tree_order { ITREE_PRE_ORDER, }; -void interval_node_init (struct interval_node *, ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object); +void interval_node_init (struct interval_node *, bool, bool, Lisp_Object); ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *); ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *); void interval_node_set_region (struct interval_tree *, struct interval_node *, ptrdiff_t, ptrdiff_t); @@ -120,7 +120,8 @@ struct interval_tree *interval_tree_create (void); void interval_tree_destroy (struct interval_tree *); intmax_t interval_tree_size (struct interval_tree *); void interval_tree_clear (struct interval_tree *); -void interval_tree_insert (struct interval_tree *, struct interval_node *); +void itree_insert_node (struct interval_tree *tree, struct interval_node *node, + ptrdiff_t begin, ptrdiff_t end); struct interval_node *interval_tree_remove (struct interval_tree *, struct interval_node *); struct interval_generator *interval_tree_iter_start (struct interval_tree *, ptrdiff_t, ptrdiff_t, enum interval_tree_order, const char* file, int line); diff --git a/src/lisp.h b/src/lisp.h index 7d838afb5c9..7cd78712814 100644 --- a/src/lisp.h +++ b/src/lisp.h @@ -4415,7 +4415,6 @@ extern Lisp_Object make_float (double); extern void display_malloc_warning (void); extern specpdl_ref inhibit_garbage_collection (void); extern Lisp_Object build_symbol_with_pos (Lisp_Object, Lisp_Object); -extern Lisp_Object build_overlay (ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object); extern void free_cons (struct Lisp_Cons *); extern void init_alloc_once (void); extern void init_alloc (void); -- 2.39.2