Ensure default trait impls hold

5 files changed, 239 insertions, 20 deletions

diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index 9c71650c7be..93e5d38637f 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -222,7 +222,7 @@ pub enum Vtable<'tcx, N> {
     VtableImpl(VtableImplData<'tcx, N>),
 
     /// Vtable for default trait implementations
-    VtableDefaultTrait(ast::DefId),
+    VtableDefaultTrait(VtableDefaultTraitData<N>),
 
     /// Successful resolution to an obligation provided by the caller
     /// for some type parameter. The `Vec<N>` represents the
@@ -263,6 +263,12 @@ pub struct VtableImplData<'tcx, N> {
 }
 
 #[derive(Debug,Clone)]
+pub struct VtableDefaultTraitData<N> {
+    pub trait_def_id: ast::DefId,
+    pub nested: subst::VecPerParamSpace<N>
+}
+
+#[derive(Debug,Clone)]
 pub struct VtableBuiltinData<N> {
     pub nested: subst::VecPerParamSpace<N>
 }
@@ -527,7 +533,7 @@ impl<'tcx, N> Vtable<'tcx, N> {
     pub fn map_nested<M, F>(&self, op: F) -> Vtable<'tcx, M> where F: FnMut(&N) -> M {
         match *self {
             VtableImpl(ref i) => VtableImpl(i.map_nested(op)),
-            VtableDefaultTrait(t) => VtableDefaultTrait(t),
+            VtableDefaultTrait(ref t) => VtableDefaultTrait(t.map_nested(op)),
             VtableFnPointer(ref sig) => VtableFnPointer((*sig).clone()),
             VtableClosure(d, ref s) => VtableClosure(d, s.clone()),
             VtableParam(ref n) => VtableParam(n.iter().map(op).collect()),
@@ -543,7 +549,7 @@ impl<'tcx, N> Vtable<'tcx, N> {
             VtableImpl(i) => VtableImpl(i.map_move_nested(op)),
             VtableFnPointer(sig) => VtableFnPointer(sig),
             VtableClosure(d, s) => VtableClosure(d, s),
-            VtableDefaultTrait(t) => VtableDefaultTrait(t),
+            VtableDefaultTrait(t) => VtableDefaultTrait(t.map_move_nested(op)),
             VtableParam(n) => VtableParam(n.into_iter().map(op).collect()),
             VtableObject(p) => VtableObject(p),
             VtableBuiltin(no) => VtableBuiltin(no.map_move_nested(op)),
@@ -578,6 +584,31 @@ impl<'tcx, N> VtableImplData<'tcx, N> {
     }
 }
 
+impl<N> VtableDefaultTraitData<N> {
+    pub fn iter_nested(&self) -> Iter<N> {
+        self.nested.iter()
+    }
+
+    pub fn map_nested<M, F>(&self, op: F) -> VtableDefaultTraitData<M> where
+        F: FnMut(&N) -> M,
+    {
+        VtableDefaultTraitData {
+            trait_def_id: self.trait_def_id,
+            nested: self.nested.map(op)
+        }
+    }
+
+    pub fn map_move_nested<M, F>(self, op: F) -> VtableDefaultTraitData<M> where
+        F: FnMut(N) -> M,
+    {
+        let VtableDefaultTraitData { trait_def_id, nested } = self;
+        VtableDefaultTraitData {
+            trait_def_id: trait_def_id,
+            nested: nested.map_move(op)
+        }
+    }
+}
+
 impl<N> VtableBuiltinData<N> {
     pub fn iter_nested(&self) -> Iter<N> {
         self.nested.iter()
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 9fade728b36..2a920721963 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -21,13 +21,13 @@ use super::{DerivedObligationCause};
 use super::{project};
 use super::project::Normalized;
 use super::{PredicateObligation, TraitObligation, ObligationCause};
-use super::{ObligationCauseCode, BuiltinDerivedObligation};
+use super::{ObligationCauseCode, BuiltinDerivedObligation, ImplDerivedObligation};
 use super::{SelectionError, Unimplemented, Overflow, OutputTypeParameterMismatch};
 use super::{Selection};
 use super::{SelectionResult};
 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableClosure,
             VtableFnPointer, VtableObject, VtableDefaultTrait};
-use super::{VtableImplData, VtableObjectData, VtableBuiltinData};
+use super::{VtableImplData, VtableObjectData, VtableBuiltinData, VtableDefaultTraitData};
 use super::object_safety;
 use super::{util};
 
@@ -1535,7 +1535,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     ty::struct_fields(self.tcx(), def_id, substs).iter()
                                                                  .map(|f| f.mt.ty)
                                                                  .collect();
-                nominal(self, bound, def_id, types)
+                nominal(bound, types)
             }
 
             ty::ty_enum(def_id, substs) => {
@@ -1545,7 +1545,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     .flat_map(|variant| variant.args.iter())
                     .cloned()
                     .collect();
-                nominal(self, bound, def_id, types)
+                nominal(bound, types)
             }
 
             ty::ty_projection(_) |
@@ -1594,9 +1594,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         };
 
-        fn nominal<'cx, 'tcx>(this: &mut SelectionContext<'cx, 'tcx>,
-                              bound: ty::BuiltinBound,
-                              def_id: ast::DefId,
+        fn nominal<'cx, 'tcx>(bound: ty::BuiltinBound,
                               types: Vec<Ty<'tcx>>)
                               -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>>
         {
@@ -1615,6 +1613,89 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         }
     }
 
+    fn constituent_types(&self, t: Ty<'tcx>) -> Vec<Ty<'tcx>> {
+        match t.sty {
+            ty::ty_uint(_) |
+            ty::ty_int(_) |
+            ty::ty_bool |
+            ty::ty_float(_) |
+            ty::ty_bare_fn(..) |
+            ty::ty_str |
+            ty::ty_err |
+            ty::ty_char => {
+                Vec::new()
+            }
+
+            ty::ty_projection(..) |
+            ty::ty_param(..) |
+            ty::ty_infer(..) => {
+                self.tcx().sess.bug(
+                    &format!(
+                        "asked to assemble constituent types of unexpected type: {}",
+                        t.repr(self.tcx()))[]);
+            }
+
+            ty::ty_uniq(referent_ty) => {  // Box<T>
+                vec![referent_ty]
+            }
+
+
+            ty::ty_trait(ref data) => {
+                // Recursively check all supertraits to find out if any further
+                // bounds are required and thus we must fulfill.
+                let principal =
+                    data.principal_trait_ref_with_self_ty(self.tcx(),
+                                                          self.tcx().types.err);
+
+
+                util::supertraits(self.tcx(), principal).map(|tr| tr.self_ty()).collect()
+            }
+
+            ty::ty_open(element_ty) => {vec![element_ty]},
+
+            ty::ty_ptr(ty::mt { ty: element_ty, ..}) |
+            ty::ty_rptr(_, ty::mt { ty: element_ty, ..}) => {
+                vec![element_ty]
+            },
+
+            ty::ty_vec(element_ty, _) => {
+                vec![element_ty]
+            }
+
+            ty::ty_tup(ref tys) => {
+                // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet
+                tys.clone()
+            }
+
+            ty::ty_closure(def_id, _, substs) => {
+                assert_eq!(def_id.krate, ast::LOCAL_CRATE);
+
+                match self.closure_typer.closure_upvars(def_id, substs) {
+                    Some(upvars) => {
+                        upvars.iter().map(|c| c.ty).collect()
+                    }
+                    None => {
+                        Vec::new()
+                    }
+                }
+            }
+
+            ty::ty_struct(def_id, substs) => {
+                ty::struct_fields(self.tcx(), def_id, substs).iter()
+                    .map(|f| f.mt.ty)
+                    .collect()
+            }
+
+            ty::ty_enum(def_id, substs) => {
+                ty::substd_enum_variants(self.tcx(), def_id, substs)
+                    .iter()
+                    .flat_map(|variant| variant.args.iter())
+                    .map(|&ty| ty)
+                    .collect()
+            }
+        }
+    }
+
     ///////////////////////////////////////////////////////////////////////////
     // CONFIRMATION
     //
@@ -1648,7 +1729,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
 
             DefaultTraitCandidate(trait_def_id) => {
-                Ok(VtableDefaultTrait(trait_def_id))
+                let data = try!(self.confirm_default_impl_candidate(obligation, trait_def_id));
+                Ok(VtableDefaultTrait(data))
             }
 
             ImplCandidate(impl_def_id) => {
@@ -1783,6 +1865,68 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         VtableBuiltinData { nested: obligations }
     }
 
+    fn confirm_default_impl_candidate(&mut self,
+                              obligation: &TraitObligation<'tcx>,
+                              impl_def_id: ast::DefId)
+                              -> Result<VtableDefaultTraitData<PredicateObligation<'tcx>>,
+                                        SelectionError<'tcx>>
+    {
+        debug!("confirm_default_impl_candidate({}, {})",
+               obligation.repr(self.tcx()),
+               impl_def_id.repr(self.tcx()));
+
+        let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty());
+        let types = self.constituent_types(self_ty);
+        Ok(self.vtable_default_impl(obligation, impl_def_id, types))
+    }
+
+    fn vtable_default_impl(&mut self,
+                           obligation: &TraitObligation<'tcx>,
+                           trait_def_id: ast::DefId,
+                           nested: Vec<Ty<'tcx>>)
+                           -> VtableDefaultTraitData<PredicateObligation<'tcx>>
+    {
+        let derived_cause = self.derived_cause(obligation, ImplDerivedObligation);
+        let obligations = nested.iter().map(|&nested_ty| {
+            // the obligation might be higher-ranked, e.g. for<'a> &'a
+            // int : Copy. In that case, we will wind up with
+            // late-bound regions in the `nested` vector. So for each
+            // one we instantiate to a skolemized region, do our work
+            // to produce something like `&'0 int : Copy`, and then
+            // re-bind it. This is a bit of busy-work but preserves
+            // the invariant that we only manipulate free regions, not
+            // bound ones.
+            self.infcx.try(|snapshot| {
+                let (skol_ty, skol_map) =
+                    self.infcx().skolemize_late_bound_regions(&ty::Binder(nested_ty), snapshot);
+                let skol_predicate =
+                    util::predicate_for_default_trait_impl(
+                        self.tcx(),
+                        derived_cause.clone(),
+                        trait_def_id,
+                        obligation.recursion_depth + 1,
+                        skol_ty);
+                match skol_predicate {
+                    Ok(skol_predicate) => Ok(self.infcx().plug_leaks(skol_map, snapshot,
+                                                                     &skol_predicate)),
+                    Err(ErrorReported) => Err(ErrorReported)
+                }
+            })
+        }).collect::<Result<_, _>>();
+        let obligations = match obligations {
+            Ok(o) => o,
+            Err(ErrorReported) => Vec::new()
+        };
+
+        let obligations = VecPerParamSpace::new(obligations, Vec::new(), Vec::new());
+        debug!("vtable_default_impl_data: obligations={}", obligations.repr(self.tcx()));
+
+        VtableDefaultTraitData {
+            trait_def_id: trait_def_id,
+            nested: obligations
+        }
+    }
+
     fn confirm_impl_candidate(&mut self,
                               obligation: &TraitObligation<'tcx>,
                               impl_def_id: ast::DefId)
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index a0affcff2ce..771c6ad3a5e 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -20,7 +20,7 @@ use util::nodemap::FnvHashSet;
 use util::ppaux::Repr;
 
 use super::{Obligation, ObligationCause, PredicateObligation,
-            VtableImpl, VtableParam, VtableImplData};
+            VtableImpl, VtableParam, VtableImplData, VtableDefaultTraitData};
 
 struct PredicateSet<'a,'tcx:'a> {
     tcx: &'a ty::ctxt<'tcx>,
@@ -323,15 +323,13 @@ pub fn trait_ref_for_builtin_bound<'tcx>(
     }
 }
 
-pub fn predicate_for_builtin_bound<'tcx>(
+pub fn predicate_for_trait_ref<'tcx>(
     tcx: &ty::ctxt<'tcx>,
     cause: ObligationCause<'tcx>,
-    builtin_bound: ty::BuiltinBound,
-    recursion_depth: uint,
-    param_ty: Ty<'tcx>)
+    trait_ref: Rc<ty::TraitRef<'tcx>>,
+    recursion_depth: uint)
     -> Result<PredicateObligation<'tcx>, ErrorReported>
 {
-    let trait_ref = try!(trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty));
     Ok(Obligation {
         cause: cause,
         recursion_depth: recursion_depth,
@@ -339,6 +337,33 @@ pub fn predicate_for_builtin_bound<'tcx>(
     })
 }
 
+pub fn predicate_for_default_trait_impl<'tcx>(
+    tcx: &ty::ctxt<'tcx>,
+    cause: ObligationCause<'tcx>,
+    trait_def_id: ast::DefId,
+    recursion_depth: uint,
+    param_ty: Ty<'tcx>)
+    -> Result<PredicateObligation<'tcx>, ErrorReported>
+{
+    let trait_ref = Rc::new(ty::TraitRef {
+        def_id: trait_def_id,
+        substs: tcx.mk_substs(Substs::empty().with_self_ty(param_ty))
+    });
+    predicate_for_trait_ref(tcx, cause, trait_ref, recursion_depth)
+}
+
+pub fn predicate_for_builtin_bound<'tcx>(
+    tcx: &ty::ctxt<'tcx>,
+    cause: ObligationCause<'tcx>,
+    builtin_bound: ty::BuiltinBound,
+    recursion_depth: uint,
+    param_ty: Ty<'tcx>)
+    -> Result<PredicateObligation<'tcx>, ErrorReported>
+{
+    let trait_ref = try!(trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty));
+    predicate_for_trait_ref(tcx, cause, trait_ref, recursion_depth)
+}
+
 /// Cast a trait reference into a reference to one of its super
 /// traits; returns `None` if `target_trait_def_id` is not a
 /// supertrait.
@@ -445,7 +470,7 @@ impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::Vtable<'tcx, N> {
                 v.repr(tcx),
 
             super::VtableDefaultTrait(ref t) =>
-                format!("VtableDefaultTrait({:?})", t),
+                t.repr(tcx),
 
             super::VtableClosure(ref d, ref s) =>
                 format!("VtableClosure({},{})",
@@ -486,6 +511,14 @@ impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableBuiltinData<N> {
     }
 }
 
+impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableDefaultTraitData<N> {
+    fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
+        format!("VtableDefaultTraitData(trait_def_id={}, nested={})",
+                self.trait_def_id.repr(tcx),
+                self.nested.repr(tcx))
+    }
+}
+
 impl<'tcx> Repr<'tcx> for super::VtableObjectData<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         format!("VtableObject(object_ty={})",
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 5652f23a16d..2fcee3d6213 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -5175,6 +5175,9 @@ pub fn impl_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
                                 &None => None
                             }
                         }
+                        ast::ItemDefTrait(_, ref ast_trait_ref) => {
+                            Some(ty::node_id_to_trait_ref(cx, ast_trait_ref.ref_id))
+                        }
                         _ => None
                     }
                 }
@@ -5999,7 +6002,6 @@ pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
 /// Records a trait-to-implementation mapping.
 pub fn record_default_trait_implementation(tcx: &ctxt, trait_def_id: DefId) {
 
-    //assert!(did.krate != ast::LOCAL_CRATE);
     if tcx.default_trait_impls.borrow().contains(&trait_def_id) {
         return;
     }
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 3f11655e16e..8ed6af652ce 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -507,6 +507,15 @@ impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableImplData<
     }
 }
 
+impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableDefaultTraitData<N> {
+    fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableDefaultTraitData<N> {
+        traits::VtableDefaultTraitData {
+            trait_def_id: self.trait_def_id,
+            nested: self.nested.fold_with(folder),
+        }
+    }
+}
+
 impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::VtableBuiltinData<N> {
     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableBuiltinData<N> {
         traits::VtableBuiltinData {
@@ -519,7 +528,7 @@ impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Vtable<'tcx, N>
     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::Vtable<'tcx, N> {
         match *self {
             traits::VtableImpl(ref v) => traits::VtableImpl(v.fold_with(folder)),
-            traits::VtableDefaultTrait(t) => traits::VtableDefaultTrait(t),
+            traits::VtableDefaultTrait(ref t) => traits::VtableDefaultTrait(t.fold_with(folder)),
             traits::VtableClosure(d, ref s) => {
                 traits::VtableClosure(d, s.fold_with(folder))
             }