1 //! Checks that meta-variables in macro definition are correctly declared and used.
5 //! ## Meta-variables must not be bound twice
8 //! macro_rules! foo { ($x:tt $x:tt) => { $x }; }
11 //! This check is sound (no false-negative) and complete (no false-positive).
13 //! ## Meta-variables must not be free
16 //! macro_rules! foo { () => { $x }; }
19 //! This check is also done at macro instantiation but only if the branch is taken.
21 //! ## Meta-variables must repeat at least as many times as their binder
24 //! macro_rules! foo { ($($x:tt)*) => { $x }; }
27 //! This check is also done at macro instantiation but only if the branch is taken.
29 //! ## Meta-variables must repeat with the same Kleene operators as their binder
32 //! macro_rules! foo { ($($x:tt)+) => { $($x)* }; }
35 //! This check is not done at macro instantiation.
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
44 //! ## Examples of false positive
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.
53 //! macro_rules! foo { ($name:ident) => { $name! bar { ($x:tt) => { $x }; } }; }
54 //! foo!(macro_rules);
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!`.
62 //! macro_rules! foo { () => { stringify!(macro_rules! bar { () => { $x }; }) }; }
65 //! ## Examples of false negative
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.
74 //! macro_rules! foo { ($d:tt) => { macro_rules! bar { ($y:tt) => { $d z }; } }; }
77 //! # How it is checked
79 //! There are 3 main functions: `check_binders`, `check_occurrences`, and `check_nested_macro`. They
80 //! all need some kind of environment.
84 //! Environments are used to pass information.
86 //! ### From LHS to RHS
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
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.
96 //! ### From outer macro to inner macro
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.
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
107 use crate::mbe::{KleeneToken, TokenTree};
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};
118 use smallvec::SmallVec;
122 /// Stack represented as linked list.
124 /// Those are used for environments because they grow incrementally and are not mutable.
128 /// A non-empty stack.
132 /// The previous elements.
133 prev: &'a Stack<'a, T>,
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)
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 }
149 impl<'a, T> Iterator for &'a Stack<'a, T> {
152 // Iterates from top to bottom of the stack.
153 fn next(&mut self) -> Option<&'a T> {
155 Stack::Empty => None,
156 Stack::Push { ref top, ref prev } => {
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.
173 /// Information attached to a meta-variable binder in LHS.
175 /// The span of the meta-variable in LHS.
177 /// The stack of Kleene operators (outermost first).
178 ops: SmallVec<[KleeneToken; 1]>,
181 /// An environment of meta-variables to their binder information.
182 type Binders = FxHashMap<MacroRulesNormalizedIdent, BinderInfo>;
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]>,
192 /// Checks that meta-variables are used correctly in a macro definition.
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(
206 if lhses.len() != rhses.len() {
207 sess.span_diagnostic.span_bug(span, "length mismatch between LHSes and RHSes")
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);
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.
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
233 macros: &Stack<'_, MacroState<'_>>,
234 binders: &mut Binders,
235 ops: &Stack<'_, KleeneToken>,
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");
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() });
259 // 3. The meta-variable is bound: This is an occurrence.
260 check_occurrences(sess, node_id, lhs, macros, binders, ops, valid);
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.
270 MISSING_FRAGMENT_SPECIFIER,
273 "missing fragment specifier",
276 if !macros.is_empty() {
277 sess.span_diagnostic.span_bug(span, "unexpected MetaVarDecl in nested lhs");
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.
284 .struct_span_err(span, "duplicate matcher binding")
285 .span_label(span, "duplicate binding")
286 .span_label(prev_info.span, "previous binding")
290 binders.insert(name, BinderInfo { span, ops: ops.into() });
293 // `MetaVarExpr` can not appear in the LHS of a macro arm
294 TokenTree::MetaVarExpr(..) => {}
295 TokenTree::Delimited(_, ref del) => {
297 check_binders(sess, node_id, tt, macros, binders, ops, valid);
300 TokenTree::Sequence(_, ref seq) => {
301 let ops = ops.push(seq.kleene);
303 check_binders(sess, node_id, tt, macros, binders, &ops, valid);
309 /// Returns the binder information of a meta-variable.
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)))
323 /// Checks `rhs` as part of the RHS of a macro definition and sets `valid` to false in case of
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(
338 macros: &Stack<'_, MacroState<'_>>,
340 ops: &Stack<'_, KleeneToken>,
344 TokenTree::Token(..) => {}
345 TokenTree::MetaVarDecl(span, _name, _kind) => {
346 sess.span_diagnostic.span_bug(span, "unexpected MetaVarDecl in rhs")
348 TokenTree::MetaVar(span, name) => {
349 let name = MacroRulesNormalizedIdent::new(name);
350 check_ops_is_prefix(sess, node_id, macros, binders, ops, span, name);
352 TokenTree::MetaVarExpr(dl, ref mve) => {
353 let Some(name) = mve.ident().map(MacroRulesNormalizedIdent::new) else {
356 check_ops_is_prefix(sess, node_id, macros, binders, ops, dl.entire(), name);
358 TokenTree::Delimited(_, ref del) => {
359 check_nested_occurrences(sess, node_id, &del.tts, macros, binders, ops, valid);
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);
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.
373 /// The token `macro_rules` was processed.
375 /// The tokens `macro_rules!` were processed.
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).
380 /// The keyword `macro` was processed.
382 /// The keyword `macro` followed by a name was processed.
384 /// The keyword `macro` followed by a name and a token delimited by parentheses was processed.
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.
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(
403 macros: &Stack<'_, MacroState<'_>>,
405 ops: &Stack<'_, KleeneToken>,
408 let mut state = NestedMacroState::Empty;
409 let nested_macros = macros.push(MacroState { binders, ops: ops.into() });
410 let mut nested_binders = Binders::default();
414 NestedMacroState::Empty,
415 &TokenTree::Token(Token { kind: TokenKind::Ident(name, false), .. }),
417 if name == kw::MacroRules {
418 state = NestedMacroState::MacroRules;
419 } else if name == kw::Macro {
420 state = NestedMacroState::Macro;
424 NestedMacroState::MacroRules,
425 &TokenTree::Token(Token { kind: TokenKind::Not, .. }),
427 state = NestedMacroState::MacroRulesNot;
430 NestedMacroState::MacroRulesNot,
431 &TokenTree::Token(Token { kind: TokenKind::Ident(..), .. }),
433 state = NestedMacroState::MacroRulesNotName;
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);
440 (NestedMacroState::MacroRulesNotName, &TokenTree::Delimited(_, ref del))
441 | (NestedMacroState::MacroName, &TokenTree::Delimited(_, ref del))
442 if del.delim == Delimiter::Brace =>
444 let macro_rules = state == NestedMacroState::MacroRulesNotName;
445 state = NestedMacroState::Empty;
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(
461 NestedMacroState::Macro,
462 &TokenTree::Token(Token { kind: TokenKind::Ident(..), .. }),
464 state = NestedMacroState::MacroName;
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);
471 (NestedMacroState::MacroName, &TokenTree::Delimited(_, ref del))
472 if del.delim == Delimiter::Parenthesis =>
474 state = NestedMacroState::MacroNameParen;
475 nested_binders = Binders::default();
486 (NestedMacroState::MacroNameParen, &TokenTree::Delimited(_, ref del))
487 if del.delim == Delimiter::Brace =>
489 state = NestedMacroState::Empty;
501 state = NestedMacroState::Empty;
502 check_occurrences(sess, node_id, tt, macros, binders, ops, valid);
508 /// Checks the body of nested macro, returns where the check stopped, and sets `valid` to false in
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.
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(
527 macros: &Stack<'_, MacroState<'_>>,
532 let separator = if macro_rules { TokenKind::Semi } else { TokenKind::Comma };
534 // We expect 3 token trees: `(LHS) => {RHS}`. The separator is checked after.
536 || !tts[i].is_delimited()
537 || !tts[i + 1].is_token(&TokenKind::FatArrow)
538 || !tts[i + 2].is_delimited()
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.
551 if i == n || !tts[i].is_token(&separator) {
554 // We increment our checked position for the semicolon.
560 /// Checks that a meta-variable occurrence is valid.
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(
573 macros: &Stack<'_, MacroState<'_>>,
575 ops: &Stack<'_, KleeneToken>,
577 name: MacroRulesNormalizedIdent,
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 ¯os {
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);
594 ops_is_prefix(sess, node_id, span, name, &binder.ops, &occurrence_ops);
598 buffer_lint(sess, span.into(), node_id, &format!("unknown macro variable `{}`", name));
601 /// Returns whether `binder_ops` is a prefix of `occurrence_ops`.
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.
606 /// Consider $i in the following example:
607 /// ```ignore (illustrative)
608 /// ( $( $i:ident = $($j:ident),+ );* ) => { $($( $i += $j; )+)* }
610 /// It occurs under the Kleene stack ["*", "+"] and is bound under ["*"] only.
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
623 name: MacroRulesNormalizedIdent,
624 binder_ops: &[KleeneToken],
625 occurrence_ops: &[KleeneToken],
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);
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);
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);