src/libsyntax/parse/parser.rs

   1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 pub use self::PathParsingMode::*;
  12
  13 use abi::{self, Abi};
  14 use ast::BareFnTy;
  15 use ast::{RegionTyParamBound, TraitTyParamBound, TraitBoundModifier};
  16 use ast::Unsafety;
  17 use ast::{Mod, Arg, Arm, Attribute, BindingMode, TraitItemKind};
  18 use ast::Block;
  19 use ast::{BlockCheckMode, CaptureBy};
  20 use ast::{Constness, Crate, CrateConfig};
  21 use ast::{Decl, DeclKind, Defaultness};
  22 use ast::{EMPTY_CTXT, EnumDef, ExplicitSelf};
  23 use ast::{Expr, ExprKind, RangeLimits};
  24 use ast::{Field, FnDecl};
  25 use ast::{ForeignItem, ForeignItemKind, FunctionRetTy};
  26 use ast::{Ident, ImplItem, Item, ItemKind};
  27 use ast::{Lit, LitKind, UintTy};
  28 use ast::Local;
  29 use ast::MacStmtStyle;
  30 use ast::Mac_;
  31 use ast::{MutTy, Mutability};
  32 use ast::{Pat, PatKind};
  33 use ast::{PolyTraitRef, QSelf};
  34 use ast::{Stmt, StmtKind};
  35 use ast::{VariantData, StructField};
  36 use ast::StrStyle;
  37 use ast::SelfKind;
  38 use ast::{Delimited, SequenceRepetition, TokenTree, TraitItem, TraitRef};
  39 use ast::{Ty, TyKind, TypeBinding, TyParam, TyParamBounds};
  40 use ast::{ViewPath, ViewPathGlob, ViewPathList, ViewPathSimple};
  41 use ast::{Visibility, WhereClause};
  42 use attr::{ThinAttributes, ThinAttributesExt, AttributesExt};
  43 use ast::{BinOpKind, UnOp};
  44 use ast;
  45 use codemap::{self, Span, BytePos, Spanned, spanned, mk_sp, CodeMap};
  46 use errors::{self, DiagnosticBuilder};
  47 use ext::tt::macro_parser;
  48 use parse;
  49 use parse::classify;
  50 use parse::common::SeqSep;
  51 use parse::lexer::{Reader, TokenAndSpan};
  52 use parse::obsolete::{ParserObsoleteMethods, ObsoleteSyntax};
  53 use parse::token::{self, intern, MatchNt, SubstNt, SpecialVarNt, InternedString};
  54 use parse::token::{keywords, special_idents, SpecialMacroVar};
  55 use parse::{new_sub_parser_from_file, ParseSess};
  56 use util::parser::{AssocOp, Fixity};
  57 use print::pprust;
  58 use ptr::P;
  59 use parse::PResult;
  60
  61 use std::collections::HashSet;
  62 use std::mem;
  63 use std::path::{Path, PathBuf};
  64 use std::rc::Rc;
  65 use std::slice;
  66
  67 bitflags! {
  68     flags Restrictions: u8 {
  69         const RESTRICTION_STMT_EXPR         = 1 << 0,
  70         const RESTRICTION_NO_STRUCT_LITERAL = 1 << 1,
  71         const NO_NONINLINE_MOD  = 1 << 2,
  72         const ALLOW_MODULE_PATHS = 1 << 3,
  73     }
  74 }
  75
  76 type ItemInfo = (Ident, ItemKind, Option<Vec<Attribute> >);
  77
  78 /// How to parse a path. There are four different kinds of paths, all of which
  79 /// are parsed somewhat differently.
  80 #[derive(Copy, Clone, PartialEq)]
  81 pub enum PathParsingMode {
  82     /// A path with no type parameters; e.g. `foo::bar::Baz`
  83     NoTypesAllowed,
  84     /// Same as `NoTypesAllowed`, but may end with `::{` or `::*`, which are left unparsed
  85     ImportPrefix,
  86     /// A path with a lifetime and type parameters, with no double colons
  87     /// before the type parameters; e.g. `foo::bar<'a>::Baz<T>`
  88     LifetimeAndTypesWithoutColons,
  89     /// A path with a lifetime and type parameters with double colons before
  90     /// the type parameters; e.g. `foo::bar::<'a>::Baz::<T>`
  91     LifetimeAndTypesWithColons,
  92 }
  93
  94 /// How to parse a bound, whether to allow bound modifiers such as `?`.
  95 #[derive(Copy, Clone, PartialEq)]
  96 pub enum BoundParsingMode {
  97     Bare,
  98     Modified,
  99 }
 100
 101 #[derive(Clone, Copy, PartialEq)]
 102 pub enum SemiColonMode {
 103     Break,
 104     Ignore,
 105 }
 106
 107 /// Possibly accept an `token::Interpolated` expression (a pre-parsed expression
 108 /// dropped into the token stream, which happens while parsing the result of
 109 /// macro expansion). Placement of these is not as complex as I feared it would
 110 /// be. The important thing is to make sure that lookahead doesn't balk at
 111 /// `token::Interpolated` tokens.
 112 macro_rules! maybe_whole_expr {
 113     ($p:expr) => (
 114         {
 115             let found = match $p.token {
 116                 token::Interpolated(token::NtExpr(ref e)) => {
 117                     Some((*e).clone())
 118                 }
 119                 token::Interpolated(token::NtPath(_)) => {
 120                     // FIXME: The following avoids an issue with lexical borrowck scopes,
 121                     // but the clone is unfortunate.
 122                     let pt = match $p.token {
 123                         token::Interpolated(token::NtPath(ref pt)) => (**pt).clone(),
 124                         _ => unreachable!()
 125                     };
 126                     let span = $p.span;
 127                     Some($p.mk_expr(span.lo, span.hi, ExprKind::Path(None, pt), None))
 128                 }
 129                 token::Interpolated(token::NtBlock(_)) => {
 130                     // FIXME: The following avoids an issue with lexical borrowck scopes,
 131                     // but the clone is unfortunate.
 132                     let b = match $p.token {
 133                         token::Interpolated(token::NtBlock(ref b)) => (*b).clone(),
 134                         _ => unreachable!()
 135                     };
 136                     let span = $p.span;
 137                     Some($p.mk_expr(span.lo, span.hi, ExprKind::Block(b), None))
 138                 }
 139                 _ => None
 140             };
 141             match found {
 142                 Some(e) => {
 143                     $p.bump();
 144                     return Ok(e);
 145                 }
 146                 None => ()
 147             }
 148         }
 149     )
 150 }
 151
 152 /// As maybe_whole_expr, but for things other than expressions
 153 macro_rules! maybe_whole {
 154     ($p:expr, $constructor:ident) => (
 155         {
 156             let found = match ($p).token {
 157                 token::Interpolated(token::$constructor(_)) => {
 158                     Some(($p).bump_and_get())
 159                 }
 160                 _ => None
 161             };
 162             if let Some(token::Interpolated(token::$constructor(x))) = found {
 163                 return Ok(x.clone());
 164             }
 165         }
 166     );
 167     (no_clone $p:expr, $constructor:ident) => (
 168         {
 169             let found = match ($p).token {
 170                 token::Interpolated(token::$constructor(_)) => {
 171                     Some(($p).bump_and_get())
 172                 }
 173                 _ => None
 174             };
 175             if let Some(token::Interpolated(token::$constructor(x))) = found {
 176                 return Ok(x);
 177             }
 178         }
 179     );
 180     (no_clone_from_p $p:expr, $constructor:ident) => (
 181         {
 182             let found = match ($p).token {
 183                 token::Interpolated(token::$constructor(_)) => {
 184                     Some(($p).bump_and_get())
 185                 }
 186                 _ => None
 187             };
 188             if let Some(token::Interpolated(token::$constructor(x))) = found {
 189                 return Ok(x.unwrap());
 190             }
 191         }
 192     );
 193     (deref $p:expr, $constructor:ident) => (
 194         {
 195             let found = match ($p).token {
 196                 token::Interpolated(token::$constructor(_)) => {
 197                     Some(($p).bump_and_get())
 198                 }
 199                 _ => None
 200             };
 201             if let Some(token::Interpolated(token::$constructor(x))) = found {
 202                 return Ok((*x).clone());
 203             }
 204         }
 205     );
 206     (Some deref $p:expr, $constructor:ident) => (
 207         {
 208             let found = match ($p).token {
 209                 token::Interpolated(token::$constructor(_)) => {
 210                     Some(($p).bump_and_get())
 211                 }
 212                 _ => None
 213             };
 214             if let Some(token::Interpolated(token::$constructor(x))) = found {
 215                 return Ok(Some((*x).clone()));
 216             }
 217         }
 218     );
 219     (pair_empty $p:expr, $constructor:ident) => (
 220         {
 221             let found = match ($p).token {
 222                 token::Interpolated(token::$constructor(_)) => {
 223                     Some(($p).bump_and_get())
 224                 }
 225                 _ => None
 226             };
 227             if let Some(token::Interpolated(token::$constructor(x))) = found {
 228                 return Ok((Vec::new(), x));
 229             }
 230         }
 231     )
 232 }
 233
 234 fn maybe_append(mut lhs: Vec<Attribute>, rhs: Option<Vec<Attribute>>)
 235                 -> Vec<Attribute> {
 236     if let Some(ref attrs) = rhs {
 237         lhs.extend(attrs.iter().cloned())
 238     }
 239     lhs
 240 }
 241
 242 /* ident is handled by common.rs */
 243
 244 pub struct Parser<'a> {
 245     pub sess: &'a ParseSess,
 246     /// the current token:
 247     pub token: token::Token,
 248     /// the span of the current token:
 249     pub span: Span,
 250     /// the span of the prior token:
 251     pub last_span: Span,
 252     pub cfg: CrateConfig,
 253     /// the previous token or None (only stashed sometimes).
 254     pub last_token: Option<Box<token::Token>>,
 255     last_token_interpolated: bool,
 256     last_token_eof: bool,
 257     pub buffer: [TokenAndSpan; 4],
 258     pub buffer_start: isize,
 259     pub buffer_end: isize,
 260     pub tokens_consumed: usize,
 261     pub restrictions: Restrictions,
 262     pub quote_depth: usize, // not (yet) related to the quasiquoter
 263     pub reader: Box<Reader+'a>,
 264     pub interner: Rc<token::IdentInterner>,
 265     /// The set of seen errors about obsolete syntax. Used to suppress
 266     /// extra detail when the same error is seen twice
 267     pub obsolete_set: HashSet<ObsoleteSyntax>,
 268     /// Used to determine the path to externally loaded source files
 269     pub filename: Option<String>,
 270     pub mod_path_stack: Vec<InternedString>,
 271     /// Stack of open delimiters and their spans. Used for error message.
 272     pub open_braces: Vec<(token::DelimToken, Span)>,
 273     /// Flag if this parser "owns" the directory that it is currently parsing
 274     /// in. This will affect how nested files are looked up.
 275     pub owns_directory: bool,
 276     /// Name of the root module this parser originated from. If `None`, then the
 277     /// name is not known. This does not change while the parser is descending
 278     /// into modules, and sub-parsers have new values for this name.
 279     pub root_module_name: Option<String>,
 280     pub expected_tokens: Vec<TokenType>,
 281 }
 282
 283 #[derive(PartialEq, Eq, Clone)]
 284 pub enum TokenType {
 285     Token(token::Token),
 286     Keyword(keywords::Keyword),
 287     Operator,
 288 }
 289
 290 impl TokenType {
 291     fn to_string(&self) -> String {
 292         match *self {
 293             TokenType::Token(ref t) => format!("`{}`", Parser::token_to_string(t)),
 294             TokenType::Operator => "an operator".to_string(),
 295             TokenType::Keyword(kw) => format!("`{}`", kw.to_name()),
 296         }
 297     }
 298 }
 299
 300 fn is_plain_ident_or_underscore(t: &token::Token) -> bool {
 301     t.is_plain_ident() || *t == token::Underscore
 302 }
 303
 304 /// Information about the path to a module.
 305 pub struct ModulePath {
 306     pub name: String,
 307     pub path_exists: bool,
 308     pub result: Result<ModulePathSuccess, ModulePathError>,
 309 }
 310
 311 pub struct ModulePathSuccess {
 312     pub path: ::std::path::PathBuf,
 313     pub owns_directory: bool,
 314 }
 315
 316 pub struct ModulePathError {
 317     pub err_msg: String,
 318     pub help_msg: String,
 319 }
 320
 321 pub enum LhsExpr {
 322     NotYetParsed,
 323     AttributesParsed(ThinAttributes),
 324     AlreadyParsed(P<Expr>),
 325 }
 326
 327 impl From<Option<ThinAttributes>> for LhsExpr {
 328     fn from(o: Option<ThinAttributes>) -> Self {
 329         if let Some(attrs) = o {
 330             LhsExpr::AttributesParsed(attrs)
 331         } else {
 332             LhsExpr::NotYetParsed
 333         }
 334     }
 335 }
 336
 337 impl From<P<Expr>> for LhsExpr {
 338     fn from(expr: P<Expr>) -> Self {
 339         LhsExpr::AlreadyParsed(expr)
 340     }
 341 }
 342
 343 impl<'a> Parser<'a> {
 344     pub fn new(sess: &'a ParseSess,
 345                cfg: ast::CrateConfig,
 346                mut rdr: Box<Reader+'a>)
 347                -> Parser<'a>
 348     {
 349         let tok0 = rdr.real_token();
 350         let span = tok0.sp;
 351         let filename = if span != codemap::DUMMY_SP {
 352             Some(sess.codemap().span_to_filename(span))
 353         } else { None };
 354         let placeholder = TokenAndSpan {
 355             tok: token::Underscore,
 356             sp: span,
 357         };
 358
 359         Parser {
 360             reader: rdr,
 361             interner: token::get_ident_interner(),
 362             sess: sess,
 363             cfg: cfg,
 364             token: tok0.tok,
 365             span: span,
 366             last_span: span,
 367             last_token: None,
 368             last_token_interpolated: false,
 369             last_token_eof: false,
 370             buffer: [
 371                 placeholder.clone(),
 372                 placeholder.clone(),
 373                 placeholder.clone(),
 374                 placeholder.clone(),
 375             ],
 376             buffer_start: 0,
 377             buffer_end: 0,
 378             tokens_consumed: 0,
 379             restrictions: Restrictions::empty(),
 380             quote_depth: 0,
 381             obsolete_set: HashSet::new(),
 382             mod_path_stack: Vec::new(),
 383             filename: filename,
 384             open_braces: Vec::new(),
 385             owns_directory: true,
 386             root_module_name: None,
 387             expected_tokens: Vec::new(),
 388         }
 389     }
 390
 391     /// Convert a token to a string using self's reader
 392     pub fn token_to_string(token: &token::Token) -> String {
 393         pprust::token_to_string(token)
 394     }
 395
 396     /// Convert the current token to a string using self's reader
 397     pub fn this_token_to_string(&self) -> String {
 398         Parser::token_to_string(&self.token)
 399     }
 400
 401     pub fn unexpected_last<T>(&self, t: &token::Token) -> PResult<'a, T> {
 402         let token_str = Parser::token_to_string(t);
 403         let last_span = self.last_span;
 404         Err(self.span_fatal(last_span, &format!("unexpected token: `{}`", token_str)))
 405     }
 406
 407     pub fn unexpected<T>(&mut self) -> PResult<'a, T> {
 408         match self.expect_one_of(&[], &[]) {
 409             Err(e) => Err(e),
 410             Ok(_) => unreachable!(),
 411         }
 412     }
 413
 414     /// Expect and consume the token t. Signal an error if
 415     /// the next token is not t.
 416     pub fn expect(&mut self, t: &token::Token) -> PResult<'a,  ()> {
 417         if self.expected_tokens.is_empty() {
 418             if self.token == *t {
 419                 self.bump();
 420                 Ok(())
 421             } else {
 422                 let token_str = Parser::token_to_string(t);
 423                 let this_token_str = self.this_token_to_string();
 424                 Err(self.fatal(&format!("expected `{}`, found `{}`",
 425                                    token_str,
 426                                    this_token_str)))
 427             }
 428         } else {
 429             self.expect_one_of(unsafe { slice::from_raw_parts(t, 1) }, &[])
 430         }
 431     }
 432
 433     /// Expect next token to be edible or inedible token.  If edible,
 434     /// then consume it; if inedible, then return without consuming
 435     /// anything.  Signal a fatal error if next token is unexpected.
 436     pub fn expect_one_of(&mut self,
 437                          edible: &[token::Token],
 438                          inedible: &[token::Token]) -> PResult<'a,  ()>{
 439         fn tokens_to_string(tokens: &[TokenType]) -> String {
 440             let mut i = tokens.iter();
 441             // This might be a sign we need a connect method on Iterator.
 442             let b = i.next()
 443                      .map_or("".to_string(), |t| t.to_string());
 444             i.enumerate().fold(b, |mut b, (i, ref a)| {
 445                 if tokens.len() > 2 && i == tokens.len() - 2 {
 446                     b.push_str(", or ");
 447                 } else if tokens.len() == 2 && i == tokens.len() - 2 {
 448                     b.push_str(" or ");
 449                 } else {
 450                     b.push_str(", ");
 451                 }
 452                 b.push_str(&a.to_string());
 453                 b
 454             })
 455         }
 456         if edible.contains(&self.token) {
 457             self.bump();
 458             Ok(())
 459         } else if inedible.contains(&self.token) {
 460             // leave it in the input
 461             Ok(())
 462         } else {
 463             let mut expected = edible.iter()
 464                 .map(|x| TokenType::Token(x.clone()))
 465                 .chain(inedible.iter().map(|x| TokenType::Token(x.clone())))
 466                 .chain(self.expected_tokens.iter().cloned())
 467                 .collect::<Vec<_>>();
 468             expected.sort_by(|a, b| a.to_string().cmp(&b.to_string()));
 469             expected.dedup();
 470             let expect = tokens_to_string(&expected[..]);
 471             let actual = self.this_token_to_string();
 472             Err(self.fatal(
 473                 &(if expected.len() > 1 {
 474                     (format!("expected one of {}, found `{}`",
 475                              expect,
 476                              actual))
 477                 } else if expected.is_empty() {
 478                     (format!("unexpected token: `{}`",
 479                              actual))
 480                 } else {
 481                     (format!("expected {}, found `{}`",
 482                              expect,
 483                              actual))
 484                 })[..]
 485             ))
 486         }
 487     }
 488
 489     /// Check for erroneous `ident { }`; if matches, signal error and
 490     /// recover (without consuming any expected input token).  Returns
 491     /// true if and only if input was consumed for recovery.
 492     pub fn check_for_erroneous_unit_struct_expecting(&mut self,
 493                                                      expected: &[token::Token])
 494                                                      -> bool {
 495         if self.token == token::OpenDelim(token::Brace)
 496             && expected.iter().all(|t| *t != token::OpenDelim(token::Brace))
 497             && self.look_ahead(1, |t| *t == token::CloseDelim(token::Brace)) {
 498             // matched; signal non-fatal error and recover.
 499             let span = self.span;
 500             self.span_err(span, "unit-like struct construction is written with no trailing `{ }`");
 501             self.eat(&token::OpenDelim(token::Brace));
 502             self.eat(&token::CloseDelim(token::Brace));
 503             true
 504         } else {
 505             false
 506         }
 507     }
 508
 509     /// Commit to parsing a complete expression `e` expected to be
 510     /// followed by some token from the set edible + inedible.  Recover
 511     /// from anticipated input errors, discarding erroneous characters.
 512     pub fn commit_expr(&mut self, e: &Expr, edible: &[token::Token],
 513                        inedible: &[token::Token]) -> PResult<'a, ()> {
 514         debug!("commit_expr {:?}", e);
 515         if let ExprKind::Path(..) = e.node {
 516             // might be unit-struct construction; check for recoverableinput error.
 517             let expected = edible.iter()
 518                 .cloned()
 519                 .chain(inedible.iter().cloned())
 520                 .collect::<Vec<_>>();
 521             self.check_for_erroneous_unit_struct_expecting(&expected[..]);
 522         }
 523         self.expect_one_of(edible, inedible)
 524     }
 525
 526     pub fn commit_expr_expecting(&mut self, e: &Expr, edible: token::Token) -> PResult<'a, ()> {
 527         self.commit_expr(e, &[edible], &[])
 528     }
 529
 530     /// Commit to parsing a complete statement `s`, which expects to be
 531     /// followed by some token from the set edible + inedible.  Check
 532     /// for recoverable input errors, discarding erroneous characters.
 533     pub fn commit_stmt(&mut self, edible: &[token::Token],
 534                        inedible: &[token::Token]) -> PResult<'a, ()> {
 535         if self.last_token
 536                .as_ref()
 537                .map_or(false, |t| t.is_ident() || t.is_path()) {
 538             let expected = edible.iter()
 539                 .cloned()
 540                 .chain(inedible.iter().cloned())
 541                 .collect::<Vec<_>>();
 542             self.check_for_erroneous_unit_struct_expecting(&expected);
 543         }
 544         self.expect_one_of(edible, inedible)
 545     }
 546
 547     pub fn commit_stmt_expecting(&mut self, edible: token::Token) -> PResult<'a, ()> {
 548         self.commit_stmt(&[edible], &[])
 549     }
 550
 551     /// returns the span of expr, if it was not interpolated or the span of the interpolated token
 552     fn interpolated_or_expr_span(&self,
 553                                  expr: PResult<'a, P<Expr>>)
 554                                  -> PResult<'a, (Span, P<Expr>)> {
 555         expr.map(|e| {
 556             if self.last_token_interpolated {
 557                 (self.last_span, e)
 558             } else {
 559                 (e.span, e)
 560             }
 561         })
 562     }
 563
 564     pub fn parse_ident(&mut self) -> PResult<'a, ast::Ident> {
 565         if !self.restrictions.contains(Restrictions::ALLOW_MODULE_PATHS) {
 566             self.check_strict_keywords();
 567         }
 568         self.check_reserved_keywords();
 569         match self.token {
 570             token::Ident(i, _) => {
 571                 self.bump();
 572                 Ok(i)
 573             }
 574             token::Interpolated(token::NtIdent(..)) => {
 575                 self.bug("ident interpolation not converted to real token");
 576             }
 577             _ => {
 578                 let mut err = self.fatal(&format!("expected identifier, found `{}`",
 579                                                   self.this_token_to_string()));
 580                 if self.token == token::Underscore {
 581                     err.fileline_note(self.span, "`_` is a wildcard pattern, not an identifier");
 582                 }
 583                 Err(err)
 584             }
 585         }
 586     }
 587
 588     pub fn parse_ident_or_self_type(&mut self) -> PResult<'a, ast::Ident> {
 589         if self.is_self_type_ident() {
 590             self.expect_self_type_ident()
 591         } else {
 592             self.parse_ident()
 593         }
 594     }
 595
 596     /// Check if the next token is `tok`, and return `true` if so.
 597     ///
 598     /// This method will automatically add `tok` to `expected_tokens` if `tok` is not
 599     /// encountered.
 600     pub fn check(&mut self, tok: &token::Token) -> bool {
 601         let is_present = self.token == *tok;
 602         if !is_present { self.expected_tokens.push(TokenType::Token(tok.clone())); }
 603         is_present
 604     }
 605
 606     /// Consume token 'tok' if it exists. Returns true if the given
 607     /// token was present, false otherwise.
 608     pub fn eat(&mut self, tok: &token::Token) -> bool {
 609         let is_present = self.check(tok);
 610         if is_present { self.bump() }
 611         is_present
 612     }
 613
 614     pub fn check_keyword(&mut self, kw: keywords::Keyword) -> bool {
 615         self.expected_tokens.push(TokenType::Keyword(kw));
 616         self.token.is_keyword(kw)
 617     }
 618
 619     /// If the next token is the given keyword, eat it and return
 620     /// true. Otherwise, return false.
 621     pub fn eat_keyword(&mut self, kw: keywords::Keyword) -> bool {
 622         if self.check_keyword(kw) {
 623             self.bump();
 624             true
 625         } else {
 626             false
 627         }
 628     }
 629
 630     pub fn eat_keyword_noexpect(&mut self, kw: keywords::Keyword) -> bool {
 631         if self.token.is_keyword(kw) {
 632             self.bump();
 633             true
 634         } else {
 635             false
 636         }
 637     }
 638
 639     pub fn check_contextual_keyword(&mut self, ident: Ident) -> bool {
 640         let tok = token::Ident(ident, token::Plain);
 641         self.expected_tokens.push(TokenType::Token(tok));
 642         if let token::Ident(ref cur_ident, _) = self.token {
 643             cur_ident.name == ident.name
 644         } else {
 645             false
 646         }
 647     }
 648
 649     pub fn eat_contextual_keyword(&mut self, ident: Ident) -> bool {
 650         if self.check_contextual_keyword(ident) {
 651             self.bump();
 652             true
 653         } else {
 654             false
 655         }
 656     }
 657
 658     /// If the given word is not a keyword, signal an error.
 659     /// If the next token is not the given word, signal an error.
 660     /// Otherwise, eat it.
 661     pub fn expect_keyword(&mut self, kw: keywords::Keyword) -> PResult<'a, ()> {
 662         if !self.eat_keyword(kw) {
 663             self.unexpected()
 664         } else {
 665             Ok(())
 666         }
 667     }
 668
 669     /// Signal an error if the given string is a strict keyword
 670     pub fn check_strict_keywords(&mut self) {
 671         if self.token.is_strict_keyword() {
 672             let token_str = self.this_token_to_string();
 673             let span = self.span;
 674             self.span_err(span,
 675                           &format!("expected identifier, found keyword `{}`",
 676                                   token_str));
 677         }
 678     }
 679
 680     /// Signal an error if the current token is a reserved keyword
 681     pub fn check_reserved_keywords(&mut self) {
 682         if self.token.is_reserved_keyword() {
 683             let token_str = self.this_token_to_string();
 684             self.fatal(&format!("`{}` is a reserved keyword", token_str)).emit()
 685         }
 686     }
 687
 688     /// Expect and consume an `&`. If `&&` is seen, replace it with a single
 689     /// `&` and continue. If an `&` is not seen, signal an error.
 690     fn expect_and(&mut self) -> PResult<'a, ()> {
 691         self.expected_tokens.push(TokenType::Token(token::BinOp(token::And)));
 692         match self.token {
 693             token::BinOp(token::And) => {
 694                 self.bump();
 695                 Ok(())
 696             }
 697             token::AndAnd => {
 698                 let span = self.span;
 699                 let lo = span.lo + BytePos(1);
 700                 Ok(self.bump_with(token::BinOp(token::And), lo, span.hi))
 701             }
 702             _ => self.unexpected()
 703         }
 704     }
 705
 706     pub fn expect_no_suffix(&self, sp: Span, kind: &str, suffix: Option<ast::Name>) {
 707         match suffix {
 708             None => {/* everything ok */}
 709             Some(suf) => {
 710                 let text = suf.as_str();
 711                 if text.is_empty() {
 712                     self.span_bug(sp, "found empty literal suffix in Some")
 713                 }
 714                 self.span_err(sp, &format!("{} with a suffix is invalid", kind));
 715             }
 716         }
 717     }
 718
 719     /// Attempt to consume a `<`. If `<<` is seen, replace it with a single
 720     /// `<` and continue. If a `<` is not seen, return false.
 721     ///
 722     /// This is meant to be used when parsing generics on a path to get the
 723     /// starting token.
 724     fn eat_lt(&mut self) -> bool {
 725         self.expected_tokens.push(TokenType::Token(token::Lt));
 726         match self.token {
 727             token::Lt => {
 728                 self.bump();
 729                 true
 730             }
 731             token::BinOp(token::Shl) => {
 732                 let span = self.span;
 733                 let lo = span.lo + BytePos(1);
 734                 self.bump_with(token::Lt, lo, span.hi);
 735                 true
 736             }
 737             _ => false,
 738         }
 739     }
 740
 741     fn expect_lt(&mut self) -> PResult<'a, ()> {
 742         if !self.eat_lt() {
 743             self.unexpected()
 744         } else {
 745             Ok(())
 746         }
 747     }
 748
 749     /// Expect and consume a GT. if a >> is seen, replace it
 750     /// with a single > and continue. If a GT is not seen,
 751     /// signal an error.
 752     pub fn expect_gt(&mut self) -> PResult<'a, ()> {
 753         self.expected_tokens.push(TokenType::Token(token::Gt));
 754         match self.token {
 755             token::Gt => {
 756                 self.bump();
 757                 Ok(())
 758             }
 759             token::BinOp(token::Shr) => {
 760                 let span = self.span;
 761                 let lo = span.lo + BytePos(1);
 762                 Ok(self.bump_with(token::Gt, lo, span.hi))
 763             }
 764             token::BinOpEq(token::Shr) => {
 765                 let span = self.span;
 766                 let lo = span.lo + BytePos(1);
 767                 Ok(self.bump_with(token::Ge, lo, span.hi))
 768             }
 769             token::Ge => {
 770                 let span = self.span;
 771                 let lo = span.lo + BytePos(1);
 772                 Ok(self.bump_with(token::Eq, lo, span.hi))
 773             }
 774             _ => {
 775                 let gt_str = Parser::token_to_string(&token::Gt);
 776                 let this_token_str = self.this_token_to_string();
 777                 Err(self.fatal(&format!("expected `{}`, found `{}`",
 778                                    gt_str,
 779                                    this_token_str)))
 780             }
 781         }
 782     }
 783
 784     pub fn parse_seq_to_before_gt_or_return<T, F>(&mut self,
 785                                                   sep: Option<token::Token>,
 786                                                   mut f: F)
 787                                                   -> PResult<'a, (P<[T]>, bool)>
 788         where F: FnMut(&mut Parser<'a>) -> PResult<'a, Option<T>>,
 789     {
 790         let mut v = Vec::new();
 791         // This loop works by alternating back and forth between parsing types
 792         // and commas.  For example, given a string `A, B,>`, the parser would
 793         // first parse `A`, then a comma, then `B`, then a comma. After that it
 794         // would encounter a `>` and stop. This lets the parser handle trailing
 795         // commas in generic parameters, because it can stop either after
 796         // parsing a type or after parsing a comma.
 797         for i in 0.. {
 798             if self.check(&token::Gt)
 799                 || self.token == token::BinOp(token::Shr)
 800                 || self.token == token::Ge
 801                 || self.token == token::BinOpEq(token::Shr) {
 802                 break;
 803             }
 804
 805             if i % 2 == 0 {
 806                 match f(self)? {
 807                     Some(result) => v.push(result),
 808                     None => return Ok((P::from_vec(v), true))
 809                 }
 810             } else {
 811                 if let Some(t) = sep.as_ref() {
 812                     self.expect(t)?;
 813                 }
 814
 815             }
 816         }
 817         return Ok((P::from_vec(v), false));
 818     }
 819
 820     /// Parse a sequence bracketed by '<' and '>', stopping
 821     /// before the '>'.
 822     pub fn parse_seq_to_before_gt<T, F>(&mut self,
 823                                         sep: Option<token::Token>,
 824                                         mut f: F)
 825                                         -> PResult<'a, P<[T]>> where
 826         F: FnMut(&mut Parser<'a>) -> PResult<'a, T>,
 827     {
 828         let (result, returned) = self.parse_seq_to_before_gt_or_return(sep,
 829                                                                        |p| Ok(Some(f(p)?)))?;
 830         assert!(!returned);
 831         return Ok(result);
 832     }
 833
 834     pub fn parse_seq_to_gt<T, F>(&mut self,
 835                                  sep: Option<token::Token>,
 836                                  f: F)
 837                                  -> PResult<'a, P<[T]>> where
 838         F: FnMut(&mut Parser<'a>) -> PResult<'a, T>,
 839     {
 840         let v = self.parse_seq_to_before_gt(sep, f)?;
 841         self.expect_gt()?;
 842         return Ok(v);
 843     }
 844
 845     pub fn parse_seq_to_gt_or_return<T, F>(&mut self,
 846                                            sep: Option<token::Token>,
 847                                            f: F)
 848                                            -> PResult<'a, (P<[T]>, bool)> where
 849         F: FnMut(&mut Parser<'a>) -> PResult<'a, Option<T>>,
 850     {
 851         let (v, returned) = self.parse_seq_to_before_gt_or_return(sep, f)?;
 852         if !returned {
 853             self.expect_gt()?;
 854         }
 855         return Ok((v, returned));
 856     }
 857
 858     /// Eat and discard tokens until one of `kets` is encountered. Respects token trees,
 859     /// passes through any errors encountered. Used for error recovery.
 860     pub fn eat_to_tokens(&mut self, kets: &[&token::Token]) {
 861         self.parse_seq_to_before_tokens(kets,
 862                                         SeqSep::none(),
 863                                         |p| p.parse_token_tree(),
 864                                         |mut e| e.cancel());
 865     }
 866
 867     /// Parse a sequence, including the closing delimiter. The function
 868     /// f must consume tokens until reaching the next separator or
 869     /// closing bracket.
 870     pub fn parse_seq_to_end<T, F>(&mut self,
 871                                   ket: &token::Token,
 872                                   sep: SeqSep,
 873                                   f: F)
 874                                   -> PResult<'a, Vec<T>> where
 875         F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>,
 876     {
 877         let val = self.parse_seq_to_before_end(ket, sep, f);
 878         self.bump();
 879         Ok(val)
 880     }
 881
 882     /// Parse a sequence, not including the closing delimiter. The function
 883     /// f must consume tokens until reaching the next separator or
 884     /// closing bracket.
 885     pub fn parse_seq_to_before_end<T, F>(&mut self,
 886                                          ket: &token::Token,
 887                                          sep: SeqSep,
 888                                          f: F)
 889                                          -> Vec<T>
 890         where F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>
 891     {
 892         self.parse_seq_to_before_tokens(&[ket], sep, f, |mut e| e.emit())
 893     }
 894
 895     // `fe` is an error handler.
 896     fn parse_seq_to_before_tokens<T, F, Fe>(&mut self,
 897                                             kets: &[&token::Token],
 898                                             sep: SeqSep,
 899                                             mut f: F,
 900                                             mut fe: Fe)
 901                                             -> Vec<T>
 902         where F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>,
 903               Fe: FnMut(DiagnosticBuilder)
 904     {
 905         let mut first: bool = true;
 906         let mut v = vec!();
 907         while !kets.contains(&&self.token) {
 908             match sep.sep {
 909                 Some(ref t) => {
 910                     if first {
 911                         first = false;
 912                     } else {
 913                         if let Err(e) = self.expect(t) {
 914                             fe(e);
 915                             break;
 916                         }
 917                     }
 918                 }
 919                 _ => ()
 920             }
 921             if sep.trailing_sep_allowed && kets.iter().any(|k| self.check(k)) {
 922                 break;
 923             }
 924
 925             match f(self) {
 926                 Ok(t) => v.push(t),
 927                 Err(e) => {
 928                     fe(e);
 929                     break;
 930                 }
 931             }
 932         }
 933
 934         v
 935     }
 936
 937     /// Parse a sequence, including the closing delimiter. The function
 938     /// f must consume tokens until reaching the next separator or
 939     /// closing bracket.
 940     pub fn parse_unspanned_seq<T, F>(&mut self,
 941                                      bra: &token::Token,
 942                                      ket: &token::Token,
 943                                      sep: SeqSep,
 944                                      f: F)
 945                                      -> PResult<'a, Vec<T>> where
 946         F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>,
 947     {
 948         self.expect(bra)?;
 949         let result = self.parse_seq_to_before_end(ket, sep, f);
 950         if self.token == *ket {
 951             self.bump();
 952         }
 953         Ok(result)
 954     }
 955
 956     /// Parse a sequence parameter of enum variant. For consistency purposes,
 957     /// these should not be empty.
 958     pub fn parse_enum_variant_seq<T, F>(&mut self,
 959                                         bra: &token::Token,
 960                                         ket: &token::Token,
 961                                         sep: SeqSep,
 962                                         f: F)
 963                                         -> PResult<'a, Vec<T>> where
 964         F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>,
 965     {
 966         let result = self.parse_unspanned_seq(bra, ket, sep, f)?;
 967         if result.is_empty() {
 968             let last_span = self.last_span;
 969             self.span_err(last_span,
 970             "nullary enum variants are written with no trailing `( )`");
 971         }
 972         Ok(result)
 973     }
 974
 975     // NB: Do not use this function unless you actually plan to place the
 976     // spanned list in the AST.
 977     pub fn parse_seq<T, F>(&mut self,
 978                            bra: &token::Token,
 979                            ket: &token::Token,
 980                            sep: SeqSep,
 981                            f: F)
 982                            -> PResult<'a, Spanned<Vec<T>>> where
 983         F: FnMut(&mut Parser<'a>) -> PResult<'a,  T>,
 984     {
 985         let lo = self.span.lo;
 986         self.expect(bra)?;
 987         let result = self.parse_seq_to_before_end(ket, sep, f);
 988         let hi = self.span.hi;
 989         self.bump();
 990         Ok(spanned(lo, hi, result))
 991     }
 992
 993     /// Advance the parser by one token
 994     pub fn bump(&mut self) {
 995         if self.last_token_eof {
 996             // Bumping after EOF is a bad sign, usually an infinite loop.
 997             self.bug("attempted to bump the parser past EOF (may be stuck in a loop)");
 998         }
 999
1000         if self.token == token::Eof {
1001             self.last_token_eof = true;
1002         }
1003
1004         self.last_span = self.span;
1005         // Stash token for error recovery (sometimes; clone is not necessarily cheap).
1006         self.last_token = if self.token.is_ident() ||
1007                           self.token.is_path() ||
1008                           self.token == token::Comma {
1009             Some(Box::new(self.token.clone()))
1010         } else {
1011             None
1012         };
1013         self.last_token_interpolated = self.token.is_interpolated();
1014         let next = if self.buffer_start == self.buffer_end {
1015             self.reader.real_token()
1016         } else {
1017             // Avoid token copies with `replace`.
1018             let buffer_start = self.buffer_start as usize;
1019             let next_index = (buffer_start + 1) & 3;
1020             self.buffer_start = next_index as isize;
1021
1022             let placeholder = TokenAndSpan {
1023                 tok: token::Underscore,
1024                 sp: self.span,
1025             };
1026             mem::replace(&mut self.buffer[buffer_start], placeholder)
1027         };
1028         self.span = next.sp;
1029         self.token = next.tok;
1030         self.tokens_consumed += 1;
1031         self.expected_tokens.clear();
1032         // check after each token
1033         self.check_unknown_macro_variable();
1034     }
1035
1036     /// Advance the parser by one token and return the bumped token.
1037     pub fn bump_and_get(&mut self) -> token::Token {
1038         let old_token = mem::replace(&mut self.token, token::Underscore);
1039         self.bump();
1040         old_token
1041     }
1042
1043     /// Advance the parser using provided token as a next one. Use this when
1044     /// consuming a part of a token. For example a single `<` from `<<`.
1045     pub fn bump_with(&mut self,
1046                      next: token::Token,
1047                      lo: BytePos,
1048                      hi: BytePos) {
1049         self.last_span = mk_sp(self.span.lo, lo);
1050         // It would be incorrect to just stash current token, but fortunately
1051         // for tokens currently using `bump_with`, last_token will be of no
1052         // use anyway.
1053         self.last_token = None;
1054         self.last_token_interpolated = false;
1055         self.span = mk_sp(lo, hi);
1056         self.token = next;
1057         self.expected_tokens.clear();
1058     }
1059
1060     pub fn buffer_length(&mut self) -> isize {
1061         if self.buffer_start <= self.buffer_end {
1062             return self.buffer_end - self.buffer_start;
1063         }
1064         return (4 - self.buffer_start) + self.buffer_end;
1065     }
1066     pub fn look_ahead<R, F>(&mut self, distance: usize, f: F) -> R where
1067         F: FnOnce(&token::Token) -> R,
1068     {
1069         let dist = distance as isize;
1070         while self.buffer_length() < dist {
1071             self.buffer[self.buffer_end as usize] = self.reader.real_token();
1072             self.buffer_end = (self.buffer_end + 1) & 3;
1073         }
1074         f(&self.buffer[((self.buffer_start + dist - 1) & 3) as usize].tok)
1075     }
1076     pub fn fatal(&self, m: &str) -> DiagnosticBuilder<'a> {
1077         self.sess.span_diagnostic.struct_span_fatal(self.span, m)
1078     }
1079     pub fn span_fatal(&self, sp: Span, m: &str) -> DiagnosticBuilder<'a> {
1080         self.sess.span_diagnostic.struct_span_fatal(sp, m)
1081     }
1082     pub fn span_fatal_help(&self, sp: Span, m: &str, help: &str) -> DiagnosticBuilder<'a> {
1083         let mut err = self.sess.span_diagnostic.struct_span_fatal(sp, m);
1084         err.fileline_help(sp, help);
1085         err
1086     }
1087     pub fn bug(&self, m: &str) -> ! {
1088         self.sess.span_diagnostic.span_bug(self.span, m)
1089     }
1090     pub fn warn(&self, m: &str) {
1091         self.sess.span_diagnostic.span_warn(self.span, m)
1092     }
1093     pub fn span_warn(&self, sp: Span, m: &str) {
1094         self.sess.span_diagnostic.span_warn(sp, m)
1095     }
1096     pub fn span_err(&self, sp: Span, m: &str) {
1097         self.sess.span_diagnostic.span_err(sp, m)
1098     }
1099     pub fn span_bug(&self, sp: Span, m: &str) -> ! {
1100         self.sess.span_diagnostic.span_bug(sp, m)
1101     }
1102     pub fn abort_if_errors(&self) {
1103         self.sess.span_diagnostic.abort_if_errors();
1104     }
1105
1106     pub fn diagnostic(&self) -> &'a errors::Handler {
1107         &self.sess.span_diagnostic
1108     }
1109
1110     pub fn id_to_interned_str(&mut self, id: Ident) -> InternedString {
1111         id.name.as_str()
1112     }
1113
1114     /// Is the current token one of the keywords that signals a bare function
1115     /// type?
1116     pub fn token_is_bare_fn_keyword(&mut self) -> bool {
1117         self.check_keyword(keywords::Fn) ||
1118             self.check_keyword(keywords::Unsafe) ||
1119             self.check_keyword(keywords::Extern)
1120     }
1121
1122     pub fn get_lifetime(&mut self) -> ast::Ident {
1123         match self.token {
1124             token::Lifetime(ref ident) => *ident,
1125             _ => self.bug("not a lifetime"),
1126         }
1127     }
1128
1129     pub fn parse_for_in_type(&mut self) -> PResult<'a, TyKind> {
1130         /*
1131         Parses whatever can come after a `for` keyword in a type.
1132         The `for` has already been consumed.
1133
1134         Deprecated:
1135
1136         - for <'lt> |S| -> T
1137
1138         Eventually:
1139
1140         - for <'lt> [unsafe] [extern "ABI"] fn (S) -> T
1141         - for <'lt> path::foo(a, b)
1142
1143         */
1144
1145         // parse <'lt>
1146         let lo = self.span.lo;
1147
1148         let lifetime_defs = self.parse_late_bound_lifetime_defs()?;
1149
1150         // examine next token to decide to do
1151         if self.token_is_bare_fn_keyword() {
1152             self.parse_ty_bare_fn(lifetime_defs)
1153         } else {
1154             let hi = self.span.hi;
1155             let trait_ref = self.parse_trait_ref()?;
1156             let poly_trait_ref = ast::PolyTraitRef { bound_lifetimes: lifetime_defs,
1157                                                      trait_ref: trait_ref,
1158                                                      span: mk_sp(lo, hi)};
1159             let other_bounds = if self.eat(&token::BinOp(token::Plus)) {
1160                 self.parse_ty_param_bounds(BoundParsingMode::Bare)?
1161             } else {
1162                 P::empty()
1163             };
1164             let all_bounds =
1165                 Some(TraitTyParamBound(poly_trait_ref, TraitBoundModifier::None)).into_iter()
1166                 .chain(other_bounds.into_vec())
1167                 .collect();
1168             Ok(ast::TyKind::PolyTraitRef(all_bounds))
1169         }
1170     }
1171
1172     pub fn parse_ty_path(&mut self) -> PResult<'a, TyKind> {
1173         Ok(TyKind::Path(None, self.parse_path(LifetimeAndTypesWithoutColons)?))
1174     }
1175
1176     /// parse a TyKind::BareFn type:
1177     pub fn parse_ty_bare_fn(&mut self, lifetime_defs: Vec<ast::LifetimeDef>)
1178                             -> PResult<'a, TyKind> {
1179         /*
1180
1181         [unsafe] [extern "ABI"] fn (S) -> T
1182          ^~~~^           ^~~~^     ^~^    ^
1183            |               |        |     |
1184            |               |        |   Return type
1185            |               |      Argument types
1186            |               |
1187            |              ABI
1188         Function Style
1189         */
1190
1191         let unsafety = self.parse_unsafety()?;
1192         let abi = if self.eat_keyword(keywords::Extern) {
1193             self.parse_opt_abi()?.unwrap_or(Abi::C)
1194         } else {
1195             Abi::Rust
1196         };
1197
1198         self.expect_keyword(keywords::Fn)?;
1199         let (inputs, variadic) = self.parse_fn_args(false, true)?;
1200         let ret_ty = self.parse_ret_ty()?;
1201         let decl = P(FnDecl {
1202             inputs: inputs,
1203             output: ret_ty,
1204             variadic: variadic
1205         });
1206         Ok(TyKind::BareFn(P(BareFnTy {
1207             abi: abi,
1208             unsafety: unsafety,
1209             lifetimes: lifetime_defs,
1210             decl: decl
1211         })))
1212     }
1213
1214     /// Parses an obsolete closure kind (`&:`, `&mut:`, or `:`).
1215     pub fn parse_obsolete_closure_kind(&mut self) -> PResult<'a, ()> {
1216          let lo = self.span.lo;
1217         if
1218             self.check(&token::BinOp(token::And)) &&
1219             self.look_ahead(1, |t| t.is_keyword(keywords::Mut)) &&
1220             self.look_ahead(2, |t| *t == token::Colon)
1221         {
1222             self.bump();
1223             self.bump();
1224             self.bump();
1225         } else if
1226             self.token == token::BinOp(token::And) &&
1227             self.look_ahead(1, |t| *t == token::Colon)
1228         {
1229             self.bump();
1230             self.bump();
1231         } else if
1232             self.eat(&token::Colon)
1233         {
1234             /* nothing */
1235         } else {
1236             return Ok(());
1237         }
1238
1239         let span = mk_sp(lo, self.span.hi);
1240         self.obsolete(span, ObsoleteSyntax::ClosureKind);
1241         Ok(())
1242     }
1243
1244     pub fn parse_unsafety(&mut self) -> PResult<'a, Unsafety> {
1245         if self.eat_keyword(keywords::Unsafe) {
1246             return Ok(Unsafety::Unsafe);
1247         } else {
1248             return Ok(Unsafety::Normal);
1249         }
1250     }
1251
1252     /// Parse the items in a trait declaration
1253     pub fn parse_trait_items(&mut self) -> PResult<'a,  Vec<TraitItem>> {
1254         self.parse_unspanned_seq(
1255             &token::OpenDelim(token::Brace),
1256             &token::CloseDelim(token::Brace),
1257             SeqSep::none(),
1258             |p| -> PResult<'a, TraitItem> {
1259             maybe_whole!(no_clone_from_p p, NtTraitItem);
1260             let mut attrs = p.parse_outer_attributes()?;
1261             let lo = p.span.lo;
1262
1263             let (name, node) = if p.eat_keyword(keywords::Type) {
1264                 let TyParam {ident, bounds, default, ..} = p.parse_ty_param()?;
1265                 p.expect(&token::Semi)?;
1266                 (ident, TraitItemKind::Type(bounds, default))
1267             } else if p.is_const_item() {
1268                 p.expect_keyword(keywords::Const)?;
1269                 let ident = p.parse_ident()?;
1270                 p.expect(&token::Colon)?;
1271                 let ty = p.parse_ty_sum()?;
1272                 let default = if p.check(&token::Eq) {
1273                     p.bump();
1274                     let expr = p.parse_expr()?;
1275                     p.commit_expr_expecting(&expr, token::Semi)?;
1276                     Some(expr)
1277                 } else {
1278                     p.expect(&token::Semi)?;
1279                     None
1280                 };
1281                 (ident, TraitItemKind::Const(ty, default))
1282             } else {
1283                 let (constness, unsafety, abi) = match p.parse_fn_front_matter() {
1284                     Ok(cua) => cua,
1285                     Err(e) => {
1286                         loop {
1287                             match p.token {
1288                                 token::Eof => break,
1289
1290                                 token::CloseDelim(token::Brace) |
1291                                 token::Semi => {
1292                                     p.bump();
1293                                     break;
1294                                 }
1295
1296                                 token::OpenDelim(token::Brace) => {
1297                                     p.parse_token_tree()?;
1298                                     break;
1299                                 }
1300
1301                                 _ => p.bump()
1302                             }
1303                         }
1304
1305                         return Err(e);
1306                     }
1307                 };
1308
1309                 let ident = p.parse_ident()?;
1310                 let mut generics = p.parse_generics()?;
1311
1312                 let (explicit_self, d) = p.parse_fn_decl_with_self(|p: &mut Parser<'a>|{
1313                     // This is somewhat dubious; We don't want to allow
1314                     // argument names to be left off if there is a
1315                     // definition...
1316                     p.parse_arg_general(false)
1317                 })?;
1318
1319                 generics.where_clause = p.parse_where_clause()?;
1320                 let sig = ast::MethodSig {
1321                     unsafety: unsafety,
1322                     constness: constness,
1323                     decl: d,
1324                     generics: generics,
1325                     abi: abi,
1326                     explicit_self: explicit_self,
1327                 };
1328
1329                 let body = match p.token {
1330                   token::Semi => {
1331                     p.bump();
1332                     debug!("parse_trait_methods(): parsing required method");
1333                     None
1334                   }
1335                   token::OpenDelim(token::Brace) => {
1336                     debug!("parse_trait_methods(): parsing provided method");
1337                     let (inner_attrs, body) =
1338                         p.parse_inner_attrs_and_block()?;
1339                     attrs.extend(inner_attrs.iter().cloned());
1340                     Some(body)
1341                   }
1342
1343                   _ => {
1344                       let token_str = p.this_token_to_string();
1345                       return Err(p.fatal(&format!("expected `;` or `{{`, found `{}`",
1346                                        token_str)[..]))
1347                   }
1348                 };
1349                 (ident, ast::TraitItemKind::Method(sig, body))
1350             };
1351
1352             Ok(TraitItem {
1353                 id: ast::DUMMY_NODE_ID,
1354                 ident: name,
1355                 attrs: attrs,
1356                 node: node,
1357                 span: mk_sp(lo, p.last_span.hi),
1358             })
1359         })
1360     }
1361
1362     /// Parse a possibly mutable type
1363     pub fn parse_mt(&mut self) -> PResult<'a, MutTy> {
1364         let mutbl = self.parse_mutability()?;
1365         let t = self.parse_ty()?;
1366         Ok(MutTy { ty: t, mutbl: mutbl })
1367     }
1368
1369     /// Parse optional return type [ -> TY ] in function decl
1370     pub fn parse_ret_ty(&mut self) -> PResult<'a, FunctionRetTy> {
1371         if self.eat(&token::RArrow) {
1372             if self.eat(&token::Not) {
1373                 Ok(FunctionRetTy::None(self.last_span))
1374             } else {
1375                 Ok(FunctionRetTy::Ty(self.parse_ty()?))
1376             }
1377         } else {
1378             let pos = self.span.lo;
1379             Ok(FunctionRetTy::Default(mk_sp(pos, pos)))
1380         }
1381     }
1382
1383     /// Parse a type in a context where `T1+T2` is allowed.
1384     pub fn parse_ty_sum(&mut self) -> PResult<'a, P<Ty>> {
1385         let lo = self.span.lo;
1386         let lhs = self.parse_ty()?;
1387
1388         if !self.eat(&token::BinOp(token::Plus)) {
1389             return Ok(lhs);
1390         }
1391
1392         let bounds = self.parse_ty_param_bounds(BoundParsingMode::Bare)?;
1393
1394         // In type grammar, `+` is treated like a binary operator,
1395         // and hence both L and R side are required.
1396         if bounds.is_empty() {
1397             let last_span = self.last_span;
1398             self.span_err(last_span,
1399                           "at least one type parameter bound \
1400                           must be specified");
1401         }
1402
1403         let sp = mk_sp(lo, self.last_span.hi);
1404         let sum = ast::TyKind::ObjectSum(lhs, bounds);
1405         Ok(P(Ty {id: ast::DUMMY_NODE_ID, node: sum, span: sp}))
1406     }
1407
1408     /// Parse a type.
1409     pub fn parse_ty(&mut self) -> PResult<'a, P<Ty>> {
1410         maybe_whole!(no_clone self, NtTy);
1411
1412         let lo = self.span.lo;
1413
1414         let t = if self.check(&token::OpenDelim(token::Paren)) {
1415             self.bump();
1416
1417             // (t) is a parenthesized ty
1418             // (t,) is the type of a tuple with only one field,
1419             // of type t
1420             let mut ts = vec![];
1421             let mut last_comma = false;
1422             while self.token != token::CloseDelim(token::Paren) {
1423                 ts.push(self.parse_ty_sum()?);
1424                 if self.check(&token::Comma) {
1425                     last_comma = true;
1426                     self.bump();
1427                 } else {
1428                     last_comma = false;
1429                     break;
1430                 }
1431             }
1432
1433             self.expect(&token::CloseDelim(token::Paren))?;
1434             if ts.len() == 1 && !last_comma {
1435                 TyKind::Paren(ts.into_iter().nth(0).unwrap())
1436             } else {
1437                 TyKind::Tup(ts)
1438             }
1439         } else if self.check(&token::BinOp(token::Star)) {
1440             // STAR POINTER (bare pointer?)
1441             self.bump();
1442             TyKind::Ptr(self.parse_ptr()?)
1443         } else if self.check(&token::OpenDelim(token::Bracket)) {
1444             // VECTOR
1445             self.expect(&token::OpenDelim(token::Bracket))?;
1446             let t = self.parse_ty_sum()?;
1447
1448             // Parse the `; e` in `[ i32; e ]`
1449             // where `e` is a const expression
1450             let t = match self.maybe_parse_fixed_length_of_vec()? {
1451                 None => TyKind::Vec(t),
1452                 Some(suffix) => TyKind::FixedLengthVec(t, suffix)
1453             };
1454             self.expect(&token::CloseDelim(token::Bracket))?;
1455             t
1456         } else if self.check(&token::BinOp(token::And)) ||
1457                   self.token == token::AndAnd {
1458             // BORROWED POINTER
1459             self.expect_and()?;
1460             self.parse_borrowed_pointee()?
1461         } else if self.check_keyword(keywords::For) {
1462             self.parse_for_in_type()?
1463         } else if self.token_is_bare_fn_keyword() {
1464             // BARE FUNCTION
1465             self.parse_ty_bare_fn(Vec::new())?
1466         } else if self.eat_keyword_noexpect(keywords::Typeof) {
1467             // TYPEOF
1468             // In order to not be ambiguous, the type must be surrounded by parens.
1469             self.expect(&token::OpenDelim(token::Paren))?;
1470             let e = self.parse_expr()?;
1471             self.expect(&token::CloseDelim(token::Paren))?;
1472             TyKind::Typeof(e)
1473         } else if self.eat_lt() {
1474
1475             let (qself, path) =
1476                  self.parse_qualified_path(NoTypesAllowed)?;
1477
1478             TyKind::Path(Some(qself), path)
1479         } else if self.check(&token::ModSep) ||
1480                   self.token.is_ident() ||
1481                   self.token.is_path() {
1482             let path = self.parse_path(LifetimeAndTypesWithoutColons)?;
1483             if self.check(&token::Not) {
1484                 // MACRO INVOCATION
1485                 self.bump();
1486                 let delim = self.expect_open_delim()?;
1487                 let tts = self.parse_seq_to_end(&token::CloseDelim(delim),
1488                                                 SeqSep::none(),
1489                                                 |p| p.parse_token_tree())?;
1490                 let hi = self.span.hi;
1491                 TyKind::Mac(spanned(lo, hi, Mac_ { path: path, tts: tts, ctxt: EMPTY_CTXT }))
1492             } else {
1493                 // NAMED TYPE
1494                 TyKind::Path(None, path)
1495             }
1496         } else if self.eat(&token::Underscore) {
1497             // TYPE TO BE INFERRED
1498             TyKind::Infer
1499         } else {
1500             let this_token_str = self.this_token_to_string();
1501             let msg = format!("expected type, found `{}`", this_token_str);
1502             return Err(self.fatal(&msg[..]));
1503         };
1504
1505         let sp = mk_sp(lo, self.last_span.hi);
1506         Ok(P(Ty {id: ast::DUMMY_NODE_ID, node: t, span: sp}))
1507     }
1508
1509     pub fn parse_borrowed_pointee(&mut self) -> PResult<'a, TyKind> {
1510         // look for `&'lt` or `&'foo ` and interpret `foo` as the region name:
1511         let opt_lifetime = self.parse_opt_lifetime()?;
1512
1513         let mt = self.parse_mt()?;
1514         return Ok(TyKind::Rptr(opt_lifetime, mt));
1515     }
1516
1517     pub fn parse_ptr(&mut self) -> PResult<'a, MutTy> {
1518         let mutbl = if self.eat_keyword(keywords::Mut) {
1519             Mutability::Mutable
1520         } else if self.eat_keyword(keywords::Const) {
1521             Mutability::Immutable
1522         } else {
1523             let span = self.last_span;
1524             self.span_err(span,
1525                           "expected mut or const in raw pointer type (use \
1526                            `*mut T` or `*const T` as appropriate)");
1527             Mutability::Immutable
1528         };
1529         let t = self.parse_ty()?;
1530         Ok(MutTy { ty: t, mutbl: mutbl })
1531     }
1532
1533     pub fn is_named_argument(&mut self) -> bool {
1534         let offset = match self.token {
1535             token::BinOp(token::And) => 1,
1536             token::AndAnd => 1,
1537             _ if self.token.is_keyword(keywords::Mut) => 1,
1538             _ => 0
1539         };
1540
1541         debug!("parser is_named_argument offset:{}", offset);
1542
1543         if offset == 0 {
1544             is_plain_ident_or_underscore(&self.token)
1545                 && self.look_ahead(1, |t| *t == token::Colon)
1546         } else {
1547             self.look_ahead(offset, |t| is_plain_ident_or_underscore(t))
1548                 && self.look_ahead(offset + 1, |t| *t == token::Colon)
1549         }
1550     }
1551
1552     /// This version of parse arg doesn't necessarily require
1553     /// identifier names.
1554     pub fn parse_arg_general(&mut self, require_name: bool) -> PResult<'a, Arg> {
1555         maybe_whole!(no_clone self, NtArg);
1556
1557         let pat = if require_name || self.is_named_argument() {
1558             debug!("parse_arg_general parse_pat (require_name:{})",
1559                    require_name);
1560             let pat = self.parse_pat()?;
1561
1562             self.expect(&token::Colon)?;
1563             pat
1564         } else {
1565             debug!("parse_arg_general ident_to_pat");
1566             let sp = self.last_span;
1567             let spanned = Spanned { span: sp, node: special_idents::invalid };
1568             P(Pat {
1569                 id: ast::DUMMY_NODE_ID,
1570                 node: PatKind::Ident(BindingMode::ByValue(Mutability::Immutable),
1571                                      spanned, None),
1572                 span: sp
1573             })
1574         };
1575
1576         let t = self.parse_ty_sum()?;
1577
1578         Ok(Arg {
1579             ty: t,
1580             pat: pat,
1581             id: ast::DUMMY_NODE_ID,
1582         })
1583     }
1584
1585     /// Parse a single function argument
1586     pub fn parse_arg(&mut self) -> PResult<'a, Arg> {
1587         self.parse_arg_general(true)
1588     }
1589
1590     /// Parse an argument in a lambda header e.g. |arg, arg|
1591     pub fn parse_fn_block_arg(&mut self) -> PResult<'a, Arg> {
1592         let pat = self.parse_pat()?;
1593         let t = if self.eat(&token::Colon) {
1594             self.parse_ty_sum()?
1595         } else {
1596             P(Ty {
1597                 id: ast::DUMMY_NODE_ID,
1598                 node: TyKind::Infer,
1599                 span: mk_sp(self.span.lo, self.span.hi),
1600             })
1601         };
1602         Ok(Arg {
1603             ty: t,
1604             pat: pat,
1605             id: ast::DUMMY_NODE_ID
1606         })
1607     }
1608
1609     pub fn maybe_parse_fixed_length_of_vec(&mut self) -> PResult<'a, Option<P<ast::Expr>>> {
1610         if self.check(&token::Semi) {
1611             self.bump();
1612             Ok(Some(self.parse_expr()?))
1613         } else {
1614             Ok(None)
1615         }
1616     }
1617
1618     /// Matches token_lit = LIT_INTEGER | ...
1619     pub fn lit_from_token(&self, tok: &token::Token) -> PResult<'a, LitKind> {
1620         match *tok {
1621             token::Interpolated(token::NtExpr(ref v)) => {
1622                 match v.node {
1623                     ExprKind::Lit(ref lit) => { Ok(lit.node.clone()) }
1624                     _ => { return self.unexpected_last(tok); }
1625                 }
1626             }
1627             token::Literal(lit, suf) => {
1628                 let (suffix_illegal, out) = match lit {
1629                     token::Byte(i) => (true, LitKind::Byte(parse::byte_lit(&i.as_str()).0)),
1630                     token::Char(i) => (true, LitKind::Char(parse::char_lit(&i.as_str()).0)),
1631
1632                     // there are some valid suffixes for integer and
1633                     // float literals, so all the handling is done
1634                     // internally.
1635                     token::Integer(s) => {
1636                         (false, parse::integer_lit(&s.as_str(),
1637                                                    suf.as_ref().map(|s| s.as_str()),
1638                                                    &self.sess.span_diagnostic,
1639                                                    self.last_span))
1640                     }
1641                     token::Float(s) => {
1642                         (false, parse::float_lit(&s.as_str(),
1643                                                  suf.as_ref().map(|s| s.as_str()),
1644                                                   &self.sess.span_diagnostic,
1645                                                  self.last_span))
1646                     }
1647
1648                     token::Str_(s) => {
1649                         (true,
1650                          LitKind::Str(token::intern_and_get_ident(&parse::str_lit(&s.as_str())),
1651                                       ast::StrStyle::Cooked))
1652                     }
1653                     token::StrRaw(s, n) => {
1654                         (true,
1655                          LitKind::Str(
1656                             token::intern_and_get_ident(&parse::raw_str_lit(&s.as_str())),
1657                             ast::StrStyle::Raw(n)))
1658                     }
1659                     token::ByteStr(i) =>
1660                         (true, LitKind::ByteStr(parse::byte_str_lit(&i.as_str()))),
1661                     token::ByteStrRaw(i, _) =>
1662                         (true,
1663                          LitKind::ByteStr(Rc::new(i.to_string().into_bytes()))),
1664                 };
1665
1666                 if suffix_illegal {
1667                     let sp = self.last_span;
1668                     self.expect_no_suffix(sp, &format!("{} literal", lit.short_name()), suf)
1669                 }
1670
1671                 Ok(out)
1672             }
1673             _ => { return self.unexpected_last(tok); }
1674         }
1675     }
1676
1677     /// Matches lit = true | false | token_lit
1678     pub fn parse_lit(&mut self) -> PResult<'a, Lit> {
1679         let lo = self.span.lo;
1680         let lit = if self.eat_keyword(keywords::True) {
1681             LitKind::Bool(true)
1682         } else if self.eat_keyword(keywords::False) {
1683             LitKind::Bool(false)
1684         } else {
1685             let token = self.bump_and_get();
1686             let lit = self.lit_from_token(&token)?;
1687             lit
1688         };
1689         Ok(codemap::Spanned { node: lit, span: mk_sp(lo, self.last_span.hi) })
1690     }
1691
1692     /// matches '-' lit | lit
1693     pub fn parse_pat_literal_maybe_minus(&mut self) -> PResult<'a, P<Expr>> {
1694         let minus_lo = self.span.lo;
1695         let minus_present = self.eat(&token::BinOp(token::Minus));
1696         let lo = self.span.lo;
1697         let literal = P(self.parse_lit()?);
1698         let hi = self.last_span.hi;
1699         let expr = self.mk_expr(lo, hi, ExprKind::Lit(literal), None);
1700
1701         if minus_present {
1702             let minus_hi = self.last_span.hi;
1703             let unary = self.mk_unary(UnOp::Neg, expr);
1704             Ok(self.mk_expr(minus_lo, minus_hi, unary, None))
1705         } else {
1706             Ok(expr)
1707         }
1708     }
1709
1710     /// Parses qualified path.
1711     ///
1712     /// Assumes that the leading `<` has been parsed already.
1713     ///
1714     /// Qualifed paths are a part of the universal function call
1715     /// syntax (UFCS).
1716     ///
1717     /// `qualified_path = <type [as trait_ref]>::path`
1718     ///
1719     /// See `parse_path` for `mode` meaning.
1720     ///
1721     /// # Examples:
1722     ///
1723     /// `<T as U>::a`
1724     /// `<T as U>::F::a::<S>`
1725     pub fn parse_qualified_path(&mut self, mode: PathParsingMode)
1726                                 -> PResult<'a, (QSelf, ast::Path)> {
1727         let span = self.last_span;
1728         let self_type = self.parse_ty_sum()?;
1729         let mut path = if self.eat_keyword(keywords::As) {
1730             self.parse_path(LifetimeAndTypesWithoutColons)?
1731         } else {
1732             ast::Path {
1733                 span: span,
1734                 global: false,
1735                 segments: vec![]
1736             }
1737         };
1738
1739         let qself = QSelf {
1740             ty: self_type,
1741             position: path.segments.len()
1742         };
1743
1744         self.expect(&token::Gt)?;
1745         self.expect(&token::ModSep)?;
1746
1747         let segments = match mode {
1748             LifetimeAndTypesWithoutColons => {
1749                 self.parse_path_segments_without_colons()?
1750             }
1751             LifetimeAndTypesWithColons => {
1752                 self.parse_path_segments_with_colons()?
1753             }
1754             NoTypesAllowed | ImportPrefix => {
1755                 self.parse_path_segments_without_types(mode == ImportPrefix)?
1756             }
1757         };
1758         path.segments.extend(segments);
1759
1760         path.span.hi = self.last_span.hi;
1761
1762         Ok((qself, path))
1763     }
1764
1765     /// Parses a path and optional type parameter bounds, depending on the
1766     /// mode. The `mode` parameter determines whether lifetimes, types, and/or
1767     /// bounds are permitted and whether `::` must precede type parameter
1768     /// groups.
1769     pub fn parse_path(&mut self, mode: PathParsingMode) -> PResult<'a, ast::Path> {
1770         // Check for a whole path...
1771         let found = match self.token {
1772             token::Interpolated(token::NtPath(_)) => Some(self.bump_and_get()),
1773             _ => None,
1774         };
1775         if let Some(token::Interpolated(token::NtPath(path))) = found {
1776             return Ok(*path);
1777         }
1778
1779         let lo = self.span.lo;
1780         let is_global = self.eat(&token::ModSep);
1781
1782         // Parse any number of segments and bound sets. A segment is an
1783         // identifier followed by an optional lifetime and a set of types.
1784         // A bound set is a set of type parameter bounds.
1785         let segments = match mode {
1786             LifetimeAndTypesWithoutColons => {
1787                 self.parse_path_segments_without_colons()?
1788             }
1789             LifetimeAndTypesWithColons => {
1790                 self.parse_path_segments_with_colons()?
1791             }
1792             NoTypesAllowed | ImportPrefix => {
1793                 self.parse_path_segments_without_types(mode == ImportPrefix)?
1794             }
1795         };
1796
1797         // Assemble the span.
1798         let span = mk_sp(lo, self.last_span.hi);
1799
1800         // Assemble the result.
1801         Ok(ast::Path {
1802             span: span,
1803             global: is_global,
1804             segments: segments,
1805         })
1806     }
1807
1808     /// Examples:
1809     /// - `a::b<T,U>::c<V,W>`
1810     /// - `a::b<T,U>::c(V) -> W`
1811     /// - `a::b<T,U>::c(V)`
1812     pub fn parse_path_segments_without_colons(&mut self) -> PResult<'a, Vec<ast::PathSegment>> {
1813         let mut segments = Vec::new();
1814         loop {
1815             // First, parse an identifier.
1816             let identifier = self.parse_ident_or_self_type()?;
1817
1818             // Parse types, optionally.
1819             let parameters = if self.eat_lt() {
1820                 let (lifetimes, types, bindings) = self.parse_generic_values_after_lt()?;
1821
1822                 ast::PathParameters::AngleBracketed(ast::AngleBracketedParameterData {
1823                     lifetimes: lifetimes,
1824                     types: P::from_vec(types),
1825                     bindings: P::from_vec(bindings),
1826                 })
1827             } else if self.eat(&token::OpenDelim(token::Paren)) {
1828                 let lo = self.last_span.lo;
1829
1830                 let inputs = self.parse_seq_to_end(
1831                     &token::CloseDelim(token::Paren),
1832                     SeqSep::trailing_allowed(token::Comma),
1833                     |p| p.parse_ty_sum())?;
1834
1835                 let output_ty = if self.eat(&token::RArrow) {
1836                     Some(self.parse_ty()?)
1837                 } else {
1838                     None
1839                 };
1840
1841                 let hi = self.last_span.hi;
1842
1843                 ast::PathParameters::Parenthesized(ast::ParenthesizedParameterData {
1844                     span: mk_sp(lo, hi),
1845                     inputs: inputs,
1846                     output: output_ty,
1847                 })
1848             } else {
1849                 ast::PathParameters::none()
1850             };
1851
1852             // Assemble and push the result.
1853             segments.push(ast::PathSegment { identifier: identifier,
1854                                              parameters: parameters });
1855
1856             // Continue only if we see a `::`
1857             if !self.eat(&token::ModSep) {
1858                 return Ok(segments);
1859             }
1860         }
1861     }
1862
1863     /// Examples:
1864     /// - `a::b::<T,U>::c`
1865     pub fn parse_path_segments_with_colons(&mut self) -> PResult<'a, Vec<ast::PathSegment>> {
1866         let mut segments = Vec::new();
1867         loop {
1868             // First, parse an identifier.
1869             let identifier = self.parse_ident_or_self_type()?;
1870
1871             // If we do not see a `::`, stop.
1872             if !self.eat(&token::ModSep) {
1873                 segments.push(ast::PathSegment {
1874                     identifier: identifier,
1875                     parameters: ast::PathParameters::none()
1876                 });
1877                 return Ok(segments);
1878             }
1879
1880             // Check for a type segment.
1881             if self.eat_lt() {
1882                 // Consumed `a::b::<`, go look for types
1883                 let (lifetimes, types, bindings) = self.parse_generic_values_after_lt()?;
1884                 let parameters = ast::AngleBracketedParameterData {
1885                     lifetimes: lifetimes,
1886                     types: P::from_vec(types),
1887                     bindings: P::from_vec(bindings),
1888                 };
1889                 segments.push(ast::PathSegment {
1890                     identifier: identifier,
1891                     parameters: ast::PathParameters::AngleBracketed(parameters),
1892                 });
1893
1894                 // Consumed `a::b::<T,U>`, check for `::` before proceeding
1895                 if !self.eat(&token::ModSep) {
1896                     return Ok(segments);
1897                 }
1898             } else {
1899                 // Consumed `a::`, go look for `b`
1900                 segments.push(ast::PathSegment {
1901                     identifier: identifier,
1902                     parameters: ast::PathParameters::none(),
1903                 });
1904             }
1905         }
1906     }
1907
1908
1909     /// Examples:
1910     /// - `a::b::c`
1911     pub fn parse_path_segments_without_types(&mut self, import_prefix: bool)
1912                                              -> PResult<'a, Vec<ast::PathSegment>> {
1913         let mut segments = Vec::new();
1914         loop {
1915             // First, parse an identifier.
1916             let identifier = self.parse_ident_or_self_type()?;
1917
1918             // Assemble and push the result.
1919             segments.push(ast::PathSegment {
1920                 identifier: identifier,
1921                 parameters: ast::PathParameters::none()
1922             });
1923
1924             // If we do not see a `::` or see `::{`/`::*`, stop.
1925             if !self.check(&token::ModSep) || import_prefix && self.is_import_coupler() {
1926                 return Ok(segments);
1927             } else {
1928                 self.bump();
1929             }
1930         }
1931     }
1932
1933     /// parses 0 or 1 lifetime
1934     pub fn parse_opt_lifetime(&mut self) -> PResult<'a, Option<ast::Lifetime>> {
1935         match self.token {
1936             token::Lifetime(..) => {
1937                 Ok(Some(self.parse_lifetime()?))
1938             }
1939             _ => {
1940                 Ok(None)
1941             }
1942         }
1943     }
1944
1945     /// Parses a single lifetime
1946     /// Matches lifetime = LIFETIME
1947     pub fn parse_lifetime(&mut self) -> PResult<'a, ast::Lifetime> {
1948         match self.token {
1949             token::Lifetime(i) => {
1950                 let span = self.span;
1951                 self.bump();
1952                 return Ok(ast::Lifetime {
1953                     id: ast::DUMMY_NODE_ID,
1954                     span: span,
1955                     name: i.name
1956                 });
1957             }
1958             _ => {
1959                 return Err(self.fatal("expected a lifetime name"));
1960             }
1961         }
1962     }
1963
1964     /// Parses `lifetime_defs = [ lifetime_defs { ',' lifetime_defs } ]` where `lifetime_def  =
1965     /// lifetime [':' lifetimes]`
1966     pub fn parse_lifetime_defs(&mut self) -> PResult<'a, Vec<ast::LifetimeDef>> {
1967
1968         let mut res = Vec::new();
1969         loop {
1970             match self.token {
1971                 token::Lifetime(_) => {
1972                     let lifetime = self.parse_lifetime()?;
1973                     let bounds =
1974                         if self.eat(&token::Colon) {
1975                             self.parse_lifetimes(token::BinOp(token::Plus))?
1976                         } else {
1977                             Vec::new()
1978                         };
1979                     res.push(ast::LifetimeDef { lifetime: lifetime,
1980                                                 bounds: bounds });
1981                 }
1982
1983                 _ => {
1984                     return Ok(res);
1985                 }
1986             }
1987
1988             match self.token {
1989                 token::Comma => { self.bump();}
1990                 token::Gt => { return Ok(res); }
1991                 token::BinOp(token::Shr) => { return Ok(res); }
1992                 _ => {
1993                     let this_token_str = self.this_token_to_string();
1994                     let msg = format!("expected `,` or `>` after lifetime \
1995                                       name, found `{}`",
1996                                       this_token_str);
1997                     return Err(self.fatal(&msg[..]));
1998                 }
1999             }
2000         }
2001     }
2002
2003     /// matches lifetimes = ( lifetime ) | ( lifetime , lifetimes ) actually, it matches the empty
2004     /// one too, but putting that in there messes up the grammar....
2005     ///
2006     /// Parses zero or more comma separated lifetimes. Expects each lifetime to be followed by
2007     /// either a comma or `>`.  Used when parsing type parameter lists, where we expect something
2008     /// like `<'a, 'b, T>`.
2009     pub fn parse_lifetimes(&mut self, sep: token::Token) -> PResult<'a, Vec<ast::Lifetime>> {
2010
2011         let mut res = Vec::new();
2012         loop {
2013             match self.token {
2014                 token::Lifetime(_) => {
2015                     res.push(self.parse_lifetime()?);
2016                 }
2017                 _ => {
2018                     return Ok(res);
2019                 }
2020             }
2021
2022             if self.token != sep {
2023                 return Ok(res);
2024             }
2025
2026             self.bump();
2027         }
2028     }
2029
2030     /// Parse mutability declaration (mut/const/imm)
2031     pub fn parse_mutability(&mut self) -> PResult<'a, Mutability> {
2032         if self.eat_keyword(keywords::Mut) {
2033             Ok(Mutability::Mutable)
2034         } else {
2035             Ok(Mutability::Immutable)
2036         }
2037     }
2038
2039     /// Parse ident COLON expr
2040     pub fn parse_field(&mut self) -> PResult<'a, Field> {
2041         let lo = self.span.lo;
2042         let i = self.parse_ident()?;
2043         let hi = self.last_span.hi;
2044         self.expect(&token::Colon)?;
2045         let e = self.parse_expr()?;
2046         Ok(ast::Field {
2047             ident: spanned(lo, hi, i),
2048             span: mk_sp(lo, e.span.hi),
2049             expr: e,
2050         })
2051     }
2052
2053     pub fn mk_expr(&mut self, lo: BytePos, hi: BytePos,
2054                    node: ExprKind, attrs: ThinAttributes) -> P<Expr> {
2055         P(Expr {
2056             id: ast::DUMMY_NODE_ID,
2057             node: node,
2058             span: mk_sp(lo, hi),
2059             attrs: attrs,
2060         })
2061     }
2062
2063     pub fn mk_unary(&mut self, unop: ast::UnOp, expr: P<Expr>) -> ast::ExprKind {
2064         ExprKind::Unary(unop, expr)
2065     }
2066
2067     pub fn mk_binary(&mut self, binop: ast::BinOp, lhs: P<Expr>, rhs: P<Expr>) -> ast::ExprKind {
2068         ExprKind::Binary(binop, lhs, rhs)
2069     }
2070
2071     pub fn mk_call(&mut self, f: P<Expr>, args: Vec<P<Expr>>) -> ast::ExprKind {
2072         ExprKind::Call(f, args)
2073     }
2074
2075     fn mk_method_call(&mut self,
2076                       ident: ast::SpannedIdent,
2077                       tps: Vec<P<Ty>>,
2078                       args: Vec<P<Expr>>)
2079                       -> ast::ExprKind {
2080         ExprKind::MethodCall(ident, tps, args)
2081     }
2082
2083     pub fn mk_index(&mut self, expr: P<Expr>, idx: P<Expr>) -> ast::ExprKind {
2084         ExprKind::Index(expr, idx)
2085     }
2086
2087     pub fn mk_range(&mut self,
2088                     start: Option<P<Expr>>,
2089                     end: Option<P<Expr>>,
2090                     limits: RangeLimits)
2091                     -> PResult<'a, ast::ExprKind> {
2092         if end.is_none() && limits == RangeLimits::Closed {
2093             Err(self.span_fatal_help(self.span,
2094                                      "inclusive range with no end",
2095                                      "inclusive ranges must be bounded at the end \
2096                                       (`...b` or `a...b`)"))
2097         } else {
2098             Ok(ExprKind::Range(start, end, limits))
2099         }
2100     }
2101
2102     pub fn mk_field(&mut self, expr: P<Expr>, ident: ast::SpannedIdent) -> ast::ExprKind {
2103         ExprKind::Field(expr, ident)
2104     }
2105
2106     pub fn mk_tup_field(&mut self, expr: P<Expr>, idx: codemap::Spanned<usize>) -> ast::ExprKind {
2107         ExprKind::TupField(expr, idx)
2108     }
2109
2110     pub fn mk_assign_op(&mut self, binop: ast::BinOp,
2111                         lhs: P<Expr>, rhs: P<Expr>) -> ast::ExprKind {
2112         ExprKind::AssignOp(binop, lhs, rhs)
2113     }
2114
2115     pub fn mk_mac_expr(&mut self, lo: BytePos, hi: BytePos,
2116                        m: Mac_, attrs: ThinAttributes) -> P<Expr> {
2117         P(Expr {
2118             id: ast::DUMMY_NODE_ID,
2119             node: ExprKind::Mac(codemap::Spanned {node: m, span: mk_sp(lo, hi)}),
2120             span: mk_sp(lo, hi),
2121             attrs: attrs,
2122         })
2123     }
2124
2125     pub fn mk_lit_u32(&mut self, i: u32, attrs: ThinAttributes) -> P<Expr> {
2126         let span = &self.span;
2127         let lv_lit = P(codemap::Spanned {
2128             node: LitKind::Int(i as u64, ast::LitIntType::Unsigned(UintTy::U32)),
2129             span: *span
2130         });
2131
2132         P(Expr {
2133             id: ast::DUMMY_NODE_ID,
2134             node: ExprKind::Lit(lv_lit),
2135             span: *span,
2136             attrs: attrs,
2137         })
2138     }
2139
2140     fn expect_open_delim(&mut self) -> PResult<'a, token::DelimToken> {
2141         self.expected_tokens.push(TokenType::Token(token::Gt));
2142         match self.token {
2143             token::OpenDelim(delim) => {
2144                 self.bump();
2145                 Ok(delim)
2146             },
2147             _ => Err(self.fatal("expected open delimiter")),
2148         }
2149     }
2150
2151     /// At the bottom (top?) of the precedence hierarchy,
2152     /// parse things like parenthesized exprs,
2153     /// macros, return, etc.
2154     ///
2155     /// NB: This does not parse outer attributes,
2156     ///     and is private because it only works
2157     ///     correctly if called from parse_dot_or_call_expr().
2158     fn parse_bottom_expr(&mut self) -> PResult<'a, P<Expr>> {
2159         maybe_whole_expr!(self);
2160
2161         // Outer attributes are already parsed and will be
2162         // added to the return value after the fact.
2163         //
2164         // Therefore, prevent sub-parser from parsing
2165         // attributes by giving them a empty "already parsed" list.
2166         let mut attrs = None;
2167
2168         let lo = self.span.lo;
2169         let mut hi = self.span.hi;
2170
2171         let ex: ExprKind;
2172
2173         // Note: when adding new syntax here, don't forget to adjust Token::can_begin_expr().
2174         match self.token {
2175             token::OpenDelim(token::Paren) => {
2176                 self.bump();
2177
2178                 let attrs = self.parse_inner_attributes()?
2179                     .into_thin_attrs()
2180                     .prepend(attrs);
2181
2182                 // (e) is parenthesized e
2183                 // (e,) is a tuple with only one field, e
2184                 let mut es = vec![];
2185                 let mut trailing_comma = false;
2186                 while self.token != token::CloseDelim(token::Paren) {
2187                     es.push(self.parse_expr()?);
2188                     self.commit_expr(&es.last().unwrap(), &[],
2189                                      &[token::Comma, token::CloseDelim(token::Paren)])?;
2190                     if self.check(&token::Comma) {
2191                         trailing_comma = true;
2192
2193                         self.bump();
2194                     } else {
2195                         trailing_comma = false;
2196                         break;
2197                     }
2198                 }
2199                 self.bump();
2200
2201                 hi = self.last_span.hi;
2202                 return if es.len() == 1 && !trailing_comma {
2203                     Ok(self.mk_expr(lo, hi, ExprKind::Paren(es.into_iter().nth(0).unwrap()), attrs))
2204                 } else {
2205                     Ok(self.mk_expr(lo, hi, ExprKind::Tup(es), attrs))
2206                 }
2207             },
2208             token::OpenDelim(token::Brace) => {
2209                 return self.parse_block_expr(lo, BlockCheckMode::Default, attrs);
2210             },
2211             token::BinOp(token::Or) |  token::OrOr => {
2212                 let lo = self.span.lo;
2213                 return self.parse_lambda_expr(lo, CaptureBy::Ref, attrs);
2214             },
2215             token::Ident(id @ ast::Ident {
2216                             name: token::SELF_KEYWORD_NAME,
2217                             ctxt: _
2218                          }, token::Plain) => {
2219                 self.bump();
2220                 let path = ast::Path::from_ident(mk_sp(lo, hi), id);
2221                 ex = ExprKind::Path(None, path);
2222                 hi = self.last_span.hi;
2223             }
2224             token::OpenDelim(token::Bracket) => {
2225                 self.bump();
2226
2227                 let inner_attrs = self.parse_inner_attributes()?
2228                     .into_thin_attrs();
2229                 attrs.update(|attrs| attrs.append(inner_attrs));
2230
2231                 if self.check(&token::CloseDelim(token::Bracket)) {
2232                     // Empty vector.
2233                     self.bump();
2234                     ex = ExprKind::Vec(Vec::new());
2235                 } else {
2236                     // Nonempty vector.
2237                     let first_expr = self.parse_expr()?;
2238                     if self.check(&token::Semi) {
2239                         // Repeating array syntax: [ 0; 512 ]
2240                         self.bump();
2241                         let count = self.parse_expr()?;
2242                         self.expect(&token::CloseDelim(token::Bracket))?;
2243                         ex = ExprKind::Repeat(first_expr, count);
2244                     } else if self.check(&token::Comma) {
2245                         // Vector with two or more elements.
2246                         self.bump();
2247                         let remaining_exprs = self.parse_seq_to_end(
2248                             &token::CloseDelim(token::Bracket),
2249                             SeqSep::trailing_allowed(token::Comma),
2250                             |p| Ok(p.parse_expr()?)
2251                         )?;
2252                         let mut exprs = vec!(first_expr);
2253                         exprs.extend(remaining_exprs);
2254                         ex = ExprKind::Vec(exprs);
2255                     } else {
2256                         // Vector with one element.
2257                         self.expect(&token::CloseDelim(token::Bracket))?;
2258                         ex = ExprKind::Vec(vec!(first_expr));
2259                     }
2260                 }
2261                 hi = self.last_span.hi;
2262             }
2263             _ => {
2264                 if self.eat_lt() {
2265                     let (qself, path) =
2266                         self.parse_qualified_path(LifetimeAndTypesWithColons)?;
2267                     hi = path.span.hi;
2268                     return Ok(self.mk_expr(lo, hi, ExprKind::Path(Some(qself), path), attrs));
2269                 }
2270                 if self.eat_keyword(keywords::Move) {
2271                     let lo = self.last_span.lo;
2272                     return self.parse_lambda_expr(lo, CaptureBy::Value, attrs);
2273                 }
2274                 if self.eat_keyword(keywords::If) {
2275                     return self.parse_if_expr(attrs);
2276                 }
2277                 if self.eat_keyword(keywords::For) {
2278                     let lo = self.last_span.lo;
2279                     return self.parse_for_expr(None, lo, attrs);
2280                 }
2281                 if self.eat_keyword(keywords::While) {
2282                     let lo = self.last_span.lo;
2283                     return self.parse_while_expr(None, lo, attrs);
2284                 }
2285                 if self.token.is_lifetime() {
2286                     let lifetime = self.get_lifetime();
2287                     let lo = self.span.lo;
2288                     self.bump();
2289                     self.expect(&token::Colon)?;
2290                     if self.eat_keyword(keywords::While) {
2291                         return self.parse_while_expr(Some(lifetime), lo, attrs)
2292                     }
2293                     if self.eat_keyword(keywords::For) {
2294                         return self.parse_for_expr(Some(lifetime), lo, attrs)
2295                     }
2296                     if self.eat_keyword(keywords::Loop) {
2297                         return self.parse_loop_expr(Some(lifetime), lo, attrs)
2298                     }
2299                     return Err(self.fatal("expected `while`, `for`, or `loop` after a label"))
2300                 }
2301                 if self.eat_keyword(keywords::Loop) {
2302                     let lo = self.last_span.lo;
2303                     return self.parse_loop_expr(None, lo, attrs);
2304                 }
2305                 if self.eat_keyword(keywords::Continue) {
2306                     let ex = if self.token.is_lifetime() {
2307                         let ex = ExprKind::Again(Some(Spanned{
2308                             node: self.get_lifetime(),
2309                             span: self.span
2310                         }));
2311                         self.bump();
2312                         ex
2313                     } else {
2314                         ExprKind::Again(None)
2315                     };
2316                     let hi = self.last_span.hi;
2317                     return Ok(self.mk_expr(lo, hi, ex, attrs));
2318                 }
2319                 if self.eat_keyword(keywords::Match) {
2320                     return self.parse_match_expr(attrs);
2321                 }
2322                 if self.eat_keyword(keywords::Unsafe) {
2323                     return self.parse_block_expr(
2324                         lo,
2325                         BlockCheckMode::Unsafe(ast::UserProvided),
2326                         attrs);
2327                 }
2328                 if self.eat_keyword(keywords::Return) {
2329                     if self.token.can_begin_expr() {
2330                         let e = self.parse_expr()?;
2331                         hi = e.span.hi;
2332                         ex = ExprKind::Ret(Some(e));
2333                     } else {
2334                         ex = ExprKind::Ret(None);
2335                     }
2336                 } else if self.eat_keyword(keywords::Break) {
2337                     if self.token.is_lifetime() {
2338                         ex = ExprKind::Break(Some(Spanned {
2339                             node: self.get_lifetime(),
2340                             span: self.span
2341                         }));
2342                         self.bump();
2343                     } else {
2344                         ex = ExprKind::Break(None);
2345                     }
2346                     hi = self.last_span.hi;
2347                 } else if self.token.is_keyword(keywords::Let) {
2348                     // Catch this syntax error here, instead of in `check_strict_keywords`, so
2349                     // that we can explicitly mention that let is not to be used as an expression
2350                     let mut db = self.fatal("expected expression, found statement (`let`)");
2351                     db.note("variable declaration using `let` is a statement");
2352                     return Err(db);
2353                 } else if self.check(&token::ModSep) ||
2354                         self.token.is_ident() &&
2355                         !self.check_keyword(keywords::True) &&
2356                         !self.check_keyword(keywords::False) {
2357                     let pth =
2358                         self.parse_path(LifetimeAndTypesWithColons)?;
2359
2360                     // `!`, as an operator, is prefix, so we know this isn't that
2361                     if self.check(&token::Not) {
2362                         // MACRO INVOCATION expression
2363                         self.bump();
2364
2365                         let delim = self.expect_open_delim()?;
2366                         let tts = self.parse_seq_to_end(
2367                             &token::CloseDelim(delim),
2368                             SeqSep::none(),
2369                             |p| p.parse_token_tree())?;
2370                         let hi = self.last_span.hi;
2371
2372                         return Ok(self.mk_mac_expr(lo,
2373                                                    hi,
2374                                                    Mac_ { path: pth, tts: tts, ctxt: EMPTY_CTXT },
2375                                                    attrs));
2376                     }
2377                     if self.check(&token::OpenDelim(token::Brace)) {
2378                         // This is a struct literal, unless we're prohibited
2379                         // from parsing struct literals here.
2380                         let prohibited = self.restrictions.contains(
2381                             Restrictions::RESTRICTION_NO_STRUCT_LITERAL
2382                         );
2383                         if !prohibited {
2384                             // It's a struct literal.
2385                             self.bump();
2386                             let mut fields = Vec::new();
2387                             let mut base = None;
2388
2389                             let attrs = attrs.append(
2390                                 self.parse_inner_attributes()?
2391                                     .into_thin_attrs());
2392
2393                             while self.token != token::CloseDelim(token::Brace) {
2394                                 if self.eat(&token::DotDot) {
2395                                     match self.parse_expr() {
2396                                         Ok(e) => {
2397                                             base = Some(e);
2398                                         }
2399                                         Err(mut e) => {
2400                                             e.emit();
2401                                             self.recover_stmt();
2402                                         }
2403                                     }
2404                                     break;
2405                                 }
2406
2407                                 match self.parse_field() {
2408                                     Ok(f) => fields.push(f),
2409                                     Err(mut e) => {
2410                                         e.emit();
2411                                         self.recover_stmt();
2412                                         break;
2413                                     }
2414                                 }
2415
2416                                 match self.commit_expr(&fields.last().unwrap().expr,
2417                                                        &[token::Comma],
2418                                                        &[token::CloseDelim(token::Brace)]) {
2419                                     Ok(()) => {}
2420                                     Err(mut e) => {
2421                                         e.emit();
2422                                         self.recover_stmt();
2423                                         break;
2424                                     }
2425                                 }
2426                             }
2427
2428                             hi = self.span.hi;
2429                             self.expect(&token::CloseDelim(token::Brace))?;
2430                             ex = ExprKind::Struct(pth, fields, base);
2431                             return Ok(self.mk_expr(lo, hi, ex, attrs));
2432                         }
2433                     }
2434
2435                     hi = pth.span.hi;
2436                     ex = ExprKind::Path(None, pth);
2437                 } else {
2438                     // other literal expression
2439                     let lit = self.parse_lit()?;
2440                     hi = lit.span.hi;
2441                     ex = ExprKind::Lit(P(lit));
2442                 }
2443             }
2444         }
2445
2446         return Ok(self.mk_expr(lo, hi, ex, attrs));
2447     }
2448
2449     fn parse_or_use_outer_attributes(&mut self,
2450                                      already_parsed_attrs: Option<ThinAttributes>)
2451                                      -> PResult<'a, ThinAttributes> {
2452         if let Some(attrs) = already_parsed_attrs {
2453             Ok(attrs)
2454         } else {
2455             self.parse_outer_attributes().map(|a| a.into_thin_attrs())
2456         }
2457     }
2458
2459     /// Parse a block or unsafe block
2460     pub fn parse_block_expr(&mut self, lo: BytePos, blk_mode: BlockCheckMode,
2461                             attrs: ThinAttributes)
2462                             -> PResult<'a, P<Expr>> {
2463
2464         let outer_attrs = attrs;
2465         self.expect(&token::OpenDelim(token::Brace))?;
2466
2467         let inner_attrs = self.parse_inner_attributes()?.into_thin_attrs();
2468         let attrs = outer_attrs.append(inner_attrs);
2469
2470         let blk = self.parse_block_tail(lo, blk_mode)?;
2471         return Ok(self.mk_expr(blk.span.lo, blk.span.hi, ExprKind::Block(blk), attrs));
2472     }
2473
2474     /// parse a.b or a(13) or a[4] or just a
2475     pub fn parse_dot_or_call_expr(&mut self,
2476                                   already_parsed_attrs: Option<ThinAttributes>)
2477                                   -> PResult<'a, P<Expr>> {
2478         let attrs = self.parse_or_use_outer_attributes(already_parsed_attrs)?;
2479
2480         let b = self.parse_bottom_expr();
2481         let (span, b) = self.interpolated_or_expr_span(b)?;
2482         self.parse_dot_or_call_expr_with(b, span.lo, attrs)
2483     }
2484
2485     pub fn parse_dot_or_call_expr_with(&mut self,
2486                                        e0: P<Expr>,
2487                                        lo: BytePos,
2488                                        attrs: ThinAttributes)
2489                                        -> PResult<'a, P<Expr>> {
2490         // Stitch the list of outer attributes onto the return value.
2491         // A little bit ugly, but the best way given the current code
2492         // structure
2493         self.parse_dot_or_call_expr_with_(e0, lo)
2494         .map(|expr|
2495             expr.map(|mut expr| {
2496                 expr.attrs.update(|a| a.prepend(attrs));
2497                 match expr.node {
2498                     ExprKind::If(..) | ExprKind::IfLet(..) => {
2499                         if !expr.attrs.as_attr_slice().is_empty() {
2500                             // Just point to the first attribute in there...
2501                             let span = expr.attrs.as_attr_slice()[0].span;
2502
2503                             self.span_err(span,
2504                                 "attributes are not yet allowed on `if` \
2505                                 expressions");
2506                         }
2507                     }
2508                     _ => {}
2509                 }
2510                 expr
2511             })
2512         )
2513     }
2514
2515     // Assuming we have just parsed `.foo` (i.e., a dot and an ident), continue
2516     // parsing into an expression.
2517     fn parse_dot_suffix(&mut self,
2518                         ident: Ident,
2519                         ident_span: Span,
2520                         self_value: P<Expr>,
2521                         lo: BytePos)
2522                         -> PResult<'a, P<Expr>> {
2523         let (_, tys, bindings) = if self.eat(&token::ModSep) {
2524             self.expect_lt()?;
2525             self.parse_generic_values_after_lt()?
2526         } else {
2527             (Vec::new(), Vec::new(), Vec::new())
2528         };
2529
2530         if !bindings.is_empty() {
2531             let last_span = self.last_span;
2532             self.span_err(last_span, "type bindings are only permitted on trait paths");
2533         }
2534
2535         Ok(match self.token {
2536             // expr.f() method call.
2537             token::OpenDelim(token::Paren) => {
2538                 let mut es = self.parse_unspanned_seq(
2539                     &token::OpenDelim(token::Paren),
2540                     &token::CloseDelim(token::Paren),
2541                     SeqSep::trailing_allowed(token::Comma),
2542                     |p| Ok(p.parse_expr()?)
2543                 )?;
2544                 let hi = self.last_span.hi;
2545
2546                 es.insert(0, self_value);
2547                 let id = spanned(ident_span.lo, ident_span.hi, ident);
2548                 let nd = self.mk_method_call(id, tys, es);
2549                 self.mk_expr(lo, hi, nd, None)
2550             }
2551             // Field access.
2552             _ => {
2553                 if !tys.is_empty() {
2554                     let last_span = self.last_span;
2555                     self.span_err(last_span,
2556                                   "field expressions may not \
2557                                    have type parameters");
2558                 }
2559
2560                 let id = spanned(ident_span.lo, ident_span.hi, ident);
2561                 let field = self.mk_field(self_value, id);
2562                 self.mk_expr(lo, ident_span.hi, field, None)
2563             }
2564         })
2565     }
2566
2567     fn parse_dot_or_call_expr_with_(&mut self, e0: P<Expr>, lo: BytePos) -> PResult<'a, P<Expr>> {
2568         let mut e = e0;
2569         let mut hi;
2570         loop {
2571             // expr?
2572             while self.eat(&token::Question) {
2573                 let hi = self.last_span.hi;
2574                 e = self.mk_expr(lo, hi, ExprKind::Try(e), None);
2575             }
2576
2577             // expr.f
2578             if self.eat(&token::Dot) {
2579                 match self.token {
2580                   token::Ident(i, _) => {
2581                     let dot_pos = self.last_span.hi;
2582                     hi = self.span.hi;
2583                     self.bump();
2584
2585                     e = self.parse_dot_suffix(i, mk_sp(dot_pos, hi), e, lo)?;
2586                   }
2587                   token::Literal(token::Integer(n), suf) => {
2588                     let sp = self.span;
2589
2590                     // A tuple index may not have a suffix
2591                     self.expect_no_suffix(sp, "tuple index", suf);
2592
2593                     let dot = self.last_span.hi;
2594                     hi = self.span.hi;
2595                     self.bump();
2596
2597                     let index = n.as_str().parse::<usize>().ok();
2598                     match index {
2599                         Some(n) => {
2600                             let id = spanned(dot, hi, n);
2601                             let field = self.mk_tup_field(e, id);
2602                             e = self.mk_expr(lo, hi, field, None);
2603                         }
2604                         None => {
2605                             let last_span = self.last_span;
2606                             self.span_err(last_span, "invalid tuple or tuple struct index");
2607                         }
2608                     }
2609                   }
2610                   token::Literal(token::Float(n), _suf) => {
2611                     self.bump();
2612                     let last_span = self.last_span;
2613                     let fstr = n.as_str();
2614                     let mut err = self.diagnostic().struct_span_err(last_span,
2615                         &format!("unexpected token: `{}`", n.as_str()));
2616                     if fstr.chars().all(|x| "0123456789.".contains(x)) {
2617                         let float = match fstr.parse::<f64>().ok() {
2618                             Some(f) => f,
2619                             None => continue,
2620                         };
2621                         err.fileline_help(last_span,
2622                             &format!("try parenthesizing the first index; e.g., `(foo.{}){}`",
2623                                     float.trunc() as usize,
2624                                     format!(".{}", fstr.splitn(2, ".").last().unwrap())));
2625                     }
2626                     return Err(err);
2627
2628                   }
2629                   _ => {
2630                     // FIXME Could factor this out into non_fatal_unexpected or something.
2631                     let actual = self.this_token_to_string();
2632                     self.span_err(self.span, &format!("unexpected token: `{}`", actual));
2633
2634                     let dot_pos = self.last_span.hi;
2635                     e = self.parse_dot_suffix(special_idents::invalid,
2636                                               mk_sp(dot_pos, dot_pos),
2637                                               e, lo)?;
2638                   }
2639                 }
2640                 continue;
2641             }
2642             if self.expr_is_complete(&e) { break; }
2643             match self.token {
2644               // expr(...)
2645               token::OpenDelim(token::Paren) => {
2646                 let es = self.parse_unspanned_seq(
2647                     &token::OpenDelim(token::Paren),
2648                     &token::CloseDelim(token::Paren),
2649                     SeqSep::trailing_allowed(token::Comma),
2650                     |p| Ok(p.parse_expr()?)
2651                 )?;
2652                 hi = self.last_span.hi;
2653
2654                 let nd = self.mk_call(e, es);
2655                 e = self.mk_expr(lo, hi, nd, None);
2656               }
2657
2658               // expr[...]
2659               // Could be either an index expression or a slicing expression.
2660               token::OpenDelim(token::Bracket) => {
2661                 self.bump();
2662                 let ix = self.parse_expr()?;
2663                 hi = self.span.hi;
2664                 self.commit_expr_expecting(&ix, token::CloseDelim(token::Bracket))?;
2665                 let index = self.mk_index(e, ix);
2666                 e = self.mk_expr(lo, hi, index, None)
2667               }
2668               _ => return Ok(e)
2669             }
2670         }
2671         return Ok(e);
2672     }
2673
2674     // Parse unquoted tokens after a `$` in a token tree
2675     fn parse_unquoted(&mut self) -> PResult<'a, TokenTree> {
2676         let mut sp = self.span;
2677         let (name, namep) = match self.token {
2678             token::Dollar => {
2679                 self.bump();
2680
2681                 if self.token == token::OpenDelim(token::Paren) {
2682                     let Spanned { node: seq, span: seq_span } = self.parse_seq(
2683                         &token::OpenDelim(token::Paren),
2684                         &token::CloseDelim(token::Paren),
2685                         SeqSep::none(),
2686                         |p| p.parse_token_tree()
2687                     )?;
2688                     let (sep, repeat) = self.parse_sep_and_kleene_op()?;
2689                     let name_num = macro_parser::count_names(&seq);
2690                     return Ok(TokenTree::Sequence(mk_sp(sp.lo, seq_span.hi),
2691                                       Rc::new(SequenceRepetition {
2692                                           tts: seq,
2693                                           separator: sep,
2694                                           op: repeat,
2695                                           num_captures: name_num
2696                                       })));
2697                 } else if self.token.is_keyword_allow_following_colon(keywords::Crate) {
2698                     self.bump();
2699                     return Ok(TokenTree::Token(sp, SpecialVarNt(SpecialMacroVar::CrateMacroVar)));
2700                 } else {
2701                     sp = mk_sp(sp.lo, self.span.hi);
2702                     let namep = match self.token { token::Ident(_, p) => p, _ => token::Plain };
2703                     let name = self.parse_ident()?;
2704                     (name, namep)
2705                 }
2706             }
2707             token::SubstNt(name, namep) => {
2708                 self.bump();
2709                 (name, namep)
2710             }
2711             _ => unreachable!()
2712         };
2713         // continue by trying to parse the `:ident` after `$name`
2714         if self.token == token::Colon && self.look_ahead(1, |t| t.is_ident() &&
2715                                                                 !t.is_strict_keyword() &&
2716                                                                 !t.is_reserved_keyword()) {
2717             self.bump();
2718             sp = mk_sp(sp.lo, self.span.hi);
2719             let kindp = match self.token { token::Ident(_, p) => p, _ => token::Plain };
2720             let nt_kind = self.parse_ident()?;
2721             Ok(TokenTree::Token(sp, MatchNt(name, nt_kind, namep, kindp)))
2722         } else {
2723             Ok(TokenTree::Token(sp, SubstNt(name, namep)))
2724         }
2725     }
2726
2727     pub fn check_unknown_macro_variable(&mut self) {
2728         if self.quote_depth == 0 {
2729             match self.token {
2730                 token::SubstNt(name, _) =>
2731                     self.fatal(&format!("unknown macro variable `{}`", name)).emit(),
2732                 _ => {}
2733             }
2734         }
2735     }
2736
2737     /// Parse an optional separator followed by a Kleene-style
2738     /// repetition token (+ or *).
2739     pub fn parse_sep_and_kleene_op(&mut self)
2740                                    -> PResult<'a, (Option<token::Token>, ast::KleeneOp)> {
2741         fn parse_kleene_op<'a>(parser: &mut Parser<'a>) -> PResult<'a,  Option<ast::KleeneOp>> {
2742             match parser.token {
2743                 token::BinOp(token::Star) => {
2744                     parser.bump();
2745                     Ok(Some(ast::KleeneOp::ZeroOrMore))
2746                 },
2747                 token::BinOp(token::Plus) => {
2748                     parser.bump();
2749                     Ok(Some(ast::KleeneOp::OneOrMore))
2750                 },
2751                 _ => Ok(None)
2752             }
2753         };
2754
2755         match parse_kleene_op(self)? {
2756             Some(kleene_op) => return Ok((None, kleene_op)),
2757             None => {}
2758         }
2759
2760         let separator = self.bump_and_get();
2761         match parse_kleene_op(self)? {
2762             Some(zerok) => Ok((Some(separator), zerok)),
2763             None => return Err(self.fatal("expected `*` or `+`"))
2764         }
2765     }
2766
2767     /// parse a single token tree from the input.
2768     pub fn parse_token_tree(&mut self) -> PResult<'a, TokenTree> {
2769         // FIXME #6994: currently, this is too eager. It
2770         // parses token trees but also identifies TokenType::Sequence's
2771         // and token::SubstNt's; it's too early to know yet
2772         // whether something will be a nonterminal or a seq
2773         // yet.
2774         maybe_whole!(deref self, NtTT);
2775
2776         match self.token {
2777             token::Eof => {
2778                 let mut err: DiagnosticBuilder<'a> =
2779                     self.diagnostic().struct_span_err(self.span,
2780                                                       "this file contains an un-closed delimiter");
2781                 for &(_, sp) in &self.open_braces {
2782                     err.span_help(sp, "did you mean to close this delimiter?");
2783                 }
2784
2785                 Err(err)
2786             },
2787             token::OpenDelim(delim) => {
2788                 // The span for beginning of the delimited section
2789                 let pre_span = self.span;
2790
2791                 // Parse the open delimiter.
2792                 self.open_braces.push((delim, self.span));
2793                 let open_span = self.span;
2794                 self.bump();
2795
2796                 // Parse the token trees within the delimiters.
2797                 // We stop at any delimiter so we can try to recover if the user
2798                 // uses an incorrect delimiter.
2799                 let tts = self.parse_seq_to_before_tokens(&[&token::CloseDelim(token::Brace),
2800                                                             &token::CloseDelim(token::Paren),
2801                                                             &token::CloseDelim(token::Bracket)],
2802                                                           SeqSep::none(),
2803                                                           |p| p.parse_token_tree(),
2804                                                           |mut e| e.emit());
2805
2806                 let close_span = self.span;
2807                 // Expand to cover the entire delimited token tree
2808                 let span = Span { hi: close_span.hi, ..pre_span };
2809
2810                 match self.token {
2811                     // Correct delmiter.
2812                     token::CloseDelim(d) if d == delim => {
2813                         self.open_braces.pop().unwrap();
2814
2815                         // Parse the close delimiter.
2816                         self.bump();
2817                     }
2818                     // Incorect delimiter.
2819                     token::CloseDelim(other) => {
2820                         let token_str = self.this_token_to_string();
2821                         let mut err = self.diagnostic().struct_span_err(self.span,
2822                             &format!("incorrect close delimiter: `{}`", token_str));
2823                         // This is a conservative error: only report the last unclosed delimiter.
2824                         // The previous unclosed delimiters could actually be closed! The parser
2825                         // just hasn't gotten to them yet.
2826                         if let Some(&(_, sp)) = self.open_braces.last() {
2827                             err.span_note(sp, "unclosed delimiter");
2828                         };
2829                         err.emit();
2830
2831                         self.open_braces.pop().unwrap();
2832
2833                         // If the incorrect delimter matches an earlier opening
2834                         // delimiter, then don't consume it (it can be used to
2835                         // close the earlier one)Otherwise, consume it.
2836                         // E.g., we try to recover from:
2837                         // fn foo() {
2838                         //     bar(baz(
2839                         // }  // Incorrect delimiter but matches the earlier `{`
2840                         if !self.open_braces.iter().any(|&(b, _)| b == other) {
2841                             self.bump();
2842                         }
2843                     }
2844                     token::Eof => {
2845                         // Silently recover, the EOF token will be seen again
2846                         // and an error emitted then. Thus we don't pop from
2847                         // self.open_braces here.
2848                     },
2849                     _ => unreachable!(),
2850                 }
2851
2852                 Ok(TokenTree::Delimited(span, Rc::new(Delimited {
2853                     delim: delim,
2854                     open_span: open_span,
2855                     tts: tts,
2856                     close_span: close_span,
2857                 })))
2858             },
2859             _ => {
2860                 // invariants: the current token is not a left-delimiter,
2861                 // not an EOF, and not the desired right-delimiter (if
2862                 // it were, parse_seq_to_before_end would have prevented
2863                 // reaching this point.
2864                 maybe_whole!(deref self, NtTT);
2865                 match self.token {
2866                     token::CloseDelim(_) => {
2867                         // An unexpected closing delimiter (i.e., there is no
2868                         // matching opening delimiter).
2869                         let token_str = self.this_token_to_string();
2870                         let err = self.diagnostic().struct_span_err(self.span,
2871                             &format!("unexpected close delimiter: `{}`", token_str));
2872                         Err(err)
2873                     },
2874                     /* we ought to allow different depths of unquotation */
2875                     token::Dollar | token::SubstNt(..) if self.quote_depth > 0 => {
2876                         self.parse_unquoted()
2877                     }
2878                     _ => {
2879                         Ok(TokenTree::Token(self.span, self.bump_and_get()))
2880                     }
2881                 }
2882             }
2883         }
2884     }
2885
2886     // parse a stream of tokens into a list of TokenTree's,
2887     // up to EOF.
2888     pub fn parse_all_token_trees(&mut self) -> PResult<'a, Vec<TokenTree>> {
2889         let mut tts = Vec::new();
2890         while self.token != token::Eof {
2891             tts.push(self.parse_token_tree()?);
2892         }
2893         Ok(tts)
2894     }
2895
2896     /// Parse a prefix-unary-operator expr
2897     pub fn parse_prefix_expr(&mut self,
2898                              already_parsed_attrs: Option<ThinAttributes>)
2899                              -> PResult<'a, P<Expr>> {
2900         let attrs = self.parse_or_use_outer_attributes(already_parsed_attrs)?;
2901         let lo = self.span.lo;
2902         let hi;
2903         // Note: when adding new unary operators, don't forget to adjust Token::can_begin_expr()
2904         let ex = match self.token {
2905             token::Not => {
2906                 self.bump();
2907                 let e = self.parse_prefix_expr(None);
2908                 let (span, e) = self.interpolated_or_expr_span(e)?;
2909                 hi = span.hi;
2910                 self.mk_unary(UnOp::Not, e)
2911             }
2912             token::BinOp(token::Minus) => {
2913                 self.bump();
2914                 let e = self.parse_prefix_expr(None);
2915                 let (span, e) = self.interpolated_or_expr_span(e)?;
2916                 hi = span.hi;
2917                 self.mk_unary(UnOp::Neg, e)
2918             }
2919             token::BinOp(token::Star) => {
2920                 self.bump();
2921                 let e = self.parse_prefix_expr(None);
2922                 let (span, e) = self.interpolated_or_expr_span(e)?;
2923                 hi = span.hi;
2924                 self.mk_unary(UnOp::Deref, e)
2925             }
2926             token::BinOp(token::And) | token::AndAnd => {
2927                 self.expect_and()?;
2928                 let m = self.parse_mutability()?;
2929                 let e = self.parse_prefix_expr(None);
2930                 let (span, e) = self.interpolated_or_expr_span(e)?;
2931                 hi = span.hi;
2932                 ExprKind::AddrOf(m, e)
2933             }
2934             token::Ident(..) if self.token.is_keyword(keywords::In) => {
2935                 self.bump();
2936                 let place = self.parse_expr_res(
2937                     Restrictions::RESTRICTION_NO_STRUCT_LITERAL,
2938                     None,
2939                 )?;
2940                 let blk = self.parse_block()?;
2941                 let span = blk.span;
2942                 hi = span.hi;
2943                 let blk_expr = self.mk_expr(span.lo, span.hi, ExprKind::Block(blk),
2944                                             None);
2945                 ExprKind::InPlace(place, blk_expr)
2946             }
2947             token::Ident(..) if self.token.is_keyword(keywords::Box) => {
2948                 self.bump();
2949                 let e = self.parse_prefix_expr(None);
2950                 let (span, e) = self.interpolated_or_expr_span(e)?;
2951                 hi = span.hi;
2952                 ExprKind::Box(e)
2953             }
2954             _ => return self.parse_dot_or_call_expr(Some(attrs))
2955         };
2956         return Ok(self.mk_expr(lo, hi, ex, attrs));
2957     }
2958
2959     /// Parse an associative expression
2960     ///
2961     /// This parses an expression accounting for associativity and precedence of the operators in
2962     /// the expression.
2963     pub fn parse_assoc_expr(&mut self,
2964                             already_parsed_attrs: Option<ThinAttributes>)
2965                             -> PResult<'a, P<Expr>> {
2966         self.parse_assoc_expr_with(0, already_parsed_attrs.into())
2967     }
2968
2969     /// Parse an associative expression with operators of at least `min_prec` precedence
2970     pub fn parse_assoc_expr_with(&mut self,
2971                                  min_prec: usize,
2972                                  lhs: LhsExpr)
2973                                  -> PResult<'a, P<Expr>> {
2974         let mut lhs = if let LhsExpr::AlreadyParsed(expr) = lhs {
2975             expr
2976         } else {
2977             let attrs = match lhs {
2978                 LhsExpr::AttributesParsed(attrs) => Some(attrs),
2979                 _ => None,
2980             };
2981             if self.token == token::DotDot || self.token == token::DotDotDot {
2982                 return self.parse_prefix_range_expr(attrs);
2983             } else {
2984                 self.parse_prefix_expr(attrs)?
2985             }
2986         };
2987
2988         if self.expr_is_complete(&lhs) {
2989             // Semi-statement forms are odd. See https://github.com/rust-lang/rust/issues/29071
2990             return Ok(lhs);
2991         }
2992         self.expected_tokens.push(TokenType::Operator);
2993         while let Some(op) = AssocOp::from_token(&self.token) {
2994
2995             let lhs_span = if self.last_token_interpolated {
2996                 self.last_span
2997             } else {
2998                 lhs.span
2999             };
3000
3001             let cur_op_span = self.span;
3002             let restrictions = if op.is_assign_like() {
3003                 self.restrictions & Restrictions::RESTRICTION_NO_STRUCT_LITERAL
3004             } else {
3005                 self.restrictions
3006             };
3007             if op.precedence() < min_prec {
3008                 break;
3009             }
3010             self.bump();
3011             if op.is_comparison() {
3012                 self.check_no_chained_comparison(&lhs, &op);
3013             }
3014             // Special cases:
3015             if op == AssocOp::As {
3016                 let rhs = self.parse_ty()?;
3017                 lhs = self.mk_expr(lhs_span.lo, rhs.span.hi,
3018                                    ExprKind::Cast(lhs, rhs), None);
3019                 continue
3020             } else if op == AssocOp::Colon {
3021                 let rhs = self.parse_ty()?;
3022                 lhs = self.mk_expr(lhs_span.lo, rhs.span.hi,
3023                                    ExprKind::Type(lhs, rhs), None);
3024                 continue
3025             } else if op == AssocOp::DotDot || op == AssocOp::DotDotDot {
3026                 // If we didn’t have to handle `x..`/`x...`, it would be pretty easy to
3027                 // generalise it to the Fixity::None code.
3028                 //
3029                 // We have 2 alternatives here: `x..y`/`x...y` and `x..`/`x...` The other
3030                 // two variants are handled with `parse_prefix_range_expr` call above.
3031                 let rhs = if self.is_at_start_of_range_notation_rhs() {
3032                     let rhs = self.parse_assoc_expr_with(op.precedence() + 1,
3033                                                          LhsExpr::NotYetParsed);
3034                     match rhs {
3035                         Ok(e) => Some(e),
3036                         Err(mut e) => {
3037                             e.cancel();
3038                             None
3039                         }
3040                     }
3041                 } else {
3042                     None
3043                 };
3044                 let (lhs_span, rhs_span) = (lhs.span, if let Some(ref x) = rhs {
3045                     x.span
3046                 } else {
3047                     cur_op_span
3048                 });
3049                 let limits = if op == AssocOp::DotDot {
3050                     RangeLimits::HalfOpen
3051                 } else {
3052                     RangeLimits::Closed
3053                 };
3054
3055                 let r = try!(self.mk_range(Some(lhs), rhs, limits));
3056                 lhs = self.mk_expr(lhs_span.lo, rhs_span.hi, r, None);
3057                 break
3058             }
3059
3060             let rhs = match op.fixity() {
3061                 Fixity::Right => self.with_res(
3062                     restrictions - Restrictions::RESTRICTION_STMT_EXPR,
3063                     |this| {
3064                         this.parse_assoc_expr_with(op.precedence(),
3065                             LhsExpr::NotYetParsed)
3066                 }),
3067                 Fixity::Left => self.with_res(
3068                     restrictions - Restrictions::RESTRICTION_STMT_EXPR,
3069                     |this| {
3070                         this.parse_assoc_expr_with(op.precedence() + 1,
3071                             LhsExpr::NotYetParsed)
3072                 }),
3073                 // We currently have no non-associative operators that are not handled above by
3074                 // the special cases. The code is here only for future convenience.
3075                 Fixity::None => self.with_res(
3076                     restrictions - Restrictions::RESTRICTION_STMT_EXPR,
3077                     |this| {
3078                         this.parse_assoc_expr_with(op.precedence() + 1,
3079                             LhsExpr::NotYetParsed)
3080                 }),
3081             }?;
3082
3083             lhs = match op {
3084                 AssocOp::Add | AssocOp::Subtract | AssocOp::Multiply | AssocOp::Divide |
3085                 AssocOp::Modulus | AssocOp::LAnd | AssocOp::LOr | AssocOp::BitXor |
3086                 AssocOp::BitAnd | AssocOp::BitOr | AssocOp::ShiftLeft | AssocOp::ShiftRight |
3087                 AssocOp::Equal | AssocOp::Less | AssocOp::LessEqual | AssocOp::NotEqual |
3088                 AssocOp::Greater | AssocOp::GreaterEqual => {
3089                     let ast_op = op.to_ast_binop().unwrap();
3090                     let (lhs_span, rhs_span) = (lhs_span, rhs.span);
3091                     let binary = self.mk_binary(codemap::respan(cur_op_span, ast_op), lhs, rhs);
3092                     self.mk_expr(lhs_span.lo, rhs_span.hi, binary, None)
3093                 }
3094                 AssocOp::Assign =>
3095                     self.mk_expr(lhs_span.lo, rhs.span.hi, ExprKind::Assign(lhs, rhs), None),
3096                 AssocOp::Inplace =>
3097                     self.mk_expr(lhs_span.lo, rhs.span.hi, ExprKind::InPlace(lhs, rhs), None),
3098                 AssocOp::AssignOp(k) => {
3099                     let aop = match k {
3100                         token::Plus =>    BinOpKind::Add,
3101                         token::Minus =>   BinOpKind::Sub,
3102                         token::Star =>    BinOpKind::Mul,
3103                         token::Slash =>   BinOpKind::Div,
3104                         token::Percent => BinOpKind::Rem,
3105                         token::Caret =>   BinOpKind::BitXor,
3106                         token::And =>     BinOpKind::BitAnd,
3107                         token::Or =>      BinOpKind::BitOr,
3108                         token::Shl =>     BinOpKind::Shl,
3109                         token::Shr =>     BinOpKind::Shr,
3110                     };
3111                     let (lhs_span, rhs_span) = (lhs_span, rhs.span);
3112                     let aopexpr = self.mk_assign_op(codemap::respan(cur_op_span, aop), lhs, rhs);
3113                     self.mk_expr(lhs_span.lo, rhs_span.hi, aopexpr, None)
3114                 }
3115                 AssocOp::As | AssocOp::Colon | AssocOp::DotDot | AssocOp::DotDotDot => {
3116                     self.bug("As, Colon, DotDot or DotDotDot branch reached")
3117                 }
3118             };
3119
3120             if op.fixity() == Fixity::None { break }
3121         }
3122         Ok(lhs)
3123     }
3124
3125     /// Produce an error if comparison operators are chained (RFC #558).
3126     /// We only need to check lhs, not rhs, because all comparison ops
3127     /// have same precedence and are left-associative
3128     fn check_no_chained_comparison(&mut self, lhs: &Expr, outer_op: &AssocOp) {
3129         debug_assert!(outer_op.is_comparison());
3130         match lhs.node {
3131             ExprKind::Binary(op, _, _) if op.node.is_comparison() => {
3132                 // respan to include both operators
3133                 let op_span = mk_sp(op.span.lo, self.span.hi);
3134                 let mut err = self.diagnostic().struct_span_err(op_span,
3135                     "chained comparison operators require parentheses");
3136                 if op.node == BinOpKind::Lt && *outer_op == AssocOp::Greater {
3137                     err.fileline_help(op_span,
3138                         "use `::<...>` instead of `<...>` if you meant to specify type arguments");
3139                 }
3140                 err.emit();
3141             }
3142             _ => {}
3143         }
3144     }
3145
3146     /// Parse prefix-forms of range notation: `..expr`, `..`, `...expr`
3147     fn parse_prefix_range_expr(&mut self,
3148                                already_parsed_attrs: Option<ThinAttributes>)
3149                                -> PResult<'a, P<Expr>> {
3150         debug_assert!(self.token == token::DotDot || self.token == token::DotDotDot);
3151         let tok = self.token.clone();
3152         let attrs = self.parse_or_use_outer_attributes(already_parsed_attrs)?;
3153         let lo = self.span.lo;
3154         let mut hi = self.span.hi;
3155         self.bump();
3156         let opt_end = if self.is_at_start_of_range_notation_rhs() {
3157             // RHS must be parsed with more associativity than the dots.
3158             let next_prec = AssocOp::from_token(&tok).unwrap().precedence() + 1;
3159             Some(self.parse_assoc_expr_with(next_prec,
3160                                             LhsExpr::NotYetParsed)
3161                 .map(|x|{
3162                     hi = x.span.hi;
3163                     x
3164                 })?)
3165          } else {
3166             None
3167         };
3168         let limits = if tok == token::DotDot {
3169             RangeLimits::HalfOpen
3170         } else {
3171             RangeLimits::Closed
3172         };
3173
3174         let r = try!(self.mk_range(None,
3175                                    opt_end,
3176                                    limits));
3177         Ok(self.mk_expr(lo, hi, r, attrs))
3178     }
3179
3180     fn is_at_start_of_range_notation_rhs(&self) -> bool {
3181         if self.token.can_begin_expr() {
3182             // parse `for i in 1.. { }` as infinite loop, not as `for i in (1..{})`.
3183             if self.token == token::OpenDelim(token::Brace) {
3184                 return !self.restrictions.contains(Restrictions::RESTRICTION_NO_STRUCT_LITERAL);
3185             }
3186             true
3187         } else {
3188             false
3189         }
3190     }
3191
3192     /// Parse an 'if' or 'if let' expression ('if' token already eaten)
3193     pub fn parse_if_expr(&mut self, attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3194         if self.check_keyword(keywords::Let) {
3195             return self.parse_if_let_expr(attrs);
3196         }
3197         let lo = self.last_span.lo;
3198         let cond = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL, None)?;
3199         let thn = self.parse_block()?;
3200         let mut els: Option<P<Expr>> = None;
3201         let mut hi = thn.span.hi;
3202         if self.eat_keyword(keywords::Else) {
3203             let elexpr = self.parse_else_expr()?;
3204             hi = elexpr.span.hi;
3205             els = Some(elexpr);
3206         }
3207         Ok(self.mk_expr(lo, hi, ExprKind::If(cond, thn, els), attrs))
3208     }
3209
3210     /// Parse an 'if let' expression ('if' token already eaten)
3211     pub fn parse_if_let_expr(&mut self, attrs: ThinAttributes)
3212                              -> PResult<'a, P<Expr>> {
3213         let lo = self.last_span.lo;
3214         self.expect_keyword(keywords::Let)?;
3215         let pat = self.parse_pat()?;
3216         self.expect(&token::Eq)?;
3217         let expr = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL, None)?;
3218         let thn = self.parse_block()?;
3219         let (hi, els) = if self.eat_keyword(keywords::Else) {
3220             let expr = self.parse_else_expr()?;
3221             (expr.span.hi, Some(expr))
3222         } else {
3223             (thn.span.hi, None)
3224         };
3225         Ok(self.mk_expr(lo, hi, ExprKind::IfLet(pat, expr, thn, els), attrs))
3226     }
3227
3228     // `|args| expr`
3229     pub fn parse_lambda_expr(&mut self, lo: BytePos,
3230                              capture_clause: CaptureBy,
3231                              attrs: ThinAttributes)
3232                              -> PResult<'a, P<Expr>>
3233     {
3234         let decl = self.parse_fn_block_decl()?;
3235         let body = match decl.output {
3236             FunctionRetTy::Default(_) => {
3237                 // If no explicit return type is given, parse any
3238                 // expr and wrap it up in a dummy block:
3239                 let body_expr = self.parse_expr()?;
3240                 P(ast::Block {
3241                     id: ast::DUMMY_NODE_ID,
3242                     stmts: vec![],
3243                     span: body_expr.span,
3244                     expr: Some(body_expr),
3245                     rules: BlockCheckMode::Default,
3246                 })
3247             }
3248             _ => {
3249                 // If an explicit return type is given, require a
3250                 // block to appear (RFC 968).
3251                 self.parse_block()?
3252             }
3253         };
3254
3255         Ok(self.mk_expr(
3256             lo,
3257             body.span.hi,
3258             ExprKind::Closure(capture_clause, decl, body), attrs))
3259     }
3260
3261     // `else` token already eaten
3262     pub fn parse_else_expr(&mut self) -> PResult<'a, P<Expr>> {
3263         if self.eat_keyword(keywords::If) {
3264             return self.parse_if_expr(None);
3265         } else {
3266             let blk = self.parse_block()?;
3267             return Ok(self.mk_expr(blk.span.lo, blk.span.hi, ExprKind::Block(blk), None));
3268         }
3269     }
3270
3271     /// Parse a 'for' .. 'in' expression ('for' token already eaten)
3272     pub fn parse_for_expr(&mut self, opt_ident: Option<ast::Ident>,
3273                           span_lo: BytePos,
3274                           attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3275         // Parse: `for <src_pat> in <src_expr> <src_loop_block>`
3276
3277         let pat = self.parse_pat()?;
3278         self.expect_keyword(keywords::In)?;
3279         let expr = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL, None)?;
3280         let (iattrs, loop_block) = self.parse_inner_attrs_and_block()?;
3281         let attrs = attrs.append(iattrs.into_thin_attrs());
3282
3283         let hi = self.last_span.hi;
3284
3285         Ok(self.mk_expr(span_lo, hi,
3286                         ExprKind::ForLoop(pat, expr, loop_block, opt_ident),
3287                         attrs))
3288     }
3289
3290     /// Parse a 'while' or 'while let' expression ('while' token already eaten)
3291     pub fn parse_while_expr(&mut self, opt_ident: Option<ast::Ident>,
3292                             span_lo: BytePos,
3293                             attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3294         if self.token.is_keyword(keywords::Let) {
3295             return self.parse_while_let_expr(opt_ident, span_lo, attrs);
3296         }
3297         let cond = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL, None)?;
3298         let (iattrs, body) = self.parse_inner_attrs_and_block()?;
3299         let attrs = attrs.append(iattrs.into_thin_attrs());
3300         let hi = body.span.hi;
3301         return Ok(self.mk_expr(span_lo, hi, ExprKind::While(cond, body, opt_ident),
3302                                attrs));
3303     }
3304
3305     /// Parse a 'while let' expression ('while' token already eaten)
3306     pub fn parse_while_let_expr(&mut self, opt_ident: Option<ast::Ident>,
3307                                 span_lo: BytePos,
3308                                 attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3309         self.expect_keyword(keywords::Let)?;
3310         let pat = self.parse_pat()?;
3311         self.expect(&token::Eq)?;
3312         let expr = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL, None)?;
3313         let (iattrs, body) = self.parse_inner_attrs_and_block()?;
3314         let attrs = attrs.append(iattrs.into_thin_attrs());
3315         let hi = body.span.hi;
3316         return Ok(self.mk_expr(span_lo, hi, ExprKind::WhileLet(pat, expr, body, opt_ident), attrs));
3317     }
3318
3319     // parse `loop {...}`, `loop` token already eaten
3320     pub fn parse_loop_expr(&mut self, opt_ident: Option<ast::Ident>,
3321                            span_lo: BytePos,
3322                            attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3323         let (iattrs, body) = self.parse_inner_attrs_and_block()?;
3324         let attrs = attrs.append(iattrs.into_thin_attrs());
3325         let hi = body.span.hi;
3326         Ok(self.mk_expr(span_lo, hi, ExprKind::Loop(body, opt_ident), attrs))
3327     }
3328
3329     // `match` token already eaten
3330     fn parse_match_expr(&mut self, attrs: ThinAttributes) -> PResult<'a, P<Expr>> {
3331         let match_span = self.last_span;
3332         let lo = self.last_span.lo;
3333         let discriminant = self.parse_expr_res(Restrictions::RESTRICTION_NO_STRUCT_LITERAL,
3334                                                None)?;
3335         if let Err(mut e) = self.commit_expr_expecting(&discriminant,
3336                                                        token::OpenDelim(token::Brace)) {
3337             if self.token == token::Token::Semi {
3338                 e.span_note(match_span, "did you mean to remove this `match` keyword?");
3339             }
3340             return Err(e)
3341         }
3342         let attrs = attrs.append(
3343             self.parse_inner_attributes()?.into_thin_attrs());
3344         let mut arms: Vec<Arm> = Vec::new();
3345         while self.token != token::CloseDelim(token::Brace) {
3346             match self.parse_arm() {
3347                 Ok(arm) => arms.push(arm),
3348                 Err(mut e) => {
3349                     // Recover by skipping to the end of the block.
3350                     e.emit();
3351                     self.recover_stmt();
3352                     let hi = self.span.hi;
3353                     if self.token == token::CloseDelim(token::Brace) {
3354                         self.bump();
3355                     }
3356                     return Ok(self.mk_expr(lo, hi, ExprKind::Match(discriminant, arms), attrs));
3357                 }
3358             }
3359         }
3360         let hi = self.span.hi;
3361         self.bump();
3362         return Ok(self.mk_expr(lo, hi, ExprKind::Match(discriminant, arms), attrs));
3363     }
3364
3365     pub fn parse_arm(&mut self) -> PResult<'a, Arm> {
3366         maybe_whole!(no_clone self, NtArm);
3367
3368         let attrs = self.parse_outer_attributes()?;
3369         let pats = self.parse_pats()?;
3370         let mut guard = None;
3371         if self.eat_keyword(keywords::If) {
3372             guard = Some(self.parse_expr()?);
3373         }
3374         self.expect(&token::FatArrow)?;
3375         let expr = self.parse_expr_res(Restrictions::RESTRICTION_STMT_EXPR, None)?;
3376
3377         let require_comma =
3378             !classify::expr_is_simple_block(&expr)
3379             && self.token != token::CloseDelim(token::Brace);
3380
3381         if require_comma {
3382             self.commit_expr(&expr, &[token::Comma], &[token::CloseDelim(token::Brace)])?;
3383         } else {
3384             self.eat(&token::Comma);
3385         }
3386
3387         Ok(ast::Arm {
3388             attrs: attrs,
3389             pats: pats,
3390             guard: guard,
3391             body: expr,
3392         })
3393     }
3394
3395     /// Parse an expression
3396     pub fn parse_expr(&mut self) -> PResult<'a, P<Expr>> {
3397         self.parse_expr_res(Restrictions::empty(), None)
3398     }
3399
3400     /// Evaluate the closure with restrictions in place.
3401     ///
3402     /// After the closure is evaluated, restrictions are reset.
3403     pub fn with_res<F, T>(&mut self, r: Restrictions, f: F) -> T
3404         where F: FnOnce(&mut Self) -> T
3405     {
3406         let old = self.restrictions;
3407         self.restrictions = r;
3408         let r = f(self);
3409         self.restrictions = old;
3410         return r;
3411
3412     }
3413
3414     /// Parse an expression, subject to the given restrictions
3415     pub fn parse_expr_res(&mut self, r: Restrictions,
3416                           already_parsed_attrs: Option<ThinAttributes>)
3417                           -> PResult<'a, P<Expr>> {
3418         self.with_res(r, |this| this.parse_assoc_expr(already_parsed_attrs))
3419     }
3420
3421     /// Parse the RHS of a local variable declaration (e.g. '= 14;')
3422     fn parse_initializer(&mut self) -> PResult<'a, Option<P<Expr>>> {
3423         if self.check(&token::Eq) {
3424             self.bump();
3425             Ok(Some(self.parse_expr()?))
3426         } else {
3427             Ok(None)
3428         }
3429     }
3430
3431     /// Parse patterns, separated by '|' s
3432     fn parse_pats(&mut self) -> PResult<'a, Vec<P<Pat>>> {
3433         let mut pats = Vec::new();
3434         loop {
3435             pats.push(self.parse_pat()?);
3436             if self.check(&token::BinOp(token::Or)) { self.bump();}
3437             else { return Ok(pats); }
3438         };
3439     }
3440
3441     fn parse_pat_tuple_elements(&mut self) -> PResult<'a, Vec<P<Pat>>> {
3442         let mut fields = vec![];
3443         if !self.check(&token::CloseDelim(token::Paren)) {
3444             fields.push(self.parse_pat()?);
3445             if self.look_ahead(1, |t| *t != token::CloseDelim(token::Paren)) {
3446                 while self.eat(&token::Comma) &&
3447                       !self.check(&token::CloseDelim(token::Paren)) {
3448                     fields.push(self.parse_pat()?);
3449                 }
3450             }
3451             if fields.len() == 1 {
3452                 self.expect(&token::Comma)?;
3453             }
3454         }
3455         Ok(fields)
3456     }
3457
3458     fn parse_pat_vec_elements(
3459         &mut self,
3460     ) -> PResult<'a, (Vec<P<Pat>>, Option<P<Pat>>, Vec<P<Pat>>)> {
3461         let mut before = Vec::new();
3462         let mut slice = None;
3463         let mut after = Vec::new();
3464         let mut first = true;
3465         let mut before_slice = true;
3466
3467         while self.token != token::CloseDelim(token::Bracket) {
3468             if first {
3469                 first = false;
3470             } else {
3471                 self.expect(&token::Comma)?;
3472
3473                 if self.token == token::CloseDelim(token::Bracket)
3474                         && (before_slice || !after.is_empty()) {
3475                     break
3476                 }
3477             }
3478
3479             if before_slice {
3480                 if self.check(&token::DotDot) {
3481                     self.bump();
3482
3483                     if self.check(&token::Comma) ||
3484                             self.check(&token::CloseDelim(token::Bracket)) {
3485                         slice = Some(P(ast::Pat {
3486                             id: ast::DUMMY_NODE_ID,
3487                             node: PatKind::Wild,
3488                             span: self.span,
3489                         }));
3490                         before_slice = false;
3491                     }
3492                     continue
3493                 }
3494             }
3495
3496             let subpat = self.parse_pat()?;
3497             if before_slice && self.check(&token::DotDot) {
3498                 self.bump();
3499                 slice = Some(subpat);
3500                 before_slice = false;
3501             } else if before_slice {
3502                 before.push(subpat);
3503             } else {
3504                 after.push(subpat);
3505             }
3506         }
3507
3508         Ok((before, slice, after))
3509     }
3510
3511     /// Parse the fields of a struct-like pattern
3512     fn parse_pat_fields(&mut self) -> PResult<'a, (Vec<codemap::Spanned<ast::FieldPat>> , bool)> {
3513         let mut fields = Vec::new();
3514         let mut etc = false;
3515         let mut first = true;
3516         while self.token != token::CloseDelim(token::Brace) {
3517             if first {
3518                 first = false;
3519             } else {
3520                 self.expect(&token::Comma)?;
3521                 // accept trailing commas
3522                 if self.check(&token::CloseDelim(token::Brace)) { break }
3523             }
3524
3525             let lo = self.span.lo;
3526             let hi;
3527
3528             if self.check(&token::DotDot) {
3529                 self.bump();
3530                 if self.token != token::CloseDelim(token::Brace) {
3531                     let token_str = self.this_token_to_string();
3532                     return Err(self.fatal(&format!("expected `{}`, found `{}`", "}",
3533                                        token_str)))
3534                 }
3535                 etc = true;
3536                 break;
3537             }
3538
3539             // Check if a colon exists one ahead. This means we're parsing a fieldname.
3540             let (subpat, fieldname, is_shorthand) = if self.look_ahead(1, |t| t == &token::Colon) {
3541                 // Parsing a pattern of the form "fieldname: pat"
3542                 let fieldname = self.parse_ident()?;
3543                 self.bump();
3544                 let pat = self.parse_pat()?;
3545                 hi = pat.span.hi;
3546                 (pat, fieldname, false)
3547             } else {
3548                 // Parsing a pattern of the form "(box) (ref) (mut) fieldname"
3549                 let is_box = self.eat_keyword(keywords::Box);
3550                 let boxed_span_lo = self.span.lo;
3551                 let is_ref = self.eat_keyword(keywords::Ref);
3552                 let is_mut = self.eat_keyword(keywords::Mut);
3553                 let fieldname = self.parse_ident()?;
3554                 hi = self.last_span.hi;
3555
3556                 let bind_type = match (is_ref, is_mut) {
3557                     (true, true) => BindingMode::ByRef(Mutability::Mutable),
3558                     (true, false) => BindingMode::ByRef(Mutability::Immutable),
3559                     (false, true) => BindingMode::ByValue(Mutability::Mutable),
3560                     (false, false) => BindingMode::ByValue(Mutability::Immutable),
3561                 };
3562                 let fieldpath = codemap::Spanned{span:self.last_span, node:fieldname};
3563                 let fieldpat = P(ast::Pat{
3564                     id: ast::DUMMY_NODE_ID,
3565                     node: PatKind::Ident(bind_type, fieldpath, None),
3566                     span: mk_sp(boxed_span_lo, hi),
3567                 });
3568
3569                 let subpat = if is_box {
3570                     P(ast::Pat{
3571                         id: ast::DUMMY_NODE_ID,
3572                         node: PatKind::Box(fieldpat),
3573                         span: mk_sp(lo, hi),
3574                     })
3575                 } else {
3576                     fieldpat
3577                 };
3578                 (subpat, fieldname, true)
3579             };
3580
3581             fields.push(codemap::Spanned { span: mk_sp(lo, hi),
3582                                            node: ast::FieldPat { ident: fieldname,
3583                                                                  pat: subpat,
3584                                                                  is_shorthand: is_shorthand }});
3585         }
3586         return Ok((fields, etc));
3587     }
3588
3589     fn parse_pat_range_end(&mut self) -> PResult<'a, P<Expr>> {
3590         if self.is_path_start() {
3591             let lo = self.span.lo;
3592             let (qself, path) = if self.eat_lt() {
3593                 // Parse a qualified path
3594                 let (qself, path) =
3595                     self.parse_qualified_path(NoTypesAllowed)?;
3596                 (Some(qself), path)
3597             } else {
3598                 // Parse an unqualified path
3599                 (None, self.parse_path(LifetimeAndTypesWithColons)?)
3600             };
3601             let hi = self.last_span.hi;
3602             Ok(self.mk_expr(lo, hi, ExprKind::Path(qself, path), None))
3603         } else {
3604             self.parse_pat_literal_maybe_minus()
3605         }
3606     }
3607
3608     fn is_path_start(&self) -> bool {
3609         (self.token == token::Lt || self.token == token::ModSep
3610             || self.token.is_ident() || self.token.is_path())
3611             && !self.token.is_keyword(keywords::True) && !self.token.is_keyword(keywords::False)
3612     }
3613
3614     /// Parse a pattern.
3615     pub fn parse_pat(&mut self) -> PResult<'a, P<Pat>> {
3616         maybe_whole!(self, NtPat);
3617
3618         let lo = self.span.lo;
3619         let pat;
3620         match self.token {
3621           token::Underscore => {
3622             // Parse _
3623             self.bump();
3624             pat = PatKind::Wild;
3625           }
3626           token::BinOp(token::And) | token::AndAnd => {
3627             // Parse &pat / &mut pat
3628             self.expect_and()?;
3629             let mutbl = self.parse_mutability()?;
3630             if let token::Lifetime(ident) = self.token {
3631                 return Err(self.fatal(&format!("unexpected lifetime `{}` in pattern", ident)));
3632             }
3633
3634             let subpat = self.parse_pat()?;
3635             pat = PatKind::Ref(subpat, mutbl);
3636           }
3637           token::OpenDelim(token::Paren) => {
3638             // Parse (pat,pat,pat,...) as tuple pattern
3639             self.bump();
3640             let fields = self.parse_pat_tuple_elements()?;
3641             self.expect(&token::CloseDelim(token::Paren))?;
3642             pat = PatKind::Tup(fields);
3643           }
3644           token::OpenDelim(token::Bracket) => {
3645             // Parse [pat,pat,...] as slice pattern
3646             self.bump();
3647             let (before, slice, after) = self.parse_pat_vec_elements()?;
3648             self.expect(&token::CloseDelim(token::Bracket))?;
3649             pat = PatKind::Vec(before, slice, after);
3650           }
3651           _ => {
3652             // At this point, token != _, &, &&, (, [
3653             if self.eat_keyword(keywords::Mut) {
3654                 // Parse mut ident @ pat
3655                 pat = self.parse_pat_ident(BindingMode::ByValue(Mutability::Mutable))?;
3656             } else if self.eat_keyword(keywords::Ref) {
3657                 // Parse ref ident @ pat / ref mut ident @ pat
3658                 let mutbl = self.parse_mutability()?;
3659                 pat = self.parse_pat_ident(BindingMode::ByRef(mutbl))?;
3660             } else if self.eat_keyword(keywords::Box) {
3661                 // Parse box pat
3662                 let subpat = self.parse_pat()?;
3663                 pat = PatKind::Box(subpat);
3664             } else if self.is_path_start() {
3665                 // Parse pattern starting with a path
3666                 if self.token.is_plain_ident() && self.look_ahead(1, |t| *t != token::DotDotDot &&
3667                         *t != token::OpenDelim(token::Brace) &&
3668                         *t != token::OpenDelim(token::Paren) &&
3669                         // Contrary to its definition, a plain ident can be followed by :: in macros
3670                         *t != token::ModSep) {
3671                     // Plain idents have some extra abilities here compared to general paths
3672                     if self.look_ahead(1, |t| *t == token::Not) {
3673                         // Parse macro invocation
3674                         let ident = self.parse_ident()?;
3675                         let ident_span = self.last_span;
3676                         let path = ast::Path::from_ident(ident_span, ident);
3677                         self.bump();
3678                         let delim = self.expect_open_delim()?;
3679                         let tts = self.parse_seq_to_end(
3680                             &token::CloseDelim(delim),
3681                             SeqSep::none(), |p| p.parse_token_tree())?;
3682                         let mac = Mac_ { path: path, tts: tts, ctxt: EMPTY_CTXT };
3683                         pat = PatKind::Mac(codemap::Spanned {node: mac,
3684                                                        span: mk_sp(lo, self.last_span.hi)});
3685                     } else {
3686                         // Parse ident @ pat
3687                         // This can give false positives and parse nullary enums,
3688                         // they are dealt with later in resolve
3689                         let binding_mode = BindingMode::ByValue(Mutability::Immutable);
3690                         pat = self.parse_pat_ident(binding_mode)?;
3691                     }
3692                 } else {
3693                     let (qself, path) = if self.eat_lt() {
3694                         // Parse a qualified path
3695                         let (qself, path) =
3696                             self.parse_qualified_path(NoTypesAllowed)?;
3697                         (Some(qself), path)
3698                     } else {
3699                         // Parse an unqualified path
3700                         (None, self.parse_path(LifetimeAndTypesWithColons)?)
3701                     };
3702                     match self.token {
3703                       token::DotDotDot => {
3704                         // Parse range
3705                         let hi = self.last_span.hi;
3706                         let begin = self.mk_expr(lo, hi, ExprKind::Path(qself, path), None);
3707                         self.bump();
3708                         let end = self.parse_pat_range_end()?;
3709                         pat = PatKind::Range(begin, end);
3710                       }
3711                       token::OpenDelim(token::Brace) => {
3712                          if qself.is_some() {
3713                             return Err(self.fatal("unexpected `{` after qualified path"));
3714                         }
3715                         // Parse struct pattern
3716                         self.bump();
3717                         let (fields, etc) = self.parse_pat_fields().unwrap_or_else(|mut e| {
3718                             e.emit();
3719                             self.recover_stmt();
3720                             (vec![], false)
3721                         });
3722                         self.bump();
3723                         pat = PatKind::Struct(path, fields, etc);
3724                       }
3725                       token::OpenDelim(token::Paren) => {
3726                         if qself.is_some() {
3727                             return Err(self.fatal("unexpected `(` after qualified path"));
3728                         }
3729                         // Parse tuple struct or enum pattern
3730                         if self.look_ahead(1, |t| *t == token::DotDot) {
3731                             // This is a "top constructor only" pat
3732                             self.bump();
3733                             self.bump();
3734                             self.expect(&token::CloseDelim(token::Paren))?;
3735                             pat = PatKind::TupleStruct(path, None);
3736                         } else {
3737                             let args = self.parse_enum_variant_seq(
3738                                 &token::OpenDelim(token::Paren),
3739                                 &token::CloseDelim(token::Paren),
3740                                 SeqSep::trailing_allowed(token::Comma),
3741                                 |p| p.parse_pat())?;
3742                             pat = PatKind::TupleStruct(path, Some(args));
3743                         }
3744                       }
3745                       _ => {
3746                         pat = match qself {
3747                             // Parse qualified path
3748                             Some(qself) => PatKind::QPath(qself, path),
3749                             // Parse nullary enum
3750                             None => PatKind::Path(path)
3751                         };
3752                       }
3753                     }
3754                 }
3755             } else {
3756                 // Try to parse everything else as literal with optional minus
3757                 let begin = self.parse_pat_literal_maybe_minus()?;
3758                 if self.eat(&token::DotDotDot) {
3759                     let end = self.parse_pat_range_end()?;
3760                     pat = PatKind::Range(begin, end);
3761                 } else {
3762                     pat = PatKind::Lit(begin);
3763                 }
3764             }
3765           }
3766         }
3767
3768         let hi = self.last_span.hi;
3769         Ok(P(ast::Pat {
3770             id: ast::DUMMY_NODE_ID,
3771             node: pat,
3772             span: mk_sp(lo, hi),
3773         }))
3774     }
3775
3776     /// Parse ident or ident @ pat
3777     /// used by the copy foo and ref foo patterns to give a good
3778     /// error message when parsing mistakes like ref foo(a,b)
3779     fn parse_pat_ident(&mut self,
3780                        binding_mode: ast::BindingMode)
3781                        -> PResult<'a, PatKind> {
3782         let ident = self.parse_ident()?;
3783         let last_span = self.last_span;
3784         let name = codemap::Spanned{span: last_span, node: ident};
3785         let sub = if self.eat(&token::At) {
3786             Some(self.parse_pat()?)
3787         } else {
3788             None
3789         };
3790
3791         // just to be friendly, if they write something like
3792         //   ref Some(i)
3793         // we end up here with ( as the current token.  This shortly
3794         // leads to a parse error.  Note that if there is no explicit
3795         // binding mode then we do not end up here, because the lookahead
3796         // will direct us over to parse_enum_variant()
3797         if self.token == token::OpenDelim(token::Paren) {
3798             let last_span = self.last_span;
3799             return Err(self.span_fatal(
3800                 last_span,
3801                 "expected identifier, found enum pattern"))
3802         }
3803
3804         Ok(PatKind::Ident(binding_mode, name, sub))
3805     }
3806
3807     /// Parse a local variable declaration
3808     fn parse_local(&mut self, attrs: ThinAttributes) -> PResult<'a, P<Local>> {
3809         let lo = self.span.lo;
3810         let pat = self.parse_pat()?;
3811
3812         let mut ty = None;
3813         if self.eat(&token::Colon) {
3814             ty = Some(self.parse_ty_sum()?);
3815         }
3816         let init = self.parse_initializer()?;
3817         Ok(P(ast::Local {
3818             ty: ty,
3819             pat: pat,
3820             init: init,
3821             id: ast::DUMMY_NODE_ID,
3822             span: mk_sp(lo, self.last_span.hi),
3823             attrs: attrs,
3824         }))
3825     }
3826
3827     /// Parse a "let" stmt
3828     fn parse_let(&mut self, attrs: ThinAttributes) -> PResult<'a, P<Decl>> {
3829         let lo = self.span.lo;
3830         let local = self.parse_local(attrs)?;
3831         Ok(P(spanned(lo, self.last_span.hi, DeclKind::Local(local))))
3832     }
3833
3834     /// Parse a structure field
3835     fn parse_name_and_ty(&mut self, pr: Visibility,
3836                          attrs: Vec<Attribute> ) -> PResult<'a, StructField> {
3837         let lo = match pr {
3838             Visibility::Inherited => self.span.lo,
3839             _ => self.last_span.lo,
3840         };
3841         let name = self.parse_ident()?;
3842         self.expect(&token::Colon)?;
3843         let ty = self.parse_ty_sum()?;
3844         Ok(StructField {
3845             span: mk_sp(lo, self.last_span.hi),
3846             ident: Some(name),
3847             vis: pr,
3848             id: ast::DUMMY_NODE_ID,
3849             ty: ty,
3850             attrs: attrs,
3851         })
3852     }
3853
3854     /// Emit an expected item after attributes error.
3855     fn expected_item_err(&self, attrs: &[Attribute]) {
3856         let message = match attrs.last() {
3857             Some(&Attribute { node: ast::Attribute_ { is_sugared_doc: true, .. }, .. }) => {
3858                 "expected item after doc comment"
3859             }
3860             _ => "expected item after attributes",
3861         };
3862
3863         self.span_err(self.last_span, message);
3864     }
3865
3866     /// Parse a statement. may include decl.
3867     pub fn parse_stmt(&mut self) -> PResult<'a, Option<Stmt>> {
3868         Ok(self.parse_stmt_())
3869     }
3870
3871     // Eat tokens until we can be relatively sure we reached the end of the
3872     // statement. This is something of a best-effort heuristic.
3873     //
3874     // We terminate when we find an unmatched `}` (without consuming it).
3875     fn recover_stmt(&mut self) {
3876         self.recover_stmt_(SemiColonMode::Ignore)
3877     }
3878     // If `break_on_semi` is `Break`, then we will stop consuming tokens after
3879     // finding (and consuming) a `;` outside of `{}` or `[]` (note that this is
3880     // approximate - it can mean we break too early due to macros, but that
3881     // shoud only lead to sub-optimal recovery, not inaccurate parsing).
3882     fn recover_stmt_(&mut self, break_on_semi: SemiColonMode) {
3883         let mut brace_depth = 0;
3884         let mut bracket_depth = 0;
3885         debug!("recover_stmt_ enter loop");
3886         loop {
3887             debug!("recover_stmt_ loop {:?}", self.token);
3888             match self.token {
3889                 token::OpenDelim(token::DelimToken::Brace) => {
3890                     brace_depth += 1;
3891                     self.bump();
3892                 }
3893                 token::OpenDelim(token::DelimToken::Bracket) => {
3894                     bracket_depth += 1;
3895                     self.bump();
3896                 }
3897                 token::CloseDelim(token::DelimToken::Brace) => {
3898                     if brace_depth == 0 {
3899                         debug!("recover_stmt_ return - close delim {:?}", self.token);
3900                         return;
3901                     }
3902                     brace_depth -= 1;
3903                     self.bump();
3904                 }
3905                 token::CloseDelim(token::DelimToken::Bracket) => {
3906                     bracket_depth -= 1;
3907                     if bracket_depth < 0 {
3908                         bracket_depth = 0;
3909                     }
3910                     self.bump();
3911                 }
3912                 token::Eof => {
3913                     debug!("recover_stmt_ return - Eof");
3914                     return;
3915                 }
3916                 token::Semi => {
3917                     self.bump();
3918                     if break_on_semi == SemiColonMode::Break &&
3919                        brace_depth == 0 &&
3920                        bracket_depth == 0 {
3921                         debug!("recover_stmt_ return - Semi");
3922                         return;
3923                     }
3924                 }
3925                 _ => {
3926                     self.bump()
3927                 }
3928             }
3929         }
3930     }
3931
3932     fn parse_stmt_(&mut self) -> Option<Stmt> {
3933         self.parse_stmt_without_recovery().unwrap_or_else(|mut e| {
3934             e.emit();
3935             self.recover_stmt_(SemiColonMode::Break);
3936             None
3937         })
3938     }
3939
3940     fn parse_stmt_without_recovery(&mut self) -> PResult<'a, Option<Stmt>> {
3941         maybe_whole!(Some deref self, NtStmt);
3942
3943         let attrs = self.parse_outer_attributes()?;
3944         let lo = self.span.lo;
3945
3946         Ok(Some(if self.check_keyword(keywords::Let) {
3947             self.expect_keyword(keywords::Let)?;
3948             let decl = self.parse_let(attrs.into_thin_attrs())?;
3949             let hi = decl.span.hi;
3950             let stmt = StmtKind::Decl(decl, ast::DUMMY_NODE_ID);
3951             spanned(lo, hi, stmt)
3952         } else if self.token.is_ident()
3953             && !self.token.is_any_keyword()
3954             && self.look_ahead(1, |t| *t == token::Not) {
3955             // it's a macro invocation:
3956
3957             // Potential trouble: if we allow macros with paths instead of
3958             // idents, we'd need to look ahead past the whole path here...
3959             let pth = self.parse_path(NoTypesAllowed)?;
3960             self.bump();
3961
3962             let id = match self.token {
3963                 token::OpenDelim(_) => token::special_idents::invalid, // no special identifier
3964                 _ => self.parse_ident()?,
3965             };
3966
3967             // check that we're pointing at delimiters (need to check
3968             // again after the `if`, because of `parse_ident`
3969             // consuming more tokens).
3970             let delim = match self.token {
3971                 token::OpenDelim(delim) => delim,
3972                 _ => {
3973                     // we only expect an ident if we didn't parse one
3974                     // above.
3975                     let ident_str = if id.name == token::special_idents::invalid.name {
3976                         "identifier, "
3977                     } else {
3978                         ""
3979                     };
3980                     let tok_str = self.this_token_to_string();
3981                     return Err(self.fatal(&format!("expected {}`(` or `{{`, found `{}`",
3982                                        ident_str,
3983                                        tok_str)))
3984                 },
3985             };
3986
3987             let tts = self.parse_unspanned_seq(
3988                 &token::OpenDelim(delim),
3989                 &token::CloseDelim(delim),
3990                 SeqSep::none(),
3991                 |p| p.parse_token_tree()
3992             )?;
3993             let hi = self.last_span.hi;
3994
3995             let style = if delim == token::Brace {
3996                 MacStmtStyle::Braces
3997             } else {
3998                 MacStmtStyle::NoBraces
3999             };
4000
4001             if id.name == token::special_idents::invalid.name {
4002                 let mac = P(spanned(lo, hi, Mac_ { path: pth, tts: tts, ctxt: EMPTY_CTXT }));
4003                 let stmt = StmtKind::Mac(mac, style, attrs.into_thin_attrs());
4004                 spanned(lo, hi, stmt)
4005             } else {
4006                 // if it has a special ident, it's definitely an item
4007                 //
4008                 // Require a semicolon or braces.
4009                 if style != MacStmtStyle::Braces {
4010                     if !self.eat(&token::Semi) {
4011                         let last_span = self.last_span;
4012                         self.span_err(last_span,
4013                                       "macros that expand to items must \
4014                                        either be surrounded with braces or \
4015                                        followed by a semicolon");
4016                     }
4017                 }
4018                 spanned(lo, hi, StmtKind::Decl(
4019                     P(spanned(lo, hi, DeclKind::Item(
4020                         self.mk_item(
4021                             lo, hi, id /*id is good here*/,
4022                             ItemKind::Mac(spanned(lo, hi,
4023                                             Mac_ { path: pth, tts: tts, ctxt: EMPTY_CTXT })),
4024                             Visibility::Inherited, attrs)))),
4025                     ast::DUMMY_NODE_ID))
4026             }
4027         } else {
4028             // FIXME: Bad copy of attrs
4029             let restrictions = self.restrictions | Restrictions::NO_NONINLINE_MOD;
4030             match self.with_res(restrictions,
4031                                 |this| this.parse_item_(attrs.clone(), false, true))? {
4032                 Some(i) => {
4033                     let hi = i.span.hi;
4034                     let decl = P(spanned(lo, hi, DeclKind::Item(i)));
4035                     spanned(lo, hi, StmtKind::Decl(decl, ast::DUMMY_NODE_ID))
4036                 }
4037                 None => {
4038                     let unused_attrs = |attrs: &[_], s: &mut Self| {
4039                         if attrs.len() > 0 {
4040                             s.span_err(s.span,
4041                                 "expected statement after outer attribute");
4042                         }
4043                     };
4044
4045                     // Do not attempt to parse an expression if we're done here.
4046                     if self.token == token::Semi {
4047                         unused_attrs(&attrs, self);
4048                         self.bump();
4049                         return Ok(None);
4050                     }
4051
4052                     if self.token == token::CloseDelim(token::Brace) {
4053                         unused_attrs(&attrs, self);
4054                         return Ok(None);
4055                     }
4056
4057                     // Remainder are line-expr stmts.
4058                     let e = self.parse_expr_res(
4059                         Restrictions::RESTRICTION_STMT_EXPR, Some(attrs.into_thin_attrs()))?;
4060                     let hi = e.span.hi;
4061                     let stmt = StmtKind::Expr(e, ast::DUMMY_NODE_ID);
4062                     spanned(lo, hi, stmt)
4063                 }
4064             }
4065         }))
4066     }
4067
4068     /// Is this expression a successfully-parsed statement?
4069     fn expr_is_complete(&mut self, e: &Expr) -> bool {
4070         self.restrictions.contains(Restrictions::RESTRICTION_STMT_EXPR) &&
4071             !classify::expr_requires_semi_to_be_stmt(e)
4072     }
4073
4074     /// Parse a block. No inner attrs are allowed.
4075     pub fn parse_block(&mut self) -> PResult<'a, P<Block>> {
4076         maybe_whole!(no_clone self, NtBlock);
4077
4078         let lo = self.span.lo;
4079
4080         if !self.eat(&token::OpenDelim(token::Brace)) {
4081             let sp = self.span;
4082             let tok = self.this_token_to_string();
4083             return Err(self.span_fatal_help(sp,
4084                                  &format!("expected `{{`, found `{}`", tok),
4085                                  "place this code inside a block"));
4086         }
4087
4088         self.parse_block_tail(lo, BlockCheckMode::Default)
4089     }
4090
4091     /// Parse a block. Inner attrs are allowed.
4092     fn parse_inner_attrs_and_block(&mut self) -> PResult<'a, (Vec<Attribute>, P<Block>)> {
4093         maybe_whole!(pair_empty self, NtBlock);
4094
4095         let lo = self.span.lo;
4096         self.expect(&token::OpenDelim(token::Brace))?;
4097         Ok((self.parse_inner_attributes()?,
4098             self.parse_block_tail(lo, BlockCheckMode::Default)?))
4099     }
4100
4101     /// Parse the rest of a block expression or function body
4102     /// Precondition: already parsed the '{'.
4103     fn parse_block_tail(&mut self, lo: BytePos, s: BlockCheckMode) -> PResult<'a, P<Block>> {
4104         let mut stmts = vec![];
4105         let mut expr = None;
4106
4107         while !self.eat(&token::CloseDelim(token::Brace)) {
4108             let Spanned {node, span} = if let Some(s) = self.parse_stmt_() {
4109                 s
4110             } else if self.token == token::Eof {
4111                 break;
4112             } else {
4113                 // Found only `;` or `}`.
4114                 continue;
4115             };
4116             match node {
4117                 StmtKind::Expr(e, _) => {
4118                     self.handle_expression_like_statement(e, span, &mut stmts, &mut expr)?;
4119                 }
4120                 StmtKind::Mac(mac, MacStmtStyle::NoBraces, attrs) => {
4121                     // statement macro without braces; might be an
4122                     // expr depending on whether a semicolon follows
4123                     match self.token {
4124                         token::Semi => {
4125                             stmts.push(Spanned {
4126                                 node: StmtKind::Mac(mac, MacStmtStyle::Semicolon, attrs),
4127                                 span: mk_sp(span.lo, self.span.hi),
4128                             });
4129                             self.bump();
4130                         }
4131                         _ => {
4132                             let e = self.mk_mac_expr(span.lo, span.hi,
4133                                                      mac.and_then(|m| m.node),
4134                                                      None);
4135                             let lo = e.span.lo;
4136                             let e = self.parse_dot_or_call_expr_with(e, lo, attrs)?;
4137                             let e = self.parse_assoc_expr_with(0, LhsExpr::AlreadyParsed(e))?;
4138                             self.handle_expression_like_statement(
4139                                 e,
4140                                 span,
4141                                 &mut stmts,
4142                                 &mut expr)?;
4143                         }
4144                     }
4145                 }
4146                 StmtKind::Mac(m, style, attrs) => {
4147                     // statement macro; might be an expr
4148                     match self.token {
4149                         token::Semi => {
4150                             stmts.push(Spanned {
4151                                 node: StmtKind::Mac(m, MacStmtStyle::Semicolon, attrs),
4152                                 span: mk_sp(span.lo, self.span.hi),
4153                             });
4154                             self.bump();
4155                         }
4156                         token::CloseDelim(token::Brace) => {
4157                             // if a block ends in `m!(arg)` without
4158                             // a `;`, it must be an expr
4159                             expr = Some(self.mk_mac_expr(span.lo, span.hi,
4160                                                          m.and_then(|x| x.node),
4161                                                          attrs));
4162                         }
4163                         _ => {
4164                             stmts.push(Spanned {
4165                                 node: StmtKind::Mac(m, style, attrs),
4166                                 span: span
4167                             });
4168                         }
4169                     }
4170                 }
4171                 _ => { // all other kinds of statements:
4172                     let mut hi = span.hi;
4173                     if classify::stmt_ends_with_semi(&node) {
4174                         self.commit_stmt_expecting(token::Semi)?;
4175                         hi = self.last_span.hi;
4176                     }
4177
4178                     stmts.push(Spanned {
4179                         node: node,
4180                         span: mk_sp(span.lo, hi)
4181                     });
4182                 }
4183             }
4184         }
4185
4186         Ok(P(ast::Block {
4187             stmts: stmts,
4188             expr: expr,
4189             id: ast::DUMMY_NODE_ID,
4190             rules: s,
4191             span: mk_sp(lo, self.last_span.hi),
4192         }))
4193     }
4194
4195     fn handle_expression_like_statement(&mut self,
4196                                         e: P<Expr>,
4197                                         span: Span,
4198                                         stmts: &mut Vec<Stmt>,
4199                                         last_block_expr: &mut Option<P<Expr>>)
4200                                         -> PResult<'a, ()> {
4201         // expression without semicolon
4202         if classify::expr_requires_semi_to_be_stmt(&e) {
4203             // Just check for errors and recover; do not eat semicolon yet.
4204             if let Err(mut e) =
4205                 self.commit_stmt(&[], &[token::Semi, token::CloseDelim(token::Brace)])
4206             {
4207                 e.emit();
4208                 self.recover_stmt();
4209             }
4210         }
4211
4212         match self.token {
4213             token::Semi => {
4214                 self.bump();
4215                 let span_with_semi = Span {
4216                     lo: span.lo,
4217                     hi: self.last_span.hi,
4218                     expn_id: span.expn_id,
4219                 };
4220                 stmts.push(Spanned {
4221                     node: StmtKind::Semi(e, ast::DUMMY_NODE_ID),
4222                     span: span_with_semi,
4223                 });
4224             }
4225             token::CloseDelim(token::Brace) => *last_block_expr = Some(e),
4226             _ => {
4227                 stmts.push(Spanned {
4228                     node: StmtKind::Expr(e, ast::DUMMY_NODE_ID),
4229                     span: span
4230                 });
4231             }
4232         }
4233         Ok(())
4234     }
4235
4236     // Parses a sequence of bounds if a `:` is found,
4237     // otherwise returns empty list.
4238     fn parse_colon_then_ty_param_bounds(&mut self,
4239                                         mode: BoundParsingMode)
4240                                         -> PResult<'a, TyParamBounds>
4241     {
4242         if !self.eat(&token::Colon) {
4243             Ok(P::empty())
4244         } else {
4245             self.parse_ty_param_bounds(mode)
4246         }
4247     }
4248
4249     // matches bounds    = ( boundseq )?
4250     // where   boundseq  = ( polybound + boundseq ) | polybound
4251     // and     polybound = ( 'for' '<' 'region '>' )? bound
4252     // and     bound     = 'region | trait_ref
4253     fn parse_ty_param_bounds(&mut self,
4254                              mode: BoundParsingMode)
4255                              -> PResult<'a, TyParamBounds>
4256     {
4257         let mut result = vec!();
4258         loop {
4259             let question_span = self.span;
4260             let ate_question = self.eat(&token::Question);
4261             match self.token {
4262                 token::Lifetime(lifetime) => {
4263                     if ate_question {
4264                         self.span_err(question_span,
4265                                       "`?` may only modify trait bounds, not lifetime bounds");
4266                     }
4267                     result.push(RegionTyParamBound(ast::Lifetime {
4268                         id: ast::DUMMY_NODE_ID,
4269                         span: self.span,
4270                         name: lifetime.name
4271                     }));
4272                     self.bump();
4273                 }
4274                 token::ModSep | token::Ident(..) => {
4275                     let poly_trait_ref = self.parse_poly_trait_ref()?;
4276                     let modifier = if ate_question {
4277                         if mode == BoundParsingMode::Modified {
4278                             TraitBoundModifier::Maybe
4279                         } else {
4280                             self.span_err(question_span,
4281                                           "unexpected `?`");
4282                             TraitBoundModifier::None
4283                         }
4284                     } else {
4285                         TraitBoundModifier::None
4286                     };
4287                     result.push(TraitTyParamBound(poly_trait_ref, modifier))
4288                 }
4289                 _ => break,
4290             }
4291
4292             if !self.eat(&token::BinOp(token::Plus)) {
4293                 break;
4294             }
4295         }
4296
4297         return Ok(P::from_vec(result));
4298     }
4299
4300     /// Matches typaram = IDENT (`?` unbound)? optbounds ( EQ ty )?
4301     fn parse_ty_param(&mut self) -> PResult<'a, TyParam> {
4302         let span = self.span;
4303         let ident = self.parse_ident()?;
4304
4305         let bounds = self.parse_colon_then_ty_param_bounds(BoundParsingMode::Modified)?;
4306
4307         let default = if self.check(&token::Eq) {
4308             self.bump();
4309             Some(self.parse_ty_sum()?)
4310         } else {
4311             None
4312         };
4313
4314         Ok(TyParam {
4315             ident: ident,
4316             id: ast::DUMMY_NODE_ID,
4317             bounds: bounds,
4318             default: default,
4319             span: span,
4320         })
4321     }
4322
4323     /// Parse a set of optional generic type parameter declarations. Where
4324     /// clauses are not parsed here, and must be added later via
4325     /// `parse_where_clause()`.
4326     ///
4327     /// matches generics = ( ) | ( < > ) | ( < typaramseq ( , )? > ) | ( < lifetimes ( , )? > )
4328     ///                  | ( < lifetimes , typaramseq ( , )? > )
4329     /// where   typaramseq = ( typaram ) | ( typaram , typaramseq )
4330     pub fn parse_generics(&mut self) -> PResult<'a, ast::Generics> {
4331         maybe_whole!(self, NtGenerics);
4332
4333         if self.eat(&token::Lt) {
4334             let lifetime_defs = self.parse_lifetime_defs()?;
4335             let mut seen_default = false;
4336             let ty_params = self.parse_seq_to_gt(Some(token::Comma), |p| {
4337                 p.forbid_lifetime()?;
4338                 let ty_param = p.parse_ty_param()?;
4339                 if ty_param.default.is_some() {
4340                     seen_default = true;
4341                 } else if seen_default {
4342                     let last_span = p.last_span;
4343                     p.span_err(last_span,
4344                                "type parameters with a default must be trailing");
4345                 }
4346                 Ok(ty_param)
4347             })?;
4348             Ok(ast::Generics {
4349                 lifetimes: lifetime_defs,
4350                 ty_params: ty_params,
4351                 where_clause: WhereClause {
4352                     id: ast::DUMMY_NODE_ID,
4353                     predicates: Vec::new(),
4354                 }
4355             })
4356         } else {
4357             Ok(ast::Generics::default())
4358         }
4359     }
4360
4361     fn parse_generic_values_after_lt(&mut self) -> PResult<'a, (Vec<ast::Lifetime>,
4362                                                             Vec<P<Ty>>,
4363                                                             Vec<TypeBinding>)> {
4364         let span_lo = self.span.lo;
4365         let lifetimes = self.parse_lifetimes(token::Comma)?;
4366
4367         let missing_comma = !lifetimes.is_empty() &&
4368                             !self.token.is_like_gt() &&
4369                             self.last_token
4370                                 .as_ref().map_or(true,
4371                                                  |x| &**x != &token::Comma);
4372
4373         if missing_comma {
4374
4375             let msg = format!("expected `,` or `>` after lifetime \
4376                               name, found `{}`",
4377                               self.this_token_to_string());
4378             let mut err = self.diagnostic().struct_span_err(self.span, &msg);
4379
4380             let span_hi = self.span.hi;
4381             let span_hi = match self.parse_ty() {
4382                 Ok(..) => self.span.hi,
4383                 Err(ref mut err) => {
4384                     err.cancel();
4385                     span_hi
4386                 }
4387             };
4388
4389             let msg = format!("did you mean a single argument type &'a Type, \
4390                               or did you mean the comma-separated arguments \
4391                               'a, Type?");
4392             err.span_note(mk_sp(span_lo, span_hi), &msg);
4393             return Err(err);
4394         }
4395
4396         // First parse types.
4397         let (types, returned) = self.parse_seq_to_gt_or_return(
4398             Some(token::Comma),
4399             |p| {
4400                 p.forbid_lifetime()?;
4401                 if p.look_ahead(1, |t| t == &token::Eq) {
4402                     Ok(None)
4403                 } else {
4404                     Ok(Some(p.parse_ty_sum()?))
4405                 }
4406             }
4407         )?;
4408
4409         // If we found the `>`, don't continue.
4410         if !returned {
4411             return Ok((lifetimes, types.into_vec(), Vec::new()));
4412         }
4413
4414         // Then parse type bindings.
4415         let bindings = self.parse_seq_to_gt(
4416             Some(token::Comma),
4417             |p| {
4418                 p.forbid_lifetime()?;
4419                 let lo = p.span.lo;
4420                 let ident = p.parse_ident()?;
4421                 let found_eq = p.eat(&token::Eq);
4422                 if !found_eq {
4423                     let span = p.span;
4424                     p.span_warn(span, "whoops, no =?");
4425                 }
4426                 let ty = p.parse_ty()?;
4427                 let hi = ty.span.hi;
4428                 let span = mk_sp(lo, hi);
4429                 return Ok(TypeBinding{id: ast::DUMMY_NODE_ID,
4430                     ident: ident,
4431                     ty: ty,
4432                     span: span,
4433                 });
4434             }
4435         )?;
4436         Ok((lifetimes, types.into_vec(), bindings.into_vec()))
4437     }
4438
4439     fn forbid_lifetime(&mut self) -> PResult<'a, ()> {
4440         if self.token.is_lifetime() {
4441             let span = self.span;
4442             return Err(self.diagnostic().struct_span_err(span, "lifetime parameters must be \
4443                                                                 declared prior to type parameters"))
4444         }
4445         Ok(())
4446     }
4447
4448     /// Parses an optional `where` clause and places it in `generics`.
4449     ///
4450     /// ```ignore
4451     /// where T : Trait<U, V> + 'b, 'a : 'b
4452     /// ```
4453     pub fn parse_where_clause(&mut self) -> PResult<'a, ast::WhereClause> {
4454         maybe_whole!(self, NtWhereClause);
4455
4456         let mut where_clause = WhereClause {
4457             id: ast::DUMMY_NODE_ID,
4458             predicates: Vec::new(),
4459         };
4460
4461         if !self.eat_keyword(keywords::Where) {
4462             return Ok(where_clause);
4463         }
4464
4465         let mut parsed_something = false;
4466         loop {
4467             let lo = self.span.lo;
4468             match self.token {
4469                 token::OpenDelim(token::Brace) => {
4470                     break
4471                 }
4472
4473                 token::Lifetime(..) => {
4474                     let bounded_lifetime =
4475                         self.parse_lifetime()?;
4476
4477                     self.eat(&token::Colon);
4478
4479                     let bounds =
4480                         self.parse_lifetimes(token::BinOp(token::Plus))?;
4481
4482                     let hi = self.last_span.hi;
4483                     let span = mk_sp(lo, hi);
4484
4485                     where_clause.predicates.push(ast::WherePredicate::RegionPredicate(
4486                         ast::WhereRegionPredicate {
4487                             span: span,
4488                             lifetime: bounded_lifetime,
4489                             bounds: bounds
4490                         }
4491                     ));
4492
4493                     parsed_something = true;
4494                 }
4495
4496                 _ => {
4497                     let bound_lifetimes = if self.eat_keyword(keywords::For) {
4498                         // Higher ranked constraint.
4499                         self.expect(&token::Lt)?;
4500                         let lifetime_defs = self.parse_lifetime_defs()?;
4501                         self.expect_gt()?;
4502                         lifetime_defs
4503                     } else {
4504                         vec![]
4505                     };
4506
4507                     let bounded_ty = self.parse_ty()?;
4508
4509                     if self.eat(&token::Colon) {
4510                         let bounds = self.parse_ty_param_bounds(BoundParsingMode::Bare)?;
4511                         let hi = self.last_span.hi;
4512                         let span = mk_sp(lo, hi);
4513
4514                         if bounds.is_empty() {
4515                             self.span_err(span,
4516                                           "each predicate in a `where` clause must have \
4517                                            at least one bound in it");
4518                         }
4519
4520                         where_clause.predicates.push(ast::WherePredicate::BoundPredicate(
4521                                 ast::WhereBoundPredicate {
4522                                     span: span,
4523                                     bound_lifetimes: bound_lifetimes,
4524                                     bounded_ty: bounded_ty,
4525                                     bounds: bounds,
4526                         }));
4527
4528                         parsed_something = true;
4529                     } else if self.eat(&token::Eq) {
4530                         // let ty = try!(self.parse_ty());
4531                         let hi = self.last_span.hi;
4532                         let span = mk_sp(lo, hi);
4533                         // where_clause.predicates.push(
4534                         //     ast::WherePredicate::EqPredicate(ast::WhereEqPredicate {
4535                         //         id: ast::DUMMY_NODE_ID,
4536                         //         span: span,
4537                         //         path: panic!("NYI"), //bounded_ty,
4538                         //         ty: ty,
4539                         // }));
4540                         // parsed_something = true;
4541                         // // FIXME(#18433)
4542                         self.span_err(span,
4543                                      "equality constraints are not yet supported \
4544                                      in where clauses (#20041)");
4545                     } else {
4546                         let last_span = self.last_span;
4547                         self.span_err(last_span,
4548                               "unexpected token in `where` clause");
4549                     }
4550                 }
4551             };
4552
4553             if !self.eat(&token::Comma) {
4554                 break
4555             }
4556         }
4557
4558         if !parsed_something {
4559             let last_span = self.last_span;
4560             self.span_err(last_span,
4561                           "a `where` clause must have at least one predicate \
4562                            in it");
4563         }
4564
4565         Ok(where_clause)
4566     }
4567
4568     fn parse_fn_args(&mut self, named_args: bool, allow_variadic: bool)
4569                      -> PResult<'a, (Vec<Arg> , bool)> {
4570         let sp = self.span;
4571         let mut variadic = false;
4572         let args: Vec<Option<Arg>> =
4573             self.parse_unspanned_seq(
4574                 &token::OpenDelim(token::Paren),
4575                 &token::CloseDelim(token::Paren),
4576                 SeqSep::trailing_allowed(token::Comma),
4577                 |p| {
4578                     if p.token == token::DotDotDot {
4579                         p.bump();
4580                         if allow_variadic {
4581                             if p.token != token::CloseDelim(token::Paren) {
4582                                 let span = p.span;
4583                                 p.span_err(span,
4584                                     "`...` must be last in argument list for variadic function");
4585                             }
4586                         } else {
4587                             let span = p.span;
4588                             p.span_err(span,
4589                                        "only foreign functions are allowed to be variadic");
4590                         }
4591                         variadic = true;
4592                         Ok(None)
4593                     } else {
4594                         match p.parse_arg_general(named_args) {
4595                             Ok(arg) => Ok(Some(arg)),
4596                             Err(mut e) => {
4597                                 e.emit();
4598                                 p.eat_to_tokens(&[&token::Comma, &token::CloseDelim(token::Paren)]);
4599                                 Ok(None)
4600                             }
4601                         }
4602                     }
4603                 }
4604             )?;
4605
4606         let args: Vec<_> = args.into_iter().filter_map(|x| x).collect();
4607
4608         if variadic && args.is_empty() {
4609             self.span_err(sp,
4610                           "variadic function must be declared with at least one named argument");
4611         }
4612
4613         Ok((args, variadic))
4614     }
4615
4616     /// Parse the argument list and result type of a function declaration
4617     pub fn parse_fn_decl(&mut self, allow_variadic: bool) -> PResult<'a, P<FnDecl>> {
4618
4619         let (args, variadic) = self.parse_fn_args(true, allow_variadic)?;
4620         let ret_ty = self.parse_ret_ty()?;
4621
4622         Ok(P(FnDecl {
4623             inputs: args,
4624             output: ret_ty,
4625             variadic: variadic
4626         }))
4627     }
4628
4629     fn is_self_ident(&mut self) -> bool {
4630         match self.token {
4631           token::Ident(id, token::Plain) => id.name == special_idents::self_.name,
4632           _ => false
4633         }
4634     }
4635
4636     fn expect_self_ident(&mut self) -> PResult<'a, ast::Ident> {
4637         match self.token {
4638             token::Ident(id, token::Plain) if id.name == special_idents::self_.name => {
4639                 self.bump();
4640                 Ok(id)
4641             },
4642             _ => {
4643                 let token_str = self.this_token_to_string();
4644                 return Err(self.fatal(&format!("expected `self`, found `{}`",
4645                                    token_str)))
4646             }
4647         }
4648     }
4649
4650     fn is_self_type_ident(&mut self) -> bool {
4651         match self.token {
4652           token::Ident(id, token::Plain) => id.name == special_idents::type_self.name,
4653           _ => false
4654         }
4655     }
4656
4657     fn expect_self_type_ident(&mut self) -> PResult<'a, ast::Ident> {
4658         match self.token {
4659             token::Ident(id, token::Plain) if id.name == special_idents::type_self.name => {
4660                 self.bump();
4661                 Ok(id)
4662             },
4663             _ => {
4664                 let token_str = self.this_token_to_string();
4665                 Err(self.fatal(&format!("expected `Self`, found `{}`",
4666                                    token_str)))
4667             }
4668         }
4669     }
4670
4671     /// Parse the argument list and result type of a function
4672     /// that may have a self type.
4673     fn parse_fn_decl_with_self<F>(&mut self,
4674                                   parse_arg_fn: F) -> PResult<'a, (ExplicitSelf, P<FnDecl>)> where
4675         F: FnMut(&mut Parser<'a>) -> PResult<'a,  Arg>,
4676     {
4677         fn maybe_parse_borrowed_explicit_self<'b>(this: &mut Parser<'b>)
4678                                                   -> PResult<'b, ast::SelfKind> {
4679             // The following things are possible to see here:
4680             //
4681             //     fn(&mut self)
4682             //     fn(&mut self)
4683             //     fn(&'lt self)
4684             //     fn(&'lt mut self)
4685             //
4686             // We already know that the current token is `&`.
4687
4688             if this.look_ahead(1, |t| t.is_keyword(keywords::SelfValue)) {
4689                 this.bump();
4690                 Ok(SelfKind::Region(None, Mutability::Immutable, this.expect_self_ident()?))
4691             } else if this.look_ahead(1, |t| t.is_mutability()) &&
4692                       this.look_ahead(2, |t| t.is_keyword(keywords::SelfValue)) {
4693                 this.bump();
4694                 let mutability = this.parse_mutability()?;
4695                 Ok(SelfKind::Region(None, mutability, this.expect_self_ident()?))
4696             } else if this.look_ahead(1, |t| t.is_lifetime()) &&
4697                       this.look_ahead(2, |t| t.is_keyword(keywords::SelfValue)) {
4698                 this.bump();
4699                 let lifetime = this.parse_lifetime()?;
4700                 let ident = this.expect_self_ident()?;
4701                 Ok(SelfKind::Region(Some(lifetime), Mutability::Immutable, ident))
4702             } else if this.look_ahead(1, |t| t.is_lifetime()) &&
4703                       this.look_ahead(2, |t| t.is_mutability()) &&
4704                       this.look_ahead(3, |t| t.is_keyword(keywords::SelfValue)) {
4705                 this.bump();
4706                 let lifetime = this.parse_lifetime()?;
4707                 let mutability = this.parse_mutability()?;
4708                 Ok(SelfKind::Region(Some(lifetime), mutability, this.expect_self_ident()?))
4709             } else {
4710                 Ok(SelfKind::Static)
4711             }
4712         }
4713
4714         self.expect(&token::OpenDelim(token::Paren))?;
4715
4716         // A bit of complexity and lookahead is needed here in order to be
4717         // backwards compatible.
4718         let lo = self.span.lo;
4719         let mut self_ident_lo = self.span.lo;
4720         let mut self_ident_hi = self.span.hi;
4721
4722         let mut mutbl_self = Mutability::Immutable;
4723         let explicit_self = match self.token {
4724             token::BinOp(token::And) => {
4725                 let eself = maybe_parse_borrowed_explicit_self(self)?;
4726                 self_ident_lo = self.last_span.lo;
4727                 self_ident_hi = self.last_span.hi;
4728                 eself
4729             }
4730             token::BinOp(token::Star) => {
4731                 // Possibly "*self" or "*mut self" -- not supported. Try to avoid
4732                 // emitting cryptic "unexpected token" errors.
4733                 self.bump();
4734                 let _mutability = if self.token.is_mutability() {
4735                     self.parse_mutability()?
4736                 } else {
4737                     Mutability::Immutable
4738                 };
4739                 if self.is_self_ident() {
4740                     let span = self.span;
4741                     self.span_err(span, "cannot pass self by raw pointer");
4742                     self.bump();
4743                 }
4744                 // error case, making bogus self ident:
4745                 SelfKind::Value(special_idents::self_)
4746             }
4747             token::Ident(..) => {
4748                 if self.is_self_ident() {
4749                     let self_ident = self.expect_self_ident()?;
4750
4751                     // Determine whether this is the fully explicit form, `self:
4752                     // TYPE`.
4753                     if self.eat(&token::Colon) {
4754                         SelfKind::Explicit(self.parse_ty_sum()?, self_ident)
4755                     } else {
4756                         SelfKind::Value(self_ident)
4757                     }
4758                 } else if self.token.is_mutability() &&
4759                         self.look_ahead(1, |t| t.is_keyword(keywords::SelfValue)) {
4760                     mutbl_self = self.parse_mutability()?;
4761                     let self_ident = self.expect_self_ident()?;
4762
4763                     // Determine whether this is the fully explicit form,
4764                     // `self: TYPE`.
4765                     if self.eat(&token::Colon) {
4766                         SelfKind::Explicit(self.parse_ty_sum()?, self_ident)
4767                     } else {
4768                         SelfKind::Value(self_ident)
4769                     }
4770                 } else {
4771                     SelfKind::Static
4772                 }
4773             }
4774             _ => SelfKind::Static,
4775         };
4776
4777         let explicit_self_sp = mk_sp(self_ident_lo, self_ident_hi);
4778
4779         // shared fall-through for the three cases below. borrowing prevents simply
4780         // writing this as a closure
4781         macro_rules! parse_remaining_arguments {
4782             ($self_id:ident) =>
4783             {
4784             // If we parsed a self type, expect a comma before the argument list.
4785             match self.token {
4786                 token::Comma => {
4787                     self.bump();
4788                     let sep = SeqSep::trailing_allowed(token::Comma);
4789                     let mut fn_inputs = self.parse_seq_to_before_end(
4790                         &token::CloseDelim(token::Paren),
4791                         sep,
4792                         parse_arg_fn
4793                     );
4794                     fn_inputs.insert(0, Arg::new_self(explicit_self_sp, mutbl_self, $self_id));
4795                     fn_inputs
4796                 }
4797                 token::CloseDelim(token::Paren) => {
4798                     vec!(Arg::new_self(explicit_self_sp, mutbl_self, $self_id))
4799                 }
4800                 _ => {
4801                     let token_str = self.this_token_to_string();
4802                     return Err(self.fatal(&format!("expected `,` or `)`, found `{}`",
4803                                        token_str)))
4804                 }
4805             }
4806             }
4807         }
4808
4809         let fn_inputs = match explicit_self {
4810             SelfKind::Static =>  {
4811                 let sep = SeqSep::trailing_allowed(token::Comma);
4812                 self.parse_seq_to_before_end(&token::CloseDelim(token::Paren), sep, parse_arg_fn)
4813             }
4814             SelfKind::Value(id) => parse_remaining_arguments!(id),
4815             SelfKind::Region(_,_,id) => parse_remaining_arguments!(id),
4816             SelfKind::Explicit(_,id) => parse_remaining_arguments!(id),
4817         };
4818
4819
4820         self.expect(&token::CloseDelim(token::Paren))?;
4821
4822         let hi = self.span.hi;
4823
4824         let ret_ty = self.parse_ret_ty()?;
4825
4826         let fn_decl = P(FnDecl {
4827             inputs: fn_inputs,
4828             output: ret_ty,
4829             variadic: false
4830         });
4831
4832         Ok((spanned(lo, hi, explicit_self), fn_decl))
4833     }
4834
4835     // parse the |arg, arg| header on a lambda
4836     fn parse_fn_block_decl(&mut self) -> PResult<'a, P<FnDecl>> {
4837         let inputs_captures = {
4838             if self.eat(&token::OrOr) {
4839                 Vec::new()
4840             } else {
4841                 self.expect(&token::BinOp(token::Or))?;
4842                 self.parse_obsolete_closure_kind()?;
4843                 let args = self.parse_seq_to_before_end(
4844                     &token::BinOp(token::Or),
4845                     SeqSep::trailing_allowed(token::Comma),
4846                     |p| p.parse_fn_block_arg()
4847                 );
4848                 self.bump();
4849                 args
4850             }
4851         };
4852         let output = self.parse_ret_ty()?;
4853
4854         Ok(P(FnDecl {
4855             inputs: inputs_captures,
4856             output: output,
4857             variadic: false
4858         }))
4859     }
4860
4861     /// Parse the name and optional generic types of a function header.
4862     fn parse_fn_header(&mut self) -> PResult<'a, (Ident, ast::Generics)> {
4863         let id = self.parse_ident()?;
4864         let generics = self.parse_generics()?;
4865         Ok((id, generics))
4866     }
4867
4868     fn mk_item(&mut self, lo: BytePos, hi: BytePos, ident: Ident,
4869                node: ItemKind, vis: Visibility,
4870                attrs: Vec<Attribute>) -> P<Item> {
4871         P(Item {
4872             ident: ident,
4873             attrs: attrs,
4874             id: ast::DUMMY_NODE_ID,
4875             node: node,
4876             vis: vis,
4877             span: mk_sp(lo, hi)
4878         })
4879     }
4880
4881     /// Parse an item-position function declaration.
4882     fn parse_item_fn(&mut self,
4883                      unsafety: Unsafety,
4884                      constness: Constness,
4885                      abi: abi::Abi)
4886                      -> PResult<'a, ItemInfo> {
4887         let (ident, mut generics) = self.parse_fn_header()?;
4888         let decl = self.parse_fn_decl(false)?;
4889         generics.where_clause = self.parse_where_clause()?;
4890         let (inner_attrs, body) = self.parse_inner_attrs_and_block()?;
4891         Ok((ident, ItemKind::Fn(decl, unsafety, constness, abi, generics, body), Some(inner_attrs)))
4892     }
4893
4894     /// true if we are looking at `const ID`, false for things like `const fn` etc
4895     pub fn is_const_item(&mut self) -> bool {
4896         self.token.is_keyword(keywords::Const) &&
4897             !self.look_ahead(1, |t| t.is_keyword(keywords::Fn)) &&
4898             !self.look_ahead(1, |t| t.is_keyword(keywords::Unsafe))
4899     }
4900
4901     /// parses all the "front matter" for a `fn` declaration, up to
4902     /// and including the `fn` keyword:
4903     ///
4904     /// - `const fn`
4905     /// - `unsafe fn`
4906     /// - `const unsafe fn`
4907     /// - `extern fn`
4908     /// - etc
4909     pub fn parse_fn_front_matter(&mut self)
4910                                  -> PResult<'a, (ast::Constness, ast::Unsafety, abi::Abi)> {
4911         let is_const_fn = self.eat_keyword(keywords::Const);
4912         let unsafety = self.parse_unsafety()?;
4913         let (constness, unsafety, abi) = if is_const_fn {
4914             (Constness::Const, unsafety, Abi::Rust)
4915         } else {
4916             let abi = if self.eat_keyword(keywords::Extern) {
4917                 self.parse_opt_abi()?.unwrap_or(Abi::C)
4918             } else {
4919                 Abi::Rust
4920             };
4921             (Constness::NotConst, unsafety, abi)
4922         };
4923         self.expect_keyword(keywords::Fn)?;
4924         Ok((constness, unsafety, abi))
4925     }
4926
4927     /// Parse an impl item.
4928     pub fn parse_impl_item(&mut self) -> PResult<'a, ImplItem> {
4929         maybe_whole!(no_clone_from_p self, NtImplItem);
4930
4931         let mut attrs = self.parse_outer_attributes()?;
4932         let lo = self.span.lo;
4933         let vis = self.parse_visibility(true)?;
4934         let defaultness = self.parse_defaultness()?;
4935         let (name, node) = if self.eat_keyword(keywords::Type) {
4936             let name = self.parse_ident()?;
4937             self.expect(&token::Eq)?;
4938             let typ = self.parse_ty_sum()?;
4939             self.expect(&token::Semi)?;
4940             (name, ast::ImplItemKind::Type(typ))
4941         } else if self.is_const_item() {
4942             self.expect_keyword(keywords::Const)?;
4943             let name = self.parse_ident()?;
4944             self.expect(&token::Colon)?;
4945             let typ = self.parse_ty_sum()?;
4946             self.expect(&token::Eq)?;
4947             let expr = self.parse_expr()?;
4948             self.commit_expr_expecting(&expr, token::Semi)?;
4949             (name, ast::ImplItemKind::Const(typ, expr))
4950         } else {
4951             let (name, inner_attrs, node) = self.parse_impl_method(&vis)?;
4952             attrs.extend(inner_attrs);
4953             (name, node)
4954         };
4955
4956         Ok(ImplItem {
4957             id: ast::DUMMY_NODE_ID,
4958             span: mk_sp(lo, self.last_span.hi),
4959             ident: name,
4960             vis: vis,
4961             defaultness: defaultness,
4962             attrs: attrs,
4963             node: node
4964         })
4965     }
4966
4967     fn complain_if_pub_macro(&mut self, visa: &Visibility, span: Span) {
4968         match *visa {
4969             Visibility::Inherited => (),
4970             _ => {
4971                 let is_macro_rules: bool = match self.token {
4972                     token::Ident(sid, _) => sid.name == intern("macro_rules"),
4973                     _ => false,
4974                 };
4975                 if is_macro_rules {
4976                     self.diagnostic().struct_span_err(span, "can't qualify macro_rules \
4977                                                              invocation with `pub`")
4978                                      .fileline_help(span, "did you mean #[macro_export]?")
4979                                      .emit();
4980                 } else {
4981                     self.diagnostic().struct_span_err(span, "can't qualify macro \
4982                                                              invocation with `pub`")
4983                                      .fileline_help(span, "try adjusting the macro to put `pub` \
4984                                                            inside the invocation")
4985                                      .emit();
4986                 }
4987             }
4988         }
4989     }
4990
4991     /// Parse a method or a macro invocation in a trait impl.
4992     fn parse_impl_method(&mut self, vis: &Visibility)
4993                          -> PResult<'a, (Ident, Vec<ast::Attribute>, ast::ImplItemKind)> {
4994         // code copied from parse_macro_use_or_failure... abstraction!
4995         if !self.token.is_any_keyword()
4996             && self.look_ahead(1, |t| *t == token::Not)
4997             && (self.look_ahead(2, |t| *t == token::OpenDelim(token::Paren))
4998                 || self.look_ahead(2, |t| *t == token::OpenDelim(token::Brace))) {
4999             // method macro.
5000
5001             let last_span = self.last_span;
5002             self.complain_if_pub_macro(&vis, last_span);
5003
5004             let lo = self.span.lo;
5005             let pth = self.parse_path(NoTypesAllowed)?;
5006             self.expect(&token::Not)?;
5007
5008             // eat a matched-delimiter token tree:
5009             let delim = self.expect_open_delim()?;
5010             let tts = self.parse_seq_to_end(&token::CloseDelim(delim),
5011                                             SeqSep::none(),
5012                                             |p| p.parse_token_tree())?;
5013             let m_ = Mac_ { path: pth, tts: tts, ctxt: EMPTY_CTXT };
5014             let m: ast::Mac = codemap::Spanned { node: m_,
5015                                                 span: mk_sp(lo,
5016                                                             self.last_span.hi) };
5017             if delim != token::Brace {
5018                 self.expect(&token::Semi)?
5019             }
5020             Ok((token::special_idents::invalid, vec![], ast::ImplItemKind::Macro(m)))
5021         } else {
5022             let (constness, unsafety, abi) = self.parse_fn_front_matter()?;
5023             let ident = self.parse_ident()?;
5024             let mut generics = self.parse_generics()?;
5025             let (explicit_self, decl) = self.parse_fn_decl_with_self(|p| {
5026                     p.parse_arg()
5027                 })?;
5028             generics.where_clause = self.parse_where_clause()?;
5029             let (inner_attrs, body) = self.parse_inner_attrs_and_block()?;
5030             Ok((ident, inner_attrs, ast::ImplItemKind::Method(ast::MethodSig {
5031                 generics: generics,
5032                 abi: abi,
5033                 explicit_self: explicit_self,
5034                 unsafety: unsafety,
5035                 constness: constness,
5036                 decl: decl
5037              }, body)))
5038         }
5039     }
5040
5041     /// Parse trait Foo { ... }
5042     fn parse_item_trait(&mut self, unsafety: Unsafety) -> PResult<'a, ItemInfo> {
5043
5044         let ident = self.parse_ident()?;
5045         let mut tps = self.parse_generics()?;
5046
5047         // Parse supertrait bounds.
5048         let bounds = self.parse_colon_then_ty_param_bounds(BoundParsingMode::Bare)?;
5049
5050         tps.where_clause = self.parse_where_clause()?;
5051
5052         let meths = self.parse_trait_items()?;
5053         Ok((ident, ItemKind::Trait(unsafety, tps, bounds, meths), None))
5054     }
5055
5056     /// Parses items implementations variants
5057     ///    impl<T> Foo { ... }
5058     ///    impl<T> ToString for &'static T { ... }
5059     ///    impl Send for .. {}
5060     fn parse_item_impl(&mut self, unsafety: ast::Unsafety) -> PResult<'a, ItemInfo> {
5061         let impl_span = self.span;
5062
5063         // First, parse type parameters if necessary.
5064         let mut generics = self.parse_generics()?;
5065
5066         // Special case: if the next identifier that follows is '(', don't
5067         // allow this to be parsed as a trait.
5068         let could_be_trait = self.token != token::OpenDelim(token::Paren);
5069
5070         let neg_span = self.span;
5071         let polarity = if self.eat(&token::Not) {
5072             ast::ImplPolarity::Negative
5073         } else {
5074             ast::ImplPolarity::Positive
5075         };
5076
5077         // Parse the trait.
5078         let mut ty = self.parse_ty_sum()?;
5079
5080         // Parse traits, if necessary.
5081         let opt_trait = if could_be_trait && self.eat_keyword(keywords::For) {
5082             // New-style trait. Reinterpret the type as a trait.
5083             match ty.node {
5084                 TyKind::Path(None, ref path) => {
5085                     Some(TraitRef {
5086                         path: (*path).clone(),
5087                         ref_id: ty.id,
5088                     })
5089                 }
5090                 _ => {
5091                     self.span_err(ty.span, "not a trait");
5092                     None
5093                 }
5094             }
5095         } else {
5096             match polarity {
5097                 ast::ImplPolarity::Negative => {
5098                     // This is a negated type implementation
5099                     // `impl !MyType {}`, which is not allowed.
5100                     self.span_err(neg_span, "inherent implementation can't be negated");
5101                 },
5102                 _ => {}
5103             }
5104             None
5105         };
5106
5107         if opt_trait.is_some() && self.eat(&token::DotDot) {
5108             if generics.is_parameterized() {
5109                 self.span_err(impl_span, "default trait implementations are not \
5110                                           allowed to have generics");
5111             }
5112
5113             self.expect(&token::OpenDelim(token::Brace))?;
5114             self.expect(&token::CloseDelim(token::Brace))?;
5115             Ok((special_idents::invalid,
5116              ItemKind::DefaultImpl(unsafety, opt_trait.unwrap()), None))
5117         } else {
5118             if opt_trait.is_some() {
5119                 ty = self.parse_ty_sum()?;
5120             }
5121             generics.where_clause = self.parse_where_clause()?;
5122
5123             self.expect(&token::OpenDelim(token::Brace))?;
5124             let attrs = self.parse_inner_attributes()?;
5125
5126             let mut impl_items = vec![];
5127             while !self.eat(&token::CloseDelim(token::Brace)) {
5128                 impl_items.push(self.parse_impl_item()?);
5129             }
5130
5131             Ok((special_idents::invalid,
5132              ItemKind::Impl(unsafety, polarity, generics, opt_trait, ty, impl_items),
5133              Some(attrs)))
5134         }
5135     }
5136
5137     /// Parse a::B<String,i32>
5138     fn parse_trait_ref(&mut self) -> PResult<'a, TraitRef> {
5139         Ok(ast::TraitRef {
5140             path: self.parse_path(LifetimeAndTypesWithoutColons)?,
5141             ref_id: ast::DUMMY_NODE_ID,
5142         })
5143     }
5144
5145     fn parse_late_bound_lifetime_defs(&mut self) -> PResult<'a, Vec<ast::LifetimeDef>> {
5146         if self.eat_keyword(keywords::For) {
5147             self.expect(&token::Lt)?;
5148             let lifetime_defs = self.parse_lifetime_defs()?;
5149             self.expect_gt()?;
5150             Ok(lifetime_defs)
5151         } else {
5152             Ok(Vec::new())
5153         }
5154     }
5155
5156     /// Parse for<'l> a::B<String,i32>
5157     fn parse_poly_trait_ref(&mut self) -> PResult<'a, PolyTraitRef> {
5158         let lo = self.span.lo;
5159         let lifetime_defs = self.parse_late_bound_lifetime_defs()?;
5160
5161         Ok(ast::PolyTraitRef {
5162             bound_lifetimes: lifetime_defs,
5163             trait_ref: self.parse_trait_ref()?,
5164             span: mk_sp(lo, self.last_span.hi),
5165         })
5166     }
5167
5168     /// Parse struct Foo { ... }
5169     fn parse_item_struct(&mut self) -> PResult<'a, ItemInfo> {
5170         let class_name = self.parse_ident()?;
5171         let mut generics = self.parse_generics()?;
5172
5173         // There is a special case worth noting here, as reported in issue #17904.
5174         // If we are parsing a tuple struct it is the case that the where clause
5175         // should follow the field list. Like so:
5176         //
5177         // struct Foo<T>(T) where T: Copy;
5178         //
5179         // If we are parsing a normal record-style struct it is the case
5180         // that the where clause comes before the body, and after the generics.
5181         // So if we look ahead and see a brace or a where-clause we begin
5182         // parsing a record style struct.
5183         //
5184         // Otherwise if we look ahead and see a paren we parse a tuple-style
5185         // struct.
5186
5187         let vdata = if self.token.is_keyword(keywords::Where) {
5188             generics.where_clause = self.parse_where_clause()?;
5189             if self.eat(&token::Semi) {
5190                 // If we see a: `struct Foo<T> where T: Copy;` style decl.
5191                 VariantData::Unit(ast::DUMMY_NODE_ID)
5192             } else {
5193                 // If we see: `struct Foo<T> where T: Copy { ... }`
5194                 VariantData::Struct(self.parse_record_struct_body()?, ast::DUMMY_NODE_ID)
5195             }
5196         // No `where` so: `struct Foo<T>;`
5197         } else if self.eat(&token::Semi) {
5198             VariantData::Unit(ast::DUMMY_NODE_ID)
5199         // Record-style struct definition
5200         } else if self.token == token::OpenDelim(token::Brace) {
5201             VariantData::Struct(self.parse_record_struct_body()?, ast::DUMMY_NODE_ID)
5202         // Tuple-style struct definition with optional where-clause.
5203         } else if self.token == token::OpenDelim(token::Paren) {
5204             let body = VariantData::Tuple(self.parse_tuple_struct_body()?, ast::DUMMY_NODE_ID);
5205             generics.where_clause = self.parse_where_clause()?;
5206             self.expect(&token::Semi)?;
5207             body
5208         } else {
5209             let token_str = self.this_token_to_string();
5210             return Err(self.fatal(&format!("expected `where`, `{{`, `(`, or `;` after struct \
5211                                             name, found `{}`", token_str)))
5212         };
5213
5214         Ok((class_name, ItemKind::Struct(vdata, generics), None))
5215     }
5216
5217     pub fn parse_record_struct_body(&mut self) -> PResult<'a, Vec<StructField>> {
5218         let mut fields = Vec::new();
5219         if self.eat(&token::OpenDelim(token::Brace)) {
5220             while self.token != token::CloseDelim(token::Brace) {
5221                 fields.push(self.parse_struct_decl_field()?);
5222             }
5223
5224             self.bump();
5225         } else {
5226             let token_str = self.this_token_to_string();
5227             return Err(self.fatal(&format!("expected `where`, or `{{` after struct \
5228                                 name, found `{}`",
5229                                 token_str)));
5230         }
5231
5232         Ok(fields)
5233     }
5234
5235     pub fn parse_tuple_struct_body(&mut self) -> PResult<'a, Vec<StructField>> {
5236         // This is the case where we find `struct Foo<T>(T) where T: Copy;`
5237         // Unit like structs are handled in parse_item_struct function
5238         let fields = self.parse_unspanned_seq(
5239             &token::OpenDelim(token::Paren),
5240             &token::CloseDelim(token::Paren),
5241             SeqSep::trailing_allowed(token::Comma),
5242             |p| {
5243                 let attrs = p.parse_outer_attributes()?;
5244                 let lo = p.span.lo;
5245                 let vis = p.parse_visibility(false)?;
5246                 let ty = p.parse_ty_sum()?;
5247                 Ok(StructField {
5248                     span: mk_sp(lo, p.span.hi),
5249                     vis: vis,
5250                     ident: None,
5251                     id: ast::DUMMY_NODE_ID,
5252                     ty: ty,
5253                     attrs: attrs,
5254                 })
5255             })?;
5256
5257         Ok(fields)
5258     }
5259
5260     /// Parse a structure field declaration
5261     pub fn parse_single_struct_field(&mut self,
5262                                      vis: Visibility,
5263                                      attrs: Vec<Attribute> )
5264                                      -> PResult<'a, StructField> {
5265         let a_var = self.parse_name_and_ty(vis, attrs)?;
5266         match self.token {
5267             token::Comma => {
5268                 self.bump();
5269             }
5270             token::CloseDelim(token::Brace) => {}
5271             _ => {
5272                 let span = self.span;
5273                 let token_str = self.this_token_to_string();
5274                 return Err(self.span_fatal_help(span,
5275                                      &format!("expected `,`, or `}}`, found `{}`",
5276                                              token_str),
5277                                      "struct fields should be separated by commas"))
5278             }
5279         }
5280         Ok(a_var)
5281     }
5282
5283     /// Parse an element of a struct definition
5284     fn parse_struct_decl_field(&mut self) -> PResult<'a, StructField> {
5285         let attrs = self.parse_outer_attributes()?;
5286         let vis = self.parse_visibility(true)?;
5287         self.parse_single_struct_field(vis, attrs)
5288     }
5289
5290     fn parse_visibility(&mut self, allow_restricted: bool) -> PResult<'a, Visibility> {
5291         if !self.eat_keyword(keywords::Pub) {
5292             Ok(Visibility::Inherited)
5293         } else if !allow_restricted || !self.eat(&token::OpenDelim(token::Paren)) {
5294             Ok(Visibility::Public)
5295         } else if self.eat_keyword(keywords::Crate) {
5296             let span = self.last_span;
5297             self.expect(&token::CloseDelim(token::Paren))?;
5298             Ok(Visibility::Crate(span))
5299         } else {
5300             let path = self.with_res(Restrictions::ALLOW_MODULE_PATHS,
5301                                      |this| this.parse_path(NoTypesAllowed))?;
5302             self.expect(&token::CloseDelim(token::Paren))?;
5303             Ok(Visibility::Restricted { path: P(path), id: ast::DUMMY_NODE_ID })
5304         }
5305     }
5306
5307     /// Parse defaultness: DEFAULT or nothing
5308     fn parse_defaultness(&mut self) -> PResult<'a, Defaultness> {
5309         if self.eat_contextual_keyword(special_idents::DEFAULT) {
5310             Ok(Defaultness::Default)
5311         } else {
5312             Ok(Defaultness::Final)
5313         }
5314     }
5315
5316     /// Given a termination token, parse all of the items in a module
5317     fn parse_mod_items(&mut self, term: &token::Token, inner_lo: BytePos) -> PResult<'a, Mod> {
5318         let mut items = vec![];
5319         while let Some(item) = self.parse_item()? {
5320             items.push(item);
5321         }
5322
5323         if !self.eat(term) {
5324             let token_str = self.this_token_to_string();
5325             return Err(self.fatal(&format!("expected item, found `{}`", token_str)));
5326         }
5327
5328         let hi = if self.span == codemap::DUMMY_SP {
5329             inner_lo
5330         } else {
5331             self.last_span.hi
5332         };
5333
5334         Ok(ast::Mod {
5335             inner: mk_sp(inner_lo, hi),
5336             items: items
5337         })
5338     }
5339
5340     fn parse_item_const(&mut self, m: Option<Mutability>) -> PResult<'a, ItemInfo> {
5341         let id = self.parse_ident()?;
5342         self.expect(&token::Colon)?;
5343         let ty = self.parse_ty_sum()?;
5344         self.expect(&token::Eq)?;
5345         let e = self.parse_expr()?;
5346         self.commit_expr_expecting(&e, token::Semi)?;
5347         let item = match m {
5348             Some(m) => ItemKind::Static(ty, m, e),
5349             None => ItemKind::Const(ty, e),
5350         };
5351         Ok((id, item, None))
5352     }
5353
5354     /// Parse a `mod <foo> { ... }` or `mod <foo>;` item
5355     fn parse_item_mod(&mut self, outer_attrs: &[Attribute]) -> PResult<'a, ItemInfo> {
5356         let id_span = self.span;
5357         let id = self.parse_ident()?;
5358         if self.check(&token::Semi) {
5359             self.bump();
5360             // This mod is in an external file. Let's go get it!
5361             let (m, attrs) = self.eval_src_mod(id, outer_attrs, id_span)?;
5362             Ok((id, m, Some(attrs)))
5363         } else {
5364             self.push_mod_path(id, outer_attrs);
5365             self.expect(&token::OpenDelim(token::Brace))?;
5366             let mod_inner_lo = self.span.lo;
5367             let attrs = self.parse_inner_attributes()?;
5368             let m = self.parse_mod_items(&token::CloseDelim(token::Brace), mod_inner_lo)?;
5369             self.pop_mod_path();
5370             Ok((id, ItemKind::Mod(m), Some(attrs)))
5371         }
5372     }
5373
5374     fn push_mod_path(&mut self, id: Ident, attrs: &[Attribute]) {
5375         let default_path = self.id_to_interned_str(id);
5376         let file_path = match ::attr::first_attr_value_str_by_name(attrs, "path") {
5377             Some(d) => d,
5378             None => default_path,
5379         };
5380         self.mod_path_stack.push(file_path)
5381     }
5382
5383     fn pop_mod_path(&mut self) {
5384         self.mod_path_stack.pop().unwrap();
5385     }
5386
5387     pub fn submod_path_from_attr(attrs: &[ast::Attribute], dir_path: &Path) -> Option<PathBuf> {
5388         ::attr::first_attr_value_str_by_name(attrs, "path").map(|d| dir_path.join(&*d))
5389     }
5390
5391     /// Returns either a path to a module, or .
5392     pub fn default_submod_path(id: ast::Ident, dir_path: &Path, codemap: &CodeMap) -> ModulePath
5393     {
5394         let mod_name = id.to_string();
5395         let default_path_str = format!("{}.rs", mod_name);
5396         let secondary_path_str = format!("{}/mod.rs", mod_name);
5397         let default_path = dir_path.join(&default_path_str);
5398         let secondary_path = dir_path.join(&secondary_path_str);
5399         let default_exists = codemap.file_exists(&default_path);
5400         let secondary_exists = codemap.file_exists(&secondary_path);
5401
5402         let result = match (default_exists, secondary_exists) {
5403             (true, false) => Ok(ModulePathSuccess { path: default_path, owns_directory: false }),
5404             (false, true) => Ok(ModulePathSuccess { path: secondary_path, owns_directory: true }),
5405             (false, false) => Err(ModulePathError {
5406                 err_msg: format!("file not found for module `{}`", mod_name),
5407                 help_msg: format!("name the file either {} or {} inside the directory {:?}",
5408                                   default_path_str,
5409                                   secondary_path_str,
5410                                   dir_path.display()),
5411             }),
5412             (true, true) => Err(ModulePathError {
5413                 err_msg: format!("file for module `{}` found at both {} and {}",
5414                                  mod_name,
5415                                  default_path_str,
5416                                  secondary_path_str),
5417                 help_msg: "delete or rename one of them to remove the ambiguity".to_owned(),
5418             }),
5419         };
5420
5421         ModulePath {
5422             name: mod_name,
5423             path_exists: default_exists || secondary_exists,
5424             result: result,
5425         }
5426     }
5427
5428     fn submod_path(&mut self,
5429                    id: ast::Ident,
5430                    outer_attrs: &[ast::Attribute],
5431                    id_sp: Span) -> PResult<'a, ModulePathSuccess> {
5432         let mut prefix = PathBuf::from(self.filename.as_ref().unwrap());
5433         prefix.pop();
5434         let mut dir_path = prefix;
5435         for part in &self.mod_path_stack {
5436             dir_path.push(&**part);
5437         }
5438
5439         if let Some(p) = Parser::submod_path_from_attr(outer_attrs, &dir_path) {
5440             return Ok(ModulePathSuccess { path: p, owns_directory: true });
5441         }
5442
5443         let paths = Parser::default_submod_path(id, &dir_path, self.sess.codemap());
5444
5445         if self.restrictions.contains(Restrictions::NO_NONINLINE_MOD) {
5446             let msg =
5447                 "Cannot declare a non-inline module inside a block unless it has a path attribute";
5448             let mut err = self.diagnostic().struct_span_err(id_sp, msg);
5449             if paths.path_exists {
5450                 let msg = format!("Maybe `use` the module `{}` instead of redeclaring it",
5451                                   paths.name);
5452                 err.span_note(id_sp, &msg);
5453             }
5454             return Err(err);
5455         } else if !self.owns_directory {
5456             let mut err = self.diagnostic().struct_span_err(id_sp,
5457                 "cannot declare a new module at this location");
5458             let this_module = match self.mod_path_stack.last() {
5459                 Some(name) => name.to_string(),
5460                 None => self.root_module_name.as_ref().unwrap().clone(),
5461             };
5462             err.span_note(id_sp,
5463                           &format!("maybe move this module `{0}` to its own directory \
5464                                      via `{0}/mod.rs`",
5465                                     this_module));
5466             if paths.path_exists {
5467                 err.span_note(id_sp,
5468                               &format!("... or maybe `use` the module `{}` instead \
5469                                         of possibly redeclaring it",
5470                                        paths.name));
5471             }
5472             return Err(err);
5473         }
5474
5475         match paths.result {
5476             Ok(succ) => Ok(succ),
5477             Err(err) => Err(self.span_fatal_help(id_sp, &err.err_msg, &err.help_msg)),
5478         }
5479     }
5480
5481     /// Read a module from a source file.
5482     fn eval_src_mod(&mut self,
5483                     id: ast::Ident,
5484                     outer_attrs: &[ast::Attribute],
5485                     id_sp: Span)
5486                     -> PResult<'a, (ast::ItemKind, Vec<ast::Attribute> )> {
5487         let ModulePathSuccess { path, owns_directory } = self.submod_path(id,
5488                                                                           outer_attrs,
5489                                                                           id_sp)?;
5490
5491         self.eval_src_mod_from_path(path,
5492                                     owns_directory,
5493                                     id.to_string(),
5494                                     id_sp)
5495     }
5496
5497     fn eval_src_mod_from_path(&mut self,
5498                               path: PathBuf,
5499                               owns_directory: bool,
5500                               name: String,
5501                               id_sp: Span) -> PResult<'a, (ast::ItemKind, Vec<ast::Attribute> )> {
5502         let mut included_mod_stack = self.sess.included_mod_stack.borrow_mut();
5503         match included_mod_stack.iter().position(|p| *p == path) {
5504             Some(i) => {
5505                 let mut err = String::from("circular modules: ");
5506                 let len = included_mod_stack.len();
5507                 for p in &included_mod_stack[i.. len] {
5508                     err.push_str(&p.to_string_lossy());
5509                     err.push_str(" -> ");
5510                 }
5511                 err.push_str(&path.to_string_lossy());
5512                 return Err(self.span_fatal(id_sp, &err[..]));
5513             }
5514             None => ()
5515         }
5516         included_mod_stack.push(path.clone());
5517         drop(included_mod_stack);
5518
5519         let mut p0 = new_sub_parser_from_file(self.sess,
5520                                               self.cfg.clone(),
5521                                               &path,
5522                                               owns_directory,
5523                                               Some(name),
5524                                               id_sp);
5525         let mod_inner_lo = p0.span.lo;
5526         let mod_attrs = p0.parse_inner_attributes()?;
5527         let m0 = p0.parse_mod_items(&token::Eof, mod_inner_lo)?;
5528         self.sess.included_mod_stack.borrow_mut().pop();
5529         Ok((ast::ItemKind::Mod(m0), mod_attrs))
5530     }
5531
5532     /// Parse a function declaration from a foreign module
5533     fn parse_item_foreign_fn(&mut self, vis: ast::Visibility, lo: BytePos,
5534                              attrs: Vec<Attribute>) -> PResult<'a, ForeignItem> {
5535         self.expect_keyword(keywords::Fn)?;
5536
5537         let (ident, mut generics) = self.parse_fn_header()?;
5538         let decl = self.parse_fn_decl(true)?;
5539         generics.where_clause = self.parse_where_clause()?;
5540         let hi = self.span.hi;
5541         self.expect(&token::Semi)?;
5542         Ok(ast::ForeignItem {
5543             ident: ident,
5544             attrs: attrs,
5545             node: ForeignItemKind::Fn(decl, generics),
5546             id: ast::DUMMY_NODE_ID,
5547             span: mk_sp(lo, hi),
5548             vis: vis
5549         })
5550     }
5551
5552     /// Parse a static item from a foreign module
5553     fn parse_item_foreign_static(&mut self, vis: ast::Visibility, lo: BytePos,
5554                                  attrs: Vec<Attribute>) -> PResult<'a, ForeignItem> {
5555         self.expect_keyword(keywords::Static)?;
5556         let mutbl = self.eat_keyword(keywords::Mut);
5557
5558         let ident = self.parse_ident()?;
5559         self.expect(&token::Colon)?;
5560         let ty = self.parse_ty_sum()?;
5561         let hi = self.span.hi;
5562         self.expect(&token::Semi)?;
5563         Ok(ForeignItem {
5564             ident: ident,
5565             attrs: attrs,
5566             node: ForeignItemKind::Static(ty, mutbl),
5567             id: ast::DUMMY_NODE_ID,
5568             span: mk_sp(lo, hi),
5569             vis: vis
5570         })
5571     }
5572
5573     /// Parse extern crate links
5574     ///
5575     /// # Examples
5576     ///
5577     /// extern crate foo;
5578     /// extern crate bar as foo;
5579     fn parse_item_extern_crate(&mut self,
5580                                lo: BytePos,
5581                                visibility: Visibility,
5582                                attrs: Vec<Attribute>)
5583                                 -> PResult<'a, P<Item>> {
5584
5585         let crate_name = self.parse_ident()?;
5586         let (maybe_path, ident) = if let Some(ident) = self.parse_rename()? {
5587             (Some(crate_name.name), ident)
5588         } else {
5589             (None, crate_name)
5590         };
5591         self.expect(&token::Semi)?;
5592
5593         let last_span = self.last_span;
5594         Ok(self.mk_item(lo,
5595                         last_span.hi,
5596                         ident,
5597                         ItemKind::ExternCrate(maybe_path),
5598                         visibility,
5599                         attrs))
5600     }
5601
5602     /// Parse `extern` for foreign ABIs
5603     /// modules.
5604     ///
5605     /// `extern` is expected to have been
5606     /// consumed before calling this method
5607     ///
5608     /// # Examples:
5609     ///
5610     /// extern "C" {}
5611     /// extern {}
5612     fn parse_item_foreign_mod(&mut self,
5613                               lo: BytePos,
5614                               opt_abi: Option<abi::Abi>,
5615                               visibility: Visibility,
5616                               mut attrs: Vec<Attribute>)
5617                               -> PResult<'a, P<Item>> {
5618         self.expect(&token::OpenDelim(token::Brace))?;
5619
5620         let abi = opt_abi.unwrap_or(Abi::C);
5621
5622         attrs.extend(self.parse_inner_attributes()?);
5623
5624         let mut foreign_items = vec![];
5625         while let Some(item) = self.parse_foreign_item()? {
5626             foreign_items.push(item);
5627         }
5628         self.expect(&token::CloseDelim(token::Brace))?;
5629
5630         let last_span = self.last_span;
5631         let m = ast::ForeignMod {
5632             abi: abi,
5633             items: foreign_items
5634         };
5635         Ok(self.mk_item(lo,
5636                      last_span.hi,
5637                      special_idents::invalid,
5638                      ItemKind::ForeignMod(m),
5639                      visibility,
5640                      attrs))
5641     }
5642
5643     /// Parse type Foo = Bar;
5644     fn parse_item_type(&mut self) -> PResult<'a, ItemInfo> {
5645         let ident = self.parse_ident()?;
5646         let mut tps = self.parse_generics()?;
5647         tps.where_clause = self.parse_where_clause()?;
5648         self.expect(&token::Eq)?;
5649         let ty = self.parse_ty_sum()?;
5650         self.expect(&token::Semi)?;
5651         Ok((ident, ItemKind::Ty(ty, tps), None))
5652     }
5653
5654     /// Parse the part of an "enum" decl following the '{'
5655     fn parse_enum_def(&mut self, _generics: &ast::Generics) -> PResult<'a, EnumDef> {
5656         let mut variants = Vec::new();
5657         let mut all_nullary = true;
5658         let mut any_disr = None;
5659         while self.token != token::CloseDelim(token::Brace) {
5660             let variant_attrs = self.parse_outer_attributes()?;
5661             let vlo = self.span.lo;
5662
5663             let struct_def;
5664             let mut disr_expr = None;
5665             let ident = self.parse_ident()?;
5666             if self.check(&token::OpenDelim(token::Brace)) {
5667                 // Parse a struct variant.
5668                 all_nullary = false;
5669                 struct_def = VariantData::Struct(self.parse_record_struct_body()?,
5670                                                  ast::DUMMY_NODE_ID);
5671             } else if self.check(&token::OpenDelim(token::Paren)) {
5672                 all_nullary = false;
5673                 struct_def = VariantData::Tuple(self.parse_tuple_struct_body()?,
5674                                                 ast::DUMMY_NODE_ID);
5675             } else if self.eat(&token::Eq) {
5676                 disr_expr = Some(self.parse_expr()?);
5677                 any_disr = disr_expr.as_ref().map(|expr| expr.span);
5678                 struct_def = VariantData::Unit(ast::DUMMY_NODE_ID);
5679             } else {
5680                 struct_def = VariantData::Unit(ast::DUMMY_NODE_ID);
5681             }
5682
5683             let vr = ast::Variant_ {
5684                 name: ident,
5685                 attrs: variant_attrs,
5686                 data: struct_def,
5687                 disr_expr: disr_expr,
5688             };
5689             variants.push(spanned(vlo, self.last_span.hi, vr));
5690
5691             if !self.eat(&token::Comma) { break; }
5692         }
5693         self.expect(&token::CloseDelim(token::Brace))?;
5694         match any_disr {
5695             Some(disr_span) if !all_nullary =>
5696                 self.span_err(disr_span,
5697                     "discriminator values can only be used with a c-like enum"),
5698             _ => ()
5699         }
5700
5701         Ok(ast::EnumDef { variants: variants })
5702     }
5703
5704     /// Parse an "enum" declaration
5705     fn parse_item_enum(&mut self) -> PResult<'a, ItemInfo> {
5706         let id = self.parse_ident()?;
5707         let mut generics = self.parse_generics()?;
5708         generics.where_clause = self.parse_where_clause()?;
5709         self.expect(&token::OpenDelim(token::Brace))?;
5710
5711         let enum_definition = self.parse_enum_def(&generics)?;
5712         Ok((id, ItemKind::Enum(enum_definition, generics), None))
5713     }
5714
5715     /// Parses a string as an ABI spec on an extern type or module. Consumes
5716     /// the `extern` keyword, if one is found.
5717     fn parse_opt_abi(&mut self) -> PResult<'a, Option<abi::Abi>> {
5718         match self.token {
5719             token::Literal(token::Str_(s), suf) | token::Literal(token::StrRaw(s, _), suf) => {
5720                 let sp = self.span;
5721                 self.expect_no_suffix(sp, "ABI spec", suf);
5722                 self.bump();
5723                 match abi::lookup(&s.as_str()) {
5724                     Some(abi) => Ok(Some(abi)),
5725                     None => {
5726                         let last_span = self.last_span;
5727                         self.span_err(
5728                             last_span,
5729                             &format!("invalid ABI: expected one of [{}], \
5730                                      found `{}`",
5731                                     abi::all_names().join(", "),
5732                                     s));
5733                         Ok(None)
5734                     }
5735                 }
5736             }
5737
5738             _ => Ok(None),
5739         }
5740     }
5741
5742     /// Parse one of the items allowed by the flags.
5743     /// NB: this function no longer parses the items inside an
5744     /// extern crate.
5745     fn parse_item_(&mut self, attrs: Vec<Attribute>,
5746                    macros_allowed: bool, attributes_allowed: bool) -> PResult<'a, Option<P<Item>>> {
5747         let nt_item = match self.token {
5748             token::Interpolated(token::NtItem(ref item)) => {
5749                 Some((**item).clone())
5750             }
5751             _ => None
5752         };
5753         match nt_item {
5754             Some(mut item) => {
5755                 self.bump();
5756                 let mut attrs = attrs;
5757                 mem::swap(&mut item.attrs, &mut attrs);
5758                 item.attrs.extend(attrs);
5759                 return Ok(Some(P(item)));
5760             }
5761             None => {}
5762         }
5763
5764         let lo = self.span.lo;
5765
5766         let visibility = self.parse_visibility(true)?;
5767
5768         if self.eat_keyword(keywords::Use) {
5769             // USE ITEM
5770             let item_ = ItemKind::Use(self.parse_view_path()?);
5771             self.expect(&token::Semi)?;
5772
5773             let last_span = self.last_span;
5774             let item = self.mk_item(lo,
5775                                     last_span.hi,
5776                                     token::special_idents::invalid,
5777                                     item_,
5778                                     visibility,
5779                                     attrs);
5780             return Ok(Some(item));
5781         }
5782
5783         if self.eat_keyword(keywords::Extern) {
5784             if self.eat_keyword(keywords::Crate) {
5785                 return Ok(Some(self.parse_item_extern_crate(lo, visibility, attrs)?));
5786             }
5787
5788             let opt_abi = self.parse_opt_abi()?;
5789
5790             if self.eat_keyword(keywords::Fn) {
5791                 // EXTERN FUNCTION ITEM
5792                 let abi = opt_abi.unwrap_or(Abi::C);
5793                 let (ident, item_, extra_attrs) =
5794                     self.parse_item_fn(Unsafety::Normal, Constness::NotConst, abi)?;
5795                 let last_span = self.last_span;
5796                 let item = self.mk_item(lo,
5797                                         last_span.hi,
5798                                         ident,
5799                                         item_,
5800                                         visibility,
5801                                         maybe_append(attrs, extra_attrs));
5802                 return Ok(Some(item));
5803             } else if self.check(&token::OpenDelim(token::Brace)) {
5804                 return Ok(Some(self.parse_item_foreign_mod(lo, opt_abi, visibility, attrs)?));
5805             }
5806
5807             self.unexpected()?;
5808         }
5809
5810         if self.eat_keyword(keywords::Static) {
5811             // STATIC ITEM
5812             let m = if self.eat_keyword(keywords::Mut) {
5813                 Mutability::Mutable
5814             } else {
5815                 Mutability::Immutable
5816             };
5817             let (ident, item_, extra_attrs) = self.parse_item_const(Some(m))?;
5818             let last_span = self.last_span;
5819             let item = self.mk_item(lo,
5820                                     last_span.hi,
5821                                     ident,
5822                                     item_,
5823                                     visibility,
5824                                     maybe_append(attrs, extra_attrs));
5825             return Ok(Some(item));
5826         }
5827         if self.eat_keyword(keywords::Const) {
5828             if self.check_keyword(keywords::Fn)
5829                 || (self.check_keyword(keywords::Unsafe)
5830                     && self.look_ahead(1, |t| t.is_keyword(keywords::Fn))) {
5831                 // CONST FUNCTION ITEM
5832                 let unsafety = if self.eat_keyword(keywords::Unsafe) {
5833                     Unsafety::Unsafe
5834                 } else {
5835                     Unsafety::Normal
5836                 };
5837                 self.bump();
5838                 let (ident, item_, extra_attrs) =
5839                     self.parse_item_fn(unsafety, Constness::Const, Abi::Rust)?;
5840                 let last_span = self.last_span;
5841                 let item = self.mk_item(lo,
5842                                         last_span.hi,
5843                                         ident,
5844                                         item_,
5845                                         visibility,
5846                                         maybe_append(attrs, extra_attrs));
5847                 return Ok(Some(item));
5848             }
5849
5850             // CONST ITEM
5851             if self.eat_keyword(keywords::Mut) {
5852                 let last_span = self.last_span;
5853                 self.diagnostic().struct_span_err(last_span, "const globals cannot be mutable")
5854                                  .fileline_help(last_span, "did you mean to declare a static?")
5855                                  .emit();
5856             }
5857             let (ident, item_, extra_attrs) = self.parse_item_const(None)?;
5858             let last_span = self.last_span;
5859             let item = self.mk_item(lo,
5860                                     last_span.hi,
5861                                     ident,
5862                                     item_,
5863                                     visibility,
5864                                     maybe_append(attrs, extra_attrs));
5865             return Ok(Some(item));
5866         }
5867         if self.check_keyword(keywords::Unsafe) &&
5868             self.look_ahead(1, |t| t.is_keyword(keywords::Trait))
5869         {
5870             // UNSAFE TRAIT ITEM
5871             self.expect_keyword(keywords::Unsafe)?;
5872             self.expect_keyword(keywords::Trait)?;
5873             let (ident, item_, extra_attrs) =
5874                 self.parse_item_trait(ast::Unsafety::Unsafe)?;
5875             let last_span = self.last_span;
5876             let item = self.mk_item(lo,
5877                                     last_span.hi,
5878                                     ident,
5879                                     item_,
5880                                     visibility,
5881                                     maybe_append(attrs, extra_attrs));
5882             return Ok(Some(item));
5883         }
5884         if self.check_keyword(keywords::Unsafe) &&
5885             self.look_ahead(1, |t| t.is_keyword(keywords::Impl))
5886         {
5887             // IMPL ITEM
5888             self.expect_keyword(keywords::Unsafe)?;
5889             self.expect_keyword(keywords::Impl)?;
5890             let (ident, item_, extra_attrs) = self.parse_item_impl(ast::Unsafety::Unsafe)?;
5891             let last_span = self.last_span;
5892             let item = self.mk_item(lo,
5893                                     last_span.hi,
5894                                     ident,
5895                                     item_,
5896                                     visibility,
5897                                     maybe_append(attrs, extra_attrs));
5898             return Ok(Some(item));
5899         }
5900         if self.check_keyword(keywords::Fn) {
5901             // FUNCTION ITEM
5902             self.bump();
5903             let (ident, item_, extra_attrs) =
5904                 self.parse_item_fn(Unsafety::Normal, Constness::NotConst, Abi::Rust)?;
5905             let last_span = self.last_span;
5906             let item = self.mk_item(lo,
5907                                     last_span.hi,
5908                                     ident,
5909                                     item_,
5910                                     visibility,
5911                                     maybe_append(attrs, extra_attrs));
5912             return Ok(Some(item));
5913         }
5914         if self.check_keyword(keywords::Unsafe)
5915             && self.look_ahead(1, |t| *t != token::OpenDelim(token::Brace)) {
5916             // UNSAFE FUNCTION ITEM
5917             self.bump();
5918             let abi = if self.eat_keyword(keywords::Extern) {
5919                 self.parse_opt_abi()?.unwrap_or(Abi::C)
5920             } else {
5921                 Abi::Rust
5922             };
5923             self.expect_keyword(keywords::Fn)?;
5924             let (ident, item_, extra_attrs) =
5925                 self.parse_item_fn(Unsafety::Unsafe, Constness::NotConst, abi)?;
5926             let last_span = self.last_span;
5927             let item = self.mk_item(lo,
5928                                     last_span.hi,
5929                                     ident,
5930                                     item_,
5931                                     visibility,
5932                                     maybe_append(attrs, extra_attrs));
5933             return Ok(Some(item));
5934         }
5935         if self.eat_keyword(keywords::Mod) {
5936             // MODULE ITEM
5937             let (ident, item_, extra_attrs) =
5938                 self.parse_item_mod(&attrs[..])?;
5939             let last_span = self.last_span;
5940             let item = self.mk_item(lo,
5941                                     last_span.hi,
5942                                     ident,
5943                                     item_,
5944                                     visibility,
5945                                     maybe_append(attrs, extra_attrs));
5946             return Ok(Some(item));
5947         }
5948         if self.eat_keyword(keywords::Type) {
5949             // TYPE ITEM
5950             let (ident, item_, extra_attrs) = self.parse_item_type()?;
5951             let last_span = self.last_span;
5952             let item = self.mk_item(lo,
5953                                     last_span.hi,
5954                                     ident,
5955                                     item_,
5956                                     visibility,
5957                                     maybe_append(attrs, extra_attrs));
5958             return Ok(Some(item));
5959         }
5960         if self.eat_keyword(keywords::Enum) {
5961             // ENUM ITEM
5962             let (ident, item_, extra_attrs) = self.parse_item_enum()?;
5963             let last_span = self.last_span;
5964             let item = self.mk_item(lo,
5965                                     last_span.hi,
5966                                     ident,
5967                                     item_,
5968                                     visibility,
5969                                     maybe_append(attrs, extra_attrs));
5970             return Ok(Some(item));
5971         }
5972         if self.eat_keyword(keywords::Trait) {
5973             // TRAIT ITEM
5974             let (ident, item_, extra_attrs) =
5975                 self.parse_item_trait(ast::Unsafety::Normal)?;
5976             let last_span = self.last_span;
5977             let item = self.mk_item(lo,
5978                                     last_span.hi,
5979                                     ident,
5980                                     item_,
5981                                     visibility,
5982                                     maybe_append(attrs, extra_attrs));
5983             return Ok(Some(item));
5984         }
5985         if self.eat_keyword(keywords::Impl) {
5986             // IMPL ITEM
5987             let (ident, item_, extra_attrs) = self.parse_item_impl(ast::Unsafety::Normal)?;
5988             let last_span = self.last_span;
5989             let item = self.mk_item(lo,
5990                                     last_span.hi,
5991                                     ident,
5992                                     item_,
5993                                     visibility,
5994                                     maybe_append(attrs, extra_attrs));
5995             return Ok(Some(item));
5996         }
5997         if self.eat_keyword(keywords::Struct) {
5998             // STRUCT ITEM
5999             let (ident, item_, extra_attrs) = self.parse_item_struct()?;
6000             let last_span = self.last_span;
6001             let item = self.mk_item(lo,
6002                                     last_span.hi,
6003                                     ident,
6004                                     item_,
6005                                     visibility,
6006                                     maybe_append(attrs, extra_attrs));
6007             return Ok(Some(item));
6008         }
6009         self.parse_macro_use_or_failure(attrs,macros_allowed,attributes_allowed,lo,visibility)
6010     }
6011
6012     /// Parse a foreign item.
6013     fn parse_foreign_item(&mut self) -> PResult<'a, Option<ForeignItem>> {
6014         let attrs = self.parse_outer_attributes()?;
6015         let lo = self.span.lo;
6016         let visibility = self.parse_visibility(true)?;
6017
6018         if self.check_keyword(keywords::Static) {
6019             // FOREIGN STATIC ITEM
6020             return Ok(Some(self.parse_item_foreign_static(visibility, lo, attrs)?));
6021         }
6022         if self.check_keyword(keywords::Fn) || self.check_keyword(keywords::Unsafe) {
6023             // FOREIGN FUNCTION ITEM
6024             return Ok(Some(self.parse_item_foreign_fn(visibility, lo, attrs)?));
6025         }
6026
6027         // FIXME #5668: this will occur for a macro invocation:
6028         match self.parse_macro_use_or_failure(attrs, true, false, lo, visibility)? {
6029             Some(item) => {
6030                 return Err(self.span_fatal(item.span, "macros cannot expand to foreign items"));
6031             }
6032             None => Ok(None)
6033         }
6034     }
6035
6036     /// This is the fall-through for parsing items.
6037     fn parse_macro_use_or_failure(
6038         &mut self,
6039         attrs: Vec<Attribute> ,
6040         macros_allowed: bool,
6041         attributes_allowed: bool,
6042         lo: BytePos,
6043         visibility: Visibility
6044     ) -> PResult<'a, Option<P<Item>>> {
6045         if macros_allowed && !self.token.is_any_keyword()
6046                 && self.look_ahead(1, |t| *t == token::Not)
6047                 && (self.look_ahead(2, |t| t.is_plain_ident())
6048                     || self.look_ahead(2, |t| *t == token::OpenDelim(token::Paren))
6049                     || self.look_ahead(2, |t| *t == token::OpenDelim(token::Brace))) {
6050             // MACRO INVOCATION ITEM
6051
6052             let last_span = self.last_span;
6053             self.complain_if_pub_macro(&visibility, last_span);
6054
6055             let mac_lo = self.span.lo;
6056
6057             // item macro.
6058             let pth = self.parse_path(NoTypesAllowed)?;
6059             self.expect(&token::Not)?;
6060
6061             // a 'special' identifier (like what `macro_rules!` uses)
6062             // is optional. We should eventually unify invoc syntax
6063             // and remove this.
6064             let id = if self.token.is_plain_ident() {
6065                 self.parse_ident()?
6066             } else {
6067                 token::special_idents::invalid // no special identifier
6068             };
6069             // eat a matched-delimiter token tree:
6070             let delim = self.expect_open_delim()?;
6071             let tts = self.parse_seq_to_end(&token::CloseDelim(delim),
6072                                             SeqSep::none(),
6073                                             |p| p.parse_token_tree())?;
6074             // single-variant-enum... :
6075             let m = Mac_ { path: pth, tts: tts, ctxt: EMPTY_CTXT };
6076             let m: ast::Mac = codemap::Spanned { node: m,
6077                                              span: mk_sp(mac_lo,
6078                                                          self.last_span.hi) };
6079
6080             if delim != token::Brace {
6081                 if !self.eat(&token::Semi) {
6082                     let last_span = self.last_span;
6083                     self.span_err(last_span,
6084                                   "macros that expand to items must either \
6085                                    be surrounded with braces or followed by \
6086                                    a semicolon");
6087                 }
6088             }
6089
6090             let item_ = ItemKind::Mac(m);
6091             let last_span = self.last_span;
6092             let item = self.mk_item(lo,
6093                                     last_span.hi,
6094                                     id,
6095                                     item_,
6096                                     visibility,
6097                                     attrs);
6098             return Ok(Some(item));
6099         }
6100
6101         // FAILURE TO PARSE ITEM
6102         match visibility {
6103             Visibility::Inherited => {}
6104             _ => {
6105                 let last_span = self.last_span;
6106                 return Err(self.span_fatal(last_span, "unmatched visibility `pub`"));
6107             }
6108         }
6109
6110         if !attributes_allowed && !attrs.is_empty() {
6111             self.expected_item_err(&attrs);
6112         }
6113         Ok(None)
6114     }
6115
6116     pub fn parse_item(&mut self) -> PResult<'a, Option<P<Item>>> {
6117         let attrs = self.parse_outer_attributes()?;
6118         self.parse_item_(attrs, true, false)
6119     }
6120
6121     fn parse_path_list_items(&mut self) -> PResult<'a, Vec<ast::PathListItem>> {
6122         self.parse_unspanned_seq(&token::OpenDelim(token::Brace),
6123                                  &token::CloseDelim(token::Brace),
6124                                  SeqSep::trailing_allowed(token::Comma), |this| {
6125             let lo = this.span.lo;
6126             let node = if this.eat_keyword(keywords::SelfValue) {
6127                 let rename = this.parse_rename()?;
6128                 ast::PathListItemKind::Mod { id: ast::DUMMY_NODE_ID, rename: rename }
6129             } else {
6130                 let ident = this.parse_ident()?;
6131                 let rename = this.parse_rename()?;
6132                 ast::PathListItemKind::Ident { name: ident, rename: rename, id: ast::DUMMY_NODE_ID }
6133             };
6134             let hi = this.last_span.hi;
6135             Ok(spanned(lo, hi, node))
6136         })
6137     }
6138
6139     /// `::{` or `::*`
6140     fn is_import_coupler(&mut self) -> bool {
6141         self.check(&token::ModSep) &&
6142             self.look_ahead(1, |t| *t == token::OpenDelim(token::Brace) ||
6143                                    *t == token::BinOp(token::Star))
6144     }
6145
6146     /// Matches ViewPath:
6147     /// MOD_SEP? non_global_path
6148     /// MOD_SEP? non_global_path as IDENT
6149     /// MOD_SEP? non_global_path MOD_SEP STAR
6150     /// MOD_SEP? non_global_path MOD_SEP LBRACE item_seq RBRACE
6151     /// MOD_SEP? LBRACE item_seq RBRACE
6152     fn parse_view_path(&mut self) -> PResult<'a, P<ViewPath>> {
6153         let lo = self.span.lo;
6154         if self.check(&token::OpenDelim(token::Brace)) || self.is_import_coupler() {
6155             // `{foo, bar}` or `::{foo, bar}`
6156             let prefix = ast::Path {
6157                 global: self.eat(&token::ModSep),
6158                 segments: Vec::new(),
6159                 span: mk_sp(lo, self.span.hi),
6160             };
6161             let items = self.parse_path_list_items()?;
6162             Ok(P(spanned(lo, self.span.hi, ViewPathList(prefix, items))))
6163         } else {
6164             let prefix = self.parse_path(ImportPrefix)?;
6165             if self.is_import_coupler() {
6166                 // `foo::bar::{a, b}` or `foo::bar::*`
6167                 self.bump();
6168                 if self.check(&token::BinOp(token::Star)) {
6169                     self.bump();
6170                     Ok(P(spanned(lo, self.span.hi, ViewPathGlob(prefix))))
6171                 } else {
6172                     let items = self.parse_path_list_items()?;
6173                     Ok(P(spanned(lo, self.span.hi, ViewPathList(prefix, items))))
6174                 }
6175             } else {
6176                 // `foo::bar` or `foo::bar as baz`
6177                 let rename = self.parse_rename()?.
6178                                   unwrap_or(prefix.segments.last().unwrap().identifier);
6179                 Ok(P(spanned(lo, self.last_span.hi, ViewPathSimple(rename, prefix))))
6180             }
6181         }
6182     }
6183
6184     fn parse_rename(&mut self) -> PResult<'a, Option<Ident>> {
6185         if self.eat_keyword(keywords::As) {
6186             self.parse_ident().map(Some)
6187         } else {
6188             Ok(None)
6189         }
6190     }
6191
6192     /// Parses a source module as a crate. This is the main
6193     /// entry point for the parser.
6194     pub fn parse_crate_mod(&mut self) -> PResult<'a, Crate> {
6195         let lo = self.span.lo;
6196         Ok(ast::Crate {
6197             attrs: self.parse_inner_attributes()?,
6198             module: self.parse_mod_items(&token::Eof, lo)?,
6199             config: self.cfg.clone(),
6200             span: mk_sp(lo, self.span.lo),
6201             exported_macros: Vec::new(),
6202         })
6203     }
6204
6205     pub fn parse_optional_str(&mut self)
6206                               -> Option<(InternedString,
6207                                          ast::StrStyle,
6208                                          Option<ast::Name>)> {
6209         let ret = match self.token {
6210             token::Literal(token::Str_(s), suf) => {
6211                 let s = self.id_to_interned_str(ast::Ident::with_empty_ctxt(s));
6212                 (s, ast::StrStyle::Cooked, suf)
6213             }
6214             token::Literal(token::StrRaw(s, n), suf) => {
6215                 let s = self.id_to_interned_str(ast::Ident::with_empty_ctxt(s));
6216                 (s, ast::StrStyle::Raw(n), suf)
6217             }
6218             _ => return None
6219         };
6220         self.bump();
6221         Some(ret)
6222     }
6223
6224     pub fn parse_str(&mut self) -> PResult<'a, (InternedString, StrStyle)> {
6225         match self.parse_optional_str() {
6226             Some((s, style, suf)) => {
6227                 let sp = self.last_span;
6228                 self.expect_no_suffix(sp, "string literal", suf);
6229                 Ok((s, style))
6230             }
6231             _ =>  Err(self.fatal("expected string literal"))
6232         }
6233     }
6234 }