Impl Index

[matklad]

To do resolve and completion, we need to answer a question "what traits are implemented for a given type?" Moreover, we need to consider only the traits that are currently in scope , so the question reduces to "Is the trait T implemented for the type S?" However, keep in mind the following "advanced" example:

mod a {
    pub trait H {}

    impl<T> H for T {}
}

mod b {
    pub trait V {
        fn foo(&self) {}
    }

    impl<T: super::a::H> V for T {}
}

struct S;

fn main() {
    use b::V;
    let s = S;

    // To understand that `S: V` we need to know that `S: H`,
    // although `H` is not in scope
    s.foo();
}

We do not handle generics in any way yet, so I think it's ok to focus on simpler cases for now.

The simplest implementation would be to create an index of all impls. Then in order to answer The Question you would process all entries and check that the trait and the type of the impl resolve to the trait and the type in question. Arguably this is not very efficient, because there are a lot of impls, and majority of them are irrelevant.

The more advanced implementation would index the impls by the name of the trait. You still need to process a number of irrelevant impls though.

It's not easy to index the impl by the type name (impl<T> X for T where T: A + B {} ?). However I suspect that the vast majority of impls have a simpler form of impl X for S or impl<T> X for S<X>, for which we can index by both the type and the trait. So my suggestion is to create two indexes:

• simple impl index, which stores impls keyed by the trait and the type name, if there is a type name.
• sophisticated (generic) impl index, keyed by the trait name (can omit this in the initial implementation).

The idea is that you first try to find a simple impl for a given trait and type. If you do not succeed, you try to find a sophisticated impl and then try to solve its constraints. Looks like this would work nicely with plain stub indexes, invalidated on file change (we only need to verify impl's trait and type resolve target)

However there are additional properties which we may want to exploit in indexing/caching.

• Crates form a DAG, and you usually work near the sink of the DAG. It may make sense to introduce CRATE_MODIFICATION_COUNT and use it for resolve caching. This count would get an update when the crate or any of it's dependencies is modified.
• Coherence rules say, roughly, that there are only two possible crates where an impl X for S can be defined. Namely, they are the crates where X is defined and where S is defined. In theory, this should allow us to cut down on the number of impls we investigate, because we'll need to consider only two crates. In practice, I think that all impls would be in these two crates anyway, so this will not cut down on anything.

[matklad]

https://github.com/rust-lang/rust/blob/master/src/librustc_typeck/check/method/README.md

[matklad]

Another thing which we could exploit is filtering the set of applicable traits by the method name (this is how rustc does resolve, but I don't think it is applicable for the completion).

[matklad]

Thinking about it a bit more, I think a better strategy would be to implement a simpler "inherent impl" rather then jumping directly to the trait impls.

[matklad]

Closed in #566