src/libsyntax/parse/parser.rs

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