src/librustc_expand/mbe/macro_rules.rs

   1 use crate::base::{DummyResult, ExtCtxt, MacResult, TTMacroExpander};
   2 use crate::base::{SyntaxExtension, SyntaxExtensionKind};
   3 use crate::expand::{ensure_complete_parse, parse_ast_fragment, AstFragment, AstFragmentKind};
   4 use crate::mbe;
   5 use crate::mbe::macro_check;
   6 use crate::mbe::macro_parser::parse;
   7 use crate::mbe::macro_parser::{Error, Failure, Success};
   8 use crate::mbe::macro_parser::{MatchedNonterminal, MatchedSeq, NamedParseResult};
   9 use crate::mbe::transcribe::transcribe;
  10
  11 use rustc_feature::Features;
  12 use rustc_parse::parser::Parser;
  13 use rustc_parse::Directory;
  14 use rustc_span::edition::Edition;
  15 use rustc_span::hygiene::Transparency;
  16 use rustc_span::symbol::{kw, sym, Symbol};
  17 use rustc_span::Span;
  18 use syntax::ast;
  19 use syntax::attr::{self, TransparencyError};
  20 use syntax::print::pprust;
  21 use syntax::sess::ParseSess;
  22 use syntax::token::{self, NtTT, Token, TokenKind::*};
  23 use syntax::tokenstream::{DelimSpan, TokenStream};
  24
  25 use errors::{DiagnosticBuilder, FatalError};
  26 use log::debug;
  27
  28 use rustc_data_structures::fx::FxHashMap;
  29 use rustc_data_structures::sync::Lrc;
  30 use std::borrow::Cow;
  31 use std::collections::hash_map::Entry;
  32 use std::{mem, slice};
  33
  34 use errors::Applicability;
  35
  36 const VALID_FRAGMENT_NAMES_MSG: &str = "valid fragment specifiers are \
  37                                         `ident`, `block`, `stmt`, `expr`, `pat`, `ty`, `lifetime`, \
  38                                         `literal`, `path`, `meta`, `tt`, `item` and `vis`";
  39
  40 crate struct ParserAnyMacro<'a> {
  41     parser: Parser<'a>,
  42
  43     /// Span of the expansion site of the macro this parser is for
  44     site_span: Span,
  45     /// The ident of the macro we're parsing
  46     macro_ident: ast::Ident,
  47     arm_span: Span,
  48 }
  49
  50 crate fn annotate_err_with_kind(
  51     err: &mut DiagnosticBuilder<'_>,
  52     kind: AstFragmentKind,
  53     span: Span,
  54 ) {
  55     match kind {
  56         AstFragmentKind::Ty => {
  57             err.span_label(span, "this macro call doesn't expand to a type");
  58         }
  59         AstFragmentKind::Pat => {
  60             err.span_label(span, "this macro call doesn't expand to a pattern");
  61         }
  62         _ => {}
  63     };
  64 }
  65
  66 /// Instead of e.g. `vec![a, b, c]` in a pattern context, suggest `[a, b, c]`.
  67 fn suggest_slice_pat(e: &mut DiagnosticBuilder<'_>, site_span: Span, parser: &Parser<'_>) {
  68     let mut suggestion = None;
  69     if let Ok(code) = parser.sess.source_map().span_to_snippet(site_span) {
  70         if let Some(bang) = code.find('!') {
  71             suggestion = Some(code[bang + 1..].to_string());
  72         }
  73     }
  74     if let Some(suggestion) = suggestion {
  75         e.span_suggestion(
  76             site_span,
  77             "use a slice pattern here instead",
  78             suggestion,
  79             Applicability::MachineApplicable,
  80         );
  81     } else {
  82         e.span_label(site_span, "use a slice pattern here instead");
  83     }
  84     e.help(
  85         "for more information, see https://doc.rust-lang.org/edition-guide/\
  86         rust-2018/slice-patterns.html",
  87     );
  88 }
  89
  90 impl<'a> ParserAnyMacro<'a> {
  91     crate fn make(mut self: Box<ParserAnyMacro<'a>>, kind: AstFragmentKind) -> AstFragment {
  92         let ParserAnyMacro { site_span, macro_ident, ref mut parser, arm_span } = *self;
  93         let fragment = panictry!(parse_ast_fragment(parser, kind, true).map_err(|mut e| {
  94             if parser.token == token::Eof && e.message().ends_with(", found `<eof>`") {
  95                 if !e.span.is_dummy() {
  96                     // early end of macro arm (#52866)
  97                     e.replace_span_with(parser.sess.source_map().next_point(parser.token.span));
  98                 }
  99                 let msg = &e.message[0];
 100                 e.message[0] = (
 101                     format!(
 102                         "macro expansion ends with an incomplete expression: {}",
 103                         msg.0.replace(", found `<eof>`", ""),
 104                     ),
 105                     msg.1,
 106                 );
 107             }
 108             if e.span.is_dummy() {
 109                 // Get around lack of span in error (#30128)
 110                 e.replace_span_with(site_span);
 111                 if parser.sess.source_map().span_to_filename(arm_span).is_real() {
 112                     e.span_label(arm_span, "in this macro arm");
 113                 }
 114             } else if !parser.sess.source_map().span_to_filename(parser.token.span).is_real() {
 115                 e.span_label(site_span, "in this macro invocation");
 116             }
 117             match kind {
 118                 AstFragmentKind::Pat if macro_ident.name == sym::vec => {
 119                     suggest_slice_pat(&mut e, site_span, parser);
 120                 }
 121                 _ => annotate_err_with_kind(&mut e, kind, site_span),
 122             };
 123             e
 124         }));
 125
 126         // We allow semicolons at the end of expressions -- e.g., the semicolon in
 127         // `macro_rules! m { () => { panic!(); } }` isn't parsed by `.parse_expr()`,
 128         // but `m!()` is allowed in expression positions (cf. issue #34706).
 129         if kind == AstFragmentKind::Expr && parser.token == token::Semi {
 130             parser.bump();
 131         }
 132
 133         // Make sure we don't have any tokens left to parse so we don't silently drop anything.
 134         let path = ast::Path::from_ident(macro_ident.with_span_pos(site_span));
 135         ensure_complete_parse(parser, &path, kind.name(), site_span);
 136         fragment
 137     }
 138 }
 139
 140 struct MacroRulesMacroExpander {
 141     name: ast::Ident,
 142     span: Span,
 143     transparency: Transparency,
 144     lhses: Vec<mbe::TokenTree>,
 145     rhses: Vec<mbe::TokenTree>,
 146     valid: bool,
 147 }
 148
 149 impl TTMacroExpander for MacroRulesMacroExpander {
 150     fn expand<'cx>(
 151         &self,
 152         cx: &'cx mut ExtCtxt<'_>,
 153         sp: Span,
 154         input: TokenStream,
 155     ) -> Box<dyn MacResult + 'cx> {
 156         if !self.valid {
 157             return DummyResult::any(sp);
 158         }
 159         generic_extension(
 160             cx,
 161             sp,
 162             self.span,
 163             self.name,
 164             self.transparency,
 165             input,
 166             &self.lhses,
 167             &self.rhses,
 168         )
 169     }
 170 }
 171
 172 fn trace_macros_note(cx: &mut ExtCtxt<'_>, sp: Span, message: String) {
 173     let sp = sp.macro_backtrace().last().map(|trace| trace.call_site).unwrap_or(sp);
 174     cx.expansions.entry(sp).or_default().push(message);
 175 }
 176
 177 /// Given `lhses` and `rhses`, this is the new macro we create
 178 fn generic_extension<'cx>(
 179     cx: &'cx mut ExtCtxt<'_>,
 180     sp: Span,
 181     def_span: Span,
 182     name: ast::Ident,
 183     transparency: Transparency,
 184     arg: TokenStream,
 185     lhses: &[mbe::TokenTree],
 186     rhses: &[mbe::TokenTree],
 187 ) -> Box<dyn MacResult + 'cx> {
 188     if cx.trace_macros() {
 189         let msg = format!("expanding `{}! {{ {} }}`", name, pprust::tts_to_string(arg.clone()));
 190         trace_macros_note(cx, sp, msg);
 191     }
 192
 193     // Which arm's failure should we report? (the one furthest along)
 194     let mut best_failure: Option<(Token, &str)> = None;
 195     for (i, lhs) in lhses.iter().enumerate() {
 196         // try each arm's matchers
 197         let lhs_tt = match *lhs {
 198             mbe::TokenTree::Delimited(_, ref delim) => &delim.tts[..],
 199             _ => cx.span_bug(sp, "malformed macro lhs"),
 200         };
 201
 202         // Take a snapshot of the state of pre-expansion gating at this point.
 203         // This is used so that if a matcher is not `Success(..)`ful,
 204         // then the spans which became gated when parsing the unsuccessful matcher
 205         // are not recorded. On the first `Success(..)`ful matcher, the spans are merged.
 206         let mut gated_spans_snaphot = mem::take(&mut *cx.parse_sess.gated_spans.spans.borrow_mut());
 207
 208         match parse_tt(cx, lhs_tt, arg.clone()) {
 209             Success(named_matches) => {
 210                 // The matcher was `Success(..)`ful.
 211                 // Merge the gated spans from parsing the matcher with the pre-existing ones.
 212                 cx.parse_sess.gated_spans.merge(gated_spans_snaphot);
 213
 214                 let rhs = match rhses[i] {
 215                     // ignore delimiters
 216                     mbe::TokenTree::Delimited(_, ref delimed) => delimed.tts.clone(),
 217                     _ => cx.span_bug(sp, "malformed macro rhs"),
 218                 };
 219                 let arm_span = rhses[i].span();
 220
 221                 let rhs_spans = rhs.iter().map(|t| t.span()).collect::<Vec<_>>();
 222                 // rhs has holes ( `$id` and `$(...)` that need filled)
 223                 let mut tts = transcribe(cx, &named_matches, rhs, transparency);
 224
 225                 // Replace all the tokens for the corresponding positions in the macro, to maintain
 226                 // proper positions in error reporting, while maintaining the macro_backtrace.
 227                 if rhs_spans.len() == tts.len() {
 228                     tts = tts.map_enumerated(|i, mut tt| {
 229                         let mut sp = rhs_spans[i];
 230                         sp = sp.with_ctxt(tt.span().ctxt());
 231                         tt.set_span(sp);
 232                         tt
 233                     });
 234                 }
 235
 236                 if cx.trace_macros() {
 237                     let msg = format!("to `{}`", pprust::tts_to_string(tts.clone()));
 238                     trace_macros_note(cx, sp, msg);
 239                 }
 240
 241                 let directory = Directory {
 242                     path: Cow::from(cx.current_expansion.module.directory.as_path()),
 243                     ownership: cx.current_expansion.directory_ownership,
 244                 };
 245                 let mut p = Parser::new(cx.parse_sess(), tts, Some(directory), true, false, None);
 246                 p.root_module_name =
 247                     cx.current_expansion.module.mod_path.last().map(|id| id.to_string());
 248                 p.last_type_ascription = cx.current_expansion.prior_type_ascription;
 249
 250                 p.process_potential_macro_variable();
 251                 // Let the context choose how to interpret the result.
 252                 // Weird, but useful for X-macros.
 253                 return Box::new(ParserAnyMacro {
 254                     parser: p,
 255
 256                     // Pass along the original expansion site and the name of the macro
 257                     // so we can print a useful error message if the parse of the expanded
 258                     // macro leaves unparsed tokens.
 259                     site_span: sp,
 260                     macro_ident: name,
 261                     arm_span,
 262                 });
 263             }
 264             Failure(token, msg) => match best_failure {
 265                 Some((ref best_token, _)) if best_token.span.lo() >= token.span.lo() => {}
 266                 _ => best_failure = Some((token, msg)),
 267             },
 268             Error(err_sp, ref msg) => cx.span_fatal(err_sp.substitute_dummy(sp), &msg[..]),
 269         }
 270
 271         // The matcher was not `Success(..)`ful.
 272         // Restore to the state before snapshotting and maybe try again.
 273         mem::swap(&mut gated_spans_snaphot, &mut cx.parse_sess.gated_spans.spans.borrow_mut());
 274     }
 275
 276     let (token, label) = best_failure.expect("ran no matchers");
 277     let span = token.span.substitute_dummy(sp);
 278     let mut err = cx.struct_span_err(span, &parse_failure_msg(&token));
 279     err.span_label(span, label);
 280     if !def_span.is_dummy() && cx.source_map().span_to_filename(def_span).is_real() {
 281         err.span_label(cx.source_map().def_span(def_span), "when calling this macro");
 282     }
 283
 284     // Check whether there's a missing comma in this macro call, like `println!("{}" a);`
 285     if let Some((arg, comma_span)) = arg.add_comma() {
 286         for lhs in lhses {
 287             // try each arm's matchers
 288             let lhs_tt = match *lhs {
 289                 mbe::TokenTree::Delimited(_, ref delim) => &delim.tts[..],
 290                 _ => continue,
 291             };
 292             match parse_tt(cx, lhs_tt, arg.clone()) {
 293                 Success(_) => {
 294                     if comma_span.is_dummy() {
 295                         err.note("you might be missing a comma");
 296                     } else {
 297                         err.span_suggestion_short(
 298                             comma_span,
 299                             "missing comma here",
 300                             ", ".to_string(),
 301                             Applicability::MachineApplicable,
 302                         );
 303                     }
 304                 }
 305                 _ => {}
 306             }
 307         }
 308     }
 309     err.emit();
 310     cx.trace_macros_diag();
 311     DummyResult::any(sp)
 312 }
 313
 314 // Note that macro-by-example's input is also matched against a token tree:
 315 //                   $( $lhs:tt => $rhs:tt );+
 316 //
 317 // Holy self-referential!
 318
 319 /// Converts a macro item into a syntax extension.
 320 pub fn compile_declarative_macro(
 321     sess: &ParseSess,
 322     features: &Features,
 323     def: &ast::Item,
 324     edition: Edition,
 325 ) -> SyntaxExtension {
 326     let diag = &sess.span_diagnostic;
 327     let lhs_nm = ast::Ident::new(sym::lhs, def.span);
 328     let rhs_nm = ast::Ident::new(sym::rhs, def.span);
 329     let tt_spec = ast::Ident::new(sym::tt, def.span);
 330
 331     // Parse the macro_rules! invocation
 332     let (is_legacy, body) = match &def.kind {
 333         ast::ItemKind::MacroDef(macro_def) => (macro_def.legacy, macro_def.body.inner_tokens()),
 334         _ => unreachable!(),
 335     };
 336
 337     // The pattern that macro_rules matches.
 338     // The grammar for macro_rules! is:
 339     // $( $lhs:tt => $rhs:tt );+
 340     // ...quasiquoting this would be nice.
 341     // These spans won't matter, anyways
 342     let argument_gram = vec![
 343         mbe::TokenTree::Sequence(
 344             DelimSpan::dummy(),
 345             Lrc::new(mbe::SequenceRepetition {
 346                 tts: vec![
 347                     mbe::TokenTree::MetaVarDecl(def.span, lhs_nm, tt_spec),
 348                     mbe::TokenTree::token(token::FatArrow, def.span),
 349                     mbe::TokenTree::MetaVarDecl(def.span, rhs_nm, tt_spec),
 350                 ],
 351                 separator: Some(Token::new(
 352                     if is_legacy { token::Semi } else { token::Comma },
 353                     def.span,
 354                 )),
 355                 kleene: mbe::KleeneToken::new(mbe::KleeneOp::OneOrMore, def.span),
 356                 num_captures: 2,
 357             }),
 358         ),
 359         // to phase into semicolon-termination instead of semicolon-separation
 360         mbe::TokenTree::Sequence(
 361             DelimSpan::dummy(),
 362             Lrc::new(mbe::SequenceRepetition {
 363                 tts: vec![mbe::TokenTree::token(
 364                     if is_legacy { token::Semi } else { token::Comma },
 365                     def.span,
 366                 )],
 367                 separator: None,
 368                 kleene: mbe::KleeneToken::new(mbe::KleeneOp::ZeroOrMore, def.span),
 369                 num_captures: 0,
 370             }),
 371         ),
 372     ];
 373
 374     let argument_map = match parse(sess, body, &argument_gram, None, true) {
 375         Success(m) => m,
 376         Failure(token, msg) => {
 377             let s = parse_failure_msg(&token);
 378             let sp = token.span.substitute_dummy(def.span);
 379             let mut err = sess.span_diagnostic.struct_span_fatal(sp, &s);
 380             err.span_label(sp, msg);
 381             err.emit();
 382             FatalError.raise();
 383         }
 384         Error(sp, s) => {
 385             sess.span_diagnostic.span_fatal(sp.substitute_dummy(def.span), &s).raise();
 386         }
 387     };
 388
 389     let mut valid = true;
 390
 391     // Extract the arguments:
 392     let lhses = match argument_map[&lhs_nm] {
 393         MatchedSeq(ref s) => s
 394             .iter()
 395             .map(|m| {
 396                 if let MatchedNonterminal(ref nt) = *m {
 397                     if let NtTT(ref tt) = **nt {
 398                         let tt = mbe::quoted::parse(tt.clone().into(), true, sess).pop().unwrap();
 399                         valid &= check_lhs_nt_follows(sess, features, &def.attrs, &tt);
 400                         return tt;
 401                     }
 402                 }
 403                 sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 404             })
 405             .collect::<Vec<mbe::TokenTree>>(),
 406         _ => sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs"),
 407     };
 408
 409     let rhses = match argument_map[&rhs_nm] {
 410         MatchedSeq(ref s) => s
 411             .iter()
 412             .map(|m| {
 413                 if let MatchedNonterminal(ref nt) = *m {
 414                     if let NtTT(ref tt) = **nt {
 415                         return mbe::quoted::parse(tt.clone().into(), false, sess).pop().unwrap();
 416                     }
 417                 }
 418                 sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 419             })
 420             .collect::<Vec<mbe::TokenTree>>(),
 421         _ => sess.span_diagnostic.span_bug(def.span, "wrong-structured rhs"),
 422     };
 423
 424     for rhs in &rhses {
 425         valid &= check_rhs(sess, rhs);
 426     }
 427
 428     // don't abort iteration early, so that errors for multiple lhses can be reported
 429     for lhs in &lhses {
 430         valid &= check_lhs_no_empty_seq(sess, slice::from_ref(lhs));
 431     }
 432
 433     // We use CRATE_NODE_ID instead of `def.id` otherwise we may emit buffered lints for a node id
 434     // that is not lint-checked and trigger the "failed to process buffered lint here" bug.
 435     valid &= macro_check::check_meta_variables(sess, ast::CRATE_NODE_ID, def.span, &lhses, &rhses);
 436
 437     let (transparency, transparency_error) = attr::find_transparency(&def.attrs, is_legacy);
 438     match transparency_error {
 439         Some(TransparencyError::UnknownTransparency(value, span)) => {
 440             diag.span_err(span, &format!("unknown macro transparency: `{}`", value))
 441         }
 442         Some(TransparencyError::MultipleTransparencyAttrs(old_span, new_span)) => {
 443             diag.span_err(vec![old_span, new_span], "multiple macro transparency attributes")
 444         }
 445         None => {}
 446     }
 447
 448     let expander: Box<_> = Box::new(MacroRulesMacroExpander {
 449         name: def.ident,
 450         span: def.span,
 451         transparency,
 452         lhses,
 453         rhses,
 454         valid,
 455     });
 456
 457     SyntaxExtension::new(
 458         sess,
 459         SyntaxExtensionKind::LegacyBang(expander),
 460         def.span,
 461         Vec::new(),
 462         edition,
 463         def.ident.name,
 464         &def.attrs,
 465     )
 466 }
 467
 468 fn check_lhs_nt_follows(
 469     sess: &ParseSess,
 470     features: &Features,
 471     attrs: &[ast::Attribute],
 472     lhs: &mbe::TokenTree,
 473 ) -> bool {
 474     // lhs is going to be like TokenTree::Delimited(...), where the
 475     // entire lhs is those tts. Or, it can be a "bare sequence", not wrapped in parens.
 476     if let mbe::TokenTree::Delimited(_, ref tts) = *lhs {
 477         check_matcher(sess, features, attrs, &tts.tts)
 478     } else {
 479         let msg = "invalid macro matcher; matchers must be contained in balanced delimiters";
 480         sess.span_diagnostic.span_err(lhs.span(), msg);
 481         false
 482     }
 483     // we don't abort on errors on rejection, the driver will do that for us
 484     // after parsing/expansion. we can report every error in every macro this way.
 485 }
 486
 487 /// Checks that the lhs contains no repetition which could match an empty token
 488 /// tree, because then the matcher would hang indefinitely.
 489 fn check_lhs_no_empty_seq(sess: &ParseSess, tts: &[mbe::TokenTree]) -> bool {
 490     use mbe::TokenTree;
 491     for tt in tts {
 492         match *tt {
 493             TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => (),
 494             TokenTree::Delimited(_, ref del) => {
 495                 if !check_lhs_no_empty_seq(sess, &del.tts) {
 496                     return false;
 497                 }
 498             }
 499             TokenTree::Sequence(span, ref seq) => {
 500                 if seq.separator.is_none()
 501                     && seq.tts.iter().all(|seq_tt| match *seq_tt {
 502                         TokenTree::MetaVarDecl(_, _, id) => id.name == sym::vis,
 503                         TokenTree::Sequence(_, ref sub_seq) => {
 504                             sub_seq.kleene.op == mbe::KleeneOp::ZeroOrMore
 505                                 || sub_seq.kleene.op == mbe::KleeneOp::ZeroOrOne
 506                         }
 507                         _ => false,
 508                     })
 509                 {
 510                     let sp = span.entire();
 511                     sess.span_diagnostic.span_err(sp, "repetition matches empty token tree");
 512                     return false;
 513                 }
 514                 if !check_lhs_no_empty_seq(sess, &seq.tts) {
 515                     return false;
 516                 }
 517             }
 518         }
 519     }
 520
 521     true
 522 }
 523
 524 fn check_rhs(sess: &ParseSess, rhs: &mbe::TokenTree) -> bool {
 525     match *rhs {
 526         mbe::TokenTree::Delimited(..) => return true,
 527         _ => sess.span_diagnostic.span_err(rhs.span(), "macro rhs must be delimited"),
 528     }
 529     false
 530 }
 531
 532 fn check_matcher(
 533     sess: &ParseSess,
 534     features: &Features,
 535     attrs: &[ast::Attribute],
 536     matcher: &[mbe::TokenTree],
 537 ) -> bool {
 538     let first_sets = FirstSets::new(matcher);
 539     let empty_suffix = TokenSet::empty();
 540     let err = sess.span_diagnostic.err_count();
 541     check_matcher_core(sess, features, attrs, &first_sets, matcher, &empty_suffix);
 542     err == sess.span_diagnostic.err_count()
 543 }
 544
 545 // `The FirstSets` for a matcher is a mapping from subsequences in the
 546 // matcher to the FIRST set for that subsequence.
 547 //
 548 // This mapping is partially precomputed via a backwards scan over the
 549 // token trees of the matcher, which provides a mapping from each
 550 // repetition sequence to its *first* set.
 551 //
 552 // (Hypothetically, sequences should be uniquely identifiable via their
 553 // spans, though perhaps that is false, e.g., for macro-generated macros
 554 // that do not try to inject artificial span information. My plan is
 555 // to try to catch such cases ahead of time and not include them in
 556 // the precomputed mapping.)
 557 struct FirstSets {
 558     // this maps each TokenTree::Sequence `$(tt ...) SEP OP` that is uniquely identified by its
 559     // span in the original matcher to the First set for the inner sequence `tt ...`.
 560     //
 561     // If two sequences have the same span in a matcher, then map that
 562     // span to None (invalidating the mapping here and forcing the code to
 563     // use a slow path).
 564     first: FxHashMap<Span, Option<TokenSet>>,
 565 }
 566
 567 impl FirstSets {
 568     fn new(tts: &[mbe::TokenTree]) -> FirstSets {
 569         use mbe::TokenTree;
 570
 571         let mut sets = FirstSets { first: FxHashMap::default() };
 572         build_recur(&mut sets, tts);
 573         return sets;
 574
 575         // walks backward over `tts`, returning the FIRST for `tts`
 576         // and updating `sets` at the same time for all sequence
 577         // substructure we find within `tts`.
 578         fn build_recur(sets: &mut FirstSets, tts: &[TokenTree]) -> TokenSet {
 579             let mut first = TokenSet::empty();
 580             for tt in tts.iter().rev() {
 581                 match *tt {
 582                     TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
 583                         first.replace_with(tt.clone());
 584                     }
 585                     TokenTree::Delimited(span, ref delimited) => {
 586                         build_recur(sets, &delimited.tts[..]);
 587                         first.replace_with(delimited.open_tt(span));
 588                     }
 589                     TokenTree::Sequence(sp, ref seq_rep) => {
 590                         let subfirst = build_recur(sets, &seq_rep.tts[..]);
 591
 592                         match sets.first.entry(sp.entire()) {
 593                             Entry::Vacant(vac) => {
 594                                 vac.insert(Some(subfirst.clone()));
 595                             }
 596                             Entry::Occupied(mut occ) => {
 597                                 // if there is already an entry, then a span must have collided.
 598                                 // This should not happen with typical macro_rules macros,
 599                                 // but syntax extensions need not maintain distinct spans,
 600                                 // so distinct syntax trees can be assigned the same span.
 601                                 // In such a case, the map cannot be trusted; so mark this
 602                                 // entry as unusable.
 603                                 occ.insert(None);
 604                             }
 605                         }
 606
 607                         // If the sequence contents can be empty, then the first
 608                         // token could be the separator token itself.
 609
 610                         if let (Some(sep), true) = (&seq_rep.separator, subfirst.maybe_empty) {
 611                             first.add_one_maybe(TokenTree::Token(sep.clone()));
 612                         }
 613
 614                         // Reverse scan: Sequence comes before `first`.
 615                         if subfirst.maybe_empty
 616                             || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrMore
 617                             || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrOne
 618                         {
 619                             // If sequence is potentially empty, then
 620                             // union them (preserving first emptiness).
 621                             first.add_all(&TokenSet { maybe_empty: true, ..subfirst });
 622                         } else {
 623                             // Otherwise, sequence guaranteed
 624                             // non-empty; replace first.
 625                             first = subfirst;
 626                         }
 627                     }
 628                 }
 629             }
 630
 631             first
 632         }
 633     }
 634
 635     // walks forward over `tts` until all potential FIRST tokens are
 636     // identified.
 637     fn first(&self, tts: &[mbe::TokenTree]) -> TokenSet {
 638         use mbe::TokenTree;
 639
 640         let mut first = TokenSet::empty();
 641         for tt in tts.iter() {
 642             assert!(first.maybe_empty);
 643             match *tt {
 644                 TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
 645                     first.add_one(tt.clone());
 646                     return first;
 647                 }
 648                 TokenTree::Delimited(span, ref delimited) => {
 649                     first.add_one(delimited.open_tt(span));
 650                     return first;
 651                 }
 652                 TokenTree::Sequence(sp, ref seq_rep) => {
 653                     let subfirst_owned;
 654                     let subfirst = match self.first.get(&sp.entire()) {
 655                         Some(&Some(ref subfirst)) => subfirst,
 656                         Some(&None) => {
 657                             subfirst_owned = self.first(&seq_rep.tts[..]);
 658                             &subfirst_owned
 659                         }
 660                         None => {
 661                             panic!("We missed a sequence during FirstSets construction");
 662                         }
 663                     };
 664
 665                     // If the sequence contents can be empty, then the first
 666                     // token could be the separator token itself.
 667                     if let (Some(sep), true) = (&seq_rep.separator, subfirst.maybe_empty) {
 668                         first.add_one_maybe(TokenTree::Token(sep.clone()));
 669                     }
 670
 671                     assert!(first.maybe_empty);
 672                     first.add_all(subfirst);
 673                     if subfirst.maybe_empty
 674                         || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrMore
 675                         || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrOne
 676                     {
 677                         // Continue scanning for more first
 678                         // tokens, but also make sure we
 679                         // restore empty-tracking state.
 680                         first.maybe_empty = true;
 681                         continue;
 682                     } else {
 683                         return first;
 684                     }
 685                 }
 686             }
 687         }
 688
 689         // we only exit the loop if `tts` was empty or if every
 690         // element of `tts` matches the empty sequence.
 691         assert!(first.maybe_empty);
 692         first
 693     }
 694 }
 695
 696 // A set of `mbe::TokenTree`s, which may include `TokenTree::Match`s
 697 // (for macro-by-example syntactic variables). It also carries the
 698 // `maybe_empty` flag; that is true if and only if the matcher can
 699 // match an empty token sequence.
 700 //
 701 // The First set is computed on submatchers like `$($a:expr b),* $(c)* d`,
 702 // which has corresponding FIRST = {$a:expr, c, d}.
 703 // Likewise, `$($a:expr b),* $(c)+ d` has FIRST = {$a:expr, c}.
 704 //
 705 // (Notably, we must allow for *-op to occur zero times.)
 706 #[derive(Clone, Debug)]
 707 struct TokenSet {
 708     tokens: Vec<mbe::TokenTree>,
 709     maybe_empty: bool,
 710 }
 711
 712 impl TokenSet {
 713     // Returns a set for the empty sequence.
 714     fn empty() -> Self {
 715         TokenSet { tokens: Vec::new(), maybe_empty: true }
 716     }
 717
 718     // Returns the set `{ tok }` for the single-token (and thus
 719     // non-empty) sequence [tok].
 720     fn singleton(tok: mbe::TokenTree) -> Self {
 721         TokenSet { tokens: vec![tok], maybe_empty: false }
 722     }
 723
 724     // Changes self to be the set `{ tok }`.
 725     // Since `tok` is always present, marks self as non-empty.
 726     fn replace_with(&mut self, tok: mbe::TokenTree) {
 727         self.tokens.clear();
 728         self.tokens.push(tok);
 729         self.maybe_empty = false;
 730     }
 731
 732     // Changes self to be the empty set `{}`; meant for use when
 733     // the particular token does not matter, but we want to
 734     // record that it occurs.
 735     fn replace_with_irrelevant(&mut self) {
 736         self.tokens.clear();
 737         self.maybe_empty = false;
 738     }
 739
 740     // Adds `tok` to the set for `self`, marking sequence as non-empy.
 741     fn add_one(&mut self, tok: mbe::TokenTree) {
 742         if !self.tokens.contains(&tok) {
 743             self.tokens.push(tok);
 744         }
 745         self.maybe_empty = false;
 746     }
 747
 748     // Adds `tok` to the set for `self`. (Leaves `maybe_empty` flag alone.)
 749     fn add_one_maybe(&mut self, tok: mbe::TokenTree) {
 750         if !self.tokens.contains(&tok) {
 751             self.tokens.push(tok);
 752         }
 753     }
 754
 755     // Adds all elements of `other` to this.
 756     //
 757     // (Since this is a set, we filter out duplicates.)
 758     //
 759     // If `other` is potentially empty, then preserves the previous
 760     // setting of the empty flag of `self`. If `other` is guaranteed
 761     // non-empty, then `self` is marked non-empty.
 762     fn add_all(&mut self, other: &Self) {
 763         for tok in &other.tokens {
 764             if !self.tokens.contains(tok) {
 765                 self.tokens.push(tok.clone());
 766             }
 767         }
 768         if !other.maybe_empty {
 769             self.maybe_empty = false;
 770         }
 771     }
 772 }
 773
 774 // Checks that `matcher` is internally consistent and that it
 775 // can legally be followed by a token `N`, for all `N` in `follow`.
 776 // (If `follow` is empty, then it imposes no constraint on
 777 // the `matcher`.)
 778 //
 779 // Returns the set of NT tokens that could possibly come last in
 780 // `matcher`. (If `matcher` matches the empty sequence, then
 781 // `maybe_empty` will be set to true.)
 782 //
 783 // Requires that `first_sets` is pre-computed for `matcher`;
 784 // see `FirstSets::new`.
 785 fn check_matcher_core(
 786     sess: &ParseSess,
 787     features: &Features,
 788     attrs: &[ast::Attribute],
 789     first_sets: &FirstSets,
 790     matcher: &[mbe::TokenTree],
 791     follow: &TokenSet,
 792 ) -> TokenSet {
 793     use mbe::TokenTree;
 794
 795     let mut last = TokenSet::empty();
 796
 797     // 2. For each token and suffix  [T, SUFFIX] in M:
 798     // ensure that T can be followed by SUFFIX, and if SUFFIX may be empty,
 799     // then ensure T can also be followed by any element of FOLLOW.
 800     'each_token: for i in 0..matcher.len() {
 801         let token = &matcher[i];
 802         let suffix = &matcher[i + 1..];
 803
 804         let build_suffix_first = || {
 805             let mut s = first_sets.first(suffix);
 806             if s.maybe_empty {
 807                 s.add_all(follow);
 808             }
 809             s
 810         };
 811
 812         // (we build `suffix_first` on demand below; you can tell
 813         // which cases are supposed to fall through by looking for the
 814         // initialization of this variable.)
 815         let suffix_first;
 816
 817         // First, update `last` so that it corresponds to the set
 818         // of NT tokens that might end the sequence `... token`.
 819         match *token {
 820             TokenTree::Token(..) | TokenTree::MetaVar(..) | TokenTree::MetaVarDecl(..) => {
 821                 let can_be_followed_by_any;
 822                 if let Err(bad_frag) = has_legal_fragment_specifier(sess, features, attrs, token) {
 823                     let msg = format!("invalid fragment specifier `{}`", bad_frag);
 824                     sess.span_diagnostic
 825                         .struct_span_err(token.span(), &msg)
 826                         .help(VALID_FRAGMENT_NAMES_MSG)
 827                         .emit();
 828                     // (This eliminates false positives and duplicates
 829                     // from error messages.)
 830                     can_be_followed_by_any = true;
 831                 } else {
 832                     can_be_followed_by_any = token_can_be_followed_by_any(token);
 833                 }
 834
 835                 if can_be_followed_by_any {
 836                     // don't need to track tokens that work with any,
 837                     last.replace_with_irrelevant();
 838                     // ... and don't need to check tokens that can be
 839                     // followed by anything against SUFFIX.
 840                     continue 'each_token;
 841                 } else {
 842                     last.replace_with(token.clone());
 843                     suffix_first = build_suffix_first();
 844                 }
 845             }
 846             TokenTree::Delimited(span, ref d) => {
 847                 let my_suffix = TokenSet::singleton(d.close_tt(span));
 848                 check_matcher_core(sess, features, attrs, first_sets, &d.tts, &my_suffix);
 849                 // don't track non NT tokens
 850                 last.replace_with_irrelevant();
 851
 852                 // also, we don't need to check delimited sequences
 853                 // against SUFFIX
 854                 continue 'each_token;
 855             }
 856             TokenTree::Sequence(_, ref seq_rep) => {
 857                 suffix_first = build_suffix_first();
 858                 // The trick here: when we check the interior, we want
 859                 // to include the separator (if any) as a potential
 860                 // (but not guaranteed) element of FOLLOW. So in that
 861                 // case, we make a temp copy of suffix and stuff
 862                 // delimiter in there.
 863                 //
 864                 // FIXME: Should I first scan suffix_first to see if
 865                 // delimiter is already in it before I go through the
 866                 // work of cloning it? But then again, this way I may
 867                 // get a "tighter" span?
 868                 let mut new;
 869                 let my_suffix = if let Some(sep) = &seq_rep.separator {
 870                     new = suffix_first.clone();
 871                     new.add_one_maybe(TokenTree::Token(sep.clone()));
 872                     &new
 873                 } else {
 874                     &suffix_first
 875                 };
 876
 877                 // At this point, `suffix_first` is built, and
 878                 // `my_suffix` is some TokenSet that we can use
 879                 // for checking the interior of `seq_rep`.
 880                 let next =
 881                     check_matcher_core(sess, features, attrs, first_sets, &seq_rep.tts, my_suffix);
 882                 if next.maybe_empty {
 883                     last.add_all(&next);
 884                 } else {
 885                     last = next;
 886                 }
 887
 888                 // the recursive call to check_matcher_core already ran the 'each_last
 889                 // check below, so we can just keep going forward here.
 890                 continue 'each_token;
 891             }
 892         }
 893
 894         // (`suffix_first` guaranteed initialized once reaching here.)
 895
 896         // Now `last` holds the complete set of NT tokens that could
 897         // end the sequence before SUFFIX. Check that every one works with `suffix`.
 898         'each_last: for token in &last.tokens {
 899             if let TokenTree::MetaVarDecl(_, name, frag_spec) = *token {
 900                 for next_token in &suffix_first.tokens {
 901                     match is_in_follow(next_token, frag_spec.name) {
 902                         IsInFollow::Invalid(msg, help) => {
 903                             sess.span_diagnostic
 904                                 .struct_span_err(next_token.span(), &msg)
 905                                 .help(help)
 906                                 .emit();
 907                             // don't bother reporting every source of
 908                             // conflict for a particular element of `last`.
 909                             continue 'each_last;
 910                         }
 911                         IsInFollow::Yes => {}
 912                         IsInFollow::No(possible) => {
 913                             let may_be = if last.tokens.len() == 1 && suffix_first.tokens.len() == 1
 914                             {
 915                                 "is"
 916                             } else {
 917                                 "may be"
 918                             };
 919
 920                             let sp = next_token.span();
 921                             let mut err = sess.span_diagnostic.struct_span_err(
 922                                 sp,
 923                                 &format!(
 924                                     "`${name}:{frag}` {may_be} followed by `{next}`, which \
 925                                      is not allowed for `{frag}` fragments",
 926                                     name = name,
 927                                     frag = frag_spec,
 928                                     next = quoted_tt_to_string(next_token),
 929                                     may_be = may_be
 930                                 ),
 931                             );
 932                             err.span_label(
 933                                 sp,
 934                                 format!("not allowed after `{}` fragments", frag_spec),
 935                             );
 936                             let msg = "allowed there are: ";
 937                             match possible {
 938                                 &[] => {}
 939                                 &[t] => {
 940                                     err.note(&format!(
 941                                         "only {} is allowed after `{}` fragments",
 942                                         t, frag_spec,
 943                                     ));
 944                                 }
 945                                 ts => {
 946                                     err.note(&format!(
 947                                         "{}{} or {}",
 948                                         msg,
 949                                         ts[..ts.len() - 1]
 950                                             .iter()
 951                                             .map(|s| *s)
 952                                             .collect::<Vec<_>>()
 953                                             .join(", "),
 954                                         ts[ts.len() - 1],
 955                                     ));
 956                                 }
 957                             }
 958                             err.emit();
 959                         }
 960                     }
 961                 }
 962             }
 963         }
 964     }
 965     last
 966 }
 967
 968 fn token_can_be_followed_by_any(tok: &mbe::TokenTree) -> bool {
 969     if let mbe::TokenTree::MetaVarDecl(_, _, frag_spec) = *tok {
 970         frag_can_be_followed_by_any(frag_spec.name)
 971     } else {
 972         // (Non NT's can always be followed by anthing in matchers.)
 973         true
 974     }
 975 }
 976
 977 /// Returns `true` if a fragment of type `frag` can be followed by any sort of
 978 /// token. We use this (among other things) as a useful approximation
 979 /// for when `frag` can be followed by a repetition like `$(...)*` or
 980 /// `$(...)+`. In general, these can be a bit tricky to reason about,
 981 /// so we adopt a conservative position that says that any fragment
 982 /// specifier which consumes at most one token tree can be followed by
 983 /// a fragment specifier (indeed, these fragments can be followed by
 984 /// ANYTHING without fear of future compatibility hazards).
 985 fn frag_can_be_followed_by_any(frag: Symbol) -> bool {
 986     match frag {
 987         sym::item     | // always terminated by `}` or `;`
 988         sym::block    | // exactly one token tree
 989         sym::ident    | // exactly one token tree
 990         sym::literal  | // exactly one token tree
 991         sym::meta     | // exactly one token tree
 992         sym::lifetime | // exactly one token tree
 993         sym::tt =>   // exactly one token tree
 994             true,
 995
 996         _ =>
 997             false,
 998     }
 999 }
1000
1001 enum IsInFollow {
1002     Yes,
1003     No(&'static [&'static str]),
1004     Invalid(String, &'static str),
1005 }
1006
1007 /// Returns `true` if `frag` can legally be followed by the token `tok`. For
1008 /// fragments that can consume an unbounded number of tokens, `tok`
1009 /// must be within a well-defined follow set. This is intended to
1010 /// guarantee future compatibility: for example, without this rule, if
1011 /// we expanded `expr` to include a new binary operator, we might
1012 /// break macros that were relying on that binary operator as a
1013 /// separator.
1014 // when changing this do not forget to update doc/book/macros.md!
1015 fn is_in_follow(tok: &mbe::TokenTree, frag: Symbol) -> IsInFollow {
1016     use mbe::TokenTree;
1017
1018     if let TokenTree::Token(Token { kind: token::CloseDelim(_), .. }) = *tok {
1019         // closing a token tree can never be matched by any fragment;
1020         // iow, we always require that `(` and `)` match, etc.
1021         IsInFollow::Yes
1022     } else {
1023         match frag {
1024             sym::item => {
1025                 // since items *must* be followed by either a `;` or a `}`, we can
1026                 // accept anything after them
1027                 IsInFollow::Yes
1028             }
1029             sym::block => {
1030                 // anything can follow block, the braces provide an easy boundary to
1031                 // maintain
1032                 IsInFollow::Yes
1033             }
1034             sym::stmt | sym::expr => {
1035                 const TOKENS: &[&str] = &["`=>`", "`,`", "`;`"];
1036                 match tok {
1037                     TokenTree::Token(token) => match token.kind {
1038                         FatArrow | Comma | Semi => IsInFollow::Yes,
1039                         _ => IsInFollow::No(TOKENS),
1040                     },
1041                     _ => IsInFollow::No(TOKENS),
1042                 }
1043             }
1044             sym::pat => {
1045                 const TOKENS: &[&str] = &["`=>`", "`,`", "`=`", "`|`", "`if`", "`in`"];
1046                 match tok {
1047                     TokenTree::Token(token) => match token.kind {
1048                         FatArrow | Comma | Eq | BinOp(token::Or) => IsInFollow::Yes,
1049                         Ident(name, false) if name == kw::If || name == kw::In => IsInFollow::Yes,
1050                         _ => IsInFollow::No(TOKENS),
1051                     },
1052                     _ => IsInFollow::No(TOKENS),
1053                 }
1054             }
1055             sym::path | sym::ty => {
1056                 const TOKENS: &[&str] = &[
1057                     "`{`", "`[`", "`=>`", "`,`", "`>`", "`=`", "`:`", "`;`", "`|`", "`as`",
1058                     "`where`",
1059                 ];
1060                 match tok {
1061                     TokenTree::Token(token) => match token.kind {
1062                         OpenDelim(token::DelimToken::Brace)
1063                         | OpenDelim(token::DelimToken::Bracket)
1064                         | Comma
1065                         | FatArrow
1066                         | Colon
1067                         | Eq
1068                         | Gt
1069                         | BinOp(token::Shr)
1070                         | Semi
1071                         | BinOp(token::Or) => IsInFollow::Yes,
1072                         Ident(name, false) if name == kw::As || name == kw::Where => {
1073                             IsInFollow::Yes
1074                         }
1075                         _ => IsInFollow::No(TOKENS),
1076                     },
1077                     TokenTree::MetaVarDecl(_, _, frag) if frag.name == sym::block => {
1078                         IsInFollow::Yes
1079                     }
1080                     _ => IsInFollow::No(TOKENS),
1081                 }
1082             }
1083             sym::ident | sym::lifetime => {
1084                 // being a single token, idents and lifetimes are harmless
1085                 IsInFollow::Yes
1086             }
1087             sym::literal => {
1088                 // literals may be of a single token, or two tokens (negative numbers)
1089                 IsInFollow::Yes
1090             }
1091             sym::meta | sym::tt => {
1092                 // being either a single token or a delimited sequence, tt is
1093                 // harmless
1094                 IsInFollow::Yes
1095             }
1096             sym::vis => {
1097                 // Explicitly disallow `priv`, on the off chance it comes back.
1098                 const TOKENS: &[&str] = &["`,`", "an ident", "a type"];
1099                 match tok {
1100                     TokenTree::Token(token) => match token.kind {
1101                         Comma => IsInFollow::Yes,
1102                         Ident(name, is_raw) if is_raw || name != kw::Priv => IsInFollow::Yes,
1103                         _ => {
1104                             if token.can_begin_type() {
1105                                 IsInFollow::Yes
1106                             } else {
1107                                 IsInFollow::No(TOKENS)
1108                             }
1109                         }
1110                     },
1111                     TokenTree::MetaVarDecl(_, _, frag)
1112                         if frag.name == sym::ident
1113                             || frag.name == sym::ty
1114                             || frag.name == sym::path =>
1115                     {
1116                         IsInFollow::Yes
1117                     }
1118                     _ => IsInFollow::No(TOKENS),
1119                 }
1120             }
1121             kw::Invalid => IsInFollow::Yes,
1122             _ => IsInFollow::Invalid(
1123                 format!("invalid fragment specifier `{}`", frag),
1124                 VALID_FRAGMENT_NAMES_MSG,
1125             ),
1126         }
1127     }
1128 }
1129
1130 fn has_legal_fragment_specifier(
1131     sess: &ParseSess,
1132     features: &Features,
1133     attrs: &[ast::Attribute],
1134     tok: &mbe::TokenTree,
1135 ) -> Result<(), String> {
1136     debug!("has_legal_fragment_specifier({:?})", tok);
1137     if let mbe::TokenTree::MetaVarDecl(_, _, ref frag_spec) = *tok {
1138         let frag_span = tok.span();
1139         if !is_legal_fragment_specifier(sess, features, attrs, frag_spec.name, frag_span) {
1140             return Err(frag_spec.to_string());
1141         }
1142     }
1143     Ok(())
1144 }
1145
1146 fn is_legal_fragment_specifier(
1147     _sess: &ParseSess,
1148     _features: &Features,
1149     _attrs: &[ast::Attribute],
1150     frag_name: Symbol,
1151     _frag_span: Span,
1152 ) -> bool {
1153     /*
1154      * If new fragment specifiers are invented in nightly, `_sess`,
1155      * `_features`, `_attrs`, and `_frag_span` will be useful here
1156      * for checking against feature gates. See past versions of
1157      * this function.
1158      */
1159     match frag_name {
1160         sym::item
1161         | sym::block
1162         | sym::stmt
1163         | sym::expr
1164         | sym::pat
1165         | sym::lifetime
1166         | sym::path
1167         | sym::ty
1168         | sym::ident
1169         | sym::meta
1170         | sym::tt
1171         | sym::vis
1172         | sym::literal
1173         | kw::Invalid => true,
1174         _ => false,
1175     }
1176 }
1177
1178 fn quoted_tt_to_string(tt: &mbe::TokenTree) -> String {
1179     match *tt {
1180         mbe::TokenTree::Token(ref token) => pprust::token_to_string(&token),
1181         mbe::TokenTree::MetaVar(_, name) => format!("${}", name),
1182         mbe::TokenTree::MetaVarDecl(_, name, kind) => format!("${}:{}", name, kind),
1183         _ => panic!(
1184             "unexpected mbe::TokenTree::{{Sequence or Delimited}} \
1185              in follow set checker"
1186         ),
1187     }
1188 }
1189
1190 /// Use this token tree as a matcher to parse given tts.
1191 fn parse_tt(cx: &ExtCtxt<'_>, mtch: &[mbe::TokenTree], tts: TokenStream) -> NamedParseResult {
1192     // `None` is because we're not interpolating
1193     let directory = Directory {
1194         path: Cow::from(cx.current_expansion.module.directory.as_path()),
1195         ownership: cx.current_expansion.directory_ownership,
1196     };
1197     parse(cx.parse_sess(), tts, mtch, Some(directory), true)
1198 }
1199
1200 /// Generates an appropriate parsing failure message. For EOF, this is "unexpected end...". For
1201 /// other tokens, this is "unexpected token...".
1202 fn parse_failure_msg(tok: &Token) -> String {
1203     match tok.kind {
1204         token::Eof => "unexpected end of macro invocation".to_string(),
1205         _ => format!("no rules expected the token `{}`", pprust::token_to_string(tok),),
1206     }
1207 }