* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree @ 2022-12-14 0:11 Yuan Fu 2022-12-14 12:08 ` Eli Zaretskii ` (3 more replies) 0 siblings, 4 replies; 8+ messages in thread From: Yuan Fu @ 2022-12-14 0:11 UTC (permalink / raw) To: 60054 This is not really an Emacs bug, but either tree-siter-c or tree-sitter’s. I’m putting it out here so that if I’m hit by a bus tomorrow, and treesit-search-forward-goto and friends hang, we (eh, you) know what’s going on. I’ve submitted an issue here: https://github.com/tree-sitter/tree-sitter-c/issues/119 So far, I’ve only observed this in that specific edge case. Yuan ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 0:11 bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree Yuan Fu @ 2022-12-14 12:08 ` Eli Zaretskii 2022-12-14 20:27 ` Yuan Fu 2022-12-16 1:14 ` Yuan Fu ` (2 subsequent siblings) 3 siblings, 1 reply; 8+ messages in thread From: Eli Zaretskii @ 2022-12-14 12:08 UTC (permalink / raw) To: Yuan Fu; +Cc: 60054 > From: Yuan Fu <casouri@gmail.com> > Date: Tue, 13 Dec 2022 16:11:01 -0800 > > > This is not really an Emacs bug, but either tree-siter-c or > tree-sitter’s. I’m putting it out here so that if I’m hit by a bus > tomorrow, and treesit-search-forward-goto and friends hang, > we (eh, you) know what’s going on. > > I’ve submitted an issue here: > https://github.com/tree-sitter/tree-sitter-c/issues/119 > > So far, I’ve only observed this in that specific edge case. We should have protection against that, which should be easy, right? ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 12:08 ` Eli Zaretskii @ 2022-12-14 20:27 ` Yuan Fu 2022-12-15 6:16 ` Eli Zaretskii 0 siblings, 1 reply; 8+ messages in thread From: Yuan Fu @ 2022-12-14 20:27 UTC (permalink / raw) To: Eli Zaretskii; +Cc: 60054 > On Dec 14, 2022, at 4:08 AM, Eli Zaretskii <eliz@gnu.org> wrote: > >> From: Yuan Fu <casouri@gmail.com> >> Date: Tue, 13 Dec 2022 16:11:01 -0800 >> >> >> This is not really an Emacs bug, but either tree-siter-c or >> tree-sitter’s. I’m putting it out here so that if I’m hit by a bus >> tomorrow, and treesit-search-forward-goto and friends hang, >> we (eh, you) know what’s going on. >> >> I’ve submitted an issue here: >> https://github.com/tree-sitter/tree-sitter-c/issues/119 >> >> So far, I’ve only observed this in that specific edge case. > > We should have protection against that, which should be easy, right? Just to make sure, we want to use something like slow-fast pointers, where we have two pointers, and one goes twice as fast, right? That’s the one I was taught in school :-) The author advices to use cursors for traversing the tree, as cursors doesn’t have this bug. He also advised against using ts_node_parent and said that they could be removed in the future. I didn’t use cursors in the first place because they can’t traverse the tree backwards, ie, no equivalent of ts_node_prev_sibling, and the performance difference is not significant in Emacs settings. But I just went to look at the source, and it seems ts_node_prev_siblings(node) is implemented by just iterating each children from first to last, until it finds the child just before NODE, LOL[1]. I can do similar things in treesit.c with cursors. By doing that we can fix this problem and be future-proof. In summary, I’m proposing: 1. I add the slow-fast pointer checks in treesit.c and treesit.el 2. I replace ts_node_parent/sibling/child with using cursors in tree-traversal functions in treesit.c. Yuan [1] static inline TSNode ts_node__prev_sibling(TSNode self, bool include_anonymous) { Subtree self_subtree = ts_node__subtree(self); bool self_is_empty = ts_subtree_total_bytes(self_subtree) == 0; uint32_t target_end_byte = ts_node_end_byte(self); TSNode node = ts_node_parent(self); TSNode earlier_node = ts_node__null(); bool earlier_node_is_relevant = false; while (!ts_node_is_null(node)) { TSNode earlier_child = ts_node__null(); bool earlier_child_is_relevant = false; bool found_child_containing_target = false; TSNode child; NodeChildIterator iterator = ts_node_iterate_children(&node); while (ts_node_child_iterator_next(&iterator, &child)) { if (child.id == self.id) break; if (iterator.position.bytes > target_end_byte) { found_child_containing_target = true; break; } if (iterator.position.bytes == target_end_byte && (!self_is_empty || ts_subtree_has_trailing_empty_descendant(ts_node__subtree(child), self_subtree))) { found_child_containing_target = true; break; } if (ts_node__is_relevant(child, include_anonymous)) { earlier_child = child; earlier_child_is_relevant = true; } else if (ts_node__relevant_child_count(child, include_anonymous) > 0) { earlier_child = child; earlier_child_is_relevant = false; } } if (found_child_containing_target) { if (!ts_node_is_null(earlier_child)) { earlier_node = earlier_child; earlier_node_is_relevant = earlier_child_is_relevant; } node = child; } else if (earlier_child_is_relevant) { return earlier_child; } else if (!ts_node_is_null(earlier_child)) { node = earlier_child; } else if (earlier_node_is_relevant) { return earlier_node; } else { node = earlier_node; } } return ts_node__null(); } ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 20:27 ` Yuan Fu @ 2022-12-15 6:16 ` Eli Zaretskii 0 siblings, 0 replies; 8+ messages in thread From: Eli Zaretskii @ 2022-12-15 6:16 UTC (permalink / raw) To: Yuan Fu; +Cc: 60054 > From: Yuan Fu <casouri@gmail.com> > Date: Wed, 14 Dec 2022 12:27:58 -0800 > Cc: 60054@debbugs.gnu.org > > >> https://github.com/tree-sitter/tree-sitter-c/issues/119 > >> > >> So far, I’ve only observed this in that specific edge case. > > > > We should have protection against that, which should be easy, right? > > Just to make sure, we want to use something like slow-fast pointers, where we have two pointers, and one goes twice as fast, right? That’s the one I was taught in school :-) No, I mean protect us from inflooping by checking that the parent of a node is not the node itself. > In summary, I’m proposing: > 1. I add the slow-fast pointer checks in treesit.c and treesit.el > 2. I replace ts_node_parent/sibling/child with using cursors in tree-traversal functions in treesit.c. SGTM, thanks. ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 0:11 bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree Yuan Fu 2022-12-14 12:08 ` Eli Zaretskii @ 2022-12-16 1:14 ` Yuan Fu 2022-12-17 23:28 ` Yuan Fu 2022-12-18 8:10 ` Yuan Fu 3 siblings, 0 replies; 8+ messages in thread From: Yuan Fu @ 2022-12-16 1:14 UTC (permalink / raw) To: Eli Zaretskii; +Cc: 60054 Eli Zaretskii <eliz@gnu.org> writes: >> From: Yuan Fu <casouri@gmail.com> >> Date: Wed, 14 Dec 2022 12:27:58 -0800 >> Cc: 60054@debbugs.gnu.org >> >> >> https://github.com/tree-sitter/tree-sitter-c/issues/119 >> >> >> >> So far, I’ve only observed this in that specific edge case. >> > >> > We should have protection against that, which should be easy, right? >> >> Just to make sure, we want to use something like slow-fast pointers, >> where we have two pointers, and one goes twice as fast, right? >> That’s the one I was taught in school :-) > > No, I mean protect us from inflooping by checking that the parent of a > node is not the node itself. In this particular case, it is the siblings’ parent that equals to the node. Ie, node->sibling->parent = node. If your intention is to protect us from this particular case, switching to use cursors will avoid this bug. Yuan ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 0:11 bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree Yuan Fu 2022-12-14 12:08 ` Eli Zaretskii 2022-12-16 1:14 ` Yuan Fu @ 2022-12-17 23:28 ` Yuan Fu 2022-12-18 6:00 ` Eli Zaretskii 2022-12-18 8:10 ` Yuan Fu 3 siblings, 1 reply; 8+ messages in thread From: Yuan Fu @ 2022-12-17 23:28 UTC (permalink / raw) To: Eli Zaretskii; +Cc: 60054 Yuan Fu <casouri@gmail.com> writes: > Eli Zaretskii <eliz@gnu.org> writes: > >>> From: Yuan Fu <casouri@gmail.com> >>> Date: Wed, 14 Dec 2022 12:27:58 -0800 >>> Cc: 60054@debbugs.gnu.org >>> >>> >> https://github.com/tree-sitter/tree-sitter-c/issues/119 >>> >> >>> >> So far, I’ve only observed this in that specific edge case. >>> > >>> > We should have protection against that, which should be easy, right? >>> >>> Just to make sure, we want to use something like slow-fast pointers, >>> where we have two pointers, and one goes twice as fast, right? >>> That’s the one I was taught in school :-) >> >> No, I mean protect us from inflooping by checking that the parent of a >> node is not the node itself. > > In this particular case, it is the siblings’ parent that equals to the > node. Ie, node->sibling->parent = node. If your intention is to protect > us from this particular case, switching to use cursors will avoid this > bug. Ok, I made the change to use cursor API with tests. Hopefully this is the last time we need to change treesit.c before release. The node->sibling->parent = node cyclic path should be fixed by this change, do you still want checks for it? Yuan ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-17 23:28 ` Yuan Fu @ 2022-12-18 6:00 ` Eli Zaretskii 0 siblings, 0 replies; 8+ messages in thread From: Eli Zaretskii @ 2022-12-18 6:00 UTC (permalink / raw) To: Yuan Fu; +Cc: 60054 > From: Yuan Fu <casouri@gmail.com> > Date: Sat, 17 Dec 2022 15:28:01 -0800 > Cc: 60054@debbugs.gnu.org > > > In this particular case, it is the siblings’ parent that equals to the > > node. Ie, node->sibling->parent = node. If your intention is to protect > > us from this particular case, switching to use cursors will avoid this > > bug. > > Ok, I made the change to use cursor API with tests. Hopefully this is > the last time we need to change treesit.c before release. This broke the Windows build (I fixed it). You cannot start using new tree-sitter functions without adding the boilerplate code for loading them dynamically from the shared library at run time. > The node->sibling->parent = node cyclic path should be fixed by this > change, do you still want checks for it? If that problem can never happen, there's no need for the checks. Thanks. ^ permalink raw reply [flat|nested] 8+ messages in thread
* bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree 2022-12-14 0:11 bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree Yuan Fu ` (2 preceding siblings ...) 2022-12-17 23:28 ` Yuan Fu @ 2022-12-18 8:10 ` Yuan Fu 3 siblings, 0 replies; 8+ messages in thread From: Yuan Fu @ 2022-12-18 8:10 UTC (permalink / raw) To: Eli Zaretskii; +Cc: 60054-done Eli Zaretskii <eliz@gnu.org> writes: >> From: Yuan Fu <casouri@gmail.com> >> Date: Sat, 17 Dec 2022 15:28:01 -0800 >> Cc: 60054@debbugs.gnu.org >> >> > In this particular case, it is the siblings’ parent that equals to the >> > node. Ie, node->sibling->parent = node. If your intention is to protect >> > us from this particular case, switching to use cursors will avoid this >> > bug. >> >> Ok, I made the change to use cursor API with tests. Hopefully this is >> the last time we need to change treesit.c before release. > > This broke the Windows build (I fixed it). You cannot start using new > tree-sitter functions without adding the boilerplate code for loading > them dynamically from the shared library at run time. Ah right, it evaded my mind, sorry about that. >> The node->sibling->parent = node cyclic path should be fixed by this >> change, do you still want checks for it? > > If that problem can never happen, there's no need for the checks. Cool. I’m closing this. Yuan ^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2022-12-18 8:10 UTC | newest] Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-12-14 0:11 bug#60054: 29.0.60; Infinite loop when there are cyclic path in the parse tree Yuan Fu 2022-12-14 12:08 ` Eli Zaretskii 2022-12-14 20:27 ` Yuan Fu 2022-12-15 6:16 ` Eli Zaretskii 2022-12-16 1:14 ` Yuan Fu 2022-12-17 23:28 ` Yuan Fu 2022-12-18 6:00 ` Eli Zaretskii 2022-12-18 8:10 ` Yuan Fu
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.