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