Make projected types select out of the trait bounds.

13 files changed, 321 insertions, 164 deletions

diff --git a/src/librustc/middle/check_static.rs b/src/librustc/middle/check_static.rs
index e8df8e84029..fb20df020ac 100644
--- a/src/librustc/middle/check_static.rs
+++ b/src/librustc/middle/check_static.rs
@@ -31,7 +31,6 @@ use middle::infer;
 use middle::traits;
 use middle::mem_categorization as mc;
 use middle::expr_use_visitor as euv;
-use util::common::ErrorReported;
 use util::nodemap::NodeSet;
 
 use syntax::ast;
@@ -120,19 +119,14 @@ impl<'a, 'tcx> CheckStaticVisitor<'a, 'tcx> {
         let ty = ty::node_id_to_type(self.tcx, e.id);
         let infcx = infer::new_infer_ctxt(self.tcx);
         let mut fulfill_cx = traits::FulfillmentContext::new();
-        match traits::poly_trait_ref_for_builtin_bound(self.tcx, ty::BoundSync, ty) {
-            Ok(trait_ref) => {
-                let cause = traits::ObligationCause::new(e.span, e.id, traits::SharedStatic);
-                fulfill_cx.register_trait_ref(self.tcx, trait_ref, cause);
-                let env = ty::empty_parameter_environment();
-                match fulfill_cx.select_all_or_error(&infcx, &env, self.tcx) {
-                    Ok(()) => { },
-                    Err(ref errors) => {
-                      traits::report_fulfillment_errors(&infcx, errors);
-                    }
-                }
+        let cause = traits::ObligationCause::new(e.span, e.id, traits::SharedStatic);
+        fulfill_cx.register_builtin_bound(&infcx, ty, ty::BoundSync, cause);
+        let env = ty::empty_parameter_environment();
+        match fulfill_cx.select_all_or_error(&infcx, &env, self.tcx) {
+            Ok(()) => { },
+            Err(ref errors) => {
+                traits::report_fulfillment_errors(&infcx, errors);
             }
-            Err(ErrorReported) => { }
         }
     }
 }
diff --git a/src/librustc/middle/subst.rs b/src/librustc/middle/subst.rs
index 8d920e0a821..a87db776ce0 100644
--- a/src/librustc/middle/subst.rs
+++ b/src/librustc/middle/subst.rs
@@ -412,6 +412,10 @@ impl<T> VecPerParamSpace<T> {
         self.content.as_slice()
     }
 
+    pub fn to_vec(self) -> Vec<T> {
+        self.content
+    }
+
     pub fn all_vecs<P>(&self, mut pred: P) -> bool where
         P: FnMut(&[T]) -> bool,
     {
diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs
index 9cd1725e4df..0d2023ead4f 100644
--- a/src/librustc/middle/traits/fulfill.rs
+++ b/src/librustc/middle/traits/fulfill.rs
@@ -119,43 +119,43 @@ impl<'tcx> FulfillmentContext<'tcx> {
                 ty: ty_var
             });
         let obligation = Obligation::new(cause, projection.as_predicate());
-        self.register_predicate(infcx.tcx, obligation);
+        self.register_predicate(infcx, obligation);
         ty_var
     }
 
-    pub fn register_builtin_bound(&mut self,
-                                  tcx: &ty::ctxt<'tcx>,
-                                  ty: Ty<'tcx>,
-                                  builtin_bound: ty::BuiltinBound,
-                                  cause: ObligationCause<'tcx>)
+    pub fn register_builtin_bound<'a>(&mut self,
+                                      infcx: &InferCtxt<'a,'tcx>,
+                                      ty: Ty<'tcx>,
+                                      builtin_bound: ty::BuiltinBound,
+                                      cause: ObligationCause<'tcx>)
     {
-        match predicate_for_builtin_bound(tcx, cause, builtin_bound, 0, ty) {
+        match predicate_for_builtin_bound(infcx.tcx, cause, builtin_bound, 0, ty) {
             Ok(predicate) => {
-                self.register_predicate(tcx, predicate);
+                self.register_predicate(infcx, predicate);
             }
             Err(ErrorReported) => { }
         }
     }
 
-    pub fn register_region_obligation(&mut self,
-                                      tcx: &ty::ctxt<'tcx>,
-                                      t_a: Ty<'tcx>,
-                                      r_b: ty::Region,
-                                      cause: ObligationCause<'tcx>)
+    pub fn register_region_obligation<'a>(&mut self,
+                                          infcx: &InferCtxt<'a,'tcx>,
+                                          t_a: Ty<'tcx>,
+                                          r_b: ty::Region,
+                                          cause: ObligationCause<'tcx>)
     {
-        register_region_obligation(tcx, t_a, r_b, cause, &mut self.region_obligations);
+        register_region_obligation(infcx.tcx, t_a, r_b, cause, &mut self.region_obligations);
     }
 
     pub fn register_predicate<'a>(&mut self,
-                                  tcx: &ty::ctxt<'tcx>,
+                                  infcx: &InferCtxt<'a,'tcx>,
                                   obligation: PredicateObligation<'tcx>)
     {
         if !self.duplicate_set.insert(obligation.predicate.clone()) {
-            debug!("register_predicate({}) -- already seen, skip", obligation.repr(tcx));
+            debug!("register_predicate({}) -- already seen, skip", obligation.repr(infcx.tcx));
             return;
         }
 
-        debug!("register_predicate({})", obligation.repr(tcx));
+        debug!("register_predicate({})", obligation.repr(infcx.tcx));
         self.predicates.push(obligation);
     }
 
@@ -230,7 +230,6 @@ impl<'tcx> FulfillmentContext<'tcx> {
                self.predicates.len(),
                only_new_obligations);
 
-        let tcx = selcx.tcx();
         let mut errors = Vec::new();
 
         loop {
@@ -279,7 +278,7 @@ impl<'tcx> FulfillmentContext<'tcx> {
             // Now go through all the successful ones,
             // registering any nested obligations for the future.
             for new_obligation in new_obligations.into_iter() {
-                self.register_predicate(tcx, new_obligation);
+                self.register_predicate(selcx.infcx(), new_obligation);
             }
         }
 
@@ -469,17 +468,22 @@ fn process_predicate<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>,
                             CodeProjectionError(e)));
                     true
                 }
-                Err(project::ProjectionError::TraitSelectionError(e)) => {
-                    // Extract just the `T : Trait` from `<T as
-                    // Trait>::Name == U`, so that when we report an
-                    // error to the user, it says something like "`T :
-                    // Trait` not satisfied".5D
+                Err(project::ProjectionError::TraitSelectionError(_)) => {
+                    // There was an error matching `T : Trait` (which
+                    // is a pre-requisite for `<T as Trait>::Name`
+                    // being valid).  We could just report the error
+                    // now, but that tends to lead to double error
+                    // reports for the user (one for the obligation `T
+                    // : Trait`, typically incurred somewhere else,
+                    // and one from here). Instead, we'll create the
+                    // `T : Trait` obligation and add THAT as a
+                    // requirement. This will (eventually) trigger the
+                    // same error, but it will also wind up flagged as
+                    // a duplicate if another requirement that `T :
+                    // Trait` arises from somewhere else.
                     let trait_predicate = data.to_poly_trait_ref();
                     let trait_obligation = obligation.with(trait_predicate.as_predicate());
-                    errors.push(
-                        FulfillmentError::new(
-                            trait_obligation,
-                            CodeSelectionError(e)));
+                    new_obligations.push(trait_obligation);
                     true
                 }
             }
diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs
index b7e2304849a..d7febea8909 100644
--- a/src/librustc/middle/traits/mod.rs
+++ b/src/librustc/middle/traits/mod.rs
@@ -37,7 +37,6 @@ pub use self::util::elaborate_predicates;
 pub use self::util::trait_ref_for_builtin_bound;
 pub use self::util::supertraits;
 pub use self::util::Supertraits;
-pub use self::util::search_trait_and_supertraits_from_bound;
 pub use self::util::transitive_bounds;
 
 mod coherence;
@@ -189,10 +188,10 @@ pub type SelectionResult<'tcx, T> = Result<Option<T>, SelectionError<'tcx>>;
 ///
 ///    // Case B: Vtable must be provided by caller. This applies when
 ///    // type is a type parameter.
-///    param.clone();    // VtableParam(Oblig_1)
+///    param.clone();    // VtableParam
 ///
 ///    // Case C: A mix of cases A and B.
-///    mixed.clone();    // Vtable(Impl_1, [VtableParam(Oblig_1)])
+///    mixed.clone();    // Vtable(Impl_1, [VtableParam])
 /// }
 /// ```
 ///
@@ -206,7 +205,7 @@ pub enum Vtable<'tcx, N> {
 
     /// Successful resolution to an obligation provided by the caller
     /// for some type parameter.
-    VtableParam(VtableParamData<'tcx>),
+    VtableParam,
 
     /// Successful resolution for a builtin trait.
     VtableBuiltin(VtableBuiltinData<N>),
@@ -243,15 +242,6 @@ pub struct VtableBuiltinData<N> {
     pub nested: subst::VecPerParamSpace<N>
 }
 
-/// A vtable provided as a parameter by the caller. For example, in a
-/// function like `fn foo<T:Eq>(...)`, if the `eq()` method is invoked
-/// on an instance of `T`, the vtable would be of type `VtableParam`.
-#[deriving(PartialEq,Eq,Clone)]
-pub struct VtableParamData<'tcx> {
-    // In the above example, this would `Eq`
-    pub bound: ty::PolyTraitRef<'tcx>,
-}
-
 /// True if neither the trait nor self type is local. Note that `impl_def_id` must refer to an impl
 /// of a trait, not an inherent impl.
 pub fn is_orphan_impl(tcx: &ty::ctxt,
@@ -302,7 +292,7 @@ pub fn type_known_to_meet_builtin_bound<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>,
     // (there shouldn't really be any anyhow).
     let cause = ObligationCause::misc(DUMMY_SP, ast::DUMMY_NODE_ID);
 
-    fulfill_cx.register_builtin_bound(infcx.tcx, ty, bound, cause);
+    fulfill_cx.register_builtin_bound(infcx, ty, bound, cause);
 
     // Note: we only assume something is `Copy` if we can
     // *definitively* show that it implements `Copy`. Otherwise,
@@ -361,7 +351,7 @@ impl<'tcx, N> Vtable<'tcx, N> {
             VtableImpl(ref i) => i.iter_nested(),
             VtableFnPointer(..) => (&[]).iter(),
             VtableUnboxedClosure(..) => (&[]).iter(),
-            VtableParam(_) => (&[]).iter(),
+            VtableParam => (&[]).iter(),
             VtableBuiltin(ref i) => i.iter_nested(),
         }
     }
@@ -371,7 +361,7 @@ impl<'tcx, N> Vtable<'tcx, N> {
             VtableImpl(ref i) => VtableImpl(i.map_nested(op)),
             VtableFnPointer(ref sig) => VtableFnPointer((*sig).clone()),
             VtableUnboxedClosure(d, ref s) => VtableUnboxedClosure(d, s.clone()),
-            VtableParam(ref p) => VtableParam((*p).clone()),
+            VtableParam => VtableParam,
             VtableBuiltin(ref b) => VtableBuiltin(b.map_nested(op)),
         }
     }
@@ -383,7 +373,7 @@ impl<'tcx, N> Vtable<'tcx, N> {
             VtableImpl(i) => VtableImpl(i.map_move_nested(op)),
             VtableFnPointer(sig) => VtableFnPointer(sig),
             VtableUnboxedClosure(d, s) => VtableUnboxedClosure(d, s),
-            VtableParam(p) => VtableParam(p),
+            VtableParam => VtableParam,
             VtableBuiltin(no) => VtableBuiltin(no.map_move_nested(op)),
         }
     }
diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs
index 0594c0ac3b8..43f97de2d43 100644
--- a/src/librustc/middle/traits/project.rs
+++ b/src/librustc/middle/traits/project.rs
@@ -128,10 +128,12 @@ pub fn project_type<'cx,'tcx>(
                                                   &mut candidates);
 
     if candidates.vec.is_empty() {
-        // TODO This `if` is not necessarily wrong, but it needs an
-        // explanation, and it should probably be accompanied by a
-        // similar rule in `select.rs`. Currently it's *needed*
-        // because the impl-trait-for-trait branch has not landed.
+        // FIXME(#20297) -- In `select.rs` there is similar logic that
+        // gives precedence to where-clauses, but it's a bit more
+        // fine-grained. I was lazy here and just always give
+        // precedence to where-clauses or other such sources over
+        // actually dredging through impls. This logic probably should
+        // be tightened up.
 
         let () = try!(assemble_candidates_from_impls(selcx,
                                                      obligation,
diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs
index 2a3bb3c80c8..2e4bdadb8c2 100644
--- a/src/librustc/middle/traits/select.rs
+++ b/src/librustc/middle/traits/select.rs
@@ -24,7 +24,7 @@ use super::{SelectionError, Unimplemented, Overflow, OutputTypeParameterMismatch
 use super::{Selection};
 use super::{SelectionResult};
 use super::{VtableBuiltin, VtableImpl, VtableParam, VtableUnboxedClosure, VtableFnPointer};
-use super::{VtableImplData, VtableParamData, VtableBuiltinData};
+use super::{VtableImplData, VtableBuiltinData};
 use super::{util};
 
 use middle::fast_reject;
@@ -131,9 +131,13 @@ pub enum MethodMatchedData {
 #[deriving(PartialEq,Eq,Show,Clone)]
 enum SelectionCandidate<'tcx> {
     BuiltinCandidate(ty::BuiltinBound),
-    ParamCandidate(VtableParamData<'tcx>),
+    ParamCandidate(ty::PolyTraitRef<'tcx>),
     ImplCandidate(ast::DefId),
 
+    /// This is a trait matching with a projected type as `Self`, and
+    /// we found an applicable bound in the trait definition.
+    ProjectionCandidate,
+
     /// Implementation of a `Fn`-family trait by one of the
     /// anonymous types generated for a `||` expression.
     UnboxedClosureCandidate(/* closure */ ast::DefId, Substs<'tcx>),
@@ -507,8 +511,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
 
         let mut candidates = candidate_set.vec;
 
-        debug!("assembled {} candidates for {}",
-               candidates.len(), stack.repr(self.tcx()));
+        debug!("assembled {} candidates for {}: {}",
+               candidates.len(),
+               stack.repr(self.tcx()),
+               candidates.repr(self.tcx()));
 
         // At this point, we know that each of the entries in the
         // candidate set is *individually* applicable. Now we have to
@@ -706,11 +712,137 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
         }
 
+        self.assemble_candidates_from_projected_tys(obligation, &mut candidates);
         try!(self.assemble_candidates_from_caller_bounds(obligation, &mut candidates));
         debug!("candidate list size: {}", candidates.vec.len());
         Ok(candidates)
     }
 
+    fn assemble_candidates_from_projected_tys(&mut self,
+                                              obligation: &TraitObligation<'tcx>,
+                                              candidates: &mut SelectionCandidateSet<'tcx>)
+    {
+        let poly_trait_predicate =
+            self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
+
+        debug!("assemble_candidates_for_projected_tys({},{})",
+               obligation.repr(self.tcx()),
+               poly_trait_predicate.repr(self.tcx()));
+
+        // FIXME(#20297) -- just examining the self-type is very simplistic
+
+        // before we go into the whole skolemization thing, just
+        // quickly check if the self-type is a projection at all.
+        let trait_def_id = match poly_trait_predicate.0.trait_ref.self_ty().sty {
+            ty::ty_projection(ref data) => data.trait_ref.def_id,
+            ty::ty_infer(ty::TyVar(_)) => {
+                // TODO ignore potential ambiguity so that we can do
+                // better inference, need to get our story
+                // straight(er) here, I think.
+                // candidates.ambiguous = true;
+                return;
+            }
+            _ => { return; }
+        };
+
+        debug!("assemble_candidates_for_projected_tys: trait_def_id={}",
+               trait_def_id.repr(self.tcx()));
+
+        let result = self.infcx.probe(|snapshot| {
+            self.match_projection_obligation_against_bounds_from_trait(obligation,
+                                                                       snapshot)
+        });
+
+        if result {
+            candidates.vec.push(ProjectionCandidate);
+        }
+    }
+
+    fn match_projection_obligation_against_bounds_from_trait(
+        &mut self,
+        obligation: &TraitObligation<'tcx>,
+        snapshot: &infer::CombinedSnapshot)
+        -> bool
+    {
+        let poly_trait_predicate =
+            self.infcx().resolve_type_vars_if_possible(&obligation.predicate);
+        let (skol_trait_predicate, skol_map) =
+            self.infcx().skolemize_late_bound_regions(&poly_trait_predicate, snapshot);
+        debug!("match_projection_obligation_against_bounds_from_trait: \
+                skol_trait_predicate={} skol_map={}",
+               skol_trait_predicate.repr(self.tcx()),
+               skol_map.repr(self.tcx()));
+
+        let projection_trait_ref = match skol_trait_predicate.trait_ref.self_ty().sty {
+            ty::ty_projection(ref data) => &data.trait_ref,
+            _ => {
+                self.tcx().sess.span_bug(
+                    obligation.cause.span,
+                    format!("match_projection_obligation_against_bounds_from_trait() called \
+                             but self-ty not a projection: {}",
+                            skol_trait_predicate.trait_ref.self_ty().repr(self.tcx())).as_slice());
+            }
+        };
+        debug!("match_projection_obligation_against_bounds_from_trait: \
+                projection_trait_ref={}",
+               projection_trait_ref.repr(self.tcx()));
+
+        let trait_def = ty::lookup_trait_def(self.tcx(), projection_trait_ref.def_id);
+        let bounds = trait_def.generics.to_bounds(self.tcx(), &projection_trait_ref.substs);
+        debug!("match_projection_obligation_against_bounds_from_trait: \
+                bounds={}",
+               bounds.repr(self.tcx()));
+
+        let matching_bound =
+            util::elaborate_predicates(self.tcx(), bounds.predicates.to_vec())
+            .filter_to_traits()
+            .find(
+                |bound| self.infcx.probe(
+                    |_| self.match_projection(obligation,
+                                              bound.clone(),
+                                              skol_trait_predicate.trait_ref.clone(),
+                                              &skol_map,
+                                              snapshot)));
+
+        debug!("match_projection_obligation_against_bounds_from_trait: \
+                matching_bound={}",
+               matching_bound.repr(self.tcx()));
+        match matching_bound {
+            None => false,
+            Some(bound) => {
+                // Repeat the successful match, if any, this time outside of a probe.
+                let result = self.match_projection(obligation,
+                                                   bound,
+                                                   skol_trait_predicate.trait_ref.clone(),
+                                                   &skol_map,
+                                                   snapshot);
+                assert!(result);
+                true
+            }
+        }
+    }
+
+    fn match_projection(&mut self,
+                        obligation: &TraitObligation<'tcx>,
+                        trait_bound: ty::PolyTraitRef<'tcx>,
+                        skol_trait_ref: Rc<ty::TraitRef<'tcx>>,
+                        skol_map: &infer::SkolemizationMap,
+                        snapshot: &infer::CombinedSnapshot)
+                        -> bool
+    {
+        assert!(!skol_trait_ref.has_escaping_regions());
+        let origin = infer::RelateOutputImplTypes(obligation.cause.span);
+        match self.infcx.sub_poly_trait_refs(false,
+                                             origin,
+                                             trait_bound.clone(),
+                                             ty::Binder(skol_trait_ref.clone())) {
+            Ok(()) => { }
+            Err(_) => { return false; }
+        }
+
+        self.infcx.leak_check(skol_map, snapshot).is_ok()
+    }
+
     /// Given an obligation like `<SomeTrait for T>`, search the obligations that the caller
     /// supplied to find out whether it is listed among them.
     ///
@@ -738,8 +870,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     |_| self.match_where_clause(obligation, bound.clone())).is_ok());
 
         let param_candidates =
-            matching_bounds.map(
-                |bound| ParamCandidate(VtableParamData { bound: bound }));
+            matching_bounds.map(|bound| ParamCandidate(bound));
 
         candidates.vec.extend(param_candidates);
 
@@ -933,7 +1064,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                                                    -> bool
     {
         match (candidate_i, candidate_j) {
-            (&ImplCandidate(impl_def_id), &ParamCandidate(ref vt)) => {
+            (&ImplCandidate(impl_def_id), &ParamCandidate(ref bound)) => {
                 debug!("Considering whether to drop param {} in favor of impl {}",
                        candidate_i.repr(self.tcx()),
                        candidate_j.repr(self.tcx()));
@@ -954,10 +1085,23 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     let origin =
                         infer::RelateOutputImplTypes(stack.obligation.cause.span);
                     self.infcx
-                        .sub_poly_trait_refs(false, origin, poly_impl_trait_ref, vt.bound.clone())
+                        .sub_poly_trait_refs(false, origin, poly_impl_trait_ref, bound.clone())
                         .is_ok()
                 })
             }
+            (&ProjectionCandidate, &ParamCandidate(_)) => {
+                // FIXME(#20297) -- this gives where clauses precedent
+                // over projections. Really these are just two means
+                // of deducing information (one based on the where
+                // clauses on the trait definition; one based on those
+                // on the enclosing scope), and it'd be better to
+                // integrate them more intelligently. But for now this
+                // seems ok. If we DON'T give where clauses
+                // precedence, we run into trouble in default methods,
+                // where both the projection bounds for `Self::A` and
+                // the where clauses are in scope.
+                true
+            }
             _ => {
                 *candidate_i == *candidate_j
             }
@@ -1390,8 +1534,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             }
 
             ParamCandidate(param) => {
-                Ok(VtableParam(
-                    try!(self.confirm_param_candidate(obligation, param))))
+                self.confirm_param_candidate(obligation, param);
+                Ok(VtableParam)
             }
 
             ImplCandidate(impl_def_id) => {
@@ -1410,14 +1554,30 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                     try!(self.confirm_fn_pointer_candidate(obligation));
                 Ok(VtableFnPointer(fn_type))
             }
+
+            ProjectionCandidate => {
+                self.confirm_projection_candidate(obligation);
+                Ok(VtableParam)
+            }
         }
     }
 
+    fn confirm_projection_candidate(&mut self,
+                                    obligation: &TraitObligation<'tcx>)
+    {
+        let _: Result<(),()> =
+            self.infcx.try(|snapshot| {
+                let result =
+                    self.match_projection_obligation_against_bounds_from_trait(obligation,
+                                                                               snapshot);
+                assert!(result);
+                Ok(())
+            });
+    }
+
     fn confirm_param_candidate(&mut self,
                                obligation: &TraitObligation<'tcx>,
-                               param: VtableParamData<'tcx>)
-                               -> Result<VtableParamData<'tcx>,
-                                         SelectionError<'tcx>>
+                               param: ty::PolyTraitRef<'tcx>)
     {
         debug!("confirm_param_candidate({},{})",
                obligation.repr(self.tcx()),
@@ -1429,12 +1589,12 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
         // transactional boundary; it should not fail.
         match self.confirm_poly_trait_refs(obligation.cause.clone(),
                                            obligation.predicate.to_poly_trait_ref(),
-                                           param.bound.clone()) {
-            Ok(()) => Ok(param),
+                                           param.clone()) {
+            Ok(()) => { }
             Err(_) => {
                 self.tcx().sess.bug(
                     format!("Where clause `{}` was applicable to `{}` but now is not",
-                            param.bound.repr(self.tcx()),
+                            param.repr(self.tcx()),
                             obligation.repr(self.tcx())).as_slice());
             }
         }
@@ -1981,14 +2141,13 @@ impl<'tcx> Repr<'tcx> for SelectionCandidate<'tcx> {
         match *self {
             ErrorCandidate => format!("ErrorCandidate"),
             BuiltinCandidate(b) => format!("BuiltinCandidate({})", b),
+            ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
+            ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
+            ProjectionCandidate => format!("ProjectionCandidate"),
+            FnPointerCandidate => format!("FnPointerCandidate"),
             UnboxedClosureCandidate(c, ref s) => {
                 format!("UnboxedClosureCandidate({},{})", c, s.repr(tcx))
             }
-            FnPointerCandidate => {
-                format!("FnPointerCandidate")
-            }
-            ParamCandidate(ref a) => format!("ParamCandidate({})", a.repr(tcx)),
-            ImplCandidate(a) => format!("ImplCandidate({})", a.repr(tcx)),
         }
     }
 }
diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs
index 00995e1ee43..95567d8240a 100644
--- a/src/librustc/middle/traits/util.rs
+++ b/src/librustc/middle/traits/util.rs
@@ -20,7 +20,7 @@ use util::common::ErrorReported;
 use util::ppaux::Repr;
 
 use super::{Obligation, ObligationCause, PredicateObligation,
-            VtableImpl, VtableParam, VtableParamData, VtableImplData};
+            VtableImpl, VtableParam, VtableImplData};
 
 ///////////////////////////////////////////////////////////////////////////
 // `Elaboration` iterator
@@ -78,6 +78,10 @@ pub fn elaborate_predicates<'cx, 'tcx>(
 }
 
 impl<'cx, 'tcx> Elaborator<'cx, 'tcx> {
+    pub fn filter_to_traits(self) -> Supertraits<'cx, 'tcx> {
+        Supertraits { elaborator: self }
+    }
+
     fn push(&mut self, predicate: &ty::Predicate<'tcx>) {
         match *predicate {
             ty::Predicate::Trait(ref data) => {
@@ -183,16 +187,14 @@ pub fn supertraits<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
                               trait_ref: ty::PolyTraitRef<'tcx>)
                               -> Supertraits<'cx, 'tcx>
 {
-    let elaborator = elaborate_trait_ref(tcx, trait_ref);
-    Supertraits { elaborator: elaborator }
+    elaborate_trait_ref(tcx, trait_ref).filter_to_traits()
 }
 
 pub fn transitive_bounds<'cx, 'tcx>(tcx: &'cx ty::ctxt<'tcx>,
                                     bounds: &[ty::PolyTraitRef<'tcx>])
                                     -> Supertraits<'cx, 'tcx>
 {
-    let elaborator = elaborate_trait_refs(tcx, bounds);
-    Supertraits { elaborator: elaborator }
+    elaborate_trait_refs(tcx, bounds).filter_to_traits()
 }
 
 impl<'cx, 'tcx> Iterator<ty::PolyTraitRef<'tcx>> for Supertraits<'cx, 'tcx> {
@@ -247,12 +249,6 @@ impl<'tcx, N> fmt::Show for VtableImplData<'tcx, N> {
     }
 }
 
-impl<'tcx> fmt::Show for VtableParamData<'tcx> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        write!(f, "VtableParam(...)")
-    }
-}
-
 /// See `super::obligations_for_generics`
 pub fn predicates_for_generics<'tcx>(tcx: &ty::ctxt<'tcx>,
                                      cause: ObligationCause<'tcx>,
@@ -306,26 +302,6 @@ pub fn predicate_for_builtin_bound<'tcx>(
     })
 }
 
-/// Starting from a caller obligation `caller_bound` (which has coordinates `space`/`i` in the list
-/// of caller obligations), search through the trait and supertraits to find one where `test(d)` is
-/// true, where `d` is the def-id of the trait/supertrait. If any is found, return `Some(p)` where
-/// `p` is the path to that trait/supertrait. Else `None`.
-pub fn search_trait_and_supertraits_from_bound<'tcx,F>(tcx: &ty::ctxt<'tcx>,
-                                                       caller_bound: ty::PolyTraitRef<'tcx>,
-                                                       mut test: F)
-                                                       -> Option<VtableParamData<'tcx>>
-    where F: FnMut(ast::DefId) -> bool,
-{
-    for bound in transitive_bounds(tcx, &[caller_bound]) {
-        if test(bound.def_id()) {
-            let vtable_param = VtableParamData { bound: bound };
-            return Some(vtable_param);
-        }
-    }
-
-    return None;
-}
-
 impl<'tcx,O:Repr<'tcx>> Repr<'tcx> for super::Obligation<'tcx, O> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         format!("Obligation(predicate={},depth={})",
@@ -349,8 +325,8 @@ impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::Vtable<'tcx, N> {
                 format!("VtableFnPointer({})",
                         d.repr(tcx)),
 
-            super::VtableParam(ref v) =>
-                format!("VtableParam({})", v.repr(tcx)),
+            super::VtableParam =>
+                format!("VtableParam"),
 
             super::VtableBuiltin(ref d) =>
                 d.repr(tcx)
@@ -374,13 +350,6 @@ impl<'tcx, N:Repr<'tcx>> Repr<'tcx> for super::VtableBuiltinData<N> {
     }
 }
 
-impl<'tcx> Repr<'tcx> for super::VtableParamData<'tcx> {
-    fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
-        format!("VtableParam(bound={})",
-                self.bound.repr(tcx))
-    }
-}
-
 impl<'tcx> Repr<'tcx> for super::SelectionError<'tcx> {
     fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
         match *self {
diff --git a/src/librustc/middle/ty_fold.rs b/src/librustc/middle/ty_fold.rs
index 3aff69c0178..1e7605c0f17 100644
--- a/src/librustc/middle/ty_fold.rs
+++ b/src/librustc/middle/ty_fold.rs
@@ -501,20 +501,12 @@ impl<'tcx, N: TypeFoldable<'tcx>> TypeFoldable<'tcx> for traits::Vtable<'tcx, N>
             traits::VtableFnPointer(ref d) => {
                 traits::VtableFnPointer(d.fold_with(folder))
             }
-            traits::VtableParam(ref p) => traits::VtableParam(p.fold_with(folder)),
+            traits::VtableParam => traits::VtableParam,
             traits::VtableBuiltin(ref d) => traits::VtableBuiltin(d.fold_with(folder)),
         }
     }
 }
 
-impl<'tcx> TypeFoldable<'tcx> for traits::VtableParamData<'tcx> {
-    fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> traits::VtableParamData<'tcx> {
-        traits::VtableParamData {
-            bound: self.bound.fold_with(folder),
-        }
-    }
-}
-
 impl<'tcx> TypeFoldable<'tcx> for ty::EquatePredicate<'tcx> {
     fn fold_with<F:TypeFolder<'tcx>>(&self, folder: &mut F) -> ty::EquatePredicate<'tcx> {
         ty::EquatePredicate(self.0.fold_with(folder),
diff --git a/src/librustc_trans/trans/common.rs b/src/librustc_trans/trans/common.rs
index 694fbf251dd..06819aac5bc 100644
--- a/src/librustc_trans/trans/common.rs
+++ b/src/librustc_trans/trans/common.rs
@@ -960,7 +960,7 @@ pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
     // iterating early.
     let mut fulfill_cx = traits::FulfillmentContext::new();
     let vtable = selection.map_move_nested(|predicate| {
-        fulfill_cx.register_predicate(infcx.tcx, predicate);
+        fulfill_cx.register_predicate(&infcx, predicate);
     });
     match fulfill_cx.select_all_or_error(&infcx, &param_env, tcx) {
         Ok(()) => { }
diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs
index 00b17ca00df..2ede6e2e47f 100644
--- a/src/librustc_trans/trans/meth.rs
+++ b/src/librustc_trans/trans/meth.rs
@@ -565,7 +565,7 @@ pub fn get_vtable<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
                 let llfn = vec![trans_fn_pointer_shim(bcx.ccx(), bare_fn_ty)];
                 llfn.into_iter()
             }
-            traits::VtableParam(..) => {
+            traits::VtableParam => {
                 bcx.sess().bug(
                     format!("resolved vtable for {} to bad vtable {} in trans",
                             trait_ref.repr(bcx.tcx()),
diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs
index be8fa21cf0e..4bc1246d393 100644
--- a/src/librustc_typeck/check/mod.rs
+++ b/src/librustc_typeck/check/mod.rs
@@ -1871,7 +1871,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                                   cause: traits::ObligationCause<'tcx>)
     {
         self.inh.fulfillment_cx.borrow_mut()
-            .register_builtin_bound(self.tcx(), ty, builtin_bound, cause);
+            .register_builtin_bound(self.infcx(), ty, builtin_bound, cause);
     }
 
     pub fn register_predicate(&self,
@@ -1882,7 +1882,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
         self.inh.fulfillment_cx
             .borrow_mut()
-            .register_predicate(self.tcx(), obligation);
+            .register_predicate(self.infcx(), obligation);
     }
 
     pub fn to_ty(&self, ast_t: &ast::Ty) -> Ty<'tcx> {
@@ -2026,7 +2026,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                                       cause: traits::ObligationCause<'tcx>)
     {
         let mut fulfillment_cx = self.inh.fulfillment_cx.borrow_mut();
-        fulfillment_cx.register_region_obligation(self.tcx(), ty, region, cause);
+        fulfillment_cx.register_region_obligation(self.infcx(), ty, region, cause);
     }
 
     pub fn add_default_region_param_bounds(&self,
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index dfe54674d63..b311f10c0a3 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -842,16 +842,15 @@ pub fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                             generics,
                                             items);
 
+    assert_eq!(mk_item_substs(ccx, &ty_generics), substs);
+
     let self_param_ty = ty::ParamTy::for_self(def_id);
 
     let bounds = compute_bounds(ccx,
-                                token::SELF_KEYWORD_NAME,
-                                self_param_ty,
+                                self_param_ty.to_ty(ccx.tcx),
                                 bounds.as_slice(),
                                 it.span);
 
-    let substs = ccx.tcx.mk_substs(mk_item_substs(ccx, &ty_generics));
-
     let associated_type_names: Vec<_> =
         items.iter()
              .filter_map(|item| {
@@ -862,14 +861,16 @@ pub fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
              })
             .collect();
 
+    let trait_ref = Rc::new(ty::TraitRef {
+        def_id: def_id,
+        substs: substs
+    });
+
     let trait_def = Rc::new(ty::TraitDef {
         unsafety: unsafety,
         generics: ty_generics,
         bounds: bounds,
-        trait_ref: Rc::new(ty::TraitRef {
-            def_id: def_id,
-            substs: substs
-        }),
+        trait_ref: trait_ref,
         associated_type_names: associated_type_names,
     });
     tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone());
@@ -1027,9 +1028,12 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                    trait_id: ast::NodeId,
                                    substs: &'tcx subst::Substs<'tcx>,
                                    ast_generics: &ast::Generics,
-                                   _items: &[ast::TraitItem])
+                                   trait_items: &[ast::TraitItem])
                                    -> ty::Generics<'tcx>
 {
+    debug!("ty_generics_for_trait(trait_id={}, substs={})",
+           local_def(trait_id).repr(ccx.tcx), substs.repr(ccx.tcx));
+
     let mut generics =
         ty_generics(ccx,
                     subst::TypeSpace,
@@ -1045,8 +1049,8 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
     let param_id = trait_id;
 
     let self_trait_ref =
-        ty::Binder(Rc::new(ty::TraitRef { def_id: local_def(trait_id),
-                                          substs: substs }));
+        Rc::new(ty::TraitRef { def_id: local_def(trait_id),
+                               substs: substs });
 
     let def = ty::TypeParameterDef {
         space: subst::SelfSpace,
@@ -1056,7 +1060,7 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
         bounds: ty::ParamBounds {
             region_bounds: vec!(),
             builtin_bounds: ty::empty_builtin_bounds(),
-            trait_bounds: vec!(self_trait_ref.clone()),
+            trait_bounds: vec!(ty::Binder(self_trait_ref.clone())),
             projection_bounds: vec!(),
         },
         default: None
@@ -1068,7 +1072,47 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
 
     generics.predicates.push(subst::SelfSpace, self_trait_ref.as_predicate());
 
-    generics
+    let assoc_predicates = predicates_for_associated_types(ccx,
+                                                           &self_trait_ref,
+                                                           trait_items);
+
+    debug!("ty_generics_for_trait: assoc_predicates={}", assoc_predicates.repr(ccx.tcx));
+
+    for assoc_predicate in assoc_predicates.into_iter() {
+        generics.predicates.push(subst::SelfSpace, assoc_predicate);
+    }
+
+    return generics;
+
+    fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
+                                                 self_trait_ref: &Rc<ty::TraitRef<'tcx>>,
+                                                 trait_items: &[ast::TraitItem])
+                                                 -> Vec<ty::Predicate<'tcx>>
+    {
+        trait_items
+            .iter()
+            .flat_map(|trait_item| {
+                let assoc_type_def = match *trait_item {
+                    ast::TypeTraitItem(ref assoc_type) => &assoc_type.ty_param,
+                    ast::RequiredMethod(..) | ast::ProvidedMethod(..) => {
+                        return vec!().into_iter();
+                    }
+                };
+
+                let assoc_ty = ty::mk_projection(ccx.tcx,
+                                                 self_trait_ref.clone(),
+                                                 assoc_type_def.ident.name);
+
+                let bounds = compute_bounds(ccx,
+                                            assoc_ty,
+                                            assoc_type_def.bounds.as_slice(),
+                                            &assoc_type_def.unbound,
+                                            assoc_type_def.span);
+
+                ty::predicates(ccx.tcx, assoc_ty, &bounds).into_iter()
+            })
+            .collect()
+    }
 }
 
 fn ty_generics_for_fn_or_method<'tcx,AC>(
@@ -1269,8 +1313,7 @@ fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
 
     let param_ty = ty::ParamTy::new(space, index, local_def(param.id));
     let bounds = compute_bounds(this,
-                                param.ident.name,
-                                param_ty,
+                                param_ty.to_ty(this.tcx()),
                                 param.bounds[],
                                 param.span);
     let default = match param.default {
@@ -1312,8 +1355,7 @@ fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
 /// a region) to ty's notion of ty param bounds, which can either be user-defined traits, or the
 /// built-in trait (formerly known as kind): Send.
 fn compute_bounds<'tcx,AC>(this: &AC,
-                           name_of_bounded_thing: ast::Name,
-                           param_ty: ty::ParamTy,
+                           param_ty: ty::Ty<'tcx>,
                            ast_bounds: &[ast::TyParamBound],
                            span: Span)
                            -> ty::ParamBounds<'tcx>
@@ -1329,7 +1371,7 @@ fn compute_bounds<'tcx,AC>(this: &AC,
                       span);
 
     check_bounds_compatible(this.tcx(),
-                            name_of_bounded_thing,
+                            param_ty,
                             &param_bounds,
                             span);
 
@@ -1339,7 +1381,7 @@ fn compute_bounds<'tcx,AC>(this: &AC,
 }
 
 fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
-                                 name_of_bounded_thing: ast::Name,
+                                 param_ty: Ty<'tcx>,
                                  param_bounds: &ty::ParamBounds<'tcx>,
                                  span: Span) {
     // Currently the only bound which is incompatible with other bounds is
@@ -1352,9 +1394,9 @@ fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
                 let trait_def = ty::lookup_trait_def(tcx, trait_ref.def_id());
                 if trait_def.bounds.builtin_bounds.contains(&ty::BoundSized) {
                     span_err!(tcx.sess, span, E0129,
-                              "incompatible bounds on type parameter `{}`, \
+                              "incompatible bounds on `{}`, \
                                bound `{}` does not allow unsized type",
-                              name_of_bounded_thing.user_string(tcx),
+                              param_ty.user_string(tcx),
                               trait_ref.user_string(tcx));
                 }
                 true
@@ -1364,7 +1406,7 @@ fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
 
 fn conv_param_bounds<'tcx,AC>(this: &AC,
                               span: Span,
-                              param_ty: ty::ParamTy,
+                              param_ty: ty::Ty<'tcx>,
                               ast_bounds: &[ast::TyParamBound])
                               -> ty::ParamBounds<'tcx>
                               where AC: AstConv<'tcx>
@@ -1382,7 +1424,7 @@ fn conv_param_bounds<'tcx,AC>(this: &AC,
             astconv::instantiate_poly_trait_ref(this,
                                                 &ExplicitRscope,
                                                 bound,
-                                                Some(param_ty.to_ty(this.tcx())),
+                                                Some(param_ty),
                                                 &mut projection_bounds)
         })
         .collect();
diff --git a/src/test/compile-fail/associated-types-path-2.rs b/src/test/compile-fail/associated-types-path-2.rs
index caf8ab3695d..486d3d38c60 100644
--- a/src/test/compile-fail/associated-types-path-2.rs
+++ b/src/test/compile-fail/associated-types-path-2.rs
@@ -26,9 +26,10 @@ pub fn f2<T: Foo>(a: T) -> T::A {
 }
 
 pub fn main() {
-    f1(2i, 4i); //~ERROR the trait `Foo` is not implemented
-    f1(2u, 4u); //~ERROR the trait `Foo` is not implemented
-    f1(2u, 4i); //~ERROR the trait `Foo` is not implemented
+    f1(2i, 4i); //~ ERROR expected uint, found int
+    f1(2i, 4u);
+    f1(2u, 4u); //~ ERROR the trait `Foo` is not implemented
+    f1(2u, 4i); //~ ERROR the trait `Foo` is not implemented
 
-    let _: int = f2(2i); //~ERROR mismatched types: expected `int`, found `uint`
+    let _: int = f2(2i); //~ERROR expected `int`, found `uint`
 }