auto merge of #20073 : nikomatsakis/rust/generalized-where-clause-parser, r=nikomatsakis

This is the same branch as #20002 but with the pretty-printing test fixed.

26 files changed, 561 insertions, 150 deletions

diff --git a/src/librustc/middle/privacy.rs b/src/librustc/middle/privacy.rs
index 8c566dd288e..7c931700f83 100644
--- a/src/librustc/middle/privacy.rs
+++ b/src/librustc/middle/privacy.rs
@@ -1505,6 +1505,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for VisiblePrivateTypesVisitor<'a, 'tcx> {
                         self.check_ty_param_bound(bound_pred.span, bound)
                     }
                 }
+                &ast::WherePredicate::RegionPredicate(_) => {}
                 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
                     self.visit_ty(&*eq_pred.ty);
                 }
diff --git a/src/librustc/middle/resolve_lifetime.rs b/src/librustc/middle/resolve_lifetime.rs
index c8f53df6727..be191801626 100644
--- a/src/librustc/middle/resolve_lifetime.rs
+++ b/src/librustc/middle/resolve_lifetime.rs
@@ -206,13 +206,21 @@ impl<'a, 'v> Visitor<'v> for LifetimeContext<'a> {
         }
         for predicate in generics.where_clause.predicates.iter() {
             match predicate {
-                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ ident,
+                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ ref bounded_ty,
                                                                                ref bounds,
-                                                                               span,
                                                                                .. }) => {
-                    self.visit_ident(span, ident);
+                    self.visit_ty(&**bounded_ty);
                     visit::walk_ty_param_bounds_helper(self, bounds);
                 }
+                &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
+                                                                                ref bounds,
+                                                                                .. }) => {
+
+                    self.visit_lifetime_ref(lifetime);
+                    for bound in bounds.iter() {
+                        self.visit_lifetime_ref(bound);
+                    }
+                }
                 &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{ id,
                                                                          ref path,
                                                                          ref ty,
@@ -545,9 +553,21 @@ fn early_bound_lifetime_names(generics: &ast::Generics) -> Vec<ast::Name> {
         }
         for predicate in generics.where_clause.predicates.iter() {
             match predicate {
-                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounds, ..}) => {
+                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounds,
+                                                                              ref bounded_ty,
+                                                                              ..}) => {
+                    collector.visit_ty(&**bounded_ty);
                     visit::walk_ty_param_bounds_helper(&mut collector, bounds);
                 }
+                &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
+                                                                                ref bounds,
+                                                                                ..}) => {
+                    collector.visit_lifetime_ref(lifetime);
+
+                    for bound in bounds.iter() {
+                        collector.visit_lifetime_ref(bound);
+                    }
+                }
                 &ast::WherePredicate::EqPredicate(_) => unimplemented!()
             }
         }
diff --git a/src/librustc_resolve/lib.rs b/src/librustc_resolve/lib.rs
index e1708be30d9..99f0a6cdfc3 100644
--- a/src/librustc_resolve/lib.rs
+++ b/src/librustc_resolve/lib.rs
@@ -4360,27 +4360,14 @@ impl<'a> Resolver<'a> {
         for predicate in where_clause.predicates.iter() {
             match predicate {
                 &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
-                    match self.resolve_identifier(bound_pred.ident,
-                                                  TypeNS,
-                                                  true,
-                                                  bound_pred.span) {
-                        Some((def @ DefTyParam(..), last_private)) => {
-                            self.record_def(bound_pred.id, (def, last_private));
-                        }
-                        _ => {
-                            self.resolve_error(
-                                bound_pred.span,
-                                format!("undeclared type parameter `{}`",
-                                        token::get_ident(
-                                            bound_pred.ident)).as_slice());
-                        }
-                    }
+                    self.resolve_type(&*bound_pred.bounded_ty);
 
                     for bound in bound_pred.bounds.iter() {
-                        self.resolve_type_parameter_bound(bound_pred.id, bound,
+                        self.resolve_type_parameter_bound(bound_pred.bounded_ty.id, bound,
                                                           TraitBoundingTypeParameter);
                     }
                 }
+                &ast::WherePredicate::RegionPredicate(_) => {}
                 &ast::WherePredicate::EqPredicate(ref eq_pred) => {
                     match self.resolve_path(eq_pred.id, &eq_pred.path, TypeNS, true) {
                         Some((def @ DefTyParam(..), last_private)) => {
diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs
index 4f4bebabead..175763c874e 100644
--- a/src/librustc_typeck/astconv.rs
+++ b/src/librustc_typeck/astconv.rs
@@ -1437,11 +1437,8 @@ pub fn conv_existential_bounds<'tcx, AC: AstConv<'tcx>, RS:RegionScope>(
     ast_bounds: &[ast::TyParamBound])
     -> ty::ExistentialBounds
 {
-    let ast_bound_refs: Vec<&ast::TyParamBound> =
-        ast_bounds.iter().collect();
-
     let partitioned_bounds =
-        partition_bounds(this.tcx(), span, ast_bound_refs.as_slice());
+        partition_bounds(this.tcx(), span, ast_bounds);
 
     conv_existential_bounds_from_partitioned_bounds(
         this, rscope, span, principal_trait_ref, partitioned_bounds)
@@ -1455,7 +1452,6 @@ fn conv_ty_poly_trait_ref<'tcx, AC, RS>(
     -> Ty<'tcx>
     where AC: AstConv<'tcx>, RS:RegionScope
 {
-    let ast_bounds: Vec<&ast::TyParamBound> = ast_bounds.iter().collect();
     let mut partitioned_bounds = partition_bounds(this.tcx(), span, ast_bounds[]);
 
     let main_trait_bound = match partitioned_bounds.trait_bounds.remove(0) {
@@ -1620,14 +1616,14 @@ pub struct PartitionedBounds<'a> {
 /// general trait bounds, and region bounds.
 pub fn partition_bounds<'a>(tcx: &ty::ctxt,
                             _span: Span,
-                            ast_bounds: &'a [&ast::TyParamBound])
+                            ast_bounds: &'a [ast::TyParamBound])
                             -> PartitionedBounds<'a>
 {
     let mut builtin_bounds = ty::empty_builtin_bounds();
     let mut region_bounds = Vec::new();
     let mut trait_bounds = Vec::new();
     let mut trait_def_ids = DefIdMap::new();
-    for &ast_bound in ast_bounds.iter() {
+    for ast_bound in ast_bounds.iter() {
         match *ast_bound {
             ast::TraitTyParamBound(ref b) => {
                 match ::lookup_def_tcx(tcx, b.trait_ref.path.span, b.trait_ref.ref_id) {
diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs
index 4612acb04b2..3f59b50337f 100644
--- a/src/librustc_typeck/collect.rs
+++ b/src/librustc_typeck/collect.rs
@@ -1364,8 +1364,7 @@ pub fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                 self_param_ty,
                                 bounds.as_slice(),
                                 unbound,
-                                it.span,
-                                &generics.where_clause);
+                                it.span);
 
     let substs = mk_item_substs(ccx, &ty_generics);
     let trait_def = Rc::new(ty::TraitDef {
@@ -1619,7 +1618,6 @@ fn ty_generics_for_trait<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                         subst::AssocSpace,
                         &associated_type.ty_param,
                         generics.types.len(subst::AssocSpace),
-                        &ast_generics.where_clause,
                         Some(local_def(trait_id)));
                 ccx.tcx.ty_param_defs.borrow_mut().insert(associated_type.ty_param.id,
                                                           def.clone());
@@ -1774,7 +1772,6 @@ fn ty_generics<'tcx,AC>(this: &AC,
                                                    space,
                                                    param,
                                                    i,
-                                                   where_clause,
                                                    None);
         debug!("ty_generics: def for type param: {}, {}",
                def.repr(this.tcx()),
@@ -1798,6 +1795,54 @@ fn ty_generics<'tcx,AC>(this: &AC,
     // into the predicates list. This is currently kind of non-DRY.
     create_predicates(this.tcx(), &mut result, space);
 
+    // Add the bounds not associated with a type parameter
+    for predicate in where_clause.predicates.iter() {
+        match predicate {
+            &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
+                let ty = ast_ty_to_ty(this, &ExplicitRscope, &*bound_pred.bounded_ty);
+
+                for bound in bound_pred.bounds.iter() {
+                    match bound {
+                        &ast::TyParamBound::TraitTyParamBound(ref poly_trait_ref) => {
+                            let trait_ref = astconv::instantiate_poly_trait_ref(
+                                this,
+                                &ExplicitRscope,
+                                //@jroesch: for now trait_ref, poly_trait_ref?
+                                poly_trait_ref,
+                                Some(ty),
+                                AllowEqConstraints::Allow
+                            );
+
+                            result.predicates.push(space, ty::Predicate::Trait(trait_ref));
+                        }
+
+                        &ast::TyParamBound::RegionTyParamBound(ref lifetime) => {
+                            let region = ast_region_to_region(this.tcx(), lifetime);
+                            let pred = ty::Binder(ty::OutlivesPredicate(ty, region));
+                            result.predicates.push(space, ty::Predicate::TypeOutlives(pred))
+                        }
+                    }
+                }
+            }
+
+            &ast::WherePredicate::RegionPredicate(ref region_pred) => {
+                let r1 = ast_region_to_region(this.tcx(), &region_pred.lifetime);
+                for bound in region_pred.bounds.iter() {
+                    let r2 = ast_region_to_region(this.tcx(), bound);
+                    let pred = ty::Binder(ty::OutlivesPredicate(r1, r2));
+                    result.predicates.push(space, ty::Predicate::RegionOutlives(pred))
+                }
+            }
+
+            &ast::WherePredicate::EqPredicate(ref eq_pred) => {
+                // FIXME(#20041)
+                this.tcx().sess.span_bug(eq_pred.span,
+                                         "Equality constraints are not yet \
+                                            implemented (#20041)")
+            }
+        }
+    }
+
     return result;
 
     fn create_type_parameters_for_associated_types<'tcx, AC>(
@@ -1915,7 +1960,6 @@ fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
                                              space: subst::ParamSpace,
                                              param: &ast::TyParam,
                                              index: uint,
-                                             where_clause: &ast::WhereClause,
                                              associated_with: Option<ast::DefId>)
                                              -> ty::TypeParameterDef<'tcx>
     where AC: AstConv<'tcx>
@@ -1931,8 +1975,7 @@ fn get_or_create_type_parameter_def<'tcx,AC>(this: &AC,
                                 param_ty,
                                 param.bounds.as_slice(),
                                 &param.unbound,
-                                param.span,
-                                where_clause);
+                                param.span);
     let default = match param.default {
         None => None,
         Some(ref path) => {
@@ -1977,15 +2020,13 @@ fn compute_bounds<'tcx,AC>(this: &AC,
                            param_ty: ty::ParamTy,
                            ast_bounds: &[ast::TyParamBound],
                            unbound: &Option<ast::TraitRef>,
-                           span: Span,
-                           where_clause: &ast::WhereClause)
+                           span: Span)
                            -> ty::ParamBounds<'tcx>
                            where AC: AstConv<'tcx> {
     let mut param_bounds = conv_param_bounds(this,
                                              span,
                                              param_ty,
-                                             ast_bounds,
-                                             where_clause);
+                                             ast_bounds);
 
 
     add_unsized_bound(this,
@@ -2031,16 +2072,14 @@ fn check_bounds_compatible<'tcx>(tcx: &ty::ctxt<'tcx>,
 fn conv_param_bounds<'tcx,AC>(this: &AC,
                               span: Span,
                               param_ty: ty::ParamTy,
-                              ast_bounds: &[ast::TyParamBound],
-                              where_clause: &ast::WhereClause)
+                              ast_bounds: &[ast::TyParamBound])
                               -> ty::ParamBounds<'tcx>
-                              where AC: AstConv<'tcx> {
-    let all_bounds =
-        merge_param_bounds(this.tcx(), param_ty, ast_bounds, where_clause);
+                              where AC: AstConv<'tcx>
+{
     let astconv::PartitionedBounds { builtin_bounds,
                                      trait_bounds,
                                      region_bounds } =
-        astconv::partition_bounds(this.tcx(), span, all_bounds.as_slice());
+        astconv::partition_bounds(this.tcx(), span, ast_bounds.as_slice());
     let trait_bounds: Vec<Rc<ty::PolyTraitRef>> =
         trait_bounds.into_iter()
         .map(|bound| {
@@ -2062,43 +2101,6 @@ fn conv_param_bounds<'tcx,AC>(this: &AC,
     }
 }
 
-/// Merges the bounds declared on a type parameter with those found from where clauses into a
-/// single list.
-fn merge_param_bounds<'a>(tcx: &ty::ctxt,
-                          param_ty: ty::ParamTy,
-                          ast_bounds: &'a [ast::TyParamBound],
-                          where_clause: &'a ast::WhereClause)
-                          -> Vec<&'a ast::TyParamBound> {
-    let mut result = Vec::new();
-
-    for ast_bound in ast_bounds.iter() {
-        result.push(ast_bound);
-    }
-
-    for predicate in where_clause.predicates.iter() {
-        match predicate {
-            &ast::WherePredicate::BoundPredicate(ref bound_pred) => {
-                let predicate_param_id =
-                    tcx.def_map
-                       .borrow()
-                       .get(&bound_pred.id)
-                       .expect("merge_param_bounds(): resolve didn't resolve the \
-                                type parameter identifier in a `where` clause")
-                       .def_id();
-                if param_ty.def_id != predicate_param_id {
-                    continue
-                }
-                for bound in bound_pred.bounds.iter() {
-                    result.push(bound);
-                }
-            }
-            &ast::WherePredicate::EqPredicate(_) => panic!("not implemented")
-        }
-    }
-
-    result
-}
-
 pub fn ty_of_foreign_fn_decl<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>,
                                        decl: &ast::FnDecl,
                                        def_id: ast::DefId,
diff --git a/src/librustdoc/clean/mod.rs b/src/librustdoc/clean/mod.rs
index ed923202795..3e8bf9bd4fd 100644
--- a/src/librustdoc/clean/mod.rs
+++ b/src/librustdoc/clean/mod.rs
@@ -693,7 +693,7 @@ impl Clean<Option<Lifetime>> for ty::Region {
 
 #[deriving(Clone, Encodable, Decodable, PartialEq)]
 pub struct WherePredicate {
-    pub name: String,
+    pub ty: Type,
     pub bounds: Vec<TyParamBound>
 }
 
@@ -702,11 +702,12 @@ impl Clean<WherePredicate> for ast::WherePredicate {
         match *self {
             ast::WherePredicate::BoundPredicate(ref wbp) => {
                 WherePredicate {
-                    name: wbp.ident.clean(cx),
+                    ty: wbp.bounded_ty.clean(cx),
                     bounds: wbp.bounds.clean(cx)
                 }
             }
-            ast::WherePredicate::EqPredicate(_) => {
+            // FIXME(#20048)
+            _ => {
                 unimplemented!();
             }
         }
diff --git a/src/librustdoc/html/format.rs b/src/librustdoc/html/format.rs
index 5572bcb6aa8..e01cbbc812b 100644
--- a/src/librustdoc/html/format.rs
+++ b/src/librustdoc/html/format.rs
@@ -129,7 +129,7 @@ impl<'a> fmt::Show for WhereClause<'a> {
                 try!(f.write(", ".as_bytes()));
             }
             let bounds = pred.bounds.as_slice();
-            try!(write!(f, "{}: {}", pred.name, TyParamBounds(bounds)));
+            try!(write!(f, "{}: {}", pred.ty, TyParamBounds(bounds)));
         }
         Ok(())
     }
diff --git a/src/libsyntax/ast.rs b/src/libsyntax/ast.rs
index be8f32bc4d5..440e11e385f 100644
--- a/src/libsyntax/ast.rs
+++ b/src/libsyntax/ast.rs
@@ -415,18 +415,25 @@ pub struct WhereClause {
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub enum WherePredicate {
     BoundPredicate(WhereBoundPredicate),
+    RegionPredicate(WhereRegionPredicate),
     EqPredicate(WhereEqPredicate)
 }
 
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub struct WhereBoundPredicate {
-    pub id: NodeId,
     pub span: Span,
-    pub ident: Ident,
+    pub bounded_ty: P<Ty>,
     pub bounds: OwnedSlice<TyParamBound>,
 }
 
 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
+pub struct WhereRegionPredicate {
+    pub span: Span,
+    pub lifetime: Lifetime,
+    pub bounds: Vec<Lifetime>,
+}
+
+#[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 pub struct WhereEqPredicate {
     pub id: NodeId,
     pub span: Span,
diff --git a/src/libsyntax/ext/deriving/generic/mod.rs b/src/libsyntax/ext/deriving/generic/mod.rs
index b31758e2d2a..d8de3d2db97 100644
--- a/src/libsyntax/ext/deriving/generic/mod.rs
+++ b/src/libsyntax/ext/deriving/generic/mod.rs
@@ -426,12 +426,18 @@ impl<'a> TraitDef<'a> {
             match *clause {
                 ast::WherePredicate::BoundPredicate(ref wb) => {
                     ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
-                        id: ast::DUMMY_NODE_ID,
                         span: self.span,
-                        ident: wb.ident,
+                        bounded_ty: wb.bounded_ty.clone(),
                         bounds: OwnedSlice::from_vec(wb.bounds.iter().map(|b| b.clone()).collect())
                     })
                 }
+                ast::WherePredicate::RegionPredicate(ref rb) => {
+                    ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
+                        span: self.span,
+                        lifetime: rb.lifetime,
+                        bounds: rb.bounds.iter().map(|b| b.clone()).collect()
+                    })
+                }
                 ast::WherePredicate::EqPredicate(ref we) => {
                     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
                         id: ast::DUMMY_NODE_ID,
diff --git a/src/libsyntax/fold.rs b/src/libsyntax/fold.rs
index 10860ee5e01..86df5883864 100644
--- a/src/libsyntax/fold.rs
+++ b/src/libsyntax/fold.rs
@@ -814,17 +814,24 @@ pub fn noop_fold_where_predicate<T: Folder>(
                                  fld: &mut T)
                                  -> WherePredicate {
     match pred {
-        ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{id,
-                                                                     ident,
+        ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{bounded_ty,
                                                                      bounds,
                                                                      span}) => {
             ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
-                id: fld.new_id(id),
-                ident: fld.fold_ident(ident),
+                bounded_ty: fld.fold_ty(bounded_ty),
                 bounds: bounds.move_map(|x| fld.fold_ty_param_bound(x)),
                 span: fld.new_span(span)
             })
         }
+        ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{lifetime,
+                                                                       bounds,
+                                                                       span}) => {
+            ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate {
+                span: fld.new_span(span),
+                lifetime: fld.fold_lifetime(lifetime),
+                bounds: bounds.move_map(|bound| fld.fold_lifetime(bound))
+            })
+        }
         ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{id,
                                                                path,
                                                                ty,
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index 3ad224b93ce..f8b47e0405f 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -1497,9 +1497,6 @@ impl<'a> Parser<'a> {
     }
 
     /// Parse a type.
-    ///
-    /// The second parameter specifies whether the `+` binary operator is
-    /// allowed in the type grammar.
     pub fn parse_ty(&mut self) -> P<Ty> {
         maybe_whole!(no_clone self, NtTy);
 
@@ -4179,6 +4176,10 @@ impl<'a> Parser<'a> {
     }
 
     /// Parses an optional `where` clause and places it in `generics`.
+    ///
+    /// ```
+    /// where T : Trait<U, V> + 'b, 'a : 'b
+    /// ```
     fn parse_where_clause(&mut self, generics: &mut ast::Generics) {
         if !self.eat_keyword(keywords::Where) {
             return
@@ -4187,58 +4188,79 @@ impl<'a> Parser<'a> {
         let mut parsed_something = false;
         loop {
             let lo = self.span.lo;
-            let path = match self.token {
-                token::Ident(..) => self.parse_path(NoTypesAllowed),
-                _ => break,
-            };
+            match self.token {
+                token::OpenDelim(token::Brace) => {
+                    break
+                }
 
-            if self.eat(&token::Colon) {
-                let bounds = self.parse_ty_param_bounds();
-                let hi = self.span.hi;
-                let span = mk_sp(lo, hi);
+                token::Lifetime(..) => {
+                    let bounded_lifetime =
+                        self.parse_lifetime();
 
-                if bounds.len() == 0 {
-                    self.span_err(span,
-                                  "each predicate in a `where` clause must have \
-                                   at least one bound in it");
+                    self.eat(&token::Colon);
+
+                    let bounds =
+                        self.parse_lifetimes(token::BinOp(token::Plus));
+
+                    let hi = self.span.hi;
+                    let span = mk_sp(lo, hi);
+
+                    generics.where_clause.predicates.push(ast::WherePredicate::RegionPredicate(
+                        ast::WhereRegionPredicate {
+                            span: span,
+                            lifetime: bounded_lifetime,
+                            bounds: bounds
+                        }
+                    ));
+
+                    parsed_something = true;
                 }
 
-                let ident = match ast_util::path_to_ident(&path) {
-                    Some(ident) => ident,
-                    None => {
-                        self.span_err(path.span, "expected a single identifier \
-                                                  in bound where clause");
-                        break;
-                    }
-                };
+                _ => {
+                    let bounded_ty = self.parse_ty();
 
-                generics.where_clause.predicates.push(
-                    ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate {
-                        id: ast::DUMMY_NODE_ID,
-                        span: span,
-                        ident: ident,
-                        bounds: bounds,
-                }));
-                parsed_something = true;
-            } else if self.eat(&token::Eq) {
-                let ty = self.parse_ty();
-                let hi = self.span.hi;
-                let span = mk_sp(lo, hi);
-                generics.where_clause.predicates.push(
-                    ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
-                        id: ast::DUMMY_NODE_ID,
-                        span: span,
-                        path: path,
-                        ty: ty,
-                }));
-                parsed_something = true;
-                // FIXME(#18433)
-                self.span_err(span, "equality constraints are not yet supported in where clauses");
-            } else {
-                let last_span = self.last_span;
-                self.span_err(last_span,
+                    if self.eat(&token::Colon) {
+                        let bounds = self.parse_ty_param_bounds();
+                        let hi = self.span.hi;
+                        let span = mk_sp(lo, hi);
+
+                        if bounds.len() == 0 {
+                            self.span_err(span,
+                                          "each predicate in a `where` clause must have \
+                                   at least one bound in it");
+                        }
+
+                        generics.where_clause.predicates.push(ast::WherePredicate::BoundPredicate(
+                                ast::WhereBoundPredicate {
+                                    span: span,
+                                    bounded_ty: bounded_ty,
+                                    bounds: bounds,
+                        }));
+
+                        parsed_something = true;
+                    } else if self.eat(&token::Eq) {
+                        // let ty = self.parse_ty();
+                        let hi = self.span.hi;
+                        let span = mk_sp(lo, hi);
+                        // generics.where_clause.predicates.push(
+                        //     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
+                        //         id: ast::DUMMY_NODE_ID,
+                        //         span: span,
+                        //         path: panic!("NYI"), //bounded_ty,
+                        //         ty: ty,
+                        // }));
+                        // parsed_something = true;
+                        // // FIXME(#18433)
+                        self.span_err(span,
+                                     "equality constraints are not yet supported \
+                                     in where clauses (#20041)");
+                    } else {
+                        let last_span = self.last_span;
+                        self.span_err(last_span,
                               "unexpected token in `where` clause");
-            }
+                    }
+                }
+            };
 
             if !self.eat(&token::Comma) {
                 break
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index d2cc0cba317..f27a476dbdd 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -2437,12 +2437,26 @@ impl<'a> State<'a> {
             }
 
             match predicate {
-                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ident,
+                &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounded_ty,
                                                                               ref bounds,
                                                                               ..}) => {
-                    try!(self.print_ident(ident));
+                    try!(self.print_type(&**bounded_ty));
                     try!(self.print_bounds(":", bounds.as_slice()));
                 }
+                &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
+                                                                                ref bounds,
+                                                                                ..}) => {
+                    try!(self.print_lifetime(lifetime));
+                    try!(word(&mut self.s, ":"));
+
+                    for (i, bound) in bounds.iter().enumerate() {
+                        try!(self.print_lifetime(bound));
+
+                        if i != 0 {
+                            try!(word(&mut self.s, ":"));
+                        }
+                    }
+                }
                 &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{ref path, ref ty, ..}) => {
                     try!(self.print_path(path, false));
                     try!(space(&mut self.s));
diff --git a/src/libsyntax/visit.rs b/src/libsyntax/visit.rs
index b89e9a59349..9938feb171e 100644
--- a/src/libsyntax/visit.rs
+++ b/src/libsyntax/visit.rs
@@ -583,13 +583,21 @@ pub fn walk_generics<'v, V: Visitor<'v>>(visitor: &mut V, generics: &'v Generics
     walk_lifetime_decls_helper(visitor, &generics.lifetimes);
     for predicate in generics.where_clause.predicates.iter() {
         match predicate {
-            &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{span,
-                                                                          ident,
+            &ast::WherePredicate::BoundPredicate(ast::WhereBoundPredicate{ref bounded_ty,
                                                                           ref bounds,
                                                                           ..}) => {
-                visitor.visit_ident(span, ident);
+                visitor.visit_ty(&**bounded_ty);
                 walk_ty_param_bounds_helper(visitor, bounds);
             }
+            &ast::WherePredicate::RegionPredicate(ast::WhereRegionPredicate{ref lifetime,
+                                                                            ref bounds,
+                                                                            ..}) => {
+                visitor.visit_lifetime_ref(lifetime);
+
+                for bound in bounds.iter() {
+                    visitor.visit_lifetime_ref(bound);
+                }
+            }
             &ast::WherePredicate::EqPredicate(ast::WhereEqPredicate{id,
                                                                     ref path,
                                                                     ref ty,
diff --git a/src/test/compile-fail/region-lifetime-bounds-on-fns-where-clause.rs b/src/test/compile-fail/region-lifetime-bounds-on-fns-where-clause.rs
new file mode 100644
index 00000000000..381144f2599
--- /dev/null
+++ b/src/test/compile-fail/region-lifetime-bounds-on-fns-where-clause.rs
@@ -0,0 +1,39 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn a<'a, 'b>(x: &mut &'a int, y: &mut &'b int) where 'b: 'a {
+    // Note: this is legal because of the `'b:'a` declaration.
+    *x = *y;
+}
+
+fn b<'a, 'b>(x: &mut &'a int, y: &mut &'b int) {
+    // Illegal now because there is no `'b:'a` declaration.
+    *x = *y; //~ ERROR mismatched types
+}
+
+fn c<'a,'b>(x: &mut &'a int, y: &mut &'b int) {
+    // Here we try to call `foo` but do not know that `'a` and `'b` are
+    // related as required.
+    a(x, y); //~ ERROR cannot infer
+}
+
+fn d() {
+    // 'a and 'b are early bound in the function `a` because they appear
+    // inconstraints:
+    let _: fn(&mut &int, &mut &int) = a; //~ ERROR mismatched types
+}
+
+fn e() {
+    // 'a and 'b are late bound in the function `b` because there are
+    // no constraints:
+    let _: fn(&mut &int, &mut &int) = b;
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/region-multiple-lifetime-bounds-on-fns-where-clause.rs b/src/test/compile-fail/region-multiple-lifetime-bounds-on-fns-where-clause.rs
new file mode 100644
index 00000000000..a03911e1d0e
--- /dev/null
+++ b/src/test/compile-fail/region-multiple-lifetime-bounds-on-fns-where-clause.rs
@@ -0,0 +1,41 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn a<'a, 'b, 'c>(x: &mut &'a int, y: &mut &'b int, z: &mut &'c int) where 'b: 'a + 'c {
+    // Note: this is legal because of the `'b:'a` declaration.
+    *x = *y;
+    *z = *y;
+}
+
+fn b<'a, 'b, 'c>(x: &mut &'a int, y: &mut &'b int, z: &mut &'c int) {
+    // Illegal now because there is no `'b:'a` declaration.
+    *x = *y; //~ ERROR mismatched types
+    *z = *y; //~ ERROR mismatched types
+}
+
+fn c<'a,'b, 'c>(x: &mut &'a int, y: &mut &'b int, z: &mut &'c int) {
+    // Here we try to call `foo` but do not know that `'a` and `'b` are
+    // related as required.
+    a(x, y, z); //~ ERROR cannot infer
+}
+
+fn d() {
+    // 'a and 'b are early bound in the function `a` because they appear
+    // inconstraints:
+    let _: fn(&mut &int, &mut &int, &mut &int) = a; //~ ERROR mismatched types
+}
+
+fn e() {
+    // 'a and 'b are late bound in the function `b` because there are
+    // no constraints:
+    let _: fn(&mut &int, &mut &int, &mut &int) = b;
+}
+
+fn main() { }
diff --git a/src/test/compile-fail/where-clause-constraints-are-local-for-inherent-impl.rs b/src/test/compile-fail/where-clause-constraints-are-local-for-inherent-impl.rs
new file mode 100644
index 00000000000..8d72e260a18
--- /dev/null
+++ b/src/test/compile-fail/where-clause-constraints-are-local-for-inherent-impl.rs
@@ -0,0 +1,28 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn require_copy<T: Copy>(x: T) {}
+
+struct Foo<T> { x: T }
+
+// Ensure constraints are only attached to methods locally
+impl<T> Foo<T> {
+    fn needs_copy(self) where T: Copy {
+        require_copy(self.x);
+
+    }
+
+    fn fails_copy(self) {
+        require_copy(self.x);
+        //~^ ERROR the trait `core::kinds::Copy` is not implemented for the type `T`
+    }
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/where-clause-constraints-are-local-for-trait-impl.rs b/src/test/compile-fail/where-clause-constraints-are-local-for-trait-impl.rs
new file mode 100644
index 00000000000..096b53a1ea6
--- /dev/null
+++ b/src/test/compile-fail/where-clause-constraints-are-local-for-trait-impl.rs
@@ -0,0 +1,33 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn require_copy<T: Copy>(x: T) {}
+
+struct Bar<T> { x: T }
+
+trait Foo<T> {
+    fn needs_copy(self) where T: Copy;
+    fn fails_copy(self);
+}
+
+// Ensure constraints are only attached to methods locally
+impl<T> Foo<T> for Bar<T> {
+    fn needs_copy(self) where T: Copy {
+        require_copy(self.x);
+
+    }
+
+    fn fails_copy(self) {
+        require_copy(self.x);
+        //~^ ERROR the trait `core::kinds::Copy` is not implemented for the type `T`
+    }
+}
+
+fn main() {}
diff --git a/src/test/compile-fail/where-clause-method-substituion.rs b/src/test/compile-fail/where-clause-method-substituion.rs
new file mode 100644
index 00000000000..40d2df45488
--- /dev/null
+++ b/src/test/compile-fail/where-clause-method-substituion.rs
@@ -0,0 +1,30 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+trait Foo<T> {}
+
+trait Bar<A> {
+    fn method<B>(&self) where A: Foo<B>;
+}
+
+struct S;
+struct X;
+
+// Remove this impl causing the below resolution to fail // impl Foo<S> for X {}
+
+impl Bar<X> for int {
+    fn method<U>(&self) where X: Foo<U> {
+    }
+}
+
+fn main() {
+    1.method::<X>();
+    //~^ ERROR the trait `Foo<X>` is not implemented for the type `X`
+}
diff --git a/src/test/compile-fail/where-clauses-method-unsatisfied.rs b/src/test/compile-fail/where-clauses-method-unsatisfied.rs
new file mode 100644
index 00000000000..e5b54582e4e
--- /dev/null
+++ b/src/test/compile-fail/where-clauses-method-unsatisfied.rs
@@ -0,0 +1,30 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a where clause attached to a method allows us to add
+// additional constraints to a parameter out of scope.
+
+struct Foo<T> {
+    value: T
+}
+
+struct Bar; // does not implement Eq
+
+impl<T> Foo<T> {
+    fn equals(&self, u: &Foo<T>) -> bool where T : Eq {
+        self.value == u.value
+    }
+}
+
+fn main() {
+    let x = Foo { value: Bar };
+    x.equals(&x);
+    //~^ ERROR the trait `core::cmp::Eq` is not implemented for the type `Bar`
+}
diff --git a/src/test/compile-fail/where-clauses-not-parameter.rs b/src/test/compile-fail/where-clauses-not-parameter.rs
index 2817aa16e8e..9e81703787f 100644
--- a/src/test/compile-fail/where-clauses-not-parameter.rs
+++ b/src/test/compile-fail/where-clauses-not-parameter.rs
@@ -8,10 +8,17 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-fn equal<T>(_: &T, _: &T) -> bool where int : Eq {
-    //~^ ERROR undeclared type parameter
+struct A;
+
+trait U {}
+
+// impl U for A {}
+
+fn equal<T>(_: &T, _: &T) -> bool where A : U {
+    true
 }
 
 fn main() {
+    equal(&0i, &0i);
+    //~^ ERROR the trait `U` is not implemented for the type `A`
 }
-
diff --git a/src/test/pretty/where-clauses.rs b/src/test/pretty/where-clauses.rs
new file mode 100644
index 00000000000..0f3b914334e
--- /dev/null
+++ b/src/test/pretty/where-clauses.rs
@@ -0,0 +1,16 @@
+// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// pp-exact
+
+fn f<'a, 'b, T>(t: T) -> int where T: 'a, 'a:'b, T: Eq { 0 }
+
+fn main() { }
+
diff --git a/src/test/run-pass/where-clause-early-bound-lifetimes.rs b/src/test/run-pass/where-clause-early-bound-lifetimes.rs
new file mode 100644
index 00000000000..cade99b83a2
--- /dev/null
+++ b/src/test/run-pass/where-clause-early-bound-lifetimes.rs
@@ -0,0 +1,23 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+trait TheTrait { }
+
+impl TheTrait for &'static int { }
+
+fn foo<'a,T>(_: &'a T) where &'a T : TheTrait { }
+
+fn bar<T>(_: &'static T) where &'static T : TheTrait { }
+
+fn main() {
+    static x: int = 1;
+    foo(&x);
+    bar(&x);
+}
diff --git a/src/test/run-pass/where-clause-method-substituion.rs b/src/test/run-pass/where-clause-method-substituion.rs
new file mode 100644
index 00000000000..b391df8500b
--- /dev/null
+++ b/src/test/run-pass/where-clause-method-substituion.rs
@@ -0,0 +1,30 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+trait Foo<T> {}
+
+trait Bar<A> {
+    fn method<B>(&self) where A: Foo<B>;
+}
+
+struct S;
+struct X;
+
+impl Foo<S> for X {}
+
+impl Bar<X> for int {
+    fn method<U>(&self) where X: Foo<U> {
+    }
+}
+
+fn main() {
+    1.method::<S>();
+}
+
diff --git a/src/test/run-pass/where-clause-region-outlives.rs b/src/test/run-pass/where-clause-region-outlives.rs
new file mode 100644
index 00000000000..1ecb4b6c2dc
--- /dev/null
+++ b/src/test/run-pass/where-clause-region-outlives.rs
@@ -0,0 +1,17 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+struct A<'a, 'b> where 'a : 'b { x: &'a int, y: &'b int }
+
+fn main() {
+    let x = 1i;
+    let y = 1i;
+    let a = A { x: &x, y: &y };
+}
diff --git a/src/test/run-pass/where-clauses-method.rs b/src/test/run-pass/where-clauses-method.rs
new file mode 100644
index 00000000000..2b87bcd4b39
--- /dev/null
+++ b/src/test/run-pass/where-clauses-method.rs
@@ -0,0 +1,29 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Test that a where clause attached to a method allows us to add
+// additional constraints to a parameter out of scope.
+
+struct Foo<T> {
+    value: T
+}
+
+impl<T> Foo<T> {
+    fn equals(&self, u: &Foo<T>) -> bool where T : Eq {
+        self.value == u.value
+    }
+}
+
+fn main() {
+    let x = Foo { value: 1i };
+    let y = Foo { value: 2i };
+    println!("{}", x.equals(&x));
+    println!("{}", x.equals(&y));
+}
diff --git a/src/test/run-pass/where-clauses-not-parameter.rs b/src/test/run-pass/where-clauses-not-parameter.rs
new file mode 100644
index 00000000000..bc5fc388ca1
--- /dev/null
+++ b/src/test/run-pass/where-clauses-not-parameter.rs
@@ -0,0 +1,17 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+fn equal<T>(_: &T, _: &T) -> bool where int : Eq {
+    true
+}
+
+fn main() {
+    equal(&0i, &0i);
+}