Skip to content

Comments

[red-knot] Goto type definition#16901

Merged
MichaReiser merged 13 commits intomainfrom
micha/go-to-type-definition
Apr 2, 2025
Merged

[red-knot] Goto type definition#16901
MichaReiser merged 13 commits intomainfrom
micha/go-to-type-definition

Conversation

@MichaReiser
Copy link
Member

@MichaReiser MichaReiser commented Mar 21, 2025

Summary

Implement basic Goto type definition support for Red Knot's LSP.

This PR also builds the foundation for other LSP operations. E.g., Goto definition, hover, etc., should be able to reuse some, if not most, logic introduced in this PR.

The basic steps of resolving the type definitions are:

  1. Find the closest token for the cursor offset. This is a bit more subtle than I first anticipated because the cursor could be positioned right between the callee and the ( in call(test), in which case we want to resolve the type for call.
  2. Find the node with the minimal range that fully encloses the token found in 1. I somewhat suspect that 1 and 2 could be done at the same time but it complicated things because we also need to compute the spine (ancestor chain) for the node and there's no guarantee that the found nodes have the same ancestors
  3. Reduce the node found in 2. to a node that is a valid goto target. This may require traversing upwards to e.g. find the closest expression.
  4. Resolve the type for the goto target
  5. Resolve the location for the type, return it to the LSP

Design decisions

The current implementation navigates to the inferred type. I think this is what we want because it means that it correctly accounts for narrowing (in which case we want to go to the narrowed type because that's the value's type at the given position). However, it does have the downside that Goto type definition doesn't work whenever we infer T & Unknown because intersection types aren't supported. I'm not sure what to do about this specific case, other than maybe ignoring Unkown in Goto type definition if the type is an intersection?

Known limitations

  • Types defined in the vendored typeshed aren't supported because the client can't open files from the red knot binary (we can either implement our own file protocol and handler OR extract the typeshed files and point there). See Go to with vendored typeshed stubs ty#77
  • Red Knot only exposes an API to get types for expressions and definitions. However, there are many other nodes with identifiers that can have a type (e.g. go to type of a globals statement, match patterns, ...). We can add support for those in separate PRs (after we figure out how to query the types from the semantic model). See Goto-type and hover-type for non-expression nodes (identifiers in statements) ty#144
  • We should have a higher-level API for the LSP that doesn't directly call semantic queries. I intentionally decided not to design that API just yet.

Test plan

Screen.Recording.2025-04-01.at.12.48.21.mov

Goto type definition on a union

Screenshot 2025-04-01 at 13 02 55

Note: I recorded this using a custom typeshed path so that navigating to builtins works.

if new_contents != old_contents {
active_index = LineIndex::from_source_text(&new_contents);
}
active_index = LineIndex::from_source_text(&new_contents);

This comment was marked as outdated.

@github-actions
Copy link
Contributor

github-actions bot commented Mar 21, 2025

mypy_primer results

No ecosystem changes detected ✅

@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch from f66cabc to 9b7cbc7 Compare March 21, 2025 16:43
@MichaReiser MichaReiser added the ty Multi-file analysis & type inference label Mar 21, 2025
@github-actions
Copy link
Contributor

github-actions bot commented Mar 21, 2025

ruff-ecosystem results

Linter (stable)

✅ ecosystem check detected no linter changes.

Linter (preview)

✅ ecosystem check detected no linter changes.

Formatter (stable)

✅ ecosystem check detected no format changes.

Formatter (preview)

✅ ecosystem check detected no format changes.

@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch 2 times, most recently from e42a8da to 6b8b185 Compare March 28, 2025 15:10
MichaReiser added a commit that referenced this pull request Mar 28, 2025
## Summary

This PR adds `as_<group>` methods to `AnyNodeRef` to e.g. convert an
`AnyNodeRef` to an `ExprRef`.

I need this for go to definition where the fallback is to test if
`AnyNodeRef` is an expression and then call `inferred_type` (listing
this mapping at every call site where we need to convert `AnyNodeRef` to
an `ExprRef` is a bit painful ;))

Split out from #16901

## Test Plan

`cargo test`
@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch from 6b8b185 to 1d6dc13 Compare March 28, 2025 20:12
@MichaReiser MichaReiser changed the base branch from main to micha/knot-ide March 28, 2025 20:12
@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch 3 times, most recently from bfd6a9b to 0a07abb Compare March 28, 2025 20:33
Base automatically changed from micha/knot-ide to main April 1, 2025 07:36
@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch 2 times, most recently from 285e071 to 54c359b Compare April 1, 2025 09:20
Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The main change here is that I extracted a helper to convert a LSP Position to a TextSize and I then used this logic in to_text_range (which simplifies the code quiet a bit)

@MichaReiser MichaReiser changed the base branch from main to micha/source-order-visitor-visit-identifier April 1, 2025 09:24
@MichaReiser MichaReiser marked this pull request as ready for review April 1, 2025 11:06
Base automatically changed from micha/source-order-visitor-visit-identifier to main April 1, 2025 14:58
@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch from 9cf6900 to d6aa201 Compare April 1, 2025 16:19
@carljm
Copy link
Contributor

carljm commented Apr 1, 2025

it does have the downside that Goto type definition doesn't work whenever we infer T & Unknown because intersection types aren't supported. I'm not sure what to do about this specific case, other than maybe ignoring Unkown in Goto type definition if the type is an intersection?

I do think that we should ideally drill down into both unions and intersections and filter out a number of types: Any, Unknown, Todo (so all Type::Dynamic), as well as Type::AlwaysTruthy, Type::AlwaysFalsy, and possibly others. Basically any type that commonly arises from narrowing that has no useful definition target. This should allow goto features to work better for many narrowed types.

Copy link
Contributor

@carljm carljm left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good to me! I don't know the LSP or parser code well, so I can't claim to have done a solid review of those parts, but I looked over the goto stuff.


impl<'db> InstanceType<'db> {
pub(super) fn class(self) -> Class<'db> {
pub fn class(self) -> Class<'db> {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should we implement focus_range and full_range on Type (and return None for types where we don't know it) so we don't have to expose so many type internals?

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

(Oh, this comment was before I read the full diff; I've seen now the navigation-targets trait. I understand why we want to keep all the trait implementations of that in one place, but it still does feel odd to me that we do that outside of the semantics crate, meaning we have to make so many type internals public.)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree that it would be great to avoid exposing these internals. I called this out in the summary that we should introduce a new high level API for all those operations. I'm reluctant to do so just now because it's unclear to me how that API would look like.

I'm getting the sense that we lack two APIs:

  • Give a type query its definition: This is roughly what the big match statement does.
  • Given a node, query its definition: We'll need this for hover (because most IDEs show the signature and not just the type) and to support some of the goto targets that we currently can't retrieve a type for.

I also don't consider this a problem specific to semantic indexing. Ideally, the LSP and linter would limit their use of salsa APIs (including APIs from ruff_db, e.g. system_path_to_file). But I'm not sure yet how that would look like. I need some more code to identify a pattern.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

For example, r-a requires that the ide crate uses its Semantics API

Copy link
Member Author

@MichaReiser MichaReiser Apr 2, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Okay, I have an idea of how to address some of the concerns. But I'll do so in a separate PR

| Type::SubclassOf(_)
| Type::Never
| Type::Callable(_)
| Type::Intersection(_)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why not handle this the same as union and collect all navigation targets from elements?

(I think we can ignore negative elements.)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The difference is that the value isn't the type of any of the elements in the intersection. Instead, it's the type that intersects with all elements. So I think it's just wrong? I can try and see what typescript does here

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's the type of all the elements of the intersection; if anything it seems even more correct here than in the union case? In the union case, the actual value only needs to be one of the union elements, the other ones are all "wrong".

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TypeScript doesn't support goto type definition on intersections, which matches my understanding unless Red Knot's intersection types work differently.

The LSP shows one location for each union variant, which very nicely matches how unions work: The value is one of the types shown (see screenshot above).

It would be very surprising if we showed intersections exactly the same as unions because users would then be unable to distinguish them from unions. I'll leave this as is (minus filtering out Unknown) because I'm not convinced that presenting them the same as unions is the right solution and there isn't an obvious alternative.

Copy link
Member

@dhruvmanila dhruvmanila left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks really great!

This shouldn't block merging the PR but I want to look at the covering node logic tomorrow morning and also want to play around with it in an editor context.

Type::Dynamic(_)
| Type::SubclassOf(_)
| Type::Never
| Type::Callable(_)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should this go to the Callable definition in collections.abc? Pyright doesn't do it thought.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Wouldn't that be Goto definition? If so, I thin it should go to type (because this is what to_meta_type returns?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I was referring to a variable that's annotated using typing.Callable similar to how we go to int class for a variable annotated as int. For example, x: Callable[[], None] = lambda: None.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah I think going to the definition of the Callable type for something with a type of Callable would make sense and be consistent with goto-type-definition. But also doesn't really matter until we support navigating to typeshed anyway.

@MichaReiser
Copy link
Member Author

I do think that we should ideally drill down into both unions and intersections and filter out a number of types: Any, Unknown, Todo (so all Type::Dynamic), as well as Type::AlwaysTruthy, Type::AlwaysFalsy, and possibly others. Basically any type that commonly arises from narrowing that has no useful definition target. This should allow goto features to work better for many narrowed types.

This already happens for unions (because those types have no navigation targets). I can see if I can refine intersection types further.

@MichaReiser MichaReiser force-pushed the micha/go-to-type-definition branch from d6aa201 to c8b07ce Compare April 2, 2025 09:28
@MichaReiser MichaReiser enabled auto-merge (squash) April 2, 2025 11:22
@MichaReiser MichaReiser merged commit 2ae39ed into main Apr 2, 2025
20 checks passed
@MichaReiser MichaReiser deleted the micha/go-to-type-definition branch April 2, 2025 12:12
maxmynter pushed a commit to maxmynter/ruff that referenced this pull request Apr 3, 2025
## Summary

Implement basic *Goto type definition* support for Red Knot's LSP.

This PR also builds the foundation for other LSP operations. E.g., Goto
definition, hover, etc., should be able to reuse some, if not most,
logic introduced in this PR.

The basic steps of resolving the type definitions are:

1. Find the closest token for the cursor offset. This is a bit more
subtle than I first anticipated because the cursor could be positioned
right between the callee and the `(` in `call(test)`, in which case we
want to resolve the type for `call`.
2. Find the node with the minimal range that fully encloses the token
found in 1. I somewhat suspect that 1 and 2 could be done at the same
time but it complicated things because we also need to compute the spine
(ancestor chain) for the node and there's no guarantee that the found
nodes have the same ancestors
3. Reduce the node found in 2. to a node that is a valid goto target.
This may require traversing upwards to e.g. find the closest expression.
4. Resolve the type for the goto target
5. Resolve the location for the type, return it to the LSP

## Design decisions

The current implementation navigates to the inferred type. I think this
is what we want because it means that it correctly accounts for
narrowing (in which case we want to go to the narrowed type because
that's the value's type at the given position). However, it does have
the downside that Goto type definition doesn't work whenever we infer `T
& Unknown` because intersection types aren't supported. I'm not sure
what to do about this specific case, other than maybe ignoring `Unkown`
in Goto type definition if the type is an intersection?

## Known limitations

* Types defined in the vendored typeshed aren't supported because the
client can't open files from the red knot binary (we can either
implement our own file protocol and handler OR extract the typeshed
files and point there). See
https://github.com/astral-sh/ruff/issues/17041
* Red Knot only exposes an API to get types for expressions and
definitions. However, there are many other nodes with identifiers that
can have a type (e.g. go to type of a globals statement, match patterns,
...). We can add support for those in separate PRs (after we figure out
how to query the types from the semantic model). See
https://github.com/astral-sh/ruff/issues/17113
* We should have a higher-level API for the LSP that doesn't directly
call semantic queries. I intentionally decided not to design that API
just yet.


## Test plan


https://github.com/user-attachments/assets/fa077297-a42d-4ec8-b71f-90c0802b4edb

Goto type definition on a union

<img width="1215" alt="Screenshot 2025-04-01 at 13 02 55"
src="https://github.com/user-attachments/assets/689cabcc-4a86-4a18-b14a-c56f56868085"
/>



Note: I recorded this using a custom typeshed path so that navigating to
builtins works.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

ty Multi-file analysis & type inference

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants