On Aug 17, 2023, at 11:00 PM, Yuan Fu <casouri@gmail.com> wrote:

Code and details here:

https://gist.github.com/jdtsmith/7fa6263a13559d587abb51827e6ae472

I’m not entirely surprised. In the parse tree that tree-sitter generates is a DAG, where the parent node has pointers to the child nodes, but not the other way around. That means to go to the parent node from a child node, what tree-sitter actually does is go down from the root node until it hits the parent node. This process is linear to the height of the tree.

to go to the parent node from a child node, what tree-sitter actually does is go down from the root node until it hits the parent node. This process is linear to the height of the tree.

Do you mean linear in the width of the tree? I’ve color-coded the plot by tree depth (i.e. how many ancestors a given node has back to root). Or maybe you are thinking of the tree lying on its side (like vundo ;)?

Also, getting the node at point isn’t free either. To get the node at point, we actually iterates from the first child node of the root node until reaching one that contains the point, then iterate from the first child node of that node until reaching one that contains the point, etc, until we reach a leaf node. So log(N) time complexity is expected.

I tested node-at-point on the same file, and it is quite fast, with worst case performance only 30µs (vs. 3ms for the full parent navigation), and growing very slowly, between sqrt(log(N)) and log(N). Check the gist for a new figure.

Unless I am misunderstanding, for the common case of finding parent of the node at point, it seems the algorithm you describe could be tweaked to work well. I.e. instead of "stop when reaching a leaf node containing point", just "stop when you reach a node containing point who has the original node as a child”? This should give (hypothetical) “parent-of-node-at-point” the same great speed as node-at-point.

Then “parent-of-node-at-point-until” could do something quite clever: accumulate parent nodes all the way from root to the child’s direct parent into a list (same low cost, modulo the node storage). Then run the predicate on that list (in reverse), returning the first match. Could of course return that full list too (“ancestors-of-node-at-point”), for other uses. These should all be quite fast compared to a full breadth and depth searching of every nook and cranny in the syntax tree that node-parent seems to do (having no positional information to wield).

I’m not too worried tho, because IIRC the absolute time is very short. The 100x variability doesn’t mean much if the 100x is still very fast.

This is on a brand new fast machine, and 3ms is pretty slow for things that need to run dozens of times per keystroke (e.g. font-lock).

That is an interesting limitation for sure. It seems that perhaps each node's start..end information can be really helpful here for winnowing the tree, when you are mostly concerned about nodes relevant to and covering particular positions in the buffer.