Tracking issue for "Lazy normalization"

[pnkfelix]

What is this?

"Lazy normalization" is a change to how we handle associated types (and constants) so that we wait until we have to equate an associated type (or constant) has to be equated or processed to normalize it (i.e., figure out if there is an impl we can use to find its definition), rather than doing so eagerly. This has a number of advantages, and in particular for const generics it can prevent a large number of cyclic errors.

Subissues

• Tracking issue for Lazy Normalization of Constants #72219 -- Lazy normalization for constants

Further background reading

What is this "lazy normalization"? (see #60471 (comment))

@Aaron1011 Normalization is replacing "projections" (such as <T as Trait>::AssocType or unevaluated constant expressions - a better name than "projection" might be "expression" or "call" - something that only says how to get to a final "value", not what it is) with what they resolve/evaluate to.
E.g. &<Rc<str> as Deref>::Target becomes &str, and [T; {1+1}] becomes [T; 2].

Right now all of this is done "eagerly", i.e. as soon as possible, and always (during typeck, or whenever there is enough information to normalize further), but that causes some issues:

• for associated types it's HRTB-related (IIRC)

• for type-level constants it's cyclic dependencies between the constant and the parent definition it's found in, which is why we can't fix Array lengths don't support generic parameters. #43408 (it's a one-line change, but then not even libcore compiles anymore)

Lazy normalization would simply defer the work of resolving/evaluating such type-level constructs until the very moment they are needed (such as when requiring that two types are the same, or when computing the low-level layout of a type for miri/codegen).
The associated type problem is more subtle (at least from what I've heard), but for constant expressions in types, it will simply break the cyclic dependencies because definitions will no longer force the evaluation of constant expressions they contain.

[varkor]

Maybe we could do with an A-lazy-normalization tracking label?

[Centril]

@varkor Go for it :) A- labels come cheap and we have too few today imo.

[alexreg]

Did we ever decide whether fixing enforcement of type alias bounds was blocked no lazy norm?

[varkor]

I've added a label for lazy normalisation and added it to a number of const generic issues I think are blocked on it.

[eddyb]

Just had a crazy idea that could help us start testing a bunch of stuff right away:
Add a feature-gate (say, defer_normalization or unbreak_generics_in_type_level_consts) that turns off all eager normalization, and also allows AnonConsts to see generics in scope.

This will break things (object safety comes to mind, IIRC there are a bunch of others), but in the context of tiny self-contained tests, it might be enough to allow testing expressions like N + 1 and size_of::<T>().

[varkor]

I tried this out here: https://github.com/varkor/rust/tree/defer_normalization
Unfortunately, things break even with very simple examples.

#![crate_type = "lib"]

#![feature(defer_normalization)]

pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
    [(); std::mem::size_of::<T>()]
}

results in:

error: internal compiler error: constant in type had an ignored error: TooGeneric
 --> bug.rs:5:1
  |
5 | / pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
6 | |     [(); std::mem::size_of::<T>()]
7 | | }
  | |_^

error: internal compiler error: cat_expr Errd
 --> bug.rs:5:75
  |
5 |   pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
  |  ___________________________________________________________________________^
6 | |     [(); std::mem::size_of::<T>()]
7 | | }
  | |_^

error: internal compiler error: cat_expr Errd
 --> bug.rs:6:5
  |
6 |     [(); std::mem::size_of::<T>()]
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: internal compiler error: QualifyAndPromoteConstants: MIR had errors
 --> bug.rs:5:1
  |
5 | / pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
6 | |     [(); std::mem::size_of::<T>()]
7 | | }
  | |_^

error: internal compiler error: broken MIR in DefId(0:12 ~ bug[8787]::size_of_units[0]) ("return type"): bad type [type error]
 --> bug.rs:5:1
  |
5 | / pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
6 | |     [(); std::mem::size_of::<T>()]
7 | | }
  | |_^

error: internal compiler error: broken MIR in DefId(0:12 ~ bug[8787]::size_of_units[0]) (LocalDecl { mutability: Mut, is_user_variable: None, internal: false, is_block_tail: None, ty: [type error], user_ty: UserTypeProjections { contents: [] }, name: None, source_info: SourceInfo { span: bug.rs:5:1: 7:2, scope: scope[0] }, visibility_scope: scope[0] }): bad type [type error]
 --> bug.rs:5:1
  |
5 | / pub unsafe fn size_of_units<T: Sized>() -> [(); std::mem::size_of::<T>()] {
6 | |     [(); std::mem::size_of::<T>()]
7 | | }
  | |_^

thread 'rustc' panicked at 'no errors encountered even though `delay_span_bug` issued', src/librustc_errors/lib.rs:362:17
stack backtrace:
   0:        0x106aec7f5 - std::sys_common::backtrace::print::hec9d18c92704ea4e
   1:        0x106af9217 - std::panicking::default_hook::{{closure}}::h0f3d5aca7e2dedd3
   2:        0x106af8f9b - std::panicking::default_hook::h8b614fd8b5161649
   3:        0x1047eea33 - rustc::util::common::panic_hook::h4038cc825e59a289
   4:        0x106af9912 - std::panicking::rust_panic_with_hook::hc4db8272f23d21fe
   5:        0x106750335 - std::panicking::begin_panic::hfcd1d79b5affa3d2
   6:        0x1067459f1 - <rustc_errors::Handler as core::ops::drop::Drop>::drop::hfae51df6b481bd4c
   7:        0x10045ef46 - core::ptr::real_drop_in_place::h885b1a61bfd60f80
   8:        0x100464f35 - <alloc::rc::Rc<T> as core::ops::drop::Drop>::drop::h0ac0677665f36c1c
   9:        0x10049f492 - core::ptr::real_drop_in_place::h5ef9b819f6ef30a7
  10:        0x10049a549 - rustc_interface::interface::run_compiler_in_existing_thread_pool::had730590df397043
  11:        0x10043c3c7 - std::thread::local::LocalKey<T>::with::h6c21b0ad4820d31b
  12:        0x100439246 - scoped_tls::ScopedKey<T>::set::h8427d787086b9670
  13:        0x1004f1585 - syntax::with_globals::h05f0ddf32b715ba3
  14:        0x10049328a - std::sys_common::backtrace::__rust_begin_short_backtrace::h94ac2988de47efec
  15:        0x106b014df - __rust_maybe_catch_panic
  16:        0x10048a489 - std::panicking::try::hd7392db478333fd3
  17:        0x10048b43c - core::ops::function::FnOnce::call_once{{vtable.shim}}::hf40a9128315d3f3a
  18:        0x106adbd3e - <alloc::boxed::Box<F> as core::ops::function::FnOnce<A>>::call_once::h8c046589a84a9004
  19:        0x106afa67e - std::sys_common::thread::start_thread::he35092619128de54
  20:        0x106ad9fd9 - std::sys::unix::thread::Thread::new::thread_start::ha5ad007dbd212143
  21:     0x7fff9241e93b - _pthread_body
  22:     0x7fff9241e887 - _pthread_body
query stack during panic:
end of query stack

[eddyb]

All of those are legitimate bugs that we'd need to fix sooner or later.
E.g. TooGeneric is supposed to be ignored by e.g. normalization (in rustc::traits::project).

But then again, what you wrote would, I believe, fail the ConstEvaluatable WF check - try taking an argument of that type, instead of creating a value.
Even barring that, you duplicated the expression, and currently they won't unify.

Also, what if you put size_of::<T>() (and N + 1 etc.) in a generic type alias, or associated type or struct, that is used with non-generic fns / consts?

That is, I expect type-checking bodies where such a type-level const expression is still parametrized by generics, to require more work.

[Aaron1011]

I'm still not sure exactly what lazy normalization is. Why do we need it? What parts of the compiler will need to be changed in order to implement it?

[eddyb]

@Aaron1011 Normalization is replacing "projections" (such as <T as Trait>::AssocType or unevaluated constant expressions - a better name than "projection" might be "expression" or "call" - something that only says how to get to a final "value", not what it is) with what they resolve/evaluate to.
E.g. &<Rc<str> as Deref>::Target becomes &str, and [T; {1+1}] becomes [T; 2].

Right now all of this is done "eagerly", i.e. as soon as possible, and always (during typeck, or whenever there is enough information to normalize further), but that causes some issues:

• for associated types it's HRTB-related (IIRC)
• for type-level constants it's cyclic dependencies between the constant and the parent definition it's found in, which is why we can't fix Array lengths don't support generic parameters. #43408 (it's a one-line change, but then not even libcore compiles anymore)

Lazy normalization would simply defer the work of resolving/evaluating such type-level constructs until the very moment they are needed (such as when requiring that two types are the same, or when computing the low-level layout of a type for miri/codegen).
The associated type problem is more subtle (at least from what I've heard), but for constant expressions in types, it will simply break the cyclic dependencies because definitions will no longer force the evaluation of constant expressions they contain.

[Centril]

(Also see https://en.wikipedia.org/wiki/Evaluation_strategy#Call_by_need)

[alexreg]

Great explanation, @eddyb. I've seen this question come up often, so I'm going to have to bookmark that comment and link people to it!

[Aaron1011]

I'm interested in working in this. What would the the best place to start?

Would it make sense to work off of @varkor's branch, add a param_env_normalized function that actually performs normalization, and start determining which callers need to use it?

[Centril]

(Please do note that actually fixing #43408 should be feature gated as it has design implications re. associated constant defaults in the sense of #29661 and whatnot.)

[eddyb]

@Aaron1011 It's not really a caller-by-caller basis. The same callers that cause the cycles also need early normalization right now.

The solution (ignoring the hack I mentioned and which @varkor was playing with) is to add lazy normalization, which is something @nikomatsakis didn't let me, for years, so I assume there is a good reason (likely regarding associated types).

Some infrastructure has been slowly making its way into the compiler, for Chalk integration (but not only), so things might be reaching a point where we can have lazy normalization.

I wouldn't bother without a more thorough discussion with @nikomatsakis and @rust-lang/wg-traits.

[eddyb]

Just because this is important, let me spell it out:

Getting this wrong can introduce unsoundness and I doubt we have enough tests to prevent that

That is, there may be tricks one might use to get all the code samples we have working, but introduce a subtle unsoundness regarding associated types, perhaps with HRTB involved, or in constants.

It's very easy to lose track of obligations (yet-to-be-proven where clauses, roughly) that are required to hold, and we plugged holes for years after 1.0.

[Manishearth]

Am I correct in assuming that the fix for this will fix #67753 ?

[varkor]

@Manishearth: yes, it ought to.

[jjpe]

I just ran into this issue. The last comment was half a year ago, could anyone tell me what the current status of this is?
I ask because I'm trying to decide what to do about array support for a library I'm developing, at least for the time being.

[tema3210]

Any news?

[p-avital]

Is lazy normalization dead? Waiting for the next trait solver?

Eager normalization is causing a whole slew of issues on my current project which attempts to provide a stable ABI for Rust with niche exploitation as a library. To do so, I rely on typenum, but eager normalization makes a lot of typenum's operations unusable in certain contexts.

[vadixidav]

I believe this issue is no longer relevant as per #72219 (comment) (@lcnr you may want to close this).

I would check https://github.com/rust-lang/project-const-generics/issues?q=is%3Aissue+is%3Aopen+label%3AA-generic-exprs, #92827, and #76560. I don't believe there is one central place to find updates, but these issues might be what you are looking for based on my limited understanding. It sounds like Chalk is part of the solution for this, but overall you can see that there is work happening on this and discussions over time using those links.

I am also eagerly awaiting these kinds of features for implementing a generic machine learning library with compile-time tensor sizes and monomorphic swappable backends (via GATs), so I also follow a lot of these compiler features hoping they will be fully implemented one day.

The team also seems to communicate on Zulip as well, but I have not visited recently.

[p-avital]

It sounds like Chalk is part of the solution for this

I heard somewhere that Chalk was getting supplanted by yet another trait solver, but I may be wrong there... Anyway, really hyped for when we'll get generic_const_exprs. In the meantime, I'm working on a successor to typenum that leverages GATs to reduce the overflowing requirement issues (or at least detect them earlier). I might not be in time for RustConf, but I'm really looking forward to finishing this project filled to the bream with evil type-fu

[lcnr]

Finally taking the time to go actually sit down and look at this issue again 😅

Going to try and explain two things with this comment: what's actually meant when talking about lazy normalization and the current status.

---

I think at its core we have a lot of different things which we talk about under the name of "lazy normalization" and I am still figuring out where to better document all of this.

As stated above by @eddyb, normalization is the process of taking a projection/expression/alias and converting it to its "underlying value". Dealing with aliases in the type system is imo the most involved part of Rusts type system.

One of the main challenges is that aliases do not need to be structurally equal to be semantically equal. For structs and enums, if you have StructA<genericargs> and StructB<genericargs> and want to check that they are equal, you can immediately return false as StructA and StructB are different. If you have vec::IntoIter<i32> and <Vec<i32> as IntoIterator>::IntoIter it's not that simple. To decide whether these two types are equal we have to normalize the associated type.

Normalizing an aliases to its underlying type can either

• succeed (<Vec<i32> as IntoIterator>::IntoIter),
• fail (in fn foo<T: IntoIterator>() { .. } we're stuck with <T as IntoIterator>::IntoIter and can't normalize it),
• or - worst of all - be ambiguous: <_ as IntoIterator>::IntoIter.

With this context, what are the issues we want to solve by "normalizing lazily"

normalizing constant expressions causes query cycles

Imagine a constant in our where-bounds and that constant depends on the where-bounds itself, e.g.

fn foo<T>()
where
    T: IntoIterator<Item = u32>,
    [u8; std::mem::size_of::<<T as IntoIterator>::Item>()]: SomeTrait,
{
    ...
}

To evaluate that constant it has to know that <T as IntoIterator>::Item is u32. If we were to now evaluate the constant while computing the where-bounds we need to evaluate it, we get a query cycle. This is only necessary for constants and is not an issue when normalizing associated types. Avoiding the normalization of constants in the where-bounds is mostly implemented with feature(generic_const_exprs).

when normalization is ambiguous, we have to defer equality checks

If we were to equate Box<<_ as IntoIterator>::IntoIter> and Box<vec::IntoIter<i32>> we don't yet know whether this holds or not, so our equality checks have to also be ambiguous. We handle this deferring the equality check for the projection. Checking for equality between these two types would return something like "yes, they are equal, but only if <_ as IntoIterator>::IntoIter == vec::IntoIter<i32> holds". We then later check <_ as IntoIterator>::IntoIter == vec::IntoIter<i32> together with any other requirements we collect during typecheck.

We're slowly moving towards calling this "deferred projection/alias equality" and it is implemented in the new trait solver but not yet in the currently stable one. Due to reasons™, this only causes issues for projections which mention higher ranked regions.

requiring normalized environments is fundamentally broken

Without deferred projection equality, we need all aliases in the environment - the where-bounds of the item we're currently in - to be fully normalized, because we can't handle them when equating things. However, to normalize aliases in the environment, we need to be inside of that environment. This is a cyclic dependency, to get a normalized environment you need the normalized environment. With deferred projection equality these issues are fixed: https://rust.godbolt.org/z/j11P694ze.

we have to eagerly normalize everywhere

There are a lot of places from which we can get unnormalized aliases, so in the current trait solver and also in HIR typeck (i.e. during type inference) we have an incredible amount of normalization calls and still get weird errors when we miss some normalization call somewhere.

We don't eagerly normalize inside of the new trait solver itself, but at least when initially stabilizing, we will keep eager normalization in HIR typeck. Having projections around "longer than necessary" results in a bunch of issues and we actually want to stabilize the new solver at some point :p

[mark-i-m]

You know... The rustc-dev-guide would be a great place for this explanation to live  ;)