Introduce `TyKind::UnnormalizedProjection`

27 files changed, 57 insertions, 11 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 9c4e995e24d..388abc88cfd 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -873,8 +873,8 @@ for ty::TyKind<'gcx>
             Tuple(inner_tys) => {
                 inner_tys.hash_stable(hcx, hasher);
             }
-            Projection(ref projection_ty) => {
-                projection_ty.hash_stable(hcx, hasher);
+            Projection(ref data) | UnnormalizedProjection(ref data) => {
+                data.hash_stable(hcx, hasher);
             }
             Opaque(def_id, substs) => {
                 def_id.hash_stable(hcx, hasher);
diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index b30ccb5976c..6449227af4a 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -283,6 +283,7 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
             | ty::Never
             | ty::Tuple(..)
             | ty::Projection(..)
+            | ty::UnnormalizedProjection(..)
             | ty::Foreign(..)
             | ty::Param(..)
             | ty::Opaque(..) => {
diff --git a/src/librustc/infer/freshen.rs b/src/librustc/infer/freshen.rs
index 1cb813c39e6..e17e777332e 100644
--- a/src/librustc/infer/freshen.rs
+++ b/src/librustc/infer/freshen.rs
@@ -193,6 +193,7 @@ impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> {
             ty::Never |
             ty::Tuple(..) |
             ty::Projection(..) |
+            ty::UnnormalizedProjection(..) |
             ty::Foreign(..) |
             ty::Param(..) |
             ty::Closure(..) |
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index 7401d4099ff..caf549e37a9 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -475,6 +475,7 @@ fn ty_is_local_constructor(ty: Ty<'_>, in_crate: InCrate) -> bool {
 
         ty::Error => true,
 
+        ty::UnnormalizedProjection(..) |
         ty::Closure(..) |
         ty::Generator(..) |
         ty::GeneratorWitness(..) |
diff --git a/src/librustc/traits/error_reporting.rs b/src/librustc/traits/error_reporting.rs
index 7695f26d701..3b3e38a8bb7 100644
--- a/src/librustc/traits/error_reporting.rs
+++ b/src/librustc/traits/error_reporting.rs
@@ -269,7 +269,8 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
                 ty::Generator(..) => Some(18),
                 ty::Foreign(..) => Some(19),
                 ty::GeneratorWitness(..) => Some(20),
-                ty::Infer(..) | ty::Error => None
+                ty::Infer(..) | ty::Error => None,
+                ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
             }
         }
 
diff --git a/src/librustc/traits/query/dropck_outlives.rs b/src/librustc/traits/query/dropck_outlives.rs
index f5fb183ec1a..aaf03f8e7fb 100644
--- a/src/librustc/traits/query/dropck_outlives.rs
+++ b/src/librustc/traits/query/dropck_outlives.rs
@@ -253,5 +253,7 @@ pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'_, '_, 'tcx>, ty: Ty<'tcx>) ->
         | ty::Opaque(..)
         | ty::Infer(_)
         | ty::Generator(..) => false,
+
+        ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
     }
 }
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 268b8e0161b..0ea9098378b 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -2200,6 +2200,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => None,
             ty::Infer(ty::TyVar(_)) => Ambiguous,
 
+            ty::UnnormalizedProjection(..) |
             ty::Infer(ty::CanonicalTy(_)) |
             ty::Infer(ty::FreshTy(_)) |
             ty::Infer(ty::FreshIntTy(_)) |
@@ -2272,6 +2273,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 Ambiguous
             }
 
+            ty::UnnormalizedProjection(..) |
             ty::Infer(ty::CanonicalTy(_)) |
             ty::Infer(ty::FreshTy(_)) |
             ty::Infer(ty::FreshIntTy(_)) |
@@ -2310,6 +2312,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 Vec::new()
             }
 
+            ty::UnnormalizedProjection(..) |
             ty::Dynamic(..) |
             ty::Param(..) |
             ty::Foreign(..) |
diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs
index 64e9d15092e..29b3db400b1 100644
--- a/src/librustc/ty/context.rs
+++ b/src/librustc/ty/context.rs
@@ -2266,7 +2266,7 @@ impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
             self,
             Adt, Array, Slice, RawPtr, Ref, FnDef, FnPtr,
             Generator, GeneratorWitness, Dynamic, Closure, Tuple,
-            Param, Infer, Projection, Opaque, Foreign);
+            Param, Infer, UnnormalizedProjection, Projection, Opaque, Foreign);
 
         println!("Substs interner: #{}", self.interners.substs.borrow().len());
         println!("Region interner: #{}", self.interners.region.borrow().len());
diff --git a/src/librustc/ty/error.rs b/src/librustc/ty/error.rs
index 9f9d918415e..b3a1b312ca1 100644
--- a/src/librustc/ty/error.rs
+++ b/src/librustc/ty/error.rs
@@ -222,6 +222,7 @@ impl<'a, 'gcx, 'lcx, 'tcx> ty::TyS<'tcx> {
             ty::Infer(ty::FreshIntTy(_)) => "skolemized integral type".to_string(),
             ty::Infer(ty::FreshFloatTy(_)) => "skolemized floating-point type".to_string(),
             ty::Projection(_) => "associated type".to_string(),
+            ty::UnnormalizedProjection(_) => "non-normalized associated type".to_string(),
             ty::Param(ref p) => {
                 if p.is_self() {
                     "Self".to_string()
diff --git a/src/librustc/ty/fast_reject.rs b/src/librustc/ty/fast_reject.rs
index 2d055fd307d..0f68e7aba4d 100644
--- a/src/librustc/ty/fast_reject.rs
+++ b/src/librustc/ty/fast_reject.rs
@@ -103,6 +103,7 @@ pub fn simplify_type<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         ty::FnPtr(ref f) => {
             Some(FunctionSimplifiedType(f.skip_binder().inputs().len()))
         }
+        ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
         ty::Projection(_) | ty::Param(_) => {
             if can_simplify_params {
                 // In normalized types, projections don't unify with
diff --git a/src/librustc/ty/flags.rs b/src/librustc/ty/flags.rs
index 08d10578238..3ccc24e73a5 100644
--- a/src/librustc/ty/flags.rs
+++ b/src/librustc/ty/flags.rs
@@ -150,6 +150,8 @@ impl FlagComputation {
                 self.add_projection_ty(data);
             }
 
+            &ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
             &ty::Opaque(_, substs) => {
                 self.add_flags(TypeFlags::HAS_PROJECTION);
                 self.add_substs(substs);
diff --git a/src/librustc/ty/item_path.rs b/src/librustc/ty/item_path.rs
index c8d104e6c32..46d133224f8 100644
--- a/src/librustc/ty/item_path.rs
+++ b/src/librustc/ty/item_path.rs
@@ -463,6 +463,7 @@ pub fn characteristic_def_id_of_type(ty: Ty<'_>) -> Option<DefId> {
         ty::Str |
         ty::FnPtr(_) |
         ty::Projection(_) |
+        ty::UnnormalizedProjection(..) |
         ty::Param(_) |
         ty::Opaque(..) |
         ty::Infer(_) |
diff --git a/src/librustc/ty/layout.rs b/src/librustc/ty/layout.rs
index 8bfe46568eb..7df8af5fa2e 100644
--- a/src/librustc/ty/layout.rs
+++ b/src/librustc/ty/layout.rs
@@ -1123,7 +1123,7 @@ impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
                 }
                 tcx.layout_raw(param_env.and(normalized))?
             }
-            ty::GeneratorWitness(..) | ty::Infer(_) => {
+            ty::UnnormalizedProjection(..) | ty::GeneratorWitness(..) | ty::Infer(_) => {
                 bug!("LayoutDetails::compute: unexpected type `{}`", ty)
             }
             ty::Param(_) | ty::Error => {
@@ -1702,8 +1702,8 @@ impl<'a, 'tcx, C> TyLayoutMethods<'tcx, C> for Ty<'tcx>
                 }
             }
 
-            ty::Projection(_) | ty::Opaque(..) | ty::Param(_) |
-            ty::Infer(_) | ty::Error => {
+            ty::Projection(_) | ty::UnnormalizedProjection(..) |
+            ty::Opaque(..) | ty::Param(_) | ty::Infer(_) | ty::Error => {
                 bug!("TyLayout::field_type: unexpected type `{}`", this.ty)
             }
         })
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index b2281691bd6..77e0b9e91bc 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -2339,6 +2339,8 @@ impl<'a, 'gcx, 'tcx> AdtDef {
                 vec![ty]
             }
 
+            UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
             Param(..) => {
                 // perf hack: if there is a `T: Sized` bound, then
                 // we know that `T` is Sized and do not need to check
diff --git a/src/librustc/ty/outlives.rs b/src/librustc/ty/outlives.rs
index 68f67070876..91eda66e08c 100644
--- a/src/librustc/ty/outlives.rs
+++ b/src/librustc/ty/outlives.rs
@@ -124,6 +124,8 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
                 }
             }
 
+            ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
             // We assume that inference variables are fully resolved.
             // So, if we encounter an inference variable, just record
             // the unresolved variable as a component.
diff --git a/src/librustc/ty/structural_impls.rs b/src/librustc/ty/structural_impls.rs
index aab268c07c4..c3c4cbed89d 100644
--- a/src/librustc/ty/structural_impls.rs
+++ b/src/librustc/ty/structural_impls.rs
@@ -876,6 +876,9 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             ty::GeneratorWitness(types) => ty::GeneratorWitness(types.fold_with(folder)),
             ty::Closure(did, substs) => ty::Closure(did, substs.fold_with(folder)),
             ty::Projection(ref data) => ty::Projection(data.fold_with(folder)),
+            ty::UnnormalizedProjection(ref data) => {
+                ty::UnnormalizedProjection(data.fold_with(folder))
+            }
             ty::Opaque(did, substs) => ty::Opaque(did, substs.fold_with(folder)),
             ty::Bool | ty::Char | ty::Str | ty::Int(_) |
             ty::Uint(_) | ty::Float(_) | ty::Error | ty::Infer(_) |
@@ -910,7 +913,9 @@ impl<'tcx> TypeFoldable<'tcx> for Ty<'tcx> {
             }
             ty::GeneratorWitness(ref types) => types.visit_with(visitor),
             ty::Closure(_did, ref substs) => substs.visit_with(visitor),
-            ty::Projection(ref data) => data.visit_with(visitor),
+            ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => {
+                data.visit_with(visitor)
+            }
             ty::Opaque(_, ref substs) => substs.visit_with(visitor),
             ty::Bool | ty::Char | ty::Str | ty::Int(_) |
             ty::Uint(_) | ty::Float(_) | ty::Error | ty::Infer(_) |
diff --git a/src/librustc/ty/sty.rs b/src/librustc/ty/sty.rs
index 6c40dd89239..06d559fd9db 100644
--- a/src/librustc/ty/sty.rs
+++ b/src/librustc/ty/sty.rs
@@ -157,6 +157,11 @@ pub enum TyKind<'tcx> {
     /// `<T as Trait<..>>::N`.
     Projection(ProjectionTy<'tcx>),
 
+    /// A placeholder type used when we do not have enough information
+    /// to normalize the projection of an associated type to an
+    /// existing concrete type. Currently only used with chalk-engine.
+    UnnormalizedProjection(ProjectionTy<'tcx>),
+
     /// Opaque (`impl Trait`) type found in a return type.
     /// The `DefId` comes either from
     /// * the `impl Trait` ast::Ty node,
@@ -1806,7 +1811,7 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
             Generator(_, GeneratorSubsts { ref substs }, _) => {
                 substs.regions().collect()
             }
-            Projection(ref data) => {
+            Projection(ref data) | UnnormalizedProjection(ref data) => {
                 data.substs.regions().collect()
             }
             FnDef(..) |
@@ -1886,6 +1891,8 @@ impl<'a, 'gcx, 'tcx> TyS<'tcx> {
 
             ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => false,
 
+            ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
             ty::Infer(ty::TyVar(_)) => false,
 
             ty::Infer(ty::CanonicalTy(_)) |
diff --git a/src/librustc/ty/util.rs b/src/librustc/ty/util.rs
index 93fc77359e4..4d7bab3cf43 100644
--- a/src/librustc/ty/util.rs
+++ b/src/librustc/ty/util.rs
@@ -958,6 +958,8 @@ fn needs_drop_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
         ty::Dynamic(..) | ty::Projection(..) | ty::Param(_) |
         ty::Opaque(..) | ty::Infer(_) | ty::Error => true,
 
+        ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
         // Structural recursion.
         ty::Array(ty, _) | ty::Slice(ty) => needs_drop(ty),
 
diff --git a/src/librustc/ty/walk.rs b/src/librustc/ty/walk.rs
index cf87c2d4574..d20c4f71642 100644
--- a/src/librustc/ty/walk.rs
+++ b/src/librustc/ty/walk.rs
@@ -97,7 +97,7 @@ fn push_subtypes<'tcx>(stack: &mut TypeWalkerStack<'tcx>, parent_ty: Ty<'tcx>) {
         ty::Ref(_, ty, _) => {
             stack.push(ty);
         }
-        ty::Projection(ref data) => {
+        ty::Projection(ref data) | ty::UnnormalizedProjection(ref data) => {
             stack.extend(data.substs.types().rev());
         }
         ty::Dynamic(ref obj, ..) => {
diff --git a/src/librustc/ty/wf.rs b/src/librustc/ty/wf.rs
index 63206a660df..397c63a149a 100644
--- a/src/librustc/ty/wf.rs
+++ b/src/librustc/ty/wf.rs
@@ -289,6 +289,8 @@ impl<'a, 'gcx, 'tcx> WfPredicates<'a, 'gcx, 'tcx> {
                     self.compute_projection(data);
                 }
 
+                ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
                 ty::Adt(def, substs) => {
                     // WfNominalType
                     let obligations = self.nominal_obligations(def.did, substs);
diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs
index 10382008e0d..814f8880bbf 100644
--- a/src/librustc/util/ppaux.rs
+++ b/src/librustc/util/ppaux.rs
@@ -18,7 +18,7 @@ use ty::{Bool, Char, Adt};
 use ty::{Error, Str, Array, Slice, Float, FnDef, FnPtr};
 use ty::{Param, RawPtr, Ref, Never, Tuple};
 use ty::{Closure, Generator, GeneratorWitness, Foreign, Projection, Opaque};
-use ty::{Dynamic, Int, Uint, Infer};
+use ty::{UnnormalizedProjection, Dynamic, Int, Uint, Infer};
 use ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable, GenericParamCount, GenericParamDefKind};
 use util::nodemap::FxHashSet;
 
@@ -1143,6 +1143,11 @@ define_print! {
                 }
                 Foreign(def_id) => parameterized(f, subst::Substs::empty(), def_id, &[]),
                 Projection(ref data) => data.print(f, cx),
+                UnnormalizedProjection(ref data) => {
+                    write!(f, "Unnormalized(")?;
+                    data.print(f, cx)?;
+                    write!(f, ")")
+                }
                 Opaque(def_id, substs) => {
                     if cx.is_verbose {
                         return write!(f, "Opaque({:?}, {:?})", def_id, substs);
diff --git a/src/librustc_codegen_llvm/debuginfo/type_names.rs b/src/librustc_codegen_llvm/debuginfo/type_names.rs
index f9eb80a1988..2f110fd552a 100644
--- a/src/librustc_codegen_llvm/debuginfo/type_names.rs
+++ b/src/librustc_codegen_llvm/debuginfo/type_names.rs
@@ -173,6 +173,7 @@ pub fn push_debuginfo_type_name<'a, 'tcx>(cx: &CodegenCx<'a, 'tcx>,
         }
         ty::Error |
         ty::Infer(_) |
+        ty::UnnormalizedProjection(..) |
         ty::Projection(..) |
         ty::Opaque(..) |
         ty::GeneratorWitness(..) |
diff --git a/src/librustc_lint/types.rs b/src/librustc_lint/types.rs
index 01d4d0f8cdb..a441f7a87f7 100644
--- a/src/librustc_lint/types.rs
+++ b/src/librustc_lint/types.rs
@@ -722,6 +722,7 @@ impl<'a, 'tcx> ImproperCTypesVisitor<'a, 'tcx> {
             ty::Closure(..) |
             ty::Generator(..) |
             ty::GeneratorWitness(..) |
+            ty::UnnormalizedProjection(..) |
             ty::Projection(..) |
             ty::Opaque(..) |
             ty::FnDef(..) => bug!("Unexpected type in foreign function"),
diff --git a/src/librustc_mir/monomorphize/item.rs b/src/librustc_mir/monomorphize/item.rs
index 3f5a05f9d0e..f0ea93bfffd 100644
--- a/src/librustc_mir/monomorphize/item.rs
+++ b/src/librustc_mir/monomorphize/item.rs
@@ -382,6 +382,7 @@ impl<'a, 'tcx> DefPathBasedNames<'a, 'tcx> {
             }
             ty::Error |
             ty::Infer(_) |
+            ty::UnnormalizedProjection(..) |
             ty::Projection(..) |
             ty::Param(_) |
             ty::GeneratorWitness(_) |
diff --git a/src/librustc_traits/dropck_outlives.rs b/src/librustc_traits/dropck_outlives.rs
index e3ec2e6b9ce..2996fe03200 100644
--- a/src/librustc_traits/dropck_outlives.rs
+++ b/src/librustc_traits/dropck_outlives.rs
@@ -272,6 +272,8 @@ fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>(
             overflows: vec![],
         }),
 
+        ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
+
         ty::Infer(..) | ty::Error => {
             // By the time this code runs, all type variables ought to
             // be fully resolved.
diff --git a/src/librustc_typeck/check/cast.rs b/src/librustc_typeck/check/cast.rs
index 564ecae15dc..285fed9544d 100644
--- a/src/librustc_typeck/check/cast.rs
+++ b/src/librustc_typeck/check/cast.rs
@@ -124,6 +124,7 @@ impl<'a, 'gcx, 'tcx> FnCtxt<'a, 'gcx, 'tcx> {
             ty::Foreign(..) => Some(PointerKind::Thin),
             // We should really try to normalize here.
             ty::Projection(ref pi) => Some(PointerKind::OfProjection(pi)),
+            ty::UnnormalizedProjection(..) => bug!("only used with chalk-engine"),
             ty::Opaque(def_id, substs) => Some(PointerKind::OfOpaque(def_id, substs)),
             ty::Param(ref p) => Some(PointerKind::OfParam(p)),
             // Insufficient type information.
diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs
index 95544da0b8e..1125de55a06 100644
--- a/src/librustc_typeck/variance/constraints.rs
+++ b/src/librustc_typeck/variance/constraints.rs
@@ -336,6 +336,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> {
                 // types, where we use Error as the Self type
             }
 
+            ty::UnnormalizedProjection(..) |
             ty::GeneratorWitness(..) |
             ty::Infer(..) => {
                 bug!("unexpected type encountered in \