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.bugs Subject: bug#58158: 29.0.50; [overlay] Interval tree iteration considered harmful Date: Thu, 06 Oct 2022 15:26:37 -0700 Message-ID: <87h70gd1wi.fsf@rfc20.org> References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="23135"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Eli Zaretskii , 58158@debbugs.gnu.org, Stefan Monnier To: Andreas Politz , Gerd =?UTF-8?Q?M=C3=B6llmann?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Fri Oct 07 00:27:22 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@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 1ogZKr-0005o8-9P for geb-bug-gnu-emacs@m.gmane-mx.org; Fri, 07 Oct 2022 00:27:21 +0200 Original-Received: from localhost ([::1]:44322 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ogZKq-0005br-7Q for geb-bug-gnu-emacs@m.gmane-mx.org; Thu, 06 Oct 2022 18:27:20 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:42640) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ogZKa-0005bb-Hl for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 18:27:04 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:34691) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ogZKZ-0005vk-QR for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 18:27:04 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1ogZKY-0007XT-Cq for bug-gnu-emacs@gnu.org; Thu, 06 Oct 2022 18:27:02 -0400 X-Loop: help-debbugs@gnu.org In-Reply-To: Resent-From: Matt Armstrong Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 06 Oct 2022 22:27:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 58158 X-GNU-PR-Package: emacs Original-Received: via spool by 58158-submit@debbugs.gnu.org id=B58158.166509521328964 (code B ref 58158); Thu, 06 Oct 2022 22:27:02 +0000 Original-Received: (at 58158) by debbugs.gnu.org; 6 Oct 2022 22:26:53 +0000 Original-Received: from localhost ([127.0.0.1]:33769 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZKO-0007X5-O7 for submit@debbugs.gnu.org; Thu, 06 Oct 2022 18:26:53 -0400 Original-Received: from relay2-d.mail.gandi.net ([217.70.183.194]:37717) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ogZKJ-0007Wo-Oq for 58158@debbugs.gnu.org; Thu, 06 Oct 2022 18:26:51 -0400 Original-Received: (Authenticated sender: matt@rfc20.org) by mail.gandi.net (Postfix) with ESMTPSA id 5D92940006; Thu, 6 Oct 2022 22:26:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rfc20.org; s=gm1; t=1665095201; 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; bh=7zAQQXk4w70sHM9M0EujZoyJa/jVCsy6nPZozma+mrQ=; b=cEHkPu7Qqn7buYfIxBz9DZwb67YwwFLVVPWd7L5gtmNFc/eurM0LW2L5/pFlbkS7UTgjMA 9vmxG2khtl6OGaG9523id17YFf9NJjKiBCGHlIhqgPxXQ6glj0BtagPW8WMnEMdhTjWmE7 7oSnL/Upg2qlJK+kDzWOZ+D36bjtIpgD7Oq2Kn97YhUbaUtl857ZIvBvKblx2TR51cHSae PcsBk6SwsWKmItwWSgTr+xm1X09dXzgtSLOknvlJjmFZ+duCvjKik8sGPLP0QvYg4ZuLQX EGxLrR8sm17EoHzHsKrT3ucnrL8ewOWUvqOyqloCGw9IUi/eeKITkoiw6ep7yg== Original-Received: from matt by naz with local (Exim 4.96) (envelope-from ) id 1ogZK9-00438r-24; Thu, 06 Oct 2022 15:26:37 -0700 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:244715 Archived-At: Andreas Politz writes: > I've managed to construct a prototype of this "stateless" iterator. > > I've only implemented the in-order case and only applied it in the overlays_in function. > > The only real trouble I had was with pushing the offset to the children > during the tree navigation in some kind of sensible way. In the end I > gave up and simply pasted calls to the corresponding function "all over > the place". It seems to work, at least buffer-tests are passing. Hey Andreas, this looks pretty good to me but I have some questions on it. > +static > +struct interval_node * > +interval_tree_iterator_in_order_successor (struct interval_tree_iterator* iterator) > +{ > + struct interval_node *node = iterator->node; > + > + if (node != ITREE_NULL) { > + interval_tree_inherit_offset (iterator->tree, node); > + } > + if (node == ITREE_NULL) { > + node = iterator->tree->root; I don't understand this branch. If the node is NULL upon entry to the successor call, why start at the root? Why is the "next in order node" of NULL the root? The root is just an node whose BEG is roughly in the middle of the total inorder traversal, right? The "stateless" inorder traversal algorithm I am used to starts with the minimum node (walk only left links down from the root until at a leaf and that is the minimum). Then do inorder traversal from there. > + if (node != ITREE_NULL) { > + interval_tree_inherit_offset (iterator->tree, node); > + } > + while (interval_tree_iter_traverse_p(iterator, node->left)) { > + node = node->left; > + interval_tree_inherit_offset (iterator->tree, node); > + } > + } else if (interval_tree_iter_traverse_p(iterator, node->right)) > + { > + node = node->right; > + interval_tree_inherit_offset (iterator->tree, node); > + while (interval_tree_iter_traverse_p(iterator, node->left)) { > + node = node->left; > + interval_tree_inherit_offset (iterator->tree, node); > + } > + } > + else > + { > + struct interval_node *parent = node->parent; > + while (node == parent->right) > + { > + node = parent; > + parent = parent->parent; > + } > + if (node != ITREE_NULL) > + node = parent; > + } > + > + return node == ITREE_NULL ? NULL : node; > +} I don't understand how the last "else" case works correctly in the face of a call to `interval_generator_narrow` during iteration. Narrowing could render a node's parent out of the "interesting" range, and so the iterator should not return it but instead keep trying to find a successor in range. Right?