Stream: t-compiler/rust-analyzer

Topic: Path Resolution in r-a


kev (Jan 02 2021 at 19:01, on Zulip):

Read the resolve_path_fp_with_macro that @Florian Diebold sent yesterday. For anyone interested, I think this is mostly correct in broad strokes. If any mistakes are found, please let me know!

These are the following path types:

Dollar Crate

Example: use $crate::foo::bar

Usage: used in macros.

Crate

Example: use crate::foo::bar

Usage: When you want to import something in the crate. It is like an absolute path from the current crate to the item you want to import.

Plain

Example: use foo::bar

Usage: You can use it to import an external dependency or a module. Local modules take precedence, here so if you had an external dependency called foo, you will need an absolute Path.

Absolute

Example: use ::foo::bar

Usage: You can use it to import an external dependency. It is similar to crate, however it is the absolute path at the crate graph level. foo in this case is a crate and not a module.

Super

Example: use super::foo::bar

Usage: If you don't want to reference the parent module, you can use Super. It is like the .. in a path.


The algorithm to solve a path is a two step process.

The first step is processing the first segment and figuring out: - path type, the crate the path is referencing to and the namespace of the first segment.

Notes on Path type

The only path types which can reference an external dependency is Absolute and Plain. Note also that Absolute cannot use crate, so the following paths are usually not valid : use ::crate::foo::bar use ::$crate::foo::bar.

Notes on Which Crate

When we see a Plain Path, we first look if the first segment is referring to another module. If not, we then look into our external dependencies which is located in extern_prelude.

When we see an absolute path, we immediately look into the extern_prelude for the crate it is referring to. Since a crate cannot depend on itself(excluding tests/dev-builds), you will not be able to reference the current crate with an absolute path.

When we see a Super Path, we first look up the module which had the import statement to begin with. Then we look at it's parent, which is a field that the ModuleData data structure stores.

Skips macros to simplify the explanation, also because I've been ignoring them while reading the codebase for simplicity, so anything I assume will most likely be wrong


Finished Step one

So given the following path use foo::bar::world at the end of step one, we would have:

For example, If foo was a module the NameSpace of foo would be ModuleDef{crate_Id : 0, module_id : 2} . We can use this information to get the items which are visible from foo.

Step Two

The second step is to iterate through the other segments until we get to the end. So in foo::bar::hello we take the NameSpace of foo which was ModuleDef{crate_Id : 0, module_id : 2} and we use that to search for a visible item named bar. We know exactly where to look too because of the Crate_ID being present. Once we've found bar in the foo namespace, we then set the bar namespace as the current namespace and repeat until we are finished.

kev (Jan 02 2021 at 19:03, on Zulip):

For debugging and learning, I created a test in crates/hir_def/src/nameres/tests.rs and pasted the following in a test function:

    compute_crate_def_map(
        r#"
        //- /lib.rs crate:main deps:foo
        mod a;
        mod b;
        pub mod foo;
        pub use ::foo::hello;

        //- /foo/mod.rs
        pub mod hello;
        pub struct Foo;

        //- /a/mod.rs
        pub mod hello;
        pub struct Foo;

        //- /b/mod.rs
        pub mod hello;
        pub struct Foo;

        //- /foo/hello.rs
        pub struct Baz;

        //- /lib.rs crate:foo
            pub fn hello() {};
        "#,
);
kev (Jan 02 2021 at 19:05, on Zulip):

You can modify the use statement to trigger different branches in resolve_path_fp_with_macro and add debug statements on curr_ns and segment to see the changed output

kev (Jan 02 2021 at 19:06, on Zulip):

I noticed that if there is an error, like the dependency is missing , then the test will silently return nothing though

kev (Jan 02 2021 at 19:21, on Zulip):

Hmm noticed I was not completely finished and am a bit perplexed as to why this line is needed: https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/hir_def/src/nameres/collector.rs#L515

kev (Jan 02 2021 at 19:22, on Zulip):

If I import a function only, then I think the macros namespace would be None and the Values namespace in PerNS would also be None? But it should be seen as Resolved, unless I'm missing something with the PerNs structure?

Florian Diebold (Jan 02 2021 at 20:43, on Zulip):

a function exists only in the values namespace, actually.

let's say you import foo and it initially resolves to the function foo, then it may later still resolve to a type additionally: e.g. something like this

kev (Jan 02 2021 at 20:52, on Zulip):

Florian Diebold said:

a function exists only in the values namespace, actually.

let's say you import foo and it initially resolves to the function foo, then it may later still resolve to a type additionally: e.g. something like this

Yeah sorry, you are right, I was reading the debug wrong:

Segment : Name(Text("hello")) for Namespace : PerNs { types: None, values: Some((FunctionId(FunctionId(0)), Public)), macros: None }
kev (Jan 02 2021 at 20:53, on Zulip):

Florian Diebold said:

a function exists only in the values namespace, actually.

let's say you import foo and it initially resolves to the function foo, then it may later still resolve to a type additionally: e.g. something like this

This does not answer the initial question though? Regarding this: https://github.com/rust-analyzer/rust-analyzer/blob/master/crates/hir_def/src/nameres/collector.rs#L515

From the code I pasted macros and types is None, so then the import would be seen as not resolved IIUC?

Hmm not sure what I am misunderstanding about that line

Florian Diebold (Jan 02 2021 at 20:56, on Zulip):

let's say you do use some_module::foo;, then in the first loop of import resolution it may only resolve to a value, but later it may also resolve to a type. that's why Indeterminate is returned there; the way import resolution works is that it loops until everything is fully resolved or nothing changes anymore. PartialResolvedImport::Resolved would mean "this is fully resolved and can't change anymore"

Florian Diebold (Jan 02 2021 at 20:58, on Zulip):

that's also why it returns Resolved when the import comes from a different crate; in that case, the resolution can't change in any future loops

kev (Jan 02 2021 at 20:58, on Zulip):

Florian Diebold said:

let's say you do use some_module::foo;, then in the first loop of import resolution it may only resolve to a value, but later it may also resolve to a type. that's why Indeterminate is returned there; the way import resolution works is that it loops until everything is fully resolved or nothing changes anymore. PartialResolvedImport::Resolved would mean "this is fully resolved and can't change anymore"

Oh right, so Indeterminate means that it is Resolved, but there is space for other things in the other namespaces

Florian Diebold (Jan 02 2021 at 20:59, on Zulip):

Oh right, so Indeterminate means that it is Resolved, but there is space for other things in the other namespaces

well, it could be Resolved with space in other namespace if the import comes from a different crate, since we know in that case it can't change

Florian Diebold (Jan 02 2021 at 21:00, on Zulip):

Indeterminate means "maybe there'll be more if we resolve some other imports first"

kev (Jan 02 2021 at 21:02, on Zulip):

Florian Diebold said:

that's also why it returns Resolved when the import comes from a different crate; in that case, the resolution can't change in any future loops

Ah this was going to be my follow-up question :)

do you mean that it is impossible to import a foo function and foo macro from another crate?

so for example:

use other_crate::foo (function);
use other_crate::foo (macro);

would be impossible, so once we resolve the function, it's impossible to resolve the macro unless it is aliased?

Florian Diebold (Jan 02 2021 at 21:03, on Zulip):

well just the first use other_crate::foo will import both the function and the macro

kev (Jan 02 2021 at 21:04, on Zulip):

Florian Diebold said:

well just the first use other_crate::foo will import both the function and the macro

Ah right, found my error

kev (Jan 02 2021 at 21:09, on Zulip):

So IIUC,

When you do use other_crate::foo once we Resolve this, the namespace cannot change, because it is not valid to do this:

use other_crate::foo;
use my_mod::foo;

In the above there is a namespace clash.

However, if it comes from a local module, then we could possibly populate the namespace further. For example:

use my_mod::foo (function);

fn bar () {
  let f : foo = foo{}
}
kev (Jan 02 2021 at 21:11, on Zulip):

So we've imported foo as a function and we've also used it as a type, so foo exists within the type and value namespace

kev (Jan 02 2021 at 21:13, on Zulip):

Hmm I think I am wrong actually, because in that instance, we did not import the foo type, we just used it as a type

Hmm I think this makes a bit more sense:

@Florian Diebold does this sound remotely correct?

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

well the point is that the use my_mod::foo could turn out to also be a type. for example

mod a { pub fn foo() {} }
pub use self::a::*;
pub use self::c::*;
mod b { use super::foo; }
mod c { pub use super::bar as foo; }
mod d { pub struct bar {} }
pub use self::d::*;

if we resolve the imports in the order as written in the first iteration, the use super::foo will first only resolve to the function foo because we haven't gotten to c and d yet. after a first loop, we know bar means the type bar in the top module; then in the second module, we can resolve the pub use super::bar as foo, which means we have an additional meaning for the pub use self::c::* as well

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

"using the function as a type" does not populate the type namespace

Florian Diebold (Jan 02 2021 at 21:20, on Zulip):

all of this mostly only matters in edge cases

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

it might be interesting to try changing that line to return Resolved and see which test cases fail ;)

kev (Jan 02 2021 at 21:34, on Zulip):

Florian Diebold said:

well the point is that the use my_mod::foo could turn out to also be a type. for example

mod a { pub fn foo() {} }
pub use self::a::*;
pub use self::c::*;
mod b { use super::foo; }
mod c { pub use super::bar as foo; }
mod d { pub struct bar {} }
pub use self::d::*;

if we resolve the imports in the order as written in the first iteration, the use super::foo will first only resolve to the function foo because we haven't gotten to c and d yet. after a first loop, we know bar means the type bar in the top module; then in the second module, we can resolve the pub use super::bar as foo, which means we have an additional meaning for the pub use self::c::* as well

Haha trying to understand this:

here

pub use super::bar as foo;

We import bar which is a Struct which is in the Type NameSpace and since we are aliasing it as foo then we now have foo being in Type namespace for mod c`

So at this point, we have foo being seen as a Type in mod c

Since we have:

pub use self::c::*;

We now have foo being seen as a Type which is the Bar struct from mod c and also foo being seen as a function from mod a

kev (Jan 02 2021 at 21:34, on Zulip):

sorry took me longer than I'd like to wrap my head around it

kev (Jan 02 2021 at 21:35, on Zulip):

Florian Diebold said:

it might be interesting to try changing that line to return Resolved and see which test cases fail ;)

thanks for the idea, going to try this now

kev (Jan 02 2021 at 21:59, on Zulip):

The test case was really helpful haha.

This is the test that fails, when we switch && to ||.

#[macro_export]
macro_rules! foo {
    ($x:ident) => { type $x = (); }
}

foo!(foo);
use foo as bar;

use self::foo as baz;
fn baz() {}
kev (Jan 02 2021 at 22:05, on Zulip):

So If the following code was an external dep, and we imported it, we would be given:

            bar: t m
            baz: t v m
            foo: t m

Which is why I believe Florian said that once we resolve an external dep, we can mark it as resolved. It's namespace would not change.

The snippet was taken from the test fn type_value_macro_live_in_different_scopes()

Last update: Jul 24 2021 at 19:30UTC