src/libsyntax/ext/tt/macro_rules.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use {ast, attr};
  12 use syntax_pos::{Span, DUMMY_SP};
  13 use ext::base::{DummyResult, ExtCtxt, MacResult, SyntaxExtension};
  14 use ext::base::{NormalTT, TTMacroExpander};
  15 use ext::expand::{Expansion, ExpansionKind};
  16 use ext::tt::macro_parser::{Success, Error, Failure};
  17 use ext::tt::macro_parser::{MatchedSeq, MatchedNonterminal};
  18 use ext::tt::macro_parser::{parse, parse_failure_msg};
  19 use ext::tt::quoted;
  20 use ext::tt::transcribe::transcribe;
  21 use parse::{Directory, ParseSess};
  22 use parse::parser::Parser;
  23 use parse::token::{self, NtTT};
  24 use parse::token::Token::*;
  25 use symbol::Symbol;
  26 use tokenstream::{TokenStream, TokenTree};
  27
  28 use std::collections::{HashMap};
  29 use std::collections::hash_map::{Entry};
  30 use std::rc::Rc;
  31
  32 pub struct ParserAnyMacro<'a> {
  33     parser: Parser<'a>,
  34
  35     /// Span of the expansion site of the macro this parser is for
  36     site_span: Span,
  37     /// The ident of the macro we're parsing
  38     macro_ident: ast::Ident
  39 }
  40
  41 impl<'a> ParserAnyMacro<'a> {
  42     pub fn make(mut self: Box<ParserAnyMacro<'a>>, kind: ExpansionKind) -> Expansion {
  43         let ParserAnyMacro { site_span, macro_ident, ref mut parser } = *self;
  44         let expansion = panictry!(parser.parse_expansion(kind, true));
  45
  46         // We allow semicolons at the end of expressions -- e.g. the semicolon in
  47         // `macro_rules! m { () => { panic!(); } }` isn't parsed by `.parse_expr()`,
  48         // but `m!()` is allowed in expression positions (c.f. issue #34706).
  49         if kind == ExpansionKind::Expr && parser.token == token::Semi {
  50             parser.bump();
  51         }
  52
  53         // Make sure we don't have any tokens left to parse so we don't silently drop anything.
  54         let path = ast::Path::from_ident(site_span, macro_ident);
  55         parser.ensure_complete_parse(&path, kind.name(), site_span);
  56         expansion
  57     }
  58 }
  59
  60 struct MacroRulesMacroExpander {
  61     name: ast::Ident,
  62     lhses: Vec<quoted::TokenTree>,
  63     rhses: Vec<quoted::TokenTree>,
  64     valid: bool,
  65 }
  66
  67 impl TTMacroExpander for MacroRulesMacroExpander {
  68     fn expand<'cx>(&self,
  69                    cx: &'cx mut ExtCtxt,
  70                    sp: Span,
  71                    input: TokenStream)
  72                    -> Box<MacResult+'cx> {
  73         if !self.valid {
  74             return DummyResult::any(sp);
  75         }
  76         generic_extension(cx,
  77                           sp,
  78                           self.name,
  79                           input,
  80                           &self.lhses,
  81                           &self.rhses)
  82     }
  83 }
  84
  85 /// Given `lhses` and `rhses`, this is the new macro we create
  86 fn generic_extension<'cx>(cx: &'cx ExtCtxt,
  87                           sp: Span,
  88                           name: ast::Ident,
  89                           arg: TokenStream,
  90                           lhses: &[quoted::TokenTree],
  91                           rhses: &[quoted::TokenTree])
  92                           -> Box<MacResult+'cx> {
  93     if cx.trace_macros() {
  94         println!("{}! {{ {} }}", name, arg);
  95     }
  96
  97     // Which arm's failure should we report? (the one furthest along)
  98     let mut best_fail_spot = DUMMY_SP;
  99     let mut best_fail_tok = None;
 100
 101     for (i, lhs) in lhses.iter().enumerate() { // try each arm's matchers
 102         let lhs_tt = match *lhs {
 103             quoted::TokenTree::Delimited(_, ref delim) => &delim.tts[..],
 104             _ => cx.span_bug(sp, "malformed macro lhs")
 105         };
 106
 107         match TokenTree::parse(cx, lhs_tt, arg.clone()) {
 108             Success(named_matches) => {
 109                 let rhs = match rhses[i] {
 110                     // ignore delimiters
 111                     quoted::TokenTree::Delimited(_, ref delimed) => delimed.tts.clone(),
 112                     _ => cx.span_bug(sp, "malformed macro rhs"),
 113                 };
 114                 // rhs has holes ( `$id` and `$(...)` that need filled)
 115                 let tts = transcribe(&cx.parse_sess.span_diagnostic, Some(named_matches), rhs);
 116                 let directory = Directory {
 117                     path: cx.current_expansion.module.directory.clone(),
 118                     ownership: cx.current_expansion.directory_ownership,
 119                 };
 120                 let mut p = Parser::new(cx.parse_sess(), tts, Some(directory), false);
 121                 p.root_module_name = cx.current_expansion.module.mod_path.last()
 122                     .map(|id| (*id.name.as_str()).to_owned());
 123
 124                 p.check_unknown_macro_variable();
 125                 // Let the context choose how to interpret the result.
 126                 // Weird, but useful for X-macros.
 127                 return Box::new(ParserAnyMacro {
 128                     parser: p,
 129
 130                     // Pass along the original expansion site and the name of the macro
 131                     // so we can print a useful error message if the parse of the expanded
 132                     // macro leaves unparsed tokens.
 133                     site_span: sp,
 134                     macro_ident: name
 135                 })
 136             }
 137             Failure(sp, tok) => if sp.lo >= best_fail_spot.lo {
 138                 best_fail_spot = sp;
 139                 best_fail_tok = Some(tok);
 140             },
 141             Error(err_sp, ref msg) => {
 142                 cx.span_fatal(err_sp.substitute_dummy(sp), &msg[..])
 143             }
 144         }
 145     }
 146
 147     let best_fail_msg = parse_failure_msg(best_fail_tok.expect("ran no matchers"));
 148     cx.span_fatal(best_fail_spot.substitute_dummy(sp), &best_fail_msg);
 149 }
 150
 151 // Note that macro-by-example's input is also matched against a token tree:
 152 //                   $( $lhs:tt => $rhs:tt );+
 153 //
 154 // Holy self-referential!
 155
 156 /// Converts a `macro_rules!` invocation into a syntax extension.
 157 pub fn compile(sess: &ParseSess, def: &ast::Item) -> SyntaxExtension {
 158     let lhs_nm = ast::Ident::with_empty_ctxt(Symbol::gensym("lhs"));
 159     let rhs_nm = ast::Ident::with_empty_ctxt(Symbol::gensym("rhs"));
 160
 161     // The pattern that macro_rules matches.
 162     // The grammar for macro_rules! is:
 163     // $( $lhs:tt => $rhs:tt );+
 164     // ...quasiquoting this would be nice.
 165     // These spans won't matter, anyways
 166     let argument_gram = vec![
 167         quoted::TokenTree::Sequence(DUMMY_SP, Rc::new(quoted::SequenceRepetition {
 168             tts: vec![
 169                 quoted::TokenTree::MetaVarDecl(DUMMY_SP, lhs_nm, ast::Ident::from_str("tt")),
 170                 quoted::TokenTree::Token(DUMMY_SP, token::FatArrow),
 171                 quoted::TokenTree::MetaVarDecl(DUMMY_SP, rhs_nm, ast::Ident::from_str("tt")),
 172             ],
 173             separator: Some(token::Semi),
 174             op: quoted::KleeneOp::OneOrMore,
 175             num_captures: 2,
 176         })),
 177         // to phase into semicolon-termination instead of semicolon-separation
 178         quoted::TokenTree::Sequence(DUMMY_SP, Rc::new(quoted::SequenceRepetition {
 179             tts: vec![quoted::TokenTree::Token(DUMMY_SP, token::Semi)],
 180             separator: None,
 181             op: quoted::KleeneOp::ZeroOrMore,
 182             num_captures: 0
 183         })),
 184     ];
 185
 186     // Parse the macro_rules! invocation
 187     let body = match def.node {
 188         ast::ItemKind::MacroDef(ref body) => body.clone().into(),
 189         _ => unreachable!(),
 190     };
 191     let argument_map = match parse(sess, body, &argument_gram, None) {
 192         Success(m) => m,
 193         Failure(sp, tok) => {
 194             let s = parse_failure_msg(tok);
 195             panic!(sess.span_diagnostic.span_fatal(sp.substitute_dummy(def.span), &s));
 196         }
 197         Error(sp, s) => {
 198             panic!(sess.span_diagnostic.span_fatal(sp.substitute_dummy(def.span), &s));
 199         }
 200     };
 201
 202     let mut valid = true;
 203
 204     // Extract the arguments:
 205     let lhses = match **argument_map.get(&lhs_nm).unwrap() {
 206         MatchedSeq(ref s, _) => {
 207             s.iter().map(|m| {
 208                 if let MatchedNonterminal(ref nt) = **m {
 209                     if let NtTT(ref tt) = **nt {
 210                         let tt = quoted::parse(tt.clone().into(), true, sess).pop().unwrap();
 211                         valid &= check_lhs_nt_follows(sess, &tt);
 212                         return tt;
 213                     }
 214                 }
 215                 sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 216             }).collect::<Vec<quoted::TokenTree>>()
 217         }
 218         _ => sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 219     };
 220
 221     let rhses = match **argument_map.get(&rhs_nm).unwrap() {
 222         MatchedSeq(ref s, _) => {
 223             s.iter().map(|m| {
 224                 if let MatchedNonterminal(ref nt) = **m {
 225                     if let NtTT(ref tt) = **nt {
 226                         return quoted::parse(tt.clone().into(), false, sess).pop().unwrap();
 227                     }
 228                 }
 229                 sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 230             }).collect::<Vec<quoted::TokenTree>>()
 231         }
 232         _ => sess.span_diagnostic.span_bug(def.span, "wrong-structured rhs")
 233     };
 234
 235     for rhs in &rhses {
 236         valid &= check_rhs(sess, rhs);
 237     }
 238
 239     // don't abort iteration early, so that errors for multiple lhses can be reported
 240     for lhs in &lhses {
 241         valid &= check_lhs_no_empty_seq(sess, &[lhs.clone()])
 242     }
 243
 244     let exp: Box<_> = Box::new(MacroRulesMacroExpander {
 245         name: def.ident,
 246         lhses: lhses,
 247         rhses: rhses,
 248         valid: valid,
 249     });
 250
 251     NormalTT(exp, Some(def.span), attr::contains_name(&def.attrs, "allow_internal_unstable"))
 252 }
 253
 254 fn check_lhs_nt_follows(sess: &ParseSess, lhs: &quoted::TokenTree) -> bool {
 255     // lhs is going to be like TokenTree::Delimited(...), where the
 256     // entire lhs is those tts. Or, it can be a "bare sequence", not wrapped in parens.
 257     match lhs {
 258         &quoted::TokenTree::Delimited(_, ref tts) => check_matcher(sess, &tts.tts),
 259         _ => {
 260             let msg = "invalid macro matcher; matchers must be contained in balanced delimiters";
 261             sess.span_diagnostic.span_err(lhs.span(), msg);
 262             false
 263         }
 264     }
 265     // we don't abort on errors on rejection, the driver will do that for us
 266     // after parsing/expansion. we can report every error in every macro this way.
 267 }
 268
 269 /// Check that the lhs contains no repetition which could match an empty token
 270 /// tree, because then the matcher would hang indefinitely.
 271 fn check_lhs_no_empty_seq(sess: &ParseSess, tts: &[quoted::TokenTree]) -> bool {
 272     use self::quoted::TokenTree;
 273     for tt in tts {
 274         match *tt {
 275             TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => (),
 276             TokenTree::Delimited(_, ref del) => if !check_lhs_no_empty_seq(sess, &del.tts) {
 277                 return false;
 278             },
 279             TokenTree::Sequence(span, ref seq) => {
 280                 if seq.separator.is_none() {
 281                     if seq.tts.iter().all(|seq_tt| {
 282                         match *seq_tt {
 283                             TokenTree::Sequence(_, ref sub_seq) =>
 284                                 sub_seq.op == quoted::KleeneOp::ZeroOrMore,
 285                             _ => false,
 286                         }
 287                     }) {
 288                         sess.span_diagnostic.span_err(span, "repetition matches empty token tree");
 289                         return false;
 290                     }
 291                 }
 292                 if !check_lhs_no_empty_seq(sess, &seq.tts) {
 293                     return false;
 294                 }
 295             }
 296         }
 297     }
 298
 299     true
 300 }
 301
 302 fn check_rhs(sess: &ParseSess, rhs: &quoted::TokenTree) -> bool {
 303     match *rhs {
 304         quoted::TokenTree::Delimited(..) => return true,
 305         _ => sess.span_diagnostic.span_err(rhs.span(), "macro rhs must be delimited")
 306     }
 307     false
 308 }
 309
 310 fn check_matcher(sess: &ParseSess, matcher: &[quoted::TokenTree]) -> bool {
 311     let first_sets = FirstSets::new(matcher);
 312     let empty_suffix = TokenSet::empty();
 313     let err = sess.span_diagnostic.err_count();
 314     check_matcher_core(sess, &first_sets, matcher, &empty_suffix);
 315     err == sess.span_diagnostic.err_count()
 316 }
 317
 318 // The FirstSets for a matcher is a mapping from subsequences in the
 319 // matcher to the FIRST set for that subsequence.
 320 //
 321 // This mapping is partially precomputed via a backwards scan over the
 322 // token trees of the matcher, which provides a mapping from each
 323 // repetition sequence to its FIRST set.
 324 //
 325 // (Hypothetically sequences should be uniquely identifiable via their
 326 // spans, though perhaps that is false e.g. for macro-generated macros
 327 // that do not try to inject artificial span information. My plan is
 328 // to try to catch such cases ahead of time and not include them in
 329 // the precomputed mapping.)
 330 struct FirstSets {
 331     // this maps each TokenTree::Sequence `$(tt ...) SEP OP` that is uniquely identified by its
 332     // span in the original matcher to the First set for the inner sequence `tt ...`.
 333     //
 334     // If two sequences have the same span in a matcher, then map that
 335     // span to None (invalidating the mapping here and forcing the code to
 336     // use a slow path).
 337     first: HashMap<Span, Option<TokenSet>>,
 338 }
 339
 340 impl FirstSets {
 341     fn new(tts: &[quoted::TokenTree]) -> FirstSets {
 342         use self::quoted::TokenTree;
 343
 344         let mut sets = FirstSets { first: HashMap::new() };
 345         build_recur(&mut sets, tts);
 346         return sets;
 347
 348         // walks backward over `tts`, returning the FIRST for `tts`
 349         // and updating `sets` at the same time for all sequence
 350         // substructure we find within `tts`.
 351         fn build_recur(sets: &mut FirstSets, tts: &[TokenTree]) -> TokenSet {
 352             let mut first = TokenSet::empty();
 353             for tt in tts.iter().rev() {
 354                 match *tt {
 355                     TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
 356                         first.replace_with(tt.clone());
 357                     }
 358                     TokenTree::Delimited(span, ref delimited) => {
 359                         build_recur(sets, &delimited.tts[..]);
 360                         first.replace_with(delimited.open_tt(span));
 361                     }
 362                     TokenTree::Sequence(sp, ref seq_rep) => {
 363                         let subfirst = build_recur(sets, &seq_rep.tts[..]);
 364
 365                         match sets.first.entry(sp) {
 366                             Entry::Vacant(vac) => {
 367                                 vac.insert(Some(subfirst.clone()));
 368                             }
 369                             Entry::Occupied(mut occ) => {
 370                                 // if there is already an entry, then a span must have collided.
 371                                 // This should not happen with typical macro_rules macros,
 372                                 // but syntax extensions need not maintain distinct spans,
 373                                 // so distinct syntax trees can be assigned the same span.
 374                                 // In such a case, the map cannot be trusted; so mark this
 375                                 // entry as unusable.
 376                                 occ.insert(None);
 377                             }
 378                         }
 379
 380                         // If the sequence contents can be empty, then the first
 381                         // token could be the separator token itself.
 382
 383                         if let (Some(ref sep), true) = (seq_rep.separator.clone(),
 384                                                         subfirst.maybe_empty) {
 385                             first.add_one_maybe(TokenTree::Token(sp, sep.clone()));
 386                         }
 387
 388                         // Reverse scan: Sequence comes before `first`.
 389                         if subfirst.maybe_empty || seq_rep.op == quoted::KleeneOp::ZeroOrMore {
 390                             // If sequence is potentially empty, then
 391                             // union them (preserving first emptiness).
 392                             first.add_all(&TokenSet { maybe_empty: true, ..subfirst });
 393                         } else {
 394                             // Otherwise, sequence guaranteed
 395                             // non-empty; replace first.
 396                             first = subfirst;
 397                         }
 398                     }
 399                 }
 400             }
 401
 402             return first;
 403         }
 404     }
 405
 406     // walks forward over `tts` until all potential FIRST tokens are
 407     // identified.
 408     fn first(&self, tts: &[quoted::TokenTree]) -> TokenSet {
 409         use self::quoted::TokenTree;
 410
 411         let mut first = TokenSet::empty();
 412         for tt in tts.iter() {
 413             assert!(first.maybe_empty);
 414             match *tt {
 415                 TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
 416                     first.add_one(tt.clone());
 417                     return first;
 418                 }
 419                 TokenTree::Delimited(span, ref delimited) => {
 420                     first.add_one(delimited.open_tt(span));
 421                     return first;
 422                 }
 423                 TokenTree::Sequence(sp, ref seq_rep) => {
 424                     match self.first.get(&sp) {
 425                         Some(&Some(ref subfirst)) => {
 426
 427                             // If the sequence contents can be empty, then the first
 428                             // token could be the separator token itself.
 429
 430                             if let (Some(ref sep), true) = (seq_rep.separator.clone(),
 431                                                             subfirst.maybe_empty) {
 432                                 first.add_one_maybe(TokenTree::Token(sp, sep.clone()));
 433                             }
 434
 435                             assert!(first.maybe_empty);
 436                             first.add_all(subfirst);
 437                             if subfirst.maybe_empty ||
 438                                seq_rep.op == quoted::KleeneOp::ZeroOrMore {
 439                                 // continue scanning for more first
 440                                 // tokens, but also make sure we
 441                                 // restore empty-tracking state
 442                                 first.maybe_empty = true;
 443                                 continue;
 444                             } else {
 445                                 return first;
 446                             }
 447                         }
 448
 449                         Some(&None) => {
 450                             panic!("assume all sequences have (unique) spans for now");
 451                         }
 452
 453                         None => {
 454                             panic!("We missed a sequence during FirstSets construction");
 455                         }
 456                     }
 457                 }
 458             }
 459         }
 460
 461         // we only exit the loop if `tts` was empty or if every
 462         // element of `tts` matches the empty sequence.
 463         assert!(first.maybe_empty);
 464         return first;
 465     }
 466 }
 467
 468 // A set of `quoted::TokenTree`s, which may include `TokenTree::Match`s
 469 // (for macro-by-example syntactic variables). It also carries the
 470 // `maybe_empty` flag; that is true if and only if the matcher can
 471 // match an empty token sequence.
 472 //
 473 // The First set is computed on submatchers like `$($a:expr b),* $(c)* d`,
 474 // which has corresponding FIRST = {$a:expr, c, d}.
 475 // Likewise, `$($a:expr b),* $(c)+ d` has FIRST = {$a:expr, c}.
 476 //
 477 // (Notably, we must allow for *-op to occur zero times.)
 478 #[derive(Clone, Debug)]
 479 struct TokenSet {
 480     tokens: Vec<quoted::TokenTree>,
 481     maybe_empty: bool,
 482 }
 483
 484 impl TokenSet {
 485     // Returns a set for the empty sequence.
 486     fn empty() -> Self { TokenSet { tokens: Vec::new(), maybe_empty: true } }
 487
 488     // Returns the set `{ tok }` for the single-token (and thus
 489     // non-empty) sequence [tok].
 490     fn singleton(tok: quoted::TokenTree) -> Self {
 491         TokenSet { tokens: vec![tok], maybe_empty: false }
 492     }
 493
 494     // Changes self to be the set `{ tok }`.
 495     // Since `tok` is always present, marks self as non-empty.
 496     fn replace_with(&mut self, tok: quoted::TokenTree) {
 497         self.tokens.clear();
 498         self.tokens.push(tok);
 499         self.maybe_empty = false;
 500     }
 501
 502     // Changes self to be the empty set `{}`; meant for use when
 503     // the particular token does not matter, but we want to
 504     // record that it occurs.
 505     fn replace_with_irrelevant(&mut self) {
 506         self.tokens.clear();
 507         self.maybe_empty = false;
 508     }
 509
 510     // Adds `tok` to the set for `self`, marking sequence as non-empy.
 511     fn add_one(&mut self, tok: quoted::TokenTree) {
 512         if !self.tokens.contains(&tok) {
 513             self.tokens.push(tok);
 514         }
 515         self.maybe_empty = false;
 516     }
 517
 518     // Adds `tok` to the set for `self`. (Leaves `maybe_empty` flag alone.)
 519     fn add_one_maybe(&mut self, tok: quoted::TokenTree) {
 520         if !self.tokens.contains(&tok) {
 521             self.tokens.push(tok);
 522         }
 523     }
 524
 525     // Adds all elements of `other` to this.
 526     //
 527     // (Since this is a set, we filter out duplicates.)
 528     //
 529     // If `other` is potentially empty, then preserves the previous
 530     // setting of the empty flag of `self`. If `other` is guaranteed
 531     // non-empty, then `self` is marked non-empty.
 532     fn add_all(&mut self, other: &Self) {
 533         for tok in &other.tokens {
 534             if !self.tokens.contains(tok) {
 535                 self.tokens.push(tok.clone());
 536             }
 537         }
 538         if !other.maybe_empty {
 539             self.maybe_empty = false;
 540         }
 541     }
 542 }
 543
 544 // Checks that `matcher` is internally consistent and that it
 545 // can legally by followed by a token N, for all N in `follow`.
 546 // (If `follow` is empty, then it imposes no constraint on
 547 // the `matcher`.)
 548 //
 549 // Returns the set of NT tokens that could possibly come last in
 550 // `matcher`. (If `matcher` matches the empty sequence, then
 551 // `maybe_empty` will be set to true.)
 552 //
 553 // Requires that `first_sets` is pre-computed for `matcher`;
 554 // see `FirstSets::new`.
 555 fn check_matcher_core(sess: &ParseSess,
 556                       first_sets: &FirstSets,
 557                       matcher: &[quoted::TokenTree],
 558                       follow: &TokenSet) -> TokenSet {
 559     use self::quoted::TokenTree;
 560
 561     let mut last = TokenSet::empty();
 562
 563     // 2. For each token and suffix  [T, SUFFIX] in M:
 564     // ensure that T can be followed by SUFFIX, and if SUFFIX may be empty,
 565     // then ensure T can also be followed by any element of FOLLOW.
 566     'each_token: for i in 0..matcher.len() {
 567         let token = &matcher[i];
 568         let suffix = &matcher[i+1..];
 569
 570         let build_suffix_first = || {
 571             let mut s = first_sets.first(suffix);
 572             if s.maybe_empty { s.add_all(follow); }
 573             return s;
 574         };
 575
 576         // (we build `suffix_first` on demand below; you can tell
 577         // which cases are supposed to fall through by looking for the
 578         // initialization of this variable.)
 579         let suffix_first;
 580
 581         // First, update `last` so that it corresponds to the set
 582         // of NT tokens that might end the sequence `... token`.
 583         match *token {
 584             TokenTree::Token(..) | TokenTree::MetaVarDecl(..) => {
 585                 let can_be_followed_by_any;
 586                 if let Err(bad_frag) = has_legal_fragment_specifier(token) {
 587                     let msg = format!("invalid fragment specifier `{}`", bad_frag);
 588                     sess.span_diagnostic.struct_span_err(token.span(), &msg)
 589                         .help("valid fragment specifiers are `ident`, `block`, \
 590                                `stmt`, `expr`, `pat`, `ty`, `path`, `meta`, `tt` \
 591                                and `item`")
 592                         .emit();
 593                     // (This eliminates false positives and duplicates
 594                     // from error messages.)
 595                     can_be_followed_by_any = true;
 596                 } else {
 597                     can_be_followed_by_any = token_can_be_followed_by_any(token);
 598                 }
 599
 600                 if can_be_followed_by_any {
 601                     // don't need to track tokens that work with any,
 602                     last.replace_with_irrelevant();
 603                     // ... and don't need to check tokens that can be
 604                     // followed by anything against SUFFIX.
 605                     continue 'each_token;
 606                 } else {
 607                     last.replace_with(token.clone());
 608                     suffix_first = build_suffix_first();
 609                 }
 610             }
 611             TokenTree::Delimited(span, ref d) => {
 612                 let my_suffix = TokenSet::singleton(d.close_tt(span));
 613                 check_matcher_core(sess, first_sets, &d.tts, &my_suffix);
 614                 // don't track non NT tokens
 615                 last.replace_with_irrelevant();
 616
 617                 // also, we don't need to check delimited sequences
 618                 // against SUFFIX
 619                 continue 'each_token;
 620             }
 621             TokenTree::Sequence(sp, ref seq_rep) => {
 622                 suffix_first = build_suffix_first();
 623                 // The trick here: when we check the interior, we want
 624                 // to include the separator (if any) as a potential
 625                 // (but not guaranteed) element of FOLLOW. So in that
 626                 // case, we make a temp copy of suffix and stuff
 627                 // delimiter in there.
 628                 //
 629                 // FIXME: Should I first scan suffix_first to see if
 630                 // delimiter is already in it before I go through the
 631                 // work of cloning it? But then again, this way I may
 632                 // get a "tighter" span?
 633                 let mut new;
 634                 let my_suffix = if let Some(ref u) = seq_rep.separator {
 635                     new = suffix_first.clone();
 636                     new.add_one_maybe(TokenTree::Token(sp, u.clone()));
 637                     &new
 638                 } else {
 639                     &suffix_first
 640                 };
 641
 642                 // At this point, `suffix_first` is built, and
 643                 // `my_suffix` is some TokenSet that we can use
 644                 // for checking the interior of `seq_rep`.
 645                 let next = check_matcher_core(sess, first_sets, &seq_rep.tts, my_suffix);
 646                 if next.maybe_empty {
 647                     last.add_all(&next);
 648                 } else {
 649                     last = next;
 650                 }
 651
 652                 // the recursive call to check_matcher_core already ran the 'each_last
 653                 // check below, so we can just keep going forward here.
 654                 continue 'each_token;
 655             }
 656         }
 657
 658         // (`suffix_first` guaranteed initialized once reaching here.)
 659
 660         // Now `last` holds the complete set of NT tokens that could
 661         // end the sequence before SUFFIX. Check that every one works with `suffix`.
 662         'each_last: for token in &last.tokens {
 663             if let TokenTree::MetaVarDecl(_, ref name, ref frag_spec) = *token {
 664                 for next_token in &suffix_first.tokens {
 665                     match is_in_follow(next_token, &frag_spec.name.as_str()) {
 666                         Err((msg, help)) => {
 667                             sess.span_diagnostic.struct_span_err(next_token.span(), &msg)
 668                                 .help(help).emit();
 669                             // don't bother reporting every source of
 670                             // conflict for a particular element of `last`.
 671                             continue 'each_last;
 672                         }
 673                         Ok(true) => {}
 674                         Ok(false) => {
 675                             let may_be = if last.tokens.len() == 1 &&
 676                                 suffix_first.tokens.len() == 1
 677                             {
 678                                 "is"
 679                             } else {
 680                                 "may be"
 681                             };
 682
 683                             sess.span_diagnostic.span_err(
 684                                 next_token.span(),
 685                                 &format!("`${name}:{frag}` {may_be} followed by `{next}`, which \
 686                                           is not allowed for `{frag}` fragments",
 687                                          name=name,
 688                                          frag=frag_spec,
 689                                          next=quoted_tt_to_string(next_token),
 690                                          may_be=may_be)
 691                             );
 692                         }
 693                     }
 694                 }
 695             }
 696         }
 697     }
 698     last
 699 }
 700
 701 fn token_can_be_followed_by_any(tok: &quoted::TokenTree) -> bool {
 702     if let quoted::TokenTree::MetaVarDecl(_, _, frag_spec) = *tok {
 703         frag_can_be_followed_by_any(&frag_spec.name.as_str())
 704     } else {
 705         // (Non NT's can always be followed by anthing in matchers.)
 706         true
 707     }
 708 }
 709
 710 /// True if a fragment of type `frag` can be followed by any sort of
 711 /// token.  We use this (among other things) as a useful approximation
 712 /// for when `frag` can be followed by a repetition like `$(...)*` or
 713 /// `$(...)+`. In general, these can be a bit tricky to reason about,
 714 /// so we adopt a conservative position that says that any fragment
 715 /// specifier which consumes at most one token tree can be followed by
 716 /// a fragment specifier (indeed, these fragments can be followed by
 717 /// ANYTHING without fear of future compatibility hazards).
 718 fn frag_can_be_followed_by_any(frag: &str) -> bool {
 719     match frag {
 720         "item"  | // always terminated by `}` or `;`
 721         "block" | // exactly one token tree
 722         "ident" | // exactly one token tree
 723         "meta"  | // exactly one token tree
 724         "tt" =>   // exactly one token tree
 725             true,
 726
 727         _ =>
 728             false,
 729     }
 730 }
 731
 732 /// True if `frag` can legally be followed by the token `tok`. For
 733 /// fragments that can consume an unbounded number of tokens, `tok`
 734 /// must be within a well-defined follow set. This is intended to
 735 /// guarantee future compatibility: for example, without this rule, if
 736 /// we expanded `expr` to include a new binary operator, we might
 737 /// break macros that were relying on that binary operator as a
 738 /// separator.
 739 // when changing this do not forget to update doc/book/macros.md!
 740 fn is_in_follow(tok: &quoted::TokenTree, frag: &str) -> Result<bool, (String, &'static str)> {
 741     use self::quoted::TokenTree;
 742
 743     if let TokenTree::Token(_, token::CloseDelim(_)) = *tok {
 744         // closing a token tree can never be matched by any fragment;
 745         // iow, we always require that `(` and `)` match, etc.
 746         Ok(true)
 747     } else {
 748         match frag {
 749             "item" => {
 750                 // since items *must* be followed by either a `;` or a `}`, we can
 751                 // accept anything after them
 752                 Ok(true)
 753             },
 754             "block" => {
 755                 // anything can follow block, the braces provide an easy boundary to
 756                 // maintain
 757                 Ok(true)
 758             },
 759             "stmt" | "expr"  => match *tok {
 760                 TokenTree::Token(_, ref tok) => match *tok {
 761                     FatArrow | Comma | Semi => Ok(true),
 762                     _ => Ok(false)
 763                 },
 764                 _ => Ok(false),
 765             },
 766             "pat" => match *tok {
 767                 TokenTree::Token(_, ref tok) => match *tok {
 768                     FatArrow | Comma | Eq | BinOp(token::Or) => Ok(true),
 769                     Ident(i) if i.name == "if" || i.name == "in" => Ok(true),
 770                     _ => Ok(false)
 771                 },
 772                 _ => Ok(false),
 773             },
 774             "path" | "ty" => match *tok {
 775                 TokenTree::Token(_, ref tok) => match *tok {
 776                     OpenDelim(token::DelimToken::Brace) | OpenDelim(token::DelimToken::Bracket) |
 777                     Comma | FatArrow | Colon | Eq | Gt | Semi | BinOp(token::Or) => Ok(true),
 778                     Ident(i) if i.name == "as" || i.name == "where" => Ok(true),
 779                     _ => Ok(false)
 780                 },
 781                 TokenTree::MetaVarDecl(_, _, frag) if frag.name == "block" => Ok(true),
 782                 _ => Ok(false),
 783             },
 784             "ident" => {
 785                 // being a single token, idents are harmless
 786                 Ok(true)
 787             },
 788             "meta" | "tt" => {
 789                 // being either a single token or a delimited sequence, tt is
 790                 // harmless
 791                 Ok(true)
 792             },
 793             "" => Ok(true), // keywords::Invalid
 794             _ => Err((format!("invalid fragment specifier `{}`", frag),
 795                      "valid fragment specifiers are `ident`, `block`, \
 796                       `stmt`, `expr`, `pat`, `ty`, `path`, `meta`, `tt` \
 797                       and `item`"))
 798         }
 799     }
 800 }
 801
 802 fn has_legal_fragment_specifier(tok: &quoted::TokenTree) -> Result<(), String> {
 803     debug!("has_legal_fragment_specifier({:?})", tok);
 804     if let quoted::TokenTree::MetaVarDecl(_, _, frag_spec) = *tok {
 805         let s = &frag_spec.name.as_str();
 806         if !is_legal_fragment_specifier(s) {
 807             return Err(s.to_string());
 808         }
 809     }
 810     Ok(())
 811 }
 812
 813 fn is_legal_fragment_specifier(frag: &str) -> bool {
 814     match frag {
 815         "item" | "block" | "stmt" | "expr" | "pat" |
 816         "path" | "ty" | "ident" | "meta" | "tt" | "" => true,
 817         _ => false,
 818     }
 819 }
 820
 821 fn quoted_tt_to_string(tt: &quoted::TokenTree) -> String {
 822     match *tt {
 823         quoted::TokenTree::Token(_, ref tok) => ::print::pprust::token_to_string(tok),
 824         quoted::TokenTree::MetaVarDecl(_, name, kind) => format!("${}:{}", name, kind),
 825         _ => panic!("unexpected quoted::TokenTree::{Sequence or Delimited} in follow set checker"),
 826     }
 827 }