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: Mon, 10 Oct 2022 09:33:43 -0700 Message-ID: <87edvf4p08.fsf@rfc20.org> References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.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="38889"; 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 Mon Oct 10 18:43:30 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 1ohvsF-0009pK-E5 for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 18:43:27 +0200 Original-Received: from localhost ([::1]:51606 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ohvsE-0004Pd-2W for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 12:43:26 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:45470) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohviy-0004eR-GX for emacs-devel@gnu.org; Mon, 10 Oct 2022 12:33:53 -0400 Original-Received: from relay7-d.mail.gandi.net ([217.70.183.200]:41091) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohviv-0002Uh-LR for emacs-devel@gnu.org; Mon, 10 Oct 2022 12:33:52 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id B544A20003; Mon, 10 Oct 2022 16:33:45 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665419626; 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=yTDxVIWyCx2xfo5PQixgK/M0KR8/QtnHUsbLynAIngU=; b=YzouH5Z8G03K93aJ5Qro/A7Rm52YWFkztPbatyXV2FN0m6m/3rHUkyIYJcVhPur7739o+R U7cnSYEdDhf01ki1sKYMZ55Ut0iKau0wE8xPfc0Gxnp76S6Ur8OLARjcLTkvIrinjuN7xe EBoTloWDokJ+dEgDTAacu9yikzt2ixT6KeXZ8Nd6HR3ytKeozlMV2p7Qnw/EeKsbRce8Bp X6yMVoa+cztcrZWMsL2reDI1b0QROjIXJyfY4jk0fzcB4mcak4VAj0tYf3FVTbRy3zL9Xs XXUFRVMVY83D0PKVPgh8enazIO71xbEEoMZ69VzwfvjhTQ/d4s7tUZdQLPzEqA== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ohvip-0083ac-1E; Mon, 10 Oct 2022 09:33:43 -0700 In-Reply-To: Received-SPF: pass client-ip=217.70.183.200; envelope-from=matt@rfc20.org; helo=relay7-d.mail.gandi.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, 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:297386 Archived-At: --=-=-= Content-Type: text/plain Stefan Monnier 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. --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0001-test-src-buffer-tests.el-Remove-unecessary-message-c.patch >From 246acbddbeb3e9a390fe78242259182af0c2cc18 Mon Sep 17 00:00:00 2001 From: Matt Armstrong 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 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0002-Improve-check_subtree.patch >From 100faa45a3e64f82f0b16fccb511db2431815940 Mon Sep 17 00:00:00 2001 From: Matt Armstrong 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 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0003-Check-red-black-invariants-in-most-places.patch >From f2c25af5217e8ab7e8c00ab3e0084bce2bdf93e8 Mon Sep 17 00:00:00 2001 From: Matt Armstrong 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 --=-=-= Content-Type: text/x-diff Content-Disposition: inline; filename=0004-Simplify-itree_null-initialization.patch >From a737c1b8298adf5586eede9bf4dca238b302439d Mon Sep 17 00:00:00 2001 From: Matt Armstrong 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 --=-=-=--