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