Stream: t-compiler/wg-rls-2.0

Topic: New name resolution


matklad (Mar 02 2019 at 21:00, on Zulip):

I am starting on integrated name-resoltion/macro-expansion in this branch: https://github.com/rust-analyzer/rust-analyzer/tree/name-resolution-2

I still don't have a clear picture in my head about how this all should work together, hopefully writing some code should make this clearer.

matklad (Mar 02 2019 at 21:02, on Zulip):

The current plan is to center nameres around CrateDefMap datastructure.

In theory, CrateDefMap should contain information about all top-level declarations inside the macro-expanded crate. It should also be a home for the tree of modules. We will populate CrateDefMap in one go, but we should't recalculate it unless the user types something on the module top-level.

matklad (Mar 05 2019 at 17:52, on Zulip):

So, I must confess I am feeling a little bit like "name resolution is stuck" error :D

matklad (Mar 05 2019 at 17:53, on Zulip):

I haven't written any working code, but made this comment explaining the proposed algorithm and imitations I am running into: https://github.com/rust-analyzer/rust-analyzer/blob/a5aa2fe7bb25fa0cb3a4f8c67d21121eb0fbb73d/crates/ra_hir/src/nameres/crate_def_map.rs#L1

matklad (Mar 05 2019 at 17:53, on Zulip):

The problem I am trying to solve is that I want to not rerun global name resolution after a change inside item body.

matklad (Mar 05 2019 at 17:54, on Zulip):

Without macros, this works by placing an intermediate query between parsing and name res, which returns a set of top-level items.

matklad (Mar 05 2019 at 17:54, on Zulip):

With macros, things get interesting. Consider this code:

lazy_static! {
    static ref HASHMAP: HashMap<u32, &'static str> = {
        let mut m = HashMap::new();
        m.insert(0, "foo");
        m.insert(1, "bar");
        m.insert(2, "baz");
        m
    };
}
matklad (Mar 05 2019 at 17:56, on Zulip):

Ideally, we should not re-run name resolution if we remove m.insert(1, "bar"); line: we should re-run only the lazy_static macro itself, check that it produced the same items as the last time, and be done with it.

matklad (Mar 05 2019 at 17:56, on Zulip):

This wont work for naive intermediate query, which stores input token trees for macro calls.

matklad (Mar 05 2019 at 17:58, on Zulip):

The fix would be to apply intermediate query recursively: instead of storing token tree itself in the result, store only some macro ID, and than have an expand macro id to top-level items query.

matklad (Mar 05 2019 at 17:59, on Zulip):

However, I don't think I can assign an id to the macro invocation: assigning Ids needs results of name resolution, and we are running name resolution right now! That is, the HirFileId trick we use today in ra to identify macros works only because macros are not really a part of name resolution

matklad (Mar 05 2019 at 18:00, on Zulip):

cc @WG-rls2.0 this is an interesting question :) Does anybody understands the problem I am trying to solve? Do we have any suggestions? :)

Florian Diebold (Mar 05 2019 at 18:01, on Zulip):

Why does assigning IDs require the results of name resolution? can't you do an 'nth macro in file x' type of ID?

matklad (Mar 05 2019 at 18:02, on Zulip):

I can do that if x is a FileId. If x is a file produced by a macro, I am unsure how to do that

Florian Diebold (Mar 05 2019 at 18:02, on Zulip):

though the query expanding that would depend on name resolution then, wouldn't it... :thinking:

matklad (Mar 05 2019 at 18:02, on Zulip):

yeah, precisely

matklad (Mar 05 2019 at 18:05, on Zulip):

I see two possible "solutions" here:

Jeremy Kolb (Mar 05 2019 at 18:16, on Zulip):

How bad would this be in practice?

matklad (Mar 05 2019 at 18:17, on Zulip):

worst case pretty horrible

#[cfg(test)]
mod tests {
    loooots of code
}
matklad (Mar 05 2019 at 18:17, on Zulip):

cfg(test) here is more or less a macro that applies to the following item

matklad (Mar 05 2019 at 18:17, on Zulip):

similarly, derives are macros

Jeremy Kolb (Mar 05 2019 at 18:24, on Zulip):

so I don't know if this would work but could you assign ids based on something besides name res? like... a weird hash of all potential names?

Jeremy Kolb (Mar 05 2019 at 18:24, on Zulip):

make it a bit fuzzy, sort of a best guess

matklad (Mar 05 2019 at 18:27, on Zulip):

we don't assign ids based on name refs. An ID is an interned location, where location is something like "the nth macro in the foo file"

matklad (Mar 05 2019 at 18:28, on Zulip):

for macro expansion, locations should contain a macro expansion backtrace "to find this thing, go to the nth macro in file foo, than to kth macro inside that macro's expansion, then to the mth item in the second expansion".

matklad (Mar 05 2019 at 18:29, on Zulip):

And we can't use such ids until macro expansion is fully complete, if we do macro exapnsion in a single query. If we do macro expansion as fine-grained queries this works, but fine-grained queries don't work with fixed-point iteration nature of macro expansion

matklad (Mar 05 2019 at 18:31, on Zulip):

So, the bad intrraction here is that we want "expand single macro" to be a query, such that we can project items out of the full syntax trees and ignore local modifications. At the same time, we have to use "expand all the macros" mega query to avoid cyclic queries.

detrumi (Mar 05 2019 at 18:33, on Zulip):

Why do you get cyclic queries then? Because macros can bring names into scope that change behavior?

matklad (Mar 05 2019 at 18:34, on Zulip):

More or less: at it's heart, nameresoluton and macro-expansion is a fixed point iteration style algorithm. If you implement this algorithm using a naive recursion, you can get an infinite loop

Florian Diebold (Mar 05 2019 at 18:35, on Zulip):

I wonder if Salsa could add special support for 'fixpoint' queries

matklad (Mar 05 2019 at 18:35, on Zulip):

https://github.com/salsa-rs/salsa/issues/9 :-)

Florian Diebold (Mar 05 2019 at 18:35, on Zulip):

aha :)

matklad (Mar 05 2019 at 18:35, on Zulip):

I am not sure what "salsa-style fixed point" means though...

Florian Diebold (Mar 05 2019 at 18:37, on Zulip):

yeah...

Florian Diebold (Mar 05 2019 at 18:38, on Zulip):

Why do you get cyclic queries then? Because macros can bring names into scope that change behavior?

yes, to expand a macro we need to resolve its name first, and to do name resolution we need to expand macros, so naively expressing that in queries leads to a cycle immediately...

detrumi (Mar 05 2019 at 18:39, on Zulip):

Right, but there should be some "correct" order in which to resolve things

detrumi (Mar 05 2019 at 18:40, on Zulip):

Though maybe then you lose the opportunity to look at a piece of code independently, if it requires resolution of another part first

Florian Diebold (Mar 05 2019 at 18:43, on Zulip):

maybe the resolution of the macro could be part of the input of the query? so we'd have a expand(TokenTree, ResolvedMacro) -> TokenTree query

Florian Diebold (Mar 05 2019 at 18:44, on Zulip):

oh, but the result of that query would change, of course

Florian Diebold (Mar 05 2019 at 18:44, on Zulip):

though there could be a lowering step after that

matklad (Mar 05 2019 at 18:45, on Zulip):

wait, that sounds like it could work?

Florian Diebold (Mar 05 2019 at 18:45, on Zulip):

so expand(LoweredMacroCall, ResolvedMacro) -> Vec<LoweredModuleItems>

matklad (Mar 05 2019 at 18:45, on Zulip):

got to run, will think about htat

matklad (Mar 05 2019 at 18:47, on Zulip):

hm, no :(

matklad (Mar 05 2019 at 18:47, on Zulip):

You still have TokenTree inside LoweredMacroCall

matklad (Mar 05 2019 at 18:47, on Zulip):

and LoweredMouduleItems can contains LowerMacroCalls

matklad (Mar 05 2019 at 18:48, on Zulip):

we need to fully expand -> Vec<LMI>, but to do that, we need to add nameres as an input to the query

Florian Diebold (Mar 05 2019 at 18:50, on Zulip):

the LoweredMacroCall could be just an ID, I think, but the return value is a problem, yeah...

Florian Diebold (Mar 05 2019 at 18:55, on Zulip):

Adding the whole macro scope to the input would be too much, I guess...

pnkfelix (Mar 07 2019 at 12:22, on Zulip):

(not sure if this even is possible) add an explicit fixed-point "round" to the query parameter. That way, we can refer, via queries to macros from current-round - 1.

have you given this more thought? I had thought this, or something like it (in terms of explicitly modeling the state of the fixed-point iteration in some fashion) would be necessary

matklad (Mar 07 2019 at 13:14, on Zulip):

yep, I've thought about this a bit: even with explicit round parameter, it seems like it could work.

Specifically, at round n a macro call will be represented not as a token tree, but as nth macro at x file at round n-1.

matklad (Mar 07 2019 at 13:15, on Zulip):

Though I think for the first implementation it makes sense to stick "typing inside a macro invalidates name resolution" strategy

matklad (Mar 07 2019 at 13:17, on Zulip):
matklad (Mar 12 2019 at 15:41, on Zulip):

Made some progress today for the simple "typing inside top-level macro invalidates the whole crate" approach

matklad (Mar 12 2019 at 15:43, on Zulip):

The actual name resolution is empty at the moment https://github.com/rust-analyzer/rust-analyzer/blob/8120d763459ce5dff32057d1d8ee972cd9b64d34/crates/ra_hir/src/nameres/crate_def_map/collector.rs#L91-L94 :D

However, there's some code that does recursive macro expansion of macro rules, while walking the crate

matklad (Mar 12 2019 at 15:46, on Zulip):

An interesting tidbit is that in this approach we are going to expand each macro call twice:

First, we eagerly expand the macro during name resolution, because we can't queryify it. Than, after name resolution is done, if some code needs to look inside the macro, it'll do so via query, which would use results of name resolution to resolve the macro and than do macro expansion the second time.

matklad (Mar 12 2019 at 15:47, on Zulip):

In other words, perhaps slightly less confusing, we need to assign DefIds during name resolution, and DefId mentions the file (which could be a macro) where the Def comes from.

matklad (Mar 12 2019 at 15:49, on Zulip):

We synthesize some files on the fly, so we need to make sure that later, when we query for Def's file, we get the same file we created during name resolution.

matklad (Mar 16 2019 at 17:26, on Zulip):

I think this is more or less ready now: https://github.com/rust-analyzer/rust-analyzer/pull/968

matklad (Mar 18 2019 at 09:53, on Zulip):

The PR is now merged, and I think it forms a pretty good basis for name resolution. @pnkfelix perhaps we could do a bit of a brainstorming about next steps for nameres librarification? It'd be cool to come up with a list of action items.

pnkfelix (Mar 18 2019 at 11:38, on Zulip):

okay I should probably take a closer look at the PR itself before I try to figure out what the next steps are

matklad (Mar 18 2019 at 11:50, on Zulip):

The PR is massive, because it also deletes existing impl. I suggest taking a look at the first commit (it has only the minimal infrastructure), and than at the current state of code in ra_hir/src/nameres

matklad (Mar 21 2019 at 10:56, on Zulip):

@pnkfelix did you get a chance to look at the PR?

pnkfelix (Mar 21 2019 at 10:56, on Zulip):

no sorry not yet

pnkfelix (Mar 21 2019 at 10:57, on Zulip):

I'll try to dive into it after I follow up on some unrelated performance issues with the compiler that I am looking at now

matklad (Mar 21 2019 at 11:01, on Zulip):

:thumbs_up: I'll do other stuff meanwhile then: it seems like name resolution could benefit from a somewhat principled planing/designing, etc :)

Last update: Nov 12 2019 at 15:30UTC