Refactor import resolution (CrateDefMap)

[matklad]

Problem

On of the larger and most important phases of rust-analyzer is CrateDefMap construction --- for each module, rust-analyzer determines the set of items defined & visible in the modules. This requires resolving imports, processing globs & expanding macros. The bulk of the current implementation lives here:

https://github.com/rust-analyzer/rust-analyzer/blob/753af410056937d7be3a1b3457c834a887288957/crates/hir_def/src/nameres/collector.rs

There are two big problems with code in question:

• it's very messy, ad hoc, hard to understand & modify
• it doesn't handle local items (fn foo() { use Bar::*; ... }) in a principled way.

I think we first should tackle the first problem (basically, refactor the thing in place until it makes sense), and then attack the second one.

Broadly, what we want is some kind of "name resolution IR", a-la chalk, which allows us to capture the essence of name resolution.

Constraints

The rough constraints for the final solution are as follows:

• the core algorithm should process the tree of modules, expanding macros and resolving the imports using the fixed-point iteration algorithm.
• it should not look into item bodies -- we should be able to lazily resolve bodies (this is important to make IDE snappy)
• however, when doing resolution inside bodies, we should use the same algorithm and data structures. Roughly, there needs to be some kind of "parent scope" concept for CrateDefMap-like things

Proposed solution

I think the best thing we can do is to extract the fixed point iteration logic elswhere, as an IR. This IR will represent a bunch of scopes (modules) which contains names and links between scopes (glob import). The primitive operation of the IR is adding a name to the module (which should backpropagate via links) or adding a link (which similarly should propagate all the names). This thing needs to know about namespaces, but it doesn't need to know what defs are (we probably can represent them as just indices) and it also doesn't need to know about imports & macros (ie, I think results of import resolution and macro expansion could be injected from the outside). Here's a very rough and incomplete sketch of the API:

https://gist.github.com/matklad/145c88131282e8392e64d088ee8a50e4

[umanwizard]

@matklad to clarify, when you say we should use the same algorithm inside item bodies, you mean because module trees with complex import relationships might exist there, too?

E.g.

fn main() {
    pub mod mymod {
        pub mod a {
            pub use super::b::*;
        }
        pub mod b {
            pub use super::a::foo as bar;
            pub fn foo() {
                println!("Hello, world!");
            }
        }
    }

    mymod::b::bar();
}

[matklad]

@umanwizard correct! We want to use the same code for both with as little duplication as possible, but (unlike rustc), we must be able to lazily resolve stuff inside functions.

[jonas-schievink]

Turns out this wasn't required to support inner items, but it would still be helpful to clean up name resolution as described here.