Stream: wg-traits

Topic: lazy-normalization and const generics


Aaron Hill (Sep 13 2019 at 20:13, on Zulip):

@nikomatsakis After experimenting locally, I'm not sure that canonicalizing the ParamEnv is the best idea. Since it replaces all regions variables with inference variables, we end up with a lot of region variables in places where we wouldn't otherwise have them.

The end result was the canonicalization was fairly 'infectious' - I had to start modifying a bunch of other places to handle canonicalizaiton and instantiating ParamEnvs. It's still not at the point where I can fully bootstrap the compiler

Aaron Hill (Sep 13 2019 at 20:14, on Zulip):

I'm starting to wonder if it might be easier to ban inference variables entirely in queries, and work backwards to see if we can find and eliminate them from where they creep in from lazy normalization (of constants)

Aaron Hill (Sep 15 2019 at 18:51, on Zulip):

I ran into https://github.com/rust-lang/rust/issues/64494 when working on this.

nikomatsakis (Sep 20 2019 at 20:26, on Zulip):

@Aaron Hill argh, I thought I wrote you back, but it appears I didn't..?

Anyway, the whole point of canon is to eliminate inference variables from queries, at least in a literal sense.

I'm pretty sure that canonicalizing is the right approach, but maybe you can point me at your branch?

Aaron Hill (Sep 20 2019 at 20:33, on Zulip):

@nikomatsakis After digging further, it turns out that some (maybe all?) of the need to canonicalize was coming from coherence checking. I ended up opening an issue regarding that: https://github.com/rust-lang/rust/issues/64494

I think we'll be able to sidestep this entire issue, and simultaneously get the proper coherence behavior, by adopting one of the two approaches I described in that issue.

Aaron Hill (Sep 20 2019 at 20:35, on Zulip):

Either forbidding const expression in 'where' clauses from depending on generic parameters, or doing a deliberate overapproximation with respect to coherence.

In either case, there shouldn't be any inference variables to worry about in const eval. Either there are no generic parameters (and therefore nothing to worry about replacing), or we treat the impl as 'potentially always applying' (in which case there is no need to actually do const eval during coherence checking)

Aaron Hill (Sep 20 2019 at 20:35, on Zulip):

Oops - I think I replied to the wrong thread

nikomatsakis (Sep 20 2019 at 20:36, on Zulip):

no, seems right

Aaron Hill (Sep 20 2019 at 20:37, on Zulip):

Still trying to figure out how zulup works ;P

Aaron Hill (Sep 20 2019 at 20:48, on Zulip):

I think I'll take a shot at implementing the conservative restriction suggested by @varkor, where we forbid arbitrary const expression in where clauses. That will allow us to skip const evaluation in where claues, and instead perform a direct comparison between const parameters when doing coherence checking.

If we ever expand which kinds of const expressions are allowed in 'where' claues, we could just modify the coherence check to take that into account.

nikomatsakis (Oct 04 2019 at 19:03, on Zulip):

@Aaron Hill so I started reading your branch

nikomatsakis (Oct 04 2019 at 19:04, on Zulip):

I am trying to remember

nikomatsakis (Oct 04 2019 at 19:04, on Zulip):

Do we have a canonical example yet of what "goes wrong"

nikomatsakis (Oct 04 2019 at 19:04, on Zulip):

in the absence of lazy norm

nikomatsakis (Oct 04 2019 at 19:05, on Zulip):

I've asked @eddyb and @oli about this before ..

nikomatsakis (Oct 04 2019 at 19:05, on Zulip):

/me goes back to do some more experiments

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

OK so

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

I returned to my original branch @Aaron Hill

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

fixed a bug in the type folding code for constants

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

that is what was causing the ICE -- not sure if you told me that already :)

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

now i'm seeing this

nikomatsakis (Oct 04 2019 at 20:29, on Zulip):
error[E0391]: cycle detected when processing `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
    |
note: ...which requires processing `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`...
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
note: ...which requires const-evaluating + checking `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`\
...
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
note: ...which requires const-evaluating + checking `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`\
...
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
note: ...which requires const-evaluating `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`...
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
    = note: ...which again requires processing `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`, com\
pleting the cycle
note: cycle used when const-evaluating `x86_64::sse2::<impl at /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:524:1: 544:2>::{{constant}}#0`
   --> /home/nmatsakis/.cargo/registry/src/github.com-1ecc6299db9ec823/ppv-lite86-0.2.5/src/x86_64/sse2.rs:526:27
    |
526 |     Self: MultiLane<[u32; 4]>,
    |                           ^
nikomatsakis (Oct 04 2019 at 20:29, on Zulip):

which I think is the cycle error I've been looking for

nikomatsakis (Oct 04 2019 at 21:17, on Zulip):
query stack during panic:
#0 [const_eval_raw] const-evaluating `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#1 [const_eval] const-evaluating + checking `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#2 [const_eval] const-evaluating + checking `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#3 [param_env] processing `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#4 [typeck_tables_of] processing `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#5 [const_eval_raw] const-evaluating `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#6 [const_eval] const-evaluating + checking `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#7 [const_eval] const-evaluating + checking `<x86_64::sse2::u32x4_sse2<S3, x86_64::YesS4, NI> as types::types::Vec4<u32>>::{{constant}}#0`
#8 [specialization_graph_of] processing `types::types::Vec4`
#9 [coherent_trait] coherence checking all impls of trait `types::types::Vec4`
#10 [analysis] running analysis passes on this crate
end of query stack
nikomatsakis (Oct 04 2019 at 21:29, on Zulip):

OK, I'm catching up now to the cycle you were talking about @Aaron Hill . I'll read that issue then leave some thoughts.

nikomatsakis (Oct 07 2019 at 22:19, on Zulip):

OK, I've been doing more exploration. Here is a doc with my current thoughts

Ben Lewis (Nov 11 2019 at 08:02, on Zulip):

Hello, I'm interested in having a look around and experimenting with this. The current branch that I'm working on is here: https://github.com/skinny121/rust/tree/lazy-norm-anon-const, I started off by building on top of both @Aaron Hill and @nikomatsakis branches and then started to implement the ConstEquate obligations outlined in the above doc.

The current problem I have is demonstrated with the following:

impl<T> A for [T; 5] {}
impl<T> A for [T; 6] {}

When it computs if these two impls overlap, It tries to equate the two constants, but with my current code, it can't due to type variables appearing within the substs of the unevaluated consts. The error message with -Z verbose is:
'conflicting implementations of trait A for type [_#0t; Const { ty: usize, val: Unevaluated(DefId(0:6 ~ main[317d]::{{impl}}[0]::{{constant}}[0]), [_#0t]) }]'.

Should we somehow filter the subsets so that they only contain the substitutions that are actually being used within the const?

varkor (Nov 14 2019 at 21:37, on Zulip):

did anything happen here @Ben Lewis, @nikomatsakis? I'm keen for this to move forward!

Ben Lewis (Nov 15 2019 at 01:29, on Zulip):

@varkor No I haven't done anything more since that comment.

nikomatsakis (Nov 16 2019 at 10:27, on Zulip):

Argh, @Ben Lewis sorry for not getting back to you. I've had your comment starred for some time.

nikomatsakis (Nov 16 2019 at 10:27, on Zulip):

Well, since Nov 11 :)

nikomatsakis (Nov 16 2019 at 10:28, on Zulip):

I think the nswer is that we ned to canonicalize those substs, but let me check out your branch itself. BTW, if you have time to press on this, maybe we should consider setting up a regular meeting time @Ben Lewis ? I'd like to actually answer you in a timely fashion.

Ben Lewis (Nov 17 2019 at 08:20, on Zulip):

I do have some time to dedicate to this, though my timezone is UTC +13, which might make it a little difficult.

Ben Lewis (Nov 17 2019 at 08:29, on Zulip):

BTW as a workaround, I used self.selcx.infcx().freshen(substs) to remove the inference variables which worked but canonicalizing it should better.

nikomatsakis (Dec 09 2019 at 22:19, on Zulip):

OK, well, @Ben Lewis, I'm back now and trying to get up to speed. Do you have more updates on that branch? I suppose I will schedule myself some time to review your branch and try to provide you with feedback to start (and/or help to push things along).

nikomatsakis (Dec 09 2019 at 22:20, on Zulip):

I'm at UTC-05:00, so that is indeed a formidable time difference. =)

Ben Lewis (Dec 10 2019 at 08:01, on Zulip):

Since my last comment, I have managed to get the standard library compiling and most of the tests passing. I did discover that my workaround above isn't sufficient and we do need to turn const_eval queries into canonical queries. For preparation for that, I opened https://github.com/rust-lang/rust/pull/66877 to reduce the number of places that invoking the underlying query.

Some other problems are:

nikomatsakis (Dec 10 2019 at 21:59, on Zulip):

@Ben Lewis great! I didn't get time to look into that today, I'm doing other reviewing now, but I'll try to earmark some time for tomorrow

nikomatsakis (Dec 17 2019 at 16:08, on Zulip):

@Ben Lewis do you plan to to turn constants into canonical queries (which I definitely agree is a good step) before the other changes on that branch? I'm reviewing the code there but there's a lot of diffs atm so I've not quite figured out if it's doing what I expected or not yet :)

Ben Lewis (Dec 20 2019 at 07:57, on Zulip):

@nikomatsakis Yes that's the plan, I have a branch with it mostly done(https://github.com/rust-lang/rust/compare/master...skinny121:canonicalize-const-eval?expand=1). I just need to figure out a couple of small issues first before I create a PR for it.

nikomatsakis (Dec 20 2019 at 11:00, on Zulip):

@Ben Lewis great, maybe I'll take a look at that branch first then

Ben Lewis (Dec 31 2019 at 19:47, on Zulip):

@nikomatsakis Do you think it would be a good idea for me to create a PR with my initial lazy normization work, but hide it behind a -Z lazy-normalization flag?

Ben Lewis (Dec 31 2019 at 19:51, on Zulip):

That would mean that the work can be broken down into multiple PRs to avoid having one massive PR. Also would allow it to be experimented with by others before we enable it by default.

nikomatsakis (Jan 06 2020 at 18:57, on Zulip):

@Ben Lewis I think you did so, right? seems good. I'm hoping to finish reviewing your first one today.

Ben Lewis (Jan 07 2020 at 06:37, on Zulip):

Yes, I went ahead and implemented it.

Last update: Jul 03 2020 at 17:40UTC