scratch/noverlay fb7f1864da 1/2: itree.c: Make the iterator reentrant (bug#59183)

[Stefan Monnier]

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

    itree.c: Make the iterator reentrant (bug#59183)
    
    Get rid of the global iterator object and instead allocate
    a separate iterator for every loop.  This still uses the "duplicate
    iterator" code, including the old iterator which needs a stack,
    make ITREE_FOREACH a bit more expensive than we'd like.
    
    * src/itree.h (init_itree, forget_itree, itree_iterator_busy_p):
    Delete declarations.
    (itree_iterator_start): Add iterator arg and remove `line` and `file` args.
    (struct itree_iterator): Move from `itree.c`.  Remove `line` and
    `file` fields.
    (ITREE_FOREACH): Stack allocate an iterator object and pass it to
    `itree_iterator_start`.
    
    * src/itree.c (struct itree_iterator): Move to itree.h.
    (iter): Delete global variable.
    (itree_iterator_create, init_itree, forget_itree, itree_iterator_busy_p):
    Delete functions.
    (itree_contains): Adjust assertion.
    (itree_iterator_finish): Deallocate the iterator's stack.
    (itree_iterator_start): Take the (uninitialized) iterator as argument.
    Allocate a fresh new stack.  Remove `file` and `line` arguments.
    Don't check `running` any more since the iterator is not expected to be
    initialized at all.
    
    * src/eval.c (signal_or_quit):
    * src/alloc.c (garbage_collect): Don't check `itree_iterator_busy_p`
    any more.
    
    * src/emacs.c (main): No need to `init_itree` any more.
    (Fdump_emacs): No need to `forget_itree` any more.
---
 src/alloc.c |  5 ----
 src/emacs.c |  3 --
 src/eval.c  |  1 -
 src/itree.c | 91 ++++++++-----------------------------------------------------
 src/itree.h | 46 +++++++++++++++++--------------
 5 files changed, 37 insertions(+), 109 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 6862cf916f..b9d12dff7e 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6279,11 +6279,6 @@ garbage_collect (void)
   image_prune_animation_caches (false);
 #endif
 
-  /* ELisp code run by `gc-post-hook' could result in itree iteration,
-     which must not happen while the itree is already busy.  See
-     bug#58639.  */
-  eassert (!itree_iterator_busy_p ());
-
   if (!NILP (Vpost_gc_hook))
     {
       specpdl_ref gc_count = inhibit_garbage_collection ();
diff --git a/src/emacs.c b/src/emacs.c
index c4c8bfc82f..85102acd28 100644
--- a/src/emacs.c
+++ b/src/emacs.c
@@ -1932,7 +1932,6 @@ Using an Emacs configured with --with-x-toolkit=lucid 
does not have this problem
   running_asynch_code = 0;
   init_random ();
   init_xfaces ();
-  init_itree ();
 
 #if defined HAVE_JSON && !defined WINDOWSNT
   init_json ();
@@ -3105,8 +3104,6 @@ You must run Emacs in batch mode in order to dump it.  */)
   gflags.will_dump_with_unexec_ = false;
   gflags.dumped_with_unexec_ = true;
 
-  forget_itree ();
-
   alloc_unexec_pre ();
 
   unexec (SSDATA (filename), !NILP (symfile) ? SSDATA (symfile) : 0);
diff --git a/src/eval.c b/src/eval.c
index ea23829948..78e606267f 100644
--- a/src/eval.c
+++ b/src/eval.c
@@ -1716,7 +1716,6 @@ signal_or_quit (Lisp_Object error_symbol, Lisp_Object 
data, bool keyboard_quit)
   Lisp_Object clause = Qnil;
   struct handler *h;
 
-  eassert (!itree_iterator_busy_p ());
   if (gc_in_progress || waiting_for_input)
     emacs_abort ();
 
diff --git a/src/itree.c b/src/itree.c
index 4f25a924b4..9e60071980 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -238,72 +238,12 @@ itree_stack_pop (struct itree_stack *stack)
 
 /* +-----------------------------------------------------------------------+ */
 
-/* State used when iterating interval. */
-struct itree_iterator
-{
-  struct itree_stack *stack;
-  struct itree_node *node;
-  ptrdiff_t begin;
-  ptrdiff_t end;
-
-  /* A copy of the tree's `otick`.  */
-  uintmax_t otick;
-  enum itree_order order;
-  bool running;
-  const char *file;
-  int line;
-};
-
-/* Ideally, every iteration would use its own `iter` object, so we could
-   have several iterations active at the same time.  In practice, iterations
-   are limited by the fact we don't allow modifying the tree at the same
-   time, making the use of nested iterations quite rare anyway.
-   So we just use a single global iterator instead for now.  */
-static struct itree_iterator *iter = NULL;
-
 static int
 itree_max_height (const struct itree_tree *tree)
 {
   return 2 * log (tree->size + 1) / log (2) + 0.5;
 }
 
-/* Allocate a new iterator for TREE. */
-
-static struct itree_iterator *
-itree_iterator_create (struct itree_tree *tree)
-{
-  struct itree_iterator *g = xmalloc (sizeof *g);
-  /* 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;
-
-  g->stack = itree_stack_create (size);
-  g->node = NULL;
-  g->running = false;
-  g->begin = 0;
-  g->end = 0;
-  g->file = NULL;
-  g->line = 0;
-  return g;
-}
-
-void
-init_itree (void)
-{
-  eassert (!iter);
-  iter = itree_iterator_create (NULL);
-}
-
-#ifdef HAVE_UNEXEC
-void
-forget_itree (void)
-{
-  iter = NULL;
-}
-#endif
-
 struct check_subtree_result
 {
   /* Node count of the tree.  */
@@ -871,7 +811,7 @@ itree_node_set_region (struct itree_tree *tree,
 static bool
 itree_contains (struct itree_tree *tree, struct itree_node *node)
 {
-  eassert (iter && node);
+  eassert (node);
   struct itree_node *other;
   ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING)
     if (other == node)
@@ -1304,18 +1244,13 @@ itree_delete_gap (struct itree_tree *tree,
  * | Iterator
  * +=======================================================================+ */
 
-bool
-itree_iterator_busy_p (void)
-{
-  return (iter && iter->running);
-}
-
 /* Stop using the iterator. */
 
 void
 itree_iterator_finish (struct itree_iterator *iter)
 {
   eassert (iter && iter->running);
+  itree_stack_destroy (iter->stack);
   iter->running = false;
 }
 
@@ -1504,18 +1439,18 @@ itree_iterator_first_node (struct itree_tree *tree,
    given ORDER.  Only one iterator per tree can be running at any time.  */
 
 struct itree_iterator *
-itree_iterator_start (struct itree_tree *tree, ptrdiff_t begin,
-                     ptrdiff_t end, enum itree_order order,
-                     const char *file, int line)
+itree_iterator_start (struct itree_iterator *iter,
+                     struct itree_tree *tree,
+                     ptrdiff_t begin, ptrdiff_t end, enum itree_order order)
 {
   eassert (iter);
-  if (iter->running)
-    {
-      fprintf (stderr,
-              "Detected nested iteration!\nOuter: %s:%d\nInner: %s:%d\n",
-              iter->file, iter->line, file, line);
-      emacs_abort ();
-    }
+  /* 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;
@@ -1524,8 +1459,6 @@ itree_iterator_start (struct itree_tree *tree, ptrdiff_t 
begin,
   itree_stack_clear (iter->stack);
   if (begin <= end && tree->root != NULL)
     itree_stack_push_flagged (iter->stack, tree->root, false);
-  iter->file = file;
-  iter->line = line;
   iter->running = true;
   /* itree_stack_ensure_space (iter->stack,
                               2 * itree_max_height (tree)); */
diff --git a/src/itree.h b/src/itree.h
index dc44823322..37cd423d34 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -107,10 +107,6 @@ enum itree_order
     ITREE_POST_ORDER,
   };
 
-extern void init_itree (void);
-#ifdef HAVE_UNEXEC
-extern void forget_itree (void);
-#endif
 extern void itree_node_init (struct itree_node *, bool, bool, Lisp_Object);
 extern ptrdiff_t itree_node_begin (struct itree_tree *, struct itree_node *);
 extern ptrdiff_t itree_node_end (struct itree_tree *, struct itree_node *);
@@ -129,17 +125,28 @@ extern void itree_delete_gap (struct itree_tree *, 
ptrdiff_t, ptrdiff_t);
 
 /* Iteration functions.  Almost all code should use ITREE_FOREACH
    instead.  */
-extern bool itree_iterator_busy_p (void);
-extern struct itree_iterator *itree_iterator_start (struct itree_tree *,
+extern struct itree_iterator *itree_iterator_start (struct itree_iterator *,
+                                                   struct itree_tree *,
                                                    ptrdiff_t,
                                                    ptrdiff_t,
-                                                   enum itree_order,
-                                                   const char *, int);
+                                                   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;
+    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`.
@@ -153,29 +160,26 @@ extern struct itree_node *itree_iterator_next (struct 
itree_iterator *);
    BEWARE:
    - The expression T may be evaluated more than once, so make sure
      it is cheap and pure.
-   - Only a single iteration can happen at a time, so make sure none of the
-     code within the loop can start another tree iteration, i.e. it shouldn't
-     be able to run ELisp code, nor GC since GC can run ELisp by way
-     of `post-gc-hook`.
    - 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)                        \
-  /* FIXME: We'd want to declare `x` right here, but I can't figure out
+  /* FIXME: We'd want to declare `n` right here, but I can't figure out
      how to make that work here: the `for` syntax only allows a single
      clause for the var declarations where we need 2 different types.
      We could use the `struct {foo x; bar y; } p;` trick to declare two
      vars `p.x` and `p.y` of unrelated types, but then none of the names
-     of the vars matches the `n` we receive :-(.  */                \
-  if (!t)                                                           \
-    { }                                                             \
-  else                                                              \
-    for (struct itree_iterator *itree_iter_                         \
-            = itree_iterator_start (t, beg, end, ITREE_##order,     \
-                                        __FILE__, __LINE__);        \
-          ((n = itree_iterator_next (itree_iter_))                  \
+     of the vars matches the `n` we receive :-(.  */             \
+  if (!t)                                                        \
+    { }                                                          \
+  else                                                           \
+    for (struct itree_iterator itree_local_iter_,                \
+                               *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() \