Limitations of node_at_span implementation in sway-lsp due to inlined AST

[mitchmindtree]

@JoshuaBatty is in the process of updating sway-lsp to use the TypedParseTree returned from compile_to_ast in order to be able to do things like go-to-definition or semantically-aware find and replace.

To achieve this, the idea is to use a function that looks like:

fn node_at_span(ast: &TypedParseTree, span: &Span) -> &TypedAstNode { ... }

A function like this would allow for taking the span of any hovered token, looking up the enclosing node and retrieving the associated node and type information.

If the TypedParseTree passed to this function was not inlined and we stored submodules, we could look up nodes very efficiently by directly looking up the given module, finding the top-level Item with the enclosing span and then drilling directly into that node.

However, as the TypedParseTree returned from compile_to_ast is inlined, this implementation will require a brute-force search across almost every node. This is because all items are inlined into the root module and as a result the spans of top-level Items give no indication whether or not they may or may not contain the node that we're searching for.

[otrho]

I'd at least be tempted to do the brute force search once and build an index. While not ideal, it'd avoid the exponential time needed without it.

Does the LSP need a fully type-checked AST to perform it's magic? Could it get away with building its own data structure from the output of the parser instead?

[mitchmindtree]

I'd at least be tempted to do the brute force search once and build an index. While not ideal, it'd avoid the exponential time needed without it.

True, this would improve the case where the files aren't changing and the user is moving their cursor around, hovering different tokens to lookup their original definitions/declarations. That said, I don't think it would help much during the file editing process.

Currently we have no concept of incremental-parsing or incremental type-checking, so sway-lsp re-parses and checks the project each time any update was made to any of its files. Building an index would be yet another pass that must be performed on each update.

Does the LSP need a fully type-checked AST to perform it's magic? Could it get away with building its own data structure from the output of the parser instead?

Generally, the more information we can get out of the AST the more fancy features the LSP implementation can provide.

Building a custom data structure from the parsed tree sounds a lot like implementing a custom subset of type-checking. I think this would lead to more work then looking up a node in the AST which the compiler already gives us, and it's not clear to me that we could get away with a much simpler structure for doing things like jump-to-definition, show inferred type for a variable, etc. It would result in a doubling of a lot of the compiler's existing type checking work, which also opens up the possibility of drifting from the original implementation as a result.

Refactoring the AST output by the compiler to be more accommodating sounds more sustainable to me, especially when it seems that the inlined AST is causing other issues both in the compiler and downstream as well #1557.

[otrho]

Currently we have no concept of incremental-parsing or incremental type-checking, so sway-lsp re-parses and checks the project each time any update was made to any of its files.

OK, this sounds expensive, even with optimised data structures. 😟

[sezna]

If inlined copies of functions contained references to their original declarations, would that solve this issue for node_at_span results? It could be a middle ground for now.

[mitchmindtree]

I had a chat with @JoshuaBatty today and he's already started working around this with an approach similar to @otrho's suggestion, so no longer blocked but may want a refactor in the future if we resolve #1557.

[JoshuaBatty]

This issue is pretty outdated and not worth keeping open. Closing.