Stream: t-compiler/rust-analyzer

Topic: Blanket trait impls lookup


Kirill Bulatov (Jan 16 2021 at 15:33, on Zulip):

I'm considering alternatives to the way we look up traits for associated items.
Right now, we store every assoc item in fst and then search it, it works for blanket impls too, but it feels pretty indirect in general and it gets tricky when there's no input at all and we still want to find every applicable assoc item for any given struct.

As an alternative, it feels like we can locate all trait impls for a certain hir::Type, similar to the way the lens code works.
But as you can see it's currently less precise: we're unable to detect any blanket impls (see how the lens show a single impl even though there are actually 2 of them):

image.png

Does anybody have an idea, if it's hard to find those blanket impls?
Maybe an idea on which way is better in general for solving the "find the trait for an assoc item" task?
cc @Florian Diebold as a chalk wizard.

Florian Diebold (Jan 16 2021 at 15:52, on Zulip):

I actually just wrote a comment about that on your PR. In the end, you can't get around asking Chalk whether your type implements each of some set of traits. You can use such heuristics to maybe make that set smaller though. You'd basically have to have an index from TyFingerprint to traits, plus a list of traits that have blanket impls (or can have built-in impls). And then you'd have to try each one of those.

Kirill Bulatov (Jan 16 2021 at 15:57, on Zulip):

Yes, just read that one.

Ok, I'd better finish the fst endeavours first then, thank you a lot.

Joshua Nelson (Jan 16 2021 at 16:04, on Zulip):

Florian Diebold said:

I actually just wrote a comment about that on your PR. In the end, you can't get around asking Chalk whether your type implements each of some set of traits. You can use such heuristics to maybe make that set smaller though. You'd basically have to have an index from TyFingerprint to traits, plus a list of traits that have blanket impls (or can have built-in impls). And then you'd have to try each one of those.

hmm - is this because the Chalk API requires it? or because there's no way even in theory to look up impls by type?

Joshua Nelson (Jan 16 2021 at 16:04, on Zulip):

(context: rustdoc is really slow looking up impls: https://rust-lang.zulipchat.com/#narrow/stream/247081-t-compiler.2Fperformance/topic/rustdoc.20calls.20.60for_each_relevant_impl.60.20a.20lot)

Florian Diebold (Jan 16 2021 at 16:19, on Zulip):

keep in mind that you can't really ask e.g. "does Vec implement Into". Vec isn't a type, Vec<T> for some T is, and it can't implement Into, only Into<T> for some (set of) T. so in the case of autocompletion, you're really asking "does this type implement Into<T> for any T", and for rustdoc I assume the question would be "is there any T and U such that Vec<T> implements Into<U>". And the answer to that question is basically determined by a logic program in a turing-complete language, and it's a different logic program for each trait. So, there might be ways to optimize the process of evaluating all those programs in this situation, but in the end I don't think you can't get around doing so

Joshua Nelson (Jan 16 2021 at 16:20, on Zulip):

that makes sense, thanks

Florian Diebold (Jan 16 2021 at 16:22, on Zulip):

(also, the ones you throw away by making an index of impls for each struct would be the ones that are fastest to evaluate anyway, so this might not actually help a huge amount)

Last update: Jul 29 2021 at 09:45UTC