Stream: t-compiler/rust-analyzer

Topic: Macros VS salsa

matklad (Mar 22 2019 at 09:36, on Zulip):

I've rewritten name resolution to account for macros, and there's this curious bit of code there:

I wonder if we can get some help from salsa to make this better.

The problem is hard to explain, but the components are as follows:

Because nameres is just a single query, we can't call expand query: expand calls back into name resolution to figure out the definition of macro. So, during nameres we basically call expand query function directly, bypassing salsa.

This is bad for two reasons:

I wonder if we can do better here...

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

the comment there says "we can't identify macro_call without adding the whole state of name resolution as a parameter to the query"

pnkfelix (Mar 22 2019 at 13:13, on Zulip):

would some subset substructure of the name resolution state suffice? Would identifying that subset and factoring it out help?

matklad (Mar 22 2019 at 13:19, on Zulip):

So, if we literally add "the set of defined macros" to the query, than we'll need to do a lot of hashing/comparisions to find the key in the hash map. I think even if we compress this, it's still would be a huge value, not really fit for being a salsa's key.

matklad (Mar 22 2019 at 13:20, on Zulip):

It would be interesting to somehow to try to add this state implicitly. For example, instead of passing the literal set of scopes, we can pass the integer stage of name resolution (that idea with explicit fixed point)

pnkfelix (Mar 22 2019 at 13:41, on Zulip):

hmm. its huge because it wouldn't be just the macros names (or unique identifiers), but also their definitions?

pnkfelix (Mar 22 2019 at 13:41, on Zulip):

or are you saying that even just a set of unique id's is not an appropriate salsa key?

matklad (Mar 22 2019 at 13:43, on Zulip):

it wouldn't be only macros, because macro might be called with a path log::error!(). Here, the state should include enough info to understand what log is

matklad (Mar 22 2019 at 13:45, on Zulip):

If we do include state, the other problem would be that the code outside of name resolution would probaly want to use the final state anyway.

That is, code inside nameres calls:

expand_macro(currest_scopes, foo)

Code outside of nameres calls:

expand_macro(final_scopes, foo)

So, these are two queries, and we must ensure manually that they give the same result (which probably means that current_scopes is subset of final_scopes).

Florian Diebold (Mar 22 2019 at 13:48, on Zulip):

I think some kind of dataflow or fixpoint computation support from salsa will be necessary to properly solve this

matklad (Mar 22 2019 at 13:49, on Zulip):

indeed, ping @nikomatsakis :)

nikomatsakis (Mar 22 2019 at 15:30, on Zulip):

So, the way I've been expecting to solve this in the case of trait resolution

nikomatsakis (Mar 22 2019 at 15:30, on Zulip):

Is to pull that sort of "dataflow/fixed-point" state out into a separate mechanism

nikomatsakis (Mar 22 2019 at 15:30, on Zulip):

Specifically, I was intending to have a volatile query

nikomatsakis (Mar 22 2019 at 15:30, on Zulip):

Which creates the state

nikomatsakis (Mar 22 2019 at 15:31, on Zulip):

and then other queries that reach into that state to get their result

nikomatsakis (Mar 22 2019 at 15:31, on Zulip):

therefore, in a new revision, all of those dependent queries will be invalidated, and the state will be recomputed from scratch

nikomatsakis (Mar 22 2019 at 15:31, on Zulip):

Basically, this doesn't fit salsa's "tree-based" model

nikomatsakis (Mar 22 2019 at 15:31, on Zulip):

I do think it might be plausible to extend salsa to accommodate richer cases, but I feel like I want to have a few examples

nikomatsakis (Mar 22 2019 at 15:31, on Zulip):

before we start to generalize

nikomatsakis (Mar 22 2019 at 15:32, on Zulip):

(@eddyb has often mentioned building on the way that GLL handles cycles here to do a better job; I confess I don't really understand what they're proposing yet, but I would like to)

nikomatsakis (Mar 22 2019 at 15:32, on Zulip):

That said, I remain a bit nervous -- e.g., within chalk, the way to handle cycles that occur in trait resolution depends on the trait

nikomatsakis (Mar 22 2019 at 15:33, on Zulip):

i.e., I don't know that there is a "one size fits all" answer here

nikomatsakis (Mar 22 2019 at 15:33, on Zulip):

and maybe that's fine, but I'd like to have a better picture of the "menu"

nikomatsakis (Mar 22 2019 at 15:33, on Zulip):

so maybe @matklad we should step back and talk about -- ignoring salsa for a second -- can we build up a manually incremental state that salsa can query into, but where we can reason about the correctness?

nikomatsakis (Mar 22 2019 at 15:34, on Zulip):

This is exactly the work I imagined doing as part of the name resolution crate, and I have some thoughts about it, but it'd be helpful to have a bit of an abstract specification for how things should work

nikomatsakis (Mar 22 2019 at 15:38, on Zulip):

(I definitely don't think that expanding salsa's keys with the state -- which basically memoizes all the steps towards convergence -- feels right.)

nikomatsakis (Mar 22 2019 at 15:39, on Zulip):

Maybe @matklad it'd be helpful to schedule some time to dig into this in more depth? Feels like a good topic for a zoom call (recorded, naturally ;).

matklad (Mar 22 2019 at 17:49, on Zulip):

@nikomatsakis yeah, a zoom call seems like a good idea.

My current thoughts is that this is not necessary about fixed-point iteration queries per se. The problem here is that you can't assign IDs based on the current computation. I have a rough idea about a toy example which shows this problem but which doesn't involve fixed point queries. This toy example seems to be fixed by making queries more fine-grained though, and fixed-point is why we can't apply this strategy in the resolution case.

I've been thinking about "monotone queries" to handle this. Let's say that we have a big query Q which computes a map, with the constraint that it never overwrites entries in the map. As Q is being computed, it calls some sub queries. I think it could be sound to allow these sub queries to peek into the in-progress map.

So, let's say Q calls into X, which uses info from partially constructed Q and an input t. We call Q in the current state, which computes the full map, invoking X in the process. X observes partial mapping. Now let's change the input t. I think we can recompute X and, if it returns the same result, we can avoid recomputing Q. Note that X naturally will have access to the full result of Q this second time, but, due to mapping being monotonic, it should be OK.

Or should we add "timestamps" to values in the map as well? Well, this needs brainstorming with a whiteboard, but I think I explained the general idea :) : we allow intermeidiate queries to peek into the result of in-progress queries and hopefully define some monotonicity conditions under which this is actually sound

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

In terms of macro expansion, the case I am thinking this this: We have a lazy-static call:

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");

which we exapnd during name resolution. Than, the user uncomments the line. Instead of re-runing the whole of name resolution (which is done by the current impl), we only re-run lazy_static re-expansion. We notice that it returns the same "result": the actual expansion will be different, of course, but we project only the set of top-level names out of it, and that is still just HASHMAP.

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

So we say that the result of name-resolution are the same

nikomatsakis (Mar 22 2019 at 19:57, on Zulip):

@matklad ok I will try to read this and comment shortly, but let's also schedule some sync time to talk it over. Here is a doodle poll with some options I can do.

nikomatsakis (Mar 22 2019 at 21:43, on Zulip):

OK, I'm going to schedule 15:00 Boston time -- I'll add to the rustc calendar.

nikomatsakis (Mar 22 2019 at 21:45, on Zulip):

Calendar event is here, with a Zoom link

detrumi (Mar 25 2019 at 18:17, on Zulip):

^ That's in 45 minutes

nikomatsakis (Mar 25 2019 at 18:51, on Zulip):

Just to check -- do we want to chat over Zoom over Zulip? I'm having trouble finding a closed room to do video conf at this co-working space right now (all in use) but that's ok

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

I think audio would work better for brainstorming, but no strong preferences

matklad (Mar 25 2019 at 18:54, on Zulip):

actually, audio would be slightly inconvenient for me as well

matklad (Mar 25 2019 at 18:54, on Zulip):

so, no preferences

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

I'm wondering a bit what our agenda is

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

seems like we should start by talking through a bit what you think you want?

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

let's try zoom

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

I also have a sense it may be slightly better for this purpose

matklad (Mar 25 2019 at 18:55, on Zulip):

yeah, I think we should start with goals and assumptions

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

(although a lot of times I am surprised by how good zulip can be)

nikomatsakis (Mar 25 2019 at 18:55, on Zulip):

so maybe i'm wrong :)

nikomatsakis (Mar 25 2019 at 18:58, on Zulip):

(regardless, I say we stick with zoom since that's what the calendar invite says...)

Florian Diebold (Mar 25 2019 at 18:59, on Zulip):

I'll try to take part but be partly AFK

detrumi (Mar 25 2019 at 19:00, on Zulip):

I'm joining, if i can get in the zoom meeting

nikomatsakis (Mar 25 2019 at 19:00, on Zulip):

Paper doc

matklad (Mar 25 2019 at 19:35, on Zulip):

Awesome, thanks a lot @nikomatsakis ! I was banging my head against this for several days, and we seem to come to the solution in 30-ish minutes :) Hope it actually works :fingers_crossed:

detrumi (Mar 25 2019 at 19:35, on Zulip):

There can only be so many walls to bang your head against :slight_smile:

matklad (Mar 25 2019 at 19:36, on Zulip):

To recap, the key idea is to identify the macro not by invocation alone (what I was doing), but by a tuple of (macro_definition, macro invocation). That way, macro expansion don't need to call into nameres, because it already knows the definition! Seems obvious in retrospect :)

matklad (Mar 25 2019 at 19:37, on Zulip):

There can only be so many walls to bang your head against

Well, that depends on the relative speeds of language design and RLS teams :D

pnkfelix (Mar 25 2019 at 20:56, on Zulip):

(Sorry to have missed the mtg; multiple factors including but not limited to my misunderstanding of when DST ends here)

matklad (Mar 26 2019 at 10:11, on Zulip):

It seems magical: to implement this idea, I had to basically remove code, and it worked on the first try:

matklad (Mar 27 2019 at 14:04, on Zulip):

@nikomatsakis do you want to upload the video?

nikomatsakis (Mar 27 2019 at 14:14, on Zulip):

sure I can do that

nikomatsakis (Mar 27 2019 at 15:05, on Zulip):

Video will be live at this URL (but it's still uploading)

Last update: Jul 27 2021 at 21:15UTC