Handle placeholder types in canonicalization

5 files changed, 85 insertions, 21 deletions

diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs
index 4b465c7ad54..e9fac5b9239 100644
--- a/src/librustc/ich/impls_ty.rs
+++ b/src/librustc/ich/impls_ty.rs
@@ -1099,12 +1099,13 @@ impl_stable_hash_for!(struct infer::canonical::CanonicalVarInfo {
 
 impl_stable_hash_for!(enum infer::canonical::CanonicalVarKind {
     Ty(k),
+    PlaceholderTy(placeholder),
     Region(ui),
     PlaceholderRegion(placeholder),
 });
 
 impl_stable_hash_for!(enum infer::canonical::CanonicalTyVarKind {
-    General,
+    General(ui),
     Int,
     Float
 });
diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs
index a9c6c3b5085..7a9527573c7 100644
--- a/src/librustc/infer/canonical/canonicalizer.rs
+++ b/src/librustc/infer/canonical/canonicalizer.rs
@@ -339,11 +339,35 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
 
     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
         match t.sty {
-            ty::Infer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
+            ty::Infer(ty::TyVar(vid)) => {
+                match self.infcx.unwrap().probe_ty_var(vid) {
+                    // `t` could be a float / int variable: canonicalize that instead
+                    Ok(t) => self.fold_ty(t),
+
+                    // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
+                    // result
+                    Err(ui) => self.canonicalize_ty_var(
+                        CanonicalVarInfo {
+                            kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui))
+                        },
+                        t
+                    )
+                }
+            }
 
-            ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
+            ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(
+                CanonicalVarInfo {
+                    kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int)
+                },
+                t
+            ),
 
-            ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
+            ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(
+                CanonicalVarInfo {
+                    kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float)
+                },
+                t
+            ),
 
             ty::Infer(ty::FreshTy(_))
             | ty::Infer(ty::FreshIntTy(_))
@@ -351,6 +375,13 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
                 bug!("encountered a fresh type during canonicalization")
             }
 
+            ty::Placeholder(placeholder) => self.canonicalize_ty_var(
+                CanonicalVarInfo {
+                    kind: CanonicalVarKind::PlaceholderTy(placeholder)
+                },
+                t
+            ),
+
             ty::Bound(bound_ty) => {
                 if bound_ty.index >= self.binder_index {
                     bug!("escaping bound type during canonicalization")
@@ -380,7 +411,6 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx>
             | ty::Never
             | ty::Tuple(..)
             | ty::Projection(..)
-            | ty::Placeholder(..)
             | ty::UnnormalizedProjection(..)
             | ty::Foreign(..)
             | ty::Param(..)
@@ -579,15 +609,12 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
     /// if `ty_var` is bound to anything; if so, canonicalize
     /// *that*. Otherwise, create a new canonical variable for
     /// `ty_var`.
-    fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
+    fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo, ty_var: Ty<'tcx>) -> Ty<'tcx> {
         let infcx = self.infcx.expect("encountered ty-var without infcx");
         let bound_to = infcx.shallow_resolve(ty_var);
         if bound_to != ty_var {
             self.fold_ty(bound_to)
         } else {
-            let info = CanonicalVarInfo {
-                kind: CanonicalVarKind::Ty(ty_kind),
-            };
             let var = self.canonical_var(info, ty_var.into());
             self.tcx().mk_ty(ty::Bound(BoundTy::new(self.binder_index, var)))
         }
diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs
index 41839d61d32..230f8958b33 100644
--- a/src/librustc/infer/canonical/mod.rs
+++ b/src/librustc/infer/canonical/mod.rs
@@ -122,6 +122,7 @@ impl CanonicalVarInfo {
     pub fn is_existential(&self) -> bool {
         match self.kind {
             CanonicalVarKind::Ty(_) => true,
+            CanonicalVarKind::PlaceholderTy(_) => false,
             CanonicalVarKind::Region(_) => true,
             CanonicalVarKind::PlaceholderRegion(..) => false,
         }
@@ -136,6 +137,9 @@ pub enum CanonicalVarKind {
     /// Some kind of type inference variable.
     Ty(CanonicalTyVarKind),
 
+    /// A "placeholder" that represents "any type".
+    PlaceholderTy(ty::PlaceholderType),
+
     /// Region variable `'?R`.
     Region(ty::UniverseIndex),
 
@@ -148,12 +152,12 @@ pub enum CanonicalVarKind {
 impl CanonicalVarKind {
     pub fn universe(self) -> ty::UniverseIndex {
         match self {
-            // At present, we don't support higher-ranked
-            // quantification over types, so all type variables are in
-            // the root universe.
-            CanonicalVarKind::Ty(_) => ty::UniverseIndex::ROOT,
+            CanonicalVarKind::Ty(kind) => match kind {
+                CanonicalTyVarKind::General(ui) => ui,
+                CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
+            }
 
-            // Region variables can be created in sub-universes.
+            CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
             CanonicalVarKind::Region(ui) => ui,
             CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
         }
@@ -168,7 +172,7 @@ impl CanonicalVarKind {
 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
 pub enum CanonicalTyVarKind {
     /// General type variable `?T` that can be unified with arbitrary types.
-    General,
+    General(ty::UniverseIndex),
 
     /// Integral type variable `?I` (that can only be unified with integral types).
     Int,
@@ -358,8 +362,11 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
         match cv_info.kind {
             CanonicalVarKind::Ty(ty_kind) => {
                 let ty = match ty_kind {
-                    CanonicalTyVarKind::General => {
-                        self.next_ty_var(TypeVariableOrigin::MiscVariable(span))
+                    CanonicalTyVarKind::General(ui) => {
+                        self.next_ty_var_in_universe(
+                            TypeVariableOrigin::MiscVariable(span),
+                            universe_map(ui)
+                        )
                     }
 
                     CanonicalTyVarKind::Int => self.tcx.mk_int_var(self.next_int_var_id()),
@@ -369,6 +376,15 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
                 ty.into()
             }
 
+            CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
+                let universe_mapped = universe_map(universe);
+                let placeholder_mapped = ty::PlaceholderType {
+                    universe: universe_mapped,
+                    name,
+                };
+                self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
+            }
+
             CanonicalVarKind::Region(ui) => self.next_region_var_in_universe(
                 RegionVariableOrigin::MiscVariable(span),
                 universe_map(ui),
@@ -380,9 +396,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
                     universe: universe_mapped,
                     name,
                 };
-                self.tcx
-                    .mk_region(ty::RePlaceholder(placeholder_mapped))
-                    .into()
+                self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
             }
         }
     }
diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs
index dfe6aa160b3..6f041fdfb0a 100644
--- a/src/librustc/infer/mod.rs
+++ b/src/librustc/infer/mod.rs
@@ -972,6 +972,17 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         self.tcx.mk_var(self.next_ty_var_id(false, origin))
     }
 
+    pub fn next_ty_var_in_universe(
+        &self,
+        origin: TypeVariableOrigin,
+        universe: ty::UniverseIndex
+    ) -> Ty<'tcx> {
+        let vid = self.type_variables
+            .borrow_mut()
+            .new_var(universe, false, origin);
+        self.tcx.mk_var(vid)
+    }
+
     pub fn next_diverging_ty_var(&self, origin: TypeVariableOrigin) -> Ty<'tcx> {
         self.tcx.mk_var(self.next_ty_var_id(true, origin))
     }
@@ -1227,6 +1238,17 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> {
         }
     }
 
+    /// If `TyVar(vid)` resolves to a type, return that type. Else, return the
+    /// universe index of `TyVar(vid)`.
+    pub fn probe_ty_var(&self, vid: TyVid) -> Result<Ty<'tcx>, ty::UniverseIndex> {
+        use self::type_variable::TypeVariableValue;
+
+        match self.type_variables.borrow_mut().probe(vid) {
+            TypeVariableValue::Known { value } => Ok(value),
+            TypeVariableValue::Unknown { universe } => Err(universe),
+        }
+    }
+
     pub fn shallow_resolve(&self, typ: Ty<'tcx>) -> Ty<'tcx> {
         self.inlined_shallow_resolve(typ)
     }
diff --git a/src/librustc/infer/type_variable.rs b/src/librustc/infer/type_variable.rs
index bec19ba9099..5624961ea6e 100644
--- a/src/librustc/infer/type_variable.rs
+++ b/src/librustc/infer/type_variable.rs
@@ -72,7 +72,7 @@ pub type TypeVariableMap = FxHashMap<ty::TyVid, TypeVariableOrigin>;
 
 struct TypeVariableData {
     origin: TypeVariableOrigin,
-    diverging: bool
+    diverging: bool,
 }
 
 #[derive(Copy, Clone, Debug)]