Stream: t-compiler/wg-incr-comp

Topic: Design of HIR


view this post on Zulip cjgillot (Mar 08 2021 at 20:22):

Is there a design document for the HIR since the work in https://github.com/rust-lang/compiler-team/blob/master/content/minutes/design-meeting/2019-12-06-end-to-end-query-PRs.md and https://zulip-archive.rust-lang.org/131828tcompiler/75795designmeeting20191206.html#182771577 ?
I was just beginning my involvement in rust at the time, so I did not really follow which decision was reached.

view this post on Zulip mw (Mar 09 2021 at 10:55):

IIRC, we went some of the way towards end-to-end queries with https://github.com/rust-lang/rust/pull/68944, but not further because there was no actual plan on what things should look like beyond that. So an actual design document would be great. I think in order to come up with a good design, it would make sense to strive for (1) documenting how macro expansion and name resolution (should) work, (2) getting the data structures (i.e. the things ending up as query results) right, and from there (3) come up with a way of formulating a querified implementation of the two. I have a gut feeling that (for historical reasons) hygiene, macro expansion, and handling of spans are more entangled than they need to be.

view this post on Zulip cjgillot (Apr 02 2021 at 19:38):

Here is a write-up of my thoughts on end-to-end queries
https://hackmd.io/CCNBA1L5R5Oxc72HtSwxuw?view

The proposed design is maximalist, going to end-to-end queries. Some restricted versions are certainly possible. The graph at the end summarizes how queries fall together (in pseudo-code).
Please tell me if I missed something on the behaviour of name resolution, my description is probably overly simplistic. I kind of swept macro expansion under the rug, I can definitely expand that part.

view this post on Zulip bjorn3 (Apr 02 2021 at 19:50):

I don't think queries can support the fix-point name resolution + macro expansion that is necessary. Macro expansion can create new macros which are then used for macro expansion. Macro invocations can change from unambiguous to ambiguous back to unambiguous.

(using decl macro 2.0 for simplicity sake)

mod a {
    pub macro foo() {}
}

mod b {
    macro bar() {
         pub macro foo() {}
    }
    bar!();
}

mod c {
    pub macro baz() { use crate::c::foo; }
    pub macro foo() {}
}

use a::*;
use b::*;
c::baz!();
foo!();

At first foo!() seems to resolve to a::foo. Then when bar!() is expanded, it becomes ambiguous and finally when baz!() is expanded it will definitively resolve to c::foo.

view this post on Zulip cjgillot (Apr 02 2021 at 20:19):

So, IIUC, macro expansion must be performed in file order to be well-defined. To expand foo!(), we can query the expanded AST from all the code above it, and resolve foo from that state. Does it answer to your example?

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 20:45):

But in that example foo!() actually resolves to a::foo

view this post on Zulip cjgillot (Apr 02 2021 at 20:50):

I don't get it: which is the correct resolution?

view this post on Zulip Joshua Nelson (Apr 02 2021 at 21:02):

it resolves to a::foo: https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=77863cd0d5c0f23451bfbd10c95fbbf5

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:04):

rust-analyzer gets it wrong

view this post on Zulip Mario Carneiro (Apr 02 2021 at 21:05):

is this an intentional feature?

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:05):

but I'm not sure which one is actually the intended outcome, in principle the explanation above makes sense for why this should be c::foo

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:05):

@Vadim Petrochenkov any clues? :)

view this post on Zulip Mario Carneiro (Apr 02 2021 at 21:05):

Is it possible to do name resolution first, before expansion?

view this post on Zulip Joshua Nelson (Apr 02 2021 at 21:06):

no, expansion affects name resolution

view this post on Zulip Joshua Nelson (Apr 02 2021 at 21:06):

macros can define modules and items

view this post on Zulip Joshua Nelson (Apr 02 2021 at 21:06):

cfg_if is the most common example

view this post on Zulip cjgillot (Apr 02 2021 at 21:06):

I re-read the documentation https://rustc-dev-guide.rust-lang.org/macro-expansion.html, and resolution is in algorithm order: resolutions that do not come from expansions take precedence.

view this post on Zulip bjorn3 (Apr 02 2021 at 21:07):

If I use macro_rules! instead of macro for the use, I get an ambiguous import error.

view this post on Zulip Mario Carneiro (Apr 02 2021 at 21:08):

I tried to set up the test with macro_rules but the scoping around modules is different

view this post on Zulip bjorn3 (Apr 02 2021 at 21:08):

macro is hygienic by default for items too, so the use never leaked out of the macro expansion.

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:09):

cjgillot said:

I re-read the documentation https://rustc-dev-guide.rust-lang.org/macro-expansion.html, and resolution is in algorithm order: resolutions that do not come from expansions take precedence.

hmm, yeah, that does make sense

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:12):

ah, this one works as I'd expect:

mod a {
    pub macro foo() {}
}

mod b {
    macro bar() {
         pub macro foo() {}
    }
    bar!();
}

mod c {
    pub macro baz($n:ident) { use crate::c::$n; }
    pub macro foo() { fn main() { println!("hello") } }
}

use a::*;
use b::*;
c::baz!(foo);
foo!();
error[E0659]: `foo` is ambiguous (glob import vs macro-expanded name in the same module during import/macro resolution)
  --> src/main.rs:22:1
   |
22 | foo!();
   | ^^^ ambiguous name
   |
note: `foo` could refer to the macro imported here
  --> src/main.rs:15:35
   |
15 |     pub macro baz($n:ident) { use crate::c::$n; }
   |                                   ^^^^^^^^^^^^
...
21 | c::baz!(foo);
   | ------------- in this macro invocation
note: `foo` could also refer to the macro imported here
  --> src/main.rs:19:5
   |
19 | use a::*;
   |     ^^^^
   = help: consider adding an explicit import of `foo` to disambiguate
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

view this post on Zulip Jonas Schievink [he/him] (Apr 02 2021 at 21:12):

so the r-a issue is merely us not supporting macro 2.0 hygiene yet

view this post on Zulip Vadim Petrochenkov (Apr 02 2021 at 21:12):

bjorn3 said:

macro is hygienic by default for items too, so the use never leaked out of the macro expansion.

This.
foo!(); is a::foo!(); because all other foos are hidden by hygiene.

view this post on Zulip Vadim Petrochenkov (Apr 02 2021 at 21:41):

resolution is in algorithm order: resolutions that do not come from expansions take precedence

That's news to me. Where is this written?

view this post on Zulip cjgillot (Apr 02 2021 at 21:44):

It's not written that way, it's just how I understood it, probably poorly.

view this post on Zulip cjgillot (Apr 02 2021 at 21:57):

This is what I get from the doc. The algorithm is structured as a work queue, in which to-be-expanded macros do not participate in resolution, and newly expanded macro always go to the end of the work queue.
By indexing the macro invocations with ExpnId in the order of their discovery, resolution only needs to considers macros created by expansions that happened earlier in ExpnId order. Does this seem right?

view this post on Zulip Vadim Petrochenkov (Apr 03 2021 at 09:43):

@cjgillot
Here's the expansion order description that I usually refer to - https://github.com/rust-lang/rust/pull/53778#issuecomment-419224049 (it's linked from somewhere in dev guide, but probably easy to miss).

view this post on Zulip Vadim Petrochenkov (Apr 03 2021 at 09:46):

ExpnIds are not fully ordered because they form a tree, and the expansion results should not depend on which specific acceptable order is used during specific compilation session (because the specific order may change if we change the compiler, or use some incremental expansion).

view this post on Zulip Vadim Petrochenkov (Apr 03 2021 at 09:48):

resolution only needs to considers macros created by expansions that happened earlier in ExpnId order.

"earlier" -> "never later" (given the previous message).

view this post on Zulip Vadim Petrochenkov (Apr 03 2021 at 09:50):

I'm pretty sure that the work queue algorithm used now is not correct (as the linked comment mentions), even if the incorrectness doesn't show up in practical cases.

view this post on Zulip cjgillot (Apr 03 2021 at 14:41):

Thank you @Vadim Petrochenkov, this comment is really helpful!
If we delay reporting the ambiguity, I think we can actually describe an incremental resolution algorithm:

  1. Look for candidates in the parent expansions to the invocation I.
    This corresponds to the very conservative shadowing mode. As it is strictly more conservative, it will find strictly less candidates. As all candidates in this search are found in parents expansions of I, there is never any ambiguity, and we just need to find the closest in terms of scoping.

  2. If we have a candidate A, we have already considered all resolutions that come from a parent expansion of A or I (by transitivity). Therefore, any other candidate must be ambiguous. Do not bother looking for them, and return A.

  3. Otherwise, we need to find a candidate that is not in a parent expansion of I. We walk all the expansion points earlier to I in reverse order, expand them, and return the first candidate A we find. We have already considered all candidates from parent expansions of A in (1), so any resolution we find later will be ambiguous.

Later in the compilation, HIR lowering will actually need to compute the full resolver, and the ambiguities we ignored can be reported at this point.


Last updated: Oct 21 2021 at 21:46 UTC