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