1 use crate::base::ExtCtxt;
2 use crate::mbe::macro_parser::{MatchedNonterminal, MatchedSeq, MatchedTokenTree, NamedMatch};
3 use crate::mbe::{self, MetaVarExpr};
4 use rustc_ast::mut_visit::{self, MutVisitor};
5 use rustc_ast::token::{self, Delimiter, Token, TokenKind};
6 use rustc_ast::tokenstream::{DelimSpan, Spacing, TokenStream, TokenTree};
7 use rustc_data_structures::fx::FxHashMap;
8 use rustc_errors::{pluralize, PResult};
9 use rustc_errors::{DiagnosticBuilder, ErrorGuaranteed};
10 use rustc_macros::SessionDiagnostic;
11 use rustc_span::hygiene::{LocalExpnId, Transparency};
12 use rustc_span::symbol::{sym, Ident, MacroRulesNormalizedIdent};
15 use smallvec::{smallvec, SmallVec};
18 // A Marker adds the given mark to the syntax context.
19 struct Marker(LocalExpnId, Transparency);
21 impl MutVisitor for Marker {
22 const VISIT_TOKENS: bool = true;
24 fn visit_span(&mut self, span: &mut Span) {
25 *span = span.apply_mark(self.0.to_expn_id(), self.1)
29 /// An iterator over the token trees in a delimited token tree (`{ ... }`) or a sequence (`$(...)`).
31 Delimited { tts: &'a [mbe::TokenTree], idx: usize, delim: Delimiter, span: DelimSpan },
32 Sequence { tts: &'a [mbe::TokenTree], idx: usize, sep: Option<Token> },
36 /// Construct a new frame around the delimited set of tokens.
37 fn new(src: &'a mbe::Delimited, span: DelimSpan) -> Frame<'a> {
38 Frame::Delimited { tts: &src.tts, idx: 0, delim: src.delim, span }
42 impl<'a> Iterator for Frame<'a> {
43 type Item = &'a mbe::TokenTree;
45 fn next(&mut self) -> Option<&'a mbe::TokenTree> {
47 Frame::Delimited { tts, ref mut idx, .. }
48 | Frame::Sequence { tts, ref mut idx, .. } => {
49 let res = tts.get(*idx);
57 #[derive(SessionDiagnostic)]
58 #[error(expand::expr_repeat_no_syntax_vars)]
59 struct NoSyntaxVarsExprRepeat {
64 #[derive(SessionDiagnostic)]
65 #[error(expand::must_repeat_once)]
66 struct MustRepeatOnce {
71 /// This can do Macro-By-Example transcription.
72 /// - `interp` is a map of meta-variables to the tokens (non-terminals) they matched in the
73 /// invocation. We are assuming we already know there is a match.
74 /// - `src` is the RHS of the MBE, that is, the "example" we are filling in.
79 /// macro_rules! foo {
80 /// ($id:ident) => { println!("{}", stringify!($id)); }
86 /// `interp` would contain `$id => bar` and `src` would contain `println!("{}", stringify!($id));`.
88 /// `transcribe` would return a `TokenStream` containing `println!("{}", stringify!(bar));`.
90 /// Along the way, we do some additional error checking.
91 pub(super) fn transcribe<'a>(
93 interp: &FxHashMap<MacroRulesNormalizedIdent, NamedMatch>,
96 transparency: Transparency,
97 ) -> PResult<'a, TokenStream> {
98 // Nothing for us to transcribe...
99 if src.tts.is_empty() {
100 return Ok(TokenStream::default());
103 // We descend into the RHS (`src`), expanding things as we go. This stack contains the things
104 // we have yet to expand/are still expanding. We start the stack off with the whole RHS.
105 let mut stack: SmallVec<[Frame<'_>; 1]> = smallvec![Frame::new(&src, src_span)];
107 // As we descend in the RHS, we will need to be able to match nested sequences of matchers.
108 // `repeats` keeps track of where we are in matching at each level, with the last element being
109 // the most deeply nested sequence. This is used as a stack.
110 let mut repeats = Vec::new();
112 // `result` contains resulting token stream from the TokenTree we just finished processing. At
113 // the end, this will contain the full result of transcription, but at arbitrary points during
114 // `transcribe`, `result` will contain subsets of the final result.
116 // Specifically, as we descend into each TokenTree, we will push the existing results onto the
117 // `result_stack` and clear `results`. We will then produce the results of transcribing the
118 // TokenTree into `results`. Then, as we unwind back out of the `TokenTree`, we will pop the
119 // `result_stack` and append `results` too it to produce the new `results` up to that point.
121 // Thus, if we try to pop the `result_stack` and it is empty, we have reached the top-level
122 // again, and we are done transcribing.
123 let mut result: Vec<TokenTree> = Vec::new();
124 let mut result_stack = Vec::new();
125 let mut marker = Marker(cx.current_expansion.id, transparency);
128 // Look at the last frame on the stack.
129 // If it still has a TokenTree we have not looked at yet, use that tree.
130 let Some(tree) = stack.last_mut().unwrap().next() else {
131 // This else-case never produces a value for `tree` (it `continue`s or `return`s).
133 // Otherwise, if we have just reached the end of a sequence and we can keep repeating,
134 // go back to the beginning of the sequence.
135 if let Frame::Sequence { idx, sep, .. } = stack.last_mut().unwrap() {
136 let (repeat_idx, repeat_len) = repeats.last_mut().unwrap();
138 if repeat_idx < repeat_len {
140 if let Some(sep) = sep {
141 result.push(TokenTree::Token(sep.clone(), Spacing::Alone));
147 // We are done with the top of the stack. Pop it. Depending on what it was, we do
148 // different things. Note that the outermost item must be the delimited, wrapped RHS
149 // that was passed in originally to `transcribe`.
150 match stack.pop().unwrap() {
151 // Done with a sequence. Pop from repeats.
152 Frame::Sequence { .. } => {
156 // We are done processing a Delimited. If this is the top-level delimited, we are
157 // done. Otherwise, we unwind the result_stack to append what we have produced to
158 // any previous results.
159 Frame::Delimited { delim, span, .. } => {
160 if result_stack.is_empty() {
161 // No results left to compute! We are back at the top-level.
162 return Ok(TokenStream::new(result));
165 // Step back into the parent Delimited.
166 let tree = TokenTree::Delimited(span, delim, TokenStream::new(result));
167 result = result_stack.pop().unwrap();
174 // At this point, we know we are in the middle of a TokenTree (the last one on `stack`).
175 // `tree` contains the next `TokenTree` to be processed.
177 // We are descending into a sequence. We first make sure that the matchers in the RHS
178 // and the matches in `interp` have the same shape. Otherwise, either the caller or the
179 // macro writer has made a mistake.
180 seq @ mbe::TokenTree::Sequence(_, delimited) => {
181 match lockstep_iter_size(&seq, interp, &repeats) {
182 LockstepIterSize::Unconstrained => {
183 return Err(cx.create_err(NoSyntaxVarsExprRepeat { span: seq.span() }));
186 LockstepIterSize::Contradiction(msg) => {
187 // FIXME: this really ought to be caught at macro definition time... It
188 // happens when two meta-variables are used in the same repetition in a
189 // sequence, but they come from different sequence matchers and repeat
190 // different amounts.
191 return Err(cx.struct_span_err(seq.span(), &msg));
194 LockstepIterSize::Constraint(len, _) => {
195 // We do this to avoid an extra clone above. We know that this is a
197 let mbe::TokenTree::Sequence(sp, seq) = seq else {
201 // Is the repetition empty?
203 if seq.kleene.op == mbe::KleeneOp::OneOrMore {
204 // FIXME: this really ought to be caught at macro definition
205 // time... It happens when the Kleene operator in the matcher and
206 // the body for the same meta-variable do not match.
207 return Err(cx.create_err(MustRepeatOnce { span: sp.entire() }));
210 // 0 is the initial counter (we have done 0 repetitions so far). `len`
211 // is the total number of repetitions we should generate.
212 repeats.push((0, len));
214 // The first time we encounter the sequence we push it to the stack. It
215 // then gets reused (see the beginning of the loop) until we are done
217 stack.push(Frame::Sequence {
219 sep: seq.separator.clone(),
227 // Replace the meta-var with the matched token tree from the invocation.
228 mbe::TokenTree::MetaVar(mut sp, mut original_ident) => {
229 // Find the matched nonterminal from the macro invocation, and use it to replace
231 let ident = MacroRulesNormalizedIdent::new(original_ident);
232 if let Some(cur_matched) = lookup_cur_matched(ident, interp, &repeats) {
234 MatchedTokenTree(ref tt) => {
235 // `tt`s are emitted into the output stream directly as "raw tokens",
236 // without wrapping them into groups.
237 let token = tt.clone();
240 MatchedNonterminal(ref nt) => {
241 // Other variables are emitted into the output stream as groups with
242 // `Delimiter::Invisible` to maintain parsing priorities.
243 // `Interpolated` is currently used for such groups in rustc parser.
244 marker.visit_span(&mut sp);
245 let token = TokenTree::token_alone(token::Interpolated(nt.clone()), sp);
249 // We were unable to descend far enough. This is an error.
250 return Err(cx.struct_span_err(
251 sp, /* blame the macro writer */
252 &format!("variable '{}' is still repeating at this depth", ident),
257 // If we aren't able to match the meta-var, we push it back into the result but
258 // with modified syntax context. (I believe this supports nested macros).
259 marker.visit_span(&mut sp);
260 marker.visit_ident(&mut original_ident);
261 result.push(TokenTree::token_alone(token::Dollar, sp));
262 result.push(TokenTree::Token(
263 Token::from_ast_ident(original_ident),
269 // Replace meta-variable expressions with the result of their expansion.
270 mbe::TokenTree::MetaVarExpr(sp, expr) => {
271 transcribe_metavar_expr(cx, expr, interp, &mut marker, &repeats, &mut result, &sp)?;
274 // If we are entering a new delimiter, we push its contents to the `stack` to be
275 // processed, and we push all of the currently produced results to the `result_stack`.
276 // We will produce all of the results of the inside of the `Delimited` and then we will
277 // jump back out of the Delimited, pop the result_stack and add the new results back to
278 // the previous results (from outside the Delimited).
279 mbe::TokenTree::Delimited(mut span, delimited) => {
280 mut_visit::visit_delim_span(&mut span, &mut marker);
281 stack.push(Frame::Delimited {
283 delim: delimited.delim,
287 result_stack.push(mem::take(&mut result));
290 // Nothing much to do here. Just push the token to the result, being careful to
291 // preserve syntax context.
292 mbe::TokenTree::Token(token) => {
293 let mut token = token.clone();
294 mut_visit::visit_token(&mut token, &mut marker);
295 let tt = TokenTree::Token(token, Spacing::Alone);
299 // There should be no meta-var declarations in the invocation of a macro.
300 mbe::TokenTree::MetaVarDecl(..) => panic!("unexpected `TokenTree::MetaVarDecl"),
305 /// Lookup the meta-var named `ident` and return the matched token tree from the invocation using
306 /// the set of matches `interpolations`.
308 /// See the definition of `repeats` in the `transcribe` function. `repeats` is used to descend
309 /// into the right place in nested matchers. If we attempt to descend too far, the macro writer has
310 /// made a mistake, and we return `None`.
311 fn lookup_cur_matched<'a>(
312 ident: MacroRulesNormalizedIdent,
313 interpolations: &'a FxHashMap<MacroRulesNormalizedIdent, NamedMatch>,
314 repeats: &[(usize, usize)],
315 ) -> Option<&'a NamedMatch> {
316 interpolations.get(&ident).map(|matched| {
317 let mut matched = matched;
318 for &(idx, _) in repeats {
320 MatchedTokenTree(_) | MatchedNonterminal(_) => break,
321 MatchedSeq(ref ads) => matched = ads.get(idx).unwrap(),
329 /// An accumulator over a TokenTree to be used with `fold`. During transcription, we need to make
330 /// sure that the size of each sequence and all of its nested sequences are the same as the sizes
331 /// of all the matched (nested) sequences in the macro invocation. If they don't match, somebody
332 /// has made a mistake (either the macro writer or caller).
334 enum LockstepIterSize {
335 /// No constraints on length of matcher. This is true for any TokenTree variants except a
336 /// `MetaVar` with an actual `MatchedSeq` (as opposed to a `MatchedNonterminal`).
339 /// A `MetaVar` with an actual `MatchedSeq`. The length of the match and the name of the
340 /// meta-var are returned.
341 Constraint(usize, MacroRulesNormalizedIdent),
343 /// Two `Constraint`s on the same sequence had different lengths. This is an error.
344 Contradiction(String),
347 impl LockstepIterSize {
348 /// Find incompatibilities in matcher/invocation sizes.
349 /// - `Unconstrained` is compatible with everything.
350 /// - `Contradiction` is incompatible with everything.
351 /// - `Constraint(len)` is only compatible with other constraints of the same length.
352 fn with(self, other: LockstepIterSize) -> LockstepIterSize {
354 LockstepIterSize::Unconstrained => other,
355 LockstepIterSize::Contradiction(_) => self,
356 LockstepIterSize::Constraint(l_len, ref l_id) => match other {
357 LockstepIterSize::Unconstrained => self,
358 LockstepIterSize::Contradiction(_) => other,
359 LockstepIterSize::Constraint(r_len, _) if l_len == r_len => self,
360 LockstepIterSize::Constraint(r_len, r_id) => {
362 "meta-variable `{}` repeats {} time{}, but `{}` repeats {} time{}",
370 LockstepIterSize::Contradiction(msg)
377 /// Given a `tree`, make sure that all sequences have the same length as the matches for the
378 /// appropriate meta-vars in `interpolations`.
380 /// Note that if `repeats` does not match the exact correct depth of a meta-var,
381 /// `lookup_cur_matched` will return `None`, which is why this still works even in the presence of
382 /// multiple nested matcher sequences.
384 /// Example: `$($($x $y)+*);+` -- we need to make sure that `x` and `y` repeat the same amount as
385 /// each other at the given depth when the macro was invoked. If they don't it might mean they were
386 /// declared at unequal depths or there was a compile bug. For example, if we have 3 repetitions of
387 /// the outer sequence and 4 repetitions of the inner sequence for `x`, we should have the same for
388 /// `y`; otherwise, we can't transcribe them both at the given depth.
389 fn lockstep_iter_size(
390 tree: &mbe::TokenTree,
391 interpolations: &FxHashMap<MacroRulesNormalizedIdent, NamedMatch>,
392 repeats: &[(usize, usize)],
393 ) -> LockstepIterSize {
396 TokenTree::Delimited(_, ref delimited) => {
397 delimited.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
398 size.with(lockstep_iter_size(tt, interpolations, repeats))
401 TokenTree::Sequence(_, ref seq) => {
402 seq.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
403 size.with(lockstep_iter_size(tt, interpolations, repeats))
406 TokenTree::MetaVar(_, name) | TokenTree::MetaVarDecl(_, name, _) => {
407 let name = MacroRulesNormalizedIdent::new(name);
408 match lookup_cur_matched(name, interpolations, repeats) {
409 Some(matched) => match matched {
410 MatchedTokenTree(_) | MatchedNonterminal(_) => LockstepIterSize::Unconstrained,
411 MatchedSeq(ref ads) => LockstepIterSize::Constraint(ads.len(), name),
413 _ => LockstepIterSize::Unconstrained,
416 TokenTree::MetaVarExpr(_, ref expr) => {
417 let default_rslt = LockstepIterSize::Unconstrained;
418 let Some(ident) = expr.ident() else { return default_rslt; };
419 let name = MacroRulesNormalizedIdent::new(ident);
420 match lookup_cur_matched(name, interpolations, repeats) {
421 Some(MatchedSeq(ref ads)) => {
422 default_rslt.with(LockstepIterSize::Constraint(ads.len(), name))
427 TokenTree::Token(..) => LockstepIterSize::Unconstrained,
431 #[derive(SessionDiagnostic)]
432 #[error(expand::count_repetition_misplaced)]
433 struct CountRepetitionMisplaced {
438 /// Used solely by the `count` meta-variable expression, counts the outer-most repetitions at a
439 /// given optional nested depth.
441 /// For example, a macro parameter of `$( { $( $foo:ident ),* } )*` called with `{ a, b } { c }`:
443 /// * `[ $( ${count(foo)} ),* ]` will return [2, 1] with a, b = 2 and c = 1
444 /// * `[ $( ${count(foo, 0)} ),* ]` will be the same as `[ $( ${count(foo)} ),* ]`
445 /// * `[ $( ${count(foo, 1)} ),* ]` will return an error because `${count(foo, 1)}` is
446 /// declared inside a single repetition and the index `1` implies two nested repetitions.
447 fn count_repetitions<'a>(
449 depth_opt: Option<usize>,
450 mut matched: &NamedMatch,
451 repeats: &[(usize, usize)],
453 ) -> PResult<'a, usize> {
454 // Recursively count the number of matches in `matched` at given depth
455 // (or at the top-level of `matched` if no depth is given).
458 declared_lhs_depth: usize,
459 depth_opt: Option<usize>,
460 matched: &NamedMatch,
462 ) -> PResult<'a, usize> {
464 MatchedTokenTree(_) | MatchedNonterminal(_) => {
465 if declared_lhs_depth == 0 {
466 return Err(cx.create_err(CountRepetitionMisplaced { span: sp.entire() }));
470 Some(_) => Err(out_of_bounds_err(cx, declared_lhs_depth, sp.entire(), "count")),
473 MatchedSeq(ref named_matches) => {
474 let new_declared_lhs_depth = declared_lhs_depth + 1;
476 None => named_matches
478 .map(|elem| count(cx, new_declared_lhs_depth, None, elem, sp))
480 Some(0) => Ok(named_matches.len()),
481 Some(depth) => named_matches
483 .map(|elem| count(cx, new_declared_lhs_depth, Some(depth - 1), elem, sp))
489 // `repeats` records all of the nested levels at which we are currently
490 // matching meta-variables. The meta-var-expr `count($x)` only counts
491 // matches that occur in this "subtree" of the `NamedMatch` where we
492 // are currently transcribing, so we need to descend to that subtree
493 // before we start counting. `matched` contains the various levels of the
494 // tree as we descend, and its final value is the subtree we are currently at.
495 for &(idx, _) in repeats {
496 if let MatchedSeq(ref ads) = matched {
500 count(cx, 0, depth_opt, matched, sp)
503 /// Returns a `NamedMatch` item declared on the LHS given an arbitrary [Ident]
504 fn matched_from_ident<'ctx, 'interp, 'rslt>(
507 interp: &'interp FxHashMap<MacroRulesNormalizedIdent, NamedMatch>,
508 ) -> PResult<'ctx, &'rslt NamedMatch>
512 let span = ident.span;
513 let key = MacroRulesNormalizedIdent::new(ident);
514 interp.get(&key).ok_or_else(|| {
517 &format!("variable `{}` is not recognized in meta-variable expression", key),
522 /// Used by meta-variable expressions when an user input is out of the actual declared bounds. For
523 /// example, index(999999) in an repetition of only three elements.
524 fn out_of_bounds_err<'a>(
529 ) -> DiagnosticBuilder<'a, ErrorGuaranteed> {
530 let msg = if max == 0 {
532 "meta-variable expression `{ty}` with depth parameter \
533 must be called inside of a macro repetition"
537 "depth parameter on meta-variable expression `{ty}` \
538 must be less than {max}"
541 cx.struct_span_err(span, &msg)
544 fn transcribe_metavar_expr<'a>(
547 interp: &FxHashMap<MacroRulesNormalizedIdent, NamedMatch>,
549 repeats: &[(usize, usize)],
550 result: &mut Vec<TokenTree>,
552 ) -> PResult<'a, ()> {
553 let mut visited_span = || {
554 let mut span = sp.entire();
555 marker.visit_span(&mut span);
559 MetaVarExpr::Count(original_ident, depth_opt) => {
560 let matched = matched_from_ident(cx, original_ident, interp)?;
561 let count = count_repetitions(cx, depth_opt, matched, &repeats, sp)?;
562 let tt = TokenTree::token_alone(
563 TokenKind::lit(token::Integer, sym::integer(count), None),
568 MetaVarExpr::Ignore(original_ident) => {
569 // Used to ensure that `original_ident` is present in the LHS
570 let _ = matched_from_ident(cx, original_ident, interp)?;
572 MetaVarExpr::Index(depth) => match repeats.iter().nth_back(depth) {
573 Some((index, _)) => {
574 result.push(TokenTree::token_alone(
575 TokenKind::lit(token::Integer, sym::integer(*index), None),
579 None => return Err(out_of_bounds_err(cx, repeats.len(), sp.entire(), "index")),
581 MetaVarExpr::Length(depth) => match repeats.iter().nth_back(depth) {
582 Some((_, length)) => {
583 result.push(TokenTree::token_alone(
584 TokenKind::lit(token::Integer, sym::integer(*length), None),
588 None => return Err(out_of_bounds_err(cx, repeats.len(), sp.entire(), "length")),