introduce a more expressive `UserSubsts`

6 files changed, 122 insertions, 40 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index dd2c41dda64..e54968c5274 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -1417,3 +1417,8 @@ impl_stable_hash_for!(enum traits::QuantifierKind {
     Universal,
     Existential
 });
+
+impl_stable_hash_for!(struct ty::subst::UserSubsts<'tcx> { substs, user_self_ty });
+
+impl_stable_hash_for!(struct ty::subst::UserSelfTy<'tcx> { impl_def_id, self_ty });
+
diff --git a/src/librustc/mir/mod.rs b/src/librustc/mir/mod.rs
index 278a9bba178..48b2ccbcf87 100644
--- a/src/librustc/mir/mod.rs
+++ b/src/librustc/mir/mod.rs
@@ -37,7 +37,7 @@ use syntax::ast::{self, Name};
 use syntax::symbol::InternedString;
 use syntax_pos::{Span, DUMMY_SP};
 use ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
-use ty::subst::{CanonicalSubsts, Subst, Substs};
+use ty::subst::{CanonicalUserSubsts, Subst, Substs};
 use ty::{self, AdtDef, CanonicalTy, ClosureSubsts, GeneratorSubsts, Region, Ty, TyCtxt};
 use util::ppaux;
 
@@ -2413,8 +2413,8 @@ pub struct Constant<'tcx> {
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 pub enum UserTypeAnnotation<'tcx> {
     Ty(CanonicalTy<'tcx>),
-    FnDef(DefId, CanonicalSubsts<'tcx>),
-    AdtDef(&'tcx AdtDef, CanonicalSubsts<'tcx>),
+    FnDef(DefId, CanonicalUserSubsts<'tcx>),
+    AdtDef(&'tcx AdtDef, CanonicalUserSubsts<'tcx>),
 }
 
 EnumTypeFoldableImpl! {
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index ab1df2d4c3b..6f0f258a217 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -33,7 +33,7 @@ use middle::resolve_lifetime::{self, ObjectLifetimeDefault};
 use middle::stability;
 use mir::{self, Mir, interpret};
 use mir::interpret::Allocation;
-use ty::subst::{CanonicalSubsts, Kind, Substs, Subst};
+use ty::subst::{CanonicalUserSubsts, Kind, Substs, Subst};
 use ty::ReprOptions;
 use traits;
 use traits::{Clause, Clauses, GoalKind, Goal, Goals};
@@ -383,7 +383,7 @@ pub struct TypeckTables<'tcx> {
     /// If the user wrote `foo.collect::<Vec<_>>()`, then the
     /// canonical substitutions would include only `for<X> { Vec<X>
     /// }`.
-    user_substs: ItemLocalMap<CanonicalSubsts<'tcx>>,
+    user_substs: ItemLocalMap<CanonicalUserSubsts<'tcx>>,
 
     adjustments: ItemLocalMap<Vec<ty::adjustment::Adjustment<'tcx>>>,
 
@@ -573,14 +573,14 @@ impl<'tcx> TypeckTables<'tcx> {
         self.node_substs.get(&id.local_id).cloned()
     }
 
-    pub fn user_substs_mut(&mut self) -> LocalTableInContextMut<'_, CanonicalSubsts<'tcx>> {
+    pub fn user_substs_mut(&mut self) -> LocalTableInContextMut<'_, CanonicalUserSubsts<'tcx>> {
         LocalTableInContextMut {
             local_id_root: self.local_id_root,
             data: &mut self.user_substs
         }
     }
 
-    pub fn user_substs(&self, id: hir::HirId) -> Option<CanonicalSubsts<'tcx>> {
+    pub fn user_substs(&self, id: hir::HirId) -> Option<CanonicalUserSubsts<'tcx>> {
         validate_hir_id_for_typeck_tables(self.local_id_root, id, false);
         self.user_substs.get(&id.local_id).cloned()
     }
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index c0a42fd5854..bea5ba04f7c 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -323,33 +323,6 @@ impl<'tcx> TypeFoldable<'tcx> for &'tcx Substs<'tcx> {
     }
 }
 
-pub type CanonicalSubsts<'gcx> = Canonical<'gcx, &'gcx Substs<'gcx>>;
-
-impl<'gcx> CanonicalSubsts<'gcx> {
-    /// True if this represents a substitution like
-    ///
-    /// ```text
-    /// [?0, ?1, ?2]
-    /// ```
-    ///
-    /// i.e., each thing is mapped to a canonical variable with the same index.
-    pub fn is_identity(&self) -> bool {
-        self.value.iter().zip(CanonicalVar::new(0)..).all(|(kind, cvar)| {
-            match kind.unpack() {
-                UnpackedKind::Type(ty) => match ty.sty {
-                    ty::Infer(ty::CanonicalTy(cvar1)) => cvar == cvar1,
-                    _ => false,
-                },
-
-                UnpackedKind::Lifetime(r) => match r {
-                    ty::ReCanonical(cvar1) => cvar == *cvar1,
-                    _ => false,
-                },
-            }
-        })
-    }
-}
-
 impl<'tcx> serialize::UseSpecializedDecodable for &'tcx Substs<'tcx> {}
 
 ///////////////////////////////////////////////////////////////////////////
@@ -564,3 +537,98 @@ impl<'a, 'gcx, 'tcx> SubstFolder<'a, 'gcx, 'tcx> {
         self.tcx().mk_region(ty::fold::shift_region(*region, self.region_binders_passed))
     }
 }
+
+pub type CanonicalUserSubsts<'tcx> = Canonical<'tcx, UserSubsts<'tcx>>;
+
+impl CanonicalUserSubsts<'tcx> {
+    /// True if this represents a substitution like
+    ///
+    /// ```text
+    /// [?0, ?1, ?2]
+    /// ```
+    ///
+    /// i.e., each thing is mapped to a canonical variable with the same index.
+    pub fn is_identity(&self) -> bool {
+        if self.value.user_self_ty.is_some() {
+            return false;
+        }
+
+        self.value.substs.iter().zip(CanonicalVar::new(0)..).all(|(kind, cvar)| {
+            match kind.unpack() {
+                UnpackedKind::Type(ty) => match ty.sty {
+                    ty::Infer(ty::CanonicalTy(cvar1)) => cvar == cvar1,
+                    _ => false,
+                },
+
+                UnpackedKind::Lifetime(r) => match r {
+                    ty::ReCanonical(cvar1) => cvar == *cvar1,
+                    _ => false,
+                },
+            }
+        })
+    }
+}
+
+/// Stores the user-given substs to reach some fully qualified path
+/// (e.g., `<T>::Item` or `<T as Trait>::Item`).
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
+pub struct UserSubsts<'tcx> {
+    /// The substitutions for the item as given by the user.
+    pub substs: &'tcx Substs<'tcx>,
+
+    /// The self-type, in the case of a `<T>::Item` path (when applied
+    /// to an inherent impl). See `UserSubsts` below.
+    pub user_self_ty: Option<UserSelfTy<'tcx>>,
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for UserSubsts<'tcx> {
+        substs,
+        user_self_ty,
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for UserSubsts<'a> {
+        type Lifted = UserSubsts<'tcx>;
+        substs,
+        user_self_ty,
+    }
+}
+
+/// Specifies the user-given self-type. In the case of a path that
+/// refers to a member in an inherent impl, this self-type is
+/// sometimes needed to constrain the type parameters on the impl. For
+/// example, in this code:
+///
+/// ```
+/// struct Foo<T> { }
+/// impl<A> Foo<A> { fn method() { } }
+/// ```
+///
+/// when you then have a path like `<Foo<&'static u32>>::method`,
+/// this struct would carry the def-id of the impl along with the
+/// self-type `Foo<u32>`. Then we can instantiate the parameters of
+/// the impl (with the substs from `UserSubsts`) and apply those to
+/// the self-type, giving `Foo<?A>`. Finally, we unify that with
+/// the self-type here, which contains `?A` to be `&'static u32`
+#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
+pub struct UserSelfTy<'tcx> {
+    pub impl_def_id: DefId,
+    pub self_ty: Ty<'tcx>,
+}
+
+BraceStructTypeFoldableImpl! {
+    impl<'tcx> TypeFoldable<'tcx> for UserSelfTy<'tcx> {
+        impl_def_id,
+        self_ty,
+    }
+}
+
+BraceStructLiftImpl! {
+    impl<'a, 'tcx> Lift<'tcx> for UserSelfTy<'a> {
+        type Lifted = UserSelfTy<'tcx>;
+        impl_def_id,
+        self_ty,
+    }
+}
diff --git a/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs b/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs
index 21dabd0c1bd..ebf9c7b4826 100644
--- a/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs
+++ b/src/librustc_mir/borrow_check/nll/type_check/relate_tys.rs
@@ -15,6 +15,7 @@ use rustc::infer::{InferCtxt, NLLRegionVariableOrigin};
 use rustc::mir::{ConstraintCategory, UserTypeAnnotation};
 use rustc::traits::query::Fallible;
 use rustc::ty::relate::TypeRelation;
+use rustc::ty::subst::UserSubsts;
 use rustc::ty::{self, Ty};
 use syntax_pos::DUMMY_SP;
 
@@ -78,13 +79,15 @@ pub(super) fn relate_type_and_user_type<'tcx>(
             ty
         }
         UserTypeAnnotation::FnDef(def_id, canonical_substs) => {
-            let (substs, _) =
+            let (UserSubsts { substs, user_self_ty }, _) =
                 infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &canonical_substs);
+            assert!(user_self_ty.is_none()); // TODO for now
             infcx.tcx.mk_fn_def(def_id, substs)
         }
         UserTypeAnnotation::AdtDef(adt_def, canonical_substs) => {
-            let (substs, _) =
+            let (UserSubsts { substs, user_self_ty }, _) =
                 infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &canonical_substs);
+            assert!(user_self_ty.is_none()); // TODO for now
             infcx.tcx.mk_adt(adt_def, substs)
         }
     };
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index be8b16dd2f5..62e4ef0f05c 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -95,7 +95,7 @@ use rustc::infer::opaque_types::OpaqueTypeDecl;
 use rustc::infer::type_variable::{TypeVariableOrigin};
 use rustc::middle::region;
 use rustc::mir::interpret::{ConstValue, GlobalId};
-use rustc::ty::subst::{CanonicalSubsts, UnpackedKind, Subst, Substs};
+use rustc::ty::subst::{CanonicalUserSubsts, UnpackedKind, Subst, Substs, UserSubsts};
 use rustc::traits::{self, ObligationCause, ObligationCauseCode, TraitEngine};
 use rustc::ty::{self, Ty, TyCtxt, GenericParamDefKind, Visibility, ToPredicate, RegionKind};
 use rustc::ty::adjustment::{Adjust, Adjustment, AllowTwoPhase, AutoBorrow, AutoBorrowMutability};
@@ -2136,7 +2136,10 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
                             method.substs[i]
                         }
                     });
-                    self.infcx.canonicalize_response(&just_method_substs)
+                    self.infcx.canonicalize_response(&UserSubsts {
+                        substs: just_method_substs,
+                        user_self_ty: None, // not relevant here
+                    })
                 });
 
                 debug!("write_method_call: user_substs = {:?}", user_substs);
@@ -2172,13 +2175,16 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
         );
 
         if !substs.is_noop() {
-            let user_substs = self.infcx.canonicalize_response(&substs);
+            let user_substs = self.infcx.canonicalize_response(&UserSubsts {
+                substs,
+                user_self_ty: None, // TODO -- fix in future commit
+            });
             debug!("instantiate_value_path: user_substs = {:?}", user_substs);
             self.write_user_substs(hir_id, user_substs);
         }
     }
 
-    pub fn write_user_substs(&self, hir_id: hir::HirId, substs: CanonicalSubsts<'tcx>) {
+    pub fn write_user_substs(&self, hir_id: hir::HirId, substs: CanonicalUserSubsts<'tcx>) {
         debug!(
             "write_user_substs({:?}, {:?}) in fcx {}",
             hir_id,