* Overlays as an AA-tree
@ 2016-09-20 10:32 Joakim Jalap
2016-09-20 12:14 ` Clément Pit--Claudel
` (4 more replies)
0 siblings, 5 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-09-20 10:32 UTC (permalink / raw)
To: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 2015 bytes --]
Hello Emacs devel
I've been working on an item from /etc/TODO on and off for a while now,
but now I have hit a bit of a roadblock.
What I've been looking at is replacing the current implementation of
buffer overlays with a self balanced tree. I chose an AA-tree as that
seemed simple enough for me to grasp :). First I tried using the tree
from intervals.c, but that seemed to be very tightly bound to the
implementation of text properties, so I gave up on that idea.
I got a bit on the way; I managed to get the tree structure in place and
to make it work for some very simple cases. I wrote some simple ert tests
for this. The idea was to be able to compile in three ways: just as
before, with just the new overlay implementation and with both
implementations and a whole lot of easserts. But alas, it turned out to
be too hard for me. There's quite a bit of fiddly code regarding
overlays and ripping it out and replacing it seems to be more than I can
chew. So the status right now is that nothing works... If you define
BOTH_OVERLAYS it will compile but fail an eassert at startup, if you
define NEW_OVERLAYS it doesn't even compile, since there's some stuff I
haven't replaced properly.
Anyway, I basically have two questions for you experts:
1) Is it worth continuing down this path?
2) If so, what's the best way to go about something like this? Replacing
the whole thing at once seems very hard, but I don't really know how to
go about replacing it little by little.
I'm attaching the diff. It is an unholy mess of ifdefs, but the meat of
it is in overlays.[ch] and buffer.c. It is a pretty big diff, and it's
based on master from a few months ago, so I'm not even sure it applies,
but I'd be grateful if somebody could have a quick look at it and try to
see if there's anything worth keeping there. If there's any interest I
could try rebasing it.
(I also just noted there's a heckload of trailing whitespace, I should
really append my init.el for that....)
Very grateful for all help!
-- Joakim
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Overlays as AA-tree --]
[-- Type: text/x-diff, Size: 29735 bytes --]
diff --git a/src/overlays.c b/src/overlays.c
new file mode 100644
index 0000000..c98c179
--- /dev/null
+++ b/src/overlays.c
@@ -0,0 +1,801 @@
+/*
+ * Copyright (C) 2016 Joakim Jalap
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* This file implements an Arne Andersson-tree (AA-tree) for buffer
+ overlays. It is an augmented interval tree. Basically each node
+ has an interval and a 'max' value, which is the largest upper
+ interval bound which appears in the subtree rooted in the node.
+
+ The implementation of the tree functions is written as closely as
+ possible to the one presented in Anderssons paper (REF)[1], but with a
+ few differences. The code in [1] is written in Pascal, which has
+ proper pass by reference. Unfortunately C doesn't really have this;
+ this is the reason for passing around pointers to pointers.
+
+ Also this tree has parent references, and the code in the delete
+ routine is a bit more complicated because we need to delete the
+ actual memory area, so as to not trip up the GC.
+
+ The fact that this is an augmented tree also makes the rebalancing
+ operation (split and skew) a bit more complex.
+ */
+#include "overlays.h"
+#include "buffer.h"
+
+extern void
+modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
+
+/* Return the max of a, b and c. */
+static inline ptrdiff_t
+overlay_max (ptrdiff_t a, ptrdiff_t b, ptrdiff_t c)
+{
+ ptrdiff_t bc_max = max(b, c);
+ return max(a, bc_max);
+}
+
+/* Find what the max value should be for X. */
+static inline ptrdiff_t
+overlay_find_max (struct Lisp_Overlay *x)
+{
+ return overlay_max(x->left->max, x->right->max, x->char_end);
+}
+
+/* The sentinel node. This indicates the bottom of the tree. It is
+ basically a way to avoid having to check for NULL pointers all the
+ time. */
+struct Lisp_Overlay OVERLAY_SENTINEL_NODE =
+ {
+ Lisp_Misc_Overlay, /* type */
+ 1, /* gcmarkbit */
+ 0, /* start_insertion_type */
+ 0, /* end_insertion_type */
+ 0, /* spacer */
+ NULL, /* next */
+ 0, /* start */
+ 0, /* end */
+ 0, /* plist */
+ 0, /* char_start */
+ 0, /* char_end */
+ 0, /* byte_start */
+ 0, /* byte_end */
+ 0, /* max */
+ 0, /* parent */
+ &OVERLAY_SENTINEL_NODE, /* left */
+ &OVERLAY_SENTINEL_NODE, /* right */
+ 0 /* level */
+ };
+
+struct Lisp_Overlay * OVERLAY_SENTINEL = &OVERLAY_SENTINEL_NODE;
+
+/* This function determines where overlays are inserted in the tree.
+ FIXME: I didn't think too hard about this...
+*/
+static inline bool
+overlay_lt (struct Lisp_Overlay *a, struct Lisp_Overlay *b)
+{
+ if (a->char_start < b->char_start)
+ return true;
+ else if (a->char_start > b->char_start)
+ return false;
+
+ if (a->char_end < b->char_end)
+ return true;
+ else if (a->char_end > b->char_end)
+ return false;
+
+ return false;
+}
+
+/* Rebalancing. See Andersson's paper for a good explaination. This
+ is a bit more complicated than his code, since we need to maintain
+ parent pointer and max field.
+*/
+inline static void
+overlay_skew (struct Lisp_Overlay **tt)
+{
+ struct Lisp_Overlay *t = *tt;
+ if (t->left->level == t->level && t != OVERLAY_SENTINEL)
+ {
+ struct Lisp_Overlay *tmp = t;
+ t = *tt = t->left;
+ tmp->left = t->right;
+ t->right = tmp;
+
+ tmp->max = overlay_find_max(tmp);
+ t->max = overlay_find_max(t);
+
+ t->parent = tmp->parent;
+ XSETMISC (tmp->parent, t);
+ if (tmp->left != OVERLAY_SENTINEL)
+ XSETMISC (tmp->left->parent, tmp);
+ }
+}
+
+/* Rebalancing. See Andersson's paper for a good explaination. This
+ is a bit more complicated than his code, since we need to maintain
+ parent pointer and max field.
+*/
+inline static void
+overlay_split (struct Lisp_Overlay **tt)
+{
+ struct Lisp_Overlay *t = *tt;
+ if (t->level == t->right->right->level && t != OVERLAY_SENTINEL)
+ {
+ struct Lisp_Overlay *tmp = t;
+ t = *tt = t->right;
+ tmp->right = t->left;
+ t->left = tmp;
+ t->level++;
+
+ tmp->max = overlay_find_max(tmp);
+ t->max = overlay_find_max(t);
+
+ t->parent = tmp->parent;
+ XSETMISC (tmp->parent, t);
+ }
+}
+
+/* Insert NODE in TREE. When it is inserted, set its parent to
+ PARENT. On the way up after the insertion, adjust the max field of
+ each node if needed.
+ */
+static ptrdiff_t
+overlay_tree_insert_internal (struct Lisp_Overlay **tree,
+ struct Lisp_Overlay *parent,
+ struct Lisp_Overlay *node)
+{
+ struct Lisp_Overlay *t = *tree;
+ if (t == OVERLAY_SENTINEL)
+ {
+ node->left = node->right = OVERLAY_SENTINEL;
+ node->level = 1;
+ node->max = node->char_end;
+ XSETMISC (node->parent, parent);
+ *tree = node;
+ return node->max;
+ }
+ else
+ {
+ struct Lisp_Overlay **dir = overlay_lt (node, t) ?
+ &t->left : &t->right;
+
+ ptrdiff_t child_max = overlay_tree_insert_internal(dir, t, node);
+ if (child_max > t->max)
+ t->max = child_max;
+ }
+ overlay_skew (&t);
+ overlay_split (&t);
+ return t->max;
+}
+
+/* Insert NODE into TREE.
+ */
+void
+overlay_tree_insert (struct Lisp_Overlay **tree,
+ struct Lisp_Overlay *node)
+{
+ overlay_tree_insert_internal(tree, *tree, node);
+}
+
+/* Delete NODE from TREE.
+ */
+void
+overlay_tree_delete (struct Lisp_Overlay **tree,
+ struct Lisp_Overlay *node)
+{
+ struct Lisp_Overlay *t = *tree;
+ static __thread struct Lisp_Overlay *last, *deleted;
+
+ if (t == OVERLAY_SENTINEL)
+ return;
+
+ last = t;
+ if (overlay_lt(node, t))
+ overlay_tree_delete (&t->left, node);
+ else
+ {
+ deleted = t;
+ overlay_tree_delete (&t->right, node);
+ }
+
+
+ if (t == last &&
+ deleted != OVERLAY_SENTINEL &&
+ node == deleted)
+ {
+ last->left = deleted->left;
+ last->right = deleted->right;
+
+ if (BUFFERP (deleted->parent))
+ {
+ struct buffer *b = XBUFFER (deleted->parent);
+ if (last == deleted)
+ {
+ b->overlays_root = OVERLAY_SENTINEL;
+ }
+ else
+ {
+ b->overlays_root = last;
+ last->parent = deleted->parent;
+ }
+ }
+ else
+ {
+ eassert (OVERLAYP (deleted->parent));
+ struct Lisp_Overlay *up = XOVERLAY (deleted->parent);
+ eassert (up->left == deleted || up->right == deleted);
+ if (up->left == deleted)
+ up->left = last == deleted ? OVERLAY_SENTINEL
+ : last;
+ else
+ up->right = last == deleted ? OVERLAY_SENTINEL
+ : last;
+
+ XSETMISC (last->parent, up);
+ }
+ deleted->parent = Qnil;
+ }
+ else if (t->left->level < t->level - 1
+ || t->right->level < t->level - 1)
+ {
+ t->level--;
+ if (t->right->level > t->level)
+ t->right->level = t->level;
+
+ /* Andersson leaves it as 'an exercise for the reader' to prove
+ that these rebalancing operions are enough. Don't you just love
+ when that happens? */
+ overlay_skew (&t);
+ overlay_skew (&t->right);
+ overlay_skew (&t->right->right);
+ overlay_split (&t);
+ overlay_split (&t->right);
+ }
+}
+
+static void
+overlay_tree_drop_all_internal (struct buffer *buf,
+ struct Lisp_Overlay *tree)
+{
+ if (tree == OVERLAY_SENTINEL)
+ return;
+ overlay_tree_drop_all_internal (buf, tree->left);
+ overlay_tree_drop_all_internal (buf, tree->right);
+ modify_overlay (buf, tree->char_start, tree->char_end);
+}
+
+void
+overlay_tree_drop_all(struct buffer *buf)
+{
+ overlay_tree_drop_all_internal (buf, buf->overlays_root);
+ buf->overlays_root = OVERLAY_SENTINEL;
+}
+
+/* Add ELM to VECP at IDX. VECP has size VEC_SIZE. If IDX is at the
+ end of VECP, realloc VECP and update VEC_SIZE.
+ */
+static inline void
+add_to_vec (ptrdiff_t *vec_size, Lisp_Object **vecp,
+ ptrdiff_t* idx, struct Lisp_Overlay *elm)
+{
+ if (*idx == *vec_size - 1)
+ {
+ *vec_size += 50;
+ *vecp = xnrealloc (*vecp, *vec_size, sizeof (Lisp_Object));
+ }
+
+ XSETMISC((*vecp)[(*idx)++], elm);
+}
+
+
+/* Add all nodes in TREE to VEC_PTR, which has size VEC_SIZE, starting
+ from IDX. The nodes will be added in the order they have in the
+ tree.
+ */
+static void
+overlay_tree_all_internal (struct Lisp_Overlay *tree,
+ ptrdiff_t *vec_size,
+ Lisp_Object **vec_ptr,
+ ptrdiff_t *idx)
+{
+ if (tree == OVERLAY_SENTINEL)
+ return;
+
+ overlay_tree_all_internal (tree->left, vec_size,
+ vec_ptr, idx);
+ add_to_vec (vec_size, vec_ptr, idx, tree);
+ overlay_tree_all_internal (tree->right, vec_size,
+ vec_ptr, idx);
+}
+
+/* Put all nodes from TREE into VEC_PTR, adjusting VEC_SIZE as
+ necessary.
+ */
+ptrdiff_t
+overlay_tree_all (struct Lisp_Overlay *tree, ptrdiff_t *vec_size,
+ Lisp_Object **vec_ptr)
+{
+ ptrdiff_t n = 0;
+ overlay_tree_all_internal (tree, vec_size, vec_ptr, &n);
+ return n;
+}
+
+/* Add all nodes in TREE which contain POS to VEC_PTR at IDX.
+ VEC_SIZE will be adjusted.
+ */
+static void
+overlay_tree_at_internal (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
+ ptrdiff_t *idx, ptrdiff_t *prev_ptr)
+{
+ /* We are at a leaf. */
+ if (tree == OVERLAY_SENTINEL)
+ return;
+
+ /* There's no subtree under here which can contain POS. Note
+ tree->max, as this might be the closest before. */
+ if (tree->max < pos)
+ {
+ if (tree->max > *prev_ptr)
+ *prev_ptr = tree->max;
+ return;
+ }
+
+
+ overlay_tree_at_internal (tree->left, pos, vec_size, vec_ptr,
+ idx, prev_ptr);
+
+ if (pos >= tree->char_start && pos <= tree->char_end)
+ add_to_vec (vec_size, vec_ptr, idx, tree);
+
+ /* If we are after POS, so are all the nodes to the right of us. */
+ if (tree->char_start <= pos)
+ overlay_tree_at_internal (tree->right, pos, vec_size, vec_ptr,
+ idx, prev_ptr);
+}
+
+
+/* Find all nodes in TREE which contain POS and put them in VEC_PTR,
+ growing it as necessary. The size of the vector VEC_PTR will be
+ stored in VEC_SIZE. Return how many nodes were actually put in
+ VEC_PTR.
+ */
+ptrdiff_t
+overlay_tree_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr,
+ ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
+ bool chane_req)
+{
+ ptrdiff_t idx = 0;
+ ptrdiff_t max_before = 0;
+
+ /* Due to the recursion order in `overlay_tree_at_internal' the
+ overlays are sorted by their `char_start' in VEC_PTR. */
+ overlay_tree_at_internal (tree, pos, vec_size, vec_ptr,
+ &idx, &max_before);
+
+ if (prev_ptr && max_before)
+ *prev_ptr = max_before;
+ else
+ *prev_ptr = BEGV;
+
+ /* If NEXT_PTR is not NULL, it should be set to the start_char of
+ the leftmost descendant of the right child of the last element in
+ VEC_PTR, or ZV if the right child is OVERLAY_SENTINEL. */
+ if (next_ptr && idx)
+ {
+ struct Lisp_Overlay *last = XOVERLAY ((*vec_ptr)[idx - 1]);
+ if (last->right != OVERLAY_SENTINEL)
+ {
+ last = last->right;
+ while (last->left != OVERLAY_SENTINEL)
+ last = last->left;
+ *next_ptr = last->char_start;
+ }
+ else
+ *next_ptr = ZV;
+ }
+
+ /* IDX points one behind the last element, so it is the size */
+ return idx;
+}
+
+static inline void
+add_entry_to_vec (ptrdiff_t *vec_size, struct overlay_entry **vecp,
+ ptrdiff_t* idx, Lisp_Object overlay,
+ Lisp_Object str, bool after_p)
+{
+ if (*idx == *vec_size - 1)
+ {
+ *vec_size += 50;
+ *vecp = xnrealloc (*vecp, *vec_size,
+ sizeof (struct overlay_entry));
+ }
+
+ Lisp_Object priority = Foverlay_get ((OVERLAY), Qpriority);
+ EMACS_INT prio = INTEGERP (priority) ? XINT (priority) : 0;
+
+#define SET_ENTRY(ENT, ELM) (*vecp)[*idx].ENT = (ELM)
+ SET_ENTRY(string, str);
+ SET_ENTRY(overlay, overlay);
+ SET_ENTRY(priority, prio);
+ SET_ENTRY(after_string, after_p);
+#undef SET_ENTRY
+
+ (*idx)++;
+}
+
+ptrdiff_t
+overlay_tree_load_overlays (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ ptrdiff_t *vec_size, ptrdiff_t **vec_ptr,
+ ptridff_t *idx, struct window *w)
+{
+ Lisp_Object window, invisible, str, ov;
+ int invis;
+
+ eassert (*idx == 0);
+
+ if (tree == OVERLAY_SENTINEL || tree->max > pos)
+ return;
+
+ if (tree->char_start != pos && tree->char_end != pos)
+ goto cont;
+
+ window = lookup_char_property (tree->plist, Qwindow, 0);
+ if (WINDOWP (window) && XWINDOW (window) != it->w)
+ goto cont;
+
+ invisible = lookup_char_property (tree->plist, Qinvisible, 0);
+ invis = TEXT_PROP_MEANS_INVISIBLE (invisible);
+
+ if ((tree->char_start == pos || (tree->char_end == pos && invis))
+ && (str = lookup_char_property (tree->plist, Qbefore_string, 0),
+ STRINGP (str))
+ && SCHARS (str))
+ {
+ XSETMISC (ov, tree);
+ add_entry_to_vec(vec_size, vec_ptr, idx, ov, str, false);
+ }
+
+ if ((tree->char_end == pos || (tree->char_start == pos && invis))
+ && (str = lookup_char_property (tree->plist, Qafter_string, 0),
+ STRINGP (str))
+ && SCHARS (str))
+ {
+ XSETMISC (ov, tree);
+ add_entry_to_vec(vec_size, vec_ptr, idx, ov, str, true);
+ }
+
+
+ cont:
+ overlay_tree_load_overlays(tree->left, pos, vec_size, vec_ptr, w);
+ if (tree->char_start <= pos)
+ overlay_tree_load_overlays(tree->right, pos, vec_size, vec_ptr, w);
+}
+
+/* Return the buffer OVERLAY is in or nil if OVERLAY has been
+ deleted. */
+Lisp_Object
+buffer_of_overlay (Lisp_Object overlay)
+{
+ Lisp_Object o = overlay;
+ while (!NILP (XOVERLAY (o)->parent) &&
+ !BUFFERP (XOVERLAY (o)->parent))
+ {
+ eassert (OVERLAYP (XOVERLAY (o)->parent));
+ eassert (XOVERLAY (XOVERLAY (o)->parent) != XOVERLAY (o));
+
+ o = XOVERLAY (o)->parent;
+ }
+ return XOVERLAY (o)->parent;
+}
+
+void
+overlay_tree_zero_size_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ Lisp_Object hit_list)
+{
+ if (tree == OVERLAY_SENTINEL || tree->max < pos)
+ return;
+
+ if (tree->char_start == pos && tree->char_end == pos)
+ {
+ Lisp_Object ov;
+ XSETMISC (ov, tree);
+ Fcons(hit_list, ov);
+ }
+
+ overlay_tree_zero_size_at (tree->right, pos, hit_list);
+ if (pos >= tree->char_start)
+ overlay_tree_zero_size_at (tree->left, pos, hit_list);
+}
+
+/* Adjust CHARPOS asn BYTEPOS for an insert from FROM_CHAR (FROM_BYTE)
+ to TO_CHAR (TO_BYTE).
+ FIXME: insertion_type and before.
+ */
+static void
+adjust_pos_for_insert (ptrdiff_t *charpos, ptrdiff_t *bytepos,
+ ptrdiff_t from_char, ptrdiff_t to_char,
+ ptrdiff_t from_byte, ptrdiff_t to_byte,
+ bool insertion_type , bool before)
+{
+ if (*bytepos > from_byte)
+ {
+ *bytepos += to_byte - from_byte;
+ *charpos += to_char - from_char;
+ }
+ else if (*bytepos == from_byte && insertion_type)
+ {
+ *bytepos = to_byte;
+ *charpos = to_char;
+ }
+}
+
+/* Adjust all nodes in TREE for an insert from FROM_CHAR (FROM_BYTE)
+ to TO_CHAR (TO_BYTE). Return TREEs max.
+ FIXME: before.
+ */
+ptrdiff_t
+overlay_tree_adjust_for_insert (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char,
+ ptrdiff_t to_char,
+ ptrdiff_t from_byte,
+ ptrdiff_t to_byte,
+ bool before)
+{
+ /* If we are at a leaf or all nodes in TREE are before the insert,
+ return. */
+ if (tree == OVERLAY_SENTINEL || tree->max < from_char)
+ return tree->max;
+
+ /* Adjust the start postions. */
+ adjust_pos_for_insert(&tree->char_start, &tree->byte_start, from_char,
+ to_char, from_byte, to_byte,
+ tree->start_insertion_type, before);
+ /* Adjust the end postions. */
+ adjust_pos_for_insert(&tree->char_end, &tree->byte_end, from_char,
+ to_char, from_byte, to_byte,
+ tree->end_insertion_type, before);
+
+ ptrdiff_t r,l;
+
+ l = overlay_tree_adjust_for_insert (tree->left, from_char,
+ to_char, from_byte,
+ to_byte, before);
+ r = overlay_tree_adjust_for_insert (tree->right, from_char,
+ to_char, from_byte,
+ to_byte, before);
+
+ tree->max = overlay_max(l, r, tree->char_end);
+ return tree->max;
+}
+
+/* Adjust CHARPOS and BYTEPOS for a delete from FROM_CHAR (FROM_BYTE)
+ to TO_CHAR (TO_BYTE).
+ */
+static void
+adjust_pos_for_delete (ptrdiff_t *charpos, ptrdiff_t *bytepos,
+ ptrdiff_t from_char, ptrdiff_t from_byte,
+ ptrdiff_t to_char, ptrdiff_t to_byte)
+{
+ if (*charpos > to_char)
+ {
+ *charpos = to_char - from_char;
+ *bytepos = to_byte - from_byte;
+ }
+ else if (*charpos > from_char)
+ {
+ *charpos = from_char;
+ *bytepos = from_byte;
+ }
+}
+
+/* Adjust TREE for a delete from FROM_CHAR (FROM_BYTE) to TO_CHAR
+ (TO_BYTE).
+ */
+ptrdiff_t
+overlay_tree_adjust_for_delete (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char, ptrdiff_t from_byte,
+ ptrdiff_t to_char, ptrdiff_t to_byte)
+{
+ if (tree == OVERLAY_SENTINEL || tree->max < from_char)
+ return tree->max;
+
+ adjust_pos_for_delete(&tree->char_start, &tree->byte_start, from_char,
+ from_byte, to_char, to_byte);
+ adjust_pos_for_delete(&tree->char_end, &tree->byte_end, from_char,
+ from_byte, to_char, to_byte);
+
+ ptrdiff_t r, l;
+
+ l = overlay_tree_adjust_for_delete(tree->left, from_char, from_byte,
+ to_char, to_byte);
+ r = overlay_tree_adjust_for_delete(tree->right, from_char, from_byte,
+ to_char, to_byte);
+
+ tree->max = overlay_max(l, r, tree->char_end);
+ return tree->max;
+}
+
+/* Adjust CHARPOS and BYTEPOS for a delete from FROM_CHAR (FROM_BYTE)
+ to TO_CHAR (TO_BYTE).
+ */
+static void
+adjust_pos_for_replace (ptrdiff_t *charpos, ptrdiff_t *bytepos,
+ ptrdiff_t from_char, ptrdiff_t from_byte,
+ ptrdiff_t old_chars, ptrdiff_t old_bytes,
+ ptrdiff_t new_chars, ptrdiff_t new_bytes)
+{
+ ptrdiff_t diff_chars = new_chars - old_chars;
+ ptrdiff_t diff_bytes = new_bytes - old_bytes;
+
+ if (*bytepos >= (from_byte + old_bytes))
+ {
+ *charpos += diff_chars;
+ *bytepos += diff_bytes;
+ }
+ else if (*bytepos > from_byte)
+ {
+ *charpos = from_char;
+ *bytepos = from_byte;
+ }
+}
+
+/* Adjust TREE for a delete from FROM_CHAR (FROM_BYTE)
+ to TO_CHAR (TO_BYTE).
+ */
+ptrdiff_t
+overlay_tree_adjust_for_replace (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char,
+ ptrdiff_t from_byte,
+ ptrdiff_t old_chars,
+ ptrdiff_t old_bytes,
+ ptrdiff_t new_chars,
+ ptrdiff_t new_bytes)
+{
+ if (tree == OVERLAY_SENTINEL || tree->max <= from_byte)
+ return tree->max;
+
+ adjust_pos_for_replace(&tree->char_start, &tree->byte_start,
+ from_char, from_byte, old_chars, old_bytes,
+ new_chars, new_bytes);
+ adjust_pos_for_replace(&tree->char_end, &tree->byte_end,
+ from_char, from_byte, old_chars, old_bytes,
+ new_chars, new_bytes);
+
+ ptrdiff_t r, l;
+
+ l = overlay_tree_adjust_for_replace(tree->left, from_char,
+ from_byte, old_chars,
+ old_bytes, new_chars,
+ new_bytes);
+ r = overlay_tree_adjust_for_replace(tree->right, from_char,
+ from_byte, old_chars,
+ old_bytes, new_chars,
+ new_bytes);
+
+ tree->max = overlay_max(l, r, tree->char_end);
+ return tree->max;
+}
+
+
+DEFUN("overlay-parent", Foverlay_parent, Soverlay_parent, 1, 1, 0,
+ doc: /* Parent of overlay. An overlay or a buffer. */)
+ (Lisp_Object overlay)
+{
+ if (!OVERLAYP(overlay))
+ signal_error("Not an overlay", Qnil);
+ return XOVERLAY (overlay)->parent;
+}
+
+DEFUN("overlay-info", Foverlay_info, Soverlay_info, 1, 1, 0,
+ doc: /* Info about OVERLAY. */)
+ (Lisp_Object overlay)
+{
+ if (!OVERLAYP(overlay))
+ signal_error("Not an overlay", Qnil);
+ Lisp_Object ret;
+ struct Lisp_Overlay *o = XOVERLAY (overlay);
+ Lisp_Object left, right, this;
+ if (o->left != OVERLAY_SENTINEL)
+ XSETMISC(left, o->left);
+ else
+ left = Qt;
+
+ if (o->right != OVERLAY_SENTINEL)
+ XSETMISC(right, o->right);
+ else
+ right = Qt;
+
+ XSETMISC (this, o);
+
+ ret = list5(Fcons(Fcons(make_number(o->char_start),
+ make_number(o->char_end)),
+ make_number(o->max)),
+ this,
+ o->parent,
+ make_number (o->level),
+ Fcons(left,
+ right));
+ return ret;
+}
+
+DEFUN("overlays-in-buffer", Foverlays_in_buffer, Soverlays_in_buffer,
+ 0, 1, 0,
+ doc: /* Return a list of all the overlays in BUFFER. */)
+ (Lisp_Object buffer)
+{
+ Lisp_Object ret;
+ struct buffer *b;
+ if (!NILP (buffer))
+ b = XBUFFER (buffer);
+ else
+ b = current_buffer;
+
+
+ ptrdiff_t vec_size = 30;
+ Lisp_Object *vec = xnmalloc (vec_size, sizeof (Lisp_Object));
+
+
+ ptrdiff_t noverlays = overlay_tree_all(b->overlays_root,
+ &vec_size, &vec);
+ ret = Flist(noverlays, vec);
+
+ return ret;
+}
+
+DEFUN("overlay-tree-at", Foverlay_tree_at, Soverlay_tree_at,
+ 1, 2, 0,
+ doc: /* Return a list of all overlays in BUFFER. If BUFFER is
+ nil, use the current buffer. */)
+ (Lisp_Object pos, Lisp_Object buffer)
+{
+ CHECK_NUMBER_COERCE_MARKER (pos);
+
+ ptrdiff_t next, prev;
+ ptrdiff_t bufpos = XINT (pos);
+
+ Lisp_Object ret;
+ struct buffer *b;
+ if (!NILP (buffer))
+ b = XBUFFER (buffer);
+ else
+ b = current_buffer;
+
+
+ ptrdiff_t vec_size = 30;
+ Lisp_Object *vec = xnmalloc (vec_size, sizeof (Lisp_Object));
+
+
+ ptrdiff_t noverlays = overlay_tree_at(b->overlays_root, bufpos,
+ &next, &prev,
+ &vec_size, &vec, false);
+
+ ret = Flist(noverlays, vec);
+
+ return ret;
+}
+
+void
+syms_of_overlays (void)
+{
+ defsubr (&Soverlay_parent);
+ defsubr (&Soverlay_info);
+ defsubr (&Soverlays_in_buffer);
+ defsubr (&Soverlay_tree_at);
+}
+
diff --git a/src/overlays.h b/src/overlays.h
new file mode 100644
index 0000000..6f00bf0
--- /dev/null
+++ b/src/overlays.h
@@ -0,0 +1,75 @@
+
+#ifndef OVERLAYS_H
+#define OVERLAYS_H
+
+#include <config.h>
+#include "lisp.h"
+
+extern struct Lisp_Overlay OVERLAY_SENTINEL_NODE;
+
+extern struct Lisp_Overlay * OVERLAY_SENTINEL;
+
+struct overlay_entry
+{
+ Lisp_Object overlay;
+ Lisp_Object string;
+ EMACS_INT priority;
+ bool after_string_p;
+};
+
+void
+overlay_tree_insert (struct Lisp_Overlay **tree,
+ struct Lisp_Overlay *node);
+
+void
+overlay_tree_delete (struct Lisp_Overlay **tree,
+ struct Lisp_Overlay *node);
+
+void
+overlay_tree_drop_all (struct buffer *buf);
+
+Lisp_Object
+buffer_of_overlay (Lisp_Object overlay);
+
+ptrdiff_t
+overlay_tree_all (struct Lisp_Overlay *tree, ptrdiff_t *vec_size,
+ Lisp_Object **vec_ptr);
+
+ptrdiff_t
+overlay_tree_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr,
+ ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
+ bool chane_req);
+
+void
+overlay_tree_zero_size_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
+ Lisp_Object hit_list);
+
+ptrdiff_t
+overlay_tree_adjust_for_insert (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char,
+ ptrdiff_t to_char,
+ ptrdiff_t from_byte,
+ ptrdiff_t to_byte,
+ bool before);
+
+ptrdiff_t
+overlay_tree_adjust_for_delete (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char, ptrdiff_t from_byte,
+ ptrdiff_t to_char, ptrdiff_t to_byte);
+
+ptrdiff_t
+overlay_tree_adjust_for_replace (struct Lisp_Overlay *tree,
+ ptrdiff_t from_char,
+ ptrdiff_t from_byte,
+ ptrdiff_t old_chars,
+ ptrdiff_t old_bytes,
+ ptrdiff_t new_chars,
+ ptrdiff_t new_bytes);
+
+ptrdiff_t
+overlay_tree_at (struct Lisp_Overlay *tree, Lisp_Object **vecp,
+ ptrdiff_t pos);
+
+
+#endif /* OVERLAYS_H */
diff --git a/test/lisp/overlay-tests.el b/test/lisp/overlay-tests.el
new file mode 100644
index 0000000..05e81a5
--- /dev/null
+++ b/test/lisp/overlay-tests.el
@@ -0,0 +1,72 @@
+
+
+
+(require 'ert)
+
+(ert-deftest overlay-create-test ()
+ " "
+ (with-temp-buffer
+ (insert "blueberrypancakes")
+ (let ((o1 (make-overlay 4 9)))
+ (should-not (overlay-get o1 'face))
+ (should (overlayp o1))
+ (should (= (overlay-start o1) 4))
+ (should (= (overlay-end o1) 9))
+ (should (eq (overlay-buffer o1) (current-buffer)))
+ (let ((b (current-buffer)))
+ (with-temp-buffer
+ (should (eq (overlay-buffer o1) b))))
+ (should (= (length (overlays-in (point-min) (point-max))) 1))
+ (should (eq (car (overlays-in (point-min) (point-max))) o1)))))
+
+
+(ert-deftest overlay-move-test ()
+ " "
+ (with-temp-buffer
+ (insert "blueberrypancakes")
+ (let ((o1 (make-overlay 4 9)))
+ ;; Test a "normal" move
+ (should (= (overlay-start o1) 4))
+ (should (= (overlay-end o1) 9))
+ (should (eq (overlay-buffer o1) (current-buffer)))
+ (move-overlay o1 3 10)
+ (should (= (overlay-start o1) 3))
+ (should (= (overlay-end o1) 10))
+ (let ((b (current-buffer)))
+ (with-temp-buffer
+ (insert "blueberry")
+ (move-overlay o1 2 4)
+ (should (eq (overlay-buffer o1) b))
+ (move-overlay o1 2 4 (current-buffer))
+ (should (eq (overlay-buffer o1) (current-buffer)))
+ (should (= (overlay-start o1) 2))
+ (should (= (overlay-end o1) 4))))
+ (move-overlay o1 1 50 (current-buffer))
+ (should (eq (overlay-buffer o1) (current-buffer)))
+ (should (= (overlay-start o1) 1))
+ (should (= (overlay-end o1) (point-max))))))
+
+(ert-deftest overlay-front-advance-test ()
+ (with-temp-buffer
+ (insert "blueberrypancakes")
+ (let ((o1 (make-overlay 1 5 nil t))
+ (o2 (make-overlay 1 5))
+ (str "creamy "))
+ (goto-char (point-min))
+ (insert str)
+ (should (= (overlay-start o2) 1))
+ (should (= (overlay-start o1) (1+ (length str)))))))
+
+(ert-deftest overlay-rear-advance-test ()
+ (with-temp-buffer
+ (insert "blueberrypancakes")
+ (let ((o1 (make-overlay 7 18 nil nil t))
+ (o2 (make-overlay 7 18))
+ (str " for dinner"))
+ (should (= (point-max) 18))
+ (goto-char (point-max))
+ (insert str)
+ (should (= (overlay-end o1) (point-max)))
+ (should (= (overlay-end o2) 18)))))
+
+
^ permalink raw reply related [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
@ 2016-09-20 12:14 ` Clément Pit--Claudel
2016-09-20 12:43 ` Lars Ingebrigtsen
` (3 subsequent siblings)
4 siblings, 0 replies; 110+ messages in thread
From: Clément Pit--Claudel @ 2016-09-20 12:14 UTC (permalink / raw)
To: emacs-devel
[-- Attachment #1.1: Type: text/plain, Size: 255 bytes --]
On 2016-09-20 06:32, Joakim Jalap wrote:
> 1) Is it worth continuing down this path?
Not an expert, but many of my projects use overlays heavily. If these changes make them faster, then it sounds like a very worthy endeavour!
Cheers,
Clément.
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
2016-09-20 12:14 ` Clément Pit--Claudel
@ 2016-09-20 12:43 ` Lars Ingebrigtsen
2016-09-20 16:19 ` Joakim Jalap
2016-09-20 23:19 ` Richard Stallman
2016-09-20 14:40 ` Eli Zaretskii
` (2 subsequent siblings)
4 siblings, 2 replies; 110+ messages in thread
From: Lars Ingebrigtsen @ 2016-09-20 12:43 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> First I tried using the tree from intervals.c, but that seemed to be
> very tightly bound to the implementation of text properties, so I gave
> up on that idea.
I seem to recall that somebody made the suggestion earlier to make
overlays a special case of text properties, and then getting rid of most
of the low-level overlay code. Text properties are already implemented
pretty efficiently, I think?
I don't know how feasible this is, though.
--
(domestic pets only, the antidote for overdose, milk.)
bloggy blog: http://lars.ingebrigtsen.no
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
2016-09-20 12:14 ` Clément Pit--Claudel
2016-09-20 12:43 ` Lars Ingebrigtsen
@ 2016-09-20 14:40 ` Eli Zaretskii
2016-09-20 17:13 ` Joakim Jalap
2016-09-21 14:52 ` Stefan Monnier
2017-02-03 8:49 ` Andreas Politz
4 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-20 14:40 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Date: Tue, 20 Sep 2016 12:32:28 +0200
>
> I've been working on an item from /etc/TODO on and off for a while now,
> but now I have hit a bit of a roadblock.
Thanks for working on this TODO item.
> I got a bit on the way; I managed to get the tree structure in place and
> to make it work for some very simple cases. I wrote some simple ert tests
> for this. The idea was to be able to compile in three ways: just as
> before, with just the new overlay implementation and with both
> implementations and a whole lot of easserts. But alas, it turned out to
> be too hard for me. There's quite a bit of fiddly code regarding
> overlays and ripping it out and replacing it seems to be more than I can
> chew. So the status right now is that nothing works... If you define
> BOTH_OVERLAYS it will compile but fail an eassert at startup, if you
> define NEW_OVERLAYS it doesn't even compile, since there's some stuff I
> haven't replaced properly.
>
> Anyway, I basically have two questions for you experts:
> 1) Is it worth continuing down this path?
> 2) If so, what's the best way to go about something like this? Replacing
> the whole thing at once seems very hard, but I don't really know how to
> go about replacing it little by little.
>
> I'm attaching the diff. It is an unholy mess of ifdefs, but the meat of
> it is in overlays.[ch] and buffer.c. It is a pretty big diff, and it's
> based on master from a few months ago, so I'm not even sure it applies,
> but I'd be grateful if somebody could have a quick look at it and try to
> see if there's anything worth keeping there. If there's any interest I
> could try rebasing it.
It seems like you only attached part of the changes, because all I see
in the attachment is 3 entirely new files, with no ifdef's anywhere in
sight. So I couldn't look at the problems that got you stuck.
Just by reading your description, I don't think I understand the
nature of your difficulties. Overlays present a relatively small
number of Lisp-visible APIs, so all you need is to re-implement those
few APIs based on the new internal representation. What exactly gives
you trouble with that? (I see you've implemented new APIs, but that
doesn't have to be part of the job, it's up to you.)
As for the migration path: if you find it difficult to keep the old
code, just remove it. When your code is ready for testing by others,
you could push a public Git branch and ask people to check it out. We
won't merge the branch to master until it is stable enough, so the
fact that the old implementation will be gone is not a problem. (If
needed, we can always compare with older versions to see if some issue
is due to the new implementation or not.)
You say that replacing it all is very hard, but I don't really
understand why. Please elaborate.
Thanks again for your efforts. Please keep up the good work.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 12:43 ` Lars Ingebrigtsen
@ 2016-09-20 16:19 ` Joakim Jalap
2016-09-20 23:19 ` Richard Stallman
1 sibling, 0 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-09-20 16:19 UTC (permalink / raw)
To: Lars Ingebrigtsen; +Cc: emacs-devel
Lars Ingebrigtsen <larsi@gnus.org> writes:
> I seem to recall that somebody made the suggestion earlier to make
> overlays a special case of text properties, and then getting rid of most
> of the low-level overlay code. Text properties are already implemented
> pretty efficiently, I think?
Well, I think the main difference is that overlays are object, that is,
there is a struct Lisp_Overlay. There were some issues with how
intervals are grafted into a buffer if I recall correctly.
> I don't know how feasible this is, though.
Hm, perhaps there is a way to make a struct Lisp_Overlay which just
points to an interval. I should probably have a look at that again.
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 14:40 ` Eli Zaretskii
@ 2016-09-20 17:13 ` Joakim Jalap
2016-09-21 16:14 ` Eli Zaretskii
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-09-20 17:13 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
[-- Attachment #1: Type: text/plain, Size: 2695 bytes --]
Eli Zaretskii <eliz@gnu.org> writes:
> It seems like you only attached part of the changes, because all I see
> in the attachment is 3 entirely new files, with no ifdef's anywhere in
> sight. So I couldn't look at the problems that got you stuck.
Yes, sorry. Attaching the full diff.
> Just by reading your description, I don't think I understand the
> nature of your difficulties. Overlays present a relatively small
> number of Lisp-visible APIs, so all you need is to re-implement those
> few APIs based on the new internal representation. What exactly gives
> you trouble with that? (I see you've implemented new APIs, but that
> doesn't have to be part of the job, it's up to you.)
Well, the Lisp-visible APIs weren't really the problem. The problem was
more in the 'internal' handling of overlays in buffer.c and in xdisp.c,
and also the fact that I had to reimplement a lot of the logic about how
markers are moved when the buffer changes. Speaking of which, is the
byte position stored in a marker of any significance in an overlay?
Otherwise I could at least get rid of those.
I don't really think it's anything that's monumentally difficult, it's
more that until everything works nothing really works, so I can't even
get Emacs to start.
The DEFUNs I added in overlays.c were just for my own debugging purposes
while writing the code, it's nothing I intended to keep.
> As for the migration path: if you find it difficult to keep the old
> code, just remove it. When your code is ready for testing by others,
> you could push a public Git branch and ask people to check it out. We
> won't merge the branch to master until it is stable enough, so the
> fact that the old implementation will be gone is not a problem. (If
> needed, we can always compare with older versions to see if some issue
> is due to the new implementation or not.)
>
> You say that replacing it all is very hard, but I don't really
> understand why. Please elaborate.
Well, first of all I thought it would be a good strategy to keep all the
old code so that I could compare the results at runtime, but that turned
into a huge mess of ifdefs.
Secondly I thought that it'd be slightly easier to iterate while keeping
the old code, but that turned out to be harder than I first imagined.
Basically my problem is that when I throw the old code out wholesale,
suddenly that's thousands of lines I have to write which have to
somewhat work, or I can't even get Emacs to build, let alone start up,
so it turns into quite a big project, which I don't really see how I can
break up into smaller parts.
> Thanks again for your efforts. Please keep up the good work.
Thanks! I'll keep working on it :)
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Complete diff --]
[-- Type: text/x-diff, Size: 64277 bytes --]
diff --git a/configure.ac b/configure.ac
index b7651ed..2674806 100644
--- a/configure.ac
+++ b/configure.ac
@@ -378,12 +378,6 @@ AC_DEFUN
OPTION_DEFAULT_OFF([xwidgets],
[enable use of some gtk widgets in Emacs buffers (requires gtk3)])
-OPTION_DEFAULT_OFF([new_overlays],
- [Use AA-tree for overlays])
-
-OPTION_DEFAULT_OFF([both_overlays],
- [Use both overlays and a lot of assertions])
-
## For the times when you want to build Emacs but don't have
## a suitable makeinfo, and can live without the manuals.
dnl http://lists.gnu.org/archive/html/emacs-devel/2008-04/msg01844.html
@@ -2648,35 +2642,6 @@ AC_DEFUN
CFLAGS=$OLD_CFLAGS
LIBS=$OLD_LIBS
-
-BOTH_OVERLAYS=no
-NEW_OVERLAYS=no
-OVERLAYS_OBJ=
-OVERLAYS_H=
-if test "$with_new_overlays" != "no"; then
- if test "$with_both_overlays" != "no"; then
- AS_ECHO([both? ${BOTH_OVERLAYS} $with_new_overlays $with_both_overlays])
- AC_MSG_ERROR([Can't have both new-overlays and both-overlays.])
- fi
- NEW_OVERLAYS=yes
- AC_DEFINE([NEW_OVERLAYS], 1, [Use new overlays.])
- OVERLAYS_OBJ=overlays.o
- OVERLAYS_H=overlays.h
-fi
-
-if test "$with_both_overlays" != "no"; then
- if test "x$ac_enable_checking" == "x" ; then
- AC_MSG_ERROR([with-both_overlays only makes sense with enable-checking])
- fi
- BOTH_OVERLAYS=yes
- AC_DEFINE([BOTH_OVERLAYS], 1, [Use both overlays.])
- OVERLAYS_OBJ=overlays.o
- OVERLAYS_H=overlays.h
-fi
-AC_SUBST(OVERLAYS_OBJ)
-AC_SUBST(OVERLAYS_H)
-
-
dnl D-Bus has been tested under GNU/Linux only. Must be adapted for
dnl other platforms.
HAVE_DBUS=no
@@ -5319,8 +5284,6 @@ AC_DEFUN
Does Emacs have dynamic modules support? ${HAVE_MODULES}
Does Emacs use toolkit scroll bars? ${USE_TOOLKIT_SCROLL_BARS}
Does Emacs support Xwidgets (requires gtk3)? ${HAVE_XWIDGETS}
- Does Emacs use both overlay structures? ${BOTH_OVERLAYS}
- Does Emacs use AA-tree for overlays? ${NEW_OVERLAYS}
"])
if test -n "${EMACSDATA}"; then
diff --git a/src/Makefile.in b/src/Makefile.in
index 89c0c2a..8639eff 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -156,8 +156,6 @@ DBUS_OBJ =
## xwidgets.o if HAVE_XWIDGETS, else empty.
XWIDGETS_OBJ = @XWIDGETS_OBJ@
-OVERLAYS_OBJ = @OVERLAYS_OBJ@
-
LIB_EXECINFO=@LIB_EXECINFO@
SETTINGS_CFLAGS = @SETTINGS_CFLAGS@
@@ -398,7 +396,7 @@ base_obj =
$(CM_OBJ) term.o terminal.o xfaces.o $(XOBJ) $(GTK_OBJ) $(DBUS_OBJ) \
emacs.o keyboard.o macros.o keymap.o sysdep.o \
buffer.o filelock.o insdel.o marker.o \
- minibuf.o fileio.o dired.o $(OVERLAYS_OBJ) \
+ minibuf.o fileio.o dired.o \
cmds.o casetab.o casefiddle.o indent.o search.o regex.o undo.o \
alloc.o data.o doc.o editfns.o callint.o \
eval.o floatfns.o fns.o font.o print.o lread.o $(MODULES_OBJ) \
diff --git a/src/alloc.c b/src/alloc.c
index 2ec7dae..5f9d6ad 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3799,18 +3799,6 @@ build_overlay (Lisp_Object start, Lisp_Object end, Lisp_Object plist)
OVERLAY_END (overlay) = end;
set_overlay_plist (overlay, plist);
XOVERLAY (overlay)->next = NULL;
-
-#ifdef NEW_OVERLAYS
- XOVERLAY (overlay)->left = NULL;
- XOVERLAY (overlay)->right = NULL;
- ptrdiff_t char_start = XINT (Fmarker_position (start));
- XOVERLAY (overlay)->char_start = char_start;
- XOVERLAY (overlay)->byte_start = CHAR_TO_BYTE(char_start);
- ptrdiff_t char_end = XINT (Fmarker_position(end));
- XOVERLAY (overlay)->char_end = char_end;
- XOVERLAY (overlay)->byte_end = CHAR_TO_BYTE(char_end);
-#endif
-
return overlay;
}
diff --git a/src/buffer.c b/src/buffer.c
index cca91c7..8756cbb 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -43,10 +43,6 @@ along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
#include "frame.h"
#include "xwidget.h"
-#if defined (NEW_OVERLAYS) || defined (BOTH_OVERLAYS)
-#include "overlays.h"
-#endif
-
#ifdef WINDOWSNT
#include "w32heap.h" /* for mmap_* */
#endif
@@ -125,7 +121,7 @@ static Lisp_Object QSFundamental; /* A string "Fundamental". */
static void alloc_buffer_text (struct buffer *, ptrdiff_t);
static void free_buffer_text (struct buffer *b);
static struct Lisp_Overlay * copy_overlays (struct buffer *, struct Lisp_Overlay *);
-void modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
+static void modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
static Lisp_Object buffer_lisp_local_variables (struct buffer *, bool);
static void
@@ -596,23 +592,6 @@ even if it is dead. The return value is never nil. */)
return buffer;
}
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
-static void INLINE
-insert_overlay_in_buffer_tree (struct buffer *b, Lisp_Object overlay)
-{
- struct Lisp_Overlay *o = XOVERLAY (overlay);
- if (b->overlays_root == OVERLAY_SENTINEL)
- {
- overlay_tree_insert (&b->overlays_root, o);
- eassert (b->overlays_root == o);
- XSETBUFFER(b->overlays_root->parent, b);
- }
- else
- {
- overlay_tree_insert (&b->overlays_root, o);
- }
-}
-#endif
/* Return a list of overlays which is a copy of the overlay list
LIST, but for buffer B. */
@@ -646,7 +625,7 @@ copy_overlays (struct buffer *b, struct Lisp_Overlay *list)
return result;
}
-#ifndef NEW_OVERLAYS
+
/* Set an appropriate overlay of B. */
static void
@@ -660,7 +639,6 @@ set_buffer_overlays_after (struct buffer *b, struct Lisp_Overlay *o)
{
b->overlays_after = o;
}
-#endif
/* Clone per-buffer values of buffer FROM.
@@ -882,7 +860,6 @@ CLONE nil means the indirect buffer's state is reset to default values. */)
return buf;
}
-#ifndef NEW_OVERLAYS
/* Mark OV as no longer associated with B. */
static void
@@ -895,14 +872,12 @@ drop_overlay (struct buffer *b, struct Lisp_Overlay *ov)
unchain_marker (XMARKER (ov->end));
}
-#endif
/* Delete all overlays of B and reset it's overlay lists. */
void
delete_all_overlays (struct buffer *b)
{
-#ifndef NEW_OVERLAYS
struct Lisp_Overlay *ov, *next;
/* FIXME: Since each drop_overlay will scan BUF_MARKERS to unlink its
@@ -923,9 +898,6 @@ delete_all_overlays (struct buffer *b)
set_buffer_overlays_before (b, NULL);
set_buffer_overlays_after (b, NULL);
-#else
- overlay_tree_drop_all (b);
-#endif
}
/* Reinitialize everything about a buffer except its name and contents
@@ -953,11 +925,9 @@ reset_buffer (register struct buffer *b)
b->auto_save_failure_time = 0;
bset_auto_save_file_name (b, Qnil);
bset_read_only (b, Qnil);
-#ifndef NEW_OVERLAYS
set_buffer_overlays_before (b, NULL);
set_buffer_overlays_after (b, NULL);
b->overlay_center = BEG;
-#endif
bset_mark_active (b, Qnil);
bset_point_before_scroll (b, Qnil);
bset_file_format (b, Qnil);
@@ -971,9 +941,6 @@ reset_buffer (register struct buffer *b)
bset_extra_line_spacing (b, BVAR (&buffer_defaults, extra_line_spacing));
b->display_error_modiff = 0;
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- b->overlays_root = OVERLAY_SENTINEL;
-#endif
}
/* Reset buffer B's local variables info.
@@ -2788,7 +2755,6 @@ overlays_at (EMACS_INT pos, bool extend, Lisp_Object **vec_ptr,
ptrdiff_t *len_ptr,
ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr, bool change_req)
{
-#ifndef NEW_OVERLAYS
Lisp_Object overlay, start, end;
struct Lisp_Overlay *tail;
ptrdiff_t idx = 0;
@@ -2895,52 +2861,7 @@ overlays_at (EMACS_INT pos, bool extend, Lisp_Object **vec_ptr,
*next_ptr = next;
if (prev_ptr)
*prev_ptr = prev;
-
-#ifdef BOTH_OVERLAYS
- ptrdiff_t check_next, check_prev, check_len = 20, check_idx;
- Lisp_Object *check_vec;
-
- check_vec = xnmalloc(check_len, sizeof *check_vec);
-
- check_idx = overlay_tree_at (current_buffer->overlays_root,
- pos, &check_next, &check_prev,
- &check_len, &check_vec,
- change_req);
-
- /* Same amount of overlays returned. */
- /* eassert (check_idx == idx); */
- /* Same NEXT_PTR. */
- if (next_ptr)
- eassert (*next_ptr == check_next);
- /* Same PREV_PTR. */
- if (prev_ptr)
- eassert (*prev_ptr == check_prev);
-
- /* Finally check that all overlays in *VEC_PTR are also in
- CHECK_VEC. */
- ptrdiff_t i, j;
- bool found;
- for (i = 0; i < idx; i++)
- {
- found = false;
- struct Lisp_Overlay *o1 = XOVERLAY ((*vec_ptr)[i]);
- for (j = 0; j < idx; j++)
- {
- struct Lisp_Overlay *o2 = XOVERLAY (check_vec[j]);
- if (o1 == o2)
- found = true;
- }
- if (!found)
- eassert (false);
- }
-
-#endif /* BOTH_OVERLAYS */
return idx;
-#else /* if NEW_OVERLAYS */
- return overlay_tree_at (current_buffer->overlays_root, pos,
- next_ptr, prev_ptr, len_ptr, vec_ptr,
- change_req)
-#endif /* ifndef NEW_OVERLAYS */
}
\f
/* Find all the overlays in the current buffer that overlap the range
@@ -3206,14 +3127,8 @@ sort_overlays (Lisp_Object *overlay_vec, ptrdiff_t noverlays, struct window *w)
overlay = overlay_vec[i];
if (OVERLAYP (overlay)
-#ifndef NEW_OVERLAYS
&& OVERLAY_POSITION (OVERLAY_START (overlay)) > 0
- && OVERLAY_POSITION (OVERLAY_END (overlay)) > 0
-#else
- && XOVERLAY (overlay)->char_start > 0
- && XOVERLAY (overlay)->char_end > 0
-#endif
- )
+ && OVERLAY_POSITION (OVERLAY_END (overlay)) > 0)
{
/* If we're interested in a specific window, then ignore
overlays that are limited to some other window. */
@@ -3228,17 +3143,8 @@ sort_overlays (Lisp_Object *overlay_vec, ptrdiff_t noverlays, struct window *w)
/* This overlay is good and counts: put it into sortvec. */
sortvec[j].overlay = overlay;
-#ifndef NEW_OVERLAYS
sortvec[j].beg = OVERLAY_POSITION (OVERLAY_START (overlay));
sortvec[j].end = OVERLAY_POSITION (OVERLAY_END (overlay));
-#ifdef BOTH_OVERLAYS
- eassert (sortvec[j].beg == XOVERLAY (overlay)->char_start);
- eassert (sortvec[j].end == XOVERLAY (overlay)->char_end);
-#endif
-#else
- sortvec[j].beg = XOVERLAY (overlay)->char_start;
- sortvec[j].end = XOVERLAY (overlay)->char_end;
-#endif
tem = Foverlay_get (overlay, Qpriority);
if (NILP (tem))
{
@@ -3488,7 +3394,6 @@ overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr)
return 0;
}
\f
-#ifndef NEW_OVERLAYS
/* Shift overlays in BUF's overlay lists, to center the lists at POS. */
void
@@ -3637,7 +3542,7 @@ adjust_overlays_for_delete (ptrdiff_t pos, ptrdiff_t length)
and also update the center point. */
recenter_overlay_lists (current_buffer, pos);
}
-#endif
+
/* Fix up overlays that were garbled as a result of permuting markers
in the range START through END. Any overlay with at least one
endpoint in this range will need to be unlinked from the overlay
@@ -3912,7 +3817,6 @@ for the rear of the overlay advance when text is inserted there
b = XBUFFER (buffer);
-#ifndef NEW_OVERLAYS
beg = Fset_marker (Fmake_marker (), beg, buffer);
end = Fset_marker (Fmake_marker (), end, buffer);
@@ -3920,20 +3824,9 @@ for the rear of the overlay advance when text is inserted there
XMARKER (beg)->insertion_type = 1;
if (!NILP (rear_advance))
XMARKER (end)->insertion_type = 1;
-#endif
overlay = build_overlay (beg, end, Qnil);
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- XOVERLAY (overlay)->start_insertion_type = !NILP (front_advance);
- XOVERLAY (overlay)->end_insertion_type = !NILP (rear_advance);
-
- insert_overlay_in_buffer_tree(b, overlay);
-#ifdef BOTH_OVERLAYS
- /* Check coherence */
-#endif /* BOTH_OVERLAYS */
-#endif /* NEW_OVERLAYS or BOTH_OVERLAYS */
-#ifndef NEW_OVERLAYS
/* Put the new overlay on the wrong list. */
end = OVERLAY_END (overlay);
if (OVERLAY_POSITION (end) < b->overlay_center)
@@ -3953,13 +3846,13 @@ for the rear of the overlay advance when text is inserted there
/* We don't need to redisplay the region covered by the overlay, because
the overlay has no properties at the moment. */
-#endif
+
return overlay;
}
\f
/* Mark a section of BUF as needing redisplay because of overlays changes. */
-void
+static void
modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
{
if (start > end)
@@ -3976,7 +3869,6 @@ modify_overlay (struct buffer *buf, ptrdiff_t start, ptrdiff_t end)
++BUF_OVERLAY_MODIFF (buf);
}
-#ifndef NEW_OVERLAYS
/* Remove OVERLAY from LIST. */
static struct Lisp_Overlay *
@@ -4005,7 +3897,6 @@ unchain_both (struct buffer *b, Lisp_Object overlay)
set_buffer_overlays_after (b, unchain_overlay (b->overlays_after, ov));
eassert (XOVERLAY (overlay)->next == NULL);
}
-#endif
DEFUN ("move-overlay", Fmove_overlay, Smove_overlay, 3, 4, 0,
doc: /* Set the endpoints of OVERLAY to BEG and END in BUFFER.
@@ -4019,23 +3910,10 @@ buffer. */)
ptrdiff_t count = SPECPDL_INDEX ();
ptrdiff_t n_beg, n_end;
ptrdiff_t o_beg UNINIT, o_end UNINIT;
-#if defined(NEW_OVERLAYS ) || defined(BOTH_OVERLAYS)
- ptrdiff_t old_start UNINIT, old_end UNINIT;
-#endif
+
CHECK_OVERLAY (overlay);
if (NILP (buffer))
- {
-#ifndef NEW_OVERLAYS
- buffer = Fmarker_buffer (OVERLAY_START (overlay));
-#ifdef BOTH_OVERLAYS
- struct buffer *b1 = XBUFFER (buffer);
- struct buffer *b2 = XBUFFER (buffer_of_overlay (overlay));
- eassert (b1 == b2);
-#endif
-#else /* NEW_OVERLAYS */
- buffer = buffer_of_overlay (overlay);
-#endif
- }
+ buffer = Fmarker_buffer (OVERLAY_START (overlay));
if (NILP (buffer))
XSETBUFFER (buffer, current_buffer);
CHECK_BUFFER (buffer);
@@ -4059,68 +3937,33 @@ buffer. */)
specbind (Qinhibit_quit, Qt);
-#ifndef NEW_OVERLAYS
obuffer = Fmarker_buffer (OVERLAY_START (overlay));
-#ifdef BOTH_OVERLAYS
- Lisp_Object obuffer2 = buffer_of_overlay (overlay);
- struct buffer *ob1 = XBUFFER (obuffer);
- struct buffer *ob2 = XBUFFER (obuffer2);
- eassert (ob1 == ob2);
-#endif
-#else
- obuffer = buffer_of_overlay (overlay);
-#endif
b = XBUFFER (buffer);
if (!NILP (obuffer))
{
ob = XBUFFER (obuffer);
-#ifndef NEW_OVERLAYS
+
o_beg = OVERLAY_POSITION (OVERLAY_START (overlay));
o_end = OVERLAY_POSITION (OVERLAY_END (overlay));
unchain_both (ob, overlay);
-#endif
-
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- old_start = XOVERLAY (overlay)->char_start;
- old_end = XOVERLAY (overlay)->char_end;
- overlay_tree_delete(&ob->overlays_root, XOVERLAY (overlay));
-#ifdef BOTH_OVERLAYS
- eassert (o_beg == old_start);
- eassert (o_end == old_end);
-#endif
-#endif
}
-#ifndef NEW_OVERLAYS
+
/* Set the overlay boundaries, which may clip them. */
Fset_marker (OVERLAY_START (overlay), beg, buffer);
Fset_marker (OVERLAY_END (overlay), end, buffer);
n_beg = marker_position (OVERLAY_START (overlay));
n_end = marker_position (OVERLAY_END (overlay));
-#endif
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- ptrdiff_t new_start = clip_to_bounds (BUF_BEG (b), XINT (beg),
- BUF_Z (b));
- ptrdiff_t new_end = clip_to_bounds(BUF_BEG (b), XINT (end),
- BUF_Z (b));
-#ifdef BOTH_OVERLAYS
- eassert (n_beg == new_start);
- eassert (n_end == new_end);
-#endif /* BPTH_OVERLAYS */
- XOVERLAY (overlay)->char_start = new_start;
- XOVERLAY (overlay)->char_end = new_end;
-#endif /* NEW_OVERLAYS || BOTH_OVERLAYS */
-
-#ifndef NEW_OVERLAYS
/* If the overlay has changed buffers, do a thorough redisplay. */
if (!EQ (buffer, obuffer))
{
/* Redisplay where the overlay was. */
if (ob)
modify_overlay (ob, o_beg, o_end);
+
/* Redisplay where the overlay is going to be. */
modify_overlay (b, n_beg, n_end);
}
@@ -4139,35 +3982,7 @@ buffer. */)
evaporate property. */
if (n_beg == n_end && !NILP (Foverlay_get (overlay, Qevaporate)))
return unbind_to (count, Fdelete_overlay (overlay));
-#else
- /* If the overlay has changed buffers, do a thorough redisplay. */
- if (!EQ (buffer, obuffer))
- {
- /* Redisplay where the overlay was. */
- if (ob)
- modify_overlay (ob, old_start, old_end);
- /* Redisplay where the overlay is going to be. */
- modify_overlay (b, new_start, new_end);
- }
- else
- /* Redisplay the area the overlay has just left, or just enclosed. */
- {
- if (old_start == new_start)
- modify_overlay (b, old_end, new_end);
- else if (old_end == new_end)
- modify_overlay (b, old_start, new_start);
- else
- modify_overlay (b, min (old_start, new_start),
- max (old_end, new_end));
- }
- /* Delete the overlay if it is empty after clipping and has the
- evaporate property. */
- if (new_start == new_end && !NILP (Foverlay_get (overlay, Qevaporate)))
- return unbind_to (count, Fdelete_overlay (overlay));
-#endif
-
-#ifndef NEW_OVERLAYS
/* Put the overlay into the new buffer's overlay lists, first on the
wrong list. */
if (n_end < b->overlay_center)
@@ -4183,9 +3998,7 @@ buffer. */)
/* This puts it in the right list, and in the right order. */
recenter_overlay_lists (b, b->overlay_center);
-#else
- insert_overlay_in_buffer_tree(b, overlay);
-#endif
+
return unbind_to (count, overlay);
}
@@ -4198,28 +4011,16 @@ DEFUN ("delete-overlay", Fdelete_overlay, Sdelete_overlay, 1, 1, 0,
ptrdiff_t count = SPECPDL_INDEX ();
CHECK_OVERLAY (overlay);
-#ifndef NEW_OVERLAYS
+
buffer = Fmarker_buffer (OVERLAY_START (overlay));
-#ifdef BOTH_OVERLAYS
- struct buffer *b1 = XBUFFER (buffer);
- struct buffer *b2 = XBUFFER (buffer_of_overlay (overlay));
- eassert (b1 == b2);
-#endif /* ifdef BOTH_OVERLAYS */
-#else
- buffer = buffer_of_overlay (overlay);
-#endif
if (NILP (buffer))
return Qnil;
b = XBUFFER (buffer);
specbind (Qinhibit_quit, Qt);
-#ifndef NEW_OVERLAYS
unchain_both (b, overlay);
drop_overlay (b, XOVERLAY (overlay));
-#else
- overlay_tree_delete(&b->overlays_root, XOVERLAY (overlay));
-#endif
/* When deleting an overlay with before or after strings, turn off
display optimizations for the affected buffer, on the basis that
@@ -4251,17 +4052,7 @@ DEFUN ("overlay-start", Foverlay_start, Soverlay_start, 1, 1, 0,
{
CHECK_OVERLAY (overlay);
-#ifdef NEW_OVERLAYS
- return make_number (XOVERLAY (overlay)->char_start);
-#else
-#ifdef BOTH_OVERLAYS
- Lisp_Object a[2];
- a[0] = make_number(XOVERLAY (overlay)->char_start);
- a[1] = Fmarker_position (OVERLAY_START (overlay));
- eassert (Feqlsign (2, a));
-#endif
- return Fmarker_position (OVERLAY_START (overlay));
-#endif
+ return (Fmarker_position (OVERLAY_START (overlay)));
}
DEFUN ("overlay-end", Foverlay_end, Soverlay_end, 1, 1, 0,
@@ -4270,17 +4061,7 @@ DEFUN ("overlay-end", Foverlay_end, Soverlay_end, 1, 1, 0,
{
CHECK_OVERLAY (overlay);
-#ifdef NEW_OVERLAYS
- return make_number (XOVERLAY (overlay)->char_end);
-#else
-#ifdef BOTH_OVERLAYS
- Lisp_Object a[2];
- a[0] = make_number(XOVERLAY (overlay)->char_end);
- a[1] = Fmarker_position (OVERLAY_END (overlay));
- eassert (Feqlsign (2, a));
-#endif
- return Fmarker_position (OVERLAY_END (overlay));
-#endif
+ return (Fmarker_position (OVERLAY_END (overlay)));
}
DEFUN ("overlay-buffer", Foverlay_buffer, Soverlay_buffer, 1, 1, 0,
@@ -4290,17 +4071,7 @@ Return nil if OVERLAY has been deleted. */)
{
CHECK_OVERLAY (overlay);
-#ifdef NEW_OVERLAYS
- return buffer_of_overlay (overlay);
-#else
-#ifdef BOTH_OVERLAYS
- struct buffer *b1, *b2;
- b1 = XBUFFER (buffer_of_overlay (overlay));
- b2 = XBUFFER (Fmarker_buffer(OVERLAY_START (overlay)));
- eassert (b1 == b2);
-#endif
return Fmarker_buffer (OVERLAY_START (overlay));
-#endif
}
DEFUN ("overlay-properties", Foverlay_properties, Soverlay_properties, 1, 1, 0,
@@ -4470,7 +4241,6 @@ The lists you get are copies, so that changing them has no effect.
However, the overlays you get are the real objects that the buffer uses. */)
(void)
{
-#ifndef NEW_OVERLAYS
struct Lisp_Overlay *ol;
Lisp_Object before = Qnil, after = Qnil, tmp;
@@ -4486,9 +4256,6 @@ However, the overlays you get are the real objects that the buffer uses. */)
}
return Fcons (Fnreverse (before), Fnreverse (after));
-#else
- return Qnil;
-#endif
}
DEFUN ("overlay-recenter", Foverlay_recenter, Soverlay_recenter, 1, 1, 0,
@@ -4497,13 +4264,11 @@ That makes overlay lookup faster for positions near POS (but perhaps slower
for positions far away from POS). */)
(Lisp_Object pos)
{
-#ifndef NEW_OVERLAYS
ptrdiff_t p;
CHECK_NUMBER_COERCE_MARKER (pos);
p = clip_to_bounds (PTRDIFF_MIN, XINT (pos), PTRDIFF_MAX);
recenter_overlay_lists (current_buffer, p);
-#endif
return Qnil;
}
\f
@@ -5376,13 +5141,9 @@ init_buffer_once (void)
bset_mark_active (&buffer_defaults, Qnil);
bset_file_format (&buffer_defaults, Qnil);
bset_auto_save_file_format (&buffer_defaults, Qt);
-#ifndef NEW_OVERLAYS
set_buffer_overlays_before (&buffer_defaults, NULL);
set_buffer_overlays_after (&buffer_defaults, NULL);
buffer_defaults.overlay_center = BEG;
-#else
- buffer_defaults.overlays_root = OVERLAYS_SENTINEL;
-#endif
XSETFASTINT (BVAR (&buffer_defaults, tab_width), 8);
bset_truncate_lines (&buffer_defaults, Qnil);
diff --git a/src/buffer.h b/src/buffer.h
index 9b2d887..87b7cee 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -27,10 +27,6 @@ along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
#include "character.h"
#include "lisp.h"
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
-extern struct Lisp_Overlay *OVERLAY_SENTINEL;
-#endif
-
INLINE_HEADER_BEGIN
/* Accessing the parameters of the current buffer. */
@@ -866,7 +862,6 @@ struct buffer
/* Non-zero whenever the narrowing is changed in this buffer. */
bool_bf clip_changed : 1;
-#ifndef NEW_OVERLAYS
/* List of overlays that end at or before the current center,
in order of end-position. */
struct Lisp_Overlay *overlays_before;
@@ -877,11 +872,7 @@ struct buffer
/* Position where the overlay lists are centered. */
ptrdiff_t overlay_center;
-#endif
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- struct Lisp_Overlay *overlays_root;
-#endif
/* Changes in the buffer are recorded here for undo, and t means
don't record anything. This information belongs to the base
buffer of an indirect buffer. But we can't store it in the
@@ -1186,17 +1177,7 @@ set_buffer_intervals (struct buffer *b, INTERVAL i)
INLINE bool
buffer_has_overlays (void)
{
-#ifdef NEW_OVERLAYS
- bool ret = current_buffer->overlays_root != OVERLAY_SENTINEL;
-#else
- bool ret = current_buffer->overlays_before ||
- current_buffer->overlays_after;
-#ifdef BOTH_OVERLAYS
- eassert (ret == (current_buffer->overlays_root !=
- OVERLAY_SENTINEL));
-#endif
-#endif
- return ret;
+ return current_buffer->overlays_before || current_buffer->overlays_after;
}
/* Return character code of multi-byte form at byte position POS. If POS
@@ -1245,7 +1226,6 @@ buffer_window_count (struct buffer *b)
return b->window_count;
}
-#ifndef NEW_OVERLAYS
/* Overlays */
/* Return the marker that stands for where OV starts in the buffer. */
@@ -1266,7 +1246,6 @@ buffer_window_count (struct buffer *b)
#define OVERLAY_POSITION(P) \
(MARKERP (P) ? marker_position (P) : (emacs_abort (), 0))
-#endif
\f
/***********************************************************************
Buffer-local Variables
diff --git a/src/deps.mk b/src/deps.mk
index c6469e6..72f68ca 100644
--- a/src/deps.mk
+++ b/src/deps.mk
@@ -40,8 +40,7 @@ bidi.o:
globals.h $(config_h)
buffer.o: buffer.c buffer.h region-cache.h commands.h window.h \
$(INTERVALS_H) blockinput.h atimer.h systime.h character.h ../lib/unistd.h \
- indent.h keyboard.h coding.h keymap.h frame.h lisp.h globals.h
- $(config_h) $(OVERLAYS_H)
+ indent.h keyboard.h coding.h keymap.h frame.h lisp.h globals.h $(config_h)
callint.o: callint.c window.h commands.h buffer.h keymap.h globals.h msdos.h \
keyboard.h dispextern.h systime.h coding.h composite.h lisp.h \
character.h $(config_h)
diff --git a/src/emacs.c b/src/emacs.c
index 9a85213..bb85733 100644
--- a/src/emacs.c
+++ b/src/emacs.c
@@ -1425,7 +1425,6 @@ Using an Emacs configured with --with-x-toolkit=lucid does not have this problem
syms_of_floatfns ();
syms_of_buffer ();
- syms_of_overlays ();
syms_of_bytecode ();
syms_of_callint ();
syms_of_casefiddle ();
diff --git a/src/insdel.c b/src/insdel.c
index e844274..4ad1074 100644
--- a/src/insdel.c
+++ b/src/insdel.c
@@ -27,7 +27,6 @@ along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
#include "intervals.h"
#include "character.h"
#include "buffer.h"
-#include "overlays.h"
#include "window.h"
#include "region-cache.h"
@@ -841,10 +840,6 @@ insert_1_both (const char *string,
PT + nchars, PT_BYTE + nbytes,
before_markers);
- overlay_tree_adjust_for_insert(current_buffer->overlays_root, PT, PT
- + nchars, PT_BYTE, PT_BYTE + nbytes,
- before_markers);
-
offset_intervals (current_buffer, PT, nchars);
if (!inherit && buffer_intervals (current_buffer))
@@ -971,12 +966,6 @@ insert_from_string_1 (Lisp_Object string, ptrdiff_t pos, ptrdiff_t pos_byte,
PT_BYTE + outgoing_nbytes,
before_markers);
- overlay_tree_adjust_for_insert(current_buffer->overlays_root, PT,
- PT + nchars, PT_BYTE,
- PT_BYTE + outgoing_nbytes,
- before_markers);
-
-
offset_intervals (current_buffer, PT, nchars);
intervals = string_intervals (string);
@@ -1031,12 +1020,6 @@ insert_from_gap (ptrdiff_t nchars, ptrdiff_t nbytes, bool text_at_gap_tail)
adjust_markers_for_insert (ins_charpos, ins_bytepos,
ins_charpos + nchars, ins_bytepos + nbytes, 0);
- overlay_tree_adjust_for_insert(current_buffer->overlays_root,
- ins_charpos, ins_charpos + nchars
- , ins_bytepos, ins_bytepos + nbytes,
- 0);
-
-
if (buffer_intervals (current_buffer))
{
offset_intervals (current_buffer, ins_charpos, nchars);
@@ -1180,11 +1163,6 @@ insert_from_buffer_1 (struct buffer *buf,
PT_BYTE + outgoing_nbytes,
0);
- overlay_tree_adjust_for_insert(current_buffer->overlays_root, PT, PT
- + nchars, PT_BYTE,
- PT_BYTE + outgoing_nbytes, 0);
-
-
offset_intervals (current_buffer, PT, nchars);
/* Get the intervals for the part of the string we are inserting. */
@@ -1235,22 +1213,11 @@ adjust_after_replace (ptrdiff_t from, ptrdiff_t from_byte,
if (GAP_SIZE > 0) *(GPT_ADDR) = 0; /* Put an anchor. */
if (nchars_del > 0)
- {
- adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
- len, len_byte);
- overlay_tree_adjust_for_replace(current_buffer->overlays_root,
- from, from_byte, nchars_del,
- nbytes_del, len, len_byte);
- }
+ adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
+ len, len_byte);
else
- {
- adjust_markers_for_insert (from, from_byte,
- from + len, from_byte + len_byte, 0);
- overlay_tree_adjust_for_insert(current_buffer->overlays_root,
- from, from + len, from_byte,
- from_byte + len_byte, 0);
- }
-
+ adjust_markers_for_insert (from, from_byte,
+ from + len, from_byte + len_byte, 0);
if (nchars_del > 0)
record_delete (from, prev_text, false);
@@ -1428,14 +1395,8 @@ replace_range (ptrdiff_t from, ptrdiff_t to, Lisp_Object new,
/* Adjust markers for the deletion and the insertion. */
if (markers)
- {
- adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
- inschars, outgoing_insbytes);
- overlay_tree_adjust_for_replace (current_buffer->overlays_root,
- from, from_byte, nchars_del,
- nbytes_del, inschars,
- outgoing_insbytes);
- }
+ adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
+ inschars, outgoing_insbytes);
/* Adjust the overlay center as needed. This must be done after
adjusting the markers that bound the overlays. */
@@ -1549,15 +1510,9 @@ replace_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
/* Adjust markers for the deletion and the insertion. */
if (markers
- && ! (nchars_del == 1 && inschars == 1 && nbytes_del ==
- insbytes))
- {
- adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
- inschars, insbytes);
- overlay_tree_adjust_for_replace (current_buffer->overlays_root,
- from, from_byte, nchars_del,
- nbytes_del, inschars, insbytes);
- }
+ && ! (nchars_del == 1 && inschars == 1 && nbytes_del == insbytes))
+ adjust_markers_for_replace (from, from_byte, nchars_del, nbytes_del,
+ inschars, insbytes);
/* Adjust the overlay center as needed. This must be done after
adjusting the markers that bound the overlays. */
@@ -1759,8 +1714,6 @@ del_range_2 (ptrdiff_t from, ptrdiff_t from_byte,
/* Relocate all markers pointing into the new, larger gap to point
at the end of the text before the gap. */
adjust_markers_for_delete (from, from_byte, to, to_byte);
- overlay_tree_adjust_for_delete(current_buffer->overlays_root, from,
- from_byte, to, to_byte);
MODIFF++;
CHARS_MODIFF = MODIFF;
diff --git a/src/lisp.h b/src/lisp.h
index d5cbec6..e0eb52a 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2112,30 +2112,11 @@ struct Lisp_Overlay
{
ENUM_BF (Lisp_Misc_Type) type : 16; /* = Lisp_Misc_Overlay */
bool_bf gcmarkbit : 1;
-
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- bool_bf start_insertion_type : 1;
- bool_bf end_insertion_type : 1;
- unsigned spacer : 13;
-#else
unsigned spacer : 15;
-#endif
-
struct Lisp_Overlay *next;
Lisp_Object start;
Lisp_Object end;
Lisp_Object plist;
-
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
- ptrdiff_t char_start, char_end;
- ptrdiff_t byte_start, byte_end;
- ptrdiff_t max;
-
- /* For the tree. */
- Lisp_Object parent; /* buffer or parent node */
- struct Lisp_Overlay *left, *right;
- unsigned level;
-#endif
};
/* Types of data which may be saved in a Lisp_Save_Value. */
@@ -3984,10 +3965,7 @@ extern void adjust_overlays_for_insert (ptrdiff_t, ptrdiff_t);
extern void adjust_overlays_for_delete (ptrdiff_t, ptrdiff_t);
extern void fix_start_end_in_overlays (ptrdiff_t, ptrdiff_t);
extern void report_overlay_modification (Lisp_Object, Lisp_Object, bool,
- Lisp_Object, Lisp_Object,
- Lisp_Object);
-
-
+ Lisp_Object, Lisp_Object, Lisp_Object);
extern bool overlay_touches_p (ptrdiff_t);
extern Lisp_Object other_buffer_safely (Lisp_Object);
extern Lisp_Object get_truename_buffer (Lisp_Object);
@@ -3996,10 +3974,6 @@ extern void init_buffer (int);
extern void syms_of_buffer (void);
extern void keys_of_buffer (void);
-/* Defined in overlay.c */
-
-extern void syms_of_overlays(void);
-
/* Defined in marker.c. */
extern ptrdiff_t marker_position (Lisp_Object);
diff --git a/src/overlays.c b/src/overlays.c
deleted file mode 100644
index c60a887..0000000
--- a/src/overlays.c
+++ /dev/null
@@ -1,800 +0,0 @@
-/*
- * Copyright (C) 2016 Joakim Jalap
- *
- * This program is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- */
-
-/* This file implements an Arne Andersson-tree (AA-tree) for buffer
- overlays. It is an augmented interval tree. Basically each node
- has an interval and a 'max' value, which is the largest upper
- interval bound which appears in the subtree rooted in the node.
-
- The implementation of the tree functions is written as closely as
- possible to the one presented in Anderssons paper (REF)[1], but with a
- few differences. The code in [1] is written in Pascal, which has
- proper pass by reference. Unfortunately C doesn't really have this;
- this is the reason for passing around pointers to pointers.
-
- Also this tree has parent references, and the code in the delete
- routine is a bit more complicated because we need to delete the
- actual memory area, so as to not trip up the GC.
-
- The fact that this is an augmented tree also makes the rebalancing
- operation (split and skew) a bit more complex.
- */
-#include "overlays.h"
-#include "buffer.h"
-
-extern void
-modify_overlay (struct buffer *, ptrdiff_t, ptrdiff_t);
-
-/* Return the max of a, b and c. */
-static inline ptrdiff_t
-overlay_max (ptrdiff_t a, ptrdiff_t b, ptrdiff_t c)
-{
- ptrdiff_t bc_max = max(b, c);
- return max(a, bc_max);
-}
-
-/* Find what the max value should be for X. */
-static inline ptrdiff_t
-overlay_find_max (struct Lisp_Overlay *x)
-{
- return overlay_max(x->left->max, x->right->max, x->char_end);
-}
-
-/* The sentinel node. This indicates the bottom of the tree. It is
- basically a way to avoid having to check for NULL pointers all the
- time. */
-struct Lisp_Overlay OVERLAY_SENTINEL_NODE =
- {
- Lisp_Misc_Overlay, /* type */
- 1, /* gcmarkbit */
- 0, /* start_insertion_type */
- 0, /* end_insertion_type */
- 0, /* spacer */
- NULL, /* next */
- 0, /* start */
- 0, /* end */
- 0, /* plist */
- 0, /* char_start */
- 0, /* char_end */
- 0, /* byte_start */
- 0, /* byte_end */
- 0, /* max */
- 0, /* parent */
- &OVERLAY_SENTINEL_NODE, /* left */
- &OVERLAY_SENTINEL_NODE, /* right */
- 0 /* level */
- };
-
-struct Lisp_Overlay * OVERLAY_SENTINEL = &OVERLAY_SENTINEL_NODE;
-
-/* This function determines where overlays are inserted in the tree.
- FIXME: I didn't think too hard about this...
-*/
-static inline bool
-overlay_lt (struct Lisp_Overlay *a, struct Lisp_Overlay *b)
-{
- if (a->char_start < b->char_start)
- return true;
- else if (a->char_start > b->char_start)
- return false;
-
- if (a->char_end < b->char_end)
- return true;
- else if (a->char_end > b->char_end)
- return false;
-
- return false;
-}
-
-/* Rebalancing. See Andersson's paper for a good explaination. This
- is a bit more complicated than his code, since we need to maintain
- parent pointer and max field.
-*/
-inline static void
-overlay_skew (struct Lisp_Overlay **tt)
-{
- struct Lisp_Overlay *t = *tt;
- if (t->left->level == t->level && t != OVERLAY_SENTINEL)
- {
- struct Lisp_Overlay *tmp = t;
- t = *tt = t->left;
- tmp->left = t->right;
- t->right = tmp;
-
- tmp->max = overlay_find_max(tmp);
- t->max = overlay_find_max(t);
-
- t->parent = tmp->parent;
- XSETMISC (tmp->parent, t);
- if (tmp->left != OVERLAY_SENTINEL)
- XSETMISC (tmp->left->parent, tmp);
- }
-}
-
-/* Rebalancing. See Andersson's paper for a good explaination. This
- is a bit more complicated than his code, since we need to maintain
- parent pointer and max field.
-*/
-inline static void
-overlay_split (struct Lisp_Overlay **tt)
-{
- struct Lisp_Overlay *t = *tt;
- if (t->level == t->right->right->level && t != OVERLAY_SENTINEL)
- {
- struct Lisp_Overlay *tmp = t;
- t = *tt = t->right;
- tmp->right = t->left;
- t->left = tmp;
- t->level++;
-
- tmp->max = overlay_find_max(tmp);
- t->max = overlay_find_max(t);
-
- t->parent = tmp->parent;
- XSETMISC (tmp->parent, t);
- }
-}
-
-/* Insert NODE in TREE. When it is inserted, set its parent to
- PARENT. On the way up after the insertion, adjust the max field of
- each node if needed.
- */
-static ptrdiff_t
-overlay_tree_insert_internal (struct Lisp_Overlay **tree,
- struct Lisp_Overlay *parent,
- struct Lisp_Overlay *node)
-{
- struct Lisp_Overlay *t = *tree;
- if (t == OVERLAY_SENTINEL)
- {
- node->left = node->right = OVERLAY_SENTINEL;
- node->level = 1;
- node->max = node->char_end;
- XSETMISC (node->parent, parent);
- *tree = node;
- return node->max;
- }
- else
- {
- struct Lisp_Overlay **dir = overlay_lt (node, t) ?
- &t->left : &t->right;
-
- ptrdiff_t child_max = overlay_tree_insert_internal(dir, t, node);
- if (child_max > t->max)
- t->max = child_max;
- }
- overlay_skew (&t);
- overlay_split (&t);
- return t->max;
-}
-
-/* Insert NODE into TREE.
- */
-void
-overlay_tree_insert (struct Lisp_Overlay **tree,
- struct Lisp_Overlay *node)
-{
- overlay_tree_insert_internal(tree, *tree, node);
-}
-
-/* Delete NODE from TREE.
- */
-void
-overlay_tree_delete (struct Lisp_Overlay **tree,
- struct Lisp_Overlay *node)
-{
- struct Lisp_Overlay *t = *tree;
- static __thread struct Lisp_Overlay *last, *deleted;
-
- if (t == OVERLAY_SENTINEL)
- return;
-
- last = t;
- if (overlay_lt(node, t))
- overlay_tree_delete (&t->left, node);
- else
- {
- deleted = t;
- overlay_tree_delete (&t->right, node);
- }
-
-
- if (t == last &&
- deleted != OVERLAY_SENTINEL &&
- node == deleted)
- {
- last->left = deleted->left;
- last->right = deleted->right;
-
- if (BUFFERP (deleted->parent))
- {
- struct buffer *b = XBUFFER (deleted->parent);
- if (last == deleted)
- {
- b->overlays_root = OVERLAY_SENTINEL;
- }
- else
- {
- b->overlays_root = last;
- last->parent = deleted->parent;
- }
- }
- else
- {
- eassert (OVERLAYP (deleted->parent));
- struct Lisp_Overlay *up = XOVERLAY (deleted->parent);
- eassert (up->left == deleted || up->right == deleted);
- if (up->left == deleted)
- up->left = last == deleted ? OVERLAY_SENTINEL
- : last;
- else
- up->right = last == deleted ? OVERLAY_SENTINEL
- : last;
-
- XSETMISC (last->parent, up);
- }
- deleted->parent = Qnil;
- }
- else if (t->left->level < t->level - 1
- || t->right->level < t->level - 1)
- {
- t->level--;
- if (t->right->level > t->level)
- t->right->level = t->level;
-
- /* Andersson leaves it as 'an exercise for the reader' to prove
- that these rebalancing operions are enough. Don't you just love
- when that happens? */
- overlay_skew (&t);
- overlay_skew (&t->right);
- overlay_skew (&t->right->right);
- overlay_split (&t);
- overlay_split (&t->right);
- }
-}
-
-static void
-overlay_tree_drop_all_internal (struct buffer *buf,
- struct Lisp_Overlay *tree)
-{
- if (tree == OVERLAY_SENTINEL)
- return;
- overlay_tree_drop_all_internal (buf, tree->left);
- overlay_tree_drop_all_internal (buf, tree->right);
- modify_overlay (buf, tree->char_start, tree->char_end);
-}
-
-void
-overlay_tree_drop_all(struct buffer *buf)
-{
- overlay_tree_drop_all_internal (buf, buf->overlays_root);
- buf->overlays_root = OVERLAY_SENTINEL;
-}
-
-/* Add ELM to VECP at IDX. VECP has size VEC_SIZE. If IDX is at the
- end of VECP, realloc VECP and update VEC_SIZE.
- */
-static inline void
-add_to_vec (ptrdiff_t *vec_size, Lisp_Object **vecp,
- ptrdiff_t* idx, struct Lisp_Overlay *elm)
-{
- if (*idx == *vec_size - 1)
- {
- *vec_size += 50;
- *vecp = xnrealloc (*vecp, *vec_size, sizeof (Lisp_Object));
- }
-
- XSETMISC((*vecp)[(*idx)++], elm);
-}
-
-
-/* Add all nodes in TREE to VEC_PTR, which has size VEC_SIZE, starting
- from IDX. The nodes will be added in the order they have in the
- tree.
- */
-static void
-overlay_tree_all_internal (struct Lisp_Overlay *tree,
- ptrdiff_t *vec_size,
- Lisp_Object **vec_ptr,
- ptrdiff_t *idx)
-{
- if (tree == OVERLAY_SENTINEL)
- return;
-
- overlay_tree_all_internal (tree->left, vec_size,
- vec_ptr, idx);
- add_to_vec (vec_size, vec_ptr, idx, tree);
- overlay_tree_all_internal (tree->right, vec_size,
- vec_ptr, idx);
-}
-
-/* Put all nodes from TREE into VEC_PTR, adjusting VEC_SIZE as
- necessary.
- */
-ptrdiff_t
-overlay_tree_all (struct Lisp_Overlay *tree, ptrdiff_t *vec_size,
- Lisp_Object **vec_ptr)
-{
- ptrdiff_t n = 0;
- overlay_tree_all_internal (tree, vec_size, vec_ptr, &n);
- return n;
-}
-
-/* Add all nodes in TREE which contain POS to VEC_PTR at IDX.
- VEC_SIZE will be adjusted.
- */
-static void
-overlay_tree_at_internal (struct Lisp_Overlay *tree, ptrdiff_t pos,
- ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
- ptrdiff_t *idx, ptrdiff_t *prev_ptr)
-{
- /* We are at a leaf. */
- if (tree == OVERLAY_SENTINEL)
- return;
-
- /* There's no subtree under here which can contain POS. Note
- tree->max, as this might be the closest before. */
- if (tree->max < pos)
- {
- if (tree->max > *prev_ptr)
- *prev_ptr = tree->max;
- return;
- }
-
-
- overlay_tree_at_internal (tree->left, pos, vec_size, vec_ptr,
- idx, prev_ptr);
-
- if (pos >= tree->char_start && pos <= tree->char_end)
- add_to_vec (vec_size, vec_ptr, idx, tree);
-
- /* If we are after POS, so are all the nodes to the right of us. */
- if (tree->char_start <= pos)
- overlay_tree_at_internal (tree->right, pos, vec_size, vec_ptr,
- idx, prev_ptr);
-}
-
-
-/* Find all nodes in TREE which contain POS and put them in VEC_PTR,
- growing it as necessary. The size of the vector VEC_PTR will be
- stored in VEC_SIZE. Return how many nodes were actually put in
- VEC_PTR.
- */
-ptrdiff_t
-overlay_tree_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
- ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr,
- ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
- bool chane_req)
-{
- ptrdiff_t idx = 0;
- ptrdiff_t max_before = 0;
-
- /* Due to the recursion order in `overlay_tree_at_internal' the
- overlays are sorted by their `char_start' in VEC_PTR. */
- overlay_tree_at_internal (tree, pos, vec_size, vec_ptr,
- &idx, &max_before);
-
- if (prev_ptr && max_before)
- *prev_ptr = max_before;
- else
- *prev_ptr = BEGV;
-
- /* If NEXT_PTR is not NULL, it should be set to the start_char of
- the leftmost descendant of the right child of the last element in
- VEC_PTR, or ZV if the right child is OVERLAY_SENTINEL. */
- if (next_ptr && idx)
- {
- struct Lisp_Overlay *last = XOVERLAY ((*vec_ptr)[idx - 1]);
- if (last->right != OVERLAY_SENTINEL)
- {
- last = last->right;
- while (last->left != OVERLAY_SENTINEL)
- last = last->left;
- *next_ptr = last->char_start;
- }
- else
- *next_ptr = ZV;
- }
-
- /* IDX points one behind the last element, so it is the size */
- return idx;
-}
-
-static inline void
-add_entry_to_vec (ptrdiff_t *vec_size, struct overlay_entry **vecp,
- ptrdiff_t* idx, Lisp_Object overlay,
- Lisp_Object str, bool after_p)
-{
- if (*idx == *vec_size - 1)
- {
- *vec_size += 50;
- *vecp = xnrealloc (*vecp, *vec_size,
- sizeof (struct overlay_entry));
- }
-
- Lisp_Object priority = Foverlay_get ((OVERLAY), Qpriority);
- EMACS_INT prio = INTEGERP (priority) ? XINT (priority) : 0;
-
-#define SET_ENTRY(ENT, ELM) (*vecp)[*idx].ENT = (ELM)
- SET_ENTRY(string, str);
- SET_ENTRY(overlay, overlay);
- SET_ENTRY(priority, prio);
- SET_ENTRY(after_string, after_p);
-#undef SET_ENTRY
-
- (*idx)++;
-}
-
-ptrdiff_t
-overlay_tree_load_overlays (struct Lisp_Overlay *tree, ptrdiff_t pos,
- ptrdiff_t *vec_size, ptrdiff_t **vec_ptr,
- ptridff_t *idx, struct window *w)
-{
- Lisp_Object window, invisible, str, ov;
- int invis;
-
- eassert (*idx == 0);
-
- if (tree == OVERLAY_SENTINEL || tree->max > pos)
- return;
-
- if (tree->char_start != pos && tree->char_end != pos)
- goto cont;
-
- window = lookup_char_property (tree->plist, Qwindow, 0);
- if (WINDOWP (window) && XWINDOW (window) != it->w)
- goto cont;
-
- invisible = lookup_char_property (tree->plist, Qinvisible, 0);
- invis = TEXT_PROP_MEANS_INVISIBLE (invisible);
-
- if ((tree->char_start == pos || (tree->char_end == pos && invis))
- && (str = lookup_char_property (tree->plist, Qbefore_string, 0),
- STRINGP (str))
- && SCHARS (str))
- {
- XSETMISC (ov, tree);
- add_entry_to_vec(vec_size, vec_ptr, idx, ov, str, false);
- }
-
- if ((tree->char_end == pos || (tree->char_start == pos && invis))
- && (str = lookup_char_property (tree->plist, Qafter_string, 0),
- STRINGP (str))
- && SCHARS (str))
- {
- XSETMISC (ov, tree);
- add_entry_to_vec(vec_size, vec_ptr, idx, ov, str, true);
- }
-
-
- cont:
- overlay_tree_load_overlays(tree->left, pos, vec_size, vec_ptr, w);
- if (tree->char_start <= pos)
- overlay_tree_load_overlays(tree->right, pos, vec_size, vec_ptr, w);
-}
-
-/* Return the buffer OVERLAY is in or nil if OVERLAY has been
- deleted. */
-Lisp_Object
-buffer_of_overlay (Lisp_Object overlay)
-{
- Lisp_Object o = overlay;
- while (!NILP (XOVERLAY (o)->parent) &&
- !BUFFERP (XOVERLAY (o)->parent))
- {
- eassert (OVERLAYP (XOVERLAY (o)->parent));
- eassert (XOVERLAY (XOVERLAY (o)->parent) != XOVERLAY (o));
-
- o = XOVERLAY (o)->parent;
- }
- return XOVERLAY (o)->parent;
-}
-
-void
-overlay_tree_zero_size_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
- Lisp_Object hit_list)
-{
- if (tree == OVERLAY_SENTINEL || tree->max < pos)
- return;
-
- if (tree->char_start == pos && tree->char_end == pos)
- {
- Lisp_Object ov;
- XSETMISC (ov, tree);
- Fcons(hit_list, ov);
- }
-
- overlay_tree_zero_size_at (tree->right, pos, hit_list);
- if (pos >= tree->char_start)
- overlay_tree_zero_size_at (tree->left, pos, hit_list);
-}
-
-/* Adjust CHARPOS asn BYTEPOS for an insert from FROM_CHAR (FROM_BYTE)
- to TO_CHAR (TO_BYTE).
- FIXME: insertion_type and before.
- */
-static void
-adjust_pos_for_insert (ptrdiff_t *charpos, ptrdiff_t *bytepos,
- ptrdiff_t from_char, ptrdiff_t to_char,
- ptrdiff_t from_byte, ptrdiff_t to_byte,
- bool insertion_type , bool before)
-{
- if (*bytepos > from_byte)
- {
- *bytepos += to_byte - from_byte;
- *charpos += to_char - from_char;
- }
- else if (*bytepos == from_byte && insertion_type)
- {
- *bytepos = to_byte;
- *charpos = to_char;
- }
-}
-
-/* Adjust all nodes in TREE for an insert from FROM_CHAR (FROM_BYTE)
- to TO_CHAR (TO_BYTE). Return TREEs max.
- FIXME: before.
- */
-ptrdiff_t
-overlay_tree_adjust_for_insert (struct Lisp_Overlay *tree,
- ptrdiff_t from_char,
- ptrdiff_t to_char,
- ptrdiff_t from_byte,
- ptrdiff_t to_byte,
- bool before)
-{
- /* If we are at a leaf or all nodes in TREE are before the insert,
- return. */
- if (tree == OVERLAY_SENTINEL || tree->max < from_char)
- return tree->max;
-
- /* Adjust the start postions. */
- adjust_pos_for_insert(&tree->char_start, &tree->byte_start, from_char,
- to_char, from_byte, to_byte,
- tree->start_insertion_type, before);
- /* Adjust the end postions. */
- adjust_pos_for_insert(&tree->char_end, &tree->byte_end, from_char,
- to_char, from_byte, to_byte,
- tree->end_insertion_type, before);
-
- ptrdiff_t r,l;
-
- l = overlay_tree_adjust_for_insert (tree->left, from_char,
- to_char, from_byte,
- to_byte, before);
- r = overlay_tree_adjust_for_insert (tree->right, from_char,
- to_char, from_byte,
- to_byte, before);
-
- tree->max = overlay_max(l, r, tree->char_end);
- return tree->max;
-}
-
-/* Adjust CHARPOS and BYTEPOS for a delete from FROM_CHAR (FROM_BYTE)
- to TO_CHAR (TO_BYTE).
- */
-static void
-adjust_pos_for_delete (ptrdiff_t *charpos, ptrdiff_t *bytepos,
- ptrdiff_t from_char, ptrdiff_t from_byte,
- ptrdiff_t to_char, ptrdiff_t to_byte)
-{
- if (*charpos > to_char)
- {
- *charpos = to_char - from_char;
- *bytepos = to_byte - from_byte;
- }
- else if (*charpos > from_char)
- {
- *charpos = from_char;
- *bytepos = from_byte;
- }
-}
-
-/* Adjust TREE for a delete from FROM_CHAR (FROM_BYTE) to TO_CHAR
- (TO_BYTE).
- */
-ptrdiff_t
-overlay_tree_adjust_for_delete (struct Lisp_Overlay *tree,
- ptrdiff_t from_char, ptrdiff_t from_byte,
- ptrdiff_t to_char, ptrdiff_t to_byte)
-{
- if (tree == OVERLAY_SENTINEL || tree->max < from_char)
- return tree->max;
-
- adjust_pos_for_delete(&tree->char_start, &tree->byte_start, from_char,
- from_byte, to_char, to_byte);
- adjust_pos_for_delete(&tree->char_end, &tree->byte_end, from_char,
- from_byte, to_char, to_byte);
-
- ptrdiff_t r, l;
-
- l = overlay_tree_adjust_for_delete(tree->left, from_char, from_byte,
- to_char, to_byte);
- r = overlay_tree_adjust_for_delete(tree->right, from_char, from_byte,
- to_char, to_byte);
-
- tree->max = overlay_max(l, r, tree->char_end);
- return tree->max;
-}
-
-/* Adjust CHARPOS and BYTEPOS for a delete from FROM_CHAR (FROM_BYTE)
- to TO_CHAR (TO_BYTE).
- */
-static void
-adjust_pos_for_replace (ptrdiff_t *charpos, ptrdiff_t *bytepos,
- ptrdiff_t from_char, ptrdiff_t from_byte,
- ptrdiff_t old_chars, ptrdiff_t old_bytes,
- ptrdiff_t new_chars, ptrdiff_t new_bytes)
-{
- ptrdiff_t diff_chars = new_chars - old_chars;
- ptrdiff_t diff_bytes = new_bytes - old_bytes;
-
- if (*bytepos >= (from_byte + old_bytes))
- {
- *charpos += diff_chars;
- *bytepos += diff_bytes;
- }
- else if (*bytepos > from_byte)
- {
- *charpos = from_char;
- *bytepos = from_byte;
- }
-}
-
-/* Adjust TREE for a delete from FROM_CHAR (FROM_BYTE)
- to TO_CHAR (TO_BYTE).
- */
-ptrdiff_t
-overlay_tree_adjust_for_replace (struct Lisp_Overlay *tree,
- ptrdiff_t from_char,
- ptrdiff_t from_byte,
- ptrdiff_t old_chars,
- ptrdiff_t old_bytes,
- ptrdiff_t new_chars,
- ptrdiff_t new_bytes)
-{
- if (tree == OVERLAY_SENTINEL || tree->max <= from_byte)
- return tree->max;
-
- adjust_pos_for_replace(&tree->char_start, &tree->byte_start,
- from_char, from_byte, old_chars, old_bytes,
- new_chars, new_bytes);
- adjust_pos_for_replace(&tree->char_end, &tree->byte_end,
- from_char, from_byte, old_chars, old_bytes,
- new_chars, new_bytes);
-
- ptrdiff_t r, l;
-
- l = overlay_tree_adjust_for_replace(tree->left, from_char,
- from_byte, old_chars,
- old_bytes, new_chars,
- new_bytes);
- r = overlay_tree_adjust_for_replace(tree->right, from_char,
- from_byte, old_chars,
- old_bytes, new_chars,
- new_bytes);
-
- tree->max = overlay_max(l, r, tree->char_end);
- return tree->max;
-}
-
-
-DEFUN("overlay-parent", Foverlay_parent, Soverlay_parent, 1, 1, 0,
- doc: /* Parent of overlay. An overlay or a buffer. */)
- (Lisp_Object overlay)
-{
- if (!OVERLAYP(overlay))
- signal_error("Not an overlay", Qnil);
- return XOVERLAY (overlay)->parent;
-}
-
-DEFUN("overlay-info", Foverlay_info, Soverlay_info, 1, 1, 0,
- doc: /* Info about OVERLAY. */)
- (Lisp_Object overlay)
-{
- if (!OVERLAYP(overlay))
- signal_error("Not an overlay", Qnil);
- Lisp_Object ret;
- struct Lisp_Overlay *o = XOVERLAY (overlay);
- Lisp_Object left, right, this;
- if (o->left != OVERLAY_SENTINEL)
- XSETMISC(left, o->left);
- else
- left = Qt;
-
- if (o->right != OVERLAY_SENTINEL)
- XSETMISC(right, o->right);
- else
- right = Qt;
-
- XSETMISC (this, o);
-
- ret = list5(Fcons(Fcons(make_number(o->char_start),
- make_number(o->char_end)),
- make_number(o->max)),
- this,
- o->parent,
- make_number (o->level),
- Fcons(left,
- right));
- return ret;
-}
-
-DEFUN("overlays-in-buffer", Foverlays_in_buffer, Soverlays_in_buffer,
- 0, 1, 0,
- doc: /* Return a list of all the overlays in BUFFER. */)
- (Lisp_Object buffer)
-{
- Lisp_Object ret;
- struct buffer *b;
- if (!NILP (buffer))
- b = XBUFFER (buffer);
- else
- b = current_buffer;
-
-
- ptrdiff_t vec_size = 30;
- Lisp_Object *vec = xnmalloc (vec_size, sizeof (Lisp_Object));
-
-
- ptrdiff_t noverlays = overlay_tree_all(b->overlays_root,
- &vec_size, &vec);
- ret = Flist(noverlays, vec);
-
- return ret;
-}
-
-DEFUN("overlay-tree-at", Foverlay_tree_at, Soverlay_tree_at,
- 1, 2, 0,
- doc: /* Return a list of all overlays in BUFFER. If BUFFER is
- nil, use the current buffer. */)
- (Lisp_Object pos, Lisp_Object buffer)
-{
- CHECK_NUMBER_COERCE_MARKER (pos);
-
- ptrdiff_t next, prev;
- ptrdiff_t bufpos = XINT (pos);
-
- Lisp_Object ret;
- struct buffer *b;
- if (!NILP (buffer))
- b = XBUFFER (buffer);
- else
- b = current_buffer;
-
-
- ptrdiff_t vec_size = 30;
- Lisp_Object *vec = xnmalloc (vec_size, sizeof (Lisp_Object));
-
-
- ptrdiff_t noverlays = overlay_tree_at(b->overlays_root, bufpos,
- &next, &prev,
- &vec_size, &vec, false);
-
- ret = Flist(noverlays, vec);
-
- return ret;
-}
-
-void
-syms_of_overlays (void)
-{
- defsubr (&Soverlay_parent);
- defsubr (&Soverlay_info);
- defsubr (&Soverlays_in_buffer);
- defsubr (&Soverlay_tree_at);
-}
diff --git a/src/overlays.h b/src/overlays.h
deleted file mode 100644
index d5d85a9..0000000
--- a/src/overlays.h
+++ /dev/null
@@ -1,75 +0,0 @@
-
-#ifndef OVERLAYS_H
-#define OVERLAYS_H
-
-#include <config.h>
-#include "lisp.h"
-
-extern struct Lisp_Overlay OVERLAY_SENTINEL_NODE;
-
-extern struct Lisp_Overlay * OVERLAY_SENTINEL;
-
-struct overlay_entry
-{
- Lisp_Object overlay;
- Lisp_Object string;
- EMACS_INT priority;
- bool after_string_p;
-};
-
-void
-overlay_tree_insert (struct Lisp_Overlay **tree,
- struct Lisp_Overlay *node);
-
-void
-overlay_tree_delete (struct Lisp_Overlay **tree,
- struct Lisp_Overlay *node);
-
-void
-overlay_tree_drop_all (struct buffer *buf);
-
-Lisp_Object
-buffer_of_overlay (Lisp_Object overlay);
-
-ptrdiff_t
-overlay_tree_all (struct Lisp_Overlay *tree, ptrdiff_t *vec_size,
- Lisp_Object **vec_ptr);
-
-ptrdiff_t
-overlay_tree_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
- ptrdiff_t *next_ptr, ptrdiff_t *prev_ptr,
- ptrdiff_t *vec_size, Lisp_Object **vec_ptr,
- bool chane_req);
-
-void
-overlay_tree_zero_size_at (struct Lisp_Overlay *tree, ptrdiff_t pos,
- Lisp_Object hit_list);
-
-ptrdiff_t
-overlay_tree_adjust_for_insert (struct Lisp_Overlay *tree,
- ptrdiff_t from_char,
- ptrdiff_t to_char,
- ptrdiff_t from_byte,
- ptrdiff_t to_byte,
- bool before);
-
-ptrdiff_t
-overlay_tree_adjust_for_delete (struct Lisp_Overlay *tree,
- ptrdiff_t from_char, ptrdiff_t from_byte,
- ptrdiff_t to_char, ptrdiff_t to_byte);
-
-ptrdiff_t
-overlay_tree_adjust_for_replace (struct Lisp_Overlay *tree,
- ptrdiff_t from_char,
- ptrdiff_t from_byte,
- ptrdiff_t old_chars,
- ptrdiff_t old_bytes,
- ptrdiff_t new_chars,
- ptrdiff_t new_bytes);
-
-ptrdiff_t
-overlay_tree_at (struct Lisp_Overlay *tree, Lisp_Object **vecp,
- ptrdiff_t pos);
-
-
-#endif /* OVERLAYS_H */
diff --git a/src/xdisp.c b/src/xdisp.c
index 785853e..1289515 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -315,9 +315,6 @@ along with GNU Emacs. If not, see <http://www.gnu.org/licenses/>. */
#include "fontset.h"
#include "blockinput.h"
#include "xwidget.h"
-#if defined(NEW_OVERLAYS) || defined(BOTH_OVERLAYS)
-#include "overlays.h"
-#endif
#ifdef HAVE_WINDOW_SYSTEM
#include TERM_HEADER
#endif /* HAVE_WINDOW_SYSTEM */
@@ -5502,7 +5499,7 @@ handle_composition_prop (struct it *it)
/* The following structure is used to record overlay strings for
later sorting in load_overlay_strings. */
-#if !defined(NEW_OVERLAYS) && !defined(BOTH_OVERLAYS)
+
struct overlay_entry
{
Lisp_Object overlay;
@@ -5510,7 +5507,7 @@ struct overlay_entry
EMACS_INT priority;
bool after_string_p;
};
-#endif
+
/* Set up iterator IT from overlay strings at its current position.
Called from handle_stop. */
@@ -5712,7 +5709,6 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos)
if (charpos <= 0)
charpos = IT_CHARPOS (*it);
-#ifndef NEW_OVERLAYS
/* Append the overlay string STRING of overlay OVERLAY to vector
`entries' which has size `size' and currently contains `n'
elements. AFTER_P means STRING is an after-string of
@@ -5819,30 +5815,6 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos)
}
#undef RECORD_OVERLAY_STRING
-#ifdef BOTH_OVERLAYS
- struct window *sw = XWINDOW (window);
- ptrdiff_t n1, ii, jj;
- struct overlay_entry entriesbuf1[20];
- ptrdiff_t size1 = ARRAYELTS (entriesbuf);
- overlay_tree_load_overlays (current_buffer->overlays_root,
- charpos, &size, &entries, &n, sw);
- eassert (n1 == n);
- for (ii = 0; ii < n; ii++) {
- bool found = false;
- struct overlay_entry *oe1 = &entries[ii];
- for (jj = 0; jj < n; jj++) {
- struct overlay_entry *oe2 = &entries1[jj];
- if (*oe1 == *oe2)
- found = true;
- }
- eassert (found);
- }
-#endif
-#else /* if NEW_OVERLAYS is defined */
- struct window *sw = XWINDOW (window);
- overlay_tree_load_overlays (current_buffer->overlays_root,
- charpos, &size, &entries, &n, sw);
-#endif
/* Sort entries. */
if (n > 1)
@@ -5868,7 +5840,6 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos)
}
-
/* Get the first chunk of overlay strings at IT's current buffer
position, or at CHARPOS if that is > 0. Value is true if at
least one overlay string was found. */
diff --git a/test/lisp/overlay-tests.el b/test/lisp/overlay-tests.el
deleted file mode 100644
index 407aaee..0000000
--- a/test/lisp/overlay-tests.el
+++ /dev/null
@@ -1,70 +0,0 @@
-
-
-
-(require 'ert)
-
-(ert-deftest overlay-create-test ()
- " "
- (with-temp-buffer
- (insert "blueberrypancakes")
- (let ((o1 (make-overlay 4 9)))
- (should-not (overlay-get o1 'face))
- (should (overlayp o1))
- (should (= (overlay-start o1) 4))
- (should (= (overlay-end o1) 9))
- (should (eq (overlay-buffer o1) (current-buffer)))
- (let ((b (current-buffer)))
- (with-temp-buffer
- (should (eq (overlay-buffer o1) b))))
- (should (= (length (overlays-in (point-min) (point-max))) 1))
- (should (eq (car (overlays-in (point-min) (point-max))) o1)))))
-
-
-(ert-deftest overlay-move-test ()
- " "
- (with-temp-buffer
- (insert "blueberrypancakes")
- (let ((o1 (make-overlay 4 9)))
- ;; Test a "normal" move
- (should (= (overlay-start o1) 4))
- (should (= (overlay-end o1) 9))
- (should (eq (overlay-buffer o1) (current-buffer)))
- (move-overlay o1 3 10)
- (should (= (overlay-start o1) 3))
- (should (= (overlay-end o1) 10))
- (let ((b (current-buffer)))
- (with-temp-buffer
- (insert "blueberry")
- (move-overlay o1 2 4)
- (should (eq (overlay-buffer o1) b))
- (move-overlay o1 2 4 (current-buffer))
- (should (eq (overlay-buffer o1) (current-buffer)))
- (should (= (overlay-start o1) 2))
- (should (= (overlay-end o1) 4))))
- (move-overlay o1 1 50 (current-buffer))
- (should (eq (overlay-buffer o1) (current-buffer)))
- (should (= (overlay-start o1) 1))
- (should (= (overlay-end o1) (point-max))))))
-
-(ert-deftest overlay-front-advance-test ()
- (with-temp-buffer
- (insert "blueberrypancakes")
- (let ((o1 (make-overlay 1 5 nil t))
- (o2 (make-overlay 1 5))
- (str "creamy "))
- (goto-char (point-min))
- (insert str)
- (should (= (overlay-start o2) 1))
- (should (= (overlay-start o1) (1+ (length str)))))))
-
-(ert-deftest overlay-rear-advance-test ()
- (with-temp-buffer
- (insert "blueberrypancakes")
- (let ((o1 (make-overlay 7 18 nil nil t))
- (o2 (make-overlay 7 18))
- (str " for dinner"))
- (should (= (point-max) 18))
- (goto-char (point-max))
- (insert str)
- (should (= (overlay-end o1) (point-max)))
- (should (= (overlay-end o2) 18)))))
^ permalink raw reply related [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 12:43 ` Lars Ingebrigtsen
2016-09-20 16:19 ` Joakim Jalap
@ 2016-09-20 23:19 ` Richard Stallman
1 sibling, 0 replies; 110+ messages in thread
From: Richard Stallman @ 2016-09-20 23:19 UTC (permalink / raw)
To: Lars Ingebrigtsen; +Cc: joakim.jalap, emacs-devel
[[[ To any NSA and FBI agents reading my email: please consider ]]]
[[[ whether defending the US Constitution against all enemies, ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> I seem to recall that somebody made the suggestion earlier to make
> overlays a special case of text properties, and then getting rid of most
> of the low-level overlay code.
Since overlays have to be discarded whenever text is copied,
the need to go through the text properties and discard those
that are really overlays could make things substantially slower.
--
Dr Richard Stallman
President, Free Software Foundation (gnu.org, fsf.org)
Internet Hall-of-Famer (internethalloffame.org)
Skype: No way! See stallman.org/skype.html.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
` (2 preceding siblings ...)
2016-09-20 14:40 ` Eli Zaretskii
@ 2016-09-21 14:52 ` Stefan Monnier
2016-09-21 15:58 ` Eli Zaretskii
2016-09-22 10:35 ` Joakim Jalap
2017-02-03 8:49 ` Andreas Politz
4 siblings, 2 replies; 110+ messages in thread
From: Stefan Monnier @ 2016-09-21 14:52 UTC (permalink / raw)
To: emacs-devel
> What I've been looking at is replacing the current implementation of
> buffer overlays with a self balanced tree. I chose an AA-tree as that
> seemed simple enough for me to grasp :).
Could you describe how you use this tree? An AA-tree is indexed by
a single "number", whereas overlays have two independent "numbers".
So how to use this AA-tree to implement an *interval* tree?
This should be documented in the code. E.g. the "struct Lisp_Overlay"
should define very clearly the meaning of char_start, char_end, left,
and right (i.e. which overlays go to the left, and which go to the
right).
While looking for an answer in the text I found:
/* This function determines where overlays are inserted in the tree.
FIXME: I didn't think too hard about this...
*/
which makes me suspect your design might not be quite right.
Have you read https://en.wikipedia.org/wiki/Interval_tree ?
[ BTW, our convention is to put the "*/" at the end of the last line
rather than alone on the next line. ]
This said, reading overlay_tree_insert_internal, I have the impression
that you're implementing what wikipedia describes as an "Augmented tree"
where the basic tree is your AA-tree, indexed by the left position of
the overlays, with the `max` field being the "augmented" data, which
sounds just fine.
Is that right?
> Anyway, I basically have two questions for you experts:
> 1) Is it worth continuing down this path?
I don't see why not.
> 2) If so, what's the best way to go about something like this? Replacing
> the whole thing at once seems very hard, but I don't really know how to
> go about replacing it little by little.
The only places you absolutely need to replace are all the places that
need to modify the tree. There shouldn't be that many of them
(basically, make-overlay, move-overlay, delete-overlay, plus text
insertion/deletion).
Then the rest can be modified little by little.
Some tricky parts:
- because of the insertion_type, two overlays may start with end1<end2
and finish with end1>end2 without any call to move-overlay.
- the overlay tree needs to be "weak" (i.e. we'll need to add special
code in the GC).
> I'm attaching the diff. It is an unholy mess of ifdefs, but the meat of
> it is in overlays.[ch] and buffer.c. It is a pretty big diff, and it's
> based on master from a few months ago, so I'm not even sure it applies,
I wouldn't worry about merging (better yet: merge from master right away
and then keep doing that on a regular basis, which should be easy since
I don't think we've touched (nor will touch) this code very much).
> Well, the Lisp-visible APIs weren't really the problem. The problem was
> more in the 'internal' handling of overlays in buffer.c and in xdisp.c,
> and also the fact that I had to reimplement a lot of the logic about how
> markers are moved when the buffer changes. Speaking of which, is the
> byte position stored in a marker of any significance in an overlay?
> Otherwise I could at least get rid of those.
AFAIK, the byte-position of markers is used, but the byte-position of
overlays isn't, so you should be able to get rid of them.
Richard said:
> Since overlays have to be discarded whenever text is copied,
> the need to go through the text properties and discard those
> that are really overlays could make things substantially slower.
My original idea was to keep overlays inside the intervals tree, but
that'd be done by adding some fields to the interval struct, so you
wouldn't need to do any extra work to "discard" the overlays when
copying an interval tree: just don't copy the overlay-related fields
while copying the interval tree.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 14:52 ` Stefan Monnier
@ 2016-09-21 15:58 ` Eli Zaretskii
2016-09-21 16:24 ` Stefan Monnier
2016-09-22 10:35 ` Joakim Jalap
1 sibling, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-21 15:58 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Wed, 21 Sep 2016 10:52:23 -0400
>
> > Speaking of which, is the byte position stored in a marker of any
> > significance in an overlay? Otherwise I could at least get rid of
> > those.
>
> AFAIK, the byte-position of markers is used, but the byte-position of
> overlays isn't, so you should be able to get rid of them.
Why bother? Using markers, you get the way overlays move when text is
inserted and deleted for free, and having to update the byte position
is easy if needed.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 17:13 ` Joakim Jalap
@ 2016-09-21 16:14 ` Eli Zaretskii
2016-09-22 10:35 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-21 16:14 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Cc: emacs-devel@gnu.org
> Date: Tue, 20 Sep 2016 19:13:38 +0200
>
> > Just by reading your description, I don't think I understand the
> > nature of your difficulties. Overlays present a relatively small
> > number of Lisp-visible APIs, so all you need is to re-implement those
> > few APIs based on the new internal representation. What exactly gives
> > you trouble with that? (I see you've implemented new APIs, but that
> > doesn't have to be part of the job, it's up to you.)
>
> Well, the Lisp-visible APIs weren't really the problem. The problem was
> more in the 'internal' handling of overlays in buffer.c and in xdisp.c,
> and also the fact that I had to reimplement a lot of the logic about how
> markers are moved when the buffer changes.
If you use markers, they move automatically, so I'm unsure what you
needed to reimplement. What am I missing?
AFAIR, xdisp.c will be perfectly happy if there are no overlays in
sight in a buffer, so just making the bunch of APIs it uses to access
overlays be no-ops should allow you to continue past the display
engine part of the puzzle. (Not sure what you meant by buffer.c,
since that is where the current overlay implementation lives.)
In any case, I know what you mean by "until everything works nothing
really works". Been there, done that. My advice is to take this
pragmatically, and basically let Emacs guide your progress.
Specifically, write whatever you think should be "enough", get it to
compile, then start Emacs under a debugger. If/when it crashes,
investigate the crash, fix it (which might require to implement
something you didn't before, or it might require deleting some code no
longer needed with the new implementation), then continue to the next
crash. Eventually you will get to a point where Emacs starts, but
maybe some parts of display don't look right; debug and fix that as
well. Finally, you get to the point where "emacs -Q" somes up and
looks OK, so you can begin implementing and testing the features in
the order you want.
> > You say that replacing it all is very hard, but I don't really
> > understand why. Please elaborate.
>
> Well, first of all I thought it would be a good strategy to keep all the
> old code so that I could compare the results at runtime, but that turned
> into a huge mess of ifdefs.
If it's hard, don't do that. There's no requirement to keep the old
code available.
> Basically my problem is that when I throw the old code out wholesale,
> suddenly that's thousands of lines I have to write which have to
> somewhat work, or I can't even get Emacs to build, let alone start up,
> so it turns into quite a big project, which I don't really see how I can
> break up into smaller parts.
See above for one suggestion, something I used successfully in my own
Emacs projects of similar magnitude.
Thanks.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 15:58 ` Eli Zaretskii
@ 2016-09-21 16:24 ` Stefan Monnier
2016-09-21 16:43 ` Eli Zaretskii
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-09-21 16:24 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
>> > Speaking of which, is the byte position stored in a marker of any
>> > significance in an overlay? Otherwise I could at least get rid of
>> > those.
>> AFAIK, the byte-position of markers is used, but the byte-position of
>> overlays isn't, so you should be able to get rid of them.
> Why bother?
AFAIK there'd be no benefit at all until/unless you add extra code to
try and use those byte-positions somewhere.
I know of two cases where we use such byte-positions, currently:
- in goto-char, but that never receives an overlay as argument.
- when converting charpos <-> bytepos (where we use the table of
markers as a kind of cache of existing translations)
The second use would probably better be served by a separate table:
- This hack of (ab)using markers can occasionally lead to bad
performance because it makes the charpos<->bytepos conversion O(N)
in the worst case where N is the number of markers which can get very
large).
- It can also lead to bad performance in the other case: lack of
markers around the "destination" makes the conversion O(N) in the
worst case where N is the size of the displacement.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 16:24 ` Stefan Monnier
@ 2016-09-21 16:43 ` Eli Zaretskii
2016-09-21 18:41 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-21 16:43 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Wed, 21 Sep 2016 12:24:30 -0400
>
> >> > Speaking of which, is the byte position stored in a marker of any
> >> > significance in an overlay? Otherwise I could at least get rid of
> >> > those.
> >> AFAIK, the byte-position of markers is used, but the byte-position of
> >> overlays isn't, so you should be able to get rid of them.
> > Why bother?
>
> AFAIK there'd be no benefit at all until/unless you add extra code to
> try and use those byte-positions somewhere.
> I know of two cases where we use such byte-positions, currently:
> - in goto-char, but that never receives an overlay as argument.
> - when converting charpos <-> bytepos (where we use the table of
> markers as a kind of cache of existing translations)
That's a larger issue about markers, AFAU, it has nothing in
particular to do with overlays.
My point was that if overlay edges are implemented as markers, their
movement with buffer changes is for free, and doesn't need to be
reimplemented.
I also envision other subtleties that rely on them being markers
(e.g., the buffer-modification hooks). I see no reason why Joakim
should add to his immediate job, which is large already, also the job
of replacing start/end markers and dealing with the fallout. That
should IMO be a separate job.
> - This hack of (ab)using markers can occasionally lead to bad
> performance because it makes the charpos<->bytepos conversion O(N)
> in the worst case where N is the number of markers which can get very
> large).
> - It can also lead to bad performance in the other case: lack of
> markers around the "destination" makes the conversion O(N) in the
> worst case where N is the size of the displacement.
Do you have numbers to back that up? IME, this is a non-issue.
in any case, I was only talking about the overlay start/end
implementation, not about the byte position of markers in general.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 16:43 ` Eli Zaretskii
@ 2016-09-21 18:41 ` Stefan Monnier
2016-09-21 19:28 ` Eli Zaretskii
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-09-21 18:41 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
> My point was that if overlay edges are implemented as markers, their
> movement with buffer changes is for free, and doesn't need to be
> reimplemented.
Keeping overlays in a tree means that the tree has to be updated when
overlays move, so "their movement with buffer changes is for free"
doesn't apply. More to the point, his code makes overlays not use
markers any more (and I agree with this choice).
> in any case, I was only talking about the overlay start/end
> implementation, not about the byte position of markers in general.
I was talking specifically about keeping byte-positions for overlays.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 18:41 ` Stefan Monnier
@ 2016-09-21 19:28 ` Eli Zaretskii
0 siblings, 0 replies; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-21 19:28 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Wed, 21 Sep 2016 14:41:19 -0400
>
> > in any case, I was only talking about the overlay start/end
> > implementation, not about the byte position of markers in general.
>
> I was talking specifically about keeping byte-positions for overlays.
Like I said, I wouldn't recommend deleting them just yet, only when
the job is done, and it is clear without doubt that the byte positions
are never used. Keeping them for now is easy on the source level, the
functions for converting between character and byte positions are
readily available, and performance is not really an important issue
for the initial implementation. OTOH, I've been bitten more then once
by some subtle corner that is not evident and not really documented,
so you don't see it until you bump into it. It is better to wait
until the job is done than risk implementing a design that is based on
incorrect assumptions. Especially for someone who does their first
job of such magnitude in Emacs.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 16:14 ` Eli Zaretskii
@ 2016-09-22 10:35 ` Joakim Jalap
2016-09-22 12:24 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-09-22 10:35 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
> If you use markers, they move automatically, so I'm unsure what you
> needed to reimplement. What am I missing?
As Stefan wrote in an earlier mail, the problem is that the tree needs
to be rebalanced when a node changes, so there will have to be code to
deal with these movements anyway. Although I guess it would be possible
to have all the markers moved the 'usual' way, and then rebalance the
tree after that.
Also, in Stefan's original suggestion (this is all his idea really) the
plan was to later replace markers by a 'degenerate overlay' of length 0,
and make use of the same tree structure. That is of course out of scope
of this, but something I had in mind nonetheless.
> AFAIR, xdisp.c will be perfectly happy if there are no overlays in
> sight in a buffer, so just making the bunch of APIs it uses to access
> overlays be no-ops should allow you to continue past the display
> engine part of the puzzle. (Not sure what you meant by buffer.c,
> since that is where the current overlay implementation lives.)
Of course! Thank you. I never thought of that.
What I meant in buffer.c are the non-Lisp-visible functions, like for
example evaporate_overlays.
> In any case, I know what you mean by "until everything works nothing
> really works". Been there, done that. My advice is to take this
> pragmatically, and basically let Emacs guide your progress.
> Specifically, write whatever you think should be "enough", get it to
> compile, then start Emacs under a debugger. If/when it crashes,
> investigate the crash, fix it (which might require to implement
> something you didn't before, or it might require deleting some code no
> longer needed with the new implementation), then continue to the next
> crash. Eventually you will get to a point where Emacs starts, but
> maybe some parts of display don't look right; debug and fix that as
> well. Finally, you get to the point where "emacs -Q" somes up and
> looks OK, so you can begin implementing and testing the features in
> the order you want.
Right. I was trying to keep all old functionality, but as you point out,
I guess nothing in Emacs really *needs* overlays to be displayed. So
maybe I can make no-ops of most of the functions which get overlays and
so on.
>> Well, first of all I thought it would be a good strategy to keep all the
>> old code so that I could compare the results at runtime, but that turned
>> into a huge mess of ifdefs.
>
> If it's hard, don't do that. There's no requirement to keep the old
> code available.
No, I'll probaly give up on that idea.
> See above for one suggestion, something I used successfully in my own
> Emacs projects of similar magnitude.
Thanks. I'll try just removing all the old code.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-21 14:52 ` Stefan Monnier
2016-09-21 15:58 ` Eli Zaretskii
@ 2016-09-22 10:35 ` Joakim Jalap
2016-09-22 12:17 ` Stefan Monnier
1 sibling, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-09-22 10:35 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
Thanks for looking at this! It is, after all, your idea :)
> Could you describe how you use this tree? An AA-tree is indexed by
> a single "number", whereas overlays have two independent "numbers".
> So how to use this AA-tree to implement an *interval* tree?
See below.
> This should be documented in the code. E.g. the "struct Lisp_Overlay"
> should define very clearly the meaning of char_start, char_end, left,
> and right (i.e. which overlays go to the left, and which go to the
> right).
>
> While looking for an answer in the text I found:
>
> /* This function determines where overlays are inserted in the tree.
> FIXME: I didn't think too hard about this...
> */
>
> which makes me suspect your design might not be quite right.
Well, I didn't think *too* hard about it. I didn't really think about
what to do when the intervals of two overlays are the same. Does it even
matter? I have a feeling that if I want to insert an overlay which
starts at the same place as another, it could just be inserted to the
left of the latter. Is that correct?
> Have you read https://en.wikipedia.org/wiki/Interval_tree ?
Yes. Well, I tried to anyway.
> [ BTW, our convention is to put the "*/" at the end of the last line
> rather than alone on the next line. ]
Got it. I'll fix that.
> This said, reading overlay_tree_insert_internal, I have the impression
> that you're implementing what wikipedia describes as an "Augmented tree"
> where the basic tree is your AA-tree, indexed by the left position of
> the overlays, with the `max` field being the "augmented" data, which
> sounds just fine.
> Is that right?
That is exactly right.
> The only places you absolutely need to replace are all the places that
> need to modify the tree. There shouldn't be that many of them
> (basically, make-overlay, move-overlay, delete-overlay, plus text
> insertion/deletion).
> Then the rest can be modified little by little.
I think I ran into some other subtle things. For example an overlay can
be in "no buffer" if both it's markers were detached from their buffer,
I think. So in the case of the overlay tree, I need to detect this and
remove the overlay from the buffers tree.
> Some tricky parts:
> - because of the insertion_type, two overlays may start with end1<end2
> and finish with end1>end2 without any call to move-overlay.
Hm, ok. I will have to look into this further.
> - the overlay tree needs to be "weak" (i.e. we'll need to add special
> code in the GC).
I don't really understand what this means. Could you please elaborate? I
was hoping it would work with the current marking and sweeping.
> I wouldn't worry about merging (better yet: merge from master right away
> and then keep doing that on a regular basis, which should be easy since
> I don't think we've touched (nor will touch) this code very much).
I tried to do that yesterday. There were some conflicts in insdel.c
(which I think I fixed) but now I can't commit, because 'git commit'
complains about trailing whitespace in some regex test files. How do I
get around this?
> AFAIK, the byte-position of markers is used, but the byte-position of
> overlays isn't, so you should be able to get rid of them.
That's great!
Thanks.
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-22 10:35 ` Joakim Jalap
@ 2016-09-22 12:17 ` Stefan Monnier
2016-09-22 20:11 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-09-22 12:17 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
>> which makes me suspect your design might not be quite right.
> Well, I didn't think *too* hard about it. I didn't really think about
> what to do when the intervals of two overlays are the same. Does it even
> matter?
Not much, no. Do note that in compare_overlays, we do need a total ordering
(this is used for sort_overlays). Your sorting and that of
compare_overlays can't be identical (compare_overlays has to obey the
`priority` property, whereas yours shouldn't pay attention to it), but
you can still use the same idea: i.e. when start and end are equal, just
use the overlays's memory addresses to decide which comes first.
>> This said, reading overlay_tree_insert_internal, I have the impression
>> that you're implementing what wikipedia describes as an "Augmented tree"
>> where the basic tree is your AA-tree, indexed by the left position of
>> the overlays, with the `max` field being the "augmented" data, which
>> sounds just fine.
>> Is that right?
> That is exactly right.
Great.
>> The only places you absolutely need to replace are all the places that
>> need to modify the tree. There shouldn't be that many of them
>> (basically, make-overlay, move-overlay, delete-overlay, plus text
>> insertion/deletion).
>> Then the rest can be modified little by little.
> I think I ran into some other subtle things. For example an overlay can
> be in "no buffer" if both it's markers were detached from their buffer,
> I think.
The user doesn't have direct access to the markers, so IIUC this
situation happens through delete-overlay or move-overlay.
> So in the case of the overlay tree, I need to detect this and
> remove the overlay from the buffers tree.
Similarly, move-overlay can necessitate moving the overlay from one tree
to another.
>> Some tricky parts:
>> - because of the insertion_type, two overlays may start with end1<end2
>> and finish with end1>end2 without any call to move-overlay.
> Hm, ok. I will have to look into this further.
I think a more important aspect is that insertion/deletion of text has
to update all char-positions of overlays after the point of
insertion/deletion. I.e. it's an O(n) operation. In the intervals tree
used for text-properties we avoid this by keeping track of distances
rather than positions. and then positions get (re)computed when needed.
>> - the overlay tree needs to be "weak" (i.e. we'll need to add special
>> code in the GC).
> I don't really understand what this means. Could you please elaborate?
> I was hoping it would work with the current marking and sweeping.
Hmm... forget it, I was confused.
>> I wouldn't worry about merging (better yet: merge from master right away
>> and then keep doing that on a regular basis, which should be easy since
>> I don't think we've touched (nor will touch) this code very much).
> I tried to do that yesterday. There were some conflicts in insdel.c
> (which I think I fixed) but now I can't commit, because 'git commit'
> complains about trailing whitespace in some regex test files. How do I
> get around this?
Just remove the trailing whitespace.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-22 10:35 ` Joakim Jalap
@ 2016-09-22 12:24 ` Stefan Monnier
0 siblings, 0 replies; 110+ messages in thread
From: Stefan Monnier @ 2016-09-22 12:24 UTC (permalink / raw)
To: emacs-devel
> Also, in Stefan's original suggestion (this is all his idea really) the
> plan was to later replace markers by a 'degenerate overlay' of length 0,
> and make use of the same tree structure. That is of course out of scope
> of this, but something I had in mind nonetheless.
FWIW, I'm not sure if it would be a good idea or not anyway, so yes,
let's not worry about: it it's completely out of scope.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-22 12:17 ` Stefan Monnier
@ 2016-09-22 20:11 ` Joakim Jalap
2016-09-23 1:29 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-09-22 20:11 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> which makes me suspect your design might not be quite right.
>> Well, I didn't think *too* hard about it. I didn't really think about
>> what to do when the intervals of two overlays are the same. Does it even
>> matter?
>
> Not much, no. Do note that in compare_overlays, we do need a total ordering
> (this is used for sort_overlays). Your sorting and that of
> compare_overlays can't be identical (compare_overlays has to obey the
> `priority` property, whereas yours shouldn't pay attention to it), but
> you can still use the same idea: i.e. when start and end are equal, just
> use the overlays's memory addresses to decide which comes first.
Do you mean when a->char_start == b->char_start && a->char_end ==
b->char_end?
Does it even matter what char_end is? I have a feeling it's ok to just
return true if a->char_start == b->char_end.
>>> Some tricky parts:
>>> - because of the insertion_type, two overlays may start with end1<end2
>>> and finish with end1>end2 without any call to move-overlay.
>> Hm, ok. I will have to look into this further.
Actually, this sounds like it could be quite complicated... I'm not sure
how to handle that in the tree.
> I think a more important aspect is that insertion/deletion of text has
> to update all char-positions of overlays after the point of
> insertion/deletion. I.e. it's an O(n) operation. In the intervals tree
> used for text-properties we avoid this by keeping track of distances
> rather than positions. and then positions get (re)computed when needed.
Hm, I don't really understand this. Do you mean how LENGTH(i) is
computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)? Hm, how
could I do that in the AA-tree? Store the position in the root and then
an offset from the parent in every child node?
But doing it like I do it now (updating all the char-positions after the
modification) shouldn't be slower than updating the positions of all
markers, right?
>>> I wouldn't worry about merging (better yet: merge from master right away
>>> and then keep doing that on a regular basis, which should be easy since
>>> I don't think we've touched (nor will touch) this code very much).
>> I tried to do that yesterday. There were some conflicts in insdel.c
>> (which I think I fixed) but now I can't commit, because 'git commit'
>> complains about trailing whitespace in some regex test files. How do I
>> get around this?
>
> Just remove the trailing whitespace.
I just commited with --no-verify instead :)
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-22 20:11 ` Joakim Jalap
@ 2016-09-23 1:29 ` Stefan Monnier
2016-09-27 6:26 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-09-23 1:29 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
>> Not much, no. Do note that in compare_overlays, we do need a total ordering
>> (this is used for sort_overlays). Your sorting and that of
>> compare_overlays can't be identical (compare_overlays has to obey the
>> `priority` property, whereas yours shouldn't pay attention to it), but
>> you can still use the same idea: i.e. when start and end are equal, just
>> use the overlays's memory addresses to decide which comes first.
> Do you mean when a->char_start == b->char_start && a->char_end ==
> b-> char_end?
Yes.
> Does it even matter what char_end is? I have a feeling it's ok to just
> return true if a->char_start == b->char_end.
Things are easier if you make the comparison a total order, so o1==o2
only if o1 and o2 are actually one and the same overlay.
>>>> Some tricky parts:
>>>> - because of the insertion_type, two overlays may start with end1<end2
>>>> and finish with end1>end2 without any call to move-overlay.
>>> Hm, ok. I will have to look into this further.
> Actually, this sounds like it could be quite complicated... I'm not sure
> how to handle that in the tree.
After an insertion/deletion, you'll need to update the char positions.
While doing it should be fairly easy to check that the adjustments don't
break the tree's consistency. When an inconsistency is detected, you
can either try to adjust things locally or just remove and re-insert the
overlay.
> Hm, I don't really understand this. Do you mean how LENGTH(i) is
> computed from TOTAL_LENGTH(i->left) and TOTAL_LENGTH(i->right)?
Not exactly, tho it's related. I was referring to the `position` field
of `struct interval`.
> Hm, how could I do that in the AA-tree?
Haven't thought about it yet.
> Store the position in the root and then an offset from the parent in
> every child node?
Something like that, I guess, yes.
> But doing it like I do it now (updating all the char-positions after the
> modification) shouldn't be slower than updating the positions of all
> markers, right?
Indeed, it's no worse than what we have, but it reduces the algorithmic
benefit of the change. IOW we can keep this for later.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-23 1:29 ` Stefan Monnier
@ 2016-09-27 6:26 ` Joakim Jalap
2016-09-27 11:50 ` Stefan Monnier
2016-09-27 14:38 ` Eli Zaretskii
0 siblings, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-09-27 6:26 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Store the position in the root and then an offset from the parent in
>> every child node?
>
> Something like that, I guess, yes.
That actually sounds quite neat.
>> But doing it like I do it now (updating all the char-positions after the
>> modification) shouldn't be slower than updating the positions of all
>> markers, right?
>
> Indeed, it's no worse than what we have, but it reduces the algorithmic
> benefit of the change. IOW we can keep this for later.
For later it is :)
I followed Eli's advice and tried to more or less rip out all the code
which deals with overlays in xdisp.c etc, so that all functions that try
to gather overlays always act as if none were found.
I managed to get it to compile at last, but now I'm hitting another
issue. temacs segfaults in a gc while loading simple.el. It seems
somehow some memory doesn't look like it should, because the stack trace
from the gc is about 1100 frames! Mostly mark_object, with some
mark_vectorlike here and there. How do I debug something like that? I
tried putting a breakpoint in mark_buffer, but that function is called
like a million times, and from what I can see at least the first hundred
or so don't cause a crash.
When it crashes, it always seems to be on the 10th Lisp_Object in struct
buffer, which by my calculations is major_mode_. From there it seems to
go haywire and into a thousand or more calls to mainly_mark object.
I will try to investigate further, but any pointers (pun intended) would
be very much appreciated.
-- Jocke
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-27 6:26 ` Joakim Jalap
@ 2016-09-27 11:50 ` Stefan Monnier
2016-09-27 14:38 ` Eli Zaretskii
1 sibling, 0 replies; 110+ messages in thread
From: Stefan Monnier @ 2016-09-27 11:50 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
> I managed to get it to compile at last, but now I'm hitting another
> issue. temacs segfaults in a gc while loading simple.el. It seems
> somehow some memory doesn't look like it should, because the stack trace
> from the gc is about 1100 frames! Mostly mark_object, with some
> mark_vectorlike here and there. How do I debug something like that?
> I tried putting a breakpoint in mark_buffer, but that function is called
> like a million times, and from what I can see at least the first hundred
> or so don't cause a crash.
You might like to take a look at etc/DEBUG, although in your case the
most likely problem is that you haven't updated the marking code
properly so that it knows about your new objects.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-27 6:26 ` Joakim Jalap
2016-09-27 11:50 ` Stefan Monnier
@ 2016-09-27 14:38 ` Eli Zaretskii
2016-09-27 16:07 ` Joakim Jalap
1 sibling, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-09-27 14:38 UTC (permalink / raw)
To: Joakim Jalap; +Cc: monnier, emacs-devel
> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Date: Tue, 27 Sep 2016 08:26:41 +0200
> Cc: emacs-devel@gnu.org
>
> I managed to get it to compile at last, but now I'm hitting another
> issue. temacs segfaults in a gc while loading simple.el. It seems
> somehow some memory doesn't look like it should, because the stack trace
> from the gc is about 1100 frames! Mostly mark_object, with some
> mark_vectorlike here and there. How do I debug something like that? I
> tried putting a breakpoint in mark_buffer, but that function is called
> like a million times, and from what I can see at least the first hundred
> or so don't cause a crash.
>
> When it crashes, it always seems to be on the 10th Lisp_Object in struct
> buffer, which by my calculations is major_mode_. From there it seems to
> go haywire and into a thousand or more calls to mainly_mark object.
Seeing 1100 frames in GC is nothing unusual. In fact, I've seen 30K
frames in a perfectly healthy GC. Garbage collection is deeply
recursive, so just that number of frames doesn't mean GC went haywire.
I agree with Stefan: most likely you didn't update the GC code to deal
with your implementation of overlays.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-27 14:38 ` Eli Zaretskii
@ 2016-09-27 16:07 ` Joakim Jalap
2016-11-21 17:32 ` Clément Pit--Claudel
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-09-27 16:07 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: monnier, emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
> Seeing 1100 frames in GC is nothing unusual. In fact, I've seen 30K
> frames in a perfectly healthy GC. Garbage collection is deeply
> recursive, so just that number of frames doesn't mean GC went haywire.
Good to know :)
> I agree with Stefan: most likely you didn't update the GC code to deal
> with your implementation of overlays.
Yes, of course you are right. I had simply forgotten to set the
gcmarkbit!
But now it works, the build finished and emacs -Q starts and runs just
fine :)
Thanks
-- Jocke
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-27 16:07 ` Joakim Jalap
@ 2016-11-21 17:32 ` Clément Pit--Claudel
2016-11-22 8:09 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Clément Pit--Claudel @ 2016-11-21 17:32 UTC (permalink / raw)
To: emacs-devel
[-- Attachment #1.1: Type: text/plain, Size: 866 bytes --]
Hey Joakim,
I hope you'll get around to finish this implementation, and I hope it'll get merged :) Many packages could benefit immensely from an efficient overlay implementation.
Cheers,
Clément.
On 2016-09-27 12:07, Joakim Jalap wrote:
> Eli Zaretskii <eliz@gnu.org> writes:
>
>> Seeing 1100 frames in GC is nothing unusual. In fact, I've seen 30K
>> frames in a perfectly healthy GC. Garbage collection is deeply
>> recursive, so just that number of frames doesn't mean GC went haywire.
>
> Good to know :)
>
>> I agree with Stefan: most likely you didn't update the GC code to deal
>> with your implementation of overlays.
>
> Yes, of course you are right. I had simply forgotten to set the
> gcmarkbit!
>
> But now it works, the build finished and emacs -Q starts and runs just
> fine :)
>
> Thanks
>
> -- Jocke
>
>
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-21 17:32 ` Clément Pit--Claudel
@ 2016-11-22 8:09 ` Joakim Jalap
2016-11-22 13:44 ` Stefan Monnier
2016-11-22 13:44 ` Clément Pit--Claudel
0 siblings, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-11-22 8:09 UTC (permalink / raw)
To: Clément Pit--Claudel; +Cc: emacs-devel
Clément Pit--Claudel <clement.pit@gmail.com> writes:
> Hey Joakim,
Hello!
> I hope you'll get around to finish this implementation, and I hope
> it'll get merged :) Many packages could benefit immensely from an
> efficient overlay implementation.
Oh, I'm chugging along, actually, albeit very slowly... I've been
working out bugs here and there, and now it's at a state where I think
it kinda works. Which means I can open a magit buffer and expand and
collapse diffs and so on and it looks mostly right.
I still have a few functions to implement, like concatenating overlay
strings and some other things. Right now I'm pondering if the which
overlays should be included when we run the overlay-modification
hooks...
Then there's a lot of cleanup of the code to be done, and changing stuff
to use SAFE_ALLOCA and things like that.
But I hope that in a few weeks or so I can publish it somewhere so you
can try it out :)
> Cheers,
> Clément.
Thanks for the encouragement! :)
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 8:09 ` Joakim Jalap
@ 2016-11-22 13:44 ` Stefan Monnier
2016-11-23 6:58 ` Joakim Jalap
2016-11-22 13:44 ` Clément Pit--Claudel
1 sibling, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-11-22 13:44 UTC (permalink / raw)
To: emacs-devel
> But I hope that in a few weeks or so I can publish it somewhere so you
> can try it out :)
I'd encourage you to put your branch in Emacs's repository even if it's
not "ready".
If the commits are "haphazard" and without carefully written
commit-messages, then just use a branch whose name starts with
"scratch/".
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 8:09 ` Joakim Jalap
2016-11-22 13:44 ` Stefan Monnier
@ 2016-11-22 13:44 ` Clément Pit--Claudel
2016-11-22 13:55 ` Evgeny Roubinchtein
2016-11-23 7:13 ` Joakim Jalap
1 sibling, 2 replies; 110+ messages in thread
From: Clément Pit--Claudel @ 2016-11-22 13:44 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
[-- Attachment #1.1: Type: text/plain, Size: 343 bytes --]
On 2016-11-22 03:09, Joakim Jalap wrote:
> But I hope that in a few weeks or so I can publish it somewhere so you
> can try it out :)
Excellent! I'll be very happy to try it out :) (two packages that I use heavily, Flycheck and Proof General, suffer from overlay-related performance issues, so I'm quite excited)
Cheers,
Clément.
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 13:44 ` Clément Pit--Claudel
@ 2016-11-22 13:55 ` Evgeny Roubinchtein
2016-11-23 7:16 ` Joakim Jalap
2016-11-23 7:13 ` Joakim Jalap
1 sibling, 1 reply; 110+ messages in thread
From: Evgeny Roubinchtein @ 2016-11-22 13:55 UTC (permalink / raw)
To: Clément Pit--Claudel; +Cc: Joakim Jalap, Emacs Development
[-- Attachment #1: Type: text/plain, Size: 656 bytes --]
This is really exciting work.
I realize this is a politically-charged issue, but would it be possible to
reuse some of the design (if not the code) from XEmacs extents?
--
Best,
Zhenya
On Tue, Nov 22, 2016 at 8:44 AM, Clément Pit--Claudel <clement.pit@gmail.com
> wrote:
> On 2016-11-22 03:09, Joakim Jalap wrote:
> > But I hope that in a few weeks or so I can publish it somewhere so you
> > can try it out :)
>
> Excellent! I'll be very happy to try it out :) (two packages that I use
> heavily, Flycheck and Proof General, suffer from overlay-related
> performance issues, so I'm quite excited)
>
> Cheers,
> Clément.
>
>
[-- Attachment #2: Type: text/html, Size: 1056 bytes --]
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 13:44 ` Stefan Monnier
@ 2016-11-23 6:58 ` Joakim Jalap
0 siblings, 0 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-11-23 6:58 UTC (permalink / raw)
To: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
> I'd encourage you to put your branch in Emacs's repository even if it's
> not "ready".
I don't have commit rights, so I don't think I can do that.
> If the commits are "haphazard" and without carefully written
> commit-messages, then just use a branch whose name starts with
> "scratch/".
Believe me, "haphazard" doesn't even begin to describe it ;)
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 13:44 ` Clément Pit--Claudel
2016-11-22 13:55 ` Evgeny Roubinchtein
@ 2016-11-23 7:13 ` Joakim Jalap
1 sibling, 0 replies; 110+ messages in thread
From: Joakim Jalap @ 2016-11-23 7:13 UTC (permalink / raw)
To: emacs-devel
Clément Pit--Claudel <clement.pit@gmail.com> writes:
> On 2016-11-22 03:09, Joakim Jalap wrote:
>> But I hope that in a few weeks or so I can publish it somewhere so you
>> can try it out :)
>
> Excellent! I'll be very happy to try it out :) (two packages that I
> use heavily, Flycheck and Proof General, suffer from overlay-related
> performance issues, so I'm quite excited)
Don't get your hopes up too much ;) My first goal is to get it to work
correctly. If I can do that I will lock at performance enhancements
next, like using stack allocation and Stefan's suggestion about storing
offsets instead of absolute positions (or somethiing like that).
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-22 13:55 ` Evgeny Roubinchtein
@ 2016-11-23 7:16 ` Joakim Jalap
2016-11-23 15:42 ` Eli Zaretskii
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2016-11-23 7:16 UTC (permalink / raw)
To: emacs-devel
Evgeny Roubinchtein <zhenya1007@gmail.com> writes:
> This is really exciting work.
>
> I realize this is a politically-charged issue, but would it be
> possible to reuse some of the design (if not the code) from XEmacs
> extents?
It is not politically charged for me :) I have never used XEmacs, but I
will have a look at the 'extents' feature. However, what I'm trying to
do is just to change the underlying implementation, not change how
overlays behave.
But I will have a look at extents, thanks for the tip!
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-23 7:16 ` Joakim Jalap
@ 2016-11-23 15:42 ` Eli Zaretskii
2016-11-23 16:06 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2016-11-23 15:42 UTC (permalink / raw)
To: Joakim Jalap, Evgeny Roubinchtein; +Cc: emacs-devel
> From: Joakim Jalap <joakim.jalap@fastmail.com>
> Date: Wed, 23 Nov 2016 08:16:05 +0100
>
> Evgeny Roubinchtein <zhenya1007@gmail.com> writes:
>
> > This is really exciting work.
> >
> > I realize this is a politically-charged issue, but would it be
> > possible to reuse some of the design (if not the code) from XEmacs
> > extents?
>
> It is not politically charged for me :) I have never used XEmacs, but I
> will have a look at the 'extents' feature. However, what I'm trying to
> do is just to change the underlying implementation, not change how
> overlays behave.
>
> But I will have a look at extents, thanks for the tip!
Beware: we cannot use their code due to copyright issues, so it's
probably not wise to look at the code there. Reading extents.texi in
the lispref/ directory is what I'd recommend.
I actually don't understand the request: what is meant by "design"
here? If there are some features we lack in the overlays, then
corresponding feature requests (better yet, patches) would be
appreciated. After reading extents.texi, I don't see any significant
features missing, except the ability to copy overlays with the text
(which AFAIR XEmacs implements somewhat inconsistently, as only some
of the primitives that process text support that). Is there something
else?
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-23 15:42 ` Eli Zaretskii
@ 2016-11-23 16:06 ` Stefan Monnier
2016-11-24 18:33 ` Evgeny Roubinchtein
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2016-11-23 16:06 UTC (permalink / raw)
To: emacs-devel
> Beware: we cannot use their code due to copyright issues, so it's
> probably not wise to look at the code there.
IIRC the majority of XEmacs's code can be integrated into Emacs
with no issue w.r.t copyright. But yes, it requires scrutiny.
> I actually don't understand the request: what is meant by "design"
> here? If there are some features we lack in the overlays, then
> corresponding feature requests (better yet, patches) would be
> appreciated. After reading extents.texi, I don't see any significant
> features missing, except the ability to copy overlays with the text
> (which AFAIR XEmacs implements somewhat inconsistently, as only some
> of the primitives that process text support that). Is there something
> else?
I think the reference wasn't to the exposed API but to the underlying
implementation technique, but XEmacs uses doubly-linked lists to store
their extents, so it's no better than what we have.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-11-23 16:06 ` Stefan Monnier
@ 2016-11-24 18:33 ` Evgeny Roubinchtein
0 siblings, 0 replies; 110+ messages in thread
From: Evgeny Roubinchtein @ 2016-11-24 18:33 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Emacs Development
[-- Attachment #1: Type: text/plain, Size: 462 bytes --]
On Wed, Nov 23, 2016 at 8:06 AM, Stefan Monnier <monnier@iro.umontreal.ca>
wrote:
>
> I think the reference wasn't to the exposed API but to the underlying
> implementation technique, but XEmacs uses doubly-linked lists to store
> their extents, so it's no better than what we have.
>
Yes. I was wondering if they were using a clever data structure and/or
search technique, but it sounds like that isn't the case.
I apologize for the noise.
--
Best,
Zhenya
[-- Attachment #2: Type: text/html, Size: 983 bytes --]
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
` (3 preceding siblings ...)
2016-09-21 14:52 ` Stefan Monnier
@ 2017-02-03 8:49 ` Andreas Politz
2017-02-03 9:13 ` Eli Zaretskii
` (2 more replies)
4 siblings, 3 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 8:49 UTC (permalink / raw)
To: emacs-devel
Hi, I'm interested in this problem as well.
I want to clarify something:
Overlays have begin B and end E positions each with a flag (front-advance
resp. rear-advance). These positions may change in one of 3 ways:
1. move-overlay is called
2. Text of length L is inserted at position P.
Here the flags decide whether begin B resp. end E will move or not
in the literal border-cases P = B resp. P = E .
3. Text of length L is deleted beginning at position P.
Is this the correct model ? Someone mentioned in a different thread,
that occasionally we may have B > E. How does this happen ?
---
I think if a tree is sorted by begin only and the front-advance of
every node is either true or false, the tree can't possibly become
disordered by insertion/deletion operations. Further the disorder
exists at most for nodes having the same begin but different
front-advances after an insert at begin was performed.
This suggests using two trees or at least limits the amount of nodes
having to be reinserted after a change.
---
Anyway, my attempt is to use the RB-tree from alloc.c and add some
node-attributes:
1. max_end :: Holds the maximum E value of this node's sub-tree and
bounds the complexity of queries in terms of their result, i.e. number
of intervals. (The so called ,,Augmented Tree'' approach to Interval
Trees (which is actually just an example for how to augment a tree in
the book).)
2. offset :: The amount of shift of this node's sub-tree relative to
its parent and applying to all position values (begin,end,max_end).
This should limit the time it takes to modify the tree after an
insertion/deletion in terms of intersecting intervals.
3. modified_tick :: Essentially just a flag, indicating that all
parent offsets have been applied to this node. This would allow for
constant time access on B/E for repeated accesses.
I'm essentially building an overlay model and if it works, will try to
plug it into the Editor.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 8:49 ` Andreas Politz
@ 2017-02-03 9:13 ` Eli Zaretskii
2017-02-03 10:24 ` Andreas Politz
2017-02-03 11:33 ` Joakim Jalap
2017-02-03 13:55 ` Stefan Monnier
2 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-03 9:13 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Date: Fri, 03 Feb 2017 09:49:20 +0100
>
> Hi, I'm interested in this problem as well.
Thanks for working on this.
> Overlays have begin B and end E positions each with a flag (front-advance
> resp. rear-advance). These positions may change in one of 3 ways:
>
> 1. move-overlay is called
> 2. Text of length L is inserted at position P.
> Here the flags decide whether begin B resp. end E will move or not
> in the literal border-cases P = B resp. P = E .
> 3. Text of length L is deleted beginning at position P.
>
> Is this the correct model ?
Not sure what you are asking here. You actually described the model
of modifying buffer text, which is only tangentially related to
overlays.
> Someone mentioned in a different thread,
> that occasionally we may have B > E. How does this happen ?
I don't think it can happen, except during internal operations of
inserting and deleting buffer text. The functions that handle these
changes in buffer text fix up B and E such that B >= E before they
return to the main loop, so Lisp will never see that.
But note that you could have B == E (so-called "empty" or
"zero-length" overlays). In this case, front-advance and rear-advance
are applied to the same buffer position.
There are also overlays that evaporate.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 9:13 ` Eli Zaretskii
@ 2017-02-03 10:24 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 10:24 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
>> From: Andreas Politz <politza@hochschule-trier.de>
>> Overlay[s] [...] positions may change in one of 3 ways: [...]
>> Is this the correct model ?
>
> Not sure what you are asking here. You actually described the model
> of modifying buffer text, which is only tangentially related to
> overlays.
Confirmation. Too many times I thought I had a grasp on something, exept
I didn't. I think its an important issue, because it influences the
performance penalty overlays have on editing text. (Note: I don't plan
to keep the markers.)
>> Someone mentioned in a different thread,
>> that occasionally we may have B > E. How does this happen ?
>
> I don't think it can happen, except during internal operations [...]
I see.
> There are also overlays that evaporate.
Now thats what I would call tangential. (Just teasing.)
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 8:49 ` Andreas Politz
2017-02-03 9:13 ` Eli Zaretskii
@ 2017-02-03 11:33 ` Joakim Jalap
2017-02-03 12:44 ` Andreas Politz
2017-02-03 13:55 ` Stefan Monnier
2 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-03 11:33 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> Hi, I'm interested in this problem as well.
Great!
I thought I might chime in since I've been bashing my head againt this
for a while now :)
> I want to clarify something:
>
> Overlays have begin B and end E positions each with a flag (front-advance
> resp. rear-advance). These positions may change in one of 3 ways:
>
> 1. move-overlay is called
> 2. Text of length L is inserted at position P.
> Here the flags decide whether begin B resp. end E will move or not
> in the literal border-cases P = B resp. P = E .
> 3. Text of length L is deleted beginning at position P.
There is also the case of a replace, conceptually I guess it's similar
to a delete or an insert, but in the code it is handled separately.
Interestingly, in the case of a replace, we don't look at the insertion type.
> Is this the correct model ? Someone mentioned in a different thread,
> that occasionally we may have B > E. How does this happen ?
I think it happens in case 2 above, when B = E = P, and we have
front-advance = t and read-advance = nil. Then B will move but E will
not, so we end up with a negative size overlay. See also the comments at
adjust_markers_for_insert in insdel.c and fix_start_end_in_overlays in
buffer.c.
> ---
>
> I think if a tree is sorted by begin only and the front-advance of
> every node is either true or false, the tree can't possibly become
> disordered by insertion/deletion operations. Further the disorder
> exists at most for nodes having the same begin but different
> front-advances after an insert at begin was performed.
But if the tree is sorted by begin only we can have multiple overlays in
the same position, how does that work? A linked list of all overlays
starting at that position? I toyed with the idea, but I haven't actually
tried it.
For reference, the last case I got stuck on was byte compiling
lisp/semantic/cpp.el, where there are a bunch overlays (26 I believe) at
different positions, but then almost all the buffer text is deleted so
that every overlay ends up being from 6 to 6!
> This suggests using two trees or at least limits the amount of nodes
> having to be reinserted after a change.
Hm I don't understand this. How would we use two trees?
>
> Anyway, my attempt is to use the RB-tree from alloc.c and add some
> node-attributes:
>
> 1. max_end :: Holds the maximum E value of this node's sub-tree and
> bounds the complexity of queries in terms of their result, i.e. number
> of intervals. (The so called ,,Augmented Tree'' approach to Interval
> Trees (which is actually just an example for how to augment a tree in
> the book).)
>
> 2. offset :: The amount of shift of this node's sub-tree relative to
> its parent and applying to all position values (begin,end,max_end).
> This should limit the time it takes to modify the tree after an
> insertion/deletion in terms of intersecting intervals.
I was going to do this too (but left that for later as I have bigger
problems right now :)). The problem here is that you have to take the
insertion_type into account, so an overlay may or may not change as the
result of an insertion. Actually maybe that isn't a problem since it
only affects those overlays with an endpoint exactly at the point of
insertion... This whole thing makes me dizzy...
> 3. modified_tick :: Essentially just a flag, indicating that all
> parent offsets have been applied to this node. This would allow for
> constant time access on B/E for repeated accesses.
>
> I'm essentially building an overlay model and if it works, will try to
> plug it into the Editor.
Sounds like a good idea. Let's hope you have better luck (or skill) than
me :)
> -ap
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 11:33 ` Joakim Jalap
@ 2017-02-03 12:44 ` Andreas Politz
2017-02-03 14:11 ` Joakim Jalap
2017-02-04 21:22 ` Stefan Monnier
0 siblings, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 12:44 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> I thought I might chime in since I've been bashing my head againt this
> for a while now :)
Much appreciated.
> There is also the case of a replace, [...]
>
>> [...] occasionally we may have B > E. How does this happen ?
>
> I think it happens in case 2 above [...] See also the comments at
> adjust_markers_for_insert in [...]
That's useful information.
>> I think if a tree is sorted by begin only [...] the tree can't possibly become
>> disordered [...]
>
> But if the tree is sorted by begin only we can have multiple overlays in
> the same position, how does that work? [...]
Why should that be a problem ? A search-tree may contain some key
multiple times. The question is whether this is useful. I don't think
it is in this case, because including end in the comparison does not
help with finding all overlays intersecting some position or interval
(i.e. it does not allow pruning some sub-trees).
It would be useful, e.g. if we were going to search for an overlay
starting at B1 and ending at E1, but I don't see were we needed this.
>
> [...] but then almost all the buffer text is deleted
> so that every overlay ends up being from 6 to 6!
No problem. Simply write a NEWS entry and declare it a new feature.
>> This suggests using two trees [...]
>
> Hm I don't understand this. How would we use two trees?
If I'm right, we *could* use one tree for front-advance overlays and one
for non-front-advance ones, such that these tree won't ever become
unordered by insertion/deletion of text.
> [...] it only affects those overlays with an endpoint exactly at the
> point of insertion... [...]
Whether it'll mess with the order depends on the comparison function ;-) .
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 8:49 ` Andreas Politz
2017-02-03 9:13 ` Eli Zaretskii
2017-02-03 11:33 ` Joakim Jalap
@ 2017-02-03 13:55 ` Stefan Monnier
2017-02-03 15:14 ` Andreas Politz
2 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-03 13:55 UTC (permalink / raw)
To: emacs-devel
> Anyway, my attempt is to use the RB-tree from alloc.c and add some
> node-attributes:
> 1. max_end :: Holds the maximum E value of this node's sub-tree and
> bounds the complexity of queries in terms of their result, i.e. number
> of intervals. (The so called ,,Augmented Tree'' approach to Interval
> Trees (which is actually just an example for how to augment a tree in
> the book).)
Sounds good.
> 2. offset :: The amount of shift of this node's sub-tree relative to
> its parent and applying to all position values (begin,end,max_end).
> This should limit the time it takes to modify the tree after an
> insertion/deletion in terms of intersecting intervals.
Sounds good.
> 3. modified_tick :: Essentially just a flag, indicating that all
> parent offsets have been applied to this node. This would allow for
> constant time access on B/E for repeated accesses.
But that can't be a boolean, right (otherwise how do you plan to set it
to true on all overlays after the insertion point, without paying an
O(n) cost)? So, by the "tick" name, I assume you keep a kind of MODIFF
counter at the root of the tree which is incremented every time an
insertion/deletion is performed, and you keep a copy of that MODIFF
value in the nodes, to remember the last time the start/end value
were recomputed, so the "flag" is really (modified_tick ==
root->modified_tick).
If so, this sounds good as well.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 12:44 ` Andreas Politz
@ 2017-02-03 14:11 ` Joakim Jalap
2017-02-03 15:02 ` Andreas Politz
2017-02-04 21:22 ` Stefan Monnier
1 sibling, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-03 14:11 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
>
>>> I think if a tree is sorted by begin only [...] the tree can't possibly become
>>> disordered [...]
>>
>> But if the tree is sorted by begin only we can have multiple overlays in
>> the same position, how does that work? [...]
>
> Why should that be a problem ? A search-tree may contain some key
> multiple times. The question is whether this is useful. I don't think
> it is in this case, because including end in the comparison does not
> help with finding all overlays intersecting some position or interval
> (i.e. it does not allow pruning some sub-trees).
Hm, that is true... I think I actually started like that, but then got
stuck in the mindset of having a total ordering. So, will there be a
linked list in each node for the overlays, or how will it work?
> It would be useful, e.g. if we were going to search for an overlay
> starting at B1 and ending at E1, but I don't see were we needed this.
I can confirm that we never need it :)
>> Hm I don't understand this. How would we use two trees?
>
> If I'm right, we *could* use one tree for front-advance overlays and one
> for non-front-advance ones, such that these tree won't ever become
> unordered by insertion/deletion of text.
Sounds like a good idea.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 14:11 ` Joakim Jalap
@ 2017-02-03 15:02 ` Andreas Politz
2017-02-03 15:23 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 15:02 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Hm, that is true... I think I actually started like that, but then got
> stuck in the mindset of having a total ordering.
No you're right, the comparison function needs to implement a total
ordering, but this just means, simply put, that any pair of nodes x, y
needs to be comparable, i.e. x <= y OR y <= x . But this does not
exclude the case where both these statements are true, i.e. x = y.
> So, will there be a linked list in each node for the overlays, or how
> will it work?
Well, imagine your AA-Tree, with <= as relation and where you keep
inserting 1s and nothing else. How will it look ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 13:55 ` Stefan Monnier
@ 2017-02-03 15:14 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 15:14 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> 3. modified_tick :: Essentially just a flag [...]
> But that can't be a boolean, [...]
Yes, yes, the comparison with tree.tick constitutes the flag.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 15:02 ` Andreas Politz
@ 2017-02-03 15:23 ` Joakim Jalap
2017-02-03 15:54 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-03 15:23 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> Joakim Jalap <joakim.jalap@fastmail.com> writes:
>
>> Hm, that is true... I think I actually started like that, but then got
>> stuck in the mindset of having a total ordering.
>
> No you're right, the comparison function needs to implement a total
> ordering, but this just means, simply put, that any pair of nodes x, y
> needs to be comparable, i.e. x <= y OR y <= x . But this does not
> exclude the case where both these statements are true, i.e. x = y.
Hm, OK. I interpreted total ordering as always being able to sort the
nodes unambiguously.
>> So, will there be a linked list in each node for the overlays, or how
>> will it work?
>
> Well, imagine your AA-Tree, with <= as relation and where you keep
> inserting 1s and nothing else. How will it look ?
It will be a bunch of 1s, but balanced, I think... :) The problem is
when we need to delete one of those nodes which has 1 as key. How do we
find it? When we're at the root (which also has key 1), do we go to the
right or to the left?
In the tree I have now, we can find the right node, since even if every
overlay starts and ends at 1, they will still be sorted according to
their address. Well that was the plan anyway, turns out it wasn't so
easy to keep this ordering.
So I think (but obviously most of my thinking so far has been wrong :))
that it might be easiest to keep a linked list of overlays which start
at that position in the node. In the example above, there would then
only be one node, containing a linked list of all the overlays.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 15:23 ` Joakim Jalap
@ 2017-02-03 15:54 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-03 15:54 UTC (permalink / raw)
To: Joakim Jalap; +Cc: emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Andreas Politz <politza@hochschule-trier.de> writes:
>> Well, imagine your AA-Tree, with <= as relation and where you keep
>> inserting 1s and nothing else. How will it look ?
>
> It will be a bunch of 1s, but balanced, I think... :)
and ordered as well.
> The problem is when we need to delete one of those nodes which has 1
> as key.
Well, you just delete the first node you find, which is the root. Since
they are all equal it doesn't matter.
> How do we find it? When we're at the root (which also has key 1), do
> we go to the right or to the left?
Neither, since you already found what your looking for. Yes, its an
exaggerated example.
>
> In the tree I have now, we can find the right node, since even if every
> overlay starts and ends at 1, they will still be sorted according to
> their address.
But if you know the memory address of an overlay, then what are you
looking for ?
I think its dawning in me what you are talking about. You seem to think
of nodes as a distinct entity without any ties to the overlays they are
representing ? And then you want to solve the problem of matching an
overlay with its corresponding node, by searching for it in the tree.
Does that sound familiar ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-03 12:44 ` Andreas Politz
2017-02-03 14:11 ` Joakim Jalap
@ 2017-02-04 21:22 ` Stefan Monnier
2017-02-04 23:10 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-04 21:22 UTC (permalink / raw)
To: emacs-devel
> No problem. Simply write a NEWS entry and declare it a new feature.
That's an efficient solution, indeed.
> If I'm right, we *could* use one tree for front-advance overlays and one
> for non-front-advance ones, such that these tree won't ever become
> unordered by insertion/deletion of text.
But I don't think this one is an efficient solution. I'm not even sure
it will lead to simpler code (at least I'm pretty sure it will lead to
more code).
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-04 21:22 ` Stefan Monnier
@ 2017-02-04 23:10 ` Andreas Politz
2017-02-06 9:56 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-04 23:10 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> If I'm right, we *could* use [two trees] [...]
>
> But I don't think this one is an efficient solution. I'm not even sure
> it will lead to simpler code (at least I'm pretty sure it will lead to
> more code).
Yes, I'm not in favour of it either.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-04 23:10 ` Andreas Politz
@ 2017-02-06 9:56 ` Joakim Jalap
2017-02-06 11:33 ` Andreas Politz
2017-02-06 13:51 ` Stefan Monnier
0 siblings, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2017-02-06 9:56 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>
>>> If I'm right, we *could* use [two trees] [...]
>>
>> But I don't think this one is an efficient solution. I'm not even sure
>> it will lead to simpler code (at least I'm pretty sure it will lead to
>> more code).
>
> Yes, I'm not in favour of it either.
>
And here I thought it was rather an elegant solution :) (to the problem
of one overlay's beg going past another's because of an insert).
What's a better way? When adjusting for an insert at an overlay with
front-advance non nil, first delete it from the tree, then reinsert it?
Isn't there a risk the tree becomes unbalanced otherwise?
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 9:56 ` Joakim Jalap
@ 2017-02-06 11:33 ` Andreas Politz
2017-02-06 15:33 ` Joakim Jalap
2017-02-07 12:35 ` Andreas Politz
2017-02-06 13:51 ` Stefan Monnier
1 sibling, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-06 11:33 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Andreas Politz <politza@hochschule-trier.de> writes:
>
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>
>>>> If I'm right, we *could* use [two trees] [...]
>>>
>>> But I don't think this one is an efficient solution.[...]
>>
>> Yes, I'm not in favour of it either.
>>
> And here I thought it was rather an elegant solution :) (to the problem
> of one overlay's beg going past another's because of an insert).
I think the problem is that this would entail either having lots of ugly
code at places where this double-tree is accessed, or having to create
some kind of layer, hiding the fact that there are two trees.
> What's a better way? When adjusting for an insert at an overlay with
> front-advance non nil, first delete it from the tree, then reinsert it?
> Isn't there a risk the tree becomes unbalanced otherwise?
I think its safe (in a RB-Tree anyway, AA probably as well) to remove
the root node of the tree, given, that all other nodes are sorted.
When recursively applied, it tells us that before we are attempting to
remove an unsorted node, we need to make sure that its descendants are
in-order. In order to do that we just need to collect them
appropriately while traversing the tree.
BTW. I don't think this would change the complexity of the algorithm,
since we're already in k*log(n) territory.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 9:56 ` Joakim Jalap
2017-02-06 11:33 ` Andreas Politz
@ 2017-02-06 13:51 ` Stefan Monnier
2017-02-06 14:26 ` Andreas Politz
2017-02-06 15:40 ` Joakim Jalap
1 sibling, 2 replies; 110+ messages in thread
From: Stefan Monnier @ 2017-02-06 13:51 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Andreas Politz, emacs-devel
> And here I thought it was rather an elegant solution :) (to the problem
> of one overlay's beg going past another's because of an insert).
It doesn't solve the problem of updating the tree after
a deletion (where some overlays may suddenly end up at the same place,
so the tree will also need some amount of reorganization).
> What's a better way? When adjusting for an insert at an overlay with
> front-advance non nil, first delete it from the tree, then
> reinsert it?
The way I look at it, there's no good reason to try and be very clever:
whenever the text is modified somewhere, remove all the overlays whose
end points fall within (or on the edge of) the change, and then
re-insert them.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 13:51 ` Stefan Monnier
@ 2017-02-06 14:26 ` Andreas Politz
2017-02-06 15:06 ` Stefan Monnier
2017-02-06 15:40 ` Joakim Jalap
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-06 14:26 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Joakim Jalap, emacs-devel
Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>> And here I thought it was rather an elegant solution :) (to the problem
>> of one overlay's beg going past another's because of an insert).
>
> It doesn't solve the problem of updating the tree after
> a deletion (where some overlays may suddenly end up at the same place,
> so the tree will also need some amount of reorganization).
Why ? If the tree is sorted by begin only, deletions won't break the
tree order. Only insertions with 2 or more overlays at the same
position and different front-advance types may do so. Unless I missed
something.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 14:26 ` Andreas Politz
@ 2017-02-06 15:06 ` Stefan Monnier
0 siblings, 0 replies; 110+ messages in thread
From: Stefan Monnier @ 2017-02-06 15:06 UTC (permalink / raw)
To: emacs-devel
> Why ? If the tree is sorted by begin only, deletions won't break the
> tree order. Only insertions with 2 or more overlays at the same
> position and different front-advance types may do so.
But you can start with OL1 < OL2 and end with OL1 = OL2.
Admittedly, if you disallow `=` in your comparison the problem should
not occur.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 11:33 ` Andreas Politz
@ 2017-02-06 15:33 ` Joakim Jalap
2017-02-06 15:46 ` Stefan Monnier
2017-02-06 17:32 ` Andreas Politz
2017-02-07 12:35 ` Andreas Politz
1 sibling, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2017-02-06 15:33 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
>> And here I thought it was rather an elegant solution :) (to the problem
>> of one overlay's beg going past another's because of an insert).
>
> I think the problem is that this would entail either having lots of ugly
> code at places where this double-tree is accessed, or having to create
> some kind of layer, hiding the fact that there are two trees.
I don't think it would be that ugly. Instead of:
adjust_overlays_for_insert (current_buffer->overlays);
it will be:
adjust_overlays_for_insert (current_buffer->front_insert_overlays);
adjust_overlays_for_insert (current_buffer->non_front_insert_overlays);
I don't think it's that big of a deal. But I guess that's a matter of
personal preference. (obviously the member names would be something...
better)
> I think its safe (in a RB-Tree anyway, AA probably as well) to remove
> the root node of the tree, given, that all other nodes are sorted.
>
> When recursively applied, it tells us that before we are attempting to
> remove an unsorted node, we need to make sure that its descendants are
> in-order. In order to do that we just need to collect them
> appropriately while traversing the tree.
>
> BTW. I don't think this would change the complexity of the algorithm,
> since we're already in k*log(n) territory.
Maybe not... but it still sounds a bit expensive to me, spontaneously.
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 13:51 ` Stefan Monnier
2017-02-06 14:26 ` Andreas Politz
@ 2017-02-06 15:40 ` Joakim Jalap
2017-02-06 16:24 ` Clément Pit-Claudel
1 sibling, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-06 15:40 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Andreas Politz, emacs-devel
Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>> And here I thought it was rather an elegant solution :) (to the problem
>> of one overlay's beg going past another's because of an insert).
>
> It doesn't solve the problem of updating the tree after
> a deletion (where some overlays may suddenly end up at the same place,
> so the tree will also need some amount of reorganization).
But an overlay can't *pass* another because of a delete, so I think that
case is OK.
>> What's a better way? When adjusting for an insert at an overlay with
>> front-advance non nil, first delete it from the tree, then
>> reinsert it?
>
> The way I look at it, there's no good reason to try and be very clever:
> whenever the text is modified somewhere, remove all the overlays whose
> end points fall within (or on the edge of) the change, and then
> re-insert them.
This sounds very expensive to me, theres quite a lot of rebalncing going
on at insertion/deletion. But maybe that isn't a problem.
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 15:33 ` Joakim Jalap
@ 2017-02-06 15:46 ` Stefan Monnier
2017-02-06 16:52 ` Joakim Jalap
2017-02-06 17:32 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-06 15:46 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Andreas Politz, emacs-devel
> Maybe not... but it still sounds a bit expensive to me, spontaneously.
The number of overlays whose boundary happens to be just at the point of
insertion is likely to be usually 0, sometimes 1 and very rarely more.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 15:40 ` Joakim Jalap
@ 2017-02-06 16:24 ` Clément Pit-Claudel
0 siblings, 0 replies; 110+ messages in thread
From: Clément Pit-Claudel @ 2017-02-06 16:24 UTC (permalink / raw)
To: emacs-devel
On 2017-02-06 10:40, Joakim Jalap wrote:
> Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>> The way I look at it, there's no good reason to try and be very clever:
>> whenever the text is modified somewhere, remove all the overlays whose
>> end points fall within (or on the edge of) the change, and then
>> re-insert them.
>
> This sounds very expensive to me, theres quite a lot of rebalncing going
> on at insertion/deletion. But maybe that isn't a problem.
Given that things currently get *very* slow with large numbers of overlays, all of this sounds blazing fast to me :P
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 15:46 ` Stefan Monnier
@ 2017-02-06 16:52 ` Joakim Jalap
2017-02-06 17:34 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-06 16:52 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Andreas Politz, emacs-devel
Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
>> Maybe not... but it still sounds a bit expensive to me, spontaneously.
>
> The number of overlays whose boundary happens to be just at the point of
> insertion is likely to be usually 0, sometimes 1 and very rarely more.
True. Even rarer I guess that they have differing front-advance types.
Still I think finding those overlays, deleting them if they are there
and then reinserting them requires quite a few traversals of the tree.
Maybe it's not a big deal perfomance wise, but I have a feeling the code
could be a bit messy. (But my feelings are eusually not correct)
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 15:33 ` Joakim Jalap
2017-02-06 15:46 ` Stefan Monnier
@ 2017-02-06 17:32 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-06 17:32 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> I don't think it would be that ugly. Instead of:
>
> adjust_overlays_for_insert (current_buffer->overlays);
>
> it will be:
>
> adjust_overlays_for_insert (current_buffer->front_insert_overlays);
> adjust_overlays_for_insert (current_buffer->non_front_insert_overlays);
>
Well, maybe ugly is not the right word. Take at the current code (where
overlays are split into 2 lists), were you see frequent occurrences of
paired loops etc..
But first, you're not done. You also need to merge two lists from both
trees sometimes, e.g. if you are looking for the next overlay after some
position. More generally, if the overlays need to be in order.
Secondly, the code which fixes the tree is pretty compact (~10lines) and
in the worst case (all but one overlay need to be reinserted) the
run-time is at most doubled, I think. But two times little is still not
very much (compared to the status quo anyway) and we spare ourselves
above trouble.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 16:52 ` Joakim Jalap
@ 2017-02-06 17:34 ` Stefan Monnier
0 siblings, 0 replies; 110+ messages in thread
From: Stefan Monnier @ 2017-02-06 17:34 UTC (permalink / raw)
To: emacs-devel
> True. Even rarer I guess that they have differing front-advance types.
> Still I think finding those overlays, deleting them if they are there
> and then reinserting them requires quite a few traversals of the tree.
Should cost O(N * log M) where N is the number of overlays that you need
to remove&add and N is the total number of overlays.
IOW should be very fast.
> Maybe it's not a big deal perfomance wise, but I have a feeling the code
> could be a bit messy. (But my feelings are eusually not correct)
My assumption is that the code to remove&add would be easy to write, but
I've often been wrong in such assessments as well. All I'm saying is
that remove&add should be plenty fast enough, so it should not be
dismissed on performance grounds. But if another solution is simpler...
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-06 11:33 ` Andreas Politz
2017-02-06 15:33 ` Joakim Jalap
@ 2017-02-07 12:35 ` Andreas Politz
2017-02-07 14:46 ` Joakim Jalap
2017-02-07 22:00 ` Andreas Politz
1 sibling, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-07 12:35 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> I think its safe (in a RB-Tree anyway, AA probably as well) to remove
> the root node of the tree, given, that all other nodes are sorted.
Well, this assumption was a little bit short-sighted, since deleting a
node may restructure the tree in way which changes this ancestor
relationship.
I thought about adding the front-advance property into the key-function,
but that just moves the problem to the deletion stage.
What I ended up doing was removing all nodes with front-advance set and
starting at the insert position before doing the normal operation on the
other nodes, and then reinserting the front-advance ones with
incremented begin (according to length of the "inserted text").
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-07 12:35 ` Andreas Politz
@ 2017-02-07 14:46 ` Joakim Jalap
2017-02-07 22:00 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Joakim Jalap @ 2017-02-07 14:46 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> What I ended up doing was removing all nodes with front-advance set and
> starting at the insert position before doing the normal operation on the
> other nodes, and then reinserting the front-advance ones with
> incremented begin (according to length of the "inserted text").
Incidentally, this is the exact same thought I had, after Stefan's
reassurance it would not be too slow :)
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-07 12:35 ` Andreas Politz
2017-02-07 14:46 ` Joakim Jalap
@ 2017-02-07 22:00 ` Andreas Politz
2017-02-08 0:36 ` Andreas Politz
2017-02-08 13:04 ` Stefan Monnier
1 sibling, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-07 22:00 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
I have a question: The comment in lisp.h says not make Lisp_Misc bigger.
I'm trying to incrementally implement the interval tree for overlays,
with out breaking everything from the start. So I added 2 pointers to
Lisp_Overlay, making it 16 bytes larger (40 vs 56). Will this
work at all ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-07 22:00 ` Andreas Politz
@ 2017-02-08 0:36 ` Andreas Politz
2017-02-08 6:53 ` Joakim Jalap
2017-02-08 13:04 ` Stefan Monnier
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-08 0:36 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> I have a question: [...] trying to incrementally implement the
> interval tree for overlays, [...]
Never mind. I think that's a waste of time.
Anyway, I have the interval data-structure pretty much down and am now
wading through the current overlay code, in order to determine the
functionality I'm going to have to reimplement. Having fun so far.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 0:36 ` Andreas Politz
@ 2017-02-08 6:53 ` Joakim Jalap
2017-02-08 7:34 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Joakim Jalap @ 2017-02-08 6:53 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> Anyway, I have the interval data-structure pretty much down and am now
> wading through the current overlay code, in order to determine the
> functionality I'm going to have to reimplement. Having fun so far.
>
FWIW I've allready all this boring stuff. I you want you can look at my
branch at https://github.com/jockej/emacs-mirror2 branch
arne-without-parent.
The interface is always the same*: Gather all the interesting overlays in
a vector. The affected files are pretty much buffer.c, xdisp.c,
xfaces.c, insdel.c and fileio.c IIRC. Somewhere towards the end
ofoverlays.c in my branch (before the new lisp functions) are my
implementations of those gathering functions. I think I got all the
places covered.
*There are some that are slightly different, like next_overlay_start and
such, but it's mostly the same.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 6:53 ` Joakim Jalap
@ 2017-02-08 7:34 ` Andreas Politz
2017-02-08 8:18 ` Joakim Jalap
2017-02-08 17:38 ` Eli Zaretskii
0 siblings, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-08 7:34 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Andreas Politz <politza@hochschule-trier.de> writes:
>
>> [...] wading through the current overlay code [...]
> FWIW I've allready all this boring stuff. I you want you can look at my
> branch at https://github.com/jockej/emacs-mirror2 branch
> arne-without-parent.
I already did, although briefly. I think its even in the upstream repository (?).
> The interface is always the same*: Gather all the interesting overlays in
> a vector. [...]
Yes, but I'm trying to get a little bit behind that. For example there
is a common idiom of
1. gather overlays in a vector
2. sort by prioriy
3. determine the effective value of some property at some position
So there should be a function answering question No. 3 without necessarily going
through steps 1 and 2 .
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 7:34 ` Andreas Politz
@ 2017-02-08 8:18 ` Joakim Jalap
2017-02-08 8:44 ` Andreas Politz
2017-02-08 16:34 ` Andreas Politz
2017-02-08 17:38 ` Eli Zaretskii
1 sibling, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2017-02-08 8:18 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> Joakim Jalap <joakim.jalap@fastmail.com> writes:
>
>> Andreas Politz <politza@hochschule-trier.de> writes:
>>
>>> [...] wading through the current overlay code [...]
>
>> FWIW I've allready all this boring stuff. I you want you can look at my
>> branch at https://github.com/jockej/emacs-mirror2 branch
>> arne-without-parent.
>
> I already did, although briefly. I think its even in the upstream repository (?).
Which upstream repository are we talking about?
>> The interface is always the same*: Gather all the interesting overlays in
>> a vector. [...]
>
> Yes, but I'm trying to get a little bit behind that. For example there
> is a common idiom of
>
> 1. gather overlays in a vector
> 2. sort by prioriy
> 3. determine the effective value of some property at some position
Actually I think 2 is not that common. Anyway I decided to keep the
existing function for sorting overlays, since that seemed simpler.
> So there should be a function answering question No. 3 without necessarily going
> through steps 1 and 2 .
I think I have done that. For example there are the next_ptr and
prev_ptr arguments to overlays_at. I got rid of those and instead
introduced separat functions to find next overlay start/end. I also got
rid of the extend argument to overlays_at and friends. In my version the
vector is always extended if necessary.
Anyway, I will leave you to it.
-- Joakim
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 8:18 ` Joakim Jalap
@ 2017-02-08 8:44 ` Andreas Politz
2017-02-08 16:34 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-08 8:44 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> I think I have done that. For example [...]
>
> Anyway, I will leave you to it.
No, that's OK. I should pay attention. I'm looking into merging my
interval tree with your branch.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-07 22:00 ` Andreas Politz
2017-02-08 0:36 ` Andreas Politz
@ 2017-02-08 13:04 ` Stefan Monnier
2017-02-08 22:27 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-08 13:04 UTC (permalink / raw)
To: Andreas Politz; +Cc: Joakim Jalap, emacs-devel
> I have a question: The comment in lisp.h says not make Lisp_Misc bigger.
All Lisp_Misc use the same space. This Lisp_Misc thingy was introduced
because the overhead of using a Lisp_Vectorlike was a bit higher than we
liked for those smallish objects (in terms of memory use as well as in
terms of CPU time needed for allocation/deallocation).
So, if you need an object to be larger, just take it out of Lisp_Misc
and use a Lisp_Vectorlike for it instead.
The implementation of Lisp_Vectorlike has been significantly improved in
the mean time, so the difference is not that large any more (but
Lisp_Misc should still be faster to allocate and suffers much less from
fragmentation).
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 8:18 ` Joakim Jalap
2017-02-08 8:44 ` Andreas Politz
@ 2017-02-08 16:34 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-08 16:34 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Which upstream repository are we talking about?
Nevermind, I forgot that I pulled from you.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 7:34 ` Andreas Politz
2017-02-08 8:18 ` Joakim Jalap
@ 2017-02-08 17:38 ` Eli Zaretskii
1 sibling, 0 replies; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-08 17:38 UTC (permalink / raw)
To: Andreas Politz; +Cc: joakim.jalap, monnier, emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Date: Wed, 08 Feb 2017 08:34:01 +0100
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
>
> 1. gather overlays in a vector
> 2. sort by prioriy
> 3. determine the effective value of some property at some position
For some very popular overlay properties, (3) is not meaningful.
Examples includes the 'face' properties, whose values are merged
rather than using only the "effective value" determined by sorting;
and before- and after-strings, for which the sorting order determines
only the order in which the strings are rendered on display.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 13:04 ` Stefan Monnier
@ 2017-02-08 22:27 ` Andreas Politz
2017-02-08 22:34 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-08 22:27 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Joakim Jalap, emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
> All Lisp_Misc use the same space.
So its not a hard limit, rather that making it bigger goes against the very
idea of it.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 22:27 ` Andreas Politz
@ 2017-02-08 22:34 ` Stefan Monnier
2017-02-09 9:34 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-08 22:34 UTC (permalink / raw)
To: Andreas Politz; +Cc: Joakim Jalap, emacs-devel
>> All Lisp_Misc use the same space.
> So its not a hard limit, rather that making it bigger goes against the very
> idea of it.
That's right.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-08 22:34 ` Stefan Monnier
@ 2017-02-09 9:34 ` Andreas Politz
2017-02-09 10:05 ` Joakim Jalap
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-09 9:34 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Joakim Jalap, emacs-devel
I think, I got mostly everything ready, from Fmake_overlay to
Fbuffer_swap_text. It compiles just fine after which it immediately dumps
core -- but that's another problem.
I am currently uncertain about how to properly allocate the memory I
need for
1. traversing the tree (log(n)) and
2. storing some nodes (n)
Number 1. isn't really a problem, since it can be allocated
when an overlay is created and kept for the life-time of the buffer,
since its size is pretty small.
The other storage I need due to the problem with front-advance overlays
while adjusting the overlays for insert. The size of this thing makes it
not so size to keep around. So, is it save to call xmalloc at this
point ?
---
My data-structures look like this at the moment.
#+BEGIN_SRC c
struct Lisp_Overlay
{
/* ... */
struct buffer *buffer;
struct interval_node *interval;
};
struct interval_node
{
ptrdiff_t begin, end;
/* ... */
Lisp_Object data; /* --> Lisp_Overlay */
};
struct buffer
{
/* ... */
struct interval_tree *overlays;
/* ... */
};
#+END_SRC
The tree is xmalloc'd, when the first overlay of the buffer is created
and overlay's interval_tree in build_overlay when making it. Both are
freed in their corresponding sweep function.
Does that sound alright ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-09 9:34 ` Andreas Politz
@ 2017-02-09 10:05 ` Joakim Jalap
2017-02-09 10:19 ` Andreas Politz
2017-02-13 3:44 ` Andreas Politz
0 siblings, 2 replies; 110+ messages in thread
From: Joakim Jalap @ 2017-02-09 10:05 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
Andreas Politz <politza@hochschule-trier.de> writes:
> I think, I got mostly everything ready, from Fmake_overlay to
> Fbuffer_swap_text. It compiles just fine after which it immediately dumps
> core -- but that's another problem.
>
> I am currently uncertain about how to properly allocate the memory I
> need for
>
> 1. traversing the tree (log(n)) and
> 2. storing some nodes (n)
>
> Number 1. isn't really a problem, since it can be allocated
> when an overlay is created and kept for the life-time of the buffer,
> since its size is pretty small.
>
> The other storage I need due to the problem with front-advance overlays
> while adjusting the overlays for insert. The size of this thing makes it
> not so size to keep around. So, is it save to call xmalloc at this
> point ?
>
I think it should be. I used xmalloc all the time in my branch :) Isn't
the idea to gather the interval_nodes which begin at the point of insertion,
adjust them outside the tree and then reinsert them? Then you can free
the memory right after, no?
Why do you need to allocate memory to traverse the tree? Isn't the tree,
already there?
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-09 10:05 ` Joakim Jalap
@ 2017-02-09 10:19 ` Andreas Politz
2017-02-13 3:44 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-09 10:19 UTC (permalink / raw)
To: Joakim Jalap; +Cc: Stefan Monnier, emacs-devel
Joakim Jalap <joakim.jalap@fastmail.com> writes:
> Andreas Politz <politza@hochschule-trier.de> writes:
>
>> [...] So, is it save to call xmalloc at this point ?
>>
> I think it should be. I used xmalloc all the time in my branch :) Isn't
> the idea to gather the interval_nodes which begin at the point of insertion,
> adjust them outside the tree and then reinsert them? Then you can free
> the memory right after, no?
Yes and I guess so.
> Why do you need to allocate memory to traverse the tree? Isn't the tree,
> already there?
I have a iterator interface, so I need to keep the stack around.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-09 10:05 ` Joakim Jalap
2017-02-09 10:19 ` Andreas Politz
@ 2017-02-13 3:44 ` Andreas Politz
2017-02-13 6:11 ` Eli Zaretskii
2017-02-14 0:45 ` Richard Stallman
1 sibling, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-13 3:44 UTC (permalink / raw)
To: emacs-devel
So,
I've been working on this thing and below are my preliminary
findings, so to speak. The code can be found here [1]. There is a
file etc/noverlay.org in there, containing some notes and pointing to
some other files.
I developed some performance tests, which for the most part are very
bare-bones and test single functions only in a constrained environment.
Following are some numbers, a description of the test-functions and an
attempt to make sense of the results.
====================================================================================
list tree
n=1000 n 8n 64n n 8n 64n
---------------------- ----------------------
perf-make-overlay 0.00 0.01 0.10 0.00 0.01 0.08
perf-make-overlay-continuous 0.00 0.01 0.10 0.00 0.01 0.08
perf-make-overlay-scatter 0.00 0.22 50.76 0.00 0.01 0.16
perf-delete-overlay 0.01 0.69 74.54 0.00 0.00 0.01
perf-delete-overlay-continuous 0.01 0.52 54.10 0.00 0.00 0.01
perf-delete-overlay-scatter 0.00 0.31 37.43 0.00 0.00 0.01
perf-overlays-at 0.00 0.44 88.08 0.00 0.02 0.32
perf-overlays-in 0.00 0.46 90.91 0.00 0.05 0.76
perf-insert-before 0.01 0.11 1.49 0.00 0.00 0.00
perf-insert-after 0.01 0.09 1.12 0.00 0.00 0.00
perf-insert-scatter 0.02 1.25 186.64 0.00 0.02 0.31
perf-delete-before 0.02 1.80 298.44 0.04 3.02 468.16
perf-delete-after 0.02 1.77 299.54 0.03 2.24 309.39
perf-delete-scatter 0.02 1.64 277.82 0.00 0.05 1.09
----------------------- -----------------------
perf-flycheck 5.01* / 23.83 4.88
perf-flycheck-display 15.03* 7.64
====================================================================================
* with overlay-recenter
* perf-(make|delete)-overlay
(Make|delete) N overlays in an empty buffer.
* perf-(make|delete)-overlay-continuous
(Make|delete) N consecutive overlays of length 1 in a buffer of size
N.
* perf-(make|delete)-overlay-scatter
(Make|delete) N randomly chosen overlays of length 24 in a buffer of
size N.
* perf-overlays-(at|in)
Extract overlays (at|in) every buffer (position|range of length 24) from
1 to point-max.
* perf-insert-(before|after|scatter)
Insert N overlays randomly in a N sized buffer and insert N
character at (point-min|point-max|randomly).
* perf-delete-(before|after|scatter)
Same as above, but delete characters.
* perf-flycheck
Perform a flycheck on a notorious file[2] with about 15000 errors.
The second lower number for the master branch results from an
inserted overlay-recenter into the flycheck code. These numbers
vary greatly for the list implementation.
* perf-flycheck-display
Same as above, then scroll the buffer once completely down and up
again, while redisplaying after every scroll step.
Since the current overlay implementation is very sensitive to its
center position, I chose the most favorable of either point-min or
-max in every non-random test. Furthermore, I measured only the
function itself, e.g. perf-delete-overlay does not include the time to
create the overlays. Also I garbage-collected before every test. All
overlays were created with default advance.
I think we see what one should expect: The list implementation
performs decent, if the number of overlays stays reasonable or it is
allowed to insert/delete from the list start. Only when the numbers
get close to 100.000 and it needs to perform random-access operations,
are we seeing a serious performance degradation.
On the other hand, the tree stays solid even with large numbers,
except for two notable cases: Continuously deleting at the beginning
or end of the buffer. In this case the overlays sooner or later all
linger at the same position and the tree slowly turns into a black
soup -- effectively a unordered, awkward to traverse list.
Recentering the list's center in the flycheck test shows the
difference between the optimal linear and the worst case quadratic
complexity of this implementation (when adding n elements). But I
this "magic trick" (using overlay-recenter) only works, if the buffer
does not contain a significant amount of overlays to begin with.
The final test seems to indicate that redisplay has an effect on this,
probably due to the fact that it in some cases recenters the lists.
-ap
[1] https://github.com/politza/emacs-noverlay
[2] https://github.com/flycheck/flycheck/issues/635
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 3:44 ` Andreas Politz
@ 2017-02-13 6:11 ` Eli Zaretskii
2017-02-13 9:04 ` Andreas Politz
2017-02-17 4:58 ` Andreas Politz
2017-02-14 0:45 ` Richard Stallman
1 sibling, 2 replies; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-13 6:11 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Date: Mon, 13 Feb 2017 04:44:05 +0100
>
> I've been working on this thing and below are my preliminary
> findings, so to speak. The code can be found here [1]. There is a
> file etc/noverlay.org in there, containing some notes and pointing to
> some other files.
>
> I developed some performance tests, which for the most part are very
> bare-bones and test single functions only in a constrained environment.
> Following are some numbers, a description of the test-functions and an
> attempt to make sense of the results.
Thank you for working on this important issue.
From my POV, a very important performance issue is that of redisplay.
So I'd like to see a performance comparison in at least three use
cases:
. scrolling through a buffer with lots of overlays that affect faces
of characters in the buffer text
. scrolling through a buffer with lots of overlays that define
'display' properties which are strings
. scrolling through a buffer with lots of overlays that define
'invisible' properties
Bonus points for having multiple overlays with different priorities at
the same buffer positions.
> The final test seems to indicate that redisplay has an effect on this,
> probably due to the fact that it in some cases recenters the lists.
The display engine always recenters overlays around the line of text
it is rendering. See, e.g., display_line in xdisp.c.
Thanks.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 6:11 ` Eli Zaretskii
@ 2017-02-13 9:04 ` Andreas Politz
2017-02-13 14:36 ` Eli Zaretskii
2017-02-17 4:58 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-13 9:04 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
>> From: Andreas Politz <politza@hochschule-trier.de>
> Thank you for working on this important issue.
I enjoyed it.
> From my POV, a very important performance issue is that of redisplay.
Do you expect redisplay performance to improve or is it your aim that it
does not degrade ?
> So I'd like to see a performance comparison in at least three use
> cases:
I did a quick test using highlight-regexp which indicate that it makes
no or not much of a difference. But I guess there is room for some
optimization left.
BTW how do you figure out which functions need attention,
performance-wise. Is there any experience using valgrind/callgrind,
because I tried it and the results seem bogus to me, but I may be
mistaken.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 9:04 ` Andreas Politz
@ 2017-02-13 14:36 ` Eli Zaretskii
2017-02-14 10:07 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-13 14:36 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Cc: emacs-devel@gnu.org
> Date: Mon, 13 Feb 2017 10:04:13 +0100
>
> Eli Zaretskii <eliz@gnu.org> writes:
>
> >> From: Andreas Politz <politza@hochschule-trier.de>
> > Thank you for working on this important issue.
>
> I enjoyed it.
I'm sure we will, too.
> > From my POV, a very important performance issue is that of redisplay.
>
> Do you expect redisplay performance to improve or is it your aim that it
> does not degrade ?
It should certainly not be worse, otherwise the design and
implementation would need to be improved, IMO. Display is a very
important client of overlays, so it shouldn't suffer from refactoring.
I would be happy to know that performance gets better, of course. The
recentering of overlays, which is not a cheap operation, should no
longer be needed, for example.
> BTW how do you figure out which functions need attention,
> performance-wise.
If you mean overlay-specific functions, I can name the most important
ones for you. I know which ones they are because I know what the
display engine calls in its inner loops.
> Is there any experience using valgrind/callgrind, because I tried it
> and the results seem bogus to me, but I may be mistaken.
Using valgrind/callgrind with Emacs needs some special techniques,
some of them are described in etc/DEBUG. I think the most important
trick is to measure temacs, not a dumped emacs binary.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 3:44 ` Andreas Politz
2017-02-13 6:11 ` Eli Zaretskii
@ 2017-02-14 0:45 ` Richard Stallman
2017-02-14 8:32 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Richard Stallman @ 2017-02-14 0:45 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
[[[ To any NSA and FBI agents reading my email: please consider ]]]
[[[ whether defending the US Constitution against all enemies, ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]
> On the other hand, the tree stays solid even with large numbers,
> except for two notable cases: Continuously deleting at the beginning
> or end of the buffer. In this case the overlays sooner or later all
> linger at the same position and the tree slowly turns into a black
> soup -- effectively a unordered, awkward to traverse list.
Aren't there established ways to avoid this by reforming the tree?
--
Dr Richard Stallman
President, Free Software Foundation (gnu.org, fsf.org)
Internet Hall-of-Famer (internethalloffame.org)
Skype: No way! See stallman.org/skype.html.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-14 0:45 ` Richard Stallman
@ 2017-02-14 8:32 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-14 8:32 UTC (permalink / raw)
To: Richard Stallman; +Cc: emacs-devel
Richard Stallman <rms@gnu.org> writes:
> Aren't there established ways to avoid this by reforming the tree?
I don't know.
We could associate a list with every node, as was mentioned earlier,
s.t. every begin position is represented by a unique node, containing
all overlays at this position. But I don't know if it'll worth it.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 14:36 ` Eli Zaretskii
@ 2017-02-14 10:07 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-14 10:07 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
>> Do you expect redisplay performance to improve or is it your aim that it
>> does not degrade ?
>
> It should certainly not be worse, otherwise the design and
> implementation would need to be improved, IMO. Display is a very
> important client of overlays, so it shouldn't suffer from refactoring.
I had the idea, that this centered list intuitively sounds like a good
fit for the display's requirements, i.e. usually little random access
and the center can be updated relatively cheaply while scrolling.
> I would be happy to know that performance gets better, of course. The
> recentering of overlays, which is not a cheap operation, should no
> longer be needed, for example.
>
It definitively is not needed. I currently trying to improve the
performance of my implementation, with some success.
>> BTW how do you figure out which functions need attention,
>> performance-wise.
> If you mean overlay-specific functions, I can name the most important
> ones for you. I know which ones they are because I know what the
> display engine calls in its inner loops.
I guess, I figured it out.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-13 6:11 ` Eli Zaretskii
2017-02-13 9:04 ` Andreas Politz
@ 2017-02-17 4:58 ` Andreas Politz
2017-02-17 7:12 ` Eli Zaretskii
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-17 4:58 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
So, I did as you ask and developed a couple of performance tests
based on 3 variables. Let N = #overlays.
1. How the overlays are created
+ Either sequentially, one overlay per every other line or
randomly, with random start and random length from 0 to 70.
2. What property to use
+ One of face, display (with a string) or invisible.
3. How the overlays are accessed
+ Either start at the top scroll down and up again, or jump to
N/25 random positions and re-display there.
This gives 2*3*2=12 different tests. In all of them I
+ ran all tests once with N=12.500 and 37500 overlays.
+ used a buffer with 2*N lines and 70 columns,
+ measured display time only, i.e. not make-overlay etc. .
+ ran each test thrice and took the average.
*--------------------------------------------------------------*
+----------------------------------+
| 12.5K | 37.5K |
creation/property/action | list tree | list tree |
================================================================
|sequential/display/scroll | 6.32 5.24 | 37.59 16.47 |
| | | |
|sequential/display/random | 4.47 4.60 | 30.41 13.03 |
+---------------------------+----------------+-----------------+
|sequential/face/scroll | 7.07 5.75 | 38.18 18.64 |
| | | |
|sequential/face/random | 4.25 4.13 | 30.50 13.23 |
+---------------------------+----------------+-----------------+
|sequential/invisible/scroll| 6.63 5.02 | 36.62 16.02 |
| | | |
|sequential/invisible/random| 3.98 3.64 | 29.93 11.10 |
+---------------------------+----------------+-----------------+
|random/display/scroll | 20.39 18.6 | 88.84 58.18 |
| | | |
|random/display/random | 7.57 7.22 | 77.65 21.14 |
+---------------------------+----------------+-----------------+
|random/face/scroll | 11.16 8.75 | 88.31 27.72 |
| | | |
|random/face/random | 6.19 5.59 | 105.0 17.05 |
+---------------------------+----------------+-----------------+
|random/invisible/scroll | 9.91 7.99 | 87.01 25.97 |
| | | |
|random/invisible/random | 6.58 5.75 | 86.73 17.01 |
+---------------------------+----------------+-----------------+
| | list | tree |
+---------------------------+----------------------------------+
|make-lines-invisible | 812.67 | 1.43 |
| | | |
|line-numbering | >15m * | 112.79 |
================================================================
As you can see they stick pretty close together in the cases with
12500 overlays, while the tree performs at least twice times better
with 37500 overlays.
After that I took 2 real-world cases. The first one stems from this
[1] thread, where a user complains about the performance of his
function make-lines-invisible. The function puts overlays with an
invisible property on all lines matching a given regexp. The function
also messages the number of hidden lines after every found match,
which may be the reason for its bad performance with the current
implementation, speak re-display. This test measures the creation of
these overlays, no scrolling.
For the other case, I wrote a very simple linum.el clone. This
function creates an overlay with a margin property containing the
line-number for every line in the buffer. Here I measured creation of
the overlays as well as a full scroll up and down.
Both of the final tests were run on a ~300000 lines file with one
english word per line (/usr/share/dict/words).
* I gave up and quit the test after nothing seemed to happen on the
screen for more than 15 minutes.
So, I think this looks pretty decent.
Finally, let me note, that the tree implementation is not
completely free of quadratic worst-case performance. There are
certain patterns of overlay layout, which trigger this kind of
thing. Though, it can be argued how likely these are to occur in
a real-world scenario. Maybe I'll write a bit more about that
later.
-ap
[1] https://lists.gnu.org/archive/html/emacs-devel/2009-04/msg00242.html
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-17 4:58 ` Andreas Politz
@ 2017-02-17 7:12 ` Eli Zaretskii
2017-02-19 22:39 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-17 7:12 UTC (permalink / raw)
To: Andreas Politz; +Cc: emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Cc: emacs-devel@gnu.org
> Date: Fri, 17 Feb 2017 05:58:34 +0100
>
> So, I did as you ask and developed a couple of performance tests
> based on 3 variables. Let N = #overlays.
Thanks.
> +----------------------------------+
> | 12.5K | 37.5K |
> creation/property/action | list tree | list tree |
> ================================================================
> |sequential/display/scroll | 6.32 5.24 | 37.59 16.47 |
> | | | |
> |sequential/display/random | 4.47 4.60 | 30.41 13.03 |
> +---------------------------+----------------+-----------------+
> |sequential/face/scroll | 7.07 5.75 | 38.18 18.64 |
> | | | |
> |sequential/face/random | 4.25 4.13 | 30.50 13.23 |
> +---------------------------+----------------+-----------------+
> |sequential/invisible/scroll| 6.63 5.02 | 36.62 16.02 |
> | | | |
> |sequential/invisible/random| 3.98 3.64 | 29.93 11.10 |
> +---------------------------+----------------+-----------------+
> |random/display/scroll | 20.39 18.6 | 88.84 58.18 |
> | | | |
> |random/display/random | 7.57 7.22 | 77.65 21.14 |
> +---------------------------+----------------+-----------------+
> |random/face/scroll | 11.16 8.75 | 88.31 27.72 |
> | | | |
> |random/face/random | 6.19 5.59 | 105.0 17.05 |
> +---------------------------+----------------+-----------------+
> |random/invisible/scroll | 9.91 7.99 | 87.01 25.97 |
> | | | |
> |random/invisible/random | 6.58 5.75 | 86.73 17.01 |
> +---------------------------+----------------+-----------------+
> | | list | tree |
> +---------------------------+----------------------------------+
> |make-lines-invisible | 812.67 | 1.43 |
> | | | |
> |line-numbering | >15m * | 112.79 |
> ================================================================
This looks very good indeed, thanks.
> So, I think this looks pretty decent.
I agree.
> Finally, let me note, that the tree implementation is not
> completely free of quadratic worst-case performance. There are
> certain patterns of overlay layout, which trigger this kind of
> thing. Though, it can be argued how likely these are to occur in
> a real-world scenario. Maybe I'll write a bit more about that
> later.
Please do when you have time.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-17 7:12 ` Eli Zaretskii
@ 2017-02-19 22:39 ` Andreas Politz
2017-02-19 23:10 ` Stefan Monnier
2017-02-20 15:34 ` Eli Zaretskii
0 siblings, 2 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-19 22:39 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: Joakim Jalap, Stefan Monnier, emacs-devel
>> From: Andreas Politz <politza@hochschule-trier.de>
>> [...] the tree implementation is not completely free of quadratic
>> worst-case performance.[...]
Here is one such case were the tree is forced to search through all
overlays in order to find the next change:
|--------------------------|
|-------------------|
|-------------|
B ^ E
P
We are looking for the next change after P, which is E. But E is the
end of some overlay, and the tree knows nothing about the order of
these, so it needs to consider all overlays. Here are some numbers;
+------------------------+-----+------+
|2500 overlays |tree |list |
+------------------------+-----+------+
|sequential/face/scroll |1.28 |1.32 |
+------------------------+-----+------+
|hierarchical/face/scroll|76.59|174.64|
+------------------------+-----+------+
For comparison, I added the results for the same number of overlays, but
layed out in a non-overlapping, sequential fashion. I think the list
performs even worse because the display engine calls overlay-recenter
approx. for every line, which does nothing but traversing the after list
once.
Earlier I wrote to the effect, this scenario being far fetched. But
there is at least one very real application coming to my mind now: A
stateful folding mode using overlays to keep data about, possibly
closed, folds.
At the moment I can think of 4 ways out of this:
1. Use a variation of the interval tree
a.) trees, the second being sorted by overlay-end.
+ would get rid of this altogether
- more memory and code
b.) Have two node types and enter every overlay twice.
- probably worse than 1. in every way.
c.) ???
2. Use some heuristic cache
E.g. when we are scrolling forward, a lot of re-computation of already
computed end-values is performed. These could be cached in some way.
+ my guess is that it had the potential of improving the performance
by a constant factor
- won't work for random access, e.g. isearch
3. Ignore the problem
I think it is a very bad idea, to replace one data-structure with bad
worst-case behavior with another one. Unless we can convince
ourselves that this really is no problem (*cough*).
4. Use some better data-structure
We need the overlays-in function, indicating that some kind of
efficient interval managing data-structure is the right approach. It
just also needs to be able to answer the next-overlay-change
challenge in all cases efficiently. I
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-19 22:39 ` Andreas Politz
@ 2017-02-19 23:10 ` Stefan Monnier
2017-02-19 23:44 ` Andreas Politz
2017-02-20 15:34 ` Eli Zaretskii
1 sibling, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-19 23:10 UTC (permalink / raw)
To: emacs-devel
> Here is one such case were the tree is forced to search through all
> overlays in order to find the next change:
> |--------------------------|
> |-------------------|
> |-------------|
> B ^ E
> P
> We are looking for the next change after P, which is E. But E is the
> end of some overlay, and the tree knows nothing about the order of
> these, so it needs to consider all overlays.
Maybe I don't understand your example, but AFAICT it doesn't need to
consider all overlays: only those that cover P.
> A stateful folding mode using overlays to keep data about, possibly
> closed, folds.
Even if that results in thousands of overlays in the buffer, any
particular location in the buffer shouldn't have a "folding nesting" so
terribly high that it is covered by hundreds of overlays.
The complexity of overlays-in and overlays-at is necessarily of O(N) where
N is the number of overlays covering the area. Even O(N log M) (where
M is the total number of overlays) should be fine.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-19 23:10 ` Stefan Monnier
@ 2017-02-19 23:44 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-19 23:44 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> Here is one such case were the tree is forced to search through all
>> overlays in order to find the next change:
>
>> |--------------------------|
>> |-------------------|
>> |-------------|
>> B ^ E
>> P
>
>> We are looking for the next change after P, which is E. But E is the
>> end of some overlay, and the tree knows nothing about the order of
>> these, so it needs to consider all overlays.
>
> Maybe I don't understand your example, but AFAICT it doesn't need to
> consider all overlays: only those that cover P.
In this case all of them do. I painted N=3 overlays only.
> Even if that results in thousands of overlays in the buffer, any
> particular location in the buffer shouldn't have a "folding nesting" so
> terribly high that it is covered by hundreds of overlays.
Yes, that's a good point.
> The complexity of overlays-in and overlays-at is necessarily of O(N) where
> N is the number of overlays covering the area. Even O(N log M) (where
> M is the total number of overlays) should be fine.
Yes, but next-overlay-change (which is a function re-display heavily
depends on) does not need all overlays at some position, but just the
least of the next end or begin of them. It is not *necessary*
to consider all overlays covering some position, its simply the best way
of doing it with the current implementations.
So, I guess I'm seeing to black then.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-19 22:39 ` Andreas Politz
2017-02-19 23:10 ` Stefan Monnier
@ 2017-02-20 15:34 ` Eli Zaretskii
2017-02-21 6:56 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2017-02-20 15:34 UTC (permalink / raw)
To: Andreas Politz; +Cc: joakim.jalap, monnier, emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Cc: emacs-devel@gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>, Joakim Jalap <joakim.jalap@fastmail.com>
> Date: Sun, 19 Feb 2017 23:39:41 +0100
>
> Here is one such case were the tree is forced to search through all
> overlays in order to find the next change:
>
> |--------------------------|
> |-------------------|
> |-------------|
> B ^ E
> P
>
> We are looking for the next change after P, which is E. But E is the
> end of some overlay, and the tree knows nothing about the order of
> these, so it needs to consider all overlays. Here are some numbers;
>
> +------------------------+-----+------+
> |2500 overlays |tree |list |
> +------------------------+-----+------+
> |sequential/face/scroll |1.28 |1.32 |
> +------------------------+-----+------+
> |hierarchical/face/scroll|76.59|174.64|
> +------------------------+-----+------+
The new implementation is still faster than the old one, so perhaps
you shouldn't bother too much? Or am I missing something?
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-20 15:34 ` Eli Zaretskii
@ 2017-02-21 6:56 ` Andreas Politz
2017-02-21 15:11 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-21 6:56 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: joakim.jalap, monnier, emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
>> +------------------------+-----+------+
>> |2500 overlays |tree |list |
>> +------------------------+-----+------+
>> |sequential/face/scroll |1.28 |1.32 |
>> +------------------------+-----+------+
>> |hierarchical/face/scroll|76.59|174.64|
>> +------------------------+-----+------+
>
> The new implementation is still faster than the old one, so perhaps
> you shouldn't bother too much? Or am I missing something?
Well, if my implementation were to be, for example, twice as fast as the
current one for every operation, that would still be to slow.
There is absolute run-time and then there is growth rate. What you
should comparing is the first with the second line, any column will
do. It's a factor of >50 and the difference between m*log(n) and m*n
(with m being the number of "scrolled lines" and n the number of
overlays.) The only difference here is the way these overlays were
layed out.
Ideally, I think, this last detail should be of no consequence and the
implementation should only be limited by the number of overlays and not
by where in the buffer they occur.
But, yes, I shouldn't worry so much. I also missed an important detail:
After we determined the next overlay change, we most likely are going to
examine the overlays properties at that position. And this would
require examining all n overlays (in the "hierarchical" scenario)
anyway, thus the complexity of the operation as a whole would not
change, if next-overlay-change were to be faster.
I think I'm going to relax now.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-21 6:56 ` Andreas Politz
@ 2017-02-21 15:11 ` Stefan Monnier
2017-02-21 18:26 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-02-21 15:11 UTC (permalink / raw)
To: emacs-devel
> Ideally, I think, this last detail should be of no consequence and the
> implementation should only be limited by the number of overlays and not
> by where in the buffer they occur.
Luckily, it's not currently a problem we really face. Instead the
problem we face is how to handle a large number of overlays in a buffer,
but where any given buffer position is only covered by a modest number
of overlays.
The problem of handling efficiently a large number of overlays covering
a given position seems pretty hard to solve, actually.
> I think I'm going to relax now.
BTW, in your new overlay representation, how many bytes (or words) does
an overlay cost (in the master tree, if I count right, an overlay costs
3 Lisp_Misc objects, so that should be 3x 6words, i.e. 72 bytes on
a 32bit system)?
I'd expect the new representation to be no larger (the current
representation has a lot of redundancy). But I'm curious because,
depending on the answer, the whole Lisp_Misc thingy might want to
be reconsidered.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-21 15:11 ` Stefan Monnier
@ 2017-02-21 18:26 ` Andreas Politz
2017-02-21 19:18 ` Stefan Monnier
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-21 18:26 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
> BTW, in your new overlay representation, how many bytes (or words) does
> an overlay cost (in the master tree, if I count right, an overlay costs
> 3 Lisp_Misc objects, so that should be 3x 6words, i.e. 72 bytes on
> a 32bit system)?
>
> I'd expect the new representation to be no larger (the current
> representation has a lot of redundancy). But I'm curious because,
> depending on the answer, the whole Lisp_Misc thingy might want to
> be reconsidered.
>
I don't' know how you're counting, so here is how I (or rtags) would.
#+BEGIN_SRC c
/* master */
struct Lisp_Overlay
{
ENUM_BF (Lisp_Misc_Type) type : 16;
bool_bf gcmarkbit : 1;
unsigned spacer : 15;
struct Lisp_Overlay *next;
Lisp_Object start; /* -> 40 bytes */
Lisp_Object end; /* -> 40 bytes */
Lisp_Object plist; /* -> 40 bytes */
}; /* 40 bytes */
/* Total: 40 + 3*40 = 160 */
/* noverlay */
struct Lisp_Overlay
{
ENUM_BF (Lisp_Misc_Type) type : 16;
bool_bf gcmarkbit : 1;
unsigned spacer : 15;
Lisp_Object plist; /* -> 40 bytes */
struct buffer *buffer;
struct interval_node *interval;
}; /* 32 bytes */
struct interval_node /* layout tweaked */
{
struct interval_node *parent;
struct interval_node *left;
struct interval_node *right;
ptrdiff_t begin; /* The beginning of this interval. */
ptrdiff_t end; /* The end of the interval. */
ptrdiff_t limit; /* The maximum end in this subtree. */
ptrdiff_t offset; /* The amount of shift to apply to this subtree. */
uintmax_t otick; /* offset modified tick */
Lisp_Object data; /* Exclusively used by the client. */
bool_bf visited : 1; /* For traversal via generator. */
bool_bf rear_advance : 1; /* Same as for marker and overlays. */
bool_bf front_advance : 1; /* Same as for marker and overlays. */
enum { ITREE_RED, ITREE_BLACK } color : 1;
}; /* 80 bytes */
/* Total: 32 + 40 + 80 = 152 */
#+END_SRC
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-21 18:26 ` Andreas Politz
@ 2017-02-21 19:18 ` Stefan Monnier
2017-02-21 23:36 ` Andreas Politz
2017-02-24 8:43 ` Andreas Politz
0 siblings, 2 replies; 110+ messages in thread
From: Stefan Monnier @ 2017-02-21 19:18 UTC (permalink / raw)
To: emacs-devel
> /* master */
> struct Lisp_Overlay
> {
> ENUM_BF (Lisp_Misc_Type) type : 16;
> bool_bf gcmarkbit : 1;
> unsigned spacer : 15;
> struct Lisp_Overlay *next;
> Lisp_Object start; /* -> 40 bytes */
> Lisp_Object end; /* -> 40 bytes */
> Lisp_Object plist; /* -> 40 bytes */
> }; /* 40 bytes */
> /* Total: 40 + 3*40 = 160 */
Hmm... I don't know how you're counting either ;-)
the type+gcmarkbit+spacer bit fields sum up to 32bits (let's round that
to a "word").
Then we have 4 fields that hold a "word" (Lisp_Object is basically an
integer), for a total of 5 words. On 32bit systems, alloc.c rounds it
up further to 6 words or 24B (because Lisp_Objects have to be aligned on
a multiple of 8B).
> /* noverlay */
> struct Lisp_Overlay
> {
> ENUM_BF (Lisp_Misc_Type) type : 16;
> bool_bf gcmarkbit : 1;
> unsigned spacer : 15;
> Lisp_Object plist; /* -> 40 bytes */
> struct buffer *buffer;
> struct interval_node *interval;
> }; /* 32 bytes */
So that's 4 words (one less than before).
> struct interval_node /* layout tweaked */
> {
> struct interval_node *parent;
> struct interval_node *left;
> struct interval_node *right;
> ptrdiff_t begin; /* The beginning of this interval. */
> ptrdiff_t end; /* The end of the interval. */
> ptrdiff_t limit; /* The maximum end in this subtree. */
> ptrdiff_t offset; /* The amount of shift to apply to this subtree. */
> uintmax_t otick; /* offset modified tick */
> Lisp_Object data; /* Exclusively used by the client. */
> bool_bf visited : 1; /* For traversal via generator. */
> bool_bf rear_advance : 1; /* Same as for marker and overlays. */
> bool_bf front_advance : 1; /* Same as for marker and overlays. */
> enum { ITREE_RED, ITREE_BLACK } color : 1;
> }; /* 80 bytes */
> /* Total: 32 + 40 + 80 = 152 */
Here I count 9 words plus some bit fields (i.e. 10 words). I assume
there's one "struct interval_node" per overlay object, so every overlay
object uses 14 words (plus 2 because all Lisp_Misc end up using 6 words
anyway) which is indeed less than the current setup.
Is there a reason why "struct Lisp_Overlay" and "struct interval_node"
are separate? IOW could we have a single struct with all the
fields together (as a Lisp_Vectorlike rather than a Lisp_Misc)?
If so, we could bring this down to 12 words plus the Lisp_Vectorlike
header, i.e. 14 words.
[ Of course, we could probably squeeze it a bit further if we really
care, e.g. merge the `parent' and `buffer' fields, at the cost of
walking up the tree when we need to find the overlay's buffer.
But I doubt it's worthwhile. ]
That means an overlay takes up about twice the size of a marker.
Should we then (re)implement markers as degenerate overlays? [it's not
as simple as it sounds: contrary to overlays markers can be GC'd if not
referenced, so we'd need to add support for "weakly referenced
overlays". Furthermore markers are used to speed up byte<->char
conversions, so we'd need to replace that code accordingly. ]
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-21 19:18 ` Stefan Monnier
@ 2017-02-21 23:36 ` Andreas Politz
2017-02-24 8:43 ` Andreas Politz
1 sibling, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-02-21 23:36 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
> Hmm... I don't know how you're counting either ;-)
I'm counting 8,16,24, ... .
You're counting 1,2,3, ... .
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-21 19:18 ` Stefan Monnier
2017-02-21 23:36 ` Andreas Politz
@ 2017-02-24 8:43 ` Andreas Politz
2017-04-08 13:28 ` Clément Pit-Claudel
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-02-24 8:43 UTC (permalink / raw)
To: Stefan Monnier; +Cc: emacs-devel
Stefan Monnier <monnier@iro.umontreal.ca> writes:
> Is there a reason why "struct Lisp_Overlay" and "struct interval_node"
> are separate?
The main reason is that it can't be used for anything else, once the
nodes are all Lisp_Overlay's . There are at least two other balanced
trees in Emacs and maybe, at some time, there should be only one. (Also,
initially I didn't need to worry about the Emacs side.)
> [...] That means an overlay takes up about twice the size of a marker.
>
> Should we then (re)implement markers as degenerate overlays? [it's not
> as simple as it sounds: contrary to overlays markers can be GC'd if not
> referenced, so we'd need to add support for "weakly referenced
> overlays". Furthermore markers are used to speed up byte<->char
> conversions, so we'd need to replace that code accordingly. ]
Could we use the end attribute as byte value ? Also, does Emacs create
extra markers for this lookup or can this be called a "opportunistic
optimization" ?
I did some comparisons between marker and empty overlays regarding
insertions and deletions. *-before and *-after insert/delete at
point-min resp. -max, scatter means randomly. In each case 4096
single character were inserted/deleted.
===============================================
32K 64K
------------ -------------
4096 edits ma ov ma ov
-----------------------------------------------
insert-before 4.20 0.22 16.66 0.44
insert-after 3.28 0.12 12.96 0.20
insert-scatter 4.84 0.21 18.74 0.37
delete-before 4.09 60.32 16.16 277.75
delete-after 3.75 35.49 14.74 160.91
delete-scatter 4.02 0.36 15.64 0.86
===============================================
As you can see the delete-before/after cases are still somewhat
problematic. Maybe we should think about using a single node per
position combined with a list. What do you think ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-02-24 8:43 ` Andreas Politz
@ 2017-04-08 13:28 ` Clément Pit-Claudel
2017-05-03 19:20 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Clément Pit-Claudel @ 2017-04-08 13:28 UTC (permalink / raw)
To: Andreas Politz, Stefan Monnier; +Cc: emacs-devel
On 2017-02-24 03:43, Andreas Politz wrote:
> As you can see the delete-before/after cases are still somewhat
> problematic. Maybe we should think about using a single node per
> position combined with a list. What do you think ?
Any news about this? More efficient overlays would be a very welcome improvement :)
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-04-08 13:28 ` Clément Pit-Claudel
@ 2017-05-03 19:20 ` Andreas Politz
2017-05-03 19:40 ` Stefan Monnier
` (2 more replies)
0 siblings, 3 replies; 110+ messages in thread
From: Andreas Politz @ 2017-05-03 19:20 UTC (permalink / raw)
To: Clément Pit-Claudel; +Cc: Stefan Monnier, emacs-devel
I stopped working on this, since it wasn't clear where this will be
going (among other things). But I'm willing to pick it up again.
Following is a fairly concise status-report.
I'm running this branch for some time now, so I'm confident that there
are no obvious hard bugs, by which I mean bugs which would terminate
Emacs.
Even though, there is at least one of those which I haven't being
able to track down yet. It occurs in a fairly complex situation
(using customize). Probably due to a combination of narrowing and
modifying the buffer, because this is not very well tested.
The branch contains about 300 Lisp- and about 50 C-level test-cases.
I am frequently merging master into it, while pushing to
https://github.com/politza/emacs-noverlay.
The memory allocation in some functions is dynamic, which could be
made static, I assume. Also, quitting may be a problem in these
cases.
I think it would be advantageous to represent overlays with identical
start values as a single node by utilizing a linked list. This would
improve performance in some degenerate cases (from a tree's
perspective), by combining the best aspects of the (current) list and
tree approaches.
We also talked about using the same data-structure for marker, but
there is no work done in this direction currently.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-03 19:20 ` Andreas Politz
@ 2017-05-03 19:40 ` Stefan Monnier
2017-05-05 20:39 ` Andreas Politz
2017-05-04 0:54 ` Clément Pit-Claudel
2017-05-04 14:21 ` Eli Zaretskii
2 siblings, 1 reply; 110+ messages in thread
From: Stefan Monnier @ 2017-05-03 19:40 UTC (permalink / raw)
To: Andreas Politz; +Cc: Clément Pit-Claudel, emacs-devel
> I stopped working on this, since it wasn't clear where this will be
> going (among other things). But I'm willing to pick it up again.
> Following is a fairly concise status-report.
What's missing for it to be "good enough for master" (which AFAIK means
mostly that the code is clean, there are no known bugs, and the
performance is varies between "no worse" and "much better" than what we
currently have)?
> I think it would be advantageous to represent overlays with identical
> start values as a single node by utilizing a linked list. This would
> improve performance in some degenerate cases (from a tree's
> perspective), by combining the best aspects of the (current) list and
> tree approaches.
I don't think we should care too much about those degenerate cases.
> We also talked about using the same data-structure for marker, but
> there is no work done in this direction currently.
Good. Maybe it's a good idea, but maybe not. There's no hurry to
investigate (let alone make a decision on) this.
Stefan
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-03 19:20 ` Andreas Politz
2017-05-03 19:40 ` Stefan Monnier
@ 2017-05-04 0:54 ` Clément Pit-Claudel
2017-05-05 20:10 ` Andreas Politz
2017-05-04 14:21 ` Eli Zaretskii
2 siblings, 1 reply; 110+ messages in thread
From: Clément Pit-Claudel @ 2017-05-04 0:54 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
On 2017-05-03 15:20, Andreas Politz wrote:
> I stopped working on this, since it wasn't clear where this will be
> going (among other things). But I'm willing to pick it up again.
> Following is a fairly concise status-report.
That would be wonderful. Overlay performance is a recurring issue in Flycheck and PG.
I will try to run your branch and benchmark it with Flycheck, but I remember seeing great results.
> I think it would be advantageous to represent overlays with identical
> start values as a single node by utilizing a linked list. This would
> improve performance in some degenerate cases (from a tree's
> perspective), by combining the best aspects of the (current) list and
> tree approaches.
Could this comment be included in Emacs' TODO list? This sounds like a nice potential improvement over your current implementation, but it doesn't sound like its absence should prevent a merge.
Thanks for working on this!
Clément.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-03 19:20 ` Andreas Politz
2017-05-03 19:40 ` Stefan Monnier
2017-05-04 0:54 ` Clément Pit-Claudel
@ 2017-05-04 14:21 ` Eli Zaretskii
2017-05-05 20:08 ` Andreas Politz
2017-09-24 13:09 ` Clément Pit-Claudel
2 siblings, 2 replies; 110+ messages in thread
From: Eli Zaretskii @ 2017-05-04 14:21 UTC (permalink / raw)
To: Andreas Politz; +Cc: cpitclaudel, monnier, emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Date: Wed, 03 May 2017 21:20:09 +0200
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
>
>
> I stopped working on this, since it wasn't clear where this will be
> going (among other things). But I'm willing to pick it up again.
Thanks for working on this, Andreas.
> The memory allocation in some functions is dynamic, which could be
> made static, I assume. Also, quitting may be a problem in these
> cases.
Why do you think quitting might be a problem?
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-04 14:21 ` Eli Zaretskii
@ 2017-05-05 20:08 ` Andreas Politz
2017-05-05 21:41 ` Eli Zaretskii
2017-09-24 13:09 ` Clément Pit-Claudel
1 sibling, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-05-05 20:08 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: cpitclaudel, monnier, emacs-devel
Eli Zaretskii <eliz@gnu.org> writes:
> Why do you think quitting might be a problem?
If it happens while memory is dynamically allocated, while adjusting the
overlays for insertions/deletions. I suppose it can't happen, but I
haven't checked this thoroughly and so I pessimistically assume that it
will.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-04 0:54 ` Clément Pit-Claudel
@ 2017-05-05 20:10 ` Andreas Politz
2017-05-05 22:22 ` Clément Pit-Claudel
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-05-05 20:10 UTC (permalink / raw)
To: Clément Pit-Claudel; +Cc: Stefan Monnier, emacs-devel
Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
> I will try to run your branch and benchmark it with Flycheck, but I remember seeing great results.
>
Is there some benchmark code available to run ?
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-03 19:40 ` Stefan Monnier
@ 2017-05-05 20:39 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-05-05 20:39 UTC (permalink / raw)
To: Stefan Monnier; +Cc: Clément Pit-Claudel, emacs-devel
Stefan Monnier <monnier@IRO.UMontreal.CA> writes:
> What's missing for it to be "good enough for master" (which AFAIK means
> mostly that the code is clean, there are no known bugs, and the
> performance is varies between "no worse" and "much better" than what we
> currently have)?
Don't know about "clean".
I found the bug I was mentioning earlier, but it literally took hours.
I needed to construct a tree with 7 nodes while performing a series of
operations in a very specific manner. It is really difficult to
anticipate these kinds of bugs within a test-suite.
Benchmarks I've posted in the past:
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html
> I don't think we should care too much about those degenerate cases.
Yes, we could wait and see if these cases (mostly many overlapping
overlays) make a difference in real applications.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-05 20:08 ` Andreas Politz
@ 2017-05-05 21:41 ` Eli Zaretskii
0 siblings, 0 replies; 110+ messages in thread
From: Eli Zaretskii @ 2017-05-05 21:41 UTC (permalink / raw)
To: Andreas Politz; +Cc: cpitclaudel, monnier, emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Cc: cpitclaudel@gmail.com, monnier@iro.umontreal.ca, emacs-devel@gnu.org
> Date: Fri, 05 May 2017 22:08:15 +0200
>
> Eli Zaretskii <eliz@gnu.org> writes:
>
> > Why do you think quitting might be a problem?
>
> If it happens while memory is dynamically allocated, while adjusting the
> overlays for insertions/deletions.
The usual way of preventing such problems, if they are real, is to
have an unwind-protect function which releases any allocated resources
when there's a quit.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-05 20:10 ` Andreas Politz
@ 2017-05-05 22:22 ` Clément Pit-Claudel
2017-05-06 8:05 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Clément Pit-Claudel @ 2017-05-05 22:22 UTC (permalink / raw)
To: Andreas Politz; +Cc: Stefan Monnier, emacs-devel
On 2017-05-05 16:10, Andreas Politz wrote:
> Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
>
>> I will try to run your branch and benchmark it with Flycheck, but I remember seeing great results.
>>
> Is there some benchmark code available to run ?
There was a thread about this at https://github.com/flycheck/flycheck/issues/1168 ; I can try to find the benchmarking code that I used back then.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-05 22:22 ` Clément Pit-Claudel
@ 2017-05-06 8:05 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-05-06 8:05 UTC (permalink / raw)
To: Clément Pit-Claudel; +Cc: Stefan Monnier, emacs-devel
Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
>> Is there some benchmark code available to run ?
>
> There was a thread about this [...]
I remember now and talked about this. The result was that both
implementations take about the same time, given that overlay-recenter is
used appropriately. If not, the tree was about 4 times faster.
-ap
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-05-04 14:21 ` Eli Zaretskii
2017-05-05 20:08 ` Andreas Politz
@ 2017-09-24 13:09 ` Clément Pit-Claudel
2017-10-04 8:17 ` Andreas Politz
1 sibling, 1 reply; 110+ messages in thread
From: Clément Pit-Claudel @ 2017-09-24 13:09 UTC (permalink / raw)
To: Eli Zaretskii, Andreas Politz; +Cc: monnier, emacs-devel
On 2017-05-04 16:21, Eli Zaretskii wrote:
>> From: Andreas Politz <politza@hochschule-trier.de>
>> Date: Wed, 03 May 2017 21:20:09 +0200
>> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
>>
>> I stopped working on this, since it wasn't clear where this will be
>> going (among other things). But I'm willing to pick it up again.
>
> Thanks for working on this, Andreas.
I would really like to see overlay performance improvements, and this looked very promising; can we help? :)
Clément.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-09-24 13:09 ` Clément Pit-Claudel
@ 2017-10-04 8:17 ` Andreas Politz
2017-10-04 9:22 ` Eli Zaretskii
0 siblings, 1 reply; 110+ messages in thread
From: Andreas Politz @ 2017-10-04 8:17 UTC (permalink / raw)
To: Clément Pit-Claudel; +Cc: Eli Zaretskii, monnier, emacs-devel
Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
> I would really like to see overlay performance improvements, and this
> looked very promising; can we help? :)
I fixed a couple of bugs in the meantime.
I would like to rebase my branch onto master, write a proper commit
entry and push it to features/noverlay. And then maybe someone finds
the time to take a look at it.
Is that agreeable ?
Andreas
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-10-04 8:17 ` Andreas Politz
@ 2017-10-04 9:22 ` Eli Zaretskii
2017-10-04 20:36 ` Andreas Politz
0 siblings, 1 reply; 110+ messages in thread
From: Eli Zaretskii @ 2017-10-04 9:22 UTC (permalink / raw)
To: Andreas Politz; +Cc: cpitclaudel, monnier, emacs-devel
> From: Andreas Politz <politza@hochschule-trier.de>
> Date: Wed, 04 Oct 2017 10:17:59 +0200
> Cc: Eli Zaretskii <eliz@gnu.org>, monnier@iro.umontreal.ca, emacs-devel@gnu.org
>
> I would like to rebase my branch onto master, write a proper commit
> entry and push it to features/noverlay. And then maybe someone finds
> the time to take a look at it.
>
> Is that agreeable ?
Yes, of course.
Thanks for working on this.
^ permalink raw reply [flat|nested] 110+ messages in thread
* Re: Overlays as an AA-tree
2017-10-04 9:22 ` Eli Zaretskii
@ 2017-10-04 20:36 ` Andreas Politz
0 siblings, 0 replies; 110+ messages in thread
From: Andreas Politz @ 2017-10-04 20:36 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: cpitclaudel, monnier, emacs-devel
Done. Here is an overview of the changes to src.
src/Makefile.in | 1 +
src/alloc.c | 49 +-
src/buffer.c | 1458 ++++++++++++++++---------------------------------------
src/buffer.h | 161 ++++--
src/editfns.c | 56 +--
src/fileio.c | 3 +-
src/fns.c | 7 +-
src/indent.c | 5 +-
src/insdel.c | 12 -
src/intervals.c | 4 +-
src/itree.c | 1138 +++++++++++++++++++++++++++++++++++++++++++
src/itree.h | 88 ++++
src/keyboard.c | 4 +-
src/lisp.h | 19 +-
src/print.c | 12 +-
src/textprop.c | 52 +-
src/window.h | 10 +
src/xdisp.c | 167 ++-----
src/xfaces.c | 17 +-
19 files changed, 1916 insertions(+), 1347 deletions(-)
Andreas
^ permalink raw reply [flat|nested] 110+ messages in thread
end of thread, other threads:[~2017-10-04 20:36 UTC | newest]
Thread overview: 110+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-09-20 10:32 Overlays as an AA-tree Joakim Jalap
2016-09-20 12:14 ` Clément Pit--Claudel
2016-09-20 12:43 ` Lars Ingebrigtsen
2016-09-20 16:19 ` Joakim Jalap
2016-09-20 23:19 ` Richard Stallman
2016-09-20 14:40 ` Eli Zaretskii
2016-09-20 17:13 ` Joakim Jalap
2016-09-21 16:14 ` Eli Zaretskii
2016-09-22 10:35 ` Joakim Jalap
2016-09-22 12:24 ` Stefan Monnier
2016-09-21 14:52 ` Stefan Monnier
2016-09-21 15:58 ` Eli Zaretskii
2016-09-21 16:24 ` Stefan Monnier
2016-09-21 16:43 ` Eli Zaretskii
2016-09-21 18:41 ` Stefan Monnier
2016-09-21 19:28 ` Eli Zaretskii
2016-09-22 10:35 ` Joakim Jalap
2016-09-22 12:17 ` Stefan Monnier
2016-09-22 20:11 ` Joakim Jalap
2016-09-23 1:29 ` Stefan Monnier
2016-09-27 6:26 ` Joakim Jalap
2016-09-27 11:50 ` Stefan Monnier
2016-09-27 14:38 ` Eli Zaretskii
2016-09-27 16:07 ` Joakim Jalap
2016-11-21 17:32 ` Clément Pit--Claudel
2016-11-22 8:09 ` Joakim Jalap
2016-11-22 13:44 ` Stefan Monnier
2016-11-23 6:58 ` Joakim Jalap
2016-11-22 13:44 ` Clément Pit--Claudel
2016-11-22 13:55 ` Evgeny Roubinchtein
2016-11-23 7:16 ` Joakim Jalap
2016-11-23 15:42 ` Eli Zaretskii
2016-11-23 16:06 ` Stefan Monnier
2016-11-24 18:33 ` Evgeny Roubinchtein
2016-11-23 7:13 ` Joakim Jalap
2017-02-03 8:49 ` Andreas Politz
2017-02-03 9:13 ` Eli Zaretskii
2017-02-03 10:24 ` Andreas Politz
2017-02-03 11:33 ` Joakim Jalap
2017-02-03 12:44 ` Andreas Politz
2017-02-03 14:11 ` Joakim Jalap
2017-02-03 15:02 ` Andreas Politz
2017-02-03 15:23 ` Joakim Jalap
2017-02-03 15:54 ` Andreas Politz
2017-02-04 21:22 ` Stefan Monnier
2017-02-04 23:10 ` Andreas Politz
2017-02-06 9:56 ` Joakim Jalap
2017-02-06 11:33 ` Andreas Politz
2017-02-06 15:33 ` Joakim Jalap
2017-02-06 15:46 ` Stefan Monnier
2017-02-06 16:52 ` Joakim Jalap
2017-02-06 17:34 ` Stefan Monnier
2017-02-06 17:32 ` Andreas Politz
2017-02-07 12:35 ` Andreas Politz
2017-02-07 14:46 ` Joakim Jalap
2017-02-07 22:00 ` Andreas Politz
2017-02-08 0:36 ` Andreas Politz
2017-02-08 6:53 ` Joakim Jalap
2017-02-08 7:34 ` Andreas Politz
2017-02-08 8:18 ` Joakim Jalap
2017-02-08 8:44 ` Andreas Politz
2017-02-08 16:34 ` Andreas Politz
2017-02-08 17:38 ` Eli Zaretskii
2017-02-08 13:04 ` Stefan Monnier
2017-02-08 22:27 ` Andreas Politz
2017-02-08 22:34 ` Stefan Monnier
2017-02-09 9:34 ` Andreas Politz
2017-02-09 10:05 ` Joakim Jalap
2017-02-09 10:19 ` Andreas Politz
2017-02-13 3:44 ` Andreas Politz
2017-02-13 6:11 ` Eli Zaretskii
2017-02-13 9:04 ` Andreas Politz
2017-02-13 14:36 ` Eli Zaretskii
2017-02-14 10:07 ` Andreas Politz
2017-02-17 4:58 ` Andreas Politz
2017-02-17 7:12 ` Eli Zaretskii
2017-02-19 22:39 ` Andreas Politz
2017-02-19 23:10 ` Stefan Monnier
2017-02-19 23:44 ` Andreas Politz
2017-02-20 15:34 ` Eli Zaretskii
2017-02-21 6:56 ` Andreas Politz
2017-02-21 15:11 ` Stefan Monnier
2017-02-21 18:26 ` Andreas Politz
2017-02-21 19:18 ` Stefan Monnier
2017-02-21 23:36 ` Andreas Politz
2017-02-24 8:43 ` Andreas Politz
2017-04-08 13:28 ` Clément Pit-Claudel
2017-05-03 19:20 ` Andreas Politz
2017-05-03 19:40 ` Stefan Monnier
2017-05-05 20:39 ` Andreas Politz
2017-05-04 0:54 ` Clément Pit-Claudel
2017-05-05 20:10 ` Andreas Politz
2017-05-05 22:22 ` Clément Pit-Claudel
2017-05-06 8:05 ` Andreas Politz
2017-05-04 14:21 ` Eli Zaretskii
2017-05-05 20:08 ` Andreas Politz
2017-05-05 21:41 ` Eli Zaretskii
2017-09-24 13:09 ` Clément Pit-Claudel
2017-10-04 8:17 ` Andreas Politz
2017-10-04 9:22 ` Eli Zaretskii
2017-10-04 20:36 ` Andreas Politz
2017-02-14 0:45 ` Richard Stallman
2017-02-14 8:32 ` Andreas Politz
2017-02-06 13:51 ` Stefan Monnier
2017-02-06 14:26 ` Andreas Politz
2017-02-06 15:06 ` Stefan Monnier
2017-02-06 15:40 ` Joakim Jalap
2017-02-06 16:24 ` Clément Pit-Claudel
2017-02-03 13:55 ` Stefan Monnier
2017-02-03 15:14 ` Andreas Politz
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).