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

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:

• [x] #42171: refactor ProjectionTy to store def-id of associated item + substs
  • PR: #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

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 https://github.com/rust-lang/rust/issues/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)

1. 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:

   • [x] #42171: refactor ProjectionTy to store def-id of associated item + substs
     • PR: #42297
   • [x] 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.
   • [x] remove the ClosureSubsts type used in TyClosure and make it into a normal substs
   • [x] [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 https://github.com/rust-lang/rust/issues/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)

   varkor at 2019-05-06 11:31:05

2. just a heads up - https://github.com/rust-lang/rust/issues/42171 isn't closed yet (only half of it), though I'm planning on getting to the other half this week.

   Tobias Grieger at 2017-05-31 21:45:22

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

   Niko Matsakis at 2017-05-31 21:47:31

4. 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.

   Eduard-Mihai Burtescu at 2019-10-04 12:28:38

5. @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).

   csmoe at 2019-10-06 08:55:17

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

   Eduard-Mihai Burtescu at 2019-10-06 13:39:55