From 8a5678906fa1b899c4d111e5ee4334b278f50d48 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Tue, 1 Nov 2022 21:38:55 -0400 Subject: src/buffer.c: Fix interaction between overlays & indirect buffers (bug#58928) * src/buffer.c (adjust_overlays_for_insert) (adjust_overlays_for_delete): Repeat for all buffers sharing the same text. * src/itree.c (itree_insert_gap, itree_delete_gap): Allow an empty tree. * test/src/buffer-tests.el (buffer-tests--overlays-indirect-bug58928): New test. --- src/buffer.c | 34 ++++++++++++++++++++++++++-------- 1 file changed, 26 insertions(+), 8 deletions(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index b67b989326e..3129aa2890e 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3456,19 +3456,37 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr) void adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length) { - /* After an insertion, the lists are still sorted properly, - but we may need to update the value of the overlay center. */ - if (! current_buffer->overlays) - return; - itree_insert_gap (current_buffer->overlays, pos, length); + if (!current_buffer->indirections) + itree_insert_gap (current_buffer->overlays, pos, length); + else + { + struct buffer *base = current_buffer->base_buffer + ? current_buffer->base_buffer + : current_buffer; + Lisp_Object tail, other; + itree_insert_gap (base->overlays, pos, length); + FOR_EACH_LIVE_BUFFER (tail, other) + if (XBUFFER (other)->base_buffer == base) + itree_insert_gap (XBUFFER (other)->overlays, pos, length); + } } void adjust_overlays_for_delete (ptrdiff_t pos, ptrdiff_t length) { - if (! current_buffer->overlays) - return; - itree_delete_gap (current_buffer->overlays, pos, length); + if (!current_buffer->indirections) + itree_delete_gap (current_buffer->overlays, pos, length); + else + { + struct buffer *base = current_buffer->base_buffer + ? current_buffer->base_buffer + : current_buffer; + Lisp_Object tail, other; + itree_delete_gap (base->overlays, pos, length); + FOR_EACH_LIVE_BUFFER (tail, other) + if (XBUFFER (other)->base_buffer == base) + itree_delete_gap (XBUFFER (other)->overlays, pos, length); + } } -- cgit v1.2.1 From a66280162f907a09be23922cc80ac352392adac6 Mon Sep 17 00:00:00 2001 From: Basil L. Contovounesios Date: Wed, 2 Nov 2022 03:50:38 +0200 Subject: Port interval trees to --enable-checking=structs Some names under the interval_* namespace were renamed under the itree_* namespace in commits: 0. f421b58db5 of 2022-10-19 "Prefix all itree.h type names with itree_". 1. 37a1145410 of 2022-10-19 "Rename all exported itree.h functions with the itree_ prefix" Further, some values still referenced in commentary were removed in commits: 2. 258e618364 of 2022-10-17 "Delete the itree_null sentinel node, use NULL everywhere." 3. 2c4a3910b3 of 2022-10-02 "itree: Use a single iterator object" * src/emacs.c (main): Allocate global itree iterator once and for all. * src/alloc.c (mark_overlay): * src/buffer.c (set_overlays_multibyte): * src/itree.c (itree_destroy): Update commentary. (interval_stack_ensure_space, itree_insert_gap): Prefer unsigned-to-unsigned comparisons over signed-to-unsigned. (interval_stack_push_flagged, interval_tree_insert) (interval_tree_contains, itree_iterator_start) (itree_iterator_finish, itree_iterator_next, itree_iterator_narrow): Improve assertions. (itree_init): Rename... (init_itree): ...to this, for consistency with other global init functions. (itree_create): Stop leaking a global iterator allocation on each call. (interval_tree_init): Complete renames of interval_tree -> itree_tree and interval_tree_clear -> itree_clear. (interval_tree_remove_fix): Fix indentation. * src/itree.h: Declare init_itree. (ITREE_FOREACH): Fix typo in commentary. * src/pdumper.c [CHECK_STRUCTS] (dump_interval_node): Use the correct name in the HASH condition and #error message. (dump_overlay, dump_buffer): Update HASH (bug#58975). --- src/buffer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 3129aa2890e..3b0e6f1f9a1 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -982,7 +982,7 @@ set_overlays_multibyte (bool multibyte) struct itree_tree *tree = current_buffer->overlays; const intmax_t size = itree_size (tree); - /* We can't use `interval_node_set_region` at the same time + /* We can't use `itree_node_set_region` at the same time as we iterate over the itree, so we need an auxiliary storage to keep the list of nodes. */ USE_SAFE_ALLOCA; -- cgit v1.2.1 From ff679e16f8bf8a9876fc1a980c372d4e55f3745d Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Thu, 3 Nov 2022 22:44:55 -0400 Subject: itree: Reproduce markers's behavior more faithfully (bug#58928) The most obvious problem was the lack of support for `insert-before-markers`, but the behavior was also different in a few other cases. * src/itree.h (itree_insert_gap): * src/itree.c (itree_insert_gap): Add `before_markers` arg. * src/lisp.h (adjust_overlays_for_insert): * src/buffer.c (adjust_overlays_for_insert): Add `before_markers` arg. * src/insdel.c (adjust_markers_for_replace, adjust_markers_for_insert) (adjust_markers_for_delete): Adjust overlays directly from here. (insert_1_both, insert_from_string_1, insert_from_gap) (insert_from_buffer_1, adjust_after_replace, replace_range) (replace_range_2, del_range_2): Don't adjust overlays explicitly here any more. * test/src/buffer-tests.el (test-overlay-insert-before-markers-empty) (test-overlay-insert-before-markers-non-empty): New tests. --- src/buffer.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 3b0e6f1f9a1..ee0b7e13508 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3454,20 +3454,20 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr) void -adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length) +adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length, bool before_markers) { if (!current_buffer->indirections) - itree_insert_gap (current_buffer->overlays, pos, length); + itree_insert_gap (current_buffer->overlays, pos, length, before_markers); else { struct buffer *base = current_buffer->base_buffer ? current_buffer->base_buffer : current_buffer; Lisp_Object tail, other; - itree_insert_gap (base->overlays, pos, length); + itree_insert_gap (base->overlays, pos, length, before_markers); FOR_EACH_LIVE_BUFFER (tail, other) if (XBUFFER (other)->base_buffer == base) - itree_insert_gap (XBUFFER (other)->overlays, pos, length); + itree_insert_gap (XBUFFER (other)->overlays, pos, length, before_markers); } } -- cgit v1.2.1 From 90a0aac3e8ebfb9f3c1df04deb9c85414f3530c0 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Fri, 4 Nov 2022 11:00:49 -0700 Subject: Pacify gcc -Wanalyzer-null-dereference This is for gcc 12.2.1 20220819 (Red Hat 12.2.1-2) x86-64 when Emacs is configured with --enable-gcc-warnings. * src/buffer.c (Fmove_overlay): Prefer BASE_EQ to EQ in a place where they’re equivalent because the only symbol allowed here is nil. --- src/buffer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index ee0b7e13508..745e62f53f7 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3619,7 +3619,7 @@ buffer. */) o_end = OVERLAY_END (overlay); } - if (! EQ (buffer, obuffer)) + if (! BASE_EQ (buffer, obuffer)) { if (! NILP (obuffer)) remove_buffer_overlay (XBUFFER (obuffer), XOVERLAY (overlay)); -- cgit v1.2.1 From 26d2ac38e9a7486aa56acb6bb0162c8ee091aaca Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Fri, 4 Nov 2022 15:24:40 -0700 Subject: Minor tweaks to the fix for `insert-before-markers' overlay fix (bug#58928) * src/buffer.c (adjust_overlays_for_insert): wrap to less than 80 chars. * src/itree.c: document BEFORE_MARKERS. --- src/buffer.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 745e62f53f7..390ccff5c8a 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3467,7 +3467,8 @@ adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length, bool before_markers itree_insert_gap (base->overlays, pos, length, before_markers); FOR_EACH_LIVE_BUFFER (tail, other) if (XBUFFER (other)->base_buffer == base) - itree_insert_gap (XBUFFER (other)->overlays, pos, length, before_markers); + itree_insert_gap (XBUFFER (other)->overlays, pos, length, + before_markers); } } -- cgit v1.2.1 From 6e5ec085510ccf52ac6cb07c3a1a2778324a1d89 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Sat, 5 Nov 2022 17:22:37 -0400 Subject: buffer.c: evaporate overlays in all indirect buffers This fixes bug#58928. The patch works by moving the `evaporate_overlays` check closer to `itree_delete_gap`. * src/buffer.c (adjust_overlays_for_delete_in_buffer): New function, integrating the functionality of `evaporate_overlays`. (adjust_overlays_for_delete): Use it. (evaporate_overlays): Delete function. * src/buffer.h (evaporate_overlays): Delete declaration. * src/insdel.c (adjust_markers_for_replace): Minor optimization. (adjust_after_replace, replace_range, replace_range_2, del_range_2): Don't call `evaporate_overlays`. * test/src/buffer-tests.el (buffer-tests--overlays-indirect-evaporate): Remove the `:expected-result :failed` attribute. --- src/buffer.c | 51 +++++++++++++++++++++++++++++---------------------- 1 file changed, 29 insertions(+), 22 deletions(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 390ccff5c8a..ec2d34daf89 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3472,21 +3472,47 @@ adjust_overlays_for_insert (ptrdiff_t pos, ptrdiff_t length, bool before_markers } } +static void +adjust_overlays_for_delete_in_buffer (struct buffer * buf, + ptrdiff_t pos, ptrdiff_t length) +{ + Lisp_Object hit_list = Qnil; + struct itree_node *node; + + /* Ideally, the evaporate check would be done directly within + `itree_delete_gap`, but that code isn't supposed to know about overlays, + only about `itree_node`s, so it would break an abstraction boundary. */ + itree_delete_gap (buf->overlays, pos, length); + + /* Delete any zero-sized overlays at position POS, if the `evaporate' + property is set. */ + + ITREE_FOREACH (node, buf->overlays, pos, pos, ASCENDING) + { + if (node->end == pos && node->begin == pos + && ! NILP (Foverlay_get (node->data, Qevaporate))) + hit_list = Fcons (node->data, hit_list); + } + + for (; CONSP (hit_list); hit_list = XCDR (hit_list)) + Fdelete_overlay (XCAR (hit_list)); +} + void adjust_overlays_for_delete (ptrdiff_t pos, ptrdiff_t length) { if (!current_buffer->indirections) - itree_delete_gap (current_buffer->overlays, pos, length); + adjust_overlays_for_delete_in_buffer (current_buffer, pos, length); else { struct buffer *base = current_buffer->base_buffer ? current_buffer->base_buffer : current_buffer; Lisp_Object tail, other; - itree_delete_gap (base->overlays, pos, length); + adjust_overlays_for_delete_in_buffer (base, pos, length); FOR_EACH_LIVE_BUFFER (tail, other) if (XBUFFER (other)->base_buffer == base) - itree_delete_gap (XBUFFER (other)->overlays, pos, length); + adjust_overlays_for_delete_in_buffer (XBUFFER (other), pos, length); } } @@ -4099,25 +4125,6 @@ call_overlay_mod_hooks (Lisp_Object list, Lisp_Object overlay, bool after, } } -/* Delete any zero-sized overlays at position POS, if the `evaporate' - property is set. */ -void -evaporate_overlays (ptrdiff_t pos) -{ - Lisp_Object hit_list = Qnil; - struct itree_node *node; - - ITREE_FOREACH (node, current_buffer->overlays, pos, pos, ASCENDING) - { - if (node->end == pos - && ! NILP (Foverlay_get (node->data, Qevaporate))) - hit_list = Fcons (node->data, hit_list); - } - - for (; CONSP (hit_list); hit_list = XCDR (hit_list)) - Fdelete_overlay (XCAR (hit_list)); -} - /*********************************************************************** Allocation with mmap ***********************************************************************/ -- cgit v1.2.1 From 435861a3baa3dbe9deff7346161887883508dee6 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Thu, 10 Nov 2022 12:18:18 +0200 Subject: ; * src/buffer.c (Foverlays_in): Doc fix. (Bug#59067) --- src/buffer.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index ec2d34daf89..9be2c4a970e 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -3835,7 +3835,9 @@ and also contained within the specified region. Empty overlays are included in the result if they are located at BEG, between BEG and END, or at END provided END denotes the position at the -end of the accessible part of the buffer. */) +end of the accessible part of the buffer. + +The resulting list of overlays is in an arbitrary unpredictable order. */) (Lisp_Object beg, Lisp_Object end) { ptrdiff_t len, noverlays; -- cgit v1.2.1 From 091e0f04ffe494ee4cddb67670f0c495a7c9b691 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Thu, 17 Nov 2022 18:09:37 -0500 Subject: itree.c: Get rid of the old iterator code Only use the new iterator which relies on a fixed size (and small) state in the iterator. This makes non-local exits safe within ITREE_FOREACH loops. * src/itree.c (make_nav, nav_nodeptr, nav_flag, itree_stack_clear) (itree_stack_push_flagged): Delete functions. (nodeptr_and_flag): Delete type. (struct itree_stack): Make the array hold plain pointers instead. (itree_stack_push): Inline the former code of `itree_stack_push_flagged`. (itree_stack_pop): Change return type. (itree_contains): Don't call `ITREE_FOREACH_ABORT` any more. (itree_insert_gap): Simplify access to the stack of nodes. (itree_delete_gap, itree_insert_gap): Adjust code to new return type of `itree_stack_pop`. (itree_iterator_finish): Delete function. (itree_iterator_start): Don't setup the `stack` field any more. (itree_iterator_next): Delete function. (itree_iter_next): Rename to `itree_iterator_next` and make it non-static. (itree_iterator_narrow): Don't check the `running` flag any more. * src/itree.h (itree_iterator_finish): Remove declaration. (struct itree_iterator): Remove the `stack` and `running` fields. (ITREE_FOREACH_ABORT): Delete macro. (ITREE_FOREACH): Don't call `itree_iterator_finish` any more. * src/xdisp.c (strings_with_newlines): * src/buffer.c (overlays_in, next_overlay_change, overlay_touches_p): Don't call `ITREE_FOREACH_ABORT` any more. --- src/buffer.c | 12 ++---------- 1 file changed, 2 insertions(+), 10 deletions(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 9be2c4a970e..4da5b451d0f 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -2985,17 +2985,13 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, if (node->begin > end) { next = min (next, node->begin); - ITREE_FOREACH_ABORT (); break; } else if (node->begin == end) { next = node->begin; if ((! empty || end < ZV) && beg < end) - { - ITREE_FOREACH_ABORT (); - break; - } + break; if (empty && node->begin != node->end) continue; } @@ -3050,7 +3046,6 @@ next_overlay_change (ptrdiff_t pos) of pos, because the search is limited to [pos,next) . */ eassert (node->begin < next); next = node->begin; - ITREE_FOREACH_ABORT (); break; } else if (node->begin < node->end && node->end < next) @@ -3155,10 +3150,7 @@ overlay_touches_p (ptrdiff_t pos) pos. */ ITREE_FOREACH (node, current_buffer->overlays, pos - 1, pos + 1, DESCENDING) if (node->begin == pos || node->end == pos) - { - ITREE_FOREACH_ABORT (); - return true; - } + return true; return false; } -- cgit v1.2.1 From 5525bd39322a66cf4133a2593d6349e4d75d8b6a Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Fri, 18 Nov 2022 11:11:46 -0500 Subject: itree: Make sure a deleted overlay has NULL pointer fields * src/buffer.c (delete_all_overlays): Use POST_ORDER to set the node's pointers to NULL, as god intended. * src/itree.c (itree_insert_node): Uncomment the assertion accordingly. --- src/buffer.c | 17 +++++++---------- 1 file changed, 7 insertions(+), 10 deletions(-) (limited to 'src/buffer.c') diff --git a/src/buffer.c b/src/buffer.c index 4da5b451d0f..d948aaa2662 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -937,19 +937,16 @@ delete_all_overlays (struct buffer *b) if (! b->overlays) return; - /* FIXME: This loop sets the overlays' `buffer` field to NULL but - doesn't set the itree_nodes' `parent`, `left` and `right` - fields accordingly. I believe it's harmless, but a bit untidy since - other parts of the code are careful to set those fields to NULL when - the overlay is deleted. - Of course, we can't set them to NULL from within the iteration - because the iterator may need them (tho we could if we added - an ITREE_POST_ORDER iteration order). */ - ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) + /* The general rule is that the tree cannot be modified from within + ITREE_FOREACH, but here we bend this rule a little because we know + that the POST_ORDER iterator will not need to look at `node` again. */ + ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, POST_ORDER) { modify_overlay (b, node->begin, node->end); - /* Where are the nodes freed ? --ap */ XOVERLAY (node->data)->buffer = NULL; + node->parent = NULL; + node->left = NULL; + node->right = NULL; } itree_clear (b->overlays); } -- cgit v1.2.1