feature/noverlay ea8daec9bb: itree.[ch]: Add sanity checks, comments, and minor tweaks

[Stefan Monnier]

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

    itree.[ch]: Add sanity checks, comments, and minor tweaks
    
    * src/alloc.c (mark_overlay): Add sanity check.
    
    * src/buffer.c (next_overlay_change, previous_overlay_change):
    Tweak code to keep the same vars for the bounds.
    
    * src/itree.c (interval_tree_clear, interval_tree_insert)
    (interval_tree_remove, interval_tree_insert_fix, interval_tree_remove_fix):
    Adjust to the `color` -> `red` change.
    (interval_tree_clear): Prefer `true/false` for booleans.
    (interval_generator_create): Use an actual `interval_tree_order` value
    rather than 0.
    (interval_generator_next): Simplify a tiny bit.  Add comment.
    (interval_generator_narrow): Add sanity check.
    
    * src/itree.h (struct interval_node): Replace `color` field with
    boolean `red` field.
    (enum interval_tree_order): Remove unused `ITREE_DEFLT_ORDER` value.
    
    * src/pdumper.c (dump_interval_node): Adjust to the
    `color` -> `red` change.
---
 src/alloc.c   |   3 ++
 src/buffer.c  |   4 +-
 src/itree.c   | 134 +++++++++++++++++++++++++++++++++++-----------------------
 src/itree.h   |   7 ++-
 src/pdumper.c |   2 +-
 5 files changed, 89 insertions(+), 61 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 20b8981bd6..be55dcf8df 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -6505,6 +6505,9 @@ mark_char_table (struct Lisp_Vector *ptr, enum pvec_type 
pvectype)
 static void
 mark_overlay (struct Lisp_Overlay *ov)
 {
+  /* We don't mark the `interval_node` object, because it is managed manually
+     rather than by the GC.  */
+  eassert (BASE_EQ (ov->interval->data, make_lisp_ptr (ov, Lisp_Vectorlike)));
   set_vectorlike_marked (&ov->header);
   mark_object (ov->plist);
 }
diff --git a/src/buffer.c b/src/buffer.c
index 2b1997fc8b..879e14be96 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -2992,7 +2992,7 @@ next_overlay_change (ptrdiff_t pos)
   ptrdiff_t next = ZV;
   struct interval_node *node;
 
-  buffer_overlay_iter_start (current_buffer, pos, ZV, ITREE_ASCENDING);
+  buffer_overlay_iter_start (current_buffer, pos, next, ITREE_ASCENDING);
   while ((node = buffer_overlay_iter_next (current_buffer)))
     {
       if (node->begin > pos)
@@ -3020,7 +3020,7 @@ previous_overlay_change (ptrdiff_t pos)
   struct interval_node *node;
   ptrdiff_t prev = BEGV;
 
-  buffer_overlay_iter_start (current_buffer, BEGV, pos, ITREE_DESCENDING);
+  buffer_overlay_iter_start (current_buffer, prev, pos, ITREE_DESCENDING);
   while ((node = buffer_overlay_iter_next (current_buffer)))
     {
       if (node->end < pos)
diff --git a/src/itree.c b/src/itree.c
index e31ce39ba1..aa6fcc1bea 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -233,11 +233,11 @@ interval_tree_clear (struct interval_tree *tree)
   null->begin = PTRDIFF_MIN;
   null->end = PTRDIFF_MIN;
   null->limit = PTRDIFF_MIN;     /* => max(x, null.limit) = x */
-  null->color = ITREE_BLACK;
+  null->red = false;
   tree->root = null;
   tree->otick = 1;
   tree->size = 0;
-  tree->iter_running = 0;
+  tree->iter_running = false;
 }
 
 #ifdef ITREE_TESTING
@@ -308,7 +308,7 @@ interval_tree_insert (struct interval_tree *tree, struct 
interval_node *node)
   node->parent = parent;
   node->left = &tree->null;
   node->right = &tree->null;
-  node->color = ITREE_RED;
+  node->red = true;
   node->offset = 0;
   node->begin -= offset;
   node->end -= offset;
@@ -351,7 +351,7 @@ interval_tree_remove (struct interval_tree *tree, struct 
interval_node *node)
     {
       struct interval_node *subst =
         (node->right == &tree->null) ? node->left : node->right;
-      if (node->color == ITREE_BLACK)
+      if (!node->red)
         broken = subst;
       interval_tree_transplant (tree, subst, node);
       interval_tree_propagate_limit (tree, subst);
@@ -361,7 +361,7 @@ interval_tree_remove (struct interval_tree *tree, struct 
interval_node *node)
       struct interval_node *min = interval_tree_subtree_min (tree, 
node->right);
       struct interval_node *min_right = min->right;
 
-      if (min->color == ITREE_BLACK)
+      if (!min->red)
         broken = min->right;
       if (min->parent == node)
         min_right->parent = min; /* set parent, if min_right = null */
@@ -375,7 +375,7 @@ interval_tree_remove (struct interval_tree *tree, struct 
interval_node *node)
       interval_tree_transplant (tree, min, node);
       min->left = node->left;
       min->left->parent = min;
-      min->color = node->color;
+      min->red = node->red;
       interval_tree_propagate_limit (tree, min_right);
       interval_tree_propagate_limit (tree, min);
     }
@@ -440,7 +440,7 @@ interval_tree_iter_start (struct interval_tree *tree,
   if (tree->iter_running)
     emacs_abort ();
   interval_generator_reset (tree->iter, begin, end, order);
-  tree->iter_running = 1;
+  tree->iter_running = true;
   tree->file = file;
   tree->line = line;
 }
@@ -464,7 +464,7 @@ interval_tree_iter_finish (struct interval_tree *tree)
 {
   if (! tree->iter_running)
     emacs_abort ();
-  tree->iter_running = 0;
+  tree->iter_running = false;
 }
 
 /* Return the next node of the iterator in the order given when it was
@@ -637,7 +637,7 @@ interval_generator_create  (struct interval_tree *tree)
 
   g->stack = interval_stack_create (size);
   g->tree = tree;
-  interval_generator_reset (g, 1, 0, 0);
+  interval_generator_reset (g, 1, 0, ITREE_ASCENDING);
   return g;
 }
 
@@ -667,7 +667,13 @@ interval_generator_ensure_space (struct interval_generator 
*g)
   interval_stack_ensure_space (g->stack, interval_tree_max_height (g->tree) + 
1);
 }
 
-/* Return true, if NODE's interval intersects with [BEGIN, END). */
+/* 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
+   at BEGIN or ending at END.  This seems to match the behavior of the
+   old overlays code but it's not clear if it's The Right Thing
+   (e.g. it breaks the expectation that if NODE1 is included, then
+   a NODE2 strictly bigger than NODE1 should also be included).  */
 
 static inline bool
 interval_node_intersects (const struct interval_node *node,
@@ -687,10 +693,29 @@ interval_generator_next (struct interval_generator *g)
   struct interval_node * const null = &g->tree->null;
   struct interval_node *node;
 
-  do {
-    node = interval_stack_pop (g->stack);
+  /* 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 generator, 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 generator's output.  */
+
+  /* FIXME: We should move the `visited` flag to the stack: each entry
+     there should simply consist of a node and a bool (the `visited` status)
+     so this internal implementation detail doesn't leak into the
+     `interval_node` structure.
+     [ In theory it would also allow multiple iterations to be active
+       at the same time, tho that does not seem particularly useful at
+       this time and would require further changes anyway.  ]
+     To save space on the stack, we could hijack the LSB bit of the `node*`
+     word to hold the `visited` bit.  */
 
-    while (node && ! node->visited)
+  do {
+    while ((node = interval_stack_pop (g->stack))
+           && ! node->visited)
       {
         struct interval_node * const left = node->left;
         struct interval_node * const right = node->right;
@@ -724,7 +749,6 @@ interval_generator_next (struct interval_generator *g)
               interval_stack_push_flagged (g->stack, node, true);
             break;
           }
-        node = interval_stack_pop (g->stack);
       }
     /* Node may have been invalidated by interval_generator_narrow
        after it was pushed: Check if it still intersects. */
@@ -740,6 +764,8 @@ static inline void
 interval_generator_narrow (struct interval_generator *g,
                            ptrdiff_t begin, ptrdiff_t end)
 {
+  eassert (begin >= g->begin);
+  eassert (end <= g->end);
   g->begin =  max (begin, g->begin);
   g->end =  min (end, g->end);
 }
@@ -980,7 +1006,7 @@ interval_tree_rotate_right (struct interval_tree *tree, 
struct interval_node *no
 static void
 interval_tree_insert_fix (struct interval_tree *tree, struct interval_node 
*node)
 {
-  while (node->parent->color == ITREE_RED)
+  while (node->parent->red)
     {
       /* NODE is red and its parent is red.  This is a violation of
         red-black tree property #3.  */
@@ -991,14 +1017,14 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
             our "uncle".  */
          struct interval_node *uncle = node->parent->parent->right;
 
-         if (uncle->color == ITREE_RED) /* case 1.a */
+         if (uncle->red) /* case 1.a */
            {
              /* Uncle and parent are red but should be black because
                 NODE is red.  Change the colors accordingly and
                 proceed with the grandparent.  */
-             node->parent->color = ITREE_BLACK;
-             uncle->color = ITREE_BLACK;
-             node->parent->parent->color = ITREE_RED;
+             node->parent->red = false;
+             uncle->red = false;
+             node->parent->parent->red = true;
              node = node->parent->parent;
             }
          else
@@ -1011,8 +1037,8 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
                  interval_tree_rotate_left (tree, node);
                 }
               /* case 3.a */
-             node->parent->color = ITREE_BLACK;
-             node->parent->parent->color = ITREE_RED;
+             node->parent->red = false;
+             node->parent->parent->red = true;
              interval_tree_rotate_right (tree, node->parent->parent);
             }
         }
@@ -1021,11 +1047,11 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
          /* This is the symmetrical case of above.  */
          struct interval_node *uncle = node->parent->parent->left;
 
-         if (uncle->color == ITREE_RED) /* case 1.b */
+         if (uncle->red) /* case 1.b */
            {
-             node->parent->color = ITREE_BLACK;
-             uncle->color = ITREE_BLACK;
-             node->parent->parent->color = ITREE_RED;
+             node->parent->red = false;
+             uncle->red = false;
+             node->parent->parent->red = true;
              node = node->parent->parent;
             }
          else
@@ -1036,8 +1062,8 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
                  interval_tree_rotate_right (tree, node);
                }
               /* case 3.b */
-             node->parent->color = ITREE_BLACK;
-             node->parent->parent->color = ITREE_RED;
+             node->parent->red = false;
+             node->parent->parent->red = true;
              interval_tree_rotate_left (tree, node->parent->parent);
             }
         }
@@ -1045,7 +1071,7 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
 
   /* The root may have been changed to red due to the algorithm.  Set
      it to black so that property #5 is satisfied.  */
-  tree->root->color = ITREE_BLACK;
+  tree->root->red = false;
 }
 
 /* Repair the tree after a deletion.  Part of the RB-Tree
@@ -1054,38 +1080,38 @@ interval_tree_insert_fix (struct interval_tree *tree, 
struct interval_node *node
 static void
 interval_tree_remove_fix (struct interval_tree *tree, struct interval_node 
*node)
 {
-  while (node != tree->root && node->color == ITREE_BLACK)
+  while (node != tree->root && !node->red)
     {
       if (node == node->parent->left)
        {
          struct interval_node *other = node->parent->right;
 
-         if (other->color == ITREE_RED) /* case 1.a */
+         if (other->red) /* case 1.a */
            {
-             other->color = ITREE_BLACK;
-             node->parent->color = ITREE_RED;
+             other->red = false;
+             node->parent->red = true;
              interval_tree_rotate_left (tree, node->parent);
              other = node->parent->right;
             }
 
-         if (other->left->color == ITREE_BLACK /* 2.a */
-              && other->right->color == ITREE_BLACK)
+         if (!other->left->red /* 2.a */
+              && !other->right->red)
            {
-             other->color = ITREE_RED;
+             other->red = true;
              node = node->parent;
             }
          else
            {
-             if (other->right->color == ITREE_BLACK) /* 3.a */
+             if (!other->right->red) /* 3.a */
                {
-                 other->left->color = ITREE_BLACK;
-                 other->color = ITREE_RED;
+                 other->left->red = false;
+                 other->red = true;
                  interval_tree_rotate_right (tree, other);
                  other = node->parent->right;
                 }
-             other->color = node->parent->color; /* 4.a */
-             node->parent->color = ITREE_BLACK;
-             other->right->color = ITREE_BLACK;
+             other->red = node->parent->red; /* 4.a */
+             node->parent->red = false;
+             other->right->red = false;
              interval_tree_rotate_left (tree, node->parent);
              node = tree->root;
             }
@@ -1094,40 +1120,40 @@ interval_tree_remove_fix (struct interval_tree *tree, 
struct interval_node *node
        {
          struct interval_node *other = node->parent->left;
 
-         if (other->color == ITREE_RED) /* 1.b */
+         if (other->red) /* 1.b */
            {
-             other->color = ITREE_BLACK;
-             node->parent->color = ITREE_RED;
+             other->red = false;
+             node->parent->red = true;
              interval_tree_rotate_right (tree, node->parent);
              other = node->parent->left;
             }
 
-         if (other->right->color == ITREE_BLACK /* 2.b */
-              && other->left->color == ITREE_BLACK)
+         if (!other->right->red /* 2.b */
+              && !other->left->red)
            {
-             other->color = ITREE_RED;
+             other->red = true;
              node = node->parent;
             }
          else
            {
-             if (other->left->color == ITREE_BLACK) /* 3.b */
+             if (!other->left->red) /* 3.b */
                {
-                 other->right->color = ITREE_BLACK;
-                 other->color = ITREE_RED;
+                 other->right->red = false;
+                 other->red = true;
                  interval_tree_rotate_left (tree, other);
                  other = node->parent->left;
                 }
 
-             other->color = node->parent->color; /* 4.b */
-             node->parent->color = ITREE_BLACK;
-             other->left->color = ITREE_BLACK;
+             other->red = node->parent->red; /* 4.b */
+             node->parent->red = false;
+             other->left->red = false;
              interval_tree_rotate_right (tree, node->parent);
              node = tree->root;
             }
         }
     }
 
-  node->color = ITREE_BLACK;
+  node->red = false;
 }
 
 /* Link node SOURCE in DEST's place. */
diff --git a/src/itree.h b/src/itree.h
index e5d68fbfab..8f0454dc7a 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -45,8 +45,8 @@ struct interval_node
   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. */
-  enum { ITREE_RED, ITREE_BLACK } color;
-  bool_bf visited : 1;          /* For traversal via generator. */
+  bool_bf red : 1;
+  bool_bf visited : 1;          /* Internal to `interval_generator_next`.  */
   bool_bf rear_advance : 1;     /* Same as for marker and overlays.  */
   bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
 };
@@ -64,8 +64,7 @@ struct interval_tree
 };
 
 enum interval_tree_order {
-  ITREE_ASCENDING = 0,
-  ITREE_DEFLT_ORDER = 0,
+  ITREE_ASCENDING,
   ITREE_DESCENDING,
   ITREE_PRE_ORDER,
 };
diff --git a/src/pdumper.c b/src/pdumper.c
index 79644c0151..44486015f0 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2154,7 +2154,7 @@ dump_interval_node (struct dump_context *ctx, struct 
interval_node *node,
   DUMP_FIELD_COPY (&out, node, offset);
   DUMP_FIELD_COPY (&out, node, otick);
   dump_field_lv (ctx, &out, node, &node->data, WEIGHT_STRONG);
-  DUMP_FIELD_COPY (&out, node, color);
+  DUMP_FIELD_COPY (&out, node, red);
   DUMP_FIELD_COPY (&out, node, visited);
   DUMP_FIELD_COPY (&out, node, rear_advance);
   DUMP_FIELD_COPY (&out, node, front_advance);