Implement intial version of name resolution for items

[matklad]

The goal here is to implement just enough name resolution to account for imports. In particular, we don't want to resolve references in items other then use tree. We also don't want to handle macros, this time.

For the final API, I think we can reuse existing ModuleScope, but it now should contain imported items as well, including those imported via * imports. OTOH, we will use unresolved ModuleScope for other things probably, so it's also find to introduce some kind of ResolvedModuleScope thing.

Here's I think a struct analgous to this ResolvedModuledScoped in rustc:

https://github.com/rust-lang/rust/blob/6b9b97bd9b704f85f0184f7a213cc4d62bd9654c/src/librustc_resolve/lib.rs#L1047

How do we actually implement this? First of all, we need to keep in mind that in rust name resolution is tricky, because use items not only import things, but they also define them, so one import can affect another import. Here's a couple of fun examples:

// Here, resolution goes a -> b -> a
pub mod a {
    pub use crate::b::*;
    pub mod c {
        pub struct D;
    }
    type T = D;
}

pub mod b {
    pub use crate::a::*;
    pub use self::c::*;
}

// Here, we can observe "infinite" paths
pub mod u {
    pub use crate::v;

    type T = crate::u::v::u::v::u::v::S;
}

pub mod v {
    pub use crate::u;

    pub struct S;
}

To deal with this, I think we need to use a kind of fixed point name resolution algorithm.

The algorithm should build a crate-wite module scope map:

scopes: FxHashMap<ModuleId, ModuleResolutionScope>

It should start with an empty scope for each module. Then, all directly defined items should be added (what current ModuleScope is). Than, we should repeat the following algorithm until there are changes (that is, we use fixed point iteration):

1. pick any import which was not processed, and can be resolved using ModuleResolutionScopes computed so far
2. if this is a * import, which imports module a into b,
   • add all items from a to b
   • Record in some kind of hashmap, that there's a start import from a to b
3. if this is a usual imprt of item I into module a
   • add I to a's scope
   • for all modules, which glob-import from a, add I there as well

The "updating glob imports" bit is implemented here in rustc.

There's a bunch of existing tests we can adapt for this in Intellij: https://github.com/intellij-rust/intellij-rust/blob/9561daee8cfb24a0f8f753b9d9c3a696491428c3/src/test/kotlin/org/rust/lang/core/resolve/RsUseResolveTest.kt

[matklad]

@aochagavia here's the issue

[matklad]

Code wise, I expect this to be handled by two queries:

fn module_resolution_scope(module_id: ModuleId) -> Arc<ModuleResolutionScope> {
    let crate_root = module_id.crate_root();
    Arc::clone(crate_resolution_scope(crate_root)[module_id])
}


fn crate_resolution_scope(root_module: ModuleId) 
    -> Arc<FxHashMap<ModuleId, ModuleResolutionScope>> 
{
     let res = FxHashMap::default();
     for id in root_module.submodules_transitive() { 
         res.insert(id, ModuleResolutionScope::default()) 
     }
     // run fixed point algo
     loop {
     }
}

[matklad]

For the reference, the IntelliJ version of name resolution is implemented here:

https://github.com/intellij-rust/intellij-rust/blob/9561daee8cfb24a0f8f753b9d9c3a696491428c3/src/main/kotlin/org/rust/lang/core/resolve/NameResolution.kt

When implementing it, I used a strategy significantly different from that of rustc. Specifically, I was trying to avoid computing a global per-crate import map, which is costly to do on every modification. So, the implementation uses a somewhat naive approach of recursively resolving each path by walking the module tree and guarding (in a very ad hoc way) against cycles.

I hope that a whole crate implementation would be feasible for rust-analyzer though: because we use salsa, we'll need to recompute import only when a set of items, defined in module, changes.

Curiously enough, this should also work in the new versions of IntelliJ Rust, which implement OutOfCodeBlockModificationCounts, so cc @vlad20012

[aochagavia]

Is there a difference between ModuleResolutionScope and ResolvedModuleScope in your description of the issue?

[matklad]

No, it’s just that half way through I’ve came up with a better name and forgot to update the first half

[matklad]

Going to write some code for this issue now

[matklad]

Status update: #236 added the basic infra. It, however, misses pretty crucial bits:

• support for glob imports
• support for reexports

[matklad]

Status update: #245 implementing proper caching. Now, module name resolution results are not recomputed if you type inside a function.

[matklad]

E-easy issue for folks how want to help out with nameres: fix this test.

I think this should be handled in use tree deshugaring

Here's the entry point to the code which actually resolves the import: https://github.com/rust-analyzer/rust-analyzer/blob/0cda188621b792265c957bdf4ac54af31cbc9947/crates/ra_hir/src/module/nameres.rs

[DJMcNab]

I have some time, so I might try and get that working now.

[DJMcNab]

This was more complicated that I expected, so I've had to leave it for now - I didn't realise we also don't handle resolving enum members either, which this sort of is. I'm not available for a few days, but I'll pick this back up afterwards if it still needs doing.

[matklad]

@DJMcNab sure! Though, I don’t think this should handle enum a specifically? Handling of enums would be another, E-less-easy task.

[matklad]

For “fixed point iteration”,
https://github.com/frankmcsherry/blog/blob/master/posts/2018-05-19.md is an awesome source of inspiration. I wonder if we could use datafrog directly...

[DJMcNab]

Well I mean that handling enum members is a similar mechanism to handling Item::self, as they both break the assumption the current algorithm makes that each step in the path is a module, and the final is an item.

[matklad]

as they both break the assumption the current algorithm makes that each step in the path is a module, and the final is an item.

That's true, but this assumption is not used in desugaring of use trees step, and I think we need only to tweak desugaring itself to fix the test.

Handling of enums would mean adding a new kind of Def and modifing the import resolution algo, yeah.

[DJMcNab]

This has been pinned as the finishing work (glob imports) is very important for improving how well our current infrastructure works (required to bring the prelude into scope).

[kjeremy]

Is there a general plan for tackling glob imports?

[matklad]

@kjeremy during name resolution, we should remember the set of glob imports in the form of "module X glob-imports from Z". When we add an item to X's namespace, we should (recursively) fill Z's namespace.

When a glob-dependency edge is introduced, we should should run the same procedure for existing items.

[lnicola]

Fixed in #778?

[DJMcNab]

Or at least superceded by #723?