bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful

[Andreas Politz <mail@andreas-politz.de>]

[-- Attachment #1: Type: text/plain, Size: 450 bytes --]

I've managed to construct a prototype of this "stateless" iterator.

I've only implemented the in-order case and only applied it in the overlays_in function.

The only real trouble I had was with pushing the offset to the children
during the tree navigation in some kind of sensible way.  In the end I
gave up and simply pasted calls to the corresponding function "all over
the place".  It seems to work, at least buffer-tests are passing.

Andreas


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: noverlay-stateless-iterator.diff --]
[-- Type: text/x-patch, Size: 6871 bytes --]

diff --git a/src/buffer.c b/src/buffer.c
index f59fddcbde..6a53b49aad 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -2948,15 +2948,16 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
   ptrdiff_t next = ZV;
   Lisp_Object *vec = *vec_ptr;
   struct interval_node *node;
+  struct interval_tree_iterator iterator;
 
-  ITREE_FOREACH (node, current_buffer->overlays, beg,
-                 /* Find empty OV at Z ? */
-                 (end >= ZV && empty) ? ZV + 1 : ZV, ASCENDING)
+  interval_tree_iterator_init(&iterator, current_buffer->overlays, beg,
+			      (end >= ZV && empty) ? ZV + 1 : ZV, ITREE_ASCENDING);
+
+  while ((node = interval_tree_iterator_next(&iterator)))
     {
       if (node->begin > end)
         {
           next = min (next, node->begin);
-          ITREE_FOREACH_ABORT ();
           break;
         }
       else if (node->begin == end)
@@ -2964,7 +2965,6 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
           next = node->begin;
           if ((! empty || end < ZV) && beg < end)
             {
-              ITREE_FOREACH_ABORT ();
               break;
             }
         }
diff --git a/src/itree.c b/src/itree.c
index eeecaf1839..21549fe8a7 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1190,3 +1190,132 @@ interval_tree_subtree_min (const struct interval_tree *tree, struct interval_nod
  * +===================================================================================+ */
 
 /* See Foverlay_tree in buffer.c */
+
+\f
+/* +===================================================================================+
+ * | Stateless iterator
+ * +===================================================================================+ */
+
+static bool
+interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator,
+                              struct interval_node *node);
+static
+struct interval_node *
+interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator);
+
+void
+interval_tree_iterator_init(struct interval_tree_iterator *iterator,
+                            struct interval_tree *tree,
+                            ptrdiff_t begin,
+                            ptrdiff_t end,
+                            enum interval_tree_order order) {
+  iterator->tree = tree;
+  iterator->node = tree && begin <= end ? ITREE_NULL : NULL;
+  iterator->begin = begin;
+  iterator->end = end;
+  iterator->order = order;
+}
+
+struct interval_node *
+interval_tree_iterator_next(struct interval_tree_iterator *iterator) {
+  if (iterator->node) {
+    do {
+      switch (iterator->order) {
+      case ITREE_ASCENDING:
+        iterator->node = interval_tree_iterator_in_order_successor (iterator);
+        break;
+      default:
+        fprintf (stderr, "interval_tree_order != ITREE_ASCENDING not implemented");
+        emacs_abort ();
+      }
+    } while (iterator->node &&
+             ! interval_node_intersects (iterator->node, iterator->begin, iterator->end));
+  }
+
+  if (iterator->node == ITREE_NULL) {
+    fprintf (stderr, "Next node: ITREE_NULL\n");
+  } else if (! iterator->node) {
+    fprintf (stderr, "Next node: NULL\n");
+  } else {
+    fprintf (stderr, "Next node: begin = %ld, end = %ld (iterator: begin = %ld, end = %ld)\n",
+             iterator->node->begin, iterator->node->end, iterator->begin, iterator->end);
+  }
+  return iterator->node;
+}
+
+static bool
+interval_tree_iter_traverse_p(struct interval_tree_iterator *iterator,
+                              struct interval_node *node) {
+  eassert (node);
+
+  if (node == ITREE_NULL) {
+    return false;
+  } else {
+    eassert (node->parent != ITREE_NULL);
+    if (node->parent->left == node) {
+      return iterator->begin <= node->limit + node->offset;
+    } else {
+      return node->parent->begin <= iterator->end;
+    }
+  }
+}
+
+static
+struct interval_node *
+interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator)
+{
+  struct interval_node *node = iterator->node;
+
+  if (node != ITREE_NULL) {
+    interval_tree_inherit_offset (iterator->tree, node);
+  }
+
+  if (node == ITREE_NULL) {
+    node = iterator->tree->root;
+    if (node != ITREE_NULL) {
+      interval_tree_inherit_offset (iterator->tree, node);
+    }
+    while (interval_tree_iter_traverse_p(iterator, node->left)) {
+      node = node->left;
+      if (node != ITREE_NULL) {
+        interval_tree_inherit_offset (iterator->tree, node);
+      }
+    }
+  } else if (interval_tree_iter_traverse_p(iterator, node->right))
+    {
+      node = node->right;
+      if (node != ITREE_NULL) {
+        interval_tree_inherit_offset (iterator->tree, node);
+      }
+      while (interval_tree_iter_traverse_p(iterator, node->left)) {
+        node = node->left;
+        if (node != ITREE_NULL) {
+          interval_tree_inherit_offset (iterator->tree, node);
+        }
+      }
+    }
+  else
+    {
+      struct interval_node *parent = node->parent;
+      while (node == parent->right)
+        {
+          node = parent;
+          parent = parent->parent;
+        }
+      if (node != ITREE_NULL)
+        node = parent;
+    }
+
+  return node == ITREE_NULL ? NULL : node;
+}
+
+void
+interval_tree_iterator_narrow (struct interval_tree_iterator *iterator,
+                               ptrdiff_t begin,
+                               ptrdiff_t end)
+{
+  eassert (begin >= iterator->begin);
+  eassert (end <= iterator->end);
+  iterator->begin =  max (begin, iterator->begin);
+  iterator->end =  min (end, iterator->end);
+}
diff --git a/src/itree.h b/src/itree.h
index 1f019a2607..53f03cca35 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -72,6 +72,15 @@ #define ITREE_NULL (&itree_null)
   ITREE_PRE_ORDER,
 };
 
+struct interval_tree_iterator
+{
+  struct interval_tree *tree;
+  struct interval_node *node;
+  ptrdiff_t begin;
+  ptrdiff_t end;
+  enum interval_tree_order order;
+};
+
 void interval_node_init (struct interval_node *, ptrdiff_t, ptrdiff_t, bool, bool, Lisp_Object);
 ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *);
 ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *);
@@ -135,4 +144,15 @@ #define ITREE_FOREACH_ABORT() \
 #define ITREE_FOREACH_NARROW(beg, end) \
   interval_generator_narrow (itree_iter_, beg, end)
 
+void interval_tree_nodes (struct interval_tree *tree, struct interval_node **nodes, enum interval_tree_order order);
+
+void interval_tree_iterator_init(struct interval_tree_iterator *iterator,
+				 struct interval_tree *tree,
+				 ptrdiff_t begin,
+				 ptrdiff_t end,
+				 enum interval_tree_order order);
+struct interval_node *interval_tree_iterator_next(struct interval_tree_iterator *iterator);
+void interval_tree_iterator_narrow (struct interval_tree_iterator *iterator,
+			       ptrdiff_t begin,
+			       ptrdiff_t end);
 #endif