Re: noverlay branch

[Matt Armstrong]

Matt Armstrong <matt@rfc20.org> writes:

> 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

...now 5 commits on https://git.sr.ht/~matta/emacs/log/feature/noverlay

The latest makes all fields of the global itree_null sentinel node
read-only.  Because this property is only by convention, fragile, and
difficult to verify by reading code, I'm going to look at removing
itree_node entirely next.

>From b4bdbbcd47530ed80d941bd4bd6d57538ee33ca5 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 10:45:05 -0700
Subject: [PATCH 5/5] Stop reading and writing the itree_null.parent field
 entirely.

With this change all fields in the itree_null sentinel are read only.
This makes accessing itree_null thread safe in an obvious way.

Because it took two commits from two peole to get this right, I think
we can call this design fragile and difficult to reason about.
Another benefit of this commit is as preparation for removing sentinel
node completely, and just using NULL.

* src/itree.c (itree_null): Statically initialize itree_null.parent to
NULL.  It is never accessed.
(null_is_sane): Assert parent == NULL.
(interval_tree_remove_fix): Remove unecessary assignments to parent
from node->parent.  These were the last places itree_null.parent were
read.
(interval_tree_remove): Avoid an assignment to itree_null.parent
through min->right->parent.
(interval_tree_transplant): Avoid an assignment to itree_null.parent
through source->parent.
---
 src/itree.c | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index 8d1dd00319..7b6a5039b3 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -146,7 +146,7 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 
 /* The sentinel node, the null node.  */
 struct interval_node itree_null = {
-  .parent = &itree_null,
+  .parent = NULL, /* never accessed */
   .left = &itree_null,
   .right = &itree_null,
   .begin = PTRDIFF_MIN,
@@ -162,12 +162,8 @@ Copyright (C) 2017-2022  Free Software Foundation, Inc.
 static bool
 null_is_sane (void)
 {
-  /* 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); */
+  /* All sentinel node fields are read-only.  */
+  eassert (itree_null.parent == NULL);
   eassert (itree_null.left == &itree_null);
   eassert (itree_null.right == &itree_null);
   eassert (itree_null.begin == PTRDIFF_MIN);
@@ -720,7 +716,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
              other->red = false;
              parent->red = true;
              interval_tree_rotate_left (tree, parent);
-             parent = node->parent;
              other = parent->right;
             }
 
@@ -739,7 +734,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
                  other->left->red = false;
                  other->red = true;
                  interval_tree_rotate_right (tree, other);
-                 parent = node->parent;
                  other = parent->right;
                 }
              other->red = parent->red; /* 4.a */
@@ -759,7 +753,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
              other->red = false;
              parent->red = true;
              interval_tree_rotate_right (tree, parent);
-             parent = node->parent;
              other = parent->left;
             }
 
@@ -778,7 +771,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
                  other->right->red = false;
                  other->red = true;
                  interval_tree_rotate_left (tree, other);
-                 parent = node->parent;
                  other = parent->left;
                 }
 
@@ -859,7 +851,8 @@ interval_tree_remove (struct interval_tree *tree, struct 
interval_node *node)
       interval_tree_transplant (tree, min, node);
       /* We set min->right->parent after `interval_tree_transplant` so
          that calls to `itree_total_offset` don't get stuck in an inf-loop.  */
-      min->right->parent = min;
+      if (min->right != ITREE_NULL)
+        min->right->parent = min;
       interval_tree_update_limit (min);
       /* This call "belongs" with the first `interval_tree_transplant`
          (of `min_right`, done earlier in the `if`) but we prefer to do it
@@ -1486,7 +1479,8 @@ interval_tree_transplant (struct interval_tree *tree, 
struct interval_node *sour
   else
     dest->parent->right = source;
 
-  source->parent = dest->parent;
+  if (source != ITREE_NULL)
+    source->parent = dest->parent;
 }
 
 
-- 
2.35.1