Rust: 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

• https://github.com/rust-lang/rust/issues/72219 -- Lazy normalization for constants

Further background reading

What is this "lazy normalization"? (see https://github.com/rust-lang/rust/issues/60471#issuecomment-523394151)

@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 #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 #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 https://github.com/rust-lang/rust/issues/43408 should be feature gated as it has design implications re. associated constant defaults in the sense of https://github.com/rust-lang/rust/issues/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 https://github.com/rust-lang/rust/issues/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.