src/libsyntax/parse/parser.rs

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