compiler/rustc_expand/src/mbe/macro_check.rs

   1 //! Checks that meta-variables in macro definition are correctly declared and used.
   2 //!
   3 //! # What is checked
   4 //!
   5 //! ## Meta-variables must not be bound twice
   6 //!
   7 //! ```compile_fail
   8 //! macro_rules! foo { ($x:tt $x:tt) => { $x }; }
   9 //! ```
  10 //!
  11 //! This check is sound (no false-negative) and complete (no false-positive).
  12 //!
  13 //! ## Meta-variables must not be free
  14 //!
  15 //! ```
  16 //! macro_rules! foo { () => { $x }; }
  17 //! ```
  18 //!
  19 //! This check is also done at macro instantiation but only if the branch is taken.
  20 //!
  21 //! ## Meta-variables must repeat at least as many times as their binder
  22 //!
  23 //! ```
  24 //! macro_rules! foo { ($($x:tt)*) => { $x }; }
  25 //! ```
  26 //!
  27 //! This check is also done at macro instantiation but only if the branch is taken.
  28 //!
  29 //! ## Meta-variables must repeat with the same Kleene operators as their binder
  30 //!
  31 //! ```
  32 //! macro_rules! foo { ($($x:tt)+) => { $($x)* }; }
  33 //! ```
  34 //!
  35 //! This check is not done at macro instantiation.
  36 //!
  37 //! # Disclaimer
  38 //!
  39 //! In the presence of nested macros (a macro defined in a macro), those checks may have false
  40 //! positives and false negatives. We try to detect those cases by recognizing potential macro
  41 //! definitions in RHSes, but nested macros may be hidden through the use of particular values of
  42 //! meta-variables.
  43 //!
  44 //! ## Examples of false positive
  45 //!
  46 //! False positives can come from cases where we don't recognize a nested macro, because it depends
  47 //! on particular values of meta-variables. In the following example, we think both instances of
  48 //! `$x` are free, which is a correct statement if `$name` is anything but `macro_rules`. But when
  49 //! `$name` is `macro_rules`, like in the instantiation below, then `$x:tt` is actually a binder of
  50 //! the nested macro and `$x` is bound to it.
  51 //!
  52 //! ```
  53 //! macro_rules! foo { ($name:ident) => { $name! bar { ($x:tt) => { $x }; } }; }
  54 //! foo!(macro_rules);
  55 //! ```
  56 //!
  57 //! False positives can also come from cases where we think there is a nested macro while there
  58 //! isn't. In the following example, we think `$x` is free, which is incorrect because `bar` is not
  59 //! a nested macro since it is not evaluated as code by `stringify!`.
  60 //!
  61 //! ```
  62 //! macro_rules! foo { () => { stringify!(macro_rules! bar { () => { $x }; }) }; }
  63 //! ```
  64 //!
  65 //! ## Examples of false negative
  66 //!
  67 //! False negatives can come from cases where we don't recognize a meta-variable, because it depends
  68 //! on particular values of meta-variables. In the following examples, we don't see that if `$d` is
  69 //! instantiated with `$` then `$d z` becomes `$z` in the nested macro definition and is thus a free
  70 //! meta-variable. Note however, that if `foo` is instantiated, then we would check the definition
  71 //! of `bar` and would see the issue.
  72 //!
  73 //! ```
  74 //! macro_rules! foo { ($d:tt) => { macro_rules! bar { ($y:tt) => { $d z }; } }; }
  75 //! ```
  76 //!
  77 //! # How it is checked
  78 //!
  79 //! There are 3 main functions: `check_binders`, `check_occurrences`, and `check_nested_macro`. They
  80 //! all need some kind of environment.
  81 //!
  82 //! ## Environments
  83 //!
  84 //! Environments are used to pass information.
  85 //!
  86 //! ### From LHS to RHS
  87 //!
  88 //! When checking a LHS with `check_binders`, we produce (and use) an environment for binders,
  89 //! namely `Binders`. This is a mapping from binder name to information about that binder: the span
  90 //! of the binder for error messages and the stack of Kleene operators under which it was bound in
  91 //! the LHS.
  92 //!
  93 //! This environment is used by both the LHS and RHS. The LHS uses it to detect duplicate binders.
  94 //! The RHS uses it to detect the other errors.
  95 //!
  96 //! ### From outer macro to inner macro
  97 //!
  98 //! When checking the RHS of an outer macro and we detect a nested macro definition, we push the
  99 //! current state, namely `MacroState`, to an environment of nested macro definitions. Each state
 100 //! stores the LHS binders when entering the macro definition as well as the stack of Kleene
 101 //! operators under which the inner macro is defined in the RHS.
 102 //!
 103 //! This environment is a stack representing the nesting of macro definitions. As such, the stack of
 104 //! Kleene operators under which a meta-variable is repeating is the concatenation of the stacks
 105 //! stored when entering a macro definition starting from the state in which the meta-variable is
 106 //! bound.
 107 use crate::mbe::{KleeneToken, TokenTree};
 108
 109 use rustc_ast::token::{Delimiter, Token, TokenKind};
 110 use rustc_ast::{NodeId, DUMMY_NODE_ID};
 111 use rustc_data_structures::fx::FxHashMap;
 112 use rustc_errors::MultiSpan;
 113 use rustc_session::lint::builtin::{META_VARIABLE_MISUSE, MISSING_FRAGMENT_SPECIFIER};
 114 use rustc_session::parse::ParseSess;
 115 use rustc_span::symbol::kw;
 116 use rustc_span::{symbol::MacroRulesNormalizedIdent, Span};
 117
 118 use smallvec::SmallVec;
 119
 120 use std::iter;
 121
 122 /// Stack represented as linked list.
 123 ///
 124 /// Those are used for environments because they grow incrementally and are not mutable.
 125 enum Stack<'a, T> {
 126     /// Empty stack.
 127     Empty,
 128     /// A non-empty stack.
 129     Push {
 130         /// The top element.
 131         top: T,
 132         /// The previous elements.
 133         prev: &'a Stack<'a, T>,
 134     },
 135 }
 136
 137 impl<'a, T> Stack<'a, T> {
 138     /// Returns whether a stack is empty.
 139     fn is_empty(&self) -> bool {
 140         matches!(*self, Stack::Empty)
 141     }
 142
 143     /// Returns a new stack with an element of top.
 144     fn push(&'a self, top: T) -> Stack<'a, T> {
 145         Stack::Push { top, prev: self }
 146     }
 147 }
 148
 149 impl<'a, T> Iterator for &'a Stack<'a, T> {
 150     type Item = &'a T;
 151
 152     // Iterates from top to bottom of the stack.
 153     fn next(&mut self) -> Option<&'a T> {
 154         match self {
 155             Stack::Empty => None,
 156             Stack::Push { top, prev } => {
 157                 *self = prev;
 158                 Some(top)
 159             }
 160         }
 161     }
 162 }
 163
 164 impl From<&Stack<'_, KleeneToken>> for SmallVec<[KleeneToken; 1]> {
 165     fn from(ops: &Stack<'_, KleeneToken>) -> SmallVec<[KleeneToken; 1]> {
 166         let mut ops: SmallVec<[KleeneToken; 1]> = ops.cloned().collect();
 167         // The stack is innermost on top. We want outermost first.
 168         ops.reverse();
 169         ops
 170     }
 171 }
 172
 173 /// Information attached to a meta-variable binder in LHS.
 174 struct BinderInfo {
 175     /// The span of the meta-variable in LHS.
 176     span: Span,
 177     /// The stack of Kleene operators (outermost first).
 178     ops: SmallVec<[KleeneToken; 1]>,
 179 }
 180
 181 /// An environment of meta-variables to their binder information.
 182 type Binders = FxHashMap<MacroRulesNormalizedIdent, BinderInfo>;
 183
 184 /// The state at which we entered a macro definition in the RHS of another macro definition.
 185 struct MacroState<'a> {
 186     /// The binders of the branch where we entered the macro definition.
 187     binders: &'a Binders,
 188     /// The stack of Kleene operators (outermost first) where we entered the macro definition.
 189     ops: SmallVec<[KleeneToken; 1]>,
 190 }
 191
 192 /// Checks that meta-variables are used correctly in a macro definition.
 193 ///
 194 /// Arguments:
 195 /// - `sess` is used to emit diagnostics and lints
 196 /// - `node_id` is used to emit lints
 197 /// - `span` is used when no spans are available
 198 /// - `lhses` and `rhses` should have the same length and represent the macro definition
 199 pub(super) fn check_meta_variables(
 200     sess: &ParseSess,
 201     node_id: NodeId,
 202     span: Span,
 203     lhses: &[TokenTree],
 204     rhses: &[TokenTree],
 205 ) -> bool {
 206     if lhses.len() != rhses.len() {
 207         sess.span_diagnostic.span_bug(span, "length mismatch between LHSes and RHSes")
 208     }
 209     let mut valid = true;
 210     for (lhs, rhs) in iter::zip(lhses, rhses) {
 211         let mut binders = Binders::default();
 212         check_binders(sess, node_id, lhs, &Stack::Empty, &mut binders, &Stack::Empty, &mut valid);
 213         check_occurrences(sess, node_id, rhs, &Stack::Empty, &binders, &Stack::Empty, &mut valid);
 214     }
 215     valid
 216 }
 217
 218 /// Checks `lhs` as part of the LHS of a macro definition, extends `binders` with new binders, and
 219 /// sets `valid` to false in case of errors.
 220 ///
 221 /// Arguments:
 222 /// - `sess` is used to emit diagnostics and lints
 223 /// - `node_id` is used to emit lints
 224 /// - `lhs` is checked as part of a LHS
 225 /// - `macros` is the stack of possible outer macros
 226 /// - `binders` contains the binders of the LHS
 227 /// - `ops` is the stack of Kleene operators from the LHS
 228 /// - `valid` is set in case of errors
 229 fn check_binders(
 230     sess: &ParseSess,
 231     node_id: NodeId,
 232     lhs: &TokenTree,
 233     macros: &Stack<'_, MacroState<'_>>,
 234     binders: &mut Binders,
 235     ops: &Stack<'_, KleeneToken>,
 236     valid: &mut bool,
 237 ) {
 238     match *lhs {
 239         TokenTree::Token(..) => {}
 240         // This can only happen when checking a nested macro because this LHS is then in the RHS of
 241         // the outer macro. See ui/macros/macro-of-higher-order.rs where $y:$fragment in the
 242         // LHS of the nested macro (and RHS of the outer macro) is parsed as MetaVar(y) Colon
 243         // MetaVar(fragment) and not as MetaVarDecl(y, fragment).
 244         TokenTree::MetaVar(span, name) => {
 245             if macros.is_empty() {
 246                 sess.span_diagnostic.span_bug(span, "unexpected MetaVar in lhs");
 247             }
 248             let name = MacroRulesNormalizedIdent::new(name);
 249             // There are 3 possibilities:
 250             if let Some(prev_info) = binders.get(&name) {
 251                 // 1. The meta-variable is already bound in the current LHS: This is an error.
 252                 let mut span = MultiSpan::from_span(span);
 253                 span.push_span_label(prev_info.span, "previous declaration");
 254                 buffer_lint(sess, span, node_id, "duplicate matcher binding");
 255             } else if get_binder_info(macros, binders, name).is_none() {
 256                 // 2. The meta-variable is free: This is a binder.
 257                 binders.insert(name, BinderInfo { span, ops: ops.into() });
 258             } else {
 259                 // 3. The meta-variable is bound: This is an occurrence.
 260                 check_occurrences(sess, node_id, lhs, macros, binders, ops, valid);
 261             }
 262         }
 263         // Similarly, this can only happen when checking a toplevel macro.
 264         TokenTree::MetaVarDecl(span, name, kind) => {
 265             if kind.is_none() && node_id != DUMMY_NODE_ID {
 266                 // FIXME: Report this as a hard error eventually and remove equivalent errors from
 267                 // `parse_tt_inner` and `nameize`. Until then the error may be reported twice, once
 268                 // as a hard error and then once as a buffered lint.
 269                 sess.buffer_lint(
 270                     MISSING_FRAGMENT_SPECIFIER,
 271                     span,
 272                     node_id,
 273                     "missing fragment specifier",
 274                 );
 275             }
 276             if !macros.is_empty() {
 277                 sess.span_diagnostic.span_bug(span, "unexpected MetaVarDecl in nested lhs");
 278             }
 279             let name = MacroRulesNormalizedIdent::new(name);
 280             if let Some(prev_info) = get_binder_info(macros, binders, name) {
 281                 // Duplicate binders at the top-level macro definition are errors. The lint is only
 282                 // for nested macro definitions.
 283                 sess.span_diagnostic
 284                     .struct_span_err(span, "duplicate matcher binding")
 285                     .span_label(span, "duplicate binding")
 286                     .span_label(prev_info.span, "previous binding")
 287                     .emit();
 288                 *valid = false;
 289             } else {
 290                 binders.insert(name, BinderInfo { span, ops: ops.into() });
 291             }
 292         }
 293         // `MetaVarExpr` can not appear in the LHS of a macro arm
 294         TokenTree::MetaVarExpr(..) => {}
 295         TokenTree::Delimited(_, ref del) => {
 296             for tt in &del.tts {
 297                 check_binders(sess, node_id, tt, macros, binders, ops, valid);
 298             }
 299         }
 300         TokenTree::Sequence(_, ref seq) => {
 301             let ops = ops.push(seq.kleene);
 302             for tt in &seq.tts {
 303                 check_binders(sess, node_id, tt, macros, binders, &ops, valid);
 304             }
 305         }
 306     }
 307 }
 308
 309 /// Returns the binder information of a meta-variable.
 310 ///
 311 /// Arguments:
 312 /// - `macros` is the stack of possible outer macros
 313 /// - `binders` contains the current binders
 314 /// - `name` is the name of the meta-variable we are looking for
 315 fn get_binder_info<'a>(
 316     mut macros: &'a Stack<'a, MacroState<'a>>,
 317     binders: &'a Binders,
 318     name: MacroRulesNormalizedIdent,
 319 ) -> Option<&'a BinderInfo> {
 320     binders.get(&name).or_else(|| macros.find_map(|state| state.binders.get(&name)))
 321 }
 322
 323 /// Checks `rhs` as part of the RHS of a macro definition and sets `valid` to false in case of
 324 /// errors.
 325 ///
 326 /// Arguments:
 327 /// - `sess` is used to emit diagnostics and lints
 328 /// - `node_id` is used to emit lints
 329 /// - `rhs` is checked as part of a RHS
 330 /// - `macros` is the stack of possible outer macros
 331 /// - `binders` contains the binders of the associated LHS
 332 /// - `ops` is the stack of Kleene operators from the RHS
 333 /// - `valid` is set in case of errors
 334 fn check_occurrences(
 335     sess: &ParseSess,
 336     node_id: NodeId,
 337     rhs: &TokenTree,
 338     macros: &Stack<'_, MacroState<'_>>,
 339     binders: &Binders,
 340     ops: &Stack<'_, KleeneToken>,
 341     valid: &mut bool,
 342 ) {
 343     match *rhs {
 344         TokenTree::Token(..) => {}
 345         TokenTree::MetaVarDecl(span, _name, _kind) => {
 346             sess.span_diagnostic.span_bug(span, "unexpected MetaVarDecl in rhs")
 347         }
 348         TokenTree::MetaVar(span, name) => {
 349             let name = MacroRulesNormalizedIdent::new(name);
 350             check_ops_is_prefix(sess, node_id, macros, binders, ops, span, name);
 351         }
 352         TokenTree::MetaVarExpr(dl, ref mve) => {
 353             let Some(name) = mve.ident().map(MacroRulesNormalizedIdent::new) else {
 354                 return;
 355             };
 356             check_ops_is_prefix(sess, node_id, macros, binders, ops, dl.entire(), name);
 357         }
 358         TokenTree::Delimited(_, ref del) => {
 359             check_nested_occurrences(sess, node_id, &del.tts, macros, binders, ops, valid);
 360         }
 361         TokenTree::Sequence(_, ref seq) => {
 362             let ops = ops.push(seq.kleene);
 363             check_nested_occurrences(sess, node_id, &seq.tts, macros, binders, &ops, valid);
 364         }
 365     }
 366 }
 367
 368 /// Represents the processed prefix of a nested macro.
 369 #[derive(Clone, Copy, PartialEq, Eq)]
 370 enum NestedMacroState {
 371     /// Nothing that matches a nested macro definition was processed yet.
 372     Empty,
 373     /// The token `macro_rules` was processed.
 374     MacroRules,
 375     /// The tokens `macro_rules!` were processed.
 376     MacroRulesNot,
 377     /// The tokens `macro_rules!` followed by a name were processed. The name may be either directly
 378     /// an identifier or a meta-variable (that hopefully would be instantiated by an identifier).
 379     MacroRulesNotName,
 380     /// The keyword `macro` was processed.
 381     Macro,
 382     /// The keyword `macro` followed by a name was processed.
 383     MacroName,
 384     /// The keyword `macro` followed by a name and a token delimited by parentheses was processed.
 385     MacroNameParen,
 386 }
 387
 388 /// Checks `tts` as part of the RHS of a macro definition, tries to recognize nested macro
 389 /// definitions, and sets `valid` to false in case of errors.
 390 ///
 391 /// Arguments:
 392 /// - `sess` is used to emit diagnostics and lints
 393 /// - `node_id` is used to emit lints
 394 /// - `tts` is checked as part of a RHS and may contain macro definitions
 395 /// - `macros` is the stack of possible outer macros
 396 /// - `binders` contains the binders of the associated LHS
 397 /// - `ops` is the stack of Kleene operators from the RHS
 398 /// - `valid` is set in case of errors
 399 fn check_nested_occurrences(
 400     sess: &ParseSess,
 401     node_id: NodeId,
 402     tts: &[TokenTree],
 403     macros: &Stack<'_, MacroState<'_>>,
 404     binders: &Binders,
 405     ops: &Stack<'_, KleeneToken>,
 406     valid: &mut bool,
 407 ) {
 408     let mut state = NestedMacroState::Empty;
 409     let nested_macros = macros.push(MacroState { binders, ops: ops.into() });
 410     let mut nested_binders = Binders::default();
 411     for tt in tts {
 412         match (state, tt) {
 413             (
 414                 NestedMacroState::Empty,
 415                 &TokenTree::Token(Token { kind: TokenKind::Ident(name, false), .. }),
 416             ) => {
 417                 if name == kw::MacroRules {
 418                     state = NestedMacroState::MacroRules;
 419                 } else if name == kw::Macro {
 420                     state = NestedMacroState::Macro;
 421                 }
 422             }
 423             (
 424                 NestedMacroState::MacroRules,
 425                 &TokenTree::Token(Token { kind: TokenKind::Not, .. }),
 426             ) => {
 427                 state = NestedMacroState::MacroRulesNot;
 428             }
 429             (
 430                 NestedMacroState::MacroRulesNot,
 431                 &TokenTree::Token(Token { kind: TokenKind::Ident(..), .. }),
 432             ) => {
 433                 state = NestedMacroState::MacroRulesNotName;
 434             }
 435             (NestedMacroState::MacroRulesNot, &TokenTree::MetaVar(..)) => {
 436                 state = NestedMacroState::MacroRulesNotName;
 437                 // We check that the meta-variable is correctly used.
 438                 check_occurrences(sess, node_id, tt, macros, binders, ops, valid);
 439             }
 440             (NestedMacroState::MacroRulesNotName, TokenTree::Delimited(_, del))
 441             | (NestedMacroState::MacroName, TokenTree::Delimited(_, del))
 442                 if del.delim == Delimiter::Brace =>
 443             {
 444                 let macro_rules = state == NestedMacroState::MacroRulesNotName;
 445                 state = NestedMacroState::Empty;
 446                 let rest =
 447                     check_nested_macro(sess, node_id, macro_rules, &del.tts, &nested_macros, valid);
 448                 // If we did not check the whole macro definition, then check the rest as if outside
 449                 // the macro definition.
 450                 check_nested_occurrences(
 451                     sess,
 452                     node_id,
 453                     &del.tts[rest..],
 454                     macros,
 455                     binders,
 456                     ops,
 457                     valid,
 458                 );
 459             }
 460             (
 461                 NestedMacroState::Macro,
 462                 &TokenTree::Token(Token { kind: TokenKind::Ident(..), .. }),
 463             ) => {
 464                 state = NestedMacroState::MacroName;
 465             }
 466             (NestedMacroState::Macro, &TokenTree::MetaVar(..)) => {
 467                 state = NestedMacroState::MacroName;
 468                 // We check that the meta-variable is correctly used.
 469                 check_occurrences(sess, node_id, tt, macros, binders, ops, valid);
 470             }
 471             (NestedMacroState::MacroName, TokenTree::Delimited(_, del))
 472                 if del.delim == Delimiter::Parenthesis =>
 473             {
 474                 state = NestedMacroState::MacroNameParen;
 475                 nested_binders = Binders::default();
 476                 check_binders(
 477                     sess,
 478                     node_id,
 479                     tt,
 480                     &nested_macros,
 481                     &mut nested_binders,
 482                     &Stack::Empty,
 483                     valid,
 484                 );
 485             }
 486             (NestedMacroState::MacroNameParen, TokenTree::Delimited(_, del))
 487                 if del.delim == Delimiter::Brace =>
 488             {
 489                 state = NestedMacroState::Empty;
 490                 check_occurrences(
 491                     sess,
 492                     node_id,
 493                     tt,
 494                     &nested_macros,
 495                     &nested_binders,
 496                     &Stack::Empty,
 497                     valid,
 498                 );
 499             }
 500             (_, tt) => {
 501                 state = NestedMacroState::Empty;
 502                 check_occurrences(sess, node_id, tt, macros, binders, ops, valid);
 503             }
 504         }
 505     }
 506 }
 507
 508 /// Checks the body of nested macro, returns where the check stopped, and sets `valid` to false in
 509 /// case of errors.
 510 ///
 511 /// The token trees are checked as long as they look like a list of (LHS) => {RHS} token trees. This
 512 /// check is a best-effort to detect a macro definition. It returns the position in `tts` where we
 513 /// stopped checking because we detected we were not in a macro definition anymore.
 514 ///
 515 /// Arguments:
 516 /// - `sess` is used to emit diagnostics and lints
 517 /// - `node_id` is used to emit lints
 518 /// - `macro_rules` specifies whether the macro is `macro_rules`
 519 /// - `tts` is checked as a list of (LHS) => {RHS}
 520 /// - `macros` is the stack of outer macros
 521 /// - `valid` is set in case of errors
 522 fn check_nested_macro(
 523     sess: &ParseSess,
 524     node_id: NodeId,
 525     macro_rules: bool,
 526     tts: &[TokenTree],
 527     macros: &Stack<'_, MacroState<'_>>,
 528     valid: &mut bool,
 529 ) -> usize {
 530     let n = tts.len();
 531     let mut i = 0;
 532     let separator = if macro_rules { TokenKind::Semi } else { TokenKind::Comma };
 533     loop {
 534         // We expect 3 token trees: `(LHS) => {RHS}`. The separator is checked after.
 535         if i + 2 >= n
 536             || !tts[i].is_delimited()
 537             || !tts[i + 1].is_token(&TokenKind::FatArrow)
 538             || !tts[i + 2].is_delimited()
 539         {
 540             break;
 541         }
 542         let lhs = &tts[i];
 543         let rhs = &tts[i + 2];
 544         let mut binders = Binders::default();
 545         check_binders(sess, node_id, lhs, macros, &mut binders, &Stack::Empty, valid);
 546         check_occurrences(sess, node_id, rhs, macros, &binders, &Stack::Empty, valid);
 547         // Since the last semicolon is optional for `macro_rules` macros and decl_macro are not terminated,
 548         // we increment our checked position by how many token trees we already checked (the 3
 549         // above) before checking for the separator.
 550         i += 3;
 551         if i == n || !tts[i].is_token(&separator) {
 552             break;
 553         }
 554         // We increment our checked position for the semicolon.
 555         i += 1;
 556     }
 557     i
 558 }
 559
 560 /// Checks that a meta-variable occurrence is valid.
 561 ///
 562 /// Arguments:
 563 /// - `sess` is used to emit diagnostics and lints
 564 /// - `node_id` is used to emit lints
 565 /// - `macros` is the stack of possible outer macros
 566 /// - `binders` contains the binders of the associated LHS
 567 /// - `ops` is the stack of Kleene operators from the RHS
 568 /// - `span` is the span of the meta-variable to check
 569 /// - `name` is the name of the meta-variable to check
 570 fn check_ops_is_prefix(
 571     sess: &ParseSess,
 572     node_id: NodeId,
 573     macros: &Stack<'_, MacroState<'_>>,
 574     binders: &Binders,
 575     ops: &Stack<'_, KleeneToken>,
 576     span: Span,
 577     name: MacroRulesNormalizedIdent,
 578 ) {
 579     let macros = macros.push(MacroState { binders, ops: ops.into() });
 580     // Accumulates the stacks the operators of each state until (and including when) the
 581     // meta-variable is found. The innermost stack is first.
 582     let mut acc: SmallVec<[&SmallVec<[KleeneToken; 1]>; 1]> = SmallVec::new();
 583     for state in &macros {
 584         acc.push(&state.ops);
 585         if let Some(binder) = state.binders.get(&name) {
 586             // This variable concatenates the stack of operators from the RHS of the LHS where the
 587             // meta-variable was defined to where it is used (in possibly nested macros). The
 588             // outermost operator is first.
 589             let mut occurrence_ops: SmallVec<[KleeneToken; 2]> = SmallVec::new();
 590             // We need to iterate from the end to start with outermost stack.
 591             for ops in acc.iter().rev() {
 592                 occurrence_ops.extend_from_slice(ops);
 593             }
 594             ops_is_prefix(sess, node_id, span, name, &binder.ops, &occurrence_ops);
 595             return;
 596         }
 597     }
 598     buffer_lint(sess, span.into(), node_id, &format!("unknown macro variable `{}`", name));
 599 }
 600
 601 /// Returns whether `binder_ops` is a prefix of `occurrence_ops`.
 602 ///
 603 /// The stack of Kleene operators of a meta-variable occurrence just needs to have the stack of
 604 /// Kleene operators of its binder as a prefix.
 605 ///
 606 /// Consider $i in the following example:
 607 /// ```ignore (illustrative)
 608 /// ( $( $i:ident = $($j:ident),+ );* ) => { $($( $i += $j; )+)* }
 609 /// ```
 610 /// It occurs under the Kleene stack ["*", "+"] and is bound under ["*"] only.
 611 ///
 612 /// Arguments:
 613 /// - `sess` is used to emit diagnostics and lints
 614 /// - `node_id` is used to emit lints
 615 /// - `span` is the span of the meta-variable being check
 616 /// - `name` is the name of the meta-variable being check
 617 /// - `binder_ops` is the stack of Kleene operators for the binder
 618 /// - `occurrence_ops` is the stack of Kleene operators for the occurrence
 619 fn ops_is_prefix(
 620     sess: &ParseSess,
 621     node_id: NodeId,
 622     span: Span,
 623     name: MacroRulesNormalizedIdent,
 624     binder_ops: &[KleeneToken],
 625     occurrence_ops: &[KleeneToken],
 626 ) {
 627     for (i, binder) in binder_ops.iter().enumerate() {
 628         if i >= occurrence_ops.len() {
 629             let mut span = MultiSpan::from_span(span);
 630             span.push_span_label(binder.span, "expected repetition");
 631             let message = &format!("variable '{}' is still repeating at this depth", name);
 632             buffer_lint(sess, span, node_id, message);
 633             return;
 634         }
 635         let occurrence = &occurrence_ops[i];
 636         if occurrence.op != binder.op {
 637             let mut span = MultiSpan::from_span(span);
 638             span.push_span_label(binder.span, "expected repetition");
 639             span.push_span_label(occurrence.span, "conflicting repetition");
 640             let message = "meta-variable repeats with different Kleene operator";
 641             buffer_lint(sess, span, node_id, message);
 642             return;
 643         }
 644     }
 645 }
 646
 647 fn buffer_lint(sess: &ParseSess, span: MultiSpan, node_id: NodeId, message: &str) {
 648     // Macros loaded from other crates have dummy node ids.
 649     if node_id != DUMMY_NODE_ID {
 650         sess.buffer_lint(&META_VARIABLE_MISUSE, span, node_id, message);
 651     }
 652 }