librustc: Implement simple `where` clauses.

These `where` clauses are accepted everywhere generics are currently
accepted and desugar during type collection to the type parameter bounds
we have today.

A new keyword, `where`, has been added. Therefore, this is a breaking
change. Change uses of `where` to other identifiers.

[breaking-change]

4 files changed, 107 insertions, 34 deletions

diff --git a/src/libsyntax/parse/lexer/mod.rs b/src/libsyntax/parse/lexer/mod.rs
index e5275af5cca..17249628989 100644
--- a/src/libsyntax/parse/lexer/mod.rs
+++ b/src/libsyntax/parse/lexer/mod.rs
@@ -543,7 +543,7 @@ impl<'a> StringReader<'a> {
     // favors rustc debugging effectiveness over runtime efficiency.
 
     /// Scan through input of form \x00name_NNNNNN,ctxt_CCCCCCC\x00
-    /// where: `NNNNNN` is a string of characters forming an integer
+    /// whence: `NNNNNN` is a string of characters forming an integer
     /// (the name) and `CCCCCCC` is a string of characters forming an
     /// integer (the ctxt), separate by a comma and delimited by a
     /// `\x00` marker.
@@ -552,22 +552,22 @@ impl<'a> StringReader<'a> {
         fn bump_expecting_char<'a,D:fmt::Show>(r: &mut StringReader<'a>,
                                                c: char,
                                                described_c: D,
-                                               where: &str) {
+                                               whence: &str) {
             match r.curr {
                 Some(r_c) if r_c == c => r.bump(),
-                Some(r_c) => fail!("expected {}, hit {}, {}", described_c, r_c, where),
-                None      => fail!("expected {}, hit EOF, {}", described_c, where),
+                Some(r_c) => fail!("expected {}, hit {}, {}", described_c, r_c, whence),
+                None      => fail!("expected {}, hit EOF, {}", described_c, whence),
             }
         }
 
-        let where = "while scanning embedded hygienic ident";
+        let whence = "while scanning embedded hygienic ident";
 
         // skip over the leading `\x00`
-        bump_expecting_char(self, '\x00', "nul-byte", where);
+        bump_expecting_char(self, '\x00', "nul-byte", whence);
 
         // skip over the "name_"
         for c in "name_".chars() {
-            bump_expecting_char(self, c, c, where);
+            bump_expecting_char(self, c, c, whence);
         }
 
         let start_bpos = self.last_pos;
@@ -578,16 +578,16 @@ impl<'a> StringReader<'a> {
         let encoded_name : u32 = self.with_str_from(start_bpos, |s| {
             num::from_str_radix(s, 10).unwrap_or_else(|| {
                 fail!("expected digits representing a name, got `{}`, {}, range [{},{}]",
-                      s, where, start_bpos, self.last_pos);
+                      s, whence, start_bpos, self.last_pos);
             })
         });
 
         // skip over the `,`
-        bump_expecting_char(self, ',', "comma", where);
+        bump_expecting_char(self, ',', "comma", whence);
 
         // skip over the "ctxt_"
         for c in "ctxt_".chars() {
-            bump_expecting_char(self, c, c, where);
+            bump_expecting_char(self, c, c, whence);
         }
 
         // find the integer representing the ctxt
@@ -595,12 +595,12 @@ impl<'a> StringReader<'a> {
         self.scan_digits(base);
         let encoded_ctxt : ast::SyntaxContext = self.with_str_from(start_bpos, |s| {
             num::from_str_radix(s, 10).unwrap_or_else(|| {
-                fail!("expected digits representing a ctxt, got `{}`, {}", s, where);
+                fail!("expected digits representing a ctxt, got `{}`, {}", s, whence);
             })
         });
 
         // skip over the `\x00`
-        bump_expecting_char(self, '\x00', "nul-byte", where);
+        bump_expecting_char(self, '\x00', "nul-byte", whence);
 
         ast::Ident { name: ast::Name(encoded_name),
                      ctxt: encoded_ctxt, }
diff --git a/src/libsyntax/parse/mod.rs b/src/libsyntax/parse/mod.rs
index af1f296a6ca..271cefeaf03 100644
--- a/src/libsyntax/parse/mod.rs
+++ b/src/libsyntax/parse/mod.rs
@@ -1053,6 +1053,10 @@ mod test {
                                     ast::Generics{ // no idea on either of these:
                                         lifetimes: Vec::new(),
                                         ty_params: OwnedSlice::empty(),
+                                        where_clause: ast::WhereClause {
+                                            id: ast::DUMMY_NODE_ID,
+                                            predicates: Vec::new(),
+                                        }
                                     },
                                     ast::P(ast::Block {
                                         view_items: Vec::new(),
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index f272f7e1887..577959ea36a 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -60,7 +60,7 @@ use ast::{UnboxedClosureKind, UnboxedFnTy, UnboxedFnTyParamBound};
 use ast::{UnnamedField, UnsafeBlock};
 use ast::{UnsafeFn, ViewItem, ViewItem_, ViewItemExternCrate, ViewItemUse};
 use ast::{ViewPath, ViewPathGlob, ViewPathList, ViewPathSimple};
-use ast::Visibility;
+use ast::{Visibility, WhereClause, WherePredicate};
 use ast;
 use ast_util::{as_prec, ident_to_path, lit_is_str, operator_prec};
 use ast_util;
@@ -1264,7 +1264,7 @@ impl<'a> Parser<'a> {
             let style = p.parse_fn_style();
             let ident = p.parse_ident();
 
-            let generics = p.parse_generics();
+            let mut generics = p.parse_generics();
 
             let (explicit_self, d) = p.parse_fn_decl_with_self(|p| {
                 // This is somewhat dubious; We don't want to allow argument
@@ -1272,6 +1272,8 @@ impl<'a> Parser<'a> {
                 p.parse_arg_general(false)
             });
 
+            p.parse_where_clause(&mut generics);
+
             let hi = p.last_span.hi;
             match p.token {
               token::SEMI => {
@@ -3742,7 +3744,10 @@ impl<'a> Parser<'a> {
         }
     }
 
-    /// Parse a set of optional generic type parameter declarations
+    /// Parse a set of optional generic type parameter declarations. Where
+    /// clauses are not parsed here, and must be added later via
+    /// `parse_where_clause()`.
+    ///
     /// matches generics = ( ) | ( < > ) | ( < typaramseq ( , )? > ) | ( < lifetimes ( , )? > )
     ///                  | ( < lifetimes , typaramseq ( , )? > )
     /// where   typaramseq = ( typaram ) | ( typaram , typaramseq )
@@ -3762,7 +3767,14 @@ impl<'a> Parser<'a> {
                 }
                 ty_param
             });
-            ast::Generics { lifetimes: lifetime_defs, ty_params: ty_params }
+            ast::Generics {
+                lifetimes: lifetime_defs,
+                ty_params: ty_params,
+                where_clause: WhereClause {
+                    id: ast::DUMMY_NODE_ID,
+                    predicates: Vec::new(),
+                }
+            }
         } else {
             ast_util::empty_generics()
         }
@@ -3788,6 +3800,52 @@ impl<'a> Parser<'a> {
         }
     }
 
+    /// Parses an optional `where` clause and places it in `generics`.
+    fn parse_where_clause(&mut self, generics: &mut ast::Generics) {
+        if !self.eat_keyword(keywords::Where) {
+            return
+        }
+
+        let mut parsed_something = false;
+        loop {
+            let lo = self.span.lo;
+            let ident = match self.token {
+                token::IDENT(..) => self.parse_ident(),
+                _ => break,
+            };
+            self.expect(&token::COLON);
+
+            let (_, bounds) = self.parse_ty_param_bounds(false);
+            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 {
+                id: ast::DUMMY_NODE_ID,
+                span: span,
+                ident: ident,
+                bounds: bounds,
+            });
+            parsed_something = true;
+
+            if !self.eat(&token::COMMA) {
+                break
+            }
+        }
+
+        if !parsed_something {
+            let last_span = self.last_span;
+            self.span_err(last_span,
+                          "a `where` clause must have at least one predicate \
+                           in it");
+        }
+    }
+
     fn parse_fn_args(&mut self, named_args: bool, allow_variadic: bool)
                      -> (Vec<Arg> , bool) {
         let sp = self.span;
@@ -4143,8 +4201,9 @@ impl<'a> Parser<'a> {
 
     /// Parse an item-position function declaration.
     fn parse_item_fn(&mut self, fn_style: FnStyle, abi: abi::Abi) -> ItemInfo {
-        let (ident, generics) = self.parse_fn_header();
+        let (ident, mut generics) = self.parse_fn_header();
         let decl = self.parse_fn_decl(false);
+        self.parse_where_clause(&mut generics);
         let (inner_attrs, body) = self.parse_inner_attrs_and_block();
         (ident, ItemFn(decl, fn_style, abi, generics, body), Some(inner_attrs))
     }
@@ -4200,10 +4259,11 @@ impl<'a> Parser<'a> {
                 };
                 let fn_style = self.parse_fn_style();
                 let ident = self.parse_ident();
-                let generics = self.parse_generics();
+                let mut generics = self.parse_generics();
                 let (explicit_self, decl) = self.parse_fn_decl_with_self(|p| {
                         p.parse_arg()
                     });
+                self.parse_where_clause(&mut generics);
                 let (inner_attrs, body) = self.parse_inner_attrs_and_block();
                 let new_attrs = attrs.append(inner_attrs.as_slice());
                 (ast::MethDecl(ident,
@@ -4228,7 +4288,7 @@ impl<'a> Parser<'a> {
     /// Parse trait Foo { ... }
     fn parse_item_trait(&mut self) -> ItemInfo {
         let ident = self.parse_ident();
-        let tps = self.parse_generics();
+        let mut tps = self.parse_generics();
         let sized = self.parse_for_sized();
 
         // Parse traits, if necessary.
@@ -4240,6 +4300,8 @@ impl<'a> Parser<'a> {
             traits = Vec::new();
         }
 
+        self.parse_where_clause(&mut tps);
+
         let meths = self.parse_trait_methods();
         (ident, ItemTrait(tps, sized, traits, meths), None)
     }
@@ -4261,7 +4323,7 @@ impl<'a> Parser<'a> {
     ///    impl<T> ToString for ~[T] { ... }
     fn parse_item_impl(&mut self) -> ItemInfo {
         // First, parse type parameters if necessary.
-        let generics = self.parse_generics();
+        let mut generics = self.parse_generics();
 
         // Special case: if the next identifier that follows is '(', don't
         // allow this to be parsed as a trait.
@@ -4297,6 +4359,7 @@ impl<'a> Parser<'a> {
             None
         };
 
+        self.parse_where_clause(&mut generics);
         let (impl_items, attrs) = self.parse_impl_items();
 
         let ident = ast_util::impl_pretty_name(&opt_trait, &*ty);
@@ -4326,7 +4389,7 @@ impl<'a> Parser<'a> {
     /// Parse struct Foo { ... }
     fn parse_item_struct(&mut self, is_virtual: bool) -> ItemInfo {
         let class_name = self.parse_ident();
-        let generics = self.parse_generics();
+        let mut generics = self.parse_generics();
 
         let super_struct = if self.eat(&token::COLON) {
             let ty = self.parse_ty(true);
@@ -4343,6 +4406,8 @@ impl<'a> Parser<'a> {
             None
         };
 
+        self.parse_where_clause(&mut generics);
+
         let mut fields: Vec<StructField>;
         let is_tuple_like;
 
@@ -4683,8 +4748,9 @@ impl<'a> Parser<'a> {
         let lo = self.span.lo;
         self.expect_keyword(keywords::Fn);
 
-        let (ident, generics) = self.parse_fn_header();
+        let (ident, mut generics) = self.parse_fn_header();
         let decl = self.parse_fn_decl(true);
+        self.parse_where_clause(&mut generics);
         let hi = self.span.hi;
         self.expect(&token::SEMI);
         box(GC) ast::ForeignItem { ident: ident,
@@ -4834,7 +4900,8 @@ impl<'a> Parser<'a> {
     /// Parse type Foo = Bar;
     fn parse_item_type(&mut self) -> ItemInfo {
         let ident = self.parse_ident();
-        let tps = self.parse_generics();
+        let mut tps = self.parse_generics();
+        self.parse_where_clause(&mut tps);
         self.expect(&token::EQ);
         let ty = self.parse_ty(true);
         self.expect(&token::SEMI);
@@ -4925,7 +4992,8 @@ impl<'a> Parser<'a> {
     /// Parse an "enum" declaration
     fn parse_item_enum(&mut self) -> ItemInfo {
         let id = self.parse_ident();
-        let generics = self.parse_generics();
+        let mut generics = self.parse_generics();
+        self.parse_where_clause(&mut generics);
         self.expect(&token::LBRACE);
 
         let enum_definition = self.parse_enum_def(&generics);
diff --git a/src/libsyntax/parse/token.rs b/src/libsyntax/parse/token.rs
index f1ef7980151..4c959932f41 100644
--- a/src/libsyntax/parse/token.rs
+++ b/src/libsyntax/parse/token.rs
@@ -499,18 +499,19 @@ declare_special_idents_and_keywords! {
         (41,                         Proc,       "proc");
         (42,                         Box,        "box");
         (43,                         Const,      "const");
+        (44,                         Where,      "where");
 
         'reserved:
-        (44,                         Alignof,    "alignof");
-        (45,                         Be,         "be");
-        (46,                         Offsetof,   "offsetof");
-        (47,                         Priv,       "priv");
-        (48,                         Pure,       "pure");
-        (49,                         Sizeof,     "sizeof");
-        (50,                         Typeof,     "typeof");
-        (51,                         Unsized,    "unsized");
-        (52,                         Yield,      "yield");
-        (53,                         Do,         "do");
+        (45,                         Alignof,    "alignof");
+        (46,                         Be,         "be");
+        (47,                         Offsetof,   "offsetof");
+        (48,                         Priv,       "priv");
+        (49,                         Pure,       "pure");
+        (50,                         Sizeof,     "sizeof");
+        (51,                         Typeof,     "typeof");
+        (52,                         Unsized,    "unsized");
+        (53,                         Yield,      "yield");
+        (54,                         Do,         "do");
     }
 }