From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Matt Armstrong Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Sun, 16 Oct 2022 14:53:00 -0700 Message-ID: <878rlf77wj.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> <87edvf4p08.fsf@rfc20.org> <87r0zffs27.fsf@rfc20.org> <875ygpvtf0.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="2734"; mail-complaints-to="usenet@ciao.gmane.io" Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Oct 16 23:53:56 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1okBa0-0000YL-0p for ged-emacs-devel@m.gmane-mx.org; Sun, 16 Oct 2022 23:53:56 +0200 Original-Received: from localhost ([::1]:43474 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1okBZy-0005Hs-NA for ged-emacs-devel@m.gmane-mx.org; Sun, 16 Oct 2022 17:53:54 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:54756) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1okBZL-0004dJ-SW for emacs-devel@gnu.org; Sun, 16 Oct 2022 17:53:15 -0400 Original-Received: from relay4-d.mail.gandi.net ([217.70.183.196]:42425) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1okBZI-00054v-0P for emacs-devel@gnu.org; Sun, 16 Oct 2022 17:53:15 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 028A3E0003; Sun, 16 Oct 2022 21:53:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665957186; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=/WZ10ZYNk9B2ykt7Dg0USw4Xrfp2RM0RWhgrjLbx2vE=; b=FLZGqS/yqmPQyLlqnOXu9Rslgofa0glbIDotWd+aK4Y2T21Q/oRPQ20nWoPC/2eAZQDJaI rk7rVg1lKOIqXCMrfUTfrCNrvsEk7oOXvQv697fnj0Kjy+G7Ue5LLElOppHmb4huQ/cuGW 1FK4yz4D6nmJ3zZMAWkI8SAzUfNr+3V4owzlF4Ss4qNct/XkLoXwf7cwRpJxvQ9aMYWyVN wsxahu6ytkH1n4qjAxJoQ5mJnRLXZS6kfFdvEwkOrkS4kwATMcfKvNO5xPkLGKWKHcvn44 s7VJ03SkY3SpXzQ6KHVrrhqQQdCZ+9h+AZx7UvTeyLTjThuGKN24IJkkt2uDOQ== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1okBZ6-000HG3-2g; Sun, 16 Oct 2022 14:53:00 -0700 In-Reply-To: Received-SPF: pass client-ip=217.70.183.196; envelope-from=matt@rfc20.org; helo=relay4-d.mail.gandi.net X-Spam_score_int: -23 X-Spam_score: -2.4 X-Spam_bar: -- X-Spam_report: (-2.4 / 5.0 requ) BAYES_00=-1.9, DKIM_INVALID=0.1, DKIM_SIGNED=0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:297885 Archived-At: --=-=-= Content-Type: text/plain Stefan Monnier writes: >> Thanks Stefan, FWIW I don't see the merges on feature/noverlay yet. >> Have you pushed? > > Hmm... I think so, yes. `git log` tells me: > > commit 65a7b5a802a15daa6274403fef822ec3c9b95469 (HEAD -> noverlay, origin/feature/noverlay) > Author: Matt Armstrong > Date: Tue Oct 11 20:19:16 2022 -0700 > > ; * src/itree.c (check_subtree): fix logical error in eassert Ah, but one patch was missed (the biggie): --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0001-Delete-the-itree_null-sentinel-node-use-NULL-everywh.patch >From 82125d32c5170bcc6ecf480be1f8265524f0aa4e Mon Sep 17 00:00:00 2001 From: Matt Armstrong Date: Wed, 12 Oct 2022 10:06:03 -0700 Subject: [PATCH] Delete the itree_null sentinel node, use NULL everywhere. This effort caught a few (already commited) places that were dereferencing through ITREE_NULL in a confusing way. It makes some functions have to check for NULL in more places, but in my experinece this is worth it from a code clarity point of view. In doing this I rewrote `interval_tree_remove` completely. There there was one final bug in that function that I simply could not find when I #define'd ITREE_NULL to NULL. I couldn't easily understand that function, so instead I rewrote it completely with a focus on code clarity. Bug went away. I have left the ITREE_NULL #define in code, to reduce code review noise. It is easily removed later, mechanically. * src/itree.h: #define ITREE_NULL to NULL and leave a FIXME. * src/itree.c (itree_null): Delete the itree_null static variable. (null_is_sane): Delete (and all callers). (interval_tree_insert): Insert the first node as black straight away. (itree_newlimit): Handle NULL children. (interval_tree_remove_fix): ditto. (interval_tree_insert_fix): ditto. (interval_tree_remove): Rewrite for clarity. (null_safe_is_red): New function. (null_safe_is_black): New function. (interval_tree_replace_child): Renamed from interval_tree_transplant. (interval_tree_transplant): New function that something I think is more like a full transplantation. (names are hard) --- src/itree.c | 278 ++++++++++++++++++++++++++-------------------------- src/itree.h | 5 +- 2 files changed, 140 insertions(+), 143 deletions(-) diff --git a/src/itree.c b/src/itree.c index 1728a8ab3a..6e2dfc6567 100644 --- a/src/itree.c +++ b/src/itree.c @@ -140,44 +140,17 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc. static void interval_tree_rotate_left (struct interval_tree *, struct interval_node *); static void interval_tree_rotate_right (struct interval_tree *, struct interval_node *); static void interval_tree_insert_fix (struct interval_tree *, struct interval_node *); -static void interval_tree_transplant (struct interval_tree *, struct interval_node *, struct interval_node *); -static struct interval_generator* interval_generator_create (struct interval_tree *); +static void interval_tree_replace_child (struct interval_tree *, + struct interval_node *, + struct interval_node *); +static void interval_tree_transplant (struct interval_tree *tree, + struct interval_node *source, + struct interval_node *dest); +static struct interval_generator * +interval_generator_create (struct interval_tree *); static void interval_tree_insert (struct interval_tree *, struct interval_node *); - -/* The sentinel node, the null node. */ -struct interval_node itree_null = { - .parent = NULL, /* never accessed */ - .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) -{ - /* 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); - 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; -} +static bool null_safe_is_red (struct interval_node *node); +static bool null_safe_is_black (struct interval_node *node); /* +------------------------------------------------------------------------------------+ */ @@ -214,8 +187,6 @@ null_is_sane (void) static void itree_init (void) { - eassert (null_is_sane ()); - iter = interval_generator_create (NULL); } @@ -299,8 +270,6 @@ check_subtree (struct interval_node *node, check_tree (struct interval_tree *tree, bool check_red_black_invariants) { - eassert (null_is_sane ()); - eassert (tree != NULL); eassert (tree->size >= 0); eassert ((tree->size == 0) == (tree->root == ITREE_NULL)); @@ -549,7 +518,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) struct interval_node *child = tree->root; uintmax_t otick = tree->otick; /* It's the responsability of the caller to set `otick` on the node, - to "confirm" that the begin/end fields are uptodate. */ + to "confirm" that the begin/end fields are up to date. */ eassert (node->otick == otick); /* Find the insertion point, accumulate node's offset and update @@ -577,7 +546,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) node->parent = parent; node->left = ITREE_NULL; node->right = ITREE_NULL; - node->red = true; + node->red = node != tree->root; node->offset = 0; node->limit = node->end; eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick); @@ -620,8 +589,12 @@ itree_newlimit (struct interval_node *node) { eassert (node != ITREE_NULL); return max (node->end, - max (node->left->limit + node->left->offset, - node->right->limit + node->right->offset)); + max (node->left == ITREE_NULL + ? PTRDIFF_MIN + : node->left->limit + node->left->offset, + node->right == ITREE_NULL + ? PTRDIFF_MIN + : node->right->limit + node->right->offset)); } static bool @@ -653,17 +626,20 @@ interval_tree_remove_fix (struct interval_tree *tree, struct interval_node *node, struct interval_node *parent) { + if (parent == ITREE_NULL) + eassert (node == tree->root); + else eassert (node == ITREE_NULL || node->parent == parent); - eassert (parent == ITREE_NULL - || node == parent->left || node == parent->right); - while (parent != ITREE_NULL && !node->red) + while (parent != ITREE_NULL && null_safe_is_black (node)) { + eassert (node == parent->left || node == parent->right); + if (node == parent->left) { struct interval_node *other = parent->right; - if (other->red) /* case 1.a */ + if (null_safe_is_red (other)) /* case 1.a */ { other->red = false; parent->red = true; @@ -671,8 +647,8 @@ interval_tree_remove_fix (struct interval_tree *tree, other = parent->right; } - if (!other->left->red /* 2.a */ - && !other->right->red) + if (null_safe_is_black (other->left) /* 2.a */ + && null_safe_is_black (other->right)) { other->red = true; node = parent; @@ -681,7 +657,7 @@ interval_tree_remove_fix (struct interval_tree *tree, } else { - if (!other->right->red) /* 3.a */ + if (null_safe_is_black (other->right)) /* 3.a */ { other->left->red = false; other->red = true; @@ -700,7 +676,7 @@ interval_tree_remove_fix (struct interval_tree *tree, { struct interval_node *other = parent->left; - if (other->red) /* 1.b */ + if (null_safe_is_red (other)) /* 1.b */ { other->red = false; parent->red = true; @@ -708,8 +684,8 @@ interval_tree_remove_fix (struct interval_tree *tree, other = parent->left; } - if (!other->right->red /* 2.b */ - && !other->left->red) + if (null_safe_is_black (other->right) /* 2.b */ + && null_safe_is_black (other->left)) { other->red = true; node = parent; @@ -718,7 +694,7 @@ interval_tree_remove_fix (struct interval_tree *tree, } else { - if (!other->left->red) /* 3.b */ + if (null_safe_is_black (other->left)) /* 3.b */ { other->right->red = false; other->red = true; @@ -736,6 +712,7 @@ interval_tree_remove_fix (struct interval_tree *tree, } } + if (node != ITREE_NULL) node->red = false; } @@ -747,86 +724,70 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node) eassert (interval_tree_contains (tree, node)); eassert (check_tree (tree, true)); /* FIXME: Too expensive. */ - /* `broken`, if non-NULL, holds a node that's being moved up to where a black - node used to be, which may thus require further fixups in its parents - (done in `interval_tree_remove_fix`). */ - struct interval_node *broken = NULL; - /* `broken` may be null but `interval_tree_remove_fix` still - needs to know its "parent". - Cormen et al.'s Introduction to Algorithms uses a trick where - they rely on the null sentinel node's `parent` field to hold - the right value. While this works, it breaks the rule that - the `parent` field is write-only making correctness much more tricky - and introducing a dependency on a global state (which is incompatible - with concurrency among other things), so instead we keep track of - `broken`'s parent manually. */ - struct interval_node *broken_parent = NULL; - + /* Find `splice`, the leaf node to splice out of the tree. When + `node` has at most one child this is `node` itself. Otherwise, + it is the in order successor of `node`. */ interval_tree_inherit_offset (tree->otick, node); - if (node->left == ITREE_NULL || node->right == ITREE_NULL) - { - struct interval_node *subst - = node->right == ITREE_NULL ? node->left : node->right; - if (!node->red) - { - broken = subst; - broken_parent = node->parent; /* The future parent. */ - } - interval_tree_transplant (tree, subst, node); - } - else + struct interval_node *splice + = (node->left == ITREE_NULL || node->right == ITREE_NULL) + ? node + : interval_tree_subtree_min (tree->otick, node->right); + + /* Find `subtree`, the only child of `splice` (may be NULL). Note: + `subtree` will not be modified other than changing its parent to + `splice`. */ + eassert (splice->left == ITREE_NULL || splice->right == ITREE_NULL); + struct interval_node *subtree + = (splice->left != ITREE_NULL) ? splice->left : splice->right; + + /* Save a pointer to the parent of where `subtree` will eventually + be in `subtree_parent`. */ + struct interval_node *subtree_parent + = (splice->parent != node) ? splice->parent : splice; + + /* If `splice` is black removing it may violate Red-Black + invariants, so note this for later. */ + + /* Replace `splice` with `subtree` under subtree's parent. If + `splice` is black, this creates a red-red violation, so remember + this now as the field can be overwritten when splice is + transplanted below. */ + interval_tree_replace_child (tree, subtree, splice); + bool removed_black = !splice->red; + + /* Replace `node` with `splice` in the tree and propagate limit + upwards, if necessary. Note: Limit propagation can stabilize at + any point, so we must call from bottom to top for every node that + has a new child. */ + if (splice != node) { - struct interval_node *min - = interval_tree_subtree_min (tree->otick, node->right); - struct interval_node *min_right = min->right; - struct interval_node *min_parent = min->parent; - - if (!min->red) - broken = min_right; - eassert (min != ITREE_NULL); - /* `min` should not have any offsets any more so we can move nodes - underneath it without risking changing their begin/end. */ - eassert (min->offset == 0); - if (min->parent == node) - broken_parent = min; /* The future parent. */ - else - { - interval_tree_transplant (tree, min_right, min); - broken_parent = min->parent; /* The parent. */ - min->right = node->right; - } - min->left = node->left; - min->left->parent = min; - min->red = node->red; - /* FIXME: At this point node->right->parent = min but node->right - is a parent of `min` so total_offsets gets stuck in an inf-loop! */ - 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. */ - 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 - here ("late") because otherwise it would sometimes update part of - the tree with values that would be invalidated by the second - `interval_tree_transplant`. */ - interval_tree_propagate_limit (min_parent); + interval_tree_transplant (tree, splice, node); + interval_tree_propagate_limit (subtree_parent); + if (splice != subtree_parent) + interval_tree_propagate_limit (splice); } - interval_tree_propagate_limit (node->parent); - --tree->size; + interval_tree_propagate_limit (splice->parent); - if (broken) - { - eassert (check_tree (tree, false)); /* FIXME: Too expensive. */ - interval_tree_remove_fix (tree, broken, broken_parent); - } + --tree->size; - node->right = node->left = node->parent = NULL; + /* Fix any black height violation caused by removing a black + node. */ + if (removed_black) + interval_tree_remove_fix (tree, subtree, subtree_parent); eassert ((tree->size == 0) == (tree->root == ITREE_NULL)); eassert (check_tree (tree, true)); /* FIXME: Too expensive. */ + /* Clear fields related to the tree for sanity while debugging. */ + node->red = false; + node->right = node->left = node->parent = NULL; + node->limit = 0; + + /* Must be clean (all offsets applied). Also, some callers rely on + node's otick being the tree's otick. */ + eassert (node->otick == tree->otick); + eassert (node->offset == 0); + return node; } @@ -860,7 +821,6 @@ interval_tree_iter_start (struct interval_tree *tree, enum interval_tree_order order, const char* file, int line) { - eassert (null_is_sane ()); /* struct interval_generator *iter = tree->iter; */ if (iter->running) { @@ -1171,6 +1131,18 @@ interval_generator_narrow (struct interval_generator *g, * | Internal Functions * +===================================================================================+ */ +static bool +null_safe_is_red (struct interval_node *node) +{ + return node != ITREE_NULL && node->red; +} + +static bool +null_safe_is_black (struct interval_node *node) +{ + return node == ITREE_NULL || !node->red; /* NULL nodes are black */ +} + /* Update NODE's limit attribute according to its children. */ static void @@ -1224,9 +1196,6 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node) /* Update limit of NODE and its ancestors. Stop when it becomes stable, i.e. new_limit = old_limit. - - NODE may also be the null node, in which case its parent is - used. (This feature is due to the RB algorithm.) */ static void @@ -1331,7 +1300,9 @@ 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->red) + eassert (tree->root->red == false); + + while (null_safe_is_red (node->parent)) { /* NODE is red and its parent is red. This is a violation of red-black tree property #3. */ @@ -1343,7 +1314,7 @@ interval_tree_insert_fix (struct interval_tree *tree, struct interval_node *node our "uncle". */ struct interval_node *uncle = node->parent->parent->right; - if (uncle->red) /* case 1.a */ + if (null_safe_is_red (uncle)) /* case 1.a */ { /* Uncle and parent are red but should be black because NODE is red. Change the colors accordingly and @@ -1373,7 +1344,7 @@ 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->red) /* case 1.b */ + if (null_safe_is_red (uncle)) /* case 1.b */ { node->parent->red = false; uncle->red = false; @@ -1415,15 +1386,20 @@ itree_total_offset (struct interval_node *node) return offset; } -/* Link node SOURCE in DEST's place. - It's the caller's responsability to refresh the `limit`s - of DEST->parents afterwards. */ +/* Replace DEST with SOURCE as a child of DEST's parent. Adjusts + *only* the parent linkage of SOURCE and either the parent's child + link the tree root. + + Warning: DEST is left unmodified. SOURCE's child links are + unchanged. Caller is responsible for recalculation of `limit`. + Requires both nodes to be using the same effective `offset`. */ static void -interval_tree_transplant (struct interval_tree *tree, struct interval_node *source, - struct interval_node *dest) +interval_tree_replace_child (struct interval_tree *tree, + struct interval_node *source, + struct interval_node *dest) { - eassert (tree && source && dest && dest != ITREE_NULL); + eassert (tree && dest != ITREE_NULL); eassert (source == ITREE_NULL || itree_total_offset (source) == itree_total_offset (dest)); @@ -1438,6 +1414,28 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour source->parent = dest->parent; } +/* Replace DEST with SOURCE in the tree. Copies the following fields + from DEST to SOURCE: red, parent, left, right. Also updates + parent, left and right in surrounding nodes to point to SOURCE. + + Warning: DEST is left unmodified. Caller is responsible for + recalculation of `limit`. Requires both nodes to be using the same + effective `offset`. */ +static void +interval_tree_transplant (struct interval_tree *tree, + struct interval_node *source, + struct interval_node *dest) +{ + interval_tree_replace_child (tree, source, dest); + source->left = dest->left; + if (source->left != ITREE_NULL) + source->left->parent = source; + source->right = dest->right; + if (source->right != ITREE_NULL) + source->right->parent = source; + source->red = dest->red; +} + /* +===================================================================================+ * | Debugging diff --git a/src/itree.h b/src/itree.h index 5733ec1530..0e2e7d1f81 100644 --- a/src/itree.h +++ b/src/itree.h @@ -95,9 +95,8 @@ #define ITREE_H bool_bf front_advance : 1; /* Same as for marker and overlays. */ }; -/* The sentinel node, the null node. */ -extern struct interval_node itree_null; -#define ITREE_NULL (&itree_null) +/* FIXME: replace ITREE_NULL -> NULL everywhere */ +#define ITREE_NULL NULL struct interval_tree { -- 2.35.1 --=-=-=--