From: Matt Armstrong <matt@rfc20.org>
To: Stefan Monnier <monnier@iro.umontreal.ca>
Cc: emacs-devel@gnu.org
Subject: Re: noverlay branch
Date: Mon, 10 Oct 2022 11:32:16 -0700 [thread overview]
Message-ID: <87r0zffs27.fsf@rfc20.org> (raw)
In-Reply-To: <87edvf4p08.fsf@rfc20.org>
[-- Attachment #1: Type: text/plain, Size: 813 bytes --]
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.
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0005-Stop-reading-and-writing-the-itree_null.parent-field.patch --]
[-- Type: text/x-diff, Size: 4086 bytes --]
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;
}
\f
--
2.35.1
next prev parent reply other threads:[~2022-10-10 18:32 UTC|newest]
Thread overview: 71+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-25 22:38 noverlay branch Stefan Monnier
2022-09-25 22:50 ` Lars Ingebrigtsen
2022-09-25 22:56 ` Stefan Monnier
2022-09-26 2:52 ` Ihor Radchenko
2022-09-26 3:17 ` Stefan Monnier
2022-09-26 6:11 ` Eli Zaretskii
2022-09-26 13:08 ` Ihor Radchenko
2022-09-26 15:59 ` Eli Zaretskii
[not found] ` <87v8ovdosz.fsf@localhost>
2022-10-08 6:57 ` Eli Zaretskii
2022-10-09 3:25 ` Matt Armstrong
2022-10-09 4:30 ` Eli Zaretskii
2022-10-09 3:23 ` Matt Armstrong
2022-10-09 3:47 ` Stefan Monnier
2022-10-13 12:09 ` Ihor Radchenko
2022-09-29 18:12 ` Stefan Monnier
2022-09-27 5:12 ` Matt Armstrong
2022-09-27 6:53 ` Eli Zaretskii
2022-09-27 17:31 ` Matt Armstrong
2022-09-27 18:45 ` Stefan Monnier
2022-09-28 23:09 ` Stefan Monnier
2022-09-29 14:54 ` Gerd Möllmann
2022-09-29 21:36 ` Stefan Monnier
2022-09-30 5:20 ` Gerd Möllmann
2022-10-06 4:47 ` Matt Armstrong
2022-10-06 5:43 ` Gerd Möllmann
2022-10-07 4:11 ` Matt Armstrong
2022-10-07 4:34 ` Gerd Möllmann
2022-10-07 13:33 ` Stefan Monnier
2022-10-07 14:29 ` Gerd Möllmann
2022-10-07 14:51 ` Stefan Monnier
2022-10-07 15:12 ` Gerd Möllmann
2022-10-07 17:12 ` Stefan Monnier
2022-10-07 14:56 ` Stefan Monnier
2022-10-07 15:59 ` Matt Armstrong
2022-10-07 15:34 ` Matt Armstrong
2022-10-06 12:08 ` Stefan Monnier
2022-09-27 8:39 ` Gerd Möllmann
2022-09-27 9:38 ` Eli Zaretskii
2022-10-06 20:41 ` Matt Armstrong
2022-10-07 16:51 ` Matt Armstrong
2022-10-07 18:28 ` Stefan Monnier
2022-10-08 23:33 ` Matt Armstrong
2022-10-09 3:44 ` Matt Armstrong
2022-10-09 4:12 ` Stefan Monnier
2022-10-09 15:34 ` Stefan Monnier
2022-10-10 2:57 ` Matt Armstrong
2022-10-10 6:24 ` Eli Zaretskii
2022-10-10 16:26 ` Matt Armstrong
2022-10-10 14:44 ` Stefan Monnier
2022-10-11 3:46 ` Matt Armstrong
2022-10-11 4:09 ` Stefan Monnier
2022-10-11 18:02 ` Matt Armstrong
2022-10-11 18:59 ` Stefan Monnier
2022-10-12 5:18 ` Matt Armstrong
2022-10-12 18:02 ` Stefan Monnier
2022-10-12 22:26 ` Matt Armstrong
2022-10-13 4:03 ` Stefan Monnier
2022-10-09 23:47 ` Stefan Monnier
2022-10-10 0:05 ` Emanuel Berg
2022-10-10 16:27 ` Matt Armstrong
2022-10-10 16:33 ` Matt Armstrong
2022-10-10 18:32 ` Matt Armstrong [this message]
2022-10-11 16:06 ` Stefan Monnier
2022-10-12 17:33 ` Matt Armstrong
2022-10-13 3:59 ` Stefan Monnier
2022-10-16 21:53 ` Matt Armstrong
2022-10-23 4:49 ` Matt Armstrong
2022-10-24 9:14 ` Stefan Kangas
2022-10-24 16:21 ` Matt Armstrong
2022-10-24 12:51 ` Eli Zaretskii
2022-10-25 20:57 ` Dmitry Gutov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://www.gnu.org/software/emacs/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87r0zffs27.fsf@rfc20.org \
--to=matt@rfc20.org \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).