master 5525bd3932: itree: Make sure a deleted overlay has NULL pointer fields

[Stefan Monnier]

branch: master
commit 5525bd39322a66cf4133a2593d6349e4d75d8b6a
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    itree: Make sure a deleted overlay has NULL pointer fields
    
    * src/buffer.c (delete_all_overlays): Use POST_ORDER to set the node's
    pointers to NULL, as god intended.
    
    * src/itree.c (itree_insert_node): Uncomment the assertion accordingly.
---
 src/buffer.c | 17 +++++++----------
 src/itree.c  | 17 +++++++++++++----
 2 files changed, 20 insertions(+), 14 deletions(-)

diff --git a/src/buffer.c b/src/buffer.c
index 4da5b451d0..d948aaa266 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -937,19 +937,16 @@ delete_all_overlays (struct buffer *b)
   if (! b->overlays)
     return;
 
-  /* FIXME: This loop sets the overlays' `buffer` field to NULL but
-     doesn't set the itree_nodes' `parent`, `left` and `right`
-     fields accordingly.  I believe it's harmless, but a bit untidy since
-     other parts of the code are careful to set those fields to NULL when
-     the overlay is deleted.
-     Of course, we can't set them to NULL from within the iteration
-     because the iterator may need them (tho we could if we added
-     an ITREE_POST_ORDER iteration order).  */
-  ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
+  /* The general rule is that the tree cannot be modified from within
+     ITREE_FOREACH, but here we bend this rule a little because we know
+     that the POST_ORDER iterator will not need to look at `node` again.  */
+  ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, POST_ORDER)
     {
       modify_overlay (b, node->begin, node->end);
-      /* Where are the nodes freed ? --ap */
       XOVERLAY (node->data)->buffer = NULL;
+      node->parent = NULL;
+      node->left = NULL;
+      node->right = NULL;
     }
   itree_clear (b->overlays);
 }
diff --git a/src/itree.c b/src/itree.c
index 7bf3b9507b..abd060d6fb 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -676,10 +676,8 @@ static void
 itree_insert_node (struct itree_tree *tree, struct itree_node *node)
 {
   eassert (node && node->begin <= node->end);
-  /* FIXME: The assertion below fails because `delete_all_overlays`
-     doesn't set left/right/parent to NULL.  */
-  /* eassert (node->left == NULL && node->right == NULL
-            && node->parent == NULL) */;
+  eassert (node->left == NULL && node->right == NULL
+          && node->parent == NULL);
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
   struct itree_node *parent = NULL;
@@ -1224,6 +1222,11 @@ static struct itree_node *
 itree_iter_next_in_subtree (struct itree_node *node,
                             struct itree_iterator *iter)
 {
+  /* FIXME: Like in the previous version of the iterator, we
+     prune based on `limit` only when moving to a left child,
+     but `limit` can also get smaller when moving to a right child
+     It's actually fairly common, so maybe it would be worthwhile
+     to prune a bit more aggressively here.  */
   struct itree_node *next;
   switch (iter->order)
     {
@@ -1386,6 +1389,12 @@ itree_iterator_start (struct itree_iterator *iter,
   iter->end = end;
   iter->otick = tree->otick;
   iter->order = order;
+  /* Beware: the `node` field alwyas holds "the next" node to consider.
+     so it's always "one node ahead" of what the iterator loop sees.
+     In most respects this makes no difference, but we depend on this
+     detail in `delete_all_overlays` where this allows us to modify
+     the current node knowing that the iterator will not need it to
+     find the next.  */
   iter->node = itree_iterator_first_node (tree, iter);
   return iter;
 }