[RFC] Refactor types to be a (TypeCore, Substs) pair

[nikomatsakis]

Currently, the Ty<'tcx> type is a reference to a struct (&TyS) that packages up a big ol' enum TypeVariants. As part of chalkification, we would like to be able to write more efficient "decision tree" like procedures that branch on this type. This would be made nicer by factoring out the type into two parts, a "core" and a "substs". This core would be roughly equivalent to the existing TypeVariants, but without the recursive references to other types, which would be uniformly packaged up in the substs.

Thus I imagine that the TyS struct would change to something like this:

pub struct TyS<'tcx> {
    pub sty: TypeVariants<'tcx>, // this is the "core" part
    pub substs: &'tcx Substs<'tcx>, // this is the "substs" part, extracted from `TypeVariants`
    pub flags: TypeFlags,

    // the maximal depth of any bound regions appearing in this type.
    region_depth: u32,
}

(Incidentally, this new notion of TypeVariants could maybe subsume the existing SimplifiedType, though that's not super important.)

Steps

This transition is best made in steps:

• refactor ProjectionTy to store def-id of associated item + substs #42171: refactor ProjectionTy to store def-id of associated item + substs
  • PR: Upgrade ProjectionTy's Name to a DefId #42297
• transition TyTuple to use a substs
  • This would make things more regular, but we "lose" the fact that tuples are always composed of types at the moment. Probably not important in practice.
• remove the ClosureSubsts type used in TyClosure and make it into a normal substs
• [do the same for GeneratorSubsts]

Unknowns

It's not 100% clear that this is a good plan, though the individual refactorings above all seem like good steps regardless. Some complicating factors:

• TyFnPtr embodies a PolyFnSig, which carries a binder.
• Existential types carry where-clauses (eventually, function pointers may do the same, to address Implied bounds on nested references + variance = soundness hole #25860)

cc @eddyb, who first suggested this to me
cc @tschottdorf, who implemented #42297, a step along this path (and an important step for ATC regardless)

[tbg]

just a heads up - #42171 isn't closed yet (only half of it), though I'm planning on getting to the other half this week.

[nikomatsakis]

@tschottdorf ah yeah, I was thinking of the "check" as "in progress", but ... seems fine

[eddyb]

Existential types carry where-clauses

Could they be moved to the binder? dyn Foo -> dyn<X: Foo> X would result in Ty::Dyn having all the information in the binder and then substs would have just an anonymous type variable (bound at the aforementioned binder) or be empty for now.

[csmoe]

@nikomatsakis @eddyb not sure whether this issue should be closed or not. How about those Unknowns? (If needed, I have a lot of brandwidth to volunteer).

[eddyb]

This isn't done, the checkboxes were only for prerequisites, I think.