Stream: wg-traits

Topic: lazy-normalization


Aaron Hill (Aug 28 2019 at 21:43, on Zulip):

@nikomatsakis: I'm interested in working on lazy normalization. Is that currently blocked on further chalk integration, or are things at the point where it would be reasonable to start working on it?

nikomatsakis (Aug 29 2019 at 22:07, on Zulip):

@Aaron Hill a good question. I've been thinking that it would make sense to try and push it forward pre-Chalk. That was something I had planned to investigate tomorrow.

nikomatsakis (Aug 29 2019 at 22:07, on Zulip):

I was going to try and look for a "coding partner" to work on PRs; maybe that could be you? :)

Aaron Hill (Aug 30 2019 at 00:28, on Zulip):

Sounds good to me :)

ranweiler (Sep 02 2019 at 00:19, on Zulip):

Hey @Aaron Hill and @nikomatsakis. I'm trying to jump in on const generics generally.

I'm just getting up to speed with, well, everything, but it sounds like lazy normalization is part of the real near-term solution for some const generics bugs. I want to keep on top of work around lazy normalization, but don't want to step on anyone's toes.

If there's a way I can at least follow along with the lazy normalization development (and help out if desired), it would really help me contribute time effectively!

nikomatsakis (Sep 03 2019 at 20:11, on Zulip):

Hi @ranweiler and @Aaron Hill -- so I spent some time investigating "lazy norm" but also const generics recently. I'll try to leave some notes here.

nikomatsakis (Sep 03 2019 at 21:57, on Zulip):

OK, so, I've done some digging, though I also got distracted by some other things.

nikomatsakis (Sep 03 2019 at 21:59, on Zulip):

One thing I've been doing is that I created a branch that "fixes" the generics of constants so that they properly inherit generics from their parents. This is currently ICEing with an assertion failure, and I'm trying to figure out why -- I have been doing some edits to dump more info because the current debug rules don't give enough.

nikomatsakis (Sep 03 2019 at 22:00, on Zulip):

The idea here is that this change is the one that is theoretically blocked by lazy norm, and I'd like to udnerstand why. I suspect we can use the existing "eager norm" strategy here as well and it should work "at least as well" as it does for associated types today, but I'm not entirely sure.

nikomatsakis (Sep 03 2019 at 22:00, on Zulip):

(That's why I'd like to reproduce the problem)

nikomatsakis (Sep 03 2019 at 22:02, on Zulip):

Separately, I think what I'd like to do is to try integrating lazy norm into the compilation in a branch and just see what problems we hit. I spent a bit of time thinking about what that would mean -- but didn't get too far. I'm debating about how to get started, basically. One problem is that the existing code manually invokes normalization in all kinds of places ('eager norm'). I suppose it would suffice to insert some logic into unification to normalize-if-needed and then to remove some of those eager normalization locations -- we don't necessarily have to remove all of them.

nikomatsakis (Sep 03 2019 at 22:03, on Zulip):

Still, there are also some questions about the strategy that chalk is using right now -- so I spent some time thinking over alternatives there. I should leave some notes in chalk#234, but I have to run at the moment.

Aaron Hill (Sep 04 2019 at 00:56, on Zulip):

@nikomatsakis is there anything I can help with at the moment? Should I take a look at that branch, and see if I can figure out the root cause of the assertion failure?

Hal Gentz (Sep 04 2019 at 01:26, on Zulip):

Hello folks! I've been told that you, @nikomatsakis, are the one to ask about anything relating to lazy-normalization, so I'm asking here: I've got a good amount of free time and would love to help get lazy normalization functional with const generics. Alas, opengl knowledge doesn't exactly help with contributing to rustc, or compilers in general, so I'm completely out of my waters and am bassically complete beginner wrt rustc. That stated, are there any problems suitable for first-time contributors that I could work on that would help you get this closer to being up and running?

nikomatsakis (Sep 04 2019 at 21:30, on Zulip):

is there anything I can help with at the moment? Should I take a look at that branch, and see if I can figure out the root cause of the assertion failure?

@Aaron Hill yeah, sorry, those comments didn't arrive at an actionable state. Indeed if you wanted to look into the source of that assertion failure, it could be useful.

What i've found is that the error is basically "legit" -- we are being asked to evaluate a predicate like this:

Binder(TraitPredicate(<[u8; Const { ty: usize, val: Unevaluated(DefId(0:29231 ~ core[db27]::str[0]::pattern[0]::CharSearcher[0]::utf8_encoded[0]::{{constant}}[0]), [ReLateBound(DebruijnIndex(1), BrAnon(0))]) }] as marker::Sized>))

this is rather hard to read but the key bit is the ReLateBound(DebruijnIndex(1), BrAnon(0)) -- this basically says there is some region with debruijn index 1, but we only have 1 level of binder in scope here, so we would not expect a region with index > 0. Now the question is where this type came from.

I think it has something to do with the core::Searcher trait (which actually is a common source of assertion failures of this kind). I think it's arising when compiling this snippet:

impl<'a> Pattern<'a> for char {
    type Searcher = CharSearcher<'a>;

    #[inline]
    fn into_searcher(self, haystack: &'a str) -> Self::Searcher {
        let mut utf8_encoded = [0; 4];
        let utf8_size = self.encode_utf8(&mut utf8_encoded).len();

My guess is that somewhere relatively early on we are somehow miscounting the depth or otherwise mishandling the 'a that appears in there. I'm not quite sure. I guess maybe trying to minimize down the hunk of libcore that encouters the problem might be a start, i've done that in the past.

Aaron Hill (Sep 05 2019 at 21:22, on Zulip):

I'm ending up with a different error message when I try to build your branch:

DEBUG 2019-09-05T21:04:30Z: rustc::traits::project: normalize_with_depth(depth=0, value=ImplHeader { impl_def_id: DefId(0:27284 ~ core[21ad]::array[0]::{{impl}}[61]), self_ty: [_; _], trait_ref: Some(<[_; _] as default::Default>), predicates: [Binder(TraitPredicate(<_ as marker::Sized>)), Binder(TraitPredicate(<_ as default::Default>))] })
DEBUG 2019-09-05T21:04:30Z: rustc::traits::codegen: subst_and_normalize_erasing_regions(param_substs=[_], value=usize, param_env=ParamEnv { caller_bounds: [], reveal: All, def_id: None })
DEBUG 2019-09-05T21:04:30Z: rustc::traits::query::normalize_erasing_regions: normalize_erasing_regions::<&rustc::ty::TyS>(value=usize, param_env=ParamEnv { caller_bounds: [], reveal: All, def_id: None })
error: internal compiler error: src/librustc/ich/impls_ty.rs:213: ty::TyKind::hash_stable() - can't hash a TyVid _#1t.

I haven't been able to minimize it - however, it looks like an inference variable is still in a constant expression after rustc has expected it to be replaced

Aaron Hill (Sep 05 2019 at 21:22, on Zulip):

@nikomatsakis ^

I think it might be caused by the fact that I'm using incremental compilation (./x.py build -i) - that stack trace involves hashing a type when a query is run

Aaron Hill (Sep 05 2019 at 21:31, on Zulip):

Minimized: https://gist.github.com/Aaron1011/8b69db43800e11a76a1c50d93fa91581

Aaron Hill (Sep 05 2019 at 21:53, on Zulip):

This seems like a legitimate error - we're trying to run the const_eval query on a type that still has inference variables,, and we don't know how to hash that type for the query key.

How should lazy normalization interact with incremental compilation? I would assume that we would want to skip caching any queries involving inference variables - but we'd probably want some way of marking which queries expect inference variables, to prevent any regressions

Aaron Hill (Sep 08 2019 at 21:31, on Zulip):

@nikomatsakis: I made some progress on your lazy normalization branch here: https://github.com/Aaron1011/rust/tree/lazy-norm-anon-const

I found two main issues, which I (maybe) fixed on that branch:
1. Trait selection needs to have constants evaluated, since this can affect trait selection (e.g. impl MyTrait for MyStruct<{1 + 1}>
2. The const_eval query was receiving types with inference variables in them. This is a more general problem, affecting any queries that attempt to do any sort of trait selection on types they receieve (e.g. is_sized_raw). When we canonicalize the predicate we're trying to select, we attempt to resolve any region inference variables found in the predicate. However, when we cross a query boundary, we create a new InferCtxt. This means that we end up trying to resolve inference variables from one InferCtxt in a completely different InferCtxt.
The workaround I came up with was to replace all ReVars with ReErased when running const eval. However, this might be completely wrong - my goal was just to see how far the compiler could get.

After applying those workaround, the compiler was able to build libcore, libstd, and several other crates. However, I wasn't able to fully bootstrap the stage1 compiler, due to a legitimate cycle error. Running const_eval eventually ended up needing to run param_env - since param_env does normalization, it needed to be able to const-eval the same type.

Based on that, I don't think it's going to be possible to get further with 'const only' lazy normalization, - we'll need lazy normalization of associated types as well

nikomatsakis (Sep 09 2019 at 17:24, on Zulip):

@Aaron Hill cool! let me read a bit. that cycle error is precisely the one I want to uncover. I suspect though we can solve it the same way we solve normalization for associated types

Aaron Hill (Sep 09 2019 at 17:29, on Zulip):

I think the correct solution for inference variables might be 'serialize' part of the inferctxt state, and 'deserialize' it on the other side if the query boundary

Aaron Hill (Sep 09 2019 at 17:30, on Zulip):

That is, if we have _#3r: _#2r in the ParamEnv we pass to a query, we want to create new inference variables in the fresh InferCtxt such that _#1r: _#0r.

Aaron Hill (Sep 09 2019 at 17:32, on Zulip):

Since those regions constraints could affect trait selection run against the paramenv (e.g impl<'a, 'b: 'a> MyTrait<'a, 'b> for MyType<'a, 'b>

nikomatsakis (Sep 09 2019 at 17:58, on Zulip):

I think the correct solution for inference variables might be 'serialize' part of the inferctxt state, and 'deserialize' it on the other side if the query boundary

this is what canonicalization does

nikomatsakis (Sep 09 2019 at 17:58, on Zulip):

have you seen the rustc-guide chapter on that, btw?

nikomatsakis (Sep 09 2019 at 17:58, on Zulip):

well, it's not exactly what canonicalization does, but that's on purpose

Aaron Hill (Sep 09 2019 at 18:03, on Zulip):

It is similar - however, I think canonicicalization replaces all region variables.
For the purposes of the query system, I think we only need to care about ReVar. For example, MyType: MyTrait<'static> is fine

Aaron Hill (Sep 09 2019 at 18:03, on Zulip):

I think early bound regions are fine too - e.g. MyType: MyTrait<'a>.
The only problem is ReVar, because it references state that's encoded in the InferCtxt.

Aaron Hill (Sep 09 2019 at 18:05, on Zulip):

I'm working under the assumption that in general, queries might want to do things with the ParamEnv other than passing it to a SelectionCtxt.
That is, we want to provide them with as much information as possible.

Aaron Hill (Sep 09 2019 at 18:28, on Zulip):

Would it make sense to introduce a weaker kind of canonicalization, which only deals with ReVar? We could change all queries taking ParamEvn to take a WeakCanonicalized<ParamEnv>, and remove the Key impl for ParamEnv

Aaron Hill (Sep 09 2019 at 18:29, on Zulip):

WeakCanonicalized<T> would have one method: instantiate(infcx: &InferCtxt), which would return a T with freshly created inference variables from the InferCtxt

nikomatsakis (Sep 09 2019 at 18:59, on Zulip):

It is similar - however, I think canonicicalization replaces all region variables.
For the purposes of the query system, I think we only need to care about ReVar. For example, MyType: MyTrait<'static> is fine

It's better to replace all, it creates a more canonical result, and they don't impact the result in any way.

nikomatsakis (Sep 09 2019 at 19:00, on Zulip):

I'm working under the assumption that in general, queries might want to do things with the ParamEnv other than passing it to a SelectionCtxt.
That is, we want to provide them with as much information as possible.

Well, we'll see, but the current canonicalization system is designed in part to restrict what queries can do -- basically, I want to execute the query once and then be able to re-use the results for all possible lifetimes later

Aaron Hill (Sep 09 2019 at 19:03, on Zulip):

@nikomatsakis: Does const-evaluation only use the ParamEnv for trait selection, then? Or does it only use it in ways where the specific lifetimes don't matter?

Aaron Hill (Sep 09 2019 at 19:04, on Zulip):

My concern was that some part of const evaluation might actually want to distinguish between MyType: MyTrait<_#0r> and MyType: MyTrait<'static>, but maybe that's never the case.

nikomatsakis (Sep 09 2019 at 19:08, on Zulip):

that should never be the case

nikomatsakis (Sep 09 2019 at 19:09, on Zulip):

Does const-evaluation only use the ParamEnv for trait selection, then? Or does it only use it in ways where the specific lifetimes don't matter?

I think only for trait selection, correct

Aaron Hill (Sep 09 2019 at 19:16, on Zulip):

sounds reasonable. Should I take a shot at switching all queries that take a ParamEnv (is_freeze_raw, `const_eval, etc) to take a canonicalized ParamEnv?

Aaron Hill (Sep 09 2019 at 19:18, on Zulip):

I think that such a change could actually be landed independently of lazy normalization stuff. I don't think we would ever want region inference variables to move across a query boundary.

nikomatsakis (Sep 09 2019 at 19:19, on Zulip):

sounds reasonable. Should I take a shot at switching all queries that take a ParamEnv (is_freeze_raw, `const_eval, etc) to take a canonicalized ParamEnv?

sounds great! keep me updated

nikomatsakis (Sep 09 2019 at 19:20, on Zulip):

I still haven't had time to dig into your comments btw, I hope to do so before end of day

Last update: Nov 12 2019 at 16:05UTC