From 8d7bdfa3fca076b34aaf86548d3243bee11872ad Mon Sep 17 00:00:00 2001 From: Andreas Politz Date: Tue, 7 Feb 2017 17:56:50 +0100 Subject: Provide a new tree data-structure for overlays. * src/itree.c (interval_generator_narrow, interval_generator_next) (interval_node_init, interval_node_begin) (interval_node_end, interval_node_set_region) (interval_tree_create, interval_tree_clear) (interval_tree_init, interval_tree_destroy) (interval_tree_size, interval_tree_insert) (interval_tree_contains, interval_tree_remove) (interval_tree_validate, interval_tree_iter_start) (interval_tree_iter_finish, interval_tree_iter_next) (interval_tree_iter_ensure_space, interval_tree_max_height) (interval_tree_insert_gap, interval_tree_delete_gap) (interval_generator_create, interval_generator_reset) (interval_generator_ensure_space, interval_node_intersects) (interval_generator_next, interval_generator_narrow) (interval_generator_destroy, interval_stack_create) (interval_stack_destroy, interval_stack_clear) (interval_stack_ensure_space, interval_stack_push) (interval_stack_push_flagged, interval_stack_pop) (interval_tree_update_limit, interval_tree_inherit_offset) (interval_tree_propagate_limit, interval_tree_rotate_left) (interval_tree_rotate_right, interval_tree_insert_fix) (interval_tree_remove_fix, interval_tree_transplant) (interval_tree_subtree_min): New file and new functions. * src/itree.h: New file. * configure.ac: Create Makefile for manual overlay tests. * src/Makefile.in: Add itree.o target. * src/alloc.c (build_overlay, mark_overlay, mark_buffer) (sweep_misc, sweep_buffers): Adapt to new tree data-structure. * src/buffer.c (overlays_in, overlays_at): Remove unused arguments prev_ptr and change_req, adapt to new data-structure and reuse code. (copy_overlays, drop_overlays, delete_all_overlays) (reset_buffer, kill-buffer, buffer-swap-text, next_overlay_change) (previous_overlay_change, mouse_face_overlay_overlaps) (disable_line_numbers_overlay_at_eob, overlay_touches_p) (overlay_strings, adjust_overlays_for_insert) (adjust_overlays_for_delete, overlayp, make-overlay, move-overlay) (delete-overlay, overlay-start, overlay-end, overlay-buffer) (overlay-properties, overlays-at, overlays-in) (next-overlay-change, previous-overlay-change, overlay-put) (overlay-get, report_overlay_modification, evaporate_overlays) (init_buffer_once): Adapt to changes and tree data-structure. (overlay-lists, overlay-recenter): Funtions are now obsolete, but kept anyway. (set_buffer_overlays_before, set_buffer_overlays_after) (recenter_overlay_lists,fix_start_end_in_overlays,fix_overlays_before) (unchain_overlay,): Removed functions of the old list data-structure. (swap_buffer_overlays, make_sortvec_item): New functions. (sort_overlays): Adapt to changes and tree data-structure. (sortvec): Moved to buffer.h . (make_lispy_interval_node, overlay_tree, overlay-tree) [ITREE_DEBUG]: New debugging functions. * src/buffer.h (overlays_before, overlays_after): Removed struct member of the list data-structure. (overlays): Added tree struct member. (sortvec): Moved here from buffer.c . (GET_OVERLAYS_AT): Adapt to changes. (set_buffer_intervals, OVERLAY_START, OVERLAY_END, OVERLAY_PLIST): Adapt to tree data-structure. (OVERLAY_POSITION): Removed macro of the list data-structure. (OVERLAY_REAR_ADVANCE_P, OVERLAY_FRONT_ADVANCE_P): New macros. (overlay_start, overlay_end) (set_overlay_region, maybe_alloc_buffer_overlays) (free_buffer_overlays, add_buffer_overlay) (remove_buffer_overlay, buffer_overlay_iter_start) (buffer_overlay_iter_next, buffer_overlay_iter_finish) (buffer_overlay_iter_narrow): New functions. (compare_overlays, make_sortvec_item): Export functions. * src/editfns.c (overlays_around): Reuse overlays_in. (get-pos-property): Adapt to tree data-structure. (transpose-regions): Remove call to deleted function. * src/fileio.c: (insert-file-contents): Remove references to deleted struct member. * src/fns.c (internal_equal): Adapt to tree data-structure. * src/indent.c (check_display_width): Adapt to tree data-structure. (skip_invisible): Remove call to deleted function. * src/insdel.c (adjust_markers_for_insert): Remove calls to deleted functions. * src/intervals.c (adjust_for_invis_intang): Adapt to tree data-structure. * src/keyboard.c (adjust_point_for_property): Adapt to tree data-structure. * src/lisp.h (Lisp_Overlay): Modified struct layout. * src/print.c (temp_output_buffer_setup, print_object): Adapt to tree data-structure. * src/textprop.c (get_char_property_and_overlay): Adapt to tree data-structure. Take advantage of the new data-structure. * src/window.h (overlay_matches_window): New function. * src/xdisp.h (next_overlay_change): Removed function. Use next-overlay-change, which does not use xmalloc anymore. (handle_single_display_spec, load_overlay_strings) (back_to_previous_visible_line_start, note_mouse_highlight): Adapt to tree data-structure. (move_it_to, display_line): Remove calls to deleted functions. * src/xfaces.c (face_at_buffer_position): Adapt to changes and tree data-structure. * test/src/buffer-tests.el: Many tests regarding overlays added. * test/manual/noverlay/itree-tests.c: New file with tests of the tree data-structure on the C level. * test/manual/noverlay/Makefile.in: New file. * test/manual/noverlay/check-sanitize.sh: New file. * test/manual/noverlay/emacs-compat.h: New file. * test/manual/noverlay/.gitignore: New file. * test/manual/noverlay/overlay-perf.el: New file providing performance tests. * test/manual/noverlay/many-errors.h: New file. --- src/editfns.c | 56 ++++++-------------------------------------------------- 1 file changed, 6 insertions(+), 50 deletions(-) (limited to 'src/editfns.c') diff --git a/src/editfns.c b/src/editfns.c index 4dcf7cbe6ef..8628b1b2d49 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -457,51 +457,9 @@ If you set the marker not to point anywhere, the buffer will have no mark. */) of length LEN. */ static ptrdiff_t -overlays_around (EMACS_INT pos, Lisp_Object *vec, ptrdiff_t len) +overlays_around (ptrdiff_t pos, Lisp_Object *vec, ptrdiff_t len) { - Lisp_Object overlay, start, end; - struct Lisp_Overlay *tail; - ptrdiff_t startpos, endpos; - ptrdiff_t idx = 0; - - for (tail = current_buffer->overlays_before; tail; tail = tail->next) - { - XSETMISC (overlay, tail); - - end = OVERLAY_END (overlay); - endpos = OVERLAY_POSITION (end); - if (endpos < pos) - break; - start = OVERLAY_START (overlay); - startpos = OVERLAY_POSITION (start); - if (startpos <= pos) - { - if (idx < len) - vec[idx] = overlay; - /* Keep counting overlays even if we can't return them all. */ - idx++; - } - } - - for (tail = current_buffer->overlays_after; tail; tail = tail->next) - { - XSETMISC (overlay, tail); - - start = OVERLAY_START (overlay); - startpos = OVERLAY_POSITION (start); - if (pos < startpos) - break; - end = OVERLAY_END (overlay); - endpos = OVERLAY_POSITION (end); - if (pos <= endpos) - { - if (idx < len) - vec[idx] = overlay; - idx++; - } - } - - return idx; + return overlays_in (pos - 1, pos, false, &vec, &len, false, NULL); } DEFUN ("get-pos-property", Fget_pos_property, Sget_pos_property, 2, 3, 0, @@ -561,11 +519,10 @@ at POSITION. */) if (!NILP (tem)) { /* Check the overlay is indeed active at point. */ - Lisp_Object start = OVERLAY_START (ol), finish = OVERLAY_END (ol); - if ((OVERLAY_POSITION (start) == posn - && XMARKER (start)->insertion_type == 1) - || (OVERLAY_POSITION (finish) == posn - && XMARKER (finish)->insertion_type == 0)) + if ((OVERLAY_START (ol) == posn + && OVERLAY_FRONT_ADVANCE_P (ol)) + || (OVERLAY_END (ol) == posn + && ! OVERLAY_REAR_ADVANCE_P (ol))) ; /* The overlay will not cover a char inserted at point. */ else { @@ -5385,7 +5342,6 @@ Transposing beyond buffer boundaries is an error. */) transpose_markers (start1, end1, start2, end2, start1_byte, start1_byte + len1_byte, start2_byte, start2_byte + len2_byte); - fix_start_end_in_overlays (start1, end2); } else { -- cgit v1.2.3 From 048b0fd0db1bae116ca8dfda461eb7de609d8b53 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Thu, 8 Sep 2022 22:50:41 +0300 Subject: ; * src/editfns.c (syms_of_editfns) : Doc fix. --- src/editfns.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'src/editfns.c') diff --git a/src/editfns.c b/src/editfns.c index cd5cddee79f..b774e79337f 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -4603,10 +4603,7 @@ it to be non-nil. */); DEFSYM (Qrestrictions_locked, "restrictions-locked"); DEFVAR_LISP ("restrictions-locked", Vrestrictions_locked, - doc: /* If non-nil, restrictions are currently locked. - -This happens when `narrow-to-region', which see, is called from Lisp -with an optional argument LOCK non-nil. */); + doc: /* If non-nil, restrictions are currently locked. */); Vrestrictions_locked = Qnil; Funintern (Qrestrictions_locked, Qnil); -- cgit v1.2.3 From d52d6e1e106117eb4bba81a65e256e2e793037b6 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Tue, 4 Oct 2022 14:23:20 +0300 Subject: Avoid assertion violations in STRING_CHAR * src/xdisp.c (handle_composition_prop): * src/editfns.c (styled_format): Don't call 'STRING_CHAR' on unibyte strings. This avoids assertion violation in 'string_char_and_length'. --- src/editfns.c | 4 +++- src/xdisp.c | 5 ++++- 2 files changed, 7 insertions(+), 2 deletions(-) (limited to 'src/editfns.c') diff --git a/src/editfns.c b/src/editfns.c index b774e79337f..c1414071c79 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -3552,7 +3552,9 @@ styled_format (ptrdiff_t nargs, Lisp_Object *args, bool message) || conversion == 'o' || conversion == 'x' || conversion == 'X')) error ("Invalid format operation %%%c", - STRING_CHAR ((unsigned char *) format - 1)); + multibyte_format + ? STRING_CHAR ((unsigned char *) format - 1) + : *((unsigned char *) format - 1)); else if (! (FIXNUMP (arg) || ((BIGNUMP (arg) || FLOATP (arg)) && conversion != 'c'))) error ("Format specifier doesn't match argument type"); diff --git a/src/xdisp.c b/src/xdisp.c index 818cf5e3f8f..9534e27843e 100644 --- a/src/xdisp.c +++ b/src/xdisp.c @@ -6312,7 +6312,10 @@ handle_composition_prop (struct it *it) pos_byte = IT_STRING_BYTEPOS (*it); string = it->string; s = SDATA (string) + pos_byte; - it->c = STRING_CHAR (s); + if (STRING_MULTIBYTE (string)) + it->c = STRING_CHAR (s); + else + it->c = *s; } else { -- cgit v1.2.3 From 71b3a37569ffa58f3640a742e31eade42cc26f98 Mon Sep 17 00:00:00 2001 From: Mattias Engdegård Date: Fri, 7 Oct 2022 18:17:40 +0200 Subject: Improved format string error message (bug#58168) * src/editfns.c (styled_format): Better message when the conversion char is non-ASCII from a unibyte format string. --- src/editfns.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'src/editfns.c') diff --git a/src/editfns.c b/src/editfns.c index c1414071c79..3f9618edb08 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -3551,10 +3551,15 @@ styled_format (ptrdiff_t nargs, Lisp_Object *args, bool message) || float_conversion || conversion == 'i' || conversion == 'o' || conversion == 'x' || conversion == 'X')) - error ("Invalid format operation %%%c", - multibyte_format - ? STRING_CHAR ((unsigned char *) format - 1) - : *((unsigned char *) format - 1)); + { + unsigned char *p = (unsigned char *) format - 1; + if (multibyte_format) + error ("Invalid format operation %%%c", STRING_CHAR (p)); + else + error (*p <= 127 ? "Invalid format operation %%%c" + : "Invalid format operation char #o%03o", + *p); + } else if (! (FIXNUMP (arg) || ((BIGNUMP (arg) || FLOATP (arg)) && conversion != 'c'))) error ("Format specifier doesn't match argument type"); -- cgit v1.2.3 From f2a51774a934f29848c5796b46faa5e3b022c401 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Fri, 21 Oct 2022 19:45:13 -0700 Subject: Fix a narrow-to-region vs. overlays-at bug See bug#58703. * src/buffer.c (overlays_in): Add a new TRAILING arg expressing the behavior wanted by `overlays-at', namely to include all overlays beginning at the POS passed to `overlays-at', even if POS is the end of the narrowed region. Pass true and the search range is extended to ZV+1 if END is greater than ZV, just as is done for EMPTY. (overlays_at): Pass 'true' for the new trailing arg. At present this is the only caller passing 'true'. (mouse_face_overlay_overlaps): Pass 'false' for the new trailing arg. (disable_line_numbers_overlay_at_eob): ditto. (Foverlays_in): ditto. * src/editfns.c (overlays_around): ditto. * test/src/buffer-tests.el (sorted-overlays): Add a spot test for this. --- src/buffer.c | 31 +++++++++++++++++++++---------- src/buffer.h | 2 +- src/editfns.c | 2 +- test/src/buffer-tests.el | 39 +++++++++++++++++++++++++++------------ 4 files changed, 50 insertions(+), 24 deletions(-) (limited to 'src/editfns.c') diff --git a/src/buffer.c b/src/buffer.c index fe6b515493e..dcb3c3944b7 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -2943,6 +2943,10 @@ the normal hook `change-major-mode-hook'. */) END, provided END denotes the position at the end of the accessible part of the buffer. + If TRAILING is true, include overlays that begin at END, provided + END denotes the position at the end of the accessible part of the + buffer. + Return the number found, and store them in a vector in *VEC_PTR. Store in *LEN_PTR the size allocated for the vector. Store in *NEXT_PTR the next position after POS where an overlay starts, @@ -2959,7 +2963,8 @@ the normal hook `change-major-mode-hook'. */) ptrdiff_t overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, - Lisp_Object **vec_ptr, ptrdiff_t *len_ptr, bool empty, + Lisp_Object **vec_ptr, ptrdiff_t *len_ptr, + bool empty, bool trailing, ptrdiff_t *next_ptr) { ptrdiff_t idx = 0; @@ -2968,9 +2973,14 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend, Lisp_Object *vec = *vec_ptr; struct itree_node *node; - ITREE_FOREACH (node, current_buffer->overlays, beg, - /* Find empty OV at ZV ? */ - (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING) + /* Extend the search range if overlays beginning at ZV are + wanted. */ + ptrdiff_t search_end = ZV; + if (end >= ZV && (empty || trailing)) + ++search_end; + + ITREE_FOREACH (node, current_buffer->overlays, beg, search_end, + ASCENDING) { if (node->begin > end) { @@ -3022,7 +3032,8 @@ overlays_at (ptrdiff_t pos, bool extend, Lisp_Object **vec_ptr, ptrdiff_t *len_ptr, ptrdiff_t *next_ptr) { - return overlays_in (pos, pos + 1, extend, vec_ptr, len_ptr, false, next_ptr); + return overlays_in (pos, pos + 1, extend, vec_ptr, len_ptr, + false, true, next_ptr); } ptrdiff_t @@ -3085,11 +3096,11 @@ mouse_face_overlay_overlaps (Lisp_Object overlay) size = ARRAYELTS (vbuf); v = vbuf; - n = overlays_in (start, end, 0, &v, &size, true, NULL); + n = overlays_in (start, end, 0, &v, &size, true, false, NULL); if (n > size) { SAFE_NALLOCA (v, 1, n); - overlays_in (start, end, 0, &v, &n, true, NULL); + overlays_in (start, end, 0, &v, &n, true, false, NULL); } for (i = 0; i < n; ++i) @@ -3114,11 +3125,11 @@ disable_line_numbers_overlay_at_eob (void) size = ARRAYELTS (vbuf); v = vbuf; - n = overlays_in (ZV, ZV, 0, &v, &size, false, NULL); + n = overlays_in (ZV, ZV, 0, &v, &size, false, false, NULL); if (n > size) { SAFE_NALLOCA (v, 1, n); - overlays_in (ZV, ZV, 0, &v, &n, false, NULL); + overlays_in (ZV, ZV, 0, &v, &n, false, false, NULL); } for (i = 0; i < n; ++i) @@ -3798,7 +3809,7 @@ end of the accessible part of the buffer. */) /* Put all the overlays we want in a vector in overlay_vec. Store the length in len. */ noverlays = overlays_in (XFIXNUM (beg), XFIXNUM (end), 1, &overlay_vec, &len, - true, NULL); + true, false, NULL); /* Make a list of them all. */ result = Flist (noverlays, overlay_vec); diff --git a/src/buffer.h b/src/buffer.h index ce1b7b27b0f..3ea4125645d 100644 --- a/src/buffer.h +++ b/src/buffer.h @@ -1173,7 +1173,7 @@ extern void compact_buffer (struct buffer *); extern void evaporate_overlays (ptrdiff_t); extern ptrdiff_t overlays_at (ptrdiff_t, bool, Lisp_Object **, ptrdiff_t *, ptrdiff_t *); extern ptrdiff_t overlays_in (ptrdiff_t, ptrdiff_t, bool, Lisp_Object **, - ptrdiff_t *, bool, ptrdiff_t *); + ptrdiff_t *, bool, bool, ptrdiff_t *); extern ptrdiff_t previous_overlay_change (ptrdiff_t); extern ptrdiff_t next_overlay_change (ptrdiff_t); extern ptrdiff_t sort_overlays (Lisp_Object *, ptrdiff_t, struct window *); diff --git a/src/editfns.c b/src/editfns.c index 1af6ea1b11d..00380175859 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -270,7 +270,7 @@ If you set the marker not to point anywhere, the buffer will have no mark. */) static ptrdiff_t overlays_around (ptrdiff_t pos, Lisp_Object *vec, ptrdiff_t len) { - return overlays_in (pos - 1, pos, false, &vec, &len, false, NULL); + return overlays_in (pos - 1, pos, false, &vec, &len, false, false, NULL); } DEFUN ("get-pos-property", Fget_pos_property, Sget_pos_property, 2, 3, 0, diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el index 6d5d9913a01..c6d176cc171 100644 --- a/test/src/buffer-tests.el +++ b/test/src/buffer-tests.el @@ -860,6 +860,33 @@ with parameters from the *Messages* buffer modification." (should-length 1 (overlays-at 15)) (should-length 1 (overlays-at (point-max)))))) +(defun sorted-overlays (overlays) + (sort + (mapcar (lambda (overlay) + (list (overlay-start overlay) + (overlay-end overlay))) + overlays) + (lambda (first second) + (cl-loop for a in first + for b in second + thereis (< a b) + until (> a b))))) + +(defun sorted-overlays-at (pos) + (sorted-overlays (overlays-at pos))) + +(defun sorted-overlays-in (beg end) + (sorted-overlays (overlays-in beg end))) + +(ert-deftest test-overlays-at-narrow-to-region-end () + ;; See bug#58703. + (with-temp-buffer + (insert (make-string 30 ?x)) + (make-overlay 10 11) + (narrow-to-region 10 10) + (should (equal + '((10 11)) + (sorted-overlays-at 10))))) ;; +==========================================================================+ ;; | overlay-in @@ -937,18 +964,6 @@ with parameters from the *Messages* buffer modification." (deftest-overlays-in-1 ae 9 11 (a) (a 10 10)) (deftest-overlays-in-1 af 10 11 (a) (a 10 10)) -(defun sorted-overlays-in (beg end) - (sort - (mapcar (lambda (overlay) - (list (overlay-start overlay) - (overlay-end overlay))) - (overlays-in beg end)) - (lambda (first second) - (cl-loop for a in first - for b in second - thereis (< a b) - until (> a b))))) - ;; behavior for empty range (ert-deftest test-overlays-in-empty-range () (with-temp-buffer -- cgit v1.2.3 From b78be2bf7a9ac8b71d25529d5736373f51852c36 Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Sat, 22 Oct 2022 20:48:10 -0700 Subject: Fix `get-pos-property' for the new overlay implementation. Some of the trickier edge cases weren't handled properly. See bug#58706. * src/editfns.c (overlays_around): Extend the search range past POS by one to fetch overlays beginning at POS. Fetch empty overlays, as they may be extended by an insertion and thus be relevant to `get-pos-property'. Make a note that the function now, unfortunately, may return out of range overlays. (Fget_pos_property): Deal with 'overlays_around' returning out of range overlays. --- src/editfns.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'src/editfns.c') diff --git a/src/editfns.c b/src/editfns.c index 00380175859..c892c02927d 100644 --- a/src/editfns.c +++ b/src/editfns.c @@ -265,12 +265,20 @@ If you set the marker not to point anywhere, the buffer will have no mark. */) /* Find all the overlays in the current buffer that touch position POS. Return the number found, and store them in a vector in VEC - of length LEN. */ + of length LEN. + + Note: this can return overlays that do not touch POS. The caller + should filter these out. */ static ptrdiff_t overlays_around (ptrdiff_t pos, Lisp_Object *vec, ptrdiff_t len) { - return overlays_in (pos - 1, pos, false, &vec, &len, false, false, NULL); + /* Find all potentially rear-advance overlays at (POS - 1). Find + all overlays at POS, so end at (POS + 1). Find even empty + overlays, which due to the way 'overlays-in' works implies that + we might also fetch empty overlays starting at (POS + 1). */ + return overlays_in (pos - 1, pos + 1, false, &vec, &len, + true, false, NULL); } DEFUN ("get-pos-property", Fget_pos_property, Sget_pos_property, 2, 3, 0, @@ -333,7 +341,9 @@ at POSITION. */) if ((OVERLAY_START (ol) == posn && OVERLAY_FRONT_ADVANCE_P (ol)) || (OVERLAY_END (ol) == posn - && ! OVERLAY_REAR_ADVANCE_P (ol))) + && ! OVERLAY_REAR_ADVANCE_P (ol)) + || OVERLAY_START (ol) > posn + || OVERLAY_END (ol) < posn) ; /* The overlay will not cover a char inserted at point. */ else { -- cgit v1.2.3