Short-cut Sized matching on ADTs

Put a constraint type on every ADT def, such that the ADT def is sized iff the constraint
type is, and use that in selection. This ignores types that are obviously sized.

This improves typeck performance by ~15%.

3 files changed, 225 insertions, 83 deletions

diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs
index 536c739bf16..85b4b4f59c4 100644
--- a/src/librustc/dep_graph/dep_node.rs
+++ b/src/librustc/dep_graph/dep_node.rs
@@ -88,6 +88,7 @@ pub enum DepNode<D: Clone + Debug> {
     ImplOrTraitItems(D),
     ItemSignature(D),
     FieldTy(D),
+    SizedConstraint(D),
     TraitItemDefIds(D),
     InherentImpls(D),
     ImplItems(D),
@@ -193,6 +194,7 @@ impl<D: Clone + Debug> DepNode<D> {
             ImplOrTraitItems(ref d) => op(d).map(ImplOrTraitItems),
             ItemSignature(ref d) => op(d).map(ItemSignature),
             FieldTy(ref d) => op(d).map(FieldTy),
+            SizedConstraint(ref d) => op(d).map(SizedConstraint),
             TraitItemDefIds(ref d) => op(d).map(TraitItemDefIds),
             InherentImpls(ref d) => op(d).map(InherentImpls),
             ImplItems(ref d) => op(d).map(ImplItems),
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index d7528fc3130..9267ea393ac 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -13,7 +13,6 @@
 pub use self::MethodMatchResult::*;
 pub use self::MethodMatchedData::*;
 use self::SelectionCandidate::*;
-use self::BuiltinBoundConditions::*;
 use self::EvaluationResult::*;
 
 use super::coherence;
@@ -232,10 +231,18 @@ struct EvaluatedCandidate<'tcx> {
     evaluation: EvaluationResult,
 }
 
-enum BuiltinBoundConditions<'tcx> {
-    If(ty::Binder<Vec<Ty<'tcx>>>),
-    ParameterBuiltin,
-    AmbiguousBuiltin
+/// When does the builtin impl for `T: Trait` apply?
+enum BuiltinImplConditions<'tcx> {
+    /// The impl is conditional on T1,T2,.. : Trait
+    Where(ty::Binder<Vec<Ty<'tcx>>>),
+    /// There is no built-in impl. There may be some other
+    /// candidate (a where-clause or user-defined impl).
+    None,
+    /// There is *no* impl for this, builtin or not. Ignore
+    /// all where-clauses.
+    Never(SelectionError<'tcx>),
+    /// It is unknown whether there is an impl.
+    Ambiguous
 }
 
 #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
@@ -1608,6 +1615,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     // those will hopefully change to library-defined traits in the
     // future.
 
+    // HACK: if this returns an error, selection exits without considering
+    // other impls.
     fn assemble_builtin_bound_candidates<'o>(&mut self,
                                              bound: ty::BuiltinBound,
                                              obligation: &TraitObligation<'tcx>,
@@ -1615,25 +1624,25 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                              -> Result<(),SelectionError<'tcx>>
     {
         match self.builtin_bound(bound, obligation) {
-            Ok(If(..)) => {
+            BuiltinImplConditions::Where(..) => {
                 debug!("builtin_bound: bound={:?}",
                        bound);
                 candidates.vec.push(BuiltinCandidate(bound));
                 Ok(())
             }
-            Ok(ParameterBuiltin) => { Ok(()) }
-            Ok(AmbiguousBuiltin) => {
+            BuiltinImplConditions::None => { Ok(()) }
+            BuiltinImplConditions::Ambiguous => {
                 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
                 Ok(candidates.ambiguous = true)
             }
-            Err(e) => { Err(e) }
+            BuiltinImplConditions::Never(e) => { Err(e) }
         }
     }
 
     fn builtin_bound(&mut self,
                      bound: ty::BuiltinBound,
                      obligation: &TraitObligation<'tcx>)
-                     -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
+                     -> BuiltinImplConditions<'tcx>
     {
         // Note: these tests operate on types that may contain bound
         // regions. To be proper, we ought to skolemize here, but we
@@ -1641,6 +1650,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // confirmation step.
 
         let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
+
+        let always = BuiltinImplConditions::Where(ty::Binder(Vec::new()));
+        let never = BuiltinImplConditions::Never(Unimplemented);
+
         return match self_ty.sty {
             ty::TyInfer(ty::IntVar(_)) |
             ty::TyInfer(ty::FloatVar(_)) |
@@ -1652,14 +1665,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             ty::TyFnPtr(_) |
             ty::TyChar => {
                 // safe for everything
-                ok_if(Vec::new())
+                always
             }
 
             ty::TyBox(_) => {  // Box<T>
                 match bound {
-                    ty::BoundCopy => Err(Unimplemented),
-
-                    ty::BoundSized => ok_if(Vec::new()),
+                    ty::BoundCopy => never,
+                    ty::BoundSized => always,
 
                     ty::BoundSync | ty::BoundSend => {
                         bug!("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1669,7 +1681,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
             ty::TyRawPtr(..) => {     // *const T, *mut T
                 match bound {
-                    ty::BoundCopy | ty::BoundSized => ok_if(Vec::new()),
+                    ty::BoundCopy | ty::BoundSized => always,
 
                     ty::BoundSync | ty::BoundSend => {
                         bug!("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1679,10 +1691,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
             ty::TyTrait(ref data) => {
                 match bound {
-                    ty::BoundSized => Err(Unimplemented),
+                    ty::BoundSized => never,
                     ty::BoundCopy => {
+                        // FIXME(#32963): bit-rot fungus infestation
                         if data.bounds.builtin_bounds.contains(&bound) {
-                            ok_if(Vec::new())
+                            always
                         } else {
                             // Recursively check all supertraits to find out if any further
                             // bounds are required and thus we must fulfill.
@@ -1692,11 +1705,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                             let copy_def_id = obligation.predicate.def_id();
                             for tr in util::supertraits(self.tcx(), principal) {
                                 if tr.def_id() == copy_def_id {
-                                    return ok_if(Vec::new())
+                                    return always
                                 }
                             }
 
-                            Err(Unimplemented)
+                            never
                         }
                     }
                     ty::BoundSync | ty::BoundSend => {
@@ -1711,14 +1724,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::BoundCopy => {
                         match mutbl {
                             // &mut T is affine and hence never `Copy`
-                            hir::MutMutable => Err(Unimplemented),
+                            hir::MutMutable => never,
 
                             // &T is always copyable
-                            hir::MutImmutable => ok_if(Vec::new()),
+                            hir::MutImmutable => always
                         }
                     }
 
-                    ty::BoundSized => ok_if(Vec::new()),
+                    ty::BoundSized => always,
 
                     ty::BoundSync | ty::BoundSend => {
                         bug!("Send/Sync shouldn't occur in builtin_bounds()");
@@ -1730,7 +1743,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // [T; n]
                 match bound {
                     ty::BoundCopy => ok_if(vec![element_ty]),
-                    ty::BoundSized => ok_if(Vec::new()),
+                    ty::BoundSized => always,
                     ty::BoundSync | ty::BoundSend => {
                         bug!("Send/Sync shouldn't occur in builtin_bounds()");
                     }
@@ -1743,46 +1756,42 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                         bug!("Send/Sync shouldn't occur in builtin_bounds()");
                     }
 
-                    ty::BoundCopy | ty::BoundSized => Err(Unimplemented),
+                    ty::BoundCopy | ty::BoundSized => never
                 }
             }
 
             // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
             ty::TyTuple(ref tys) => ok_if(tys.clone()),
 
-            ty::TyClosure(_, ref substs) => {
-                // FIXME -- This case is tricky. In the case of by-ref
-                // closures particularly, we need the results of
-                // inference to decide how to reflect the type of each
-                // upvar (the upvar may have type `T`, but the runtime
-                // type could be `&mut`, `&`, or just `T`). For now,
-                // though, we'll do this unsoundly and assume that all
-                // captures are by value. Really what we ought to do
-                // is reserve judgement and then intertwine this
-                // analysis with closure inference.
-
-                // Unboxed closures shouldn't be
-                // implicitly copyable
-                if bound == ty::BoundCopy {
-                    return Ok(ParameterBuiltin);
-                }
+            ty::TyClosure(..) => {
+                match bound {
+                    ty::BoundSync | ty::BoundSend => {
+                        bug!("Send/Sync shouldn't occur in builtin_bounds()");
+                    }
 
-                // Upvars are always local variables or references to
-                // local variables, and local variables cannot be
-                // unsized, so the closure struct as a whole must be
-                // Sized.
-                if bound == ty::BoundSized {
-                    return ok_if(Vec::new());
+                    ty::BoundCopy => never,
+                    ty::BoundSized => always
                 }
-
-                ok_if(substs.upvar_tys.clone())
             }
 
             ty::TyStruct(def, substs) | ty::TyEnum(def, substs) => {
-                let types: Vec<Ty> = def.all_fields().map(|f| {
-                    f.ty(self.tcx(), substs)
-                }).collect();
-                nominal(bound, types)
+                match bound {
+                    // Fallback to whatever user-defined impls exist in this case.
+                    ty::BoundCopy => BuiltinImplConditions::None,
+
+                    // Sized if all the component types are sized.
+                    ty::BoundSized => {
+                        let sized_crit = def.sized_constraint(self.tcx());
+                        if sized_crit == self.tcx().types.bool {
+                            always
+                        } else {
+                            ok_if(vec![sized_crit.subst(self.tcx(), substs)])
+                        }
+                    }
+
+                    // Shouldn't be coming through here.
+                    ty::BoundSend | ty::BoundSync => bug!(),
+                }
             }
 
             ty::TyProjection(_) | ty::TyParam(_) => {
@@ -1790,7 +1799,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // particular bound if there is a where clause telling
                 // us that it does, and that case is handled by
                 // `assemble_candidates_from_caller_bounds()`.
-                Ok(ParameterBuiltin)
+                BuiltinImplConditions::None
             }
 
             ty::TyInfer(ty::TyVar(_)) => {
@@ -1798,10 +1807,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 // applicable impls and so forth, depending on what
                 // those type variables wind up being bound to.
                 debug!("assemble_builtin_bound_candidates: ambiguous builtin");
-                Ok(AmbiguousBuiltin)
+                BuiltinImplConditions::Ambiguous
             }
 
-            ty::TyError => ok_if(Vec::new()),
+            ty::TyError => always,
 
             ty::TyInfer(ty::FreshTy(_))
             | ty::TyInfer(ty::FreshIntTy(_))
@@ -1811,26 +1820,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         };
 
-        fn ok_if<'tcx>(v: Vec<Ty<'tcx>>)
-                       -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> {
-            Ok(If(ty::Binder(v)))
-        }
-
-        fn nominal<'cx, 'tcx>(bound: ty::BuiltinBound,
-                              types: Vec<Ty<'tcx>>)
-                              -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>>
-        {
-            // First check for markers and other nonsense.
-            match bound {
-                // Fallback to whatever user-defined impls exist in this case.
-                ty::BoundCopy => Ok(ParameterBuiltin),
-
-                // Sized if all the component types are sized.
-                ty::BoundSized => ok_if(types),
-
-                // Shouldn't be coming through here.
-                ty::BoundSend | ty::BoundSync => bug!(),
-            }
+        fn ok_if<'tcx>(v: Vec<Ty<'tcx>>) -> BuiltinImplConditions<'tcx> {
+            BuiltinImplConditions::Where(ty::Binder(v))
         }
     }
 
@@ -1999,7 +1990,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         match candidate {
             BuiltinCandidate(builtin_bound) => {
                 Ok(VtableBuiltin(
-                    self.confirm_builtin_candidate(obligation, builtin_bound)?))
+                    self.confirm_builtin_candidate(obligation, builtin_bound)))
             }
 
             ParamCandidate(param) => {
@@ -2100,18 +2091,18 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
     fn confirm_builtin_candidate(&mut self,
                                  obligation: &TraitObligation<'tcx>,
                                  bound: ty::BuiltinBound)
-                                 -> Result<VtableBuiltinData<PredicateObligation<'tcx>>,
-                                           SelectionError<'tcx>>
+                                 -> VtableBuiltinData<PredicateObligation<'tcx>>
     {
         debug!("confirm_builtin_candidate({:?})",
                obligation);
 
-        match self.builtin_bound(bound, obligation)? {
-            If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)),
-            AmbiguousBuiltin | ParameterBuiltin => {
+        match self.builtin_bound(bound, obligation) {
+            BuiltinImplConditions::Where(nested) =>
+                self.vtable_builtin_data(obligation, bound, nested),
+            _ => {
                 span_bug!(
                     obligation.cause.span,
-                    "builtin bound for {:?} was ambig",
+                    "confiriming builtin impl for {:?} where none exists",
                     obligation);
             }
         }
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index bc342b235dd..b3ca120bd9f 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -1498,6 +1498,7 @@ pub struct AdtDefData<'tcx, 'container: 'tcx> {
     pub variants: Vec<VariantDefData<'tcx, 'container>>,
     destructor: Cell<Option<DefId>>,
     flags: Cell<AdtFlags>,
+    sized_constraint: ivar::TyIVar<'tcx, 'container>,
 }
 
 impl<'tcx, 'container> PartialEq for AdtDefData<'tcx, 'container> {
@@ -1575,7 +1576,8 @@ impl<'tcx, 'container> AdtDefData<'tcx, 'container> {
             did: did,
             variants: variants,
             flags: Cell::new(flags),
-            destructor: Cell::new(None)
+            destructor: Cell::new(None),
+            sized_constraint: ivar::TyIVar::new(),
         }
     }
 
@@ -1716,6 +1718,153 @@ impl<'tcx, 'container> AdtDefData<'tcx, 'container> {
             None => NoDtor,
         }
     }
+
+    /// Returns a simpler type such that `Self: Sized` if and only
+    /// if that type is Sized, or `TyErr` if this type is recursive.
+    pub fn sized_constraint(&self, tcx: &ty::TyCtxt<'tcx>) -> Ty<'tcx> {
+        let dep_node = DepNode::SizedConstraint(self.did);
+        match self.sized_constraint.get(dep_node) {
+            None => {
+                let this = tcx.lookup_adt_def_master(self.did);
+                this.calculate_sized_constraint_inner(tcx, &mut Vec::new());
+                self.sized_constraint.unwrap(dep_node)
+            }
+            Some(ty) => ty
+        }
+    }
+}
+
+impl<'tcx> AdtDefData<'tcx, 'tcx> {
+    fn sized_constraint_for_tys<TYS>(
+        &'tcx self,
+        tcx: &ty::TyCtxt<'tcx>,
+        stack: &mut Vec<AdtDefMaster<'tcx>>,
+        tys: TYS
+    ) -> Ty<'tcx>
+        where TYS: IntoIterator<Item=Ty<'tcx>>
+    {
+        let tys : Vec<_> = tys.into_iter()
+            .map(|ty| self.sized_constraint_for_ty(tcx, stack, ty))
+            .filter(|ty| *ty != tcx.types.bool)
+            .collect();
+
+        match tys.len() {
+            0 => tcx.types.bool,
+            1 => tys[0],
+            _ => tcx.mk_tup(tys)
+        }
+    }
+    fn sized_constraint_for_ty(
+        &'tcx self,
+        tcx: &ty::TyCtxt<'tcx>,
+        stack: &mut Vec<AdtDefMaster<'tcx>>,
+        ty: Ty<'tcx>
+    ) -> Ty<'tcx> {
+        let result = match ty.sty {
+            TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
+            TyBox(..) | TyRawPtr(..) | TyRef(..) | TyFnDef(..) | TyFnPtr(_) |
+            TyArray(..) | TyClosure(..) => {
+                // these are always sized - return a primitive
+                tcx.types.bool
+            }
+
+            TyStr | TyTrait(..) | TySlice(_) => {
+                // these are never sized - return the target type
+                ty
+            }
+
+            TyTuple(ref tys) => {
+                self.sized_constraint_for_tys(tcx, stack, tys.iter().cloned())
+            }
+
+            TyEnum(adt, substs) | TyStruct(adt, substs) => {
+                // recursive case
+                let adt = tcx.lookup_adt_def_master(adt.did);
+                adt.calculate_sized_constraint_inner(tcx, stack);
+                let adt_ty =
+                    adt.sized_constraint
+                    .unwrap(DepNode::SizedConstraint(adt.did))
+                    .subst(tcx, substs);
+                debug!("sized_constraint_for_ty({:?}) intermediate = {:?}",
+                       ty, adt_ty);
+                self.sized_constraint_for_ty(tcx, stack, adt_ty)
+            }
+
+            TyProjection(..) => {
+                // must calculate explicitly.
+                // FIXME: consider special-casing always-Sized projections
+                ty
+            }
+
+            TyParam(..) => {
+                let sized_trait = match tcx.lang_items.sized_trait() {
+                    Some(x) => x,
+                    _ => return ty
+                };
+                let sized_predicate = Binder(TraitRef {
+                    def_id: sized_trait,
+                    substs: tcx.mk_substs(Substs::new_trait(
+                        vec![], vec![], ty
+                    ))
+                }).to_predicate();
+                let predicates = tcx.lookup_predicates(self.did).predicates;
+                if predicates.into_iter().any(|p| p == sized_predicate) {
+                    tcx.types.bool
+                } else {
+                    ty
+                }
+            }
+
+            TyInfer(..) | TyError => {
+                bug!("unexpected type `{:?}` in sized_constraint_for_ty",
+                     ty)
+            }
+        };
+        debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result);
+        result
+    }
+
+    /// Calculates the Sized-constraint. This replaces all always-Sized
+    /// types with bool. I could have made the TyIVar an Option, but that
+    /// would have been so much code.
+    fn calculate_sized_constraint_inner(&'tcx self, tcx: &ty::TyCtxt<'tcx>,
+                                        stack: &mut Vec<AdtDefMaster<'tcx>>)
+    {
+
+        let dep_node = DepNode::SizedConstraint(self.did);
+
+        if self.sized_constraint.get(dep_node).is_some() {
+            return;
+        }
+
+        if stack.contains(&self) {
+            debug!("calculate_sized_constraint: {:?} is recursive", self);
+            self.sized_constraint.fulfill(dep_node, tcx.types.err);
+            return;
+        }
+
+        stack.push(self);
+        let ty = self.sized_constraint_for_tys(
+            tcx, stack,
+            self.variants.iter().flat_map(|v| {
+                v.fields.last()
+            }).map(|f| f.unsubst_ty())
+        );
+
+        let self_ = stack.pop().unwrap();
+        assert_eq!(self_, self);
+
+        match self.sized_constraint.get(dep_node) {
+            Some(old_ty) => {
+                debug!("calculate_sized_constraint: {:?} recurred", self);
+                assert_eq!(old_ty, tcx.types.err)
+            }
+            None => {
+                debug!("calculate_sized_constraint: {:?} => {:?}", self, ty);
+                self.sized_constraint.fulfill(dep_node, ty)
+            }
+        }
+    }
 }
 
 impl<'tcx, 'container> VariantDefData<'tcx, 'container> {