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