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