Add stack graphs

[jorendorff]

The main work here is in queries/stack-graphs.tsg.

Implemented:

• use-to-definition lookups for: local variables, arguments, items, type parameters, lifetime parameters, loop labels, bindings in match, if let, and while let expressions
• field names, in the unusual cases where the type is obvious (struct literals and struct patterns, including struct-like enums)
• paths (using ::)
• imports, within a crate

Not implemented: (an incomplete list)

• field names, when after .
• methods
• generally anything that requires figuring out the type of an expression
• imports with * (doing this right would require implementing some form of visibility, which will be hard)
• imports with as _
• anything defined in an impl block; Self

I intend to keep working on it, but I figure there's enough here to land something now.

[maxbrunsfeld]

Wow, this is awesome.

Not implemented: (an incomplete list)

• field names, when after .
• methods
• anything defined in an impl block; Self

I'm curious about your thoughts on what level of support for fields/methods/impls would be reasonable to achieve within the stack graphs framework. Do you think it's doable to get pretty close to rust-analyzer's level of code navigation when in "normal" rust code, that's not full of macros? Do you have a sense of what Rust constructs are going to be difficult to model?

I commented on https://github.com/tree-sitter/tree-sitter-typescript/pull/209 with a question to @hendrikvanantwerpen and @dcreager about whether or not we should break CI if the stack graphs are broken on subsequent grammar changes (since most contributors won't yet be familiar with stack graphs). We didn't yet get a chance to schedule a call yet, but FWIW, I definitely don't mean to discourage you folks from merging these PRs if you folks think they're ready to go.

[jorendorff]

I'm curious about your thoughts on what level of support for fields/methods/impls would be reasonable to achieve within the stack graphs framework. Do you think it's doable to get pretty close to rust-analyzer's level of code navigation when in "normal" rust code, that's not full of macros? Do you have a sense of what Rust constructs are going to be difficult to model?

I can't guess what the experience will be like qualitatively. I think we just have to try it.

• Basic fields/methods/impls is doable. I'll tackle that next.
• I'm not sure how to model reference and slice types. I'll figure something out.
• Traits and generics are much harder; some common cases are very hard or impossible given the model as I understand it. But I need more tutorial time with @dcreager and more experience before I can say for sure.

Together, these uncertain features touch most Rust code.

I don't think any of these features are the biggest obstacle. Cross-crate references within a repo don't work; cross-crate references across repos and into the standard library will require significant changes to support. rust-analyzer does all that out of the box. Without those features, I'm about 73% sure that the precise code nav experience will suck.

It would be nice to provide jump-to-definition for identifiers that appear inside, say, a println!() macro. Currently this doesn't work either. Works in rust-analyzer.

I'm sure I have other bugs that don't affect rust-analyzer. And so on.

I commented on tree-sitter/tree-sitter-typescript#209 with a question to @hendrikvanantwerpen and @dcreager about whether or not we should break CI if the stack graphs are broken on subsequent grammar changes (since most contributors won't yet be familiar with stack graphs). We didn't yet get a chance to schedule a call yet, but FWIW, I definitely don't mean to discourage you folks from merging these PRs if you folks think they're ready to go.

Yeah, it makes sense to clarify what the criteria are for this branch before merging.

I'll happily accept whatever criteria are on offer; I mainly want to get this into any branch in this repo, so we can use GitHub Issues, PRs, and code review from now on.

[hendrikvanantwerpen]

@maxbrunsfeld I had suggested to @jorendorff to open PR's on this add-stack-graph branch, so we can do reviewing and merge his work into something that is part of the ecosystem. Dependiong on the outcome of our discussion I would then make sure this is either merged into main or moved over to the dedicated repository for stack graph rules.