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