scratch/noverlay 091e0f04ff 2/2: itree.c: Get rid of the old iterator code

[Stefan Monnier]

branch: scratch/noverlay
commit 091e0f04ffe494ee4cddb67670f0c495a7c9b691
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    itree.c: Get rid of the old iterator code
    
    Only use the new iterator which relies on a fixed size (and small)
    state in the iterator.
    This makes non-local exits safe within ITREE_FOREACH loops.
    
    * src/itree.c (make_nav, nav_nodeptr, nav_flag, itree_stack_clear)
    (itree_stack_push_flagged): Delete functions.
    (nodeptr_and_flag): Delete type.
    (struct itree_stack): Make the array hold plain pointers instead.
    (itree_stack_push): Inline the former code of `itree_stack_push_flagged`.
    (itree_stack_pop): Change return type.
    (itree_contains): Don't call `ITREE_FOREACH_ABORT` any more.
    (itree_insert_gap): Simplify access to the stack of nodes.
    (itree_delete_gap, itree_insert_gap): Adjust code to new return type of
    `itree_stack_pop`.
    (itree_iterator_finish): Delete function.
    (itree_iterator_start): Don't setup the `stack` field any more.
    (itree_iterator_next): Delete function.
    (itree_iter_next): Rename to `itree_iterator_next` and make it non-static.
    (itree_iterator_narrow): Don't check the `running` flag any more.
    
    * src/itree.h (itree_iterator_finish): Remove declaration.
    (struct itree_iterator): Remove the `stack` and `running` fields.
    (ITREE_FOREACH_ABORT): Delete macro.
    (ITREE_FOREACH): Don't call `itree_iterator_finish` any more.
    
    * src/xdisp.c (strings_with_newlines):
    * src/buffer.c (overlays_in, next_overlay_change, overlay_touches_p):
    Don't call `ITREE_FOREACH_ABORT` any more.
---
 src/buffer.c |  12 +---
 src/itree.c  | 199 +++++------------------------------------------------------
 src/itree.h  |  16 +----
 src/xdisp.c  |  10 +--
 4 files changed, 23 insertions(+), 214 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 9be2c4a970..4da5b451d0 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -2985,17 +2985,13 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
       if (node->begin > end)
         {
           next = min (next, node->begin);
-          ITREE_FOREACH_ABORT ();
           break;
         }
       else if (node->begin == end)
         {
           next = node->begin;
           if ((! empty || end < ZV) && beg < end)
-            {
-              ITREE_FOREACH_ABORT ();
-              break;
-            }
+            break;
           if (empty && node->begin != node->end)
             continue;
         }
@@ -3050,7 +3046,6 @@ next_overlay_change (ptrdiff_t pos)
              of pos, because the search is limited to [pos,next) . */
           eassert (node->begin < next);
           next = node->begin;
-          ITREE_FOREACH_ABORT ();
           break;
         }
       else if (node->begin < node->end && node->end < next)
@@ -3155,10 +3150,7 @@ overlay_touches_p (ptrdiff_t pos)
      pos. */
   ITREE_FOREACH (node, current_buffer->overlays, pos - 1, pos + 1, DESCENDING)
     if (node->begin == pos || node->end == pos)
-      {
-        ITREE_FOREACH_ABORT ();
-        return true;
-      }
+      return true;
   return false;
 }
 
diff --git a/src/itree.c b/src/itree.c
index 9e60071980..e4d5fb304b 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -131,33 +131,10 @@ along with GNU Emacs.  If not, see 
<http://www.gnu.org/licenses/>.  */
  * | Stack
  * +=======================================================================+ */
 
-typedef uintptr_t nodeptr_and_flag;
-
-static inline nodeptr_and_flag
-make_nav (struct itree_node *ptr, bool flag)
-{
-  uintptr_t v = (uintptr_t) ptr;
-  /* We assume alignment imposes the LSB is clear for us to use it.  */
-  eassert (!(v & 1));
-  return v | !!flag;
-}
-
-static inline struct itree_node *
-nav_nodeptr (nodeptr_and_flag nav)
-{
-  return (struct itree_node *) (nav & (~(uintptr_t)1));
-}
-
-static inline bool
-nav_flag (nodeptr_and_flag nav)
-{
-  return (bool) (nav & 1);
-}
-
 /* Simple dynamic array. */
 struct itree_stack
 {
-  nodeptr_and_flag *nodes;
+  struct itree_node **nodes;
   size_t size;
   size_t length;
 };
@@ -184,12 +161,6 @@ itree_stack_destroy (struct itree_stack *stack)
   xfree (stack);
 }
 
-static void
-itree_stack_clear (struct itree_stack *stack)
-{
-  stack->length = 0;
-}
-
 static inline void
 itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements)
 {
@@ -204,34 +175,20 @@ itree_stack_ensure_space (struct itree_stack *stack, 
uintmax_t nelements)
 /* Push NODE on the STACK, while settings its visited flag to FLAG. */
 
 static inline void
-itree_stack_push_flagged (struct itree_stack *stack,
-                            struct itree_node *node, bool flag)
+itree_stack_push (struct itree_stack *stack, struct itree_node *node)
 {
   eassert (node);
-
-  /* FIXME: While the stack used in the iterator is bounded by the tree
-     depth and could be easily pre-allocated to a large enough size to avoid
-     this "ensure" check, `itree_stack_push` is also used elsewhere to
-     simply collect some subset of the overlays, where it's only bounded by
-     the total number of overlays in the buffer (which can be large and thus
-     preferably not pre-allocated needlessly).  */
   itree_stack_ensure_space (stack, stack->length + 1);
 
-  stack->nodes[stack->length] = make_nav (node, flag);
+  stack->nodes[stack->length] = node;
   stack->length++;
 }
 
-static inline void
-itree_stack_push (struct itree_stack *stack, struct itree_node *node)
-{
-  itree_stack_push_flagged (stack, node, false);
-}
-
-static inline nodeptr_and_flag
+static inline struct itree_node *
 itree_stack_pop (struct itree_stack *stack)
 {
   if (stack->length == 0)
-    return make_nav (NULL, false);
+    return NULL;
   return stack->nodes[--stack->length];
 }
 
@@ -815,10 +772,7 @@ itree_contains (struct itree_tree *tree, struct itree_node 
*node)
   struct itree_node *other;
   ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING)
     if (other == node)
-      {
-       ITREE_FOREACH_ABORT ();
-       return true;
-      }
+      return true;
 
   return false;
 }
@@ -1122,7 +1076,7 @@ itree_insert_gap (struct itree_tree *tree,
        }
     }
   for (size_t i = 0; i < saved->length; ++i)
-    itree_remove (tree, nav_nodeptr (saved->nodes[i]));
+    itree_remove (tree, saved->nodes[i]);
 
   /* We can't use an iterator here, because we can't effectively
      narrow AND shift some subtree at the same time.  */
@@ -1131,9 +1085,7 @@ itree_insert_gap (struct itree_tree *tree,
       const int size = itree_max_height (tree) + 1;
       struct itree_stack *stack = itree_stack_create (size);
       itree_stack_push (stack, tree->root);
-      nodeptr_and_flag nav;
-      while ((nav = itree_stack_pop (stack),
-             node = nav_nodeptr (nav)))
+      while ((node = itree_stack_pop (stack)))
        {
          /* Process in pre-order. */
          itree_inherit_offset (tree->otick, node);
@@ -1170,9 +1122,7 @@ itree_insert_gap (struct itree_tree *tree,
 
   /* Reinsert nodes starting at POS having front-advance.  */
   uintmax_t notick = tree->otick;
-  nodeptr_and_flag nav;
-  while ((nav = itree_stack_pop (saved),
-         node = nav_nodeptr (nav)))
+  while ((node = itree_stack_pop (saved)))
     {
       eassert (node->otick == ootick);
       eassert (node->begin == pos);
@@ -1205,10 +1155,8 @@ itree_delete_gap (struct itree_tree *tree,
   struct itree_node *node;
 
   itree_stack_push (stack, tree->root);
-  nodeptr_and_flag nav;
-  while ((nav = itree_stack_pop (stack)))
+  while ((node = itree_stack_pop (stack)))
     {
-      node = nav_nodeptr (nav);
       itree_inherit_offset (tree->otick, node);
       if (pos > node->limit)
        continue;
@@ -1244,16 +1192,6 @@ itree_delete_gap (struct itree_tree *tree,
  * | Iterator
  * +=======================================================================+ */
 
-/* Stop using the iterator. */
-
-void
-itree_iterator_finish (struct itree_iterator *iter)
-{
-  eassert (iter && iter->running);
-  itree_stack_destroy (iter->stack);
-  iter->running = false;
-}
-
 /* Return true, if NODE's interval intersects with [BEGIN, END).
    Note: We always include empty nodes at BEGIN (and not at END),
    but if BEGIN==END, then we don't include non-empty nodes starting
@@ -1436,7 +1374,7 @@ itree_iterator_first_node (struct itree_tree *tree,
 }
 
 /* Start a iterator enumerating all intervals in [BEGIN,END) in the
-   given ORDER.  Only one iterator per tree can be running at any time.  */
+   given ORDER.  */
 
 struct itree_iterator *
 itree_iterator_start (struct itree_iterator *iter,
@@ -1444,133 +1382,28 @@ itree_iterator_start (struct itree_iterator *iter,
                      ptrdiff_t begin, ptrdiff_t end, enum itree_order order)
 {
   eassert (iter);
-  /* eassert (!iter->running); */
-  /* 19 here just avoids starting with a silly-small stack.
-     FIXME: Since this stack only needs to be about 2*max_depth
-     in the worst case, we could completely pre-allocate it to something
-     like word-bit-size * 2 and then never worry about growing it.  */
-  const int size = (tree ? itree_max_height (tree) : 19) + 1;
-  iter->stack = itree_stack_create (size);
-  uintmax_t otick= tree->otick;
   iter->begin = begin;
   iter->end = end;
-  iter->otick = otick;
+  iter->otick = tree->otick;
   iter->order = order;
-  itree_stack_clear (iter->stack);
-  if (begin <= end && tree->root != NULL)
-    itree_stack_push_flagged (iter->stack, tree->root, false);
-  iter->running = true;
-  /* itree_stack_ensure_space (iter->stack,
-                              2 * itree_max_height (tree)); */
   iter->node = itree_iterator_first_node (tree, iter);
   return iter;
 }
 
-static struct itree_node *
-itree_iter_next (struct itree_iterator *iter)
+struct itree_node *
+itree_iterator_next (struct itree_iterator *iter)
 {
   struct itree_node *node = iter->node;
   while (node
          && !itree_node_intersects (node, iter->begin, iter->end))
     {
       node = itree_iter_next_in_subtree (node, iter);
+      eassert (itree_limit_is_stable (node));
     }
   iter->node = node ? itree_iter_next_in_subtree (node, iter) : NULL;
   return node;
 }
 
-/* Return the next node of the iterator in the order given when it was
-   started; or NULL if there are no more nodes. */
-
-struct itree_node *
-itree_iterator_next (struct itree_iterator *g)
-{
-  eassert (g && g->running);
-
-  struct itree_node *const null = NULL;
-  struct itree_node *node;
-
-  /* The `visited` flag stored in each node is used here (and only here):
-     We keep a "workstack" of nodes we need to consider.  This stack
-     consist of nodes of two types: nodes that we have decided
-     should be returned by the iterator, and nodes which we may
-     need to consider (including checking their children).
-     We start an iteration with a stack containing just the root
-     node marked as "not visited" which means that it (and its children)
-     needs to be considered but we haven't yet decided whether it's included
-     in the iterator's output.  */
-
-  do
-    {
-      nodeptr_and_flag nav;
-      bool visited;
-      while ((nav = itree_stack_pop (g->stack),
-             node = nav_nodeptr (nav),
-             visited = nav_flag (nav),
-             node && !visited))
-       {
-         struct itree_node *const left = node->left;
-         struct itree_node *const right = node->right;
-
-         itree_inherit_offset (g->otick, node);
-         eassert (itree_limit_is_stable (node));
-         switch (g->order)
-           {
-           case ITREE_ASCENDING:
-             if (right != null && node->begin <= g->end)
-               itree_stack_push_flagged (g->stack, right, false);
-             if (itree_node_intersects (node, g->begin, g->end))
-               itree_stack_push_flagged (g->stack, node, true);
-             /* Node's children may still be off-set and we need to add it.  */
-             if (left != null && g->begin <= left->limit + left->offset)
-               itree_stack_push_flagged (g->stack, left, false);
-             break;
-           case ITREE_DESCENDING:
-             if (left != null && g->begin <= left->limit + left->offset)
-               itree_stack_push_flagged (g->stack, left, false);
-             if (itree_node_intersects (node, g->begin, g->end))
-               itree_stack_push_flagged (g->stack, node, true);
-             if (right != null && node->begin <= g->end)
-               itree_stack_push_flagged (g->stack, right, false);
-             break;
-           case ITREE_PRE_ORDER:
-             if (right != null && node->begin <= g->end)
-               itree_stack_push_flagged (g->stack, right, false);
-             if (left != null && g->begin <= left->limit + left->offset)
-               itree_stack_push_flagged (g->stack, left, false);
-             if (itree_node_intersects (node, g->begin, g->end))
-               itree_stack_push_flagged (g->stack, node, true);
-             break;
-           case ITREE_POST_ORDER:
-             if (itree_node_intersects (node, g->begin, g->end))
-               itree_stack_push_flagged (g->stack, node, true);
-             if (right != null && node->begin <= g->end)
-               itree_stack_push_flagged (g->stack, right, false);
-             if (left != null && g->begin <= left->limit + left->offset)
-               itree_stack_push_flagged (g->stack, left, false);
-             break;
-           }
-       }
-      /* Node may have been invalidated by itree_iterator_narrow
-        after it was pushed: Check if it still intersects. */
-    } while (node && ! itree_node_intersects (node, g->begin, g->end));
-
-  struct itree_node *old_node = g->node;
-  struct itree_node *other_node = itree_iter_next (g);
-  if (other_node != node)
-    {
-      fprintf (stderr, "WOW!! %ld..%ld vs %ld..%ld\n",
-               other_node ? other_node->begin : -1,
-               other_node ? other_node->end : -1,
-               node ? node->begin : -1,
-               node ? node->end : -1);
-      fprintf (stderr, "ON=%lx N=%lx OlN=%lx\n", other_node, node,
-               old_node);
-      emacs_abort ();
-    }
-  return node;
-}
-
 /* Limit G to the new interval [BEGIN, END), which must be a subset of
    the current one.  I.E. it can't grow on either side. */
 
@@ -1578,7 +1411,7 @@ void
 itree_iterator_narrow (struct itree_iterator *g,
                       ptrdiff_t begin, ptrdiff_t end)
 {
-  eassert (g && g->running);
+  eassert (g);
   eassert (begin >= g->begin);
   eassert (end <= g->end);
   g->begin = max (begin, g->begin);
diff --git a/src/itree.h b/src/itree.h
index 37cd423d34..291fa53fd3 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -132,24 +132,21 @@ extern struct itree_iterator *itree_iterator_start 
(struct itree_iterator *,
                                                    enum itree_order);
 extern void itree_iterator_narrow (struct itree_iterator *, ptrdiff_t,
                                   ptrdiff_t);
-extern void itree_iterator_finish (struct itree_iterator *);
 extern struct itree_node *itree_iterator_next (struct itree_iterator *);
 
 /* State used when iterating interval. */
 struct itree_iterator
   {
-    struct itree_node *node; /* FIXME: It should be either `node` or `stack`. 
*/
-    struct itree_stack *stack;
+    struct itree_node *node;
     ptrdiff_t begin;
     ptrdiff_t end;
     uintmax_t otick;    /* A copy of the tree's `otick`.  */
     enum itree_order order;
-    bool running;
   };
 
 /* Iterate over the intervals between BEG and END in the tree T.
    N will hold successive nodes.  ORDER can be one of : `ASCENDING`,
-   `DESCENDING`, or `PRE_ORDER`.
+   `DESCENDING`, `POST_ORDER`, or `PRE_ORDER`.
    It should be used as:
 
       ITREE_FOREACH (n, t, beg, end, order)
@@ -160,9 +157,6 @@ struct itree_iterator
    BEWARE:
    - The expression T may be evaluated more than once, so make sure
      it is cheap and pure.
-   - If you need to exit the loop early, you *have* to call `ITREE_ABORT`
-     just before exiting (e.g. with `break` or `return`).
-   - Non-local exits are not supported within the body of the loop.
    - Don't modify the tree during the iteration.
  */
 #define ITREE_FOREACH(n, t, beg, end, order)                        \
@@ -179,11 +173,7 @@ struct itree_iterator
                                *itree_iter_                      \
             = itree_iterator_start (&itree_local_iter_,          \
                                     t, beg, end, ITREE_##order); \
-          ((n = itree_iterator_next (itree_iter_))               \
-           || (itree_iterator_finish (itree_iter_), false));)
-
-#define ITREE_FOREACH_ABORT() \
-  itree_iterator_finish (itree_iter_)
+          ((n = itree_iterator_next (itree_iter_)));)
 
 #define ITREE_FOREACH_NARROW(beg, end) \
   itree_iterator_narrow (itree_iter_, beg, end)
diff --git a/src/xdisp.c b/src/xdisp.c
index f6a279636a..414ee9bfe2 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -7036,17 +7036,11 @@ strings_with_newlines (ptrdiff_t startpos, ptrdiff_t 
endpos, struct window *w)
       str = Foverlay_get (overlay, Qbefore_string);
       if (STRINGP (str) && SCHARS (str)
          && memchr (SDATA (str), '\n', SBYTES (str)))
-       {
-         ITREE_FOREACH_ABORT ();
-         return true;
-       }
+       return true;
       str = Foverlay_get (overlay, Qafter_string);
       if (STRINGP (str) && SCHARS (str)
          && memchr (SDATA (str), '\n', SBYTES (str)))
-       {
-         ITREE_FOREACH_ABORT ();
-         return true;
-       }
+       return true;
     }
 
   /* Check for 'display' properties whose values include strings.  */