Re: Tree Sitter (was Re: cc-mode fontification feels random)

[Stefan Monnier]

> Alternately, you can only store the length of each token (as tree-sitter
> does); then when processing queries, you have to add up all the lengths
> of the preceding tokens in order to report the buffer position of the
> information you are computing. That is also linear in the length of the
> buffer.

You can probably get better than linear performance in "the usual case"
by storing the total length of the subtree at each node of the AST.
It's still theoretically linear in the worst case, of course.


        Stefan