Auto merge of #55274 - pnkfelix:issue-54570-proj-path-into-pats-with-type-take-2, r=nikomatsakis

Handle bindings in substructure of patterns with type ascriptions

This attempts to follow the outline described by @nikomatsakis [here](https://github.com/rust-lang/rust/issues/47184#issuecomment-420041056). Its a bit more complicated than expected for two reasons:

 1. In general it handles sets of type ascriptions, because such ascriptions can be nested within patterns
 2.  It has a separate types in the HAIR, `PatternTypeProjections` and `PatternTypeProjection`, which are analogues to the corresponding types in the MIR.

The main reason I added the new HAIR types was because I am worried that the current implementation is inefficent, and asymptotically so: It makes copies of vectors as it descends the patterns, even when those accumulated vectors are never used.

Longer term, I would like to used a linked tree structure for the `PatternTypeProjections` and `PatternTypeProjection`, and save the construction of standalone vectors for the MIR types. I didn't want to block landing this on that hypoethetical revision; but I figured I could at least make the future change easier by differentiating between the two types now.

Oh, one more thing: This doesn't attempt to handle `ref x` (in terms of ensuring that any necessary types are ascribed to `x` in that scenario as well). We should open an issue to investigate supporting that as well. But I didn't want to block this PR on that future work.

Fix #54570

2 files changed, 50 insertions, 2 deletions

diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 1686e3e0e0c..d4b47db6081 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -31,7 +31,7 @@ use middle::cstore::EncodedMetadata;
 use middle::lang_items;
 use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
 use middle::stability;
-use mir::{self, Mir, interpret};
+use mir::{self, Mir, interpret, ProjectionKind};
 use mir::interpret::Allocation;
 use ty::subst::{CanonicalUserSubsts, Kind, Substs, Subst};
 use ty::ReprOptions;
@@ -132,6 +132,7 @@ pub struct CtxtInterners<'tcx> {
     clauses: InternedSet<'tcx, List<Clause<'tcx>>>,
     goal: InternedSet<'tcx, GoalKind<'tcx>>,
     goal_list: InternedSet<'tcx, List<Goal<'tcx>>>,
+    projs: InternedSet<'tcx, List<ProjectionKind<'tcx>>>,
 }
 
 impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
@@ -149,6 +150,7 @@ impl<'gcx: 'tcx, 'tcx> CtxtInterners<'tcx> {
             clauses: Default::default(),
             goal: Default::default(),
             goal_list: Default::default(),
+            projs: Default::default(),
         }
     }
 
@@ -1886,6 +1888,24 @@ impl<'a, 'tcx> Lift<'tcx> for &'a List<CanonicalVarInfo> {
     }
 }
 
+impl<'a, 'tcx> Lift<'tcx> for &'a List<ProjectionKind<'a>> {
+    type Lifted = &'tcx List<ProjectionKind<'tcx>>;
+    fn lift_to_tcx<'b, 'gcx>(&self, tcx: TyCtxt<'b, 'gcx, 'tcx>) -> Option<Self::Lifted> {
+        if self.len() == 0 {
+            return Some(List::empty());
+        }
+        if tcx.interners.arena.in_arena(*self as *const _) {
+            return Some(unsafe { mem::transmute(*self) });
+        }
+        // Also try in the global tcx if we're not that.
+        if !tcx.is_global() {
+            self.lift_to_tcx(tcx.global_tcx())
+        } else {
+            None
+        }
+    }
+}
+
 pub mod tls {
     use super::{GlobalCtxt, TyCtxt};
 
@@ -2294,6 +2314,13 @@ impl<'tcx: 'lcx, 'lcx> Borrow<[Kind<'lcx>]> for Interned<'tcx, Substs<'tcx>> {
     }
 }
 
+impl<'tcx: 'lcx, 'lcx> Borrow<[ProjectionKind<'lcx>]>
+    for Interned<'tcx, List<ProjectionKind<'tcx>>> {
+    fn borrow<'a>(&'a self) -> &'a [ProjectionKind<'lcx>] {
+        &self.0[..]
+    }
+}
+
 impl<'tcx> Borrow<RegionKind> for Interned<'tcx, RegionKind> {
     fn borrow<'a>(&'a self) -> &'a RegionKind {
         &self.0
@@ -2441,7 +2468,8 @@ slice_interners!(
     type_list: _intern_type_list(Ty),
     substs: _intern_substs(Kind),
     clauses: _intern_clauses(Clause),
-    goal_list: _intern_goals(Goal)
+    goal_list: _intern_goals(Goal),
+    projs: _intern_projs(ProjectionKind)
 );
 
 // This isn't a perfect fit: CanonicalVarInfo slices are always
@@ -2743,6 +2771,14 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
+    pub fn intern_projs(self, ps: &[ProjectionKind<'tcx>]) -> &'tcx List<ProjectionKind<'tcx>> {
+        if ps.len() == 0 {
+            List::empty()
+        } else {
+            self._intern_projs(ps)
+        }
+    }
+
     pub fn intern_canonical_var_infos(self, ts: &[CanonicalVarInfo]) -> CanonicalVarInfos<'gcx> {
         if ts.len() == 0 {
             List::empty()
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index a93dca4af42..62827ea20c3 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -13,6 +13,7 @@
 //! hand, though we've recently added some macros (e.g.,
 //! `BraceStructLiftImpl!`) to help with the tedium.
 
+use mir::ProjectionKind;
 use mir::interpret::ConstValue;
 use ty::{self, Lift, Ty, TyCtxt};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
@@ -628,6 +629,17 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<Ty<'tcx>> {
     }
 }
 
+impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<ProjectionKind<'tcx>> {
+    fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
+        let v = self.iter().map(|t| t.fold_with(folder)).collect::<SmallVec<[_; 8]>>();
+        folder.tcx().intern_projs(&v)
+    }
+
+    fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
+        self.iter().any(|t| t.visit_with(visitor))
+    }
+}
+
 impl<'tcx> TypeFoldable<'tcx> for ty::instance::Instance<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         use ty::InstanceDef::*;