src/libsyntax/parse/parser.rs

   1 // Copyright 2012-2013 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 abi::AbiSet;
  15 use ast::{Sigil, BorrowedSigil, ManagedSigil, OwnedSigil};
  16 use ast::{CallSugar, NoSugar, DoSugar};
  17 use ast::{TyBareFn, TyClosure};
  18 use ast::{RegionTyParamBound, TraitTyParamBound};
  19 use ast::{provided, public, purity};
  20 use ast::{_mod, BiAdd, arg, Arm, Attribute, BindByRef, BindInfer};
  21 use ast::{BiBitAnd, BiBitOr, BiBitXor, Block};
  22 use ast::{BlockCheckMode, UnBox};
  23 use ast::{Crate, CrateConfig, Decl, DeclItem};
  24 use ast::{DeclLocal, DefaultBlock, UnDeref, BiDiv, EMPTY_CTXT, enum_def, explicit_self};
  25 use ast::{Expr, Expr_, ExprAddrOf, ExprMatch, ExprAgain};
  26 use ast::{ExprAssign, ExprAssignOp, ExprBinary, ExprBlock};
  27 use ast::{ExprBreak, ExprCall, ExprCast, ExprDoBody};
  28 use ast::{ExprField, ExprFnBlock, ExprIf, ExprIndex};
  29 use ast::{ExprLit, ExprLogLevel, ExprLoop, ExprMac};
  30 use ast::{ExprMethodCall, ExprParen, ExprPath, ExprRepeat};
  31 use ast::{ExprRet, ExprSelf, ExprStruct, ExprTup, ExprUnary};
  32 use ast::{ExprVec, ExprVstore, ExprVstoreMutBox};
  33 use ast::{ExprVstoreSlice, ExprVstoreBox};
  34 use ast::{ExprVstoreMutSlice, ExprWhile, ExprForLoop, extern_fn, Field, fn_decl};
  35 use ast::{ExprVstoreUniq, Onceness, Once, Many};
  36 use ast::{foreign_item, foreign_item_static, foreign_item_fn, foreign_mod};
  37 use ast::{Ident, impure_fn, inherited, item, item_, item_static};
  38 use ast::{item_enum, item_fn, item_foreign_mod, item_impl};
  39 use ast::{item_mac, item_mod, item_struct, item_trait, item_ty, lit, lit_};
  40 use ast::{lit_bool, lit_float, lit_float_unsuffixed, lit_int, lit_char};
  41 use ast::{lit_int_unsuffixed, lit_nil, lit_str, lit_uint, Local};
  42 use ast::{MutImmutable, MutMutable, mac_, mac_invoc_tt, matcher, match_nonterminal};
  43 use ast::{match_seq, match_tok, method, mt, BiMul, Mutability};
  44 use ast::{named_field, UnNeg, noreturn, UnNot, Pat, PatBox, PatEnum};
  45 use ast::{PatIdent, PatLit, PatRange, PatRegion, PatStruct};
  46 use ast::{PatTup, PatUniq, PatWild, private};
  47 use ast::{BiRem, required};
  48 use ast::{ret_style, return_val, BiShl, BiShr, Stmt, StmtDecl};
  49 use ast::{StmtExpr, StmtSemi, StmtMac, struct_def, struct_field};
  50 use ast::{struct_variant_kind, BiSub};
  51 use ast::StrStyle;
  52 use ast::{sty_box, sty_region, sty_static, sty_uniq, sty_value};
  53 use ast::{token_tree, trait_method, trait_ref, tt_delim, tt_seq, tt_tok};
  54 use ast::{tt_nonterminal, tuple_variant_kind, Ty, ty_, ty_bot, ty_box};
  55 use ast::{TypeField, ty_fixed_length_vec, ty_closure, ty_bare_fn, ty_typeof};
  56 use ast::{ty_infer, TypeMethod};
  57 use ast::{ty_nil, TyParam, TyParamBound, ty_path, ty_ptr, ty_rptr};
  58 use ast::{ty_tup, ty_u32, ty_uniq, ty_vec, UnUniq};
  59 use ast::{unnamed_field, UnsafeBlock, unsafe_fn, view_item};
  60 use ast::{view_item_, view_item_extern_mod, view_item_use};
  61 use ast::{view_path, view_path_glob, view_path_list, view_path_simple};
  62 use ast::visibility;
  63 use ast;
  64 use ast_util::{as_prec, operator_prec};
  65 use ast_util;
  66 use codemap::{Span, BytePos, Spanned, spanned, mk_sp};
  67 use codemap;
  68 use parse::attr::parser_attr;
  69 use parse::classify;
  70 use parse::common::{SeqSep, seq_sep_none};
  71 use parse::common::{seq_sep_trailing_disallowed, seq_sep_trailing_allowed};
  72 use parse::lexer::reader;
  73 use parse::lexer::TokenAndSpan;
  74 use parse::obsolete::*;
  75 use parse::token::{can_begin_expr, get_ident_interner, ident_to_str, is_ident};
  76 use parse::token::{is_ident_or_path};
  77 use parse::token::{is_plain_ident, INTERPOLATED, keywords, special_idents};
  78 use parse::token::{token_to_binop};
  79 use parse::token;
  80 use parse::{new_sub_parser_from_file, ParseSess};
  81 use opt_vec;
  82 use opt_vec::OptVec;
  83
  84 use std::hashmap::HashSet;
  85 use std::util;
  86 use std::vec;
  87
  88 #[deriving(Eq)]
  89 enum restriction {
  90     UNRESTRICTED,
  91     RESTRICT_STMT_EXPR,
  92     RESTRICT_NO_BAR_OP,
  93     RESTRICT_NO_BAR_OR_DOUBLEBAR_OP,
  94 }
  95
  96 type item_info = (Ident, item_, Option<~[Attribute]>);
  97
  98 /// How to parse a path. There are four different kinds of paths, all of which
  99 /// are parsed somewhat differently.
 100 #[deriving(Eq)]
 101 pub enum PathParsingMode {
 102     /// A path with no type parameters; e.g. `foo::bar::Baz`
 103     NoTypesAllowed,
 104     /// A path with a lifetime and type parameters, with no double colons
 105     /// before the type parameters; e.g. `foo::bar<'self>::Baz<T>`
 106     LifetimeAndTypesWithoutColons,
 107     /// A path with a lifetime and type parameters with double colons before
 108     /// the type parameters; e.g. `foo::bar::<'self>::Baz::<T>`
 109     LifetimeAndTypesWithColons,
 110     /// A path with a lifetime and type parameters with bounds before the last
 111     /// set of type parameters only; e.g. `foo::bar<'self>::Baz:X+Y<T>` This
 112     /// form does not use extra double colons.
 113     LifetimeAndTypesAndBounds,
 114 }
 115
 116 /// A pair of a path segment and group of type parameter bounds. (See `ast.rs`
 117 /// for the definition of a path segment.)
 118 struct PathSegmentAndBoundSet {
 119     segment: ast::PathSegment,
 120     bound_set: Option<OptVec<TyParamBound>>,
 121 }
 122
 123 /// A path paired with optional type bounds.
 124 struct PathAndBounds {
 125     path: ast::Path,
 126     bounds: Option<OptVec<TyParamBound>>,
 127 }
 128
 129 pub enum item_or_view_item {
 130     // Indicates a failure to parse any kind of item. The attributes are
 131     // returned.
 132     iovi_none(~[Attribute]),
 133     iovi_item(@item),
 134     iovi_foreign_item(@foreign_item),
 135     iovi_view_item(view_item)
 136 }
 137
 138 #[deriving(Eq)]
 139 enum view_item_parse_mode {
 140     VIEW_ITEMS_AND_ITEMS_ALLOWED,
 141     FOREIGN_ITEMS_ALLOWED,
 142     IMPORTS_AND_ITEMS_ALLOWED
 143 }
 144
 145 /* The expr situation is not as complex as I thought it would be.
 146 The important thing is to make sure that lookahead doesn't balk
 147 at INTERPOLATED tokens */
 148 macro_rules! maybe_whole_expr (
 149     ($p:expr) => (
 150         {
 151             // This horrible convolution is brought to you by
 152             // @mut, have a terrible day
 153             let ret = match *($p).token {
 154                 INTERPOLATED(token::nt_expr(e)) => {
 155                     Some(e)
 156                 }
 157                 INTERPOLATED(token::nt_path(ref pt)) => {
 158                     Some($p.mk_expr(
 159                         ($p).span.lo,
 160                         ($p).span.hi,
 161                         ExprPath(/* bad */ (**pt).clone())))
 162                 }
 163                 _ => None
 164             };
 165             match ret {
 166                 Some(e) => {
 167                     $p.bump();
 168                     return e;
 169                 }
 170                 None => ()
 171             }
 172         }
 173     )
 174 )
 175
 176 macro_rules! maybe_whole (
 177     ($p:expr, $constructor:ident) => (
 178         {
 179             let __found__ = match *($p).token {
 180                 INTERPOLATED(token::$constructor(_)) => {
 181                     Some(($p).bump_and_get())
 182                 }
 183                 _ => None
 184             };
 185             match __found__ {
 186                 Some(INTERPOLATED(token::$constructor(x))) => {
 187                     return x.clone()
 188                 }
 189                 _ => {}
 190             }
 191         }
 192     );
 193     (deref $p:expr, $constructor:ident) => (
 194         {
 195             let __found__ = match *($p).token {
 196                 INTERPOLATED(token::$constructor(_)) => {
 197                     Some(($p).bump_and_get())
 198                 }
 199                 _ => None
 200             };
 201             match __found__ {
 202                 Some(INTERPOLATED(token::$constructor(x))) => {
 203                     return (*x).clone()
 204                 }
 205                 _ => {}
 206             }
 207         }
 208     );
 209     (Some $p:expr, $constructor:ident) => (
 210         {
 211             let __found__ = match *($p).token {
 212                 INTERPOLATED(token::$constructor(_)) => {
 213                     Some(($p).bump_and_get())
 214                 }
 215                 _ => None
 216             };
 217             match __found__ {
 218                 Some(INTERPOLATED(token::$constructor(x))) => {
 219                     return Some(x.clone()),
 220                 }
 221                 _ => {}
 222             }
 223         }
 224     );
 225     (iovi $p:expr, $constructor:ident) => (
 226         {
 227             let __found__ = match *($p).token {
 228                 INTERPOLATED(token::$constructor(_)) => {
 229                     Some(($p).bump_and_get())
 230                 }
 231                 _ => None
 232             };
 233             match __found__ {
 234                 Some(INTERPOLATED(token::$constructor(x))) => {
 235                     return iovi_item(x.clone())
 236                 }
 237                 _ => {}
 238             }
 239         }
 240     );
 241     (pair_empty $p:expr, $constructor:ident) => (
 242         {
 243             let __found__ = match *($p).token {
 244                 INTERPOLATED(token::$constructor(_)) => {
 245                     Some(($p).bump_and_get())
 246                 }
 247                 _ => None
 248             };
 249             match __found__ {
 250                 Some(INTERPOLATED(token::$constructor(ref x))) => {
 251                     return (~[], (**x).clone())
 252                 }
 253                 _ => {}
 254             }
 255         }
 256     )
 257 )
 258
 259
 260 fn maybe_append(lhs: ~[Attribute], rhs: Option<~[Attribute]>)
 261              -> ~[Attribute] {
 262     match rhs {
 263         None => lhs,
 264         Some(ref attrs) => vec::append(lhs, (*attrs))
 265     }
 266 }
 267
 268
 269 struct ParsedItemsAndViewItems {
 270     attrs_remaining: ~[Attribute],
 271     view_items: ~[view_item],
 272     items: ~[@item],
 273     foreign_items: ~[@foreign_item]
 274 }
 275
 276 /* ident is handled by common.rs */
 277
 278 pub fn Parser(sess: @mut ParseSess,
 279               cfg: ast::CrateConfig,
 280               rdr: @mut reader)
 281            -> Parser {
 282     let tok0 = rdr.next_token();
 283     let interner = get_ident_interner();
 284     let span = tok0.sp;
 285     let placeholder = TokenAndSpan {
 286         tok: token::UNDERSCORE,
 287         sp: span,
 288     };
 289
 290     Parser {
 291         reader: rdr,
 292         interner: interner,
 293         sess: sess,
 294         cfg: cfg,
 295         token: @mut tok0.tok,
 296         span: @mut span,
 297         last_span: @mut span,
 298         last_token: @mut None,
 299         buffer: @mut ([
 300             placeholder.clone(),
 301             placeholder.clone(),
 302             placeholder.clone(),
 303             placeholder.clone(),
 304         ]),
 305         buffer_start: @mut 0,
 306         buffer_end: @mut 0,
 307         tokens_consumed: @mut 0,
 308         restriction: @mut UNRESTRICTED,
 309         quote_depth: @mut 0,
 310         obsolete_set: @mut HashSet::new(),
 311         mod_path_stack: @mut ~[],
 312         open_braces: @mut ~[]
 313     }
 314 }
 315
 316 // ooh, nasty mutable fields everywhere....
 317 pub struct Parser {
 318     sess: @mut ParseSess,
 319     cfg: CrateConfig,
 320     // the current token:
 321     token: @mut token::Token,
 322     // the span of the current token:
 323     span: @mut Span,
 324     // the span of the prior token:
 325     last_span: @mut Span,
 326     // the previous token or None (only stashed sometimes).
 327     last_token: @mut Option<~token::Token>,
 328     buffer: @mut [TokenAndSpan, ..4],
 329     buffer_start: @mut int,
 330     buffer_end: @mut int,
 331     tokens_consumed: @mut uint,
 332     restriction: @mut restriction,
 333     quote_depth: @mut uint, // not (yet) related to the quasiquoter
 334     reader: @mut reader,
 335     interner: @token::ident_interner,
 336     /// The set of seen errors about obsolete syntax. Used to suppress
 337     /// extra detail when the same error is seen twice
 338     obsolete_set: @mut HashSet<ObsoleteSyntax>,
 339     /// Used to determine the path to externally loaded source files
 340     mod_path_stack: @mut ~[@str],
 341     /// Stack of spans of open delimiters. Used for error message.
 342     open_braces: @mut ~[Span]
 343 }
 344
 345 #[unsafe_destructor]
 346 impl Drop for Parser {
 347     /* do not copy the parser; its state is tied to outside state */
 348     fn drop(&mut self) {}
 349 }
 350
 351 fn is_plain_ident_or_underscore(t: &token::Token) -> bool {
 352     is_plain_ident(t) || *t == token::UNDERSCORE
 353 }
 354
 355 impl Parser {
 356     // convert a token to a string using self's reader
 357     pub fn token_to_str(&self, token: &token::Token) -> ~str {
 358         token::to_str(get_ident_interner(), token)
 359     }
 360
 361     // convert the current token to a string using self's reader
 362     pub fn this_token_to_str(&self) -> ~str {
 363         self.token_to_str(self.token)
 364     }
 365
 366     pub fn unexpected_last(&self, t: &token::Token) -> ! {
 367         self.span_fatal(
 368             *self.last_span,
 369             format!(
 370                 "unexpected token: `{}`",
 371                 self.token_to_str(t)
 372             )
 373         );
 374     }
 375
 376     pub fn unexpected(&self) -> ! {
 377         self.fatal(
 378             format!(
 379                 "unexpected token: `{}`",
 380                 self.this_token_to_str()
 381             )
 382         );
 383     }
 384
 385     // expect and consume the token t. Signal an error if
 386     // the next token is not t.
 387     pub fn expect(&self, t: &token::Token) {
 388         if *self.token == *t {
 389             self.bump();
 390         } else {
 391             self.fatal(
 392                 format!(
 393                     "expected `{}` but found `{}`",
 394                     self.token_to_str(t),
 395                     self.this_token_to_str()
 396                 )
 397             )
 398         }
 399     }
 400
 401     // Expect next token to be edible or inedible token.  If edible,
 402     // then consume it; if inedible, then return without consuming
 403     // anything.  Signal a fatal error if next token is unexpected.
 404     pub fn expect_one_of(&self, edible: &[token::Token], inedible: &[token::Token]) {
 405         fn tokens_to_str(p:&Parser, tokens: &[token::Token]) -> ~str {
 406             let mut i = tokens.iter();
 407             // This might be a sign we need a connect method on Iterator.
 408             let b = i.next().map_default(~"", |t| p.token_to_str(t));
 409             i.fold(b, |b,a| b + "`, `" + p.token_to_str(a))
 410         }
 411         if edible.contains(self.token) {
 412             self.bump();
 413         } else if inedible.contains(self.token) {
 414             // leave it in the input
 415         } else {
 416             let expected = vec::append(edible.to_owned(), inedible);
 417             let expect = tokens_to_str(self, expected);
 418             let actual = self.this_token_to_str();
 419             self.fatal(
 420                 if expected.len() != 1 {
 421                     format!("expected one of `{}` but found `{}`", expect, actual)
 422                 } else {
 423                     format!("expected `{}` but found `{}`", expect, actual)
 424                 }
 425             )
 426         }
 427     }
 428
 429     // Check for erroneous `ident { }`; if matches, signal error and
 430     // recover (without consuming any expected input token).  Returns
 431     // true if and only if input was consumed for recovery.
 432     pub fn check_for_erroneous_unit_struct_expecting(&self, expected: &[token::Token]) -> bool {
 433         if *self.token == token::LBRACE
 434             && expected.iter().all(|t| *t != token::LBRACE)
 435             && self.look_ahead(1, |t| *t == token::RBRACE) {
 436             // matched; signal non-fatal error and recover.
 437             self.span_err(*self.span,
 438                           "Unit-like struct construction is written with no trailing `{ }`");
 439             self.eat(&token::LBRACE);
 440             self.eat(&token::RBRACE);
 441             true
 442         } else {
 443             false
 444         }
 445     }
 446
 447     // Commit to parsing a complete expression `e` expected to be
 448     // followed by some token from the set edible + inedible.  Recover
 449     // from anticipated input errors, discarding erroneous characters.
 450     pub fn commit_expr(&self, e: @Expr, edible: &[token::Token], inedible: &[token::Token]) {
 451         debug!("commit_expr {:?}", e);
 452         match e.node {
 453             ExprPath(*) => {
 454                 // might be unit-struct construction; check for recoverableinput error.
 455                 let expected = vec::append(edible.to_owned(), inedible);
 456                 self.check_for_erroneous_unit_struct_expecting(expected);
 457             }
 458             _ => {}
 459         }
 460         self.expect_one_of(edible, inedible)
 461     }
 462
 463     pub fn commit_expr_expecting(&self, e: @Expr, edible: token::Token) {
 464         self.commit_expr(e, &[edible], &[])
 465     }
 466
 467     // Commit to parsing a complete statement `s`, which expects to be
 468     // followed by some token from the set edible + inedible.  Check
 469     // for recoverable input errors, discarding erroneous characters.
 470     pub fn commit_stmt(&self, s: @Stmt, edible: &[token::Token], inedible: &[token::Token]) {
 471         debug!("commit_stmt {:?}", s);
 472         let _s = s; // unused, but future checks might want to inspect `s`.
 473         if self.last_token.as_ref().map_default(false, |t| is_ident_or_path(*t)) {
 474             let expected = vec::append(edible.to_owned(), inedible);
 475             self.check_for_erroneous_unit_struct_expecting(expected);
 476         }
 477         self.expect_one_of(edible, inedible)
 478     }
 479
 480     pub fn commit_stmt_expecting(&self, s: @Stmt, edible: token::Token) {
 481         self.commit_stmt(s, &[edible], &[])
 482     }
 483
 484     pub fn parse_ident(&self) -> ast::Ident {
 485         self.check_strict_keywords();
 486         self.check_reserved_keywords();
 487         match *self.token {
 488             token::IDENT(i, _) => {
 489                 self.bump();
 490                 i
 491             }
 492             token::INTERPOLATED(token::nt_ident(*)) => {
 493                 self.bug("ident interpolation not converted to real token");
 494             }
 495             _ => {
 496                 self.fatal(
 497                     format!(
 498                         "expected ident, found `{}`",
 499                         self.this_token_to_str()
 500                     )
 501                 );
 502             }
 503         }
 504     }
 505
 506     pub fn parse_path_list_ident(&self) -> ast::path_list_ident {
 507         let lo = self.span.lo;
 508         let ident = self.parse_ident();
 509         let hi = self.last_span.hi;
 510         spanned(lo, hi, ast::path_list_ident_ { name: ident,
 511                                                 id: ast::DUMMY_NODE_ID })
 512     }
 513
 514     // consume token 'tok' if it exists. Returns true if the given
 515     // token was present, false otherwise.
 516     pub fn eat(&self, tok: &token::Token) -> bool {
 517         let is_present = *self.token == *tok;
 518         if is_present { self.bump() }
 519         is_present
 520     }
 521
 522     pub fn is_keyword(&self, kw: keywords::Keyword) -> bool {
 523         token::is_keyword(kw, self.token)
 524     }
 525
 526     // if the next token is the given keyword, eat it and return
 527     // true. Otherwise, return false.
 528     pub fn eat_keyword(&self, kw: keywords::Keyword) -> bool {
 529         let is_kw = match *self.token {
 530             token::IDENT(sid, false) => kw.to_ident().name == sid.name,
 531             _ => false
 532         };
 533         if is_kw { self.bump() }
 534         is_kw
 535     }
 536
 537     // if the given word is not a keyword, signal an error.
 538     // if the next token is not the given word, signal an error.
 539     // otherwise, eat it.
 540     pub fn expect_keyword(&self, kw: keywords::Keyword) {
 541         if !self.eat_keyword(kw) {
 542             self.fatal(
 543                 format!(
 544                     "expected `{}`, found `{}`",
 545                     self.id_to_str(kw.to_ident()).to_str(),
 546                     self.this_token_to_str()
 547                 )
 548             );
 549         }
 550     }
 551
 552     // signal an error if the given string is a strict keyword
 553     pub fn check_strict_keywords(&self) {
 554         if token::is_strict_keyword(self.token) {
 555             self.span_err(*self.span,
 556                           format!("found `{}` in ident position", self.this_token_to_str()));
 557         }
 558     }
 559
 560     // signal an error if the current token is a reserved keyword
 561     pub fn check_reserved_keywords(&self) {
 562         if token::is_reserved_keyword(self.token) {
 563             self.fatal(format!("`{}` is a reserved keyword", self.this_token_to_str()));
 564         }
 565     }
 566
 567     // expect and consume a GT. if a >> is seen, replace it
 568     // with a single > and continue. If a GT is not seen,
 569     // signal an error.
 570     pub fn expect_gt(&self) {
 571         match *self.token {
 572             token::GT => self.bump(),
 573             token::BINOP(token::SHR) => self.replace_token(
 574                 token::GT,
 575                 self.span.lo + BytePos(1u),
 576                 self.span.hi
 577             ),
 578             _ => self.fatal(format!("expected `{}`, found `{}`",
 579                                  self.token_to_str(&token::GT),
 580                                  self.this_token_to_str()))
 581         }
 582     }
 583
 584     // parse a sequence bracketed by '<' and '>', stopping
 585     // before the '>'.
 586     pub fn parse_seq_to_before_gt<T>(&self,
 587                                      sep: Option<token::Token>,
 588                                      f: &fn(&Parser) -> T)
 589                                      -> OptVec<T> {
 590         let mut first = true;
 591         let mut v = opt_vec::Empty;
 592         while *self.token != token::GT
 593             && *self.token != token::BINOP(token::SHR) {
 594             match sep {
 595               Some(ref t) => {
 596                 if first { first = false; }
 597                 else { self.expect(t); }
 598               }
 599               _ => ()
 600             }
 601             v.push(f(self));
 602         }
 603         return v;
 604     }
 605
 606     pub fn parse_seq_to_gt<T>(&self,
 607                               sep: Option<token::Token>,
 608                               f: &fn(&Parser) -> T)
 609                               -> OptVec<T> {
 610         let v = self.parse_seq_to_before_gt(sep, f);
 611         self.expect_gt();
 612         return v;
 613     }
 614
 615     // parse a sequence, including the closing delimiter. The function
 616     // f must consume tokens until reaching the next separator or
 617     // closing bracket.
 618     pub fn parse_seq_to_end<T>(&self,
 619                                ket: &token::Token,
 620                                sep: SeqSep,
 621                                f: &fn(&Parser) -> T)
 622                                -> ~[T] {
 623         let val = self.parse_seq_to_before_end(ket, sep, f);
 624         self.bump();
 625         val
 626     }
 627
 628     // parse a sequence, not including the closing delimiter. The function
 629     // f must consume tokens until reaching the next separator or
 630     // closing bracket.
 631     pub fn parse_seq_to_before_end<T>(&self,
 632                                       ket: &token::Token,
 633                                       sep: SeqSep,
 634                                       f: &fn(&Parser) -> T)
 635                                       -> ~[T] {
 636         let mut first: bool = true;
 637         let mut v: ~[T] = ~[];
 638         while *self.token != *ket {
 639             match sep.sep {
 640               Some(ref t) => {
 641                 if first { first = false; }
 642                 else { self.expect(t); }
 643               }
 644               _ => ()
 645             }
 646             if sep.trailing_sep_allowed && *self.token == *ket { break; }
 647             v.push(f(self));
 648         }
 649         return v;
 650     }
 651
 652     // parse a sequence, including the closing delimiter. The function
 653     // f must consume tokens until reaching the next separator or
 654     // closing bracket.
 655     pub fn parse_unspanned_seq<T>(&self,
 656                                   bra: &token::Token,
 657                                   ket: &token::Token,
 658                                   sep: SeqSep,
 659                                   f: &fn(&Parser) -> T)
 660                                   -> ~[T] {
 661         self.expect(bra);
 662         let result = self.parse_seq_to_before_end(ket, sep, f);
 663         self.bump();
 664         result
 665     }
 666
 667     // NB: Do not use this function unless you actually plan to place the
 668     // spanned list in the AST.
 669     pub fn parse_seq<T>(&self,
 670                         bra: &token::Token,
 671                         ket: &token::Token,
 672                         sep: SeqSep,
 673                         f: &fn(&Parser) -> T)
 674                         -> Spanned<~[T]> {
 675         let lo = self.span.lo;
 676         self.expect(bra);
 677         let result = self.parse_seq_to_before_end(ket, sep, f);
 678         let hi = self.span.hi;
 679         self.bump();
 680         spanned(lo, hi, result)
 681     }
 682
 683     // advance the parser by one token
 684     pub fn bump(&self) {
 685         *self.last_span = *self.span;
 686         // Stash token for error recovery (sometimes; clone is not necessarily cheap).
 687         *self.last_token = if is_ident_or_path(self.token) {
 688             Some(~(*self.token).clone())
 689         } else {
 690             None
 691         };
 692         let next = if *self.buffer_start == *self.buffer_end {
 693             self.reader.next_token()
 694         } else {
 695             // Avoid token copies with `util::replace`.
 696             let buffer_start = *self.buffer_start as uint;
 697             let next_index = (buffer_start + 1) & 3 as uint;
 698             *self.buffer_start = next_index as int;
 699
 700             let placeholder = TokenAndSpan {
 701                 tok: token::UNDERSCORE,
 702                 sp: *self.span,
 703             };
 704             util::replace(&mut self.buffer[buffer_start], placeholder)
 705         };
 706         *self.span = next.sp;
 707         *self.token = next.tok;
 708         *self.tokens_consumed += 1u;
 709     }
 710
 711     // Advance the parser by one token and return the bumped token.
 712     pub fn bump_and_get(&self) -> token::Token {
 713         let old_token = util::replace(self.token, token::UNDERSCORE);
 714         self.bump();
 715         old_token
 716     }
 717
 718     // EFFECT: replace the current token and span with the given one
 719     pub fn replace_token(&self,
 720                          next: token::Token,
 721                          lo: BytePos,
 722                          hi: BytePos) {
 723         *self.token = next;
 724         *self.span = mk_sp(lo, hi);
 725     }
 726     pub fn buffer_length(&self) -> int {
 727         if *self.buffer_start <= *self.buffer_end {
 728             return *self.buffer_end - *self.buffer_start;
 729         }
 730         return (4 - *self.buffer_start) + *self.buffer_end;
 731     }
 732     pub fn look_ahead<R>(&self, distance: uint, f: &fn(&token::Token) -> R)
 733                          -> R {
 734         let dist = distance as int;
 735         while self.buffer_length() < dist {
 736             self.buffer[*self.buffer_end] = self.reader.next_token();
 737             *self.buffer_end = (*self.buffer_end + 1) & 3;
 738         }
 739         f(&self.buffer[(*self.buffer_start + dist - 1) & 3].tok)
 740     }
 741     pub fn fatal(&self, m: &str) -> ! {
 742         self.sess.span_diagnostic.span_fatal(*self.span, m)
 743     }
 744     pub fn span_fatal(&self, sp: Span, m: &str) -> ! {
 745         self.sess.span_diagnostic.span_fatal(sp, m)
 746     }
 747     pub fn span_note(&self, sp: Span, m: &str) {
 748         self.sess.span_diagnostic.span_note(sp, m)
 749     }
 750     pub fn bug(&self, m: &str) -> ! {
 751         self.sess.span_diagnostic.span_bug(*self.span, m)
 752     }
 753     pub fn warn(&self, m: &str) {
 754         self.sess.span_diagnostic.span_warn(*self.span, m)
 755     }
 756     pub fn span_err(&self, sp: Span, m: &str) {
 757         self.sess.span_diagnostic.span_err(sp, m)
 758     }
 759     pub fn abort_if_errors(&self) {
 760         self.sess.span_diagnostic.handler().abort_if_errors();
 761     }
 762
 763     pub fn id_to_str(&self, id: Ident) -> @str {
 764         get_ident_interner().get(id.name)
 765     }
 766
 767     // is this one of the keywords that signals a closure type?
 768     pub fn token_is_closure_keyword(&self, tok: &token::Token) -> bool {
 769         token::is_keyword(keywords::Unsafe, tok) ||
 770             token::is_keyword(keywords::Once, tok) ||
 771             token::is_keyword(keywords::Fn, tok)
 772     }
 773
 774     pub fn token_is_lifetime(&self, tok: &token::Token) -> bool {
 775         match *tok {
 776             token::LIFETIME(*) => true,
 777             _ => false,
 778         }
 779     }
 780
 781     pub fn get_lifetime(&self, tok: &token::Token) -> ast::Ident {
 782         match *tok {
 783             token::LIFETIME(ref ident) => *ident,
 784             _ => self.bug("not a lifetime"),
 785         }
 786     }
 787
 788     // parse a ty_bare_fun type:
 789     pub fn parse_ty_bare_fn(&self) -> ty_ {
 790         /*
 791
 792         extern "ABI" [unsafe] fn <'lt> (S) -> T
 793                ^~~~^ ^~~~~~~^    ^~~~^ ^~^    ^
 794                  |     |           |    |     |
 795                  |     |           |    |   Return type
 796                  |     |           |  Argument types
 797                  |     |       Lifetimes
 798                  |     |
 799                  |   Purity
 800                 ABI
 801
 802         */
 803
 804         let opt_abis = self.parse_opt_abis();
 805         let abis = opt_abis.unwrap_or(AbiSet::Rust());
 806         let purity = self.parse_unsafety();
 807         self.expect_keyword(keywords::Fn);
 808         let (decl, lifetimes) = self.parse_ty_fn_decl();
 809         return ty_bare_fn(@TyBareFn {
 810             abis: abis,
 811             purity: purity,
 812             lifetimes: lifetimes,
 813             decl: decl
 814         });
 815     }
 816
 817     // parse a ty_closure type
 818     pub fn parse_ty_closure(&self,
 819                             sigil: ast::Sigil,
 820                             region: Option<ast::Lifetime>)
 821                             -> ty_ {
 822         /*
 823
 824         (&|~|@) ['r] [unsafe] [once] fn [:Bounds] <'lt> (S) -> T
 825         ^~~~~~^ ^~~^ ^~~~~~~^ ^~~~~^    ^~~~~~~~^ ^~~~^ ^~^    ^
 826            |     |     |        |           |       |    |     |
 827            |     |     |        |           |       |    |   Return type
 828            |     |     |        |           |       |  Argument types
 829            |     |     |        |           |   Lifetimes
 830            |     |     |        |       Closure bounds
 831            |     |     |     Once-ness (a.k.a., affine)
 832            |     |   Purity
 833            | Lifetime bound
 834         Allocation type
 835
 836         */
 837
 838         // At this point, the allocation type and lifetime bound have been
 839         // parsed.
 840
 841         let purity = self.parse_unsafety();
 842         let onceness = parse_onceness(self);
 843         self.expect_keyword(keywords::Fn);
 844         let bounds = self.parse_optional_ty_param_bounds();
 845
 846         let (decl, lifetimes) = self.parse_ty_fn_decl();
 847
 848         return ty_closure(@TyClosure {
 849             sigil: sigil,
 850             region: region,
 851             purity: purity,
 852             onceness: onceness,
 853             bounds: bounds,
 854             decl: decl,
 855             lifetimes: lifetimes,
 856         });
 857
 858         fn parse_onceness(this: &Parser) -> Onceness {
 859             if this.eat_keyword(keywords::Once) {
 860                 Once
 861             } else {
 862                 Many
 863             }
 864         }
 865     }
 866
 867     pub fn parse_unsafety(&self) -> purity {
 868         if self.eat_keyword(keywords::Unsafe) {
 869             return unsafe_fn;
 870         } else {
 871             return impure_fn;
 872         }
 873     }
 874
 875     // parse a function type (following the 'fn')
 876     pub fn parse_ty_fn_decl(&self) -> (fn_decl, OptVec<ast::Lifetime>) {
 877         /*
 878
 879         (fn) <'lt> (S) -> T
 880              ^~~~^ ^~^    ^
 881                |    |     |
 882                |    |   Return type
 883                |  Argument types
 884            Lifetimes
 885
 886         */
 887         let lifetimes = if self.eat(&token::LT) {
 888             let lifetimes = self.parse_lifetimes();
 889             self.expect_gt();
 890             lifetimes
 891         } else {
 892             opt_vec::Empty
 893         };
 894
 895         let inputs = self.parse_unspanned_seq(
 896             &token::LPAREN,
 897             &token::RPAREN,
 898             seq_sep_trailing_disallowed(token::COMMA),
 899             |p| p.parse_arg_general(false)
 900         );
 901         let (ret_style, ret_ty) = self.parse_ret_ty();
 902         let decl = ast::fn_decl {
 903             inputs: inputs,
 904             output: ret_ty,
 905             cf: ret_style
 906         };
 907         (decl, lifetimes)
 908     }
 909
 910     // parse the methods in a trait declaration
 911     pub fn parse_trait_methods(&self) -> ~[trait_method] {
 912         do self.parse_unspanned_seq(
 913             &token::LBRACE,
 914             &token::RBRACE,
 915             seq_sep_none()
 916         ) |p| {
 917             let attrs = p.parse_outer_attributes();
 918             let lo = p.span.lo;
 919
 920             let vis_span = *self.span;
 921             let vis = p.parse_visibility();
 922             let pur = p.parse_fn_purity();
 923             // NB: at the moment, trait methods are public by default; this
 924             // could change.
 925             let ident = p.parse_ident();
 926
 927             let generics = p.parse_generics();
 928
 929             let (explicit_self, d) = do self.parse_fn_decl_with_self() |p| {
 930                 // This is somewhat dubious; We don't want to allow argument
 931                 // names to be left off if there is a definition...
 932                 p.parse_arg_general(false)
 933             };
 934
 935             let hi = p.last_span.hi;
 936             debug!("parse_trait_methods(): trait method signature ends in \
 937                     `{}`",
 938                    self.this_token_to_str());
 939             match *p.token {
 940               token::SEMI => {
 941                 p.bump();
 942                 debug!("parse_trait_methods(): parsing required method");
 943                 // NB: at the moment, visibility annotations on required
 944                 // methods are ignored; this could change.
 945                 if vis != ast::inherited {
 946                     self.obsolete(vis_span,
 947                                   ObsoleteTraitFuncVisibility);
 948                 }
 949                 required(TypeMethod {
 950                     ident: ident,
 951                     attrs: attrs,
 952                     purity: pur,
 953                     decl: d,
 954                     generics: generics,
 955                     explicit_self: explicit_self,
 956                     id: ast::DUMMY_NODE_ID,
 957                     span: mk_sp(lo, hi)
 958                 })
 959               }
 960               token::LBRACE => {
 961                 debug!("parse_trait_methods(): parsing provided method");
 962                 let (inner_attrs, body) =
 963                     p.parse_inner_attrs_and_block();
 964                 let attrs = vec::append(attrs, inner_attrs);
 965                 provided(@ast::method {
 966                     ident: ident,
 967                     attrs: attrs,
 968                     generics: generics,
 969                     explicit_self: explicit_self,
 970                     purity: pur,
 971                     decl: d,
 972                     body: body,
 973                     id: ast::DUMMY_NODE_ID,
 974                     span: mk_sp(lo, hi),
 975                     self_id: ast::DUMMY_NODE_ID,
 976                     vis: vis,
 977                 })
 978               }
 979
 980               _ => {
 981                     p.fatal(
 982                         format!(
 983                             "expected `;` or `\\{` but found `{}`",
 984                             self.this_token_to_str()
 985                         )
 986                     );
 987                 }
 988             }
 989         }
 990     }
 991
 992     // parse a possibly mutable type
 993     pub fn parse_mt(&self) -> mt {
 994         let mutbl = self.parse_mutability();
 995         let t = ~self.parse_ty(false);
 996         mt { ty: t, mutbl: mutbl }
 997     }
 998
 999     // parse [mut/const/imm] ID : TY
1000     // now used only by obsolete record syntax parser...
1001     pub fn parse_ty_field(&self) -> TypeField {
1002         let lo = self.span.lo;
1003         let mutbl = self.parse_mutability();
1004         let id = self.parse_ident();
1005         self.expect(&token::COLON);
1006         let ty = ~self.parse_ty(false);
1007         let hi = ty.span.hi;
1008         ast::TypeField {
1009             ident: id,
1010             mt: ast::mt { ty: ty, mutbl: mutbl },
1011             span: mk_sp(lo, hi),
1012         }
1013     }
1014
1015     // parse optional return type [ -> TY ] in function decl
1016     pub fn parse_ret_ty(&self) -> (ret_style, Ty) {
1017         return if self.eat(&token::RARROW) {
1018             let lo = self.span.lo;
1019             if self.eat(&token::NOT) {
1020                 (
1021                     noreturn,
1022                     Ty {
1023                         id: ast::DUMMY_NODE_ID,
1024                         node: ty_bot,
1025                         span: mk_sp(lo, self.last_span.hi)
1026                     }
1027                 )
1028             } else {
1029                 (return_val, self.parse_ty(false))
1030             }
1031         } else {
1032             let pos = self.span.lo;
1033             (
1034                 return_val,
1035                 Ty {
1036                     id: ast::DUMMY_NODE_ID,
1037                     node: ty_nil,
1038                     span: mk_sp(pos, pos),
1039                 }
1040             )
1041         }
1042     }
1043
1044     // parse a type.
1045     // Useless second parameter for compatibility with quasiquote macros.
1046     // Bleh!
1047     pub fn parse_ty(&self, _: bool) -> Ty {
1048         maybe_whole!(deref self, nt_ty);
1049
1050         let lo = self.span.lo;
1051
1052         let t = if *self.token == token::LPAREN {
1053             self.bump();
1054             if *self.token == token::RPAREN {
1055                 self.bump();
1056                 ty_nil
1057             } else {
1058                 // (t) is a parenthesized ty
1059                 // (t,) is the type of a tuple with only one field,
1060                 // of type t
1061                 let mut ts = ~[self.parse_ty(false)];
1062                 let mut one_tuple = false;
1063                 while *self.token == token::COMMA {
1064                     self.bump();
1065                     if *self.token != token::RPAREN {
1066                         ts.push(self.parse_ty(false));
1067                     }
1068                     else {
1069                         one_tuple = true;
1070                     }
1071                 }
1072
1073                 if ts.len() == 1 && !one_tuple {
1074                     self.expect(&token::RPAREN);
1075                     return ts[0]
1076                 }
1077
1078                 let t = ty_tup(ts);
1079                 self.expect(&token::RPAREN);
1080                 t
1081             }
1082         } else if *self.token == token::AT {
1083             // MANAGED POINTER
1084             self.bump();
1085             self.parse_box_or_uniq_pointee(ManagedSigil, ty_box)
1086         } else if *self.token == token::TILDE {
1087             // OWNED POINTER
1088             self.bump();
1089             self.parse_box_or_uniq_pointee(OwnedSigil, ty_uniq)
1090         } else if *self.token == token::BINOP(token::STAR) {
1091             // STAR POINTER (bare pointer?)
1092             self.bump();
1093             ty_ptr(self.parse_mt())
1094         } else if *self.token == token::LBRACKET {
1095             // VECTOR
1096             self.expect(&token::LBRACKET);
1097             let mt = mt { ty: ~self.parse_ty(false), mutbl: MutImmutable };
1098
1099             // Parse the `, ..e` in `[ int, ..e ]`
1100             // where `e` is a const expression
1101             let t = match self.maybe_parse_fixed_vstore() {
1102                 None => ty_vec(mt),
1103                 Some(suffix) => ty_fixed_length_vec(mt, suffix)
1104             };
1105             self.expect(&token::RBRACKET);
1106             t
1107         } else if *self.token == token::BINOP(token::AND) {
1108             // BORROWED POINTER
1109             self.bump();
1110             self.parse_borrowed_pointee()
1111         } else if self.eat_keyword(keywords::Extern) {
1112             // EXTERN FUNCTION
1113             self.parse_ty_bare_fn()
1114         } else if self.token_is_closure_keyword(self.token) {
1115             // CLOSURE
1116             let result = self.parse_ty_closure(ast::BorrowedSigil, None);
1117             self.obsolete(*self.last_span, ObsoleteBareFnType);
1118             result
1119         } else if self.eat_keyword(keywords::Typeof) {
1120             // TYPEOF
1121             // In order to not be ambiguous, the type must be surrounded by parens.
1122             self.expect(&token::LPAREN);
1123             let e = self.parse_expr();
1124             self.expect(&token::RPAREN);
1125             ty_typeof(e)
1126         } else if *self.token == token::MOD_SEP
1127             || is_ident_or_path(self.token) {
1128             // NAMED TYPE
1129             let PathAndBounds {
1130                 path,
1131                 bounds
1132             } = self.parse_path(LifetimeAndTypesAndBounds);
1133             ty_path(path, bounds, ast::DUMMY_NODE_ID)
1134         } else {
1135             self.fatal(format!("expected type, found token {:?}", *self.token));
1136         };
1137
1138         let sp = mk_sp(lo, self.last_span.hi);
1139         Ty {id: ast::DUMMY_NODE_ID, node: t, span: sp}
1140     }
1141
1142     // parse the type following a @ or a ~
1143     pub fn parse_box_or_uniq_pointee(&self,
1144                                      sigil: ast::Sigil,
1145                                      ctor: &fn(v: mt) -> ty_) -> ty_ {
1146         // ~'foo fn() or ~fn() are parsed directly as fn types:
1147         match *self.token {
1148             token::LIFETIME(*) => {
1149                 let lifetime = self.parse_lifetime();
1150                 return self.parse_ty_closure(sigil, Some(lifetime));
1151             }
1152
1153             token::IDENT(*) => {
1154                 if self.token_is_closure_keyword(self.token) {
1155                     return self.parse_ty_closure(sigil, None);
1156                 }
1157             }
1158             _ => {}
1159         }
1160
1161         // other things are parsed as @/~ + a type.  Note that constructs like
1162         // @[] and @str will be resolved during typeck to slices and so forth,
1163         // rather than boxed ptrs.  But the special casing of str/vec is not
1164         // reflected in the AST type.
1165         if sigil == OwnedSigil {
1166             ctor(mt { ty: ~self.parse_ty(false), mutbl: MutImmutable })
1167         } else {
1168             ctor(self.parse_mt())
1169         }
1170     }
1171
1172     pub fn parse_borrowed_pointee(&self) -> ty_ {
1173         // look for `&'lt` or `&'foo ` and interpret `foo` as the region name:
1174         let opt_lifetime = self.parse_opt_lifetime();
1175
1176         if self.token_is_closure_keyword(self.token) {
1177             return self.parse_ty_closure(BorrowedSigil, opt_lifetime);
1178         }
1179
1180         let mt = self.parse_mt();
1181         return ty_rptr(opt_lifetime, mt);
1182     }
1183
1184     pub fn is_named_argument(&self) -> bool {
1185         let offset = match *self.token {
1186             token::BINOP(token::AND) => 1,
1187             token::BINOP(token::MINUS) => 1,
1188             token::ANDAND => 1,
1189             token::BINOP(token::PLUS) => {
1190                 if self.look_ahead(1, |t| *t == token::BINOP(token::PLUS)) {
1191                     2
1192                 } else {
1193                     1
1194                 }
1195             },
1196             _ => 0
1197         };
1198
1199         debug!("parser is_named_argument offset:{}", offset);
1200
1201         if offset == 0 {
1202             is_plain_ident_or_underscore(&*self.token)
1203                 && self.look_ahead(1, |t| *t == token::COLON)
1204         } else {
1205             self.look_ahead(offset, |t| is_plain_ident_or_underscore(t))
1206                 && self.look_ahead(offset + 1, |t| *t == token::COLON)
1207         }
1208     }
1209
1210     // This version of parse arg doesn't necessarily require
1211     // identifier names.
1212     pub fn parse_arg_general(&self, require_name: bool) -> arg {
1213         let is_mutbl = self.eat_keyword(keywords::Mut);
1214         let pat = if require_name || self.is_named_argument() {
1215             debug!("parse_arg_general parse_pat (require_name:{:?})",
1216                    require_name);
1217             let pat = self.parse_pat();
1218
1219             if is_mutbl && !ast_util::pat_is_ident(pat) {
1220                 self.obsolete(*self.span, ObsoleteMutWithMultipleBindings)
1221             }
1222
1223             self.expect(&token::COLON);
1224             pat
1225         } else {
1226             debug!("parse_arg_general ident_to_pat");
1227             ast_util::ident_to_pat(ast::DUMMY_NODE_ID,
1228                                    *self.last_span,
1229                                    special_idents::invalid)
1230         };
1231
1232         let t = self.parse_ty(false);
1233
1234         ast::arg {
1235             is_mutbl: is_mutbl,
1236             ty: t,
1237             pat: pat,
1238             id: ast::DUMMY_NODE_ID,
1239         }
1240     }
1241
1242     // parse a single function argument
1243     pub fn parse_arg(&self) -> arg {
1244         self.parse_arg_general(true)
1245     }
1246
1247     // parse an argument in a lambda header e.g. |arg, arg|
1248     pub fn parse_fn_block_arg(&self) -> arg {
1249         let is_mutbl = self.eat_keyword(keywords::Mut);
1250         let pat = self.parse_pat();
1251         let t = if self.eat(&token::COLON) {
1252             self.parse_ty(false)
1253         } else {
1254             Ty {
1255                 id: ast::DUMMY_NODE_ID,
1256                 node: ty_infer,
1257                 span: mk_sp(self.span.lo, self.span.hi),
1258             }
1259         };
1260         ast::arg {
1261             is_mutbl: is_mutbl,
1262             ty: t,
1263             pat: pat,
1264             id: ast::DUMMY_NODE_ID
1265         }
1266     }
1267
1268     pub fn maybe_parse_fixed_vstore(&self) -> Option<@ast::Expr> {
1269         if *self.token == token::COMMA &&
1270                 self.look_ahead(1, |t| *t == token::DOTDOT) {
1271             self.bump();
1272             self.bump();
1273             Some(self.parse_expr())
1274         } else {
1275             None
1276         }
1277     }
1278
1279     // matches token_lit = LIT_INT | ...
1280     pub fn lit_from_token(&self, tok: &token::Token) -> lit_ {
1281         match *tok {
1282             token::LIT_CHAR(i) => lit_char(i),
1283             token::LIT_INT(i, it) => lit_int(i, it),
1284             token::LIT_UINT(u, ut) => lit_uint(u, ut),
1285             token::LIT_INT_UNSUFFIXED(i) => lit_int_unsuffixed(i),
1286             token::LIT_FLOAT(s, ft) => lit_float(self.id_to_str(s), ft),
1287             token::LIT_FLOAT_UNSUFFIXED(s) =>
1288                 lit_float_unsuffixed(self.id_to_str(s)),
1289             token::LIT_STR(s) => lit_str(self.id_to_str(s), ast::CookedStr),
1290             token::LIT_STR_RAW(s, n) => lit_str(self.id_to_str(s), ast::RawStr(n)),
1291             token::LPAREN => { self.expect(&token::RPAREN); lit_nil },
1292             _ => { self.unexpected_last(tok); }
1293         }
1294     }
1295
1296     // matches lit = true | false | token_lit
1297     pub fn parse_lit(&self) -> lit {
1298         let lo = self.span.lo;
1299         let lit = if self.eat_keyword(keywords::True) {
1300             lit_bool(true)
1301         } else if self.eat_keyword(keywords::False) {
1302             lit_bool(false)
1303         } else {
1304             let token = self.bump_and_get();
1305             let lit = self.lit_from_token(&token);
1306             lit
1307         };
1308         codemap::Spanned { node: lit, span: mk_sp(lo, self.last_span.hi) }
1309     }
1310
1311     // matches '-' lit | lit
1312     pub fn parse_literal_maybe_minus(&self) -> @Expr {
1313         let minus_lo = self.span.lo;
1314         let minus_present = self.eat(&token::BINOP(token::MINUS));
1315
1316         let lo = self.span.lo;
1317         let literal = @self.parse_lit();
1318         let hi = self.span.hi;
1319         let expr = self.mk_expr(lo, hi, ExprLit(literal));
1320
1321         if minus_present {
1322             let minus_hi = self.span.hi;
1323             self.mk_expr(minus_lo, minus_hi, self.mk_unary(UnNeg, expr))
1324         } else {
1325             expr
1326         }
1327     }
1328
1329     /// Parses a path and optional type parameter bounds, depending on the
1330     /// mode. The `mode` parameter determines whether lifetimes, types, and/or
1331     /// bounds are permitted and whether `::` must precede type parameter
1332     /// groups.
1333     pub fn parse_path(&self, mode: PathParsingMode) -> PathAndBounds {
1334         // Check for a whole path...
1335         let found = match *self.token {
1336             INTERPOLATED(token::nt_path(_)) => Some(self.bump_and_get()),
1337             _ => None,
1338         };
1339         match found {
1340             Some(INTERPOLATED(token::nt_path(~path))) => {
1341                 return PathAndBounds {
1342                     path: path,
1343                     bounds: None,
1344                 }
1345             }
1346             _ => {}
1347         }
1348
1349         let lo = self.span.lo;
1350         let is_global = self.eat(&token::MOD_SEP);
1351
1352         // Parse any number of segments and bound sets. A segment is an
1353         // identifier followed by an optional lifetime and a set of types.
1354         // A bound set is a set of type parameter bounds.
1355         let mut segments = ~[];
1356         loop {
1357             // First, parse an identifier.
1358             match *self.token {
1359                 token::IDENT(*) => {}
1360                 _ => break,
1361             }
1362             let identifier = self.parse_ident();
1363
1364             // Next, parse a colon and bounded type parameters, if applicable.
1365             let bound_set = if mode == LifetimeAndTypesAndBounds {
1366                 self.parse_optional_ty_param_bounds()
1367             } else {
1368                 None
1369             };
1370
1371             // Parse the '::' before type parameters if it's required. If
1372             // it is required and wasn't present, then we're done.
1373             if mode == LifetimeAndTypesWithColons &&
1374                     !self.eat(&token::MOD_SEP) {
1375                 segments.push(PathSegmentAndBoundSet {
1376                     segment: ast::PathSegment {
1377                         identifier: identifier,
1378                         lifetime: None,
1379                         types: opt_vec::Empty,
1380                     },
1381                     bound_set: bound_set
1382                 });
1383                 break
1384             }
1385
1386             // Parse the `<` before the lifetime and types, if applicable.
1387             let (any_lifetime_or_types, optional_lifetime, types) =
1388                     if mode != NoTypesAllowed && self.eat(&token::LT) {
1389                 // Parse an optional lifetime.
1390                 let optional_lifetime = match *self.token {
1391                     token::LIFETIME(*) => Some(self.parse_lifetime()),
1392                     _ => None,
1393                 };
1394
1395                 // Parse type parameters.
1396                 let mut types = opt_vec::Empty;
1397                 let mut need_comma = optional_lifetime.is_some();
1398                 loop {
1399                     // We're done if we see a `>`.
1400                     match *self.token {
1401                         token::GT | token::BINOP(token::SHR) => {
1402                             self.expect_gt();
1403                             break
1404                         }
1405                         _ => {} // Go on.
1406                     }
1407
1408                     if need_comma {
1409                         self.expect(&token::COMMA)
1410                     } else {
1411                         need_comma = true
1412                     }
1413
1414                     types.push(self.parse_ty(false))
1415                 }
1416
1417                 (true, optional_lifetime, types)
1418             } else {
1419                 (false, None, opt_vec::Empty)
1420             };
1421
1422             // Assemble and push the result.
1423             segments.push(PathSegmentAndBoundSet {
1424                 segment: ast::PathSegment {
1425                     identifier: identifier,
1426                     lifetime: optional_lifetime,
1427                     types: types,
1428                 },
1429                 bound_set: bound_set
1430             });
1431
1432             // We're done if we don't see a '::', unless the mode required
1433             // a double colon to get here in the first place.
1434             if !(mode == LifetimeAndTypesWithColons &&
1435                     !any_lifetime_or_types) {
1436                 if !self.eat(&token::MOD_SEP) {
1437                     break
1438                 }
1439             }
1440         }
1441
1442         // Assemble the span.
1443         let span = mk_sp(lo, self.last_span.hi);
1444
1445         // Assemble the path segments.
1446         let mut path_segments = ~[];
1447         let mut bounds = None;
1448         let last_segment_index = segments.len() - 1;
1449         for (i, segment_and_bounds) in segments.move_iter().enumerate() {
1450             let PathSegmentAndBoundSet {
1451                 segment: segment,
1452                 bound_set: bound_set
1453             } = segment_and_bounds;
1454             path_segments.push(segment);
1455
1456             if bound_set.is_some() {
1457                 if i != last_segment_index {
1458                     self.span_err(span,
1459                                   "type parameter bounds are allowed only \
1460                                    before the last segment in a path")
1461                 }
1462
1463                 bounds = bound_set
1464             }
1465         }
1466
1467         // Assemble the result.
1468         let path_and_bounds = PathAndBounds {
1469             path: ast::Path {
1470                 span: span,
1471                 global: is_global,
1472                 segments: path_segments,
1473             },
1474             bounds: bounds,
1475         };
1476
1477         path_and_bounds
1478     }
1479
1480     /// parses 0 or 1 lifetime
1481     pub fn parse_opt_lifetime(&self) -> Option<ast::Lifetime> {
1482         match *self.token {
1483             token::LIFETIME(*) => {
1484                 Some(self.parse_lifetime())
1485             }
1486             _ => {
1487                 None
1488             }
1489         }
1490     }
1491
1492     /// Parses a single lifetime
1493     // matches lifetime = LIFETIME
1494     pub fn parse_lifetime(&self) -> ast::Lifetime {
1495         match *self.token {
1496             token::LIFETIME(i) => {
1497                 let span = self.span;
1498                 self.bump();
1499                 return ast::Lifetime {
1500                     id: ast::DUMMY_NODE_ID,
1501                     span: *span,
1502                     ident: i
1503                 };
1504             }
1505             _ => {
1506                 self.fatal(format!("Expected a lifetime name"));
1507             }
1508         }
1509     }
1510
1511     // matches lifetimes = ( lifetime ) | ( lifetime , lifetimes )
1512     // actually, it matches the empty one too, but putting that in there
1513     // messes up the grammar....
1514     pub fn parse_lifetimes(&self) -> OptVec<ast::Lifetime> {
1515         /*!
1516          *
1517          * Parses zero or more comma separated lifetimes.
1518          * Expects each lifetime to be followed by either
1519          * a comma or `>`.  Used when parsing type parameter
1520          * lists, where we expect something like `<'a, 'b, T>`.
1521          */
1522
1523         let mut res = opt_vec::Empty;
1524         loop {
1525             match *self.token {
1526                 token::LIFETIME(_) => {
1527                     res.push(self.parse_lifetime());
1528                 }
1529                 _ => {
1530                     return res;
1531                 }
1532             }
1533
1534             match *self.token {
1535                 token::COMMA => { self.bump();}
1536                 token::GT => { return res; }
1537                 token::BINOP(token::SHR) => { return res; }
1538                 _ => {
1539                     self.fatal(format!("expected `,` or `>` after lifetime name, got: {:?}",
1540                                     *self.token));
1541                 }
1542             }
1543         }
1544     }
1545
1546     pub fn token_is_mutability(&self, tok: &token::Token) -> bool {
1547         token::is_keyword(keywords::Mut, tok) ||
1548         token::is_keyword(keywords::Const, tok)
1549     }
1550
1551     // parse mutability declaration (mut/const/imm)
1552     pub fn parse_mutability(&self) -> Mutability {
1553         if self.eat_keyword(keywords::Mut) {
1554             MutMutable
1555         } else if self.eat_keyword(keywords::Const) {
1556             self.obsolete(*self.last_span, ObsoleteConstPointer);
1557             MutImmutable
1558         } else {
1559             MutImmutable
1560         }
1561     }
1562
1563     // parse ident COLON expr
1564     pub fn parse_field(&self) -> Field {
1565         let lo = self.span.lo;
1566         let i = self.parse_ident();
1567         self.expect(&token::COLON);
1568         let e = self.parse_expr();
1569         ast::Field {
1570             ident: i,
1571             expr: e,
1572             span: mk_sp(lo, e.span.hi),
1573         }
1574     }
1575
1576     pub fn mk_expr(&self, lo: BytePos, hi: BytePos, node: Expr_) -> @Expr {
1577         @Expr {
1578             id: ast::DUMMY_NODE_ID,
1579             node: node,
1580             span: mk_sp(lo, hi),
1581         }
1582     }
1583
1584     pub fn mk_unary(&self, unop: ast::UnOp, expr: @Expr) -> ast::Expr_ {
1585         ExprUnary(ast::DUMMY_NODE_ID, unop, expr)
1586     }
1587
1588     pub fn mk_binary(&self, binop: ast::BinOp, lhs: @Expr, rhs: @Expr) -> ast::Expr_ {
1589         ExprBinary(ast::DUMMY_NODE_ID, binop, lhs, rhs)
1590     }
1591
1592     pub fn mk_call(&self, f: @Expr, args: ~[@Expr], sugar: CallSugar) -> ast::Expr_ {
1593         ExprCall(f, args, sugar)
1594     }
1595
1596     pub fn mk_method_call(&self,
1597                       rcvr: @Expr,
1598                       ident: Ident,
1599                       tps: ~[Ty],
1600                       args: ~[@Expr],
1601                       sugar: CallSugar) -> ast::Expr_ {
1602         ExprMethodCall(ast::DUMMY_NODE_ID, rcvr, ident, tps, args, sugar)
1603     }
1604
1605     pub fn mk_index(&self, expr: @Expr, idx: @Expr) -> ast::Expr_ {
1606         ExprIndex(ast::DUMMY_NODE_ID, expr, idx)
1607     }
1608
1609     pub fn mk_field(&self, expr: @Expr, ident: Ident, tys: ~[Ty]) -> ast::Expr_ {
1610         ExprField(expr, ident, tys)
1611     }
1612
1613     pub fn mk_assign_op(&self, binop: ast::BinOp, lhs: @Expr, rhs: @Expr) -> ast::Expr_ {
1614         ExprAssignOp(ast::DUMMY_NODE_ID, binop, lhs, rhs)
1615     }
1616
1617     pub fn mk_mac_expr(&self, lo: BytePos, hi: BytePos, m: mac_) -> @Expr {
1618         @Expr {
1619             id: ast::DUMMY_NODE_ID,
1620             node: ExprMac(codemap::Spanned {node: m, span: mk_sp(lo, hi)}),
1621             span: mk_sp(lo, hi),
1622         }
1623     }
1624
1625     pub fn mk_lit_u32(&self, i: u32) -> @Expr {
1626         let span = self.span;
1627         let lv_lit = @codemap::Spanned {
1628             node: lit_uint(i as u64, ty_u32),
1629             span: *span
1630         };
1631
1632         @Expr {
1633             id: ast::DUMMY_NODE_ID,
1634             node: ExprLit(lv_lit),
1635             span: *span,
1636         }
1637     }
1638
1639     // at the bottom (top?) of the precedence hierarchy,
1640     // parse things like parenthesized exprs,
1641     // macros, return, etc.
1642     pub fn parse_bottom_expr(&self) -> @Expr {
1643         maybe_whole_expr!(self);
1644
1645         let lo = self.span.lo;
1646         let mut hi = self.span.hi;
1647
1648         let ex: Expr_;
1649
1650         if *self.token == token::LPAREN {
1651             self.bump();
1652             // (e) is parenthesized e
1653             // (e,) is a tuple with only one field, e
1654             let mut trailing_comma = false;
1655             if *self.token == token::RPAREN {
1656                 hi = self.span.hi;
1657                 self.bump();
1658                 let lit = @spanned(lo, hi, lit_nil);
1659                 return self.mk_expr(lo, hi, ExprLit(lit));
1660             }
1661             let mut es = ~[self.parse_expr()];
1662             self.commit_expr(*es.last(), &[], &[token::COMMA, token::RPAREN]);
1663             while *self.token == token::COMMA {
1664                 self.bump();
1665                 if *self.token != token::RPAREN {
1666                     es.push(self.parse_expr());
1667                     self.commit_expr(*es.last(), &[], &[token::COMMA, token::RPAREN]);
1668                 }
1669                 else {
1670                     trailing_comma = true;
1671                 }
1672             }
1673             hi = self.span.hi;
1674             self.commit_expr_expecting(*es.last(), token::RPAREN);
1675
1676             return if es.len() == 1 && !trailing_comma {
1677                 self.mk_expr(lo, self.span.hi, ExprParen(es[0]))
1678             }
1679             else {
1680                 self.mk_expr(lo, hi, ExprTup(es))
1681             }
1682         } else if *self.token == token::LBRACE {
1683             self.bump();
1684             let blk = self.parse_block_tail(lo, DefaultBlock);
1685             return self.mk_expr(blk.span.lo, blk.span.hi,
1686                                  ExprBlock(blk));
1687         } else if token::is_bar(&*self.token) {
1688             return self.parse_lambda_expr();
1689         } else if self.eat_keyword(keywords::Self) {
1690             ex = ExprSelf;
1691             hi = self.span.hi;
1692         } else if self.eat_keyword(keywords::If) {
1693             return self.parse_if_expr();
1694         } else if self.eat_keyword(keywords::For) {
1695             return self.parse_for_expr(None);
1696         } else if self.eat_keyword(keywords::Do) {
1697             return self.parse_sugary_call_expr(lo, ~"do", DoSugar,
1698                                                ExprDoBody);
1699         } else if self.eat_keyword(keywords::While) {
1700             return self.parse_while_expr();
1701         } else if self.token_is_lifetime(&*self.token) {
1702             let lifetime = self.get_lifetime(&*self.token);
1703             self.bump();
1704             self.expect(&token::COLON);
1705             if self.eat_keyword(keywords::For) {
1706                 return self.parse_for_expr(Some(lifetime))
1707             } else if self.eat_keyword(keywords::Loop) {
1708                 return self.parse_loop_expr(Some(lifetime))
1709             } else {
1710                 self.fatal("expected `for` or `loop` after a label")
1711             }
1712         } else if self.eat_keyword(keywords::Loop) {
1713             return self.parse_loop_expr(None);
1714         } else if self.eat_keyword(keywords::Continue) {
1715             let lo = self.span.lo;
1716             let ex = if self.token_is_lifetime(&*self.token) {
1717                 let lifetime = self.get_lifetime(&*self.token);
1718                 self.bump();
1719                 ExprAgain(Some(lifetime.name))
1720             } else {
1721                 ExprAgain(None)
1722             };
1723             let hi = self.span.hi;
1724             return self.mk_expr(lo, hi, ex);
1725         } else if self.eat_keyword(keywords::Match) {
1726             return self.parse_match_expr();
1727         } else if self.eat_keyword(keywords::Unsafe) {
1728             return self.parse_block_expr(lo, UnsafeBlock(ast::UserProvided));
1729         } else if *self.token == token::LBRACKET {
1730             self.bump();
1731             let mutbl = MutImmutable;
1732
1733             if *self.token == token::RBRACKET {
1734                 // Empty vector.
1735                 self.bump();
1736                 ex = ExprVec(~[], mutbl);
1737             } else {
1738                 // Nonempty vector.
1739                 let first_expr = self.parse_expr();
1740                 if *self.token == token::COMMA &&
1741                         self.look_ahead(1, |t| *t == token::DOTDOT) {
1742                     // Repeating vector syntax: [ 0, ..512 ]
1743                     self.bump();
1744                     self.bump();
1745                     let count = self.parse_expr();
1746                     self.expect(&token::RBRACKET);
1747                     ex = ExprRepeat(first_expr, count, mutbl);
1748                 } else if *self.token == token::COMMA {
1749                     // Vector with two or more elements.
1750                     self.bump();
1751                     let remaining_exprs = self.parse_seq_to_end(
1752                         &token::RBRACKET,
1753                         seq_sep_trailing_allowed(token::COMMA),
1754                         |p| p.parse_expr()
1755                     );
1756                     ex = ExprVec(~[first_expr] + remaining_exprs, mutbl);
1757                 } else {
1758                     // Vector with one element.
1759                     self.expect(&token::RBRACKET);
1760                     ex = ExprVec(~[first_expr], mutbl);
1761                 }
1762             }
1763             hi = self.last_span.hi;
1764         } else if self.eat_keyword(keywords::__LogLevel) {
1765             // LOG LEVEL expression
1766             self.expect(&token::LPAREN);
1767             ex = ExprLogLevel;
1768             hi = self.span.hi;
1769             self.expect(&token::RPAREN);
1770         } else if self.eat_keyword(keywords::Return) {
1771             // RETURN expression
1772             if can_begin_expr(&*self.token) {
1773                 let e = self.parse_expr();
1774                 hi = e.span.hi;
1775                 ex = ExprRet(Some(e));
1776             } else { ex = ExprRet(None); }
1777         } else if self.eat_keyword(keywords::Break) {
1778             // BREAK expression
1779             if self.token_is_lifetime(&*self.token) {
1780                 let lifetime = self.get_lifetime(&*self.token);
1781                 self.bump();
1782                 ex = ExprBreak(Some(lifetime.name));
1783             } else {
1784                 ex = ExprBreak(None);
1785             }
1786             hi = self.span.hi;
1787         } else if *self.token == token::MOD_SEP ||
1788                 is_ident(&*self.token) && !self.is_keyword(keywords::True) &&
1789                 !self.is_keyword(keywords::False) {
1790             let pth = self.parse_path(LifetimeAndTypesWithColons).path;
1791
1792             // `!`, as an operator, is prefix, so we know this isn't that
1793             if *self.token == token::NOT {
1794                 // MACRO INVOCATION expression
1795                 self.bump();
1796                 match *self.token {
1797                     token::LPAREN | token::LBRACE => {}
1798                     _ => self.fatal("expected open delimiter")
1799                 };
1800
1801                 let ket = token::flip_delimiter(&*self.token);
1802                 self.bump();
1803
1804                 let tts = self.parse_seq_to_end(&ket,
1805                                                 seq_sep_none(),
1806                                                 |p| p.parse_token_tree());
1807                 let hi = self.span.hi;
1808
1809                 return self.mk_mac_expr(lo, hi, mac_invoc_tt(pth, tts, EMPTY_CTXT));
1810             } else if *self.token == token::LBRACE {
1811                 // This might be a struct literal.
1812                 if self.looking_at_record_literal() {
1813                     // It's a struct literal.
1814                     self.bump();
1815                     let mut fields = ~[];
1816                     let mut base = None;
1817
1818                     fields.push(self.parse_field());
1819                     while *self.token != token::RBRACE {
1820                         self.commit_expr(fields.last().expr, &[token::COMMA], &[token::RBRACE]);
1821
1822                         if self.eat(&token::DOTDOT) {
1823                             base = Some(self.parse_expr());
1824                             break;
1825                         }
1826
1827                         if *self.token == token::RBRACE {
1828                             // Accept an optional trailing comma.
1829                             break;
1830                         }
1831                         fields.push(self.parse_field());
1832                     }
1833
1834                     hi = pth.span.hi;
1835                     self.commit_expr_expecting(fields.last().expr, token::RBRACE);
1836                     ex = ExprStruct(pth, fields, base);
1837                     return self.mk_expr(lo, hi, ex);
1838                 }
1839             }
1840
1841             hi = pth.span.hi;
1842             ex = ExprPath(pth);
1843         } else {
1844             // other literal expression
1845             let lit = self.parse_lit();
1846             hi = lit.span.hi;
1847             ex = ExprLit(@lit);
1848         }
1849
1850         return self.mk_expr(lo, hi, ex);
1851     }
1852
1853     // parse a block or unsafe block
1854     pub fn parse_block_expr(&self, lo: BytePos, blk_mode: BlockCheckMode)
1855                             -> @Expr {
1856         self.expect(&token::LBRACE);
1857         let blk = self.parse_block_tail(lo, blk_mode);
1858         return self.mk_expr(blk.span.lo, blk.span.hi, ExprBlock(blk));
1859     }
1860
1861     // parse a.b or a(13) or a[4] or just a
1862     pub fn parse_dot_or_call_expr(&self) -> @Expr {
1863         let b = self.parse_bottom_expr();
1864         self.parse_dot_or_call_expr_with(b)
1865     }
1866
1867     pub fn parse_dot_or_call_expr_with(&self, e0: @Expr) -> @Expr {
1868         let mut e = e0;
1869         let lo = e.span.lo;
1870         let mut hi;
1871         loop {
1872             // expr.f
1873             if self.eat(&token::DOT) {
1874                 match *self.token {
1875                   token::IDENT(i, _) => {
1876                     hi = self.span.hi;
1877                     self.bump();
1878                     let (_, tys) = if self.eat(&token::MOD_SEP) {
1879                         self.expect(&token::LT);
1880                         self.parse_generic_values_after_lt()
1881                     } else {
1882                         (opt_vec::Empty, ~[])
1883                     };
1884
1885                     // expr.f() method call
1886                     match *self.token {
1887                         token::LPAREN => {
1888                             let es = self.parse_unspanned_seq(
1889                                 &token::LPAREN,
1890                                 &token::RPAREN,
1891                                 seq_sep_trailing_disallowed(token::COMMA),
1892                                 |p| p.parse_expr()
1893                             );
1894                             hi = self.span.hi;
1895
1896                             let nd = self.mk_method_call(e, i, tys, es, NoSugar);
1897                             e = self.mk_expr(lo, hi, nd);
1898                         }
1899                         _ => {
1900                             e = self.mk_expr(lo, hi, self.mk_field(e, i, tys));
1901                         }
1902                     }
1903                   }
1904                   _ => self.unexpected()
1905                 }
1906                 continue;
1907             }
1908             if self.expr_is_complete(e) { break; }
1909             match *self.token {
1910               // expr(...)
1911               token::LPAREN => {
1912                 let es = self.parse_unspanned_seq(
1913                     &token::LPAREN,
1914                     &token::RPAREN,
1915                     seq_sep_trailing_disallowed(token::COMMA),
1916                     |p| p.parse_expr()
1917                 );
1918                 hi = self.span.hi;
1919
1920                 let nd = self.mk_call(e, es, NoSugar);
1921                 e = self.mk_expr(lo, hi, nd);
1922               }
1923
1924               // expr[...]
1925               token::LBRACKET => {
1926                 self.bump();
1927                 let ix = self.parse_expr();
1928                 hi = ix.span.hi;
1929                 self.commit_expr_expecting(ix, token::RBRACKET);
1930                 e = self.mk_expr(lo, hi, self.mk_index(e, ix));
1931               }
1932
1933               _ => return e
1934             }
1935         }
1936         return e;
1937     }
1938
1939     // parse an optional separator followed by a kleene-style
1940     // repetition token (+ or *).
1941     pub fn parse_sep_and_zerok(&self) -> (Option<token::Token>, bool) {
1942         fn parse_zerok(parser: &Parser) -> Option<bool> {
1943             match *parser.token {
1944                 token::BINOP(token::STAR) | token::BINOP(token::PLUS) => {
1945                     let zerok = *parser.token == token::BINOP(token::STAR);
1946                     parser.bump();
1947                     Some(zerok)
1948                 },
1949                 _ => None
1950             }
1951         };
1952
1953         match parse_zerok(self) {
1954             Some(zerok) => return (None, zerok),
1955             None => {}
1956         }
1957
1958         let separator = self.bump_and_get();
1959         match parse_zerok(self) {
1960             Some(zerok) => (Some(separator), zerok),
1961             None => self.fatal("expected `*` or `+`")
1962         }
1963     }
1964
1965     // parse a single token tree from the input.
1966     pub fn parse_token_tree(&self) -> token_tree {
1967         // FIXME #6994: currently, this is too eager. It
1968         // parses token trees but also identifies tt_seq's
1969         // and tt_nonterminals; it's too early to know yet
1970         // whether something will be a nonterminal or a seq
1971         // yet.
1972         maybe_whole!(deref self, nt_tt);
1973
1974         // this is the fall-through for the 'match' below.
1975         // invariants: the current token is not a left-delimiter,
1976         // not an EOF, and not the desired right-delimiter (if
1977         // it were, parse_seq_to_before_end would have prevented
1978         // reaching this point.
1979         fn parse_non_delim_tt_tok(p: &Parser) -> token_tree {
1980             maybe_whole!(deref p, nt_tt);
1981             match *p.token {
1982               token::RPAREN | token::RBRACE | token::RBRACKET
1983               => {
1984                 p.fatal(
1985                     format!(
1986                         "incorrect close delimiter: `{}`",
1987                         p.this_token_to_str()
1988                     )
1989                 );
1990               }
1991               /* we ought to allow different depths of unquotation */
1992               token::DOLLAR if *p.quote_depth > 0u => {
1993                 p.bump();
1994                 let sp = *p.span;
1995
1996                 if *p.token == token::LPAREN {
1997                     let seq = p.parse_seq(
1998                         &token::LPAREN,
1999                         &token::RPAREN,
2000                         seq_sep_none(),
2001                         |p| p.parse_token_tree()
2002                     );
2003                     let (s, z) = p.parse_sep_and_zerok();
2004                     let seq = match seq {
2005                         Spanned { node, _ } => node,
2006                     };
2007                     tt_seq(
2008                         mk_sp(sp.lo, p.span.hi),
2009                         @mut seq,
2010                         s,
2011                         z
2012                     )
2013                 } else {
2014                     tt_nonterminal(sp, p.parse_ident())
2015                 }
2016               }
2017               _ => {
2018                   parse_any_tt_tok(p)
2019               }
2020             }
2021         }
2022
2023         // turn the next token into a tt_tok:
2024         fn parse_any_tt_tok(p: &Parser) -> token_tree{
2025             tt_tok(*p.span, p.bump_and_get())
2026         }
2027
2028         match *self.token {
2029             token::EOF => {
2030                 for sp in self.open_braces.iter() {
2031                     self.span_note(*sp, "Did you mean to close this delimiter?");
2032                 }
2033                 // There shouldn't really be a span, but it's easier for the test runner
2034                 // if we give it one
2035                 self.fatal("This file contains an un-closed delimiter ");
2036             }
2037             token::LPAREN | token::LBRACE | token::LBRACKET => {
2038                 let close_delim = token::flip_delimiter(&*self.token);
2039
2040                 // Parse the open delimiter.
2041                 (*self.open_braces).push(*self.span);
2042                 let mut result = ~[parse_any_tt_tok(self)];
2043
2044                 let trees =
2045                     self.parse_seq_to_before_end(&close_delim,
2046                                                  seq_sep_none(),
2047                                                  |p| p.parse_token_tree());
2048                 result.push_all_move(trees);
2049
2050                 // Parse the close delimiter.
2051                 result.push(parse_any_tt_tok(self));
2052                 self.open_braces.pop();
2053
2054                 tt_delim(@mut result)
2055             }
2056             _ => parse_non_delim_tt_tok(self)
2057         }
2058     }
2059
2060     // parse a stream of tokens into a list of token_trees,
2061     // up to EOF.
2062     pub fn parse_all_token_trees(&self) -> ~[token_tree] {
2063         let mut tts = ~[];
2064         while *self.token != token::EOF {
2065             tts.push(self.parse_token_tree());
2066         }
2067         tts
2068     }
2069
2070     pub fn parse_matchers(&self) -> ~[matcher] {
2071         // unification of matchers and token_trees would vastly improve
2072         // the interpolation of matchers
2073         maybe_whole!(self, nt_matchers);
2074         let name_idx = @mut 0u;
2075         match *self.token {
2076             token::LBRACE | token::LPAREN | token::LBRACKET => {
2077                 let other_delimiter = token::flip_delimiter(self.token);
2078                 self.bump();
2079                 self.parse_matcher_subseq_upto(name_idx, &other_delimiter)
2080             }
2081             _ => self.fatal("expected open delimiter")
2082         }
2083     }
2084
2085     // This goofy function is necessary to correctly match parens in matchers.
2086     // Otherwise, `$( ( )` would be a valid matcher, and `$( () )` would be
2087     // invalid. It's similar to common::parse_seq.
2088     pub fn parse_matcher_subseq_upto(&self,
2089                                      name_idx: @mut uint,
2090                                      ket: &token::Token)
2091                                      -> ~[matcher] {
2092         let mut ret_val = ~[];
2093         let mut lparens = 0u;
2094
2095         while *self.token != *ket || lparens > 0u {
2096             if *self.token == token::LPAREN { lparens += 1u; }
2097             if *self.token == token::RPAREN { lparens -= 1u; }
2098             ret_val.push(self.parse_matcher(name_idx));
2099         }
2100
2101         self.bump();
2102
2103         return ret_val;
2104     }
2105
2106     pub fn parse_matcher(&self, name_idx: @mut uint) -> matcher {
2107         let lo = self.span.lo;
2108
2109         let m = if *self.token == token::DOLLAR {
2110             self.bump();
2111             if *self.token == token::LPAREN {
2112                 let name_idx_lo = *name_idx;
2113                 self.bump();
2114                 let ms = self.parse_matcher_subseq_upto(name_idx,
2115                                                         &token::RPAREN);
2116                 if ms.len() == 0u {
2117                     self.fatal("repetition body must be nonempty");
2118                 }
2119                 let (sep, zerok) = self.parse_sep_and_zerok();
2120                 match_seq(ms, sep, zerok, name_idx_lo, *name_idx)
2121             } else {
2122                 let bound_to = self.parse_ident();
2123                 self.expect(&token::COLON);
2124                 let nt_name = self.parse_ident();
2125                 let m = match_nonterminal(bound_to, nt_name, *name_idx);
2126                 *name_idx += 1u;
2127                 m
2128             }
2129         } else {
2130             match_tok(self.bump_and_get())
2131         };
2132
2133         return spanned(lo, self.span.hi, m);
2134     }
2135
2136     // parse a prefix-operator expr
2137     pub fn parse_prefix_expr(&self) -> @Expr {
2138         let lo = self.span.lo;
2139         let hi;
2140
2141         let ex;
2142         match *self.token {
2143           token::NOT => {
2144             self.bump();
2145             let e = self.parse_prefix_expr();
2146             hi = e.span.hi;
2147             ex = self.mk_unary(UnNot, e);
2148           }
2149           token::BINOP(b) => {
2150             match b {
2151               token::MINUS => {
2152                 self.bump();
2153                 let e = self.parse_prefix_expr();
2154                 hi = e.span.hi;
2155                 ex = self.mk_unary(UnNeg, e);
2156               }
2157               token::STAR => {
2158                 self.bump();
2159                 let e = self.parse_prefix_expr();
2160                 hi = e.span.hi;
2161                 ex = self.mk_unary(UnDeref, e);
2162               }
2163               token::AND => {
2164                 self.bump();
2165                 let _lt = self.parse_opt_lifetime();
2166                 let m = self.parse_mutability();
2167                 let e = self.parse_prefix_expr();
2168                 hi = e.span.hi;
2169                 // HACK: turn &[...] into a &-evec
2170                 ex = match e.node {
2171                   ExprVec(*) | ExprLit(@codemap::Spanned {
2172                     node: lit_str(*), span: _
2173                   })
2174                   if m == MutImmutable => {
2175                     ExprVstore(e, ExprVstoreSlice)
2176                   }
2177                   ExprVec(*) if m == MutMutable => {
2178                     ExprVstore(e, ExprVstoreMutSlice)
2179                   }
2180                   _ => ExprAddrOf(m, e)
2181                 };
2182               }
2183               _ => return self.parse_dot_or_call_expr()
2184             }
2185           }
2186           token::AT => {
2187             self.bump();
2188             let m = self.parse_mutability();
2189             let e = self.parse_prefix_expr();
2190             hi = e.span.hi;
2191             // HACK: turn @[...] into a @-evec
2192             ex = match e.node {
2193               ExprVec(*) | ExprRepeat(*) if m == MutMutable =>
2194                 ExprVstore(e, ExprVstoreMutBox),
2195               ExprVec(*) |
2196               ExprLit(@codemap::Spanned { node: lit_str(*), span: _}) |
2197               ExprRepeat(*) if m == MutImmutable => ExprVstore(e, ExprVstoreBox),
2198               _ => self.mk_unary(UnBox(m), e)
2199             };
2200           }
2201           token::TILDE => {
2202             self.bump();
2203
2204             let e = self.parse_prefix_expr();
2205             hi = e.span.hi;
2206             // HACK: turn ~[...] into a ~-evec
2207             ex = match e.node {
2208               ExprVec(*) |
2209               ExprLit(@codemap::Spanned { node: lit_str(*), span: _}) |
2210               ExprRepeat(*) => ExprVstore(e, ExprVstoreUniq),
2211               _ => self.mk_unary(UnUniq, e)
2212             };
2213           }
2214           _ => return self.parse_dot_or_call_expr()
2215         }
2216         return self.mk_expr(lo, hi, ex);
2217     }
2218
2219     // parse an expression of binops
2220     pub fn parse_binops(&self) -> @Expr {
2221         self.parse_more_binops(self.parse_prefix_expr(), 0)
2222     }
2223
2224     // parse an expression of binops of at least min_prec precedence
2225     pub fn parse_more_binops(&self, lhs: @Expr, min_prec: uint) -> @Expr {
2226         if self.expr_is_complete(lhs) { return lhs; }
2227
2228         // Prevent dynamic borrow errors later on by limiting the
2229         // scope of the borrows.
2230         {
2231             let token: &token::Token = self.token;
2232             let restriction: &restriction = self.restriction;
2233             match (token, restriction) {
2234                 (&token::BINOP(token::OR), &RESTRICT_NO_BAR_OP) => return lhs,
2235                 (&token::BINOP(token::OR),
2236                  &RESTRICT_NO_BAR_OR_DOUBLEBAR_OP) => return lhs,
2237                 (&token::OROR, &RESTRICT_NO_BAR_OR_DOUBLEBAR_OP) => return lhs,
2238                 _ => { }
2239             }
2240         }
2241
2242         let cur_opt = token_to_binop(self.token);
2243         match cur_opt {
2244             Some(cur_op) => {
2245                 let cur_prec = operator_prec(cur_op);
2246                 if cur_prec > min_prec {
2247                     self.bump();
2248                     let expr = self.parse_prefix_expr();
2249                     let rhs = self.parse_more_binops(expr, cur_prec);
2250                     let bin = self.mk_expr(lhs.span.lo, rhs.span.hi,
2251                                            self.mk_binary(cur_op, lhs, rhs));
2252                     self.parse_more_binops(bin, min_prec)
2253                 } else {
2254                     lhs
2255                 }
2256             }
2257             None => {
2258                 if as_prec > min_prec && self.eat_keyword(keywords::As) {
2259                     let rhs = self.parse_ty(true);
2260                     let _as = self.mk_expr(lhs.span.lo,
2261                                            rhs.span.hi,
2262                                            ExprCast(lhs, rhs));
2263                     self.parse_more_binops(_as, min_prec)
2264                 } else {
2265                     lhs
2266                 }
2267             }
2268         }
2269     }
2270
2271     // parse an assignment expression....
2272     // actually, this seems to be the main entry point for
2273     // parsing an arbitrary expression.
2274     pub fn parse_assign_expr(&self) -> @Expr {
2275         let lo = self.span.lo;
2276         let lhs = self.parse_binops();
2277         match *self.token {
2278           token::EQ => {
2279               self.bump();
2280               let rhs = self.parse_expr();
2281               self.mk_expr(lo, rhs.span.hi, ExprAssign(lhs, rhs))
2282           }
2283           token::BINOPEQ(op) => {
2284               self.bump();
2285               let rhs = self.parse_expr();
2286               let aop = match op {
2287                   token::PLUS =>    BiAdd,
2288                   token::MINUS =>   BiSub,
2289                   token::STAR =>    BiMul,
2290                   token::SLASH =>   BiDiv,
2291                   token::PERCENT => BiRem,
2292                   token::CARET =>   BiBitXor,
2293                   token::AND =>     BiBitAnd,
2294                   token::OR =>      BiBitOr,
2295                   token::SHL =>     BiShl,
2296                   token::SHR =>     BiShr
2297               };
2298               self.mk_expr(lo, rhs.span.hi,
2299                            self.mk_assign_op(aop, lhs, rhs))
2300           }
2301           token::DARROW => {
2302             self.obsolete(*self.span, ObsoleteSwap);
2303             self.bump();
2304             // Ignore what we get, this is an error anyway
2305             self.parse_expr();
2306             self.mk_expr(lo, self.span.hi, ExprBreak(None))
2307           }
2308           _ => {
2309               lhs
2310           }
2311         }
2312     }
2313
2314     // parse an 'if' expression ('if' token already eaten)
2315     pub fn parse_if_expr(&self) -> @Expr {
2316         let lo = self.last_span.lo;
2317         let cond = self.parse_expr();
2318         let thn = self.parse_block();
2319         let mut els: Option<@Expr> = None;
2320         let mut hi = thn.span.hi;
2321         if self.eat_keyword(keywords::Else) {
2322             let elexpr = self.parse_else_expr();
2323             els = Some(elexpr);
2324             hi = elexpr.span.hi;
2325         }
2326         self.mk_expr(lo, hi, ExprIf(cond, thn, els))
2327     }
2328
2329     // `|args| { ... }` or `{ ...}` like in `do` expressions
2330     pub fn parse_lambda_block_expr(&self) -> @Expr {
2331         self.parse_lambda_expr_(
2332             || {
2333                 match *self.token {
2334                   token::BINOP(token::OR) | token::OROR => {
2335                     self.parse_fn_block_decl()
2336                   }
2337                   _ => {
2338                     // No argument list - `do foo {`
2339                       ast::fn_decl {
2340                           inputs: ~[],
2341                           output: Ty {
2342                               id: ast::DUMMY_NODE_ID,
2343                               node: ty_infer,
2344                               span: *self.span
2345                           },
2346                           cf: return_val
2347                       }
2348                   }
2349                 }
2350             },
2351             || {
2352                 let blk = self.parse_block();
2353                 self.mk_expr(blk.span.lo, blk.span.hi, ExprBlock(blk))
2354             })
2355     }
2356
2357     // `|args| expr`
2358     pub fn parse_lambda_expr(&self) -> @Expr {
2359         self.parse_lambda_expr_(|| self.parse_fn_block_decl(),
2360                                 || self.parse_expr())
2361     }
2362
2363     // parse something of the form |args| expr
2364     // this is used both in parsing a lambda expr
2365     // and in parsing a block expr as e.g. in for...
2366     pub fn parse_lambda_expr_(&self,
2367                               parse_decl: &fn() -> fn_decl,
2368                               parse_body: &fn() -> @Expr)
2369                               -> @Expr {
2370         let lo = self.last_span.lo;
2371         let decl = parse_decl();
2372         let body = parse_body();
2373         let fakeblock = ast::Block {
2374             view_items: ~[],
2375             stmts: ~[],
2376             expr: Some(body),
2377             id: ast::DUMMY_NODE_ID,
2378             rules: DefaultBlock,
2379             span: body.span,
2380         };
2381
2382         return self.mk_expr(lo, body.span.hi,
2383                             ExprFnBlock(decl, fakeblock));
2384     }
2385
2386     pub fn parse_else_expr(&self) -> @Expr {
2387         if self.eat_keyword(keywords::If) {
2388             return self.parse_if_expr();
2389         } else {
2390             let blk = self.parse_block();
2391             return self.mk_expr(blk.span.lo, blk.span.hi, ExprBlock(blk));
2392         }
2393     }
2394
2395     // parse a 'for' .. 'in' expression ('for' token already eaten)
2396     pub fn parse_for_expr(&self, opt_ident: Option<ast::Ident>) -> @Expr {
2397         // Parse: `for <src_pat> in <src_expr> <src_loop_block>`
2398
2399         let lo = self.last_span.lo;
2400         let pat = self.parse_pat();
2401         self.expect_keyword(keywords::In);
2402         let expr = self.parse_expr();
2403         let loop_block = self.parse_block();
2404         let hi = self.span.hi;
2405
2406         self.mk_expr(lo, hi, ExprForLoop(pat, expr, loop_block, opt_ident))
2407     }
2408
2409
2410     // parse a 'for' or 'do'.
2411     // the 'for' and 'do' expressions parse as calls, but look like
2412     // function calls followed by a closure expression.
2413     pub fn parse_sugary_call_expr(&self, lo: BytePos,
2414                                   keyword: ~str,
2415                                   sugar: CallSugar,
2416                                   ctor: &fn(v: @Expr) -> Expr_)
2417                                   -> @Expr {
2418         // Parse the callee `foo` in
2419         //    for foo || {
2420         //    for foo.bar || {
2421         // etc, or the portion of the call expression before the lambda in
2422         //    for foo() || {
2423         // or
2424         //    for foo.bar(a) || {
2425         // Turn on the restriction to stop at | or || so we can parse
2426         // them as the lambda arguments
2427         let e = self.parse_expr_res(RESTRICT_NO_BAR_OR_DOUBLEBAR_OP);
2428         match e.node {
2429             ExprCall(f, ref args, NoSugar) => {
2430                 let block = self.parse_lambda_block_expr();
2431                 let last_arg = self.mk_expr(block.span.lo, block.span.hi,
2432                                             ctor(block));
2433                 let args = vec::append((*args).clone(), [last_arg]);
2434                 self.mk_expr(lo, block.span.hi, ExprCall(f, args, sugar))
2435             }
2436             ExprMethodCall(_, f, i, ref tps, ref args, NoSugar) => {
2437                 let block = self.parse_lambda_block_expr();
2438                 let last_arg = self.mk_expr(block.span.lo, block.span.hi,
2439                                             ctor(block));
2440                 let args = vec::append((*args).clone(), [last_arg]);
2441                 self.mk_expr(lo, block.span.hi,
2442                              self.mk_method_call(f,
2443                                                  i,
2444                                                  (*tps).clone(),
2445                                                  args,
2446                                                  sugar))
2447             }
2448             ExprField(f, i, ref tps) => {
2449                 let block = self.parse_lambda_block_expr();
2450                 let last_arg = self.mk_expr(block.span.lo, block.span.hi,
2451                                             ctor(block));
2452                 self.mk_expr(lo, block.span.hi,
2453                              self.mk_method_call(f,
2454                                                  i,
2455                                                  (*tps).clone(),
2456                                                  ~[last_arg],
2457                                                  sugar))
2458             }
2459             ExprPath(*) | ExprCall(*) | ExprMethodCall(*) |
2460                 ExprParen(*) => {
2461                 let block = self.parse_lambda_block_expr();
2462                 let last_arg = self.mk_expr(block.span.lo, block.span.hi,
2463                                             ctor(block));
2464                 self.mk_expr(
2465                     lo,
2466                     last_arg.span.hi,
2467                     self.mk_call(e, ~[last_arg], sugar))
2468             }
2469             _ => {
2470                 // There may be other types of expressions that can
2471                 // represent the callee in `for` and `do` expressions
2472                 // but they aren't represented by tests
2473                 debug!("sugary call on {:?}", e.node);
2474                 self.span_fatal(
2475                     e.span,
2476                     format!("`{}` must be followed by a block call", keyword));
2477             }
2478         }
2479     }
2480
2481     pub fn parse_while_expr(&self) -> @Expr {
2482         let lo = self.last_span.lo;
2483         let cond = self.parse_expr();
2484         let body = self.parse_block();
2485         let hi = body.span.hi;
2486         return self.mk_expr(lo, hi, ExprWhile(cond, body));
2487     }
2488
2489     pub fn parse_loop_expr(&self, opt_ident: Option<ast::Ident>) -> @Expr {
2490         // loop headers look like 'loop {' or 'loop unsafe {'
2491         let is_loop_header =
2492             *self.token == token::LBRACE
2493             || (is_ident(&*self.token)
2494                 && self.look_ahead(1, |t| *t == token::LBRACE));
2495
2496         if is_loop_header {
2497             // This is a loop body
2498             let lo = self.last_span.lo;
2499             let body = self.parse_block();
2500             let hi = body.span.hi;
2501             return self.mk_expr(lo, hi, ExprLoop(body, opt_ident));
2502         } else {
2503             // This is an obsolete 'continue' expression
2504             if opt_ident.is_some() {
2505                 self.span_err(*self.last_span,
2506                               "a label may not be used with a `loop` expression");
2507             }
2508
2509             self.obsolete(*self.last_span, ObsoleteLoopAsContinue);
2510             let lo = self.span.lo;
2511             let ex = if self.token_is_lifetime(&*self.token) {
2512                 let lifetime = self.get_lifetime(&*self.token);
2513                 self.bump();
2514                 ExprAgain(Some(lifetime.name))
2515             } else {
2516                 ExprAgain(None)
2517             };
2518             let hi = self.span.hi;
2519             return self.mk_expr(lo, hi, ex);
2520         }
2521     }
2522
2523     // For distingishing between record literals and blocks
2524     fn looking_at_record_literal(&self) -> bool {
2525         *self.token == token::LBRACE &&
2526             (self.look_ahead(1, |t| token::is_keyword(keywords::Mut, t)) ||
2527              (self.look_ahead(1, |t| token::is_plain_ident(t)) &&
2528               self.look_ahead(2, |t| *t == token::COLON)))
2529     }
2530
2531     fn parse_match_expr(&self) -> @Expr {
2532         let lo = self.last_span.lo;
2533         let discriminant = self.parse_expr();
2534         self.commit_expr_expecting(discriminant, token::LBRACE);
2535         let mut arms: ~[Arm] = ~[];
2536         while *self.token != token::RBRACE {
2537             let pats = self.parse_pats();
2538             let mut guard = None;
2539             if self.eat_keyword(keywords::If) {
2540                 guard = Some(self.parse_expr());
2541             }
2542             self.expect(&token::FAT_ARROW);
2543             let expr = self.parse_expr_res(RESTRICT_STMT_EXPR);
2544
2545             let require_comma =
2546                 !classify::expr_is_simple_block(expr)
2547                 && *self.token != token::RBRACE;
2548
2549             if require_comma {
2550                 self.commit_expr(expr, &[token::COMMA], &[token::RBRACE]);
2551             } else {
2552                 self.eat(&token::COMMA);
2553             }
2554
2555             let blk = ast::Block {
2556                 view_items: ~[],
2557                 stmts: ~[],
2558                 expr: Some(expr),
2559                 id: ast::DUMMY_NODE_ID,
2560                 rules: DefaultBlock,
2561                 span: expr.span,
2562             };
2563
2564             arms.push(ast::Arm { pats: pats, guard: guard, body: blk });
2565         }
2566         let hi = self.span.hi;
2567         self.bump();
2568         return self.mk_expr(lo, hi, ExprMatch(discriminant, arms));
2569     }
2570
2571     // parse an expression
2572     pub fn parse_expr(&self) -> @Expr {
2573         return self.parse_expr_res(UNRESTRICTED);
2574     }
2575
2576     // parse an expression, subject to the given restriction
2577     fn parse_expr_res(&self, r: restriction) -> @Expr {
2578         let old = *self.restriction;
2579         *self.restriction = r;
2580         let e = self.parse_assign_expr();
2581         *self.restriction = old;
2582         return e;
2583     }
2584
2585     // parse the RHS of a local variable declaration (e.g. '= 14;')
2586     fn parse_initializer(&self) -> Option<@Expr> {
2587         if *self.token == token::EQ {
2588             self.bump();
2589             Some(self.parse_expr())
2590         } else {
2591             None
2592         }
2593     }
2594
2595     // parse patterns, separated by '|' s
2596     fn parse_pats(&self) -> ~[@Pat] {
2597         let mut pats = ~[];
2598         loop {
2599             pats.push(self.parse_pat());
2600             if *self.token == token::BINOP(token::OR) { self.bump(); }
2601             else { return pats; }
2602         };
2603     }
2604
2605     fn parse_pat_vec_elements(
2606         &self,
2607     ) -> (~[@Pat], Option<@Pat>, ~[@Pat]) {
2608         let mut before = ~[];
2609         let mut slice = None;
2610         let mut after = ~[];
2611         let mut first = true;
2612         let mut before_slice = true;
2613
2614         while *self.token != token::RBRACKET {
2615             if first { first = false; }
2616             else { self.expect(&token::COMMA); }
2617
2618             let mut is_slice = false;
2619             if before_slice {
2620                 if *self.token == token::DOTDOT {
2621                     self.bump();
2622                     is_slice = true;
2623                     before_slice = false;
2624                 }
2625             }
2626
2627             let subpat = self.parse_pat();
2628             if is_slice {
2629                 match subpat {
2630                     @ast::Pat { node: PatWild, _ } => (),
2631                     @ast::Pat { node: PatIdent(_, _, _), _ } => (),
2632                     @ast::Pat { span, _ } => self.span_fatal(
2633                         span, "expected an identifier or `_`"
2634                     )
2635                 }
2636                 slice = Some(subpat);
2637             } else {
2638                 if before_slice {
2639                     before.push(subpat);
2640                 } else {
2641                     after.push(subpat);
2642                 }
2643             }
2644         }
2645
2646         (before, slice, after)
2647     }
2648
2649     // parse the fields of a struct-like pattern
2650     fn parse_pat_fields(&self) -> (~[ast::FieldPat], bool) {
2651         let mut fields = ~[];
2652         let mut etc = false;
2653         let mut first = true;
2654         while *self.token != token::RBRACE {
2655             if first { first = false; }
2656             else { self.expect(&token::COMMA); }
2657
2658             if *self.token == token::UNDERSCORE {
2659                 self.bump();
2660                 if *self.token != token::RBRACE {
2661                     self.fatal(
2662                         format!(
2663                             "expected `\\}`, found `{}`",
2664                             self.this_token_to_str()
2665                         )
2666                     );
2667                 }
2668                 etc = true;
2669                 break;
2670             }
2671
2672             let lo1 = self.last_span.lo;
2673             let fieldname = self.parse_ident();
2674             let hi1 = self.last_span.lo;
2675             let fieldpath = ast_util::ident_to_path(mk_sp(lo1, hi1),
2676                                                     fieldname);
2677             let subpat;
2678             if *self.token == token::COLON {
2679                 self.bump();
2680                 subpat = self.parse_pat();
2681             } else {
2682                 subpat = @ast::Pat {
2683                     id: ast::DUMMY_NODE_ID,
2684                     node: PatIdent(BindInfer, fieldpath, None),
2685                     span: *self.last_span
2686                 };
2687             }
2688             fields.push(ast::FieldPat { ident: fieldname, pat: subpat });
2689         }
2690         return (fields, etc);
2691     }
2692
2693     // parse a pattern.
2694     pub fn parse_pat(&self) -> @Pat {
2695         maybe_whole!(self, nt_pat);
2696
2697         let lo = self.span.lo;
2698         let mut hi;
2699         let pat;
2700         match *self.token {
2701             // parse _
2702           token::UNDERSCORE => {
2703             self.bump();
2704             pat = PatWild;
2705             hi = self.last_span.hi;
2706             return @ast::Pat {
2707                 id: ast::DUMMY_NODE_ID,
2708                 node: pat,
2709                 span: mk_sp(lo, hi)
2710             }
2711           }
2712           // parse @pat
2713           token::AT => {
2714             self.bump();
2715             let sub = self.parse_pat();
2716             hi = sub.span.hi;
2717             // HACK: parse @"..." as a literal of a vstore @str
2718             pat = match sub.node {
2719               PatLit(e@@Expr {
2720                 node: ExprLit(@codemap::Spanned {
2721                     node: lit_str(*),
2722                     span: _}), _
2723               }) => {
2724                 let vst = @Expr {
2725                     id: ast::DUMMY_NODE_ID,
2726                     node: ExprVstore(e, ExprVstoreBox),
2727                     span: mk_sp(lo, hi),
2728                 };
2729                 PatLit(vst)
2730               }
2731               _ => PatBox(sub)
2732             };
2733             hi = self.last_span.hi;
2734             return @ast::Pat {
2735                 id: ast::DUMMY_NODE_ID,
2736                 node: pat,
2737                 span: mk_sp(lo, hi)
2738             }
2739           }
2740           token::TILDE => {
2741             // parse ~pat
2742             self.bump();
2743             let sub = self.parse_pat();
2744             hi = sub.span.hi;
2745             // HACK: parse ~"..." as a literal of a vstore ~str
2746             pat = match sub.node {
2747               PatLit(e@@Expr {
2748                 node: ExprLit(@codemap::Spanned {
2749                     node: lit_str(*),
2750                     span: _}), _
2751               }) => {
2752                 let vst = @Expr {
2753                     id: ast::DUMMY_NODE_ID,
2754                     node: ExprVstore(e, ExprVstoreUniq),
2755                     span: mk_sp(lo, hi),
2756                 };
2757                 PatLit(vst)
2758               }
2759               _ => PatUniq(sub)
2760             };
2761             hi = self.last_span.hi;
2762             return @ast::Pat {
2763                 id: ast::DUMMY_NODE_ID,
2764                 node: pat,
2765                 span: mk_sp(lo, hi)
2766             }
2767           }
2768           token::BINOP(token::AND) => {
2769               // parse &pat
2770               let lo = self.span.lo;
2771               self.bump();
2772               let sub = self.parse_pat();
2773               hi = sub.span.hi;
2774               // HACK: parse &"..." as a literal of a borrowed str
2775               pat = match sub.node {
2776                   PatLit(e@@Expr {
2777                       node: ExprLit(@codemap::Spanned {
2778                             node: lit_str(*), span: _}), _
2779                   }) => {
2780                       let vst = @Expr {
2781                           id: ast::DUMMY_NODE_ID,
2782                           node: ExprVstore(e, ExprVstoreSlice),
2783                           span: mk_sp(lo, hi)
2784                       };
2785                       PatLit(vst)
2786                   }
2787               _ => PatRegion(sub)
2788             };
2789             hi = self.last_span.hi;
2790             return @ast::Pat {
2791                 id: ast::DUMMY_NODE_ID,
2792                 node: pat,
2793                 span: mk_sp(lo, hi)
2794             }
2795           }
2796           token::LPAREN => {
2797             // parse (pat,pat,pat,...) as tuple
2798             self.bump();
2799             if *self.token == token::RPAREN {
2800                 hi = self.span.hi;
2801                 self.bump();
2802                 let lit = @codemap::Spanned {
2803                     node: lit_nil,
2804                     span: mk_sp(lo, hi)};
2805                 let expr = self.mk_expr(lo, hi, ExprLit(lit));
2806                 pat = PatLit(expr);
2807             } else {
2808                 let mut fields = ~[self.parse_pat()];
2809                 if self.look_ahead(1, |t| *t != token::RPAREN) {
2810                     while *self.token == token::COMMA {
2811                         self.bump();
2812                         fields.push(self.parse_pat());
2813                     }
2814                 }
2815                 if fields.len() == 1 { self.expect(&token::COMMA); }
2816                 self.expect(&token::RPAREN);
2817                 pat = PatTup(fields);
2818             }
2819             hi = self.last_span.hi;
2820             return @ast::Pat {
2821                 id: ast::DUMMY_NODE_ID,
2822                 node: pat,
2823                 span: mk_sp(lo, hi)
2824             }
2825           }
2826           token::LBRACKET => {
2827             // parse [pat,pat,...] as vector pattern
2828             self.bump();
2829             let (before, slice, after) =
2830                 self.parse_pat_vec_elements();
2831
2832             self.expect(&token::RBRACKET);
2833             pat = ast::PatVec(before, slice, after);
2834             hi = self.last_span.hi;
2835             return @ast::Pat {
2836                 id: ast::DUMMY_NODE_ID,
2837                 node: pat,
2838                 span: mk_sp(lo, hi)
2839             }
2840           }
2841           _ => {}
2842         }
2843
2844         let tok = self.token;
2845         if !is_ident_or_path(tok)
2846                 || self.is_keyword(keywords::True)
2847                 || self.is_keyword(keywords::False) {
2848             // Parse an expression pattern or exp .. exp.
2849             //
2850             // These expressions are limited to literals (possibly
2851             // preceded by unary-minus) or identifiers.
2852             let val = self.parse_literal_maybe_minus();
2853             if self.eat(&token::DOTDOT) {
2854                 let end = if is_ident_or_path(tok) {
2855                     let path = self.parse_path(LifetimeAndTypesWithColons)
2856                                    .path;
2857                     let hi = self.span.hi;
2858                     self.mk_expr(lo, hi, ExprPath(path))
2859                 } else {
2860                     self.parse_literal_maybe_minus()
2861                 };
2862                 pat = PatRange(val, end);
2863             } else {
2864                 pat = PatLit(val);
2865             }
2866         } else if self.eat_keyword(keywords::Ref) {
2867             // parse ref pat
2868             let mutbl = self.parse_mutability();
2869             pat = self.parse_pat_ident(BindByRef(mutbl));
2870         } else {
2871             let can_be_enum_or_struct = do self.look_ahead(1) |t| {
2872                 match *t {
2873                     token::LPAREN | token::LBRACKET | token::LT |
2874                     token::LBRACE | token::MOD_SEP => true,
2875                     _ => false,
2876                 }
2877             };
2878
2879             if self.look_ahead(1, |t| *t == token::DOTDOT) {
2880                 let start = self.parse_expr_res(RESTRICT_NO_BAR_OP);
2881                 self.eat(&token::DOTDOT);
2882                 let end = self.parse_expr_res(RESTRICT_NO_BAR_OP);
2883                 pat = PatRange(start, end);
2884             } else if is_plain_ident(&*self.token) && !can_be_enum_or_struct {
2885                 let name = self.parse_path(NoTypesAllowed).path;
2886                 let sub;
2887                 if self.eat(&token::AT) {
2888                     // parse foo @ pat
2889                     sub = Some(self.parse_pat());
2890                 } else {
2891                     // or just foo
2892                     sub = None;
2893                 }
2894                 pat = PatIdent(BindInfer, name, sub);
2895             } else {
2896                 // parse an enum pat
2897                 let enum_path = self.parse_path(LifetimeAndTypesWithColons)
2898                                     .path;
2899                 match *self.token {
2900                     token::LBRACE => {
2901                         self.bump();
2902                         let (fields, etc) =
2903                             self.parse_pat_fields();
2904                         self.bump();
2905                         pat = PatStruct(enum_path, fields, etc);
2906                     }
2907                     _ => {
2908                         let mut args: ~[@Pat] = ~[];
2909                         match *self.token {
2910                           token::LPAREN => {
2911                             let is_star = do self.look_ahead(1) |t| {
2912                                 match *t {
2913                                     token::BINOP(token::STAR) => true,
2914                                     _ => false,
2915                                 }
2916                             };
2917                             if is_star {
2918                                 // This is a "top constructor only" pat
2919                                 self.bump();
2920                                 self.bump();
2921                                 self.expect(&token::RPAREN);
2922                                 pat = PatEnum(enum_path, None);
2923                             } else {
2924                                 args = self.parse_unspanned_seq(
2925                                     &token::LPAREN,
2926                                     &token::RPAREN,
2927                                     seq_sep_trailing_disallowed(token::COMMA),
2928                                     |p| p.parse_pat()
2929                                 );
2930                                 pat = PatEnum(enum_path, Some(args));
2931                             }
2932                           },
2933                           _ => {
2934                               if enum_path.segments.len() == 1 {
2935                                   // it could still be either an enum
2936                                   // or an identifier pattern, resolve
2937                                   // will sort it out:
2938                                   pat = PatIdent(BindInfer,
2939                                                   enum_path,
2940                                                   None);
2941                               } else {
2942                                   pat = PatEnum(enum_path, Some(args));
2943                               }
2944                           }
2945                         }
2946                     }
2947                 }
2948             }
2949         }
2950         hi = self.last_span.hi;
2951         @ast::Pat {
2952             id: ast::DUMMY_NODE_ID,
2953             node: pat,
2954             span: mk_sp(lo, hi),
2955         }
2956     }
2957
2958     // parse ident or ident @ pat
2959     // used by the copy foo and ref foo patterns to give a good
2960     // error message when parsing mistakes like ref foo(a,b)
2961     fn parse_pat_ident(&self,
2962                        binding_mode: ast::BindingMode)
2963                        -> ast::Pat_ {
2964         if !is_plain_ident(&*self.token) {
2965             self.span_fatal(*self.last_span,
2966                             "expected identifier, found path");
2967         }
2968         // why a path here, and not just an identifier?
2969         let name = self.parse_path(NoTypesAllowed).path;
2970         let sub = if self.eat(&token::AT) {
2971             Some(self.parse_pat())
2972         } else {
2973             None
2974         };
2975
2976         // just to be friendly, if they write something like
2977         //   ref Some(i)
2978         // we end up here with ( as the current token.  This shortly
2979         // leads to a parse error.  Note that if there is no explicit
2980         // binding mode then we do not end up here, because the lookahead
2981         // will direct us over to parse_enum_variant()
2982         if *self.token == token::LPAREN {
2983             self.span_fatal(
2984                 *self.last_span,
2985                 "expected identifier, found enum pattern");
2986         }
2987
2988         PatIdent(binding_mode, name, sub)
2989     }
2990
2991     // parse a local variable declaration
2992     fn parse_local(&self, is_mutbl: bool) -> @Local {
2993         let lo = self.span.lo;
2994         let pat = self.parse_pat();
2995
2996         if is_mutbl && !ast_util::pat_is_ident(pat) {
2997             self.obsolete(*self.span, ObsoleteMutWithMultipleBindings)
2998         }
2999
3000         let mut ty = Ty {
3001             id: ast::DUMMY_NODE_ID,
3002             node: ty_infer,
3003             span: mk_sp(lo, lo),
3004         };
3005         if self.eat(&token::COLON) { ty = self.parse_ty(false); }
3006         let init = self.parse_initializer();
3007         @ast::Local {
3008             is_mutbl: is_mutbl,
3009             ty: ty,
3010             pat: pat,
3011             init: init,
3012             id: ast::DUMMY_NODE_ID,
3013             span: mk_sp(lo, self.last_span.hi),
3014         }
3015     }
3016
3017     // parse a "let" stmt
3018     fn parse_let(&self) -> @Decl {
3019         let is_mutbl = self.eat_keyword(keywords::Mut);
3020         let lo = self.span.lo;
3021         let local = self.parse_local(is_mutbl);
3022         while self.eat(&token::COMMA) {
3023             let _ = self.parse_local(is_mutbl);
3024             self.obsolete(*self.span, ObsoleteMultipleLocalDecl);
3025         }
3026         return @spanned(lo, self.last_span.hi, DeclLocal(local));
3027     }
3028
3029     // parse a structure field
3030     fn parse_name_and_ty(&self,
3031                          pr: visibility,
3032                          attrs: ~[Attribute]) -> @struct_field {
3033         let lo = self.span.lo;
3034         if !is_plain_ident(&*self.token) {
3035             self.fatal("expected ident");
3036         }
3037         let name = self.parse_ident();
3038         self.expect(&token::COLON);
3039         let ty = self.parse_ty(false);
3040         @spanned(lo, self.last_span.hi, ast::struct_field_ {
3041             kind: named_field(name, pr),
3042             id: ast::DUMMY_NODE_ID,
3043             ty: ty,
3044             attrs: attrs,
3045         })
3046     }
3047
3048     // parse a statement. may include decl.
3049     // precondition: any attributes are parsed already
3050     pub fn parse_stmt(&self, item_attrs: ~[Attribute]) -> @Stmt {
3051         maybe_whole!(self, nt_stmt);
3052
3053         fn check_expected_item(p: &Parser, found_attrs: bool) {
3054             // If we have attributes then we should have an item
3055             if found_attrs {
3056                 p.span_err(*p.last_span, "expected item after attributes");
3057             }
3058         }
3059
3060         let lo = self.span.lo;
3061         if self.is_keyword(keywords::Let) {
3062             check_expected_item(self, !item_attrs.is_empty());
3063             self.expect_keyword(keywords::Let);
3064             let decl = self.parse_let();
3065             return @spanned(lo, decl.span.hi, StmtDecl(decl, ast::DUMMY_NODE_ID));
3066         } else if is_ident(&*self.token)
3067             && !token::is_any_keyword(self.token)
3068             && self.look_ahead(1, |t| *t == token::NOT) {
3069             // parse a macro invocation. Looks like there's serious
3070             // overlap here; if this clause doesn't catch it (and it
3071             // won't, for brace-delimited macros) it will fall through
3072             // to the macro clause of parse_item_or_view_item. This
3073             // could use some cleanup, it appears to me.
3074
3075             // whoops! I now have a guess: I'm guessing the "parens-only"
3076             // rule here is deliberate, to allow macro users to use parens
3077             // for things that should be parsed as stmt_mac, and braces
3078             // for things that should expand into items. Tricky, and
3079             // somewhat awkward... and probably undocumented. Of course,
3080             // I could just be wrong.
3081
3082             check_expected_item(self, !item_attrs.is_empty());
3083
3084             // Potential trouble: if we allow macros with paths instead of
3085             // idents, we'd need to look ahead past the whole path here...
3086             let pth = self.parse_path(NoTypesAllowed).path;
3087             self.bump();
3088
3089             let id = if *self.token == token::LPAREN {
3090                 token::special_idents::invalid // no special identifier
3091             } else {
3092                 self.parse_ident()
3093             };
3094
3095             let tts = self.parse_unspanned_seq(
3096                 &token::LPAREN,
3097                 &token::RPAREN,
3098                 seq_sep_none(),
3099                 |p| p.parse_token_tree()
3100             );
3101             let hi = self.span.hi;
3102
3103             if id == token::special_idents::invalid {
3104                 return @spanned(lo, hi, StmtMac(
3105                     spanned(lo, hi, mac_invoc_tt(pth, tts, EMPTY_CTXT)), false));
3106             } else {
3107                 // if it has a special ident, it's definitely an item
3108                 return @spanned(lo, hi, StmtDecl(
3109                     @spanned(lo, hi, DeclItem(
3110                         self.mk_item(
3111                             lo, hi, id /*id is good here*/,
3112                             item_mac(spanned(lo, hi, mac_invoc_tt(pth, tts, EMPTY_CTXT))),
3113                             inherited, ~[/*no attrs*/]))),
3114                     ast::DUMMY_NODE_ID));
3115             }
3116
3117         } else {
3118             let found_attrs = !item_attrs.is_empty();
3119             match self.parse_item_or_view_item(item_attrs, false) {
3120                 iovi_item(i) => {
3121                     let hi = i.span.hi;
3122                     let decl = @spanned(lo, hi, DeclItem(i));
3123                     return @spanned(lo, hi, StmtDecl(decl, ast::DUMMY_NODE_ID));
3124                 }
3125                 iovi_view_item(vi) => {
3126                     self.span_fatal(vi.span,
3127                                     "view items must be declared at the top of the block");
3128                 }
3129                 iovi_foreign_item(_) => {
3130                     self.fatal("foreign items are not allowed here");
3131                 }
3132                 iovi_none(_) => { /* fallthrough */ }
3133             }
3134
3135             check_expected_item(self, found_attrs);
3136
3137             // Remainder are line-expr stmts.
3138             let e = self.parse_expr_res(RESTRICT_STMT_EXPR);
3139             return @spanned(lo, e.span.hi, StmtExpr(e, ast::DUMMY_NODE_ID));
3140         }
3141     }
3142
3143     // is this expression a successfully-parsed statement?
3144     fn expr_is_complete(&self, e: @Expr) -> bool {
3145         return *self.restriction == RESTRICT_STMT_EXPR &&
3146             !classify::expr_requires_semi_to_be_stmt(e);
3147     }
3148
3149     // parse a block. No inner attrs are allowed.
3150     pub fn parse_block(&self) -> Block {
3151         maybe_whole!(deref self, nt_block);
3152
3153         let lo = self.span.lo;
3154         if self.eat_keyword(keywords::Unsafe) {
3155             self.obsolete(*self.span, ObsoleteUnsafeBlock);
3156         }
3157         self.expect(&token::LBRACE);
3158
3159         return self.parse_block_tail_(lo, DefaultBlock, ~[]);
3160     }
3161
3162     // parse a block. Inner attrs are allowed.
3163     fn parse_inner_attrs_and_block(&self)
3164         -> (~[Attribute], Block) {
3165
3166         maybe_whole!(pair_empty self, nt_block);
3167
3168         let lo = self.span.lo;
3169         if self.eat_keyword(keywords::Unsafe) {
3170             self.obsolete(*self.span, ObsoleteUnsafeBlock);
3171         }
3172         self.expect(&token::LBRACE);
3173         let (inner, next) = self.parse_inner_attrs_and_next();
3174
3175         (inner, self.parse_block_tail_(lo, DefaultBlock, next))
3176     }
3177
3178     // Precondition: already parsed the '{' or '#{'
3179     // I guess that also means "already parsed the 'impure'" if
3180     // necessary, and this should take a qualifier.
3181     // some blocks start with "#{"...
3182     fn parse_block_tail(&self, lo: BytePos, s: BlockCheckMode) -> Block {
3183         self.parse_block_tail_(lo, s, ~[])
3184     }
3185
3186     // parse the rest of a block expression or function body
3187     fn parse_block_tail_(&self, lo: BytePos, s: BlockCheckMode,
3188                          first_item_attrs: ~[Attribute]) -> Block {
3189         let mut stmts = ~[];
3190         let mut expr = None;
3191
3192         // wouldn't it be more uniform to parse view items only, here?
3193         let ParsedItemsAndViewItems {
3194             attrs_remaining: attrs_remaining,
3195             view_items: view_items,
3196             items: items,
3197             _
3198         } = self.parse_items_and_view_items(first_item_attrs,
3199                                             false, false);
3200
3201         for item in items.iter() {
3202             let decl = @spanned(item.span.lo, item.span.hi, DeclItem(*item));
3203             stmts.push(@spanned(item.span.lo, item.span.hi,
3204                                 StmtDecl(decl, ast::DUMMY_NODE_ID)));
3205         }
3206
3207         let mut attributes_box = attrs_remaining;
3208
3209         while (*self.token != token::RBRACE) {
3210             // parsing items even when they're not allowed lets us give
3211             // better error messages and recover more gracefully.
3212             attributes_box.push_all(self.parse_outer_attributes());
3213             match *self.token {
3214                 token::SEMI => {
3215                     if !attributes_box.is_empty() {
3216                         self.span_err(*self.last_span, "expected item after attributes");
3217                         attributes_box = ~[];
3218                     }
3219                     self.bump(); // empty
3220                 }
3221                 token::RBRACE => {
3222                     // fall through and out.
3223                 }
3224                 _ => {
3225                     let stmt = self.parse_stmt(attributes_box);
3226                     attributes_box = ~[];
3227                     match stmt.node {
3228                         StmtExpr(e, stmt_id) => {
3229                             // expression without semicolon
3230                             if classify::stmt_ends_with_semi(stmt) {
3231                                 // Just check for errors and recover; do not eat semicolon yet.
3232                                 self.commit_stmt(stmt, &[], &[token::SEMI, token::RBRACE]);
3233                             }
3234
3235                             match *self.token {
3236                                 token::SEMI => {
3237                                     self.bump();
3238                                     stmts.push(@codemap::Spanned {
3239                                         node: StmtSemi(e, stmt_id),
3240                                         span: stmt.span,
3241                                     });
3242                                 }
3243                                 token::RBRACE => {
3244                                     expr = Some(e);
3245                                 }
3246                                 _ => {
3247                                     stmts.push(stmt);
3248                                 }
3249                             }
3250                         }
3251                         StmtMac(ref m, _) => {
3252                             // statement macro; might be an expr
3253                             let has_semi;
3254                             match *self.token {
3255                                 token::SEMI => {
3256                                     has_semi = true;
3257                                 }
3258                                 token::RBRACE => {
3259                                     // if a block ends in `m!(arg)` without
3260                                     // a `;`, it must be an expr
3261                                     has_semi = false;
3262                                     expr = Some(
3263                                         self.mk_mac_expr(stmt.span.lo,
3264                                                          stmt.span.hi,
3265                                                          m.node.clone()));
3266                                 }
3267                                 _ => {
3268                                     has_semi = false;
3269                                     stmts.push(stmt);
3270                                 }
3271                             }
3272
3273                             if has_semi {
3274                                 self.bump();
3275                                 stmts.push(@codemap::Spanned {
3276                                     node: StmtMac((*m).clone(), true),
3277                                     span: stmt.span,
3278                                 });
3279                             }
3280                         }
3281                         _ => { // all other kinds of statements:
3282                             stmts.push(stmt);
3283
3284                             if classify::stmt_ends_with_semi(stmt) {
3285                                 self.commit_stmt_expecting(stmt, token::SEMI);
3286                             }
3287                         }
3288                     }
3289                 }
3290             }
3291         }
3292
3293         if !attributes_box.is_empty() {
3294             self.span_err(*self.last_span, "expected item after attributes");
3295         }
3296
3297         let hi = self.span.hi;
3298         self.bump();
3299         ast::Block {
3300             view_items: view_items,
3301             stmts: stmts,
3302             expr: expr,
3303             id: ast::DUMMY_NODE_ID,
3304             rules: s,
3305             span: mk_sp(lo, hi),
3306         }
3307     }
3308
3309     fn parse_optional_purity(&self) -> ast::purity {
3310         if self.eat_keyword(keywords::Unsafe) {
3311             ast::unsafe_fn
3312         } else {
3313             ast::impure_fn
3314         }
3315     }
3316
3317     fn parse_optional_onceness(&self) -> ast::Onceness {
3318         if self.eat_keyword(keywords::Once) { ast::Once } else { ast::Many }
3319     }
3320
3321     // matches optbounds = ( ( : ( boundseq )? )? )
3322     // where   boundseq  = ( bound + boundseq ) | bound
3323     // and     bound     = 'static | ty
3324     // Returns "None" if there's no colon (e.g. "T");
3325     // Returns "Some(Empty)" if there's a colon but nothing after (e.g. "T:")
3326     // Returns "Some(stuff)" otherwise (e.g. "T:stuff").
3327     // NB: The None/Some distinction is important for issue #7264.
3328     fn parse_optional_ty_param_bounds(&self) -> Option<OptVec<TyParamBound>> {
3329         if !self.eat(&token::COLON) {
3330             return None;
3331         }
3332
3333         let mut result = opt_vec::Empty;
3334         loop {
3335             match *self.token {
3336                 token::LIFETIME(lifetime) => {
3337                     if "static" == self.id_to_str(lifetime) {
3338                         result.push(RegionTyParamBound);
3339                     } else {
3340                         self.span_err(*self.span,
3341                                       "`'static` is the only permissible region bound here");
3342                     }
3343                     self.bump();
3344                 }
3345                 token::MOD_SEP | token::IDENT(*) => {
3346                     let tref = self.parse_trait_ref();
3347                     result.push(TraitTyParamBound(tref));
3348                 }
3349                 _ => break,
3350             }
3351
3352             if !self.eat(&token::BINOP(token::PLUS)) {
3353                 break;
3354             }
3355         }
3356
3357         return Some(result);
3358     }
3359
3360     // matches typaram = IDENT optbounds
3361     fn parse_ty_param(&self) -> TyParam {
3362         let ident = self.parse_ident();
3363         let opt_bounds = self.parse_optional_ty_param_bounds();
3364         // For typarams we don't care about the difference b/w "<T>" and "<T:>".
3365         let bounds = opt_bounds.unwrap_or_default();
3366         ast::TyParam { ident: ident, id: ast::DUMMY_NODE_ID, bounds: bounds }
3367     }
3368
3369     // parse a set of optional generic type parameter declarations
3370     // matches generics = ( ) | ( < > ) | ( < typaramseq ( , )? > ) | ( < lifetimes ( , )? > )
3371     //                  | ( < lifetimes , typaramseq ( , )? > )
3372     // where   typaramseq = ( typaram ) | ( typaram , typaramseq )
3373     pub fn parse_generics(&self) -> ast::Generics {
3374         if self.eat(&token::LT) {
3375             let lifetimes = self.parse_lifetimes();
3376             let ty_params = self.parse_seq_to_gt(
3377                 Some(token::COMMA),
3378                 |p| p.parse_ty_param());
3379             ast::Generics { lifetimes: lifetimes, ty_params: ty_params }
3380         } else {
3381             ast_util::empty_generics()
3382         }
3383     }
3384
3385     // parse a generic use site
3386     fn parse_generic_values(&self) -> (OptVec<ast::Lifetime>, ~[Ty]) {
3387         if !self.eat(&token::LT) {
3388             (opt_vec::Empty, ~[])
3389         } else {
3390             self.parse_generic_values_after_lt()
3391         }
3392     }
3393
3394     fn parse_generic_values_after_lt(&self) -> (OptVec<ast::Lifetime>, ~[Ty]) {
3395         let lifetimes = self.parse_lifetimes();
3396         let result = self.parse_seq_to_gt(
3397             Some(token::COMMA),
3398             |p| p.parse_ty(false));
3399         (lifetimes, opt_vec::take_vec(result))
3400     }
3401
3402     // parse the argument list and result type of a function declaration
3403     pub fn parse_fn_decl(&self) -> fn_decl {
3404         let args: ~[arg] =
3405             self.parse_unspanned_seq(
3406                 &token::LPAREN,
3407                 &token::RPAREN,
3408                 seq_sep_trailing_disallowed(token::COMMA),
3409                 |p| p.parse_arg()
3410             );
3411
3412         let (ret_style, ret_ty) = self.parse_ret_ty();
3413         ast::fn_decl {
3414             inputs: args,
3415             output: ret_ty,
3416             cf: ret_style,
3417         }
3418     }
3419
3420     fn is_self_ident(&self) -> bool {
3421         match *self.token {
3422           token::IDENT(id, false) => id.name == special_idents::self_.name,
3423           _ => false
3424         }
3425     }
3426
3427     fn expect_self_ident(&self) {
3428         if !self.is_self_ident() {
3429             self.fatal(
3430                 format!(
3431                     "expected `self` but found `{}`",
3432                     self.this_token_to_str()
3433                 )
3434             );
3435         }
3436         self.bump();
3437     }
3438
3439     // parse the argument list and result type of a function
3440     // that may have a self type.
3441     fn parse_fn_decl_with_self(&self, parse_arg_fn: &fn(&Parser) -> arg)
3442         -> (explicit_self, fn_decl) {
3443
3444         fn maybe_parse_explicit_self(cnstr: &fn(v: Mutability) -> ast::explicit_self_,
3445                                      p: &Parser) -> ast::explicit_self_ {
3446             // We need to make sure it isn't a type
3447             if p.look_ahead(1, |t| token::is_keyword(keywords::Self, t)) ||
3448                 ((p.look_ahead(1, |t| token::is_keyword(keywords::Const, t)) ||
3449                   p.look_ahead(1, |t| token::is_keyword(keywords::Mut, t))) &&
3450                  p.look_ahead(2, |t| token::is_keyword(keywords::Self, t))) {
3451
3452                 p.bump();
3453                 let mutability = p.parse_mutability();
3454                 p.expect_self_ident();
3455                 cnstr(mutability)
3456             } else {
3457                 sty_static
3458             }
3459         }
3460
3461         fn maybe_parse_borrowed_explicit_self(this: &Parser) -> ast::explicit_self_ {
3462             // The following things are possible to see here:
3463             //
3464             //     fn(&self)
3465             //     fn(&mut self)
3466             //     fn(&'lt self)
3467             //     fn(&'lt mut self)
3468             //
3469             // We already know that the current token is `&`.
3470
3471             if this.look_ahead(1, |t| token::is_keyword(keywords::Self, t)) {
3472                 this.bump();
3473                 this.expect_self_ident();
3474                 sty_region(None, MutImmutable)
3475             } else if this.look_ahead(1, |t| this.token_is_mutability(t)) &&
3476                     this.look_ahead(2,
3477                                     |t| token::is_keyword(keywords::Self,
3478                                                           t)) {
3479                 this.bump();
3480                 let mutability = this.parse_mutability();
3481                 this.expect_self_ident();
3482                 sty_region(None, mutability)
3483             } else if this.look_ahead(1, |t| this.token_is_lifetime(t)) &&
3484                        this.look_ahead(2,
3485                                        |t| token::is_keyword(keywords::Self,
3486                                                              t)) {
3487                 this.bump();
3488                 let lifetime = this.parse_lifetime();
3489                 this.expect_self_ident();
3490                 sty_region(Some(lifetime), MutImmutable)
3491             } else if this.look_ahead(1, |t| this.token_is_lifetime(t)) &&
3492                       this.look_ahead(2, |t| this.token_is_mutability(t)) &&
3493                       this.look_ahead(3, |t| token::is_keyword(keywords::Self,
3494                                                                t)) {
3495                 this.bump();
3496                 let lifetime = this.parse_lifetime();
3497                 let mutability = this.parse_mutability();
3498                 this.expect_self_ident();
3499                 sty_region(Some(lifetime), mutability)
3500             } else {
3501                 sty_static
3502             }
3503         }
3504
3505         self.expect(&token::LPAREN);
3506
3507         // A bit of complexity and lookahead is needed here in order to be
3508         // backwards compatible.
3509         let lo = self.span.lo;
3510         let explicit_self = match *self.token {
3511           token::BINOP(token::AND) => {
3512             maybe_parse_borrowed_explicit_self(self)
3513           }
3514           token::AT => {
3515             maybe_parse_explicit_self(sty_box, self)
3516           }
3517           token::TILDE => {
3518             maybe_parse_explicit_self(|mutability| {
3519                 if mutability != MutImmutable {
3520                     self.span_err(*self.last_span,
3521                                   "mutability declaration not allowed here");
3522                 }
3523                 sty_uniq(MutImmutable)
3524             }, self)
3525           }
3526           token::IDENT(*) if self.is_self_ident() => {
3527             self.bump();
3528             sty_value(MutImmutable)
3529           }
3530           token::BINOP(token::STAR) => {
3531             // Possibly "*self" or "*mut self" -- not supported. Try to avoid
3532             // emitting cryptic "unexpected token" errors.
3533             self.bump();
3534             let mutability = if self.token_is_mutability(self.token) {
3535                 self.parse_mutability()
3536             } else { MutImmutable };
3537             if self.is_self_ident() {
3538                 self.span_err(*self.span, "cannot pass self by unsafe pointer");
3539                 self.bump();
3540             }
3541             sty_value(mutability)
3542           }
3543           _ if self.token_is_mutability(self.token) &&
3544                self.look_ahead(1, |t| token::is_keyword(keywords::Self, t)) => {
3545             let mutability = self.parse_mutability();
3546             self.expect_self_ident();
3547             sty_value(mutability)
3548           }
3549           _ if self.token_is_mutability(self.token) &&
3550                self.look_ahead(1, |t| *t == token::TILDE) &&
3551                self.look_ahead(2, |t| token::is_keyword(keywords::Self, t)) => {
3552             let mutability = self.parse_mutability();
3553             self.bump();
3554             self.expect_self_ident();
3555             sty_uniq(mutability)
3556           }
3557           _ => {
3558             sty_static
3559           }
3560         };
3561
3562         // If we parsed a self type, expect a comma before the argument list.
3563         let fn_inputs;
3564         if explicit_self != sty_static {
3565             match *self.token {
3566                 token::COMMA => {
3567                     self.bump();
3568                     let sep = seq_sep_trailing_disallowed(token::COMMA);
3569                     fn_inputs = self.parse_seq_to_before_end(
3570                         &token::RPAREN,
3571                         sep,
3572                         parse_arg_fn
3573                     );
3574                 }
3575                 token::RPAREN => {
3576                     fn_inputs = ~[];
3577                 }
3578                 _ => {
3579                     self.fatal(
3580                         format!(
3581                             "expected `,` or `)`, found `{}`",
3582                             self.this_token_to_str()
3583                         )
3584                     );
3585                 }
3586             }
3587         } else {
3588             let sep = seq_sep_trailing_disallowed(token::COMMA);
3589             fn_inputs = self.parse_seq_to_before_end(
3590                 &token::RPAREN,
3591                 sep,
3592                 parse_arg_fn
3593             );
3594         }
3595
3596         self.expect(&token::RPAREN);
3597
3598         let hi = self.span.hi;
3599
3600         let (ret_style, ret_ty) = self.parse_ret_ty();
3601
3602         let fn_decl = ast::fn_decl {
3603             inputs: fn_inputs,
3604             output: ret_ty,
3605             cf: ret_style
3606         };
3607
3608         (spanned(lo, hi, explicit_self), fn_decl)
3609     }
3610
3611     // parse the |arg, arg| header on a lambda
3612     fn parse_fn_block_decl(&self) -> fn_decl {
3613         let inputs_captures = {
3614             if self.eat(&token::OROR) {
3615                 ~[]
3616             } else {
3617                 self.parse_unspanned_seq(
3618                     &token::BINOP(token::OR),
3619                     &token::BINOP(token::OR),
3620                     seq_sep_trailing_disallowed(token::COMMA),
3621                     |p| p.parse_fn_block_arg()
3622                 )
3623             }
3624         };
3625         let output = if self.eat(&token::RARROW) {
3626             self.parse_ty(false)
3627         } else {
3628             Ty { id: ast::DUMMY_NODE_ID, node: ty_infer, span: *self.span }
3629         };
3630
3631         ast::fn_decl {
3632             inputs: inputs_captures,
3633             output: output,
3634             cf: return_val,
3635         }
3636     }
3637
3638     // parse the name and optional generic types of a function header.
3639     fn parse_fn_header(&self) -> (Ident, ast::Generics) {
3640         let id = self.parse_ident();
3641         let generics = self.parse_generics();
3642         (id, generics)
3643     }
3644
3645     fn mk_item(&self, lo: BytePos, hi: BytePos, ident: Ident,
3646                node: item_, vis: visibility,
3647                attrs: ~[Attribute]) -> @item {
3648         @ast::item { ident: ident,
3649                      attrs: attrs,
3650                      id: ast::DUMMY_NODE_ID,
3651                      node: node,
3652                      vis: vis,
3653                      span: mk_sp(lo, hi) }
3654     }
3655
3656     // parse an item-position function declaration.
3657     fn parse_item_fn(&self, purity: purity, abis: AbiSet) -> item_info {
3658         let (ident, generics) = self.parse_fn_header();
3659         let decl = self.parse_fn_decl();
3660         let (inner_attrs, body) = self.parse_inner_attrs_and_block();
3661         (ident,
3662          item_fn(decl, purity, abis, generics, body),
3663          Some(inner_attrs))
3664     }
3665
3666     // parse a method in a trait impl
3667     fn parse_method(&self) -> @method {
3668         let attrs = self.parse_outer_attributes();
3669         let lo = self.span.lo;
3670
3671         let visa = self.parse_visibility();
3672         let pur = self.parse_fn_purity();
3673         let ident = self.parse_ident();
3674         let generics = self.parse_generics();
3675         let (explicit_self, decl) = do self.parse_fn_decl_with_self() |p| {
3676             p.parse_arg()
3677         };
3678
3679         let (inner_attrs, body) = self.parse_inner_attrs_and_block();
3680         let hi = body.span.hi;
3681         let attrs = vec::append(attrs, inner_attrs);
3682         @ast::method {
3683             ident: ident,
3684             attrs: attrs,
3685             generics: generics,
3686             explicit_self: explicit_self,
3687             purity: pur,
3688             decl: decl,
3689             body: body,
3690             id: ast::DUMMY_NODE_ID,
3691             span: mk_sp(lo, hi),
3692             self_id: ast::DUMMY_NODE_ID,
3693             vis: visa,
3694         }
3695     }
3696
3697     // parse trait Foo { ... }
3698     fn parse_item_trait(&self) -> item_info {
3699         let ident = self.parse_ident();
3700         let tps = self.parse_generics();
3701
3702         // Parse traits, if necessary.
3703         let traits;
3704         if *self.token == token::COLON {
3705             self.bump();
3706             traits = self.parse_trait_ref_list(&token::LBRACE);
3707         } else {
3708             traits = ~[];
3709         }
3710
3711         let meths = self.parse_trait_methods();
3712         (ident, item_trait(tps, traits, meths), None)
3713     }
3714
3715     // Parses two variants (with the region/type params always optional):
3716     //    impl<T> Foo { ... }
3717     //    impl<T> ToStr for ~[T] { ... }
3718     fn parse_item_impl(&self) -> item_info {
3719         // First, parse type parameters if necessary.
3720         let generics = self.parse_generics();
3721
3722         // This is a new-style impl declaration.
3723         // XXX: clownshoes
3724         let ident = special_idents::clownshoes_extensions;
3725
3726         // Special case: if the next identifier that follows is '(', don't
3727         // allow this to be parsed as a trait.
3728         let could_be_trait = *self.token != token::LPAREN;
3729
3730         // Parse the trait.
3731         let mut ty = self.parse_ty(false);
3732
3733         // Parse traits, if necessary.
3734         let opt_trait = if could_be_trait && self.eat_keyword(keywords::For) {
3735             // New-style trait. Reinterpret the type as a trait.
3736             let opt_trait_ref = match ty.node {
3737                 ty_path(ref path, None, node_id) => {
3738                     Some(trait_ref {
3739                         path: /* bad */ (*path).clone(),
3740                         ref_id: node_id
3741                     })
3742                 }
3743                 ty_path(*) => {
3744                     self.span_err(ty.span,
3745                                   "bounded traits are only valid in type position");
3746                     None
3747                 }
3748                 _ => {
3749                     self.span_err(ty.span, "not a trait");
3750                     None
3751                 }
3752             };
3753
3754             ty = self.parse_ty(false);
3755             opt_trait_ref
3756         } else {
3757             None
3758         };
3759
3760         let mut meths = ~[];
3761         if self.eat(&token::SEMI) {
3762             self.obsolete(*self.last_span, ObsoleteEmptyImpl);
3763         } else {
3764             self.expect(&token::LBRACE);
3765             while !self.eat(&token::RBRACE) {
3766                 meths.push(self.parse_method());
3767             }
3768         }
3769
3770         (ident, item_impl(generics, opt_trait, ty, meths), None)
3771     }
3772
3773     // parse a::B<~str,int>
3774     fn parse_trait_ref(&self) -> trait_ref {
3775         ast::trait_ref {
3776             path: self.parse_path(LifetimeAndTypesWithoutColons).path,
3777             ref_id: ast::DUMMY_NODE_ID,
3778         }
3779     }
3780
3781     // parse B + C<~str,int> + D
3782     fn parse_trait_ref_list(&self, ket: &token::Token) -> ~[trait_ref] {
3783         self.parse_seq_to_before_end(
3784             ket,
3785             seq_sep_trailing_disallowed(token::BINOP(token::PLUS)),
3786             |p| p.parse_trait_ref()
3787         )
3788     }
3789
3790     // parse struct Foo { ... }
3791     fn parse_item_struct(&self) -> item_info {
3792         let class_name = self.parse_ident();
3793         let generics = self.parse_generics();
3794
3795         let mut fields: ~[@struct_field];
3796         let is_tuple_like;
3797
3798         if self.eat(&token::LBRACE) {
3799             // It's a record-like struct.
3800             is_tuple_like = false;
3801             fields = ~[];
3802             while *self.token != token::RBRACE {
3803                 fields.push(self.parse_struct_decl_field());
3804             }
3805             if fields.len() == 0 {
3806                 self.fatal(format!("Unit-like struct definition should be written as `struct {};`",
3807                                 get_ident_interner().get(class_name.name)));
3808             }
3809             self.bump();
3810         } else if *self.token == token::LPAREN {
3811             // It's a tuple-like struct.
3812             is_tuple_like = true;
3813             fields = do self.parse_unspanned_seq(
3814                 &token::LPAREN,
3815                 &token::RPAREN,
3816                 seq_sep_trailing_allowed(token::COMMA)
3817             ) |p| {
3818                 let attrs = self.parse_outer_attributes();
3819                 let lo = p.span.lo;
3820                 let struct_field_ = ast::struct_field_ {
3821                     kind: unnamed_field,
3822                     id: ast::DUMMY_NODE_ID,
3823                     ty: p.parse_ty(false),
3824                     attrs: attrs,
3825                 };
3826                 @spanned(lo, p.span.hi, struct_field_)
3827             };
3828             self.expect(&token::SEMI);
3829         } else if self.eat(&token::SEMI) {
3830             // It's a unit-like struct.
3831             is_tuple_like = true;
3832             fields = ~[];
3833         } else {
3834             self.fatal(
3835                 format!(
3836                     "expected `\\{`, `(`, or `;` after struct name \
3837                     but found `{}`",
3838                     self.this_token_to_str()
3839                 )
3840             );
3841         }
3842
3843         let _ = ast::DUMMY_NODE_ID;  // XXX: Workaround for crazy bug.
3844         let new_id = ast::DUMMY_NODE_ID;
3845         (class_name,
3846          item_struct(@ast::struct_def {
3847              fields: fields,
3848              ctor_id: if is_tuple_like { Some(new_id) } else { None }
3849          }, generics),
3850          None)
3851     }
3852
3853     fn token_is_pound_or_doc_comment(&self, tok: token::Token) -> bool {
3854         match tok {
3855             token::POUND | token::DOC_COMMENT(_) => true,
3856             _ => false
3857         }
3858     }
3859
3860     // parse a structure field declaration
3861     pub fn parse_single_struct_field(&self,
3862                                      vis: visibility,
3863                                      attrs: ~[Attribute])
3864                                      -> @struct_field {
3865         let a_var = self.parse_name_and_ty(vis, attrs);
3866         match *self.token {
3867             token::COMMA => {
3868                 self.bump();
3869             }
3870             token::RBRACE => {}
3871             _ => {
3872                 self.span_fatal(*self.span,
3873                                 format!("expected `,`, or `\\}` but found `{}`",
3874                                      self.this_token_to_str()));
3875             }
3876         }
3877         a_var
3878     }
3879
3880     // parse an element of a struct definition
3881     fn parse_struct_decl_field(&self) -> @struct_field {
3882
3883         let attrs = self.parse_outer_attributes();
3884
3885         if self.eat_keyword(keywords::Priv) {
3886             return self.parse_single_struct_field(private, attrs);
3887         }
3888
3889         if self.eat_keyword(keywords::Pub) {
3890            return self.parse_single_struct_field(public, attrs);
3891         }
3892
3893         return self.parse_single_struct_field(inherited, attrs);
3894     }
3895
3896     // parse visiility: PUB, PRIV, or nothing
3897     fn parse_visibility(&self) -> visibility {
3898         if self.eat_keyword(keywords::Pub) { public }
3899         else if self.eat_keyword(keywords::Priv) { private }
3900         else { inherited }
3901     }
3902
3903     // given a termination token and a vector of already-parsed
3904     // attributes (of length 0 or 1), parse all of the items in a module
3905     fn parse_mod_items(&self,
3906                        term: token::Token,
3907                        first_item_attrs: ~[Attribute])
3908                        -> _mod {
3909         // parse all of the items up to closing or an attribute.
3910         // view items are legal here.
3911         let ParsedItemsAndViewItems {
3912             attrs_remaining: attrs_remaining,
3913             view_items: view_items,
3914             items: starting_items,
3915             _
3916         } = self.parse_items_and_view_items(first_item_attrs, true, true);
3917         let mut items: ~[@item] = starting_items;
3918         let attrs_remaining_len = attrs_remaining.len();
3919
3920         // don't think this other loop is even necessary....
3921
3922         let mut first = true;
3923         while *self.token != term {
3924             let mut attrs = self.parse_outer_attributes();
3925             if first {
3926                 attrs = attrs_remaining + attrs;
3927                 first = false;
3928             }
3929             debug!("parse_mod_items: parse_item_or_view_item(attrs={:?})",
3930                    attrs);
3931             match self.parse_item_or_view_item(attrs,
3932                                                true /* macros allowed */) {
3933               iovi_item(item) => items.push(item),
3934               iovi_view_item(view_item) => {
3935                 self.span_fatal(view_item.span,
3936                                 "view items must be declared at the top of \
3937                                  the module");
3938               }
3939               _ => {
3940                 self.fatal(format!("expected item but found `{}`",
3941                                 self.this_token_to_str()));
3942               }
3943             }
3944         }
3945
3946         if first && attrs_remaining_len > 0u {
3947             // We parsed attributes for the first item but didn't find it
3948             self.span_err(*self.last_span, "expected item after attributes");
3949         }
3950
3951         ast::_mod { view_items: view_items, items: items }
3952     }
3953
3954     fn parse_item_const(&self) -> item_info {
3955         let m = if self.eat_keyword(keywords::Mut) {MutMutable} else {MutImmutable};
3956         let id = self.parse_ident();
3957         self.expect(&token::COLON);
3958         let ty = self.parse_ty(false);
3959         self.expect(&token::EQ);
3960         let e = self.parse_expr();
3961         self.commit_expr_expecting(e, token::SEMI);
3962         (id, item_static(ty, m, e), None)
3963     }
3964
3965     // parse a `mod <foo> { ... }` or `mod <foo>;` item
3966     fn parse_item_mod(&self, outer_attrs: &[Attribute]) -> item_info {
3967         let id_span = *self.span;
3968         let id = self.parse_ident();
3969         if *self.token == token::SEMI {
3970             self.bump();
3971             // This mod is in an external file. Let's go get it!
3972             let (m, attrs) = self.eval_src_mod(id, outer_attrs, id_span);
3973             (id, m, Some(attrs))
3974         } else {
3975             self.push_mod_path(id, outer_attrs);
3976             self.expect(&token::LBRACE);
3977             let (inner, next) = self.parse_inner_attrs_and_next();
3978             let m = self.parse_mod_items(token::RBRACE, next);
3979             self.expect(&token::RBRACE);
3980             self.pop_mod_path();
3981             (id, item_mod(m), Some(inner))
3982         }
3983     }
3984
3985     fn push_mod_path(&self, id: Ident, attrs: &[Attribute]) {
3986         let default_path = token::interner_get(id.name);
3987         let file_path = match ::attr::first_attr_value_str_by_name(attrs,
3988                                                                    "path") {
3989             Some(d) => d,
3990             None => default_path
3991         };
3992         self.mod_path_stack.push(file_path)
3993     }
3994
3995     fn pop_mod_path(&self) {
3996         self.mod_path_stack.pop();
3997     }
3998
3999     // read a module from a source file.
4000     fn eval_src_mod(&self,
4001                     id: ast::Ident,
4002                     outer_attrs: &[ast::Attribute],
4003                     id_sp: Span)
4004                     -> (ast::item_, ~[ast::Attribute]) {
4005         let mut prefix = Path::new(self.sess.cm.span_to_filename(*self.span));
4006         prefix.pop();
4007         let mod_path_stack = &*self.mod_path_stack;
4008         let mod_path = Path::new(".").join_many(*mod_path_stack);
4009         let dir_path = prefix.join(&mod_path);
4010         let file_path = match ::attr::first_attr_value_str_by_name(
4011                 outer_attrs, "path") {
4012             Some(d) => dir_path.join(d),
4013             None => {
4014                 let mod_name = token::interner_get(id.name).to_owned();
4015                 let default_path_str = mod_name + ".rs";
4016                 let secondary_path_str = mod_name + "/mod.rs";
4017                 let default_path = dir_path.join(default_path_str.as_slice());
4018                 let secondary_path = dir_path.join(secondary_path_str.as_slice());
4019                 let default_exists = default_path.exists();
4020                 let secondary_exists = secondary_path.exists();
4021                 match (default_exists, secondary_exists) {
4022                     (true, false) => default_path,
4023                     (false, true) => secondary_path,
4024                     (false, false) => {
4025                         self.span_fatal(id_sp, format!("file not found for module `{}`", mod_name));
4026                     }
4027                     (true, true) => {
4028                         self.span_fatal(id_sp,
4029                                         format!("file for module `{}` found at both {} and {}",
4030                                              mod_name, default_path_str, secondary_path_str));
4031                     }
4032                 }
4033             }
4034         };
4035
4036         self.eval_src_mod_from_path(file_path,
4037                                     outer_attrs.to_owned(),
4038                                     id_sp)
4039     }
4040
4041     fn eval_src_mod_from_path(&self,
4042                               path: Path,
4043                               outer_attrs: ~[ast::Attribute],
4044                               id_sp: Span) -> (ast::item_, ~[ast::Attribute]) {
4045         let maybe_i = do self.sess.included_mod_stack.iter().position |p| { *p == path };
4046         match maybe_i {
4047             Some(i) => {
4048                 let stack = &self.sess.included_mod_stack;
4049                 let mut err = ~"circular modules: ";
4050                 for p in stack.slice(i, stack.len()).iter() {
4051                     do p.display().with_str |s| {
4052                         err.push_str(s);
4053                     }
4054                     err.push_str(" -> ");
4055                 }
4056                 do path.display().with_str |s| {
4057                     err.push_str(s);
4058                 }
4059                 self.span_fatal(id_sp, err);
4060             }
4061             None => ()
4062         }
4063         self.sess.included_mod_stack.push(path.clone());
4064
4065         let p0 =
4066             new_sub_parser_from_file(self.sess,
4067                                      self.cfg.clone(),
4068                                      &path,
4069                                      id_sp);
4070         let (inner, next) = p0.parse_inner_attrs_and_next();
4071         let mod_attrs = vec::append(outer_attrs, inner);
4072         let first_item_outer_attrs = next;
4073         let m0 = p0.parse_mod_items(token::EOF, first_item_outer_attrs);
4074         self.sess.included_mod_stack.pop();
4075         return (ast::item_mod(m0), mod_attrs);
4076     }
4077
4078     // parse a function declaration from a foreign module
4079     fn parse_item_foreign_fn(&self, vis: ast::visibility,
4080                              attrs: ~[Attribute]) -> @foreign_item {
4081         let lo = self.span.lo;
4082
4083         // Parse obsolete purity.
4084         let purity = self.parse_fn_purity();
4085         if purity != impure_fn {
4086             self.obsolete(*self.last_span, ObsoleteUnsafeExternFn);
4087         }
4088
4089         let (ident, generics) = self.parse_fn_header();
4090         let decl = self.parse_fn_decl();
4091         let hi = self.span.hi;
4092         self.expect(&token::SEMI);
4093         @ast::foreign_item { ident: ident,
4094                              attrs: attrs,
4095                              node: foreign_item_fn(decl, generics),
4096                              id: ast::DUMMY_NODE_ID,
4097                              span: mk_sp(lo, hi),
4098                              vis: vis }
4099     }
4100
4101     // parse a static item from a foreign module
4102     fn parse_item_foreign_static(&self, vis: ast::visibility,
4103                                  attrs: ~[Attribute]) -> @foreign_item {
4104         let lo = self.span.lo;
4105
4106         self.expect_keyword(keywords::Static);
4107         let mutbl = self.eat_keyword(keywords::Mut);
4108
4109         let ident = self.parse_ident();
4110         self.expect(&token::COLON);
4111         let ty = self.parse_ty(false);
4112         let hi = self.span.hi;
4113         self.expect(&token::SEMI);
4114         @ast::foreign_item { ident: ident,
4115                              attrs: attrs,
4116                              node: foreign_item_static(ty, mutbl),
4117                              id: ast::DUMMY_NODE_ID,
4118                              span: mk_sp(lo, hi),
4119                              vis: vis }
4120     }
4121
4122     // parse safe/unsafe and fn
4123     fn parse_fn_purity(&self) -> purity {
4124         if self.eat_keyword(keywords::Fn) { impure_fn }
4125         else if self.eat_keyword(keywords::Unsafe) {
4126             self.expect_keyword(keywords::Fn);
4127             unsafe_fn
4128         }
4129         else { self.unexpected(); }
4130     }
4131
4132
4133     // at this point, this is essentially a wrapper for
4134     // parse_foreign_items.
4135     fn parse_foreign_mod_items(&self,
4136                                abis: AbiSet,
4137                                first_item_attrs: ~[Attribute])
4138                                -> foreign_mod {
4139         let ParsedItemsAndViewItems {
4140             attrs_remaining: attrs_remaining,
4141             view_items: view_items,
4142             items: _,
4143             foreign_items: foreign_items
4144         } = self.parse_foreign_items(first_item_attrs, true);
4145         if (! attrs_remaining.is_empty()) {
4146             self.span_err(*self.last_span,
4147                           "expected item after attributes");
4148         }
4149         assert!(*self.token == token::RBRACE);
4150         ast::foreign_mod {
4151             abis: abis,
4152             view_items: view_items,
4153             items: foreign_items
4154         }
4155     }
4156
4157     // parse extern foo; or extern mod foo { ... } or extern { ... }
4158     fn parse_item_foreign_mod(&self,
4159                               lo: BytePos,
4160                               opt_abis: Option<AbiSet>,
4161                               visibility: visibility,
4162                               attrs: ~[Attribute],
4163                               items_allowed: bool)
4164                               -> item_or_view_item {
4165         let mut must_be_named_mod = false;
4166         if self.is_keyword(keywords::Mod) {
4167             must_be_named_mod = true;
4168             self.expect_keyword(keywords::Mod);
4169         } else if *self.token != token::LBRACE {
4170             self.span_fatal(*self.span,
4171                             format!("expected `\\{` or `mod` but found `{}`",
4172                                  self.this_token_to_str()));
4173         }
4174
4175         let (named, maybe_path, ident) = match *self.token {
4176             token::IDENT(*) => {
4177                 let the_ident = self.parse_ident();
4178                 let path = if *self.token == token::EQ {
4179                     self.bump();
4180                     Some(self.parse_str())
4181                 }
4182                 else { None };
4183                 (true, path, the_ident)
4184             }
4185             _ => {
4186                 if must_be_named_mod {
4187                     self.span_fatal(*self.span,
4188                                     format!("expected foreign module name but \
4189                                           found `{}`",
4190                                          self.this_token_to_str()));
4191                 }
4192
4193                 (false, None,
4194                  special_idents::clownshoes_foreign_mod)
4195             }
4196         };
4197
4198         // extern mod foo { ... } or extern { ... }
4199         if items_allowed && self.eat(&token::LBRACE) {
4200             // `extern mod foo { ... }` is obsolete.
4201             if named {
4202                 self.obsolete(*self.last_span, ObsoleteNamedExternModule);
4203             }
4204
4205             let abis = opt_abis.unwrap_or(AbiSet::C());
4206
4207             let (inner, next) = self.parse_inner_attrs_and_next();
4208             let m = self.parse_foreign_mod_items(abis, next);
4209             self.expect(&token::RBRACE);
4210
4211             return iovi_item(self.mk_item(lo,
4212                                           self.last_span.hi,
4213                                           ident,
4214                                           item_foreign_mod(m),
4215                                           visibility,
4216                                           maybe_append(attrs, Some(inner))));
4217         }
4218
4219         if opt_abis.is_some() {
4220             self.span_err(*self.span, "an ABI may not be specified here");
4221         }
4222
4223         // extern mod foo;
4224         let metadata = self.parse_optional_meta();
4225         self.expect(&token::SEMI);
4226         iovi_view_item(ast::view_item {
4227             node: view_item_extern_mod(ident, maybe_path, metadata, ast::DUMMY_NODE_ID),
4228             attrs: attrs,
4229             vis: visibility,
4230             span: mk_sp(lo, self.last_span.hi)
4231         })
4232     }
4233
4234     // parse type Foo = Bar;
4235     fn parse_item_type(&self) -> item_info {
4236         let ident = self.parse_ident();
4237         let tps = self.parse_generics();
4238         self.expect(&token::EQ);
4239         let ty = self.parse_ty(false);
4240         self.expect(&token::SEMI);
4241         (ident, item_ty(ty, tps), None)
4242     }
4243
4244     // parse a structure-like enum variant definition
4245     // this should probably be renamed or refactored...
4246     fn parse_struct_def(&self) -> @struct_def {
4247         let mut fields: ~[@struct_field] = ~[];
4248         while *self.token != token::RBRACE {
4249             fields.push(self.parse_struct_decl_field());
4250         }
4251         self.bump();
4252
4253         return @ast::struct_def {
4254             fields: fields,
4255             ctor_id: None
4256         };
4257     }
4258
4259     // parse the part of an "enum" decl following the '{'
4260     fn parse_enum_def(&self, _generics: &ast::Generics) -> enum_def {
4261         let mut variants = ~[];
4262         let mut all_nullary = true;
4263         let mut have_disr = false;
4264         while *self.token != token::RBRACE {
4265             let variant_attrs = self.parse_outer_attributes();
4266             let vlo = self.span.lo;
4267
4268             let vis = self.parse_visibility();
4269
4270             let ident;
4271             let kind;
4272             let mut args = ~[];
4273             let mut disr_expr = None;
4274             ident = self.parse_ident();
4275             if self.eat(&token::LBRACE) {
4276                 // Parse a struct variant.
4277                 all_nullary = false;
4278                 kind = struct_variant_kind(self.parse_struct_def());
4279             } else if *self.token == token::LPAREN {
4280                 all_nullary = false;
4281                 let arg_tys = self.parse_unspanned_seq(
4282                     &token::LPAREN,
4283                     &token::RPAREN,
4284                     seq_sep_trailing_disallowed(token::COMMA),
4285                     |p| p.parse_ty(false)
4286                 );
4287                 for ty in arg_tys.move_iter() {
4288                     args.push(ast::variant_arg {
4289                         ty: ty,
4290                         id: ast::DUMMY_NODE_ID,
4291                     });
4292                 }
4293                 kind = tuple_variant_kind(args);
4294             } else if self.eat(&token::EQ) {
4295                 have_disr = true;
4296                 disr_expr = Some(self.parse_expr());
4297                 kind = tuple_variant_kind(args);
4298             } else {
4299                 kind = tuple_variant_kind(~[]);
4300             }
4301
4302             let vr = ast::variant_ {
4303                 name: ident,
4304                 attrs: variant_attrs,
4305                 kind: kind,
4306                 id: ast::DUMMY_NODE_ID,
4307                 disr_expr: disr_expr,
4308                 vis: vis,
4309             };
4310             variants.push(spanned(vlo, self.last_span.hi, vr));
4311
4312             if !self.eat(&token::COMMA) { break; }
4313         }
4314         self.expect(&token::RBRACE);
4315         if (have_disr && !all_nullary) {
4316             self.fatal("discriminator values can only be used with a c-like \
4317                         enum");
4318         }
4319
4320         ast::enum_def { variants: variants }
4321     }
4322
4323     // parse an "enum" declaration
4324     fn parse_item_enum(&self) -> item_info {
4325         let id = self.parse_ident();
4326         let generics = self.parse_generics();
4327         self.expect(&token::LBRACE);
4328
4329         let enum_definition = self.parse_enum_def(&generics);
4330         (id, item_enum(enum_definition, generics), None)
4331     }
4332
4333     fn parse_fn_ty_sigil(&self) -> Option<Sigil> {
4334         match *self.token {
4335             token::AT => {
4336                 self.bump();
4337                 Some(ManagedSigil)
4338             }
4339             token::TILDE => {
4340                 self.bump();
4341                 Some(OwnedSigil)
4342             }
4343             token::BINOP(token::AND) => {
4344                 self.bump();
4345                 Some(BorrowedSigil)
4346             }
4347             _ => {
4348                 None
4349             }
4350         }
4351     }
4352
4353     fn fn_expr_lookahead(&self, tok: &token::Token) -> bool {
4354         match *tok {
4355           token::LPAREN | token::AT | token::TILDE | token::BINOP(_) => true,
4356           _ => false
4357         }
4358     }
4359
4360     // parse a string as an ABI spec on an extern type or module
4361     fn parse_opt_abis(&self) -> Option<AbiSet> {
4362         match *self.token {
4363             token::LIT_STR(s)
4364             | token::LIT_STR_RAW(s, _) => {
4365                 self.bump();
4366                 let the_string = ident_to_str(&s);
4367                 let mut abis = AbiSet::empty();
4368                 for word in the_string.word_iter() {
4369                     match abi::lookup(word) {
4370                         Some(abi) => {
4371                             if abis.contains(abi) {
4372                                 self.span_err(
4373                                     *self.span,
4374                                     format!("ABI `{}` appears twice",
4375                                          word));
4376                             } else {
4377                                 abis.add(abi);
4378                             }
4379                         }
4380
4381                         None => {
4382                             self.span_err(
4383                                 *self.span,
4384                                 format!("illegal ABI: \
4385                                       expected one of [{}], \
4386                                       found `{}`",
4387                                      abi::all_names().connect(", "),
4388                                      word));
4389                         }
4390                      }
4391                  }
4392                 Some(abis)
4393             }
4394
4395             _ => {
4396                 None
4397              }
4398          }
4399     }
4400
4401     // parse one of the items or view items allowed by the
4402     // flags; on failure, return iovi_none.
4403     // NB: this function no longer parses the items inside an
4404     // extern mod.
4405     fn parse_item_or_view_item(&self,
4406                                attrs: ~[Attribute],
4407                                macros_allowed: bool)
4408                                -> item_or_view_item {
4409         match *self.token {
4410             INTERPOLATED(token::nt_item(item)) => {
4411                 self.bump();
4412                 let new_attrs = vec::append(attrs, item.attrs);
4413                 return iovi_item(@ast::item {
4414                         attrs: new_attrs,
4415                         ..(*item).clone()});
4416             }
4417             _ => {}
4418         }
4419
4420         let lo = self.span.lo;
4421
4422         let visibility = self.parse_visibility();
4423
4424         // must be a view item:
4425         if self.eat_keyword(keywords::Use) {
4426             // USE ITEM (iovi_view_item)
4427             let view_item = self.parse_use();
4428             self.expect(&token::SEMI);
4429             return iovi_view_item(ast::view_item {
4430                 node: view_item,
4431                 attrs: attrs,
4432                 vis: visibility,
4433                 span: mk_sp(lo, self.last_span.hi)
4434             });
4435         }
4436         // either a view item or an item:
4437         if self.eat_keyword(keywords::Extern) {
4438             let opt_abis = self.parse_opt_abis();
4439
4440             if self.eat_keyword(keywords::Fn) {
4441                 // EXTERN FUNCTION ITEM
4442                 let abis = opt_abis.unwrap_or(AbiSet::C());
4443                 let (ident, item_, extra_attrs) =
4444                     self.parse_item_fn(extern_fn, abis);
4445                 return iovi_item(self.mk_item(lo, self.last_span.hi, ident,
4446                                               item_, visibility,
4447                                               maybe_append(attrs,
4448                                                            extra_attrs)));
4449             } else  {
4450                 // EXTERN MODULE ITEM (iovi_view_item)
4451                 return self.parse_item_foreign_mod(lo, opt_abis, visibility, attrs,
4452                                                    true);
4453             }
4454         }
4455         // the rest are all guaranteed to be items:
4456         if self.is_keyword(keywords::Static) {
4457             // STATIC ITEM
4458             self.bump();
4459             let (ident, item_, extra_attrs) = self.parse_item_const();
4460             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4461                                           visibility,
4462                                           maybe_append(attrs, extra_attrs)));
4463         }
4464         if self.is_keyword(keywords::Fn) &&
4465                 self.look_ahead(1, |f| !self.fn_expr_lookahead(f)) {
4466             // FUNCTION ITEM
4467             self.bump();
4468             let (ident, item_, extra_attrs) =
4469                 self.parse_item_fn(impure_fn, AbiSet::Rust());
4470             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4471                                           visibility,
4472                                           maybe_append(attrs, extra_attrs)));
4473         }
4474         if self.is_keyword(keywords::Unsafe)
4475             && self.look_ahead(1u, |t| *t != token::LBRACE) {
4476             // UNSAFE FUNCTION ITEM
4477             self.bump();
4478             self.expect_keyword(keywords::Fn);
4479             let (ident, item_, extra_attrs) =
4480                 self.parse_item_fn(unsafe_fn, AbiSet::Rust());
4481             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4482                                           visibility,
4483                                           maybe_append(attrs, extra_attrs)));
4484         }
4485         if self.eat_keyword(keywords::Mod) {
4486             // MODULE ITEM
4487             let (ident, item_, extra_attrs) = self.parse_item_mod(attrs);
4488             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4489                                           visibility,
4490                                           maybe_append(attrs, extra_attrs)));
4491         }
4492         if self.eat_keyword(keywords::Type) {
4493             // TYPE ITEM
4494             let (ident, item_, extra_attrs) = self.parse_item_type();
4495             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4496                                           visibility,
4497                                           maybe_append(attrs, extra_attrs)));
4498         }
4499         if self.eat_keyword(keywords::Enum) {
4500             // ENUM ITEM
4501             let (ident, item_, extra_attrs) = self.parse_item_enum();
4502             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4503                                           visibility,
4504                                           maybe_append(attrs, extra_attrs)));
4505         }
4506         if self.eat_keyword(keywords::Trait) {
4507             // TRAIT ITEM
4508             let (ident, item_, extra_attrs) = self.parse_item_trait();
4509             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4510                                           visibility,
4511                                           maybe_append(attrs, extra_attrs)));
4512         }
4513         if self.eat_keyword(keywords::Impl) {
4514             // IMPL ITEM
4515             let (ident, item_, extra_attrs) = self.parse_item_impl();
4516             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4517                                           visibility,
4518                                           maybe_append(attrs, extra_attrs)));
4519         }
4520         if self.eat_keyword(keywords::Struct) {
4521             // STRUCT ITEM
4522             let (ident, item_, extra_attrs) = self.parse_item_struct();
4523             return iovi_item(self.mk_item(lo, self.last_span.hi, ident, item_,
4524                                           visibility,
4525                                           maybe_append(attrs, extra_attrs)));
4526         }
4527         self.parse_macro_use_or_failure(attrs,macros_allowed,lo,visibility)
4528     }
4529
4530     // parse a foreign item; on failure, return iovi_none.
4531     fn parse_foreign_item(&self,
4532                           attrs: ~[Attribute],
4533                           macros_allowed: bool)
4534                           -> item_or_view_item {
4535         maybe_whole!(iovi self, nt_item);
4536         let lo = self.span.lo;
4537
4538         let visibility = self.parse_visibility();
4539
4540         if self.is_keyword(keywords::Static) {
4541             // FOREIGN STATIC ITEM
4542             let item = self.parse_item_foreign_static(visibility, attrs);
4543             return iovi_foreign_item(item);
4544         }
4545         if self.is_keyword(keywords::Fn) || self.is_keyword(keywords::Unsafe) {
4546             // FOREIGN FUNCTION ITEM
4547             let item = self.parse_item_foreign_fn(visibility, attrs);
4548             return iovi_foreign_item(item);
4549         }
4550         self.parse_macro_use_or_failure(attrs,macros_allowed,lo,visibility)
4551     }
4552
4553     // this is the fall-through for parsing items.
4554     fn parse_macro_use_or_failure(
4555         &self,
4556         attrs: ~[Attribute],
4557         macros_allowed: bool,
4558         lo : BytePos,
4559         visibility : visibility
4560     ) -> item_or_view_item {
4561         if macros_allowed && !token::is_any_keyword(self.token)
4562                 && self.look_ahead(1, |t| *t == token::NOT)
4563                 && (self.look_ahead(2, |t| is_plain_ident(t))
4564                     || self.look_ahead(2, |t| *t == token::LPAREN)
4565                     || self.look_ahead(2, |t| *t == token::LBRACE)) {
4566             // MACRO INVOCATION ITEM
4567
4568             // item macro.
4569             let pth = self.parse_path(NoTypesAllowed).path;
4570             self.expect(&token::NOT);
4571
4572             // a 'special' identifier (like what `macro_rules!` uses)
4573             // is optional. We should eventually unify invoc syntax
4574             // and remove this.
4575             let id = if is_plain_ident(&*self.token) {
4576                 self.parse_ident()
4577             } else {
4578                 token::special_idents::invalid // no special identifier
4579             };
4580             // eat a matched-delimiter token tree:
4581             let tts = match *self.token {
4582                 token::LPAREN | token::LBRACE => {
4583                     let ket = token::flip_delimiter(&*self.token);
4584                     self.bump();
4585                     self.parse_seq_to_end(&ket,
4586                                           seq_sep_none(),
4587                                           |p| p.parse_token_tree())
4588                 }
4589                 _ => self.fatal("expected open delimiter")
4590             };
4591             // single-variant-enum... :
4592             let m = ast::mac_invoc_tt(pth, tts, EMPTY_CTXT);
4593             let m: ast::mac = codemap::Spanned { node: m,
4594                                              span: mk_sp(self.span.lo,
4595                                                          self.span.hi) };
4596             let item_ = item_mac(m);
4597             return iovi_item(self.mk_item(lo, self.last_span.hi, id, item_,
4598                                           visibility, attrs));
4599         }
4600
4601         // FAILURE TO PARSE ITEM
4602         if visibility != inherited {
4603             let mut s = ~"unmatched visibility `";
4604             if visibility == public {
4605                 s.push_str("pub")
4606             } else {
4607                 s.push_str("priv")
4608             }
4609             s.push_char('`');
4610             self.span_fatal(*self.last_span, s);
4611         }
4612         return iovi_none(attrs);
4613     }
4614
4615     pub fn parse_item(&self, attrs: ~[Attribute]) -> Option<@ast::item> {
4616         match self.parse_item_or_view_item(attrs, true) {
4617             iovi_none(_) => None,
4618             iovi_view_item(_) =>
4619                 self.fatal("view items are not allowed here"),
4620             iovi_foreign_item(_) =>
4621                 self.fatal("foreign items are not allowed here"),
4622             iovi_item(item) => Some(item)
4623         }
4624     }
4625
4626     // parse, e.g., "use a::b::{z,y}"
4627     fn parse_use(&self) -> view_item_ {
4628         return view_item_use(self.parse_view_paths());
4629     }
4630
4631
4632     // matches view_path : MOD? IDENT EQ non_global_path
4633     // | MOD? non_global_path MOD_SEP LBRACE RBRACE
4634     // | MOD? non_global_path MOD_SEP LBRACE ident_seq RBRACE
4635     // | MOD? non_global_path MOD_SEP STAR
4636     // | MOD? non_global_path
4637     fn parse_view_path(&self) -> @view_path {
4638         let lo = self.span.lo;
4639
4640         let first_ident = self.parse_ident();
4641         let mut path = ~[first_ident];
4642         debug!("parsed view_path: {}", self.id_to_str(first_ident));
4643         match *self.token {
4644           token::EQ => {
4645             // x = foo::bar
4646             self.bump();
4647             path = ~[self.parse_ident()];
4648             while *self.token == token::MOD_SEP {
4649                 self.bump();
4650                 let id = self.parse_ident();
4651                 path.push(id);
4652             }
4653             let path = ast::Path {
4654                 span: mk_sp(lo, self.span.hi),
4655                 global: false,
4656                 segments: path.move_iter().map(|identifier| {
4657                     ast::PathSegment {
4658                         identifier: identifier,
4659                         lifetime: None,
4660                         types: opt_vec::Empty,
4661                     }
4662                 }).collect()
4663             };
4664             return @spanned(lo, self.span.hi,
4665                             view_path_simple(first_ident,
4666                                              path,
4667                                              ast::DUMMY_NODE_ID));
4668           }
4669
4670           token::MOD_SEP => {
4671             // foo::bar or foo::{a,b,c} or foo::*
4672             while *self.token == token::MOD_SEP {
4673                 self.bump();
4674
4675                 match *self.token {
4676                   token::IDENT(i, _) => {
4677                     self.bump();
4678                     path.push(i);
4679                   }
4680
4681                   // foo::bar::{a,b,c}
4682                   token::LBRACE => {
4683                     let idents = self.parse_unspanned_seq(
4684                         &token::LBRACE,
4685                         &token::RBRACE,
4686                         seq_sep_trailing_allowed(token::COMMA),
4687                         |p| p.parse_path_list_ident()
4688                     );
4689                     let path = ast::Path {
4690                         span: mk_sp(lo, self.span.hi),
4691                         global: false,
4692                         segments: path.move_iter().map(|identifier| {
4693                             ast::PathSegment {
4694                                 identifier: identifier,
4695                                 lifetime: None,
4696                                 types: opt_vec::Empty,
4697                             }
4698                         }).collect()
4699                     };
4700                     return @spanned(lo, self.span.hi,
4701                                  view_path_list(path, idents, ast::DUMMY_NODE_ID));
4702                   }
4703
4704                   // foo::bar::*
4705                   token::BINOP(token::STAR) => {
4706                     self.bump();
4707                     let path = ast::Path {
4708                         span: mk_sp(lo, self.span.hi),
4709                         global: false,
4710                         segments: path.move_iter().map(|identifier| {
4711                             ast::PathSegment {
4712                                 identifier: identifier,
4713                                 lifetime: None,
4714                                 types: opt_vec::Empty,
4715                             }
4716                         }).collect()
4717                     };
4718                     return @spanned(lo, self.span.hi,
4719                                     view_path_glob(path, ast::DUMMY_NODE_ID));
4720                   }
4721
4722                   _ => break
4723                 }
4724             }
4725           }
4726           _ => ()
4727         }
4728         let last = path[path.len() - 1u];
4729         let path = ast::Path {
4730             span: mk_sp(lo, self.span.hi),
4731             global: false,
4732             segments: path.move_iter().map(|identifier| {
4733                 ast::PathSegment {
4734                     identifier: identifier,
4735                     lifetime: None,
4736                     types: opt_vec::Empty,
4737                 }
4738             }).collect()
4739         };
4740         return @spanned(lo,
4741                         self.last_span.hi,
4742                         view_path_simple(last, path, ast::DUMMY_NODE_ID));
4743     }
4744
4745     // matches view_paths = view_path | view_path , view_paths
4746     fn parse_view_paths(&self) -> ~[@view_path] {
4747         let mut vp = ~[self.parse_view_path()];
4748         while *self.token == token::COMMA {
4749             self.bump();
4750             vp.push(self.parse_view_path());
4751         }
4752         return vp;
4753     }
4754
4755     fn is_view_item(&self) -> bool {
4756         if !self.is_keyword(keywords::Pub) && !self.is_keyword(keywords::Priv) {
4757             token::is_keyword(keywords::Use, self.token)
4758                 || (token::is_keyword(keywords::Extern, self.token) &&
4759                     self.look_ahead(1,
4760                                     |t| token::is_keyword(keywords::Mod, t)))
4761         } else {
4762             self.look_ahead(1, |t| token::is_keyword(keywords::Use, t))
4763                 || (self.look_ahead(1,
4764                                     |t| token::is_keyword(keywords::Extern,
4765                                                           t)) &&
4766                     self.look_ahead(2,
4767                                     |t| token::is_keyword(keywords::Mod, t)))
4768         }
4769     }
4770
4771     // parse a view item.
4772     fn parse_view_item(
4773         &self,
4774         attrs: ~[Attribute],
4775         vis: visibility
4776     ) -> view_item {
4777         let lo = self.span.lo;
4778         let node = if self.eat_keyword(keywords::Use) {
4779             self.parse_use()
4780         } else if self.eat_keyword(keywords::Extern) {
4781             self.expect_keyword(keywords::Mod);
4782             let ident = self.parse_ident();
4783             let path = if *self.token == token::EQ {
4784                 self.bump();
4785                 Some(self.parse_str())
4786             }
4787             else { None };
4788             let metadata = self.parse_optional_meta();
4789             view_item_extern_mod(ident, path, metadata, ast::DUMMY_NODE_ID)
4790         } else {
4791             self.bug("expected view item");
4792         };
4793         self.expect(&token::SEMI);
4794         ast::view_item { node: node,
4795                           attrs: attrs,
4796                           vis: vis,
4797                           span: mk_sp(lo, self.last_span.hi) }
4798     }
4799
4800     // Parses a sequence of items. Stops when it finds program
4801     // text that can't be parsed as an item
4802     // - mod_items uses extern_mod_allowed = true
4803     // - block_tail_ uses extern_mod_allowed = false
4804     fn parse_items_and_view_items(&self,
4805                                   first_item_attrs: ~[Attribute],
4806                                   mut extern_mod_allowed: bool,
4807                                   macros_allowed: bool)
4808                                   -> ParsedItemsAndViewItems {
4809         let mut attrs = vec::append(first_item_attrs,
4810                                     self.parse_outer_attributes());
4811         // First, parse view items.
4812         let mut view_items : ~[ast::view_item] = ~[];
4813         let mut items = ~[];
4814
4815         // I think this code would probably read better as a single
4816         // loop with a mutable three-state-variable (for extern mods,
4817         // view items, and regular items) ... except that because
4818         // of macros, I'd like to delay that entire check until later.
4819         loop {
4820             match self.parse_item_or_view_item(attrs, macros_allowed) {
4821                 iovi_none(attrs) => {
4822                     return ParsedItemsAndViewItems {
4823                         attrs_remaining: attrs,
4824                         view_items: view_items,
4825                         items: items,
4826                         foreign_items: ~[]
4827                     }
4828                 }
4829                 iovi_view_item(view_item) => {
4830                     match view_item.node {
4831                         view_item_use(*) => {
4832                             // `extern mod` must precede `use`.
4833                             extern_mod_allowed = false;
4834                         }
4835                         view_item_extern_mod(*)
4836                         if !extern_mod_allowed => {
4837                             self.span_err(view_item.span,
4838                                           "\"extern mod\" declarations are not allowed here");
4839                         }
4840                         view_item_extern_mod(*) => {}
4841                     }
4842                     view_items.push(view_item);
4843                 }
4844                 iovi_item(item) => {
4845                     items.push(item);
4846                     attrs = self.parse_outer_attributes();
4847                     break;
4848                 }
4849                 iovi_foreign_item(_) => {
4850                     fail!();
4851                 }
4852             }
4853             attrs = self.parse_outer_attributes();
4854         }
4855
4856         // Next, parse items.
4857         loop {
4858             match self.parse_item_or_view_item(attrs, macros_allowed) {
4859                 iovi_none(returned_attrs) => {
4860                     attrs = returned_attrs;
4861                     break
4862                 }
4863                 iovi_view_item(view_item) => {
4864                     attrs = self.parse_outer_attributes();
4865                     self.span_err(view_item.span,
4866                                   "`use` and `extern mod` declarations must precede items");
4867                 }
4868                 iovi_item(item) => {
4869                     attrs = self.parse_outer_attributes();
4870                     items.push(item)
4871                 }
4872                 iovi_foreign_item(_) => {
4873                     fail!();
4874                 }
4875             }
4876         }
4877
4878         ParsedItemsAndViewItems {
4879             attrs_remaining: attrs,
4880             view_items: view_items,
4881             items: items,
4882             foreign_items: ~[]
4883         }
4884     }
4885
4886     // Parses a sequence of foreign items. Stops when it finds program
4887     // text that can't be parsed as an item
4888     fn parse_foreign_items(&self, first_item_attrs: ~[Attribute],
4889                            macros_allowed: bool)
4890         -> ParsedItemsAndViewItems {
4891         let mut attrs = vec::append(first_item_attrs,
4892                                     self.parse_outer_attributes());
4893         let mut foreign_items = ~[];
4894         loop {
4895             match self.parse_foreign_item(attrs, macros_allowed) {
4896                 iovi_none(returned_attrs) => {
4897                     if *self.token == token::RBRACE {
4898                         attrs = returned_attrs;
4899                         break
4900                     }
4901                     self.unexpected();
4902                 },
4903                 iovi_view_item(view_item) => {
4904                     // I think this can't occur:
4905                     self.span_err(view_item.span,
4906                                   "`use` and `extern mod` declarations must precede items");
4907                 }
4908                 iovi_item(item) => {
4909                     // FIXME #5668: this will occur for a macro invocation:
4910                     self.span_fatal(item.span, "macros cannot expand to foreign items");
4911                 }
4912                 iovi_foreign_item(foreign_item) => {
4913                     foreign_items.push(foreign_item);
4914                 }
4915             }
4916             attrs = self.parse_outer_attributes();
4917         }
4918
4919         ParsedItemsAndViewItems {
4920             attrs_remaining: attrs,
4921             view_items: ~[],
4922             items: ~[],
4923             foreign_items: foreign_items
4924         }
4925     }
4926
4927     // Parses a source module as a crate. This is the main
4928     // entry point for the parser.
4929     pub fn parse_crate_mod(&self) -> Crate {
4930         let lo = self.span.lo;
4931         // parse the crate's inner attrs, maybe (oops) one
4932         // of the attrs of an item:
4933         let (inner, next) = self.parse_inner_attrs_and_next();
4934         let first_item_outer_attrs = next;
4935         // parse the items inside the crate:
4936         let m = self.parse_mod_items(token::EOF, first_item_outer_attrs);
4937
4938         ast::Crate {
4939             module: m,
4940             attrs: inner,
4941             config: self.cfg.clone(),
4942             span: mk_sp(lo, self.span.lo)
4943         }
4944     }
4945
4946     pub fn parse_optional_str(&self) -> Option<(@str, ast::StrStyle)> {
4947         let (s, style) = match *self.token {
4948             token::LIT_STR(s) => (s, ast::CookedStr),
4949             token::LIT_STR_RAW(s, n) => (s, ast::RawStr(n)),
4950             _ => return None
4951         };
4952         self.bump();
4953         Some((ident_to_str(&s), style))
4954     }
4955
4956     pub fn parse_str(&self) -> (@str, StrStyle) {
4957         match self.parse_optional_str() {
4958             Some(s) => { s }
4959             _ =>  self.fatal("expected string literal")
4960         }
4961     }
4962 }