Internal Tracking Issue for normalization redesign

This is a tracking issue to migrate the way we handle alias types (associated types, opaque types, etc) in the type system, and especially the next-generation trait solver -Znext-solver. This is a large change and requires a lot of churn, because of this, it will land in multiple steps.

This refactor includes the addition of a wrapper struct Unnormalized to explicitly track whether a type needs should be eagerly normalized. It also adds a IsRigid flag to TyKind::Alias, marking whether an alias is known to be rigid in the current context.

This is in progress and we've somewhat adjusted this design as we've tried to implement it. For a terse and likely slightly outdated description, see https://hackmd.io/d4spupEOTySQmkz1gaPk1g.

Please contact @lcnr on the #t-types zulip stream in case there are questions or issues. While we're changing this, please do not hesitate to reach out in case the current state is unclear or confusing. If you want to help out, see the links to messages in the #t-types/trait-system-refactor zulip.

Steps

• initial PR adding ty::Unnormalized #155083
• initial PR explicitly tracking IsRigid #156742
• https://github.com/rust-lang/rust/pull/156224
  • All of the t == cx.tcx.normalize_erasing_regions(cx.typing_env(), t) asserts should be some assert_fully_normalized and don't use Unnormalized::new_wip
  • computing struct_tail should take Unnormalized<T> and return T
  • field.ty should return Unnormalized. This can be done with changing the normalize method in borrowck typechecker to take Unnormalized.
• #158438 fast_reject consider IsRigid in fast path: perrrrf
• #158606 yeet AliasRelate, lazily replace non-rigid aliases in type relations with infer var and directly emit Projection goals
• #158643 implement a hack in ParamEnv normalization to incorrectly mark things as rigid
• #158620 All calls to skip_norm_wip().def_id should be replaced with a def_id() method on Unnormalized<Whateverhasadefid> https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607085904
• #158668
  • the DeeplyNormalize QueryTypeOp should contain an Unnormalized<T> as input https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607086213
  • normalize_with_depth_to should take Unnormalized https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607086213
• #158731 remove eq_structurally_relating_aliases, have a special type folder to instantiate canonical responses

Rigid aliases

• type relating, first normalize aliases, then handle infer vars, this means generalization never results in an infer var :>
• change coherence to actually rely on lazy norm :<
• eagerly normalize when adding stuff to the fulfillment ctxt :> (blocked on removing the dependence on lazy norm in coherence)
• change TypeOutlives handling to only expect rigid aliases, eagerly normalize https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607084889
• properly use expect IsRigid::Yes in region handling
• trying changing EarlyBinder::bind to assert that there are no rigid aliases instead of implicitly replacing rigid aliases (manually replace them before then)
• TypeFolder try to do rigid to non rigid conversion automatically/make it harder to mess up

ty::Unnormalized cleanup

• in general, all funtions that take a normalize function argument should change its signature https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607086444
• bororwck: TypeChecker::normalize should be fallible instead of returning unnormalized types
• ty.fn_sig should return Unnormalized https://rust-lang.zulipchat.com/#narrow/channel/364551-t-types.2Ftrait-system-refactor/topic/ask.20for.20help/near/607086926
• HirTyLowering use Unnormalized everywhere
• change normalization closures to return Result<Ty<'tcx>, E> instead of being infallible to support eager errors
• util::supertraits should return Unnormalized
• DropckConstraint should have Unnormalized fields?
• PredicateKind::WellFormed goals should take Unnormalized<Term>
• remaining Unnormalized::new_wip and skip_norm_wip

Start by reading the linked PRs and the messages in the #t-types/trait-system-refactor Zulip stream to understand which checklist item is still actionable. Choose one narrowly scoped item with guidance from the type-system maintainers, then update the corresponding checklist entry when its implementation and validation are complete.