From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: noverlay branch Date: Mon, 10 Oct 2022 10:44:55 -0400 Message-ID: References: <87sfjzefvv.fsf@rfc20.org> <875ygt6gbj.fsf@rfc20.org> <87pmf04c7s.fsf@rfc20.org> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="29711"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) Cc: emacs-devel@gnu.org To: Matt Armstrong Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Oct 10 17:24:00 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 1ohudM-0007Qg-GC for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 17:24:00 +0200 Original-Received: from localhost ([::1]:35792 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ohudL-000322-ER for ged-emacs-devel@m.gmane-mx.org; Mon, 10 Oct 2022 11:23:59 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:43494) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohu1i-000528-0n for emacs-devel@gnu.org; Mon, 10 Oct 2022 10:45:06 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]:44713) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ohu1e-000828-Pd for emacs-devel@gnu.org; Mon, 10 Oct 2022 10:45:04 -0400 Original-Received: from pmg3.iro.umontreal.ca (localhost [127.0.0.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 8EDE7441ADA; Mon, 10 Oct 2022 10:44:59 -0400 (EDT) Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg3.iro.umontreal.ca (Proxmox) with ESMTP id 4F7B344162D; Mon, 10 Oct 2022 10:44:57 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1665413097; bh=dOGM6qpBy1l8yfcKdgfRJBOSAB8/CpT211s85BTTA4E=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=Hs54HAGNM/pqf50xryIsR+OB3BfDuxtk1AdxFjN0hZwxGjMw2+3Sg5IIWOreC+Vj1 tP8nex2GnDs5Qc38fqhyAodyGe/O/VgLiY+zCcGEvIvTyx3CsOVJXx6A5X9IngR3tB lowiElDftRBtcI9A5S6qiFxSuu1IMTl4RJly9RqvDl7zyn2ZURk+vrhNro2MjFjhMq 7roByiYZQwH5hMzLZUCi0KeWXOCVfVAZmJPTk9edY8vF1RRFn8aTz/KIyCI63s1bkW 7dEcb7M207p6L1nr4ebG2pJpaxejN/Eq6UCw+MmvrcDAfC/0YxNiKOw4EMPOaWACaq aWZ+E4yHFVk7g== Original-Received: from pastel (65-110-220-202.cpe.pppoe.ca [65.110.220.202]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 2AFA7120636; Mon, 10 Oct 2022 10:44:57 -0400 (EDT) In-Reply-To: <87pmf04c7s.fsf@rfc20.org> (Matt Armstrong's message of "Sun, 09 Oct 2022 19:57:43 -0700") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, 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:297370 Archived-At: > I had a different idea of tightening the otree invariant to this: > > 1) A node's otick must be greater than or equal to its children's. That's already checked in the current code, right? > 2) There is no tree->otick, just tree->root->otick. That is what is > incremented when offsets are added. Sounds good. > 3) All downward tree traversal propagates offsets and otick. I think we already do that, but if there are places we missed, then yes, of course. Regarding `otick`, I can see 2 more options: - Get rid of it completely: its sole purpose is to try and keep `overlay-start/end` O(1) in the usual case instead of O(log N), but I'm not convinced it's worth the cost of propagating `otick` everywhere all the time. - A halfway point is to keep `otick` but update it more lazily, i.e. only update it when we do `overlay-start/end` (e.g. in `interval_tree_validate`). > Anyway, thanks for fixing my "thinko" bug in the check_tree code -- I > had the fix but should have sent it faster. I didn't actually intend > for that to be commited yet (pushed it to sr.ht by accident), but maybe > it helped you chase down the bugs you fixed today? Yes, pointed out the problem in the tree insertion code, yes. > Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays I think this is going overboard. I'd rather focus on providing good "everyday checks" (i.e. cheap checks which help document our invariants, controlled by the normal ENABLE_CHECKING) and leave the rest of the debugging code under "manual" control rather than expose it as an `--enable-checking=` option. My assumption here is that once debugged, this overlay code will stay untouched for the next many years (based on the past history of our overlay code). > +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) This max_depth also sounds to me like over-engineering. > - /* 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); > + } > + } Since we'll be recursing into the children, the first two easserts seem redundant with the third (IOW the new code just does the same as the old code, only more verbosely and less efficiently :-( ). What am I missing? > + result.complete = left_result.complete && right_result.complete; > + if (result.complete) I think all calls to `check_tree` should be complete traversals. Most of the invariants checked in it are already checked incrementally via sprinkled assertions elsewhere, so it's only really useful when debugging a concrete known issue where the "local" checks aren't good enough. We could also include a few "cheap" calls to `check_tree` via `eassert` (i.e. calls which we know shouldn't be algorithmically too expensive because we're already traversing the whole tree for some other reason, e.g. when killing a buffer (e.g. to verify that, at the end of the day, we still preversed the RB invariants :-) or maybe during GC). > + { > + /* 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); IIUC this assertion should be conditionalized in the same way as the red+red check, since this invariant can be temporarily false. Stefan