Re: noverlay branch

[Matt Armstrong <matt@rfc20.org>]

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

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> In any case, I do have a new test for tests/src/buffer-tests.el that
>> crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
>> in a spot in itree.c having to do with offset inheritance.
>
> I tightened up a few things and the code now passes the tests without
> crashing any more.

Stefan, I now have four commits queued up on
https://git.sr.ht/~matta/emacs/log/feature/noverlay

These supercede my last message, and reflect the withdrawal of the diffs
that add a new "overlays" configure time flag, as requested by Eli.

We're still checking the entire tree unconditionally, but the code still
has the height limiting logic in case it is needed.  It also doubles as
a spot check of the fuction that computes the max height of the tree
given its size.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-test-src-buffer-tests.el-Remove-unecessary-message-c.patch --]
[-- Type: text/x-diff, Size: 958 bytes --]

From 246acbddbeb3e9a390fe78242259182af0c2cc18 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sun, 9 Oct 2022 10:12:32 -0700
Subject: [PATCH 1/4] ; * test/src/buffer-tests.el: Remove unecessary `message'
 calls.

---
 test/src/buffer-tests.el | 2 --
 1 file changed, 2 deletions(-)

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index 01780a15cc..9bccbdf2e8 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -1554,10 +1554,8 @@ test-overlay-randomly
         ;; is to initially steadily increase the overlay count, then
         ;; steadily decrease it, then repeat.
         (when (and growing (= overlay-count overlay-count-limit))
-          (message "now shrinking")
           (setq growing nil))
         (when (and (not growing) (= overlay-count 0))
-          (message "now growing")
           (setq growing t))
 
         ;; Create or delete a random overlay according to a
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #3: 0002-Improve-check_subtree.patch --]
[-- Type: text/x-diff, Size: 6916 bytes --]

From 100faa45a3e64f82f0b16fccb511db2431815940 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:48:41 -0700
Subject: [PATCH 2/4] Improve check_subtree

* src/itree.c (struct check_subtree_result): new struct returned by
check_subtree.
(check_subtree): new function, renamed from recurse_check_tree.  Add
new black height assertions.
(check_tree): assert that the tree has non-negative size, assert that
limiting to interval_tree_max_height(tree) levels is enough to
traverses the complete tree.
---
 src/itree.c | 136 ++++++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 111 insertions(+), 25 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index bbab70dac7..60bc2b5c89 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -205,14 +205,44 @@ itree_init (void)
   iter = interval_generator_create (NULL);
 }
 
-static ptrdiff_t
-recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
-                    ptrdiff_t offset, ptrdiff_t min_begin,
-                    ptrdiff_t max_begin, intmax_t *size)
+struct check_subtree_result
 {
+  /* Were all nodes visited?  */
+  bool complete;
+
+  /* Computed node count of the tree.  */
+  int size;
+
+  /* Computed limit of the tree (max END).  */
+  ptrdiff_t limit;
+
+  /* Computed black height of the tree (count of black nodes from the
+     bottom up to the root).  */
+  int black_height;
+};
+
+static struct check_subtree_result
+check_subtree (struct interval_node *node, uintmax_t tree_otick,
+               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
+               ptrdiff_t max_begin)
+{
+  struct check_subtree_result result = { .complete = false,
+                                         .size = 0,
+                                         .limit = PTRDIFF_MIN,
+                                         .black_height = 0 };
   if (node == ITREE_NULL)
-    return PTRDIFF_MIN;
-  ++*size;
+    {
+      /* Every nil node of a Red-Black tree is black */
+      result.black_height = 1;
+      result.complete = true;
+      return result;
+    };
+
+  if (max_depth == 0)
+    {
+      result.complete = false;
+      return result;
+    }
 
   /* Validate structure.  */
   eassert (
@@ -221,12 +251,23 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't check the RB invariants here (neither the absence of
-     red+red nor the equal-black-depth), so that we can use this check
-     even while the tree is temporarily breaking some of those invarints.  */
-  /* Red nodes cannot have red parents.  */
-  /* eassert (node->parent == ITREE_NULL
-              || !(node->red && node->parent->red)); */
+  /* We don't normally check the RB invariants here (neither the
+     absence of red+red nor the equal-black-depth), so that we can use
+     this check even while the tree is temporarily breaking some of
+     those invarints.  You can enable them if you want.  */
+  if (false)
+    {
+      /* If a node is red then both of its children are black.  Red
+         nodes cannot have red parents.  */
+      if (node->red)
+        {
+          eassert (node->left == ITREE_NULL
+                   || node->left->red == false);
+          eassert (node->right == ITREE_NULL
+                   || node->right->red == false);
+          eassert (node->parent == ITREE_NULL || !node->parent->red);
+        }
+    }
 
   eassert (node->offset == 0 || node->otick < tree_otick);
 
@@ -240,29 +281,74 @@ recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
   eassert (begin <= max_begin);
   eassert (end <= limit);
 
-  ptrdiff_t left_limit
-    = recurse_check_tree (node->left, tree_otick, offset, min_begin,
-                          begin, size);
-  ptrdiff_t right_limit
-    = recurse_check_tree (node->right, tree_otick, offset, begin,
-                          max_begin, size);
-  eassert (left_limit <= limit);
-  eassert (right_limit <= limit);
-  eassert (limit == max (end, max (left_limit, right_limit)));
-  return limit;
+  struct check_subtree_result left_result
+    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
+                     min_begin, begin);
+  struct check_subtree_result right_result
+    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
+                     begin, max_begin);
+
+  eassert (left_result.limit <= limit);
+  eassert (right_result.limit <= limit);
+
+  result.complete = left_result.complete && right_result.complete;
+  if (result.complete)
+    {
+      /* Every path from a node to a descendent leaf contains the same
+         number of black nodes.  Often said this way: all nodes have
+         the same "black height".  */
+      eassert (left_result.black_height == right_result.black_height);
+      result.black_height
+        = (node->red ? 0 : 1) + left_result.black_height;
+
+      result.size = 1 + left_result.size + right_result.size;
+      result.limit
+        = max (end, max (left_result.limit, right_result.limit));
+
+      eassert (limit == result.limit);
+    }
+
+  return result;
 }
 
+/* Validate invariants for TREE.
+
+   This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
+   (i.e. Emacs is not configured with
+   "--enable_checking=yes,overlays").  In this mode it can't check all
+   the invariants.  When ENABLE_OVERLAY_CHECKING is 1 it checks the
+   entire tree and validates all invariants.
+*/
 static bool
 check_tree (struct interval_tree *tree)
 {
   eassert (tree != NULL);
+  eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
   if (tree->root == ITREE_NULL)
     return true;
 
-  intmax_t size = 0;
-  recurse_check_tree (tree->root, tree->otick, 0,
-                      PTRDIFF_MIN, PTRDIFF_MAX, &size);
+  /* Limit the traversal depth to what 'interval_tree_max_height'
+     returns.  Later, verify that this is enough height to traverse
+     the complete tree.  */
+  const int max_height = interval_tree_max_height (tree);
+  eassert (max_height >= 0);
+  eassert (max_height <= 120);
+
+  /* NOTE: if this check is too expensive an easy fix is to reduce
+     max_height to for large trees, then relax the assertion on
+     result.complete.  Assertions in check_subtree will still be made
+     at the bottom of the tree (where they are probably most
+     interesting), but some will be skipped closer to the root.  */
+
+  struct interval_node *node = tree->root;
+  struct check_subtree_result result
+    = check_subtree (node, tree->otick, max_height, node->offset,
+                     PTRDIFF_MIN, PTRDIFF_MAX);
+  eassert (result.complete);
+  eassert (result.size == tree->size);
+
+  /* The only way this function fails is eassert().  */
   return true;
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #4: 0003-Check-red-black-invariants-in-most-places.patch --]
[-- Type: text/x-diff, Size: 5270 bytes --]

From f2c25af5217e8ab7e8c00ab3e0084bce2bdf93e8 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 09:07:42 -0700
Subject: [PATCH 3/4] Check red-black invariants in most places

Stefan recently disabled this but I happened to want it back soon
after.

* src/itree.c (check_subtree): new arg: allow_red_red
(check_tree_common): renamed from check_tree, pass allow_red_red
through.
(check_tree): new function, pass allow_red_red=false
(interval_tree_insert): check_tree -> check_tree_common with
allow_red_red=true.
---
 src/itree.c | 50 +++++++++++++++++++++++++-------------------------
 1 file changed, 25 insertions(+), 25 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 60bc2b5c89..9dfac57930 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -222,9 +222,9 @@ itree_init (void)
 };
 
 static struct check_subtree_result
-check_subtree (struct interval_node *node, uintmax_t tree_otick,
-               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
-               ptrdiff_t max_begin)
+check_subtree (struct interval_node *node, bool allow_red_red,
+               uintmax_t tree_otick, int max_depth, ptrdiff_t offset,
+               ptrdiff_t min_begin, ptrdiff_t max_begin)
 {
   struct check_subtree_result result = { .complete = false,
                                          .size = 0,
@@ -251,22 +251,14 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (node->left == ITREE_NULL || node->left->parent == node);
   eassert (node->right == ITREE_NULL || node->right->parent == node);
 
-  /* We don't normally check the RB invariants here (neither the
-     absence of red+red nor the equal-black-depth), so that we can use
-     this check even while the tree is temporarily breaking some of
-     those invarints.  You can enable them if you want.  */
-  if (false)
+  if (!allow_red_red && node->red)
     {
       /* If a node is red then both of its children are black.  Red
          nodes cannot have red parents.  */
-      if (node->red)
-        {
-          eassert (node->left == ITREE_NULL
-                   || node->left->red == false);
-          eassert (node->right == ITREE_NULL
-                   || node->right->red == false);
-          eassert (node->parent == ITREE_NULL || !node->parent->red);
-        }
+      eassert (node->left == ITREE_NULL || node->left->red == false);
+      eassert (node->right == ITREE_NULL
+               || node->right->red == false);
+      eassert (node->parent == ITREE_NULL || !node->parent->red);
     }
 
   eassert (node->offset == 0 || node->otick < tree_otick);
@@ -282,11 +274,11 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   eassert (end <= limit);
 
   struct check_subtree_result left_result
-    = check_subtree (node->left, tree_otick, max_depth - 1, offset,
-                     min_begin, begin);
+    = check_subtree (node->left, allow_red_red, tree_otick,
+                     max_depth - 1, offset, min_begin, begin);
   struct check_subtree_result right_result
-    = check_subtree (node->right, tree_otick, max_depth - 1, offset,
-                     begin, max_begin);
+    = check_subtree (node->right, allow_red_red, tree_otick,
+                     max_depth - 1, offset, begin, max_begin);
 
   eassert (left_result.limit <= limit);
   eassert (right_result.limit <= limit);
@@ -311,7 +303,8 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
   return result;
 }
 
-/* Validate invariants for TREE.
+/* Validate invariants for TREE.  If ALLOW_RED_RED, red nodes with red
+   children are considered valid.
 
    This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
    (i.e. Emacs is not configured with
@@ -320,7 +313,7 @@ check_subtree (struct interval_node *node, uintmax_t tree_otick,
    entire tree and validates all invariants.
 */
 static bool
-check_tree (struct interval_tree *tree)
+check_tree_common (struct interval_tree *tree, bool allow_red_red)
 {
   eassert (tree != NULL);
   eassert (tree->size >= 0);
@@ -343,8 +336,8 @@ check_tree (struct interval_tree *tree)
 
   struct interval_node *node = tree->root;
   struct check_subtree_result result
-    = check_subtree (node, tree->otick, max_height, node->offset,
-                     PTRDIFF_MIN, PTRDIFF_MAX);
+    = check_subtree (node, allow_red_red, tree->otick, max_height,
+                     node->offset, PTRDIFF_MIN, PTRDIFF_MAX);
   eassert (result.complete);
   eassert (result.size == tree->size);
 
@@ -352,6 +345,13 @@ check_tree (struct interval_tree *tree)
   return true;
 }
 
+/* Syntactic sugar for check_tree(tree, false)  */
+static bool
+check_tree (struct interval_tree *tree)
+{
+  return check_tree_common (tree, /* allow_red_red= */ false);
+}
+
 /* +===================================================================================+
  * | Stack
  * +===================================================================================+ */
@@ -616,7 +616,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
 
   /* Fix/update the tree */
   ++tree->size;
-  eassert (check_tree (tree));
+  eassert (check_tree_common (tree, /* allow_red_red= */ true));
   interval_tree_insert_fix (tree, node);
 }
 
-- 
2.35.1


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #5: 0004-Simplify-itree_null-initialization.patch --]
[-- Type: text/x-diff, Size: 3296 bytes --]

From a737c1b8298adf5586eede9bf4dca238b302439d Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:32:56 -0700
Subject: [PATCH 4/4] Simplify itree_null initialization

* src/itree.c (null_is_sane): call eassert directly, check
REAR_ADVANCE, FRONT_ADVANCE.  Add FIXME that PARENT is still
read/write.
(itree_null): initialize statically
(itree_init): remove initialization code, call eassert(null_is_sane())
(check_tree_common): call eassert (null_is_sane())
---
 src/itree.c | 52 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 16 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 9dfac57930..8d1dd00319 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -145,19 +145,42 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static void interval_tree_insert (struct interval_tree *, struct interval_node *);
 
 /* The sentinel node, the null node.  */
-struct interval_node itree_null;
+struct interval_node itree_null = {
+  .parent = &itree_null,
+  .left = &itree_null,
+  .right = &itree_null,
+  .begin = PTRDIFF_MIN,
+  .end = PTRDIFF_MIN,
+  .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
+  .offset = 0,
+  .otick = 0,
+  .red = false,
+  .rear_advance = false,
+  .front_advance = false,
+};
 
 static bool
 null_is_sane (void)
 {
-  /* The sentinel node has most of its fields read-only, except for `parent`,
-     `left`, `right` which are write only.  */
-  return itree_null.red == false
-         && itree_null.otick == 0
-         && itree_null.offset == 0
-         && itree_null.begin == PTRDIFF_MIN
-         && itree_null.end == PTRDIFF_MIN
-         && itree_null.limit == PTRDIFF_MIN;
+  /* The sentinel node has most of its fields read-only.
+
+     FIXME: PARENT is still read/write.  It is written to
+     ininterval_tree_transplant, and later read.  --matt
+  */
+  /* eassert (itree_null.parent == &itree_null); */
+  eassert (itree_null.left == &itree_null);
+  eassert (itree_null.right == &itree_null);
+  eassert (itree_null.begin == PTRDIFF_MIN);
+  eassert (itree_null.end == PTRDIFF_MIN);
+  eassert (itree_null.limit == PTRDIFF_MIN);
+  eassert (itree_null.offset == 0);
+  eassert (itree_null.otick == 0);
+  eassert (itree_null.red == false);
+  eassert (itree_null.rear_advance == false);
+  eassert (itree_null.front_advance == false);
+
+  /* if we get this far things must be good */
+  return true;
 }
 
 /* +------------------------------------------------------------------------------------+ */
@@ -195,13 +218,8 @@ null_is_sane (void)
 static void
 itree_init (void)
 {
-  struct interval_node *null = ITREE_NULL;
-  null->left = null->right = null->parent = null;
-  null->offset = null->otick = 0;
-  null->begin = PTRDIFF_MIN;
-  null->end = PTRDIFF_MIN;
-  null->limit = PTRDIFF_MIN;     /* => max(x, null.limit) = x */
-  null->red = false;
+  eassert (null_is_sane ());
+
   iter = interval_generator_create (NULL);
 }
 
@@ -315,6 +333,8 @@ check_subtree (struct interval_node *node, bool allow_red_red,
 static bool
 check_tree_common (struct interval_tree *tree, bool allow_red_red)
 {
+  eassert (null_is_sane ());
+
   eassert (tree != NULL);
   eassert (tree->size >= 0);
   eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
-- 
2.35.1