1 use crate::base
::ExtCtxt
;
3 CountRepetitionMisplaced
, MetaVarExprUnrecognizedVar
, MetaVarsDifSeqMatchers
, MustRepeatOnce
,
4 NoSyntaxVarsExprRepeat
, VarStillRepeating
,
6 use crate::mbe
::macro_parser
::{MatchedNonterminal, MatchedSeq, MatchedTokenTree, NamedMatch}
;
7 use crate::mbe
::{self, MetaVarExpr}
;
8 use rustc_ast
::mut_visit
::{self, MutVisitor}
;
9 use rustc_ast
::token
::{self, Delimiter, Token, TokenKind}
;
10 use rustc_ast
::tokenstream
::{DelimSpacing, DelimSpan, Spacing, TokenStream, TokenTree}
;
11 use rustc_data_structures
::fx
::FxHashMap
;
12 use rustc_errors
::{pluralize, PResult}
;
13 use rustc_errors
::{DiagnosticBuilder, ErrorGuaranteed}
;
14 use rustc_span
::hygiene
::{LocalExpnId, Transparency}
;
15 use rustc_span
::symbol
::{sym, Ident, MacroRulesNormalizedIdent}
;
18 use smallvec
::{smallvec, SmallVec}
;
21 // A Marker adds the given mark to the syntax context.
22 struct Marker(LocalExpnId
, Transparency
);
24 impl MutVisitor
for Marker
{
25 const VISIT_TOKENS
: bool
= true;
27 fn visit_span(&mut self, span
: &mut Span
) {
28 *span
= span
.apply_mark(self.0.to_expn_id(), self.1)
32 /// An iterator over the token trees in a delimited token tree (`{ ... }`) or a sequence (`$(...)`).
35 tts
: &'a
[mbe
::TokenTree
],
39 spacing
: DelimSpacing
,
42 tts
: &'a
[mbe
::TokenTree
],
49 /// Construct a new frame around the delimited set of tokens.
50 fn new(src
: &'a mbe
::Delimited
, span
: DelimSpan
, spacing
: DelimSpacing
) -> Frame
<'a
> {
51 Frame
::Delimited { tts: &src.tts, idx: 0, delim: src.delim, span, spacing }
55 impl<'a
> Iterator
for Frame
<'a
> {
56 type Item
= &'a mbe
::TokenTree
;
58 fn next(&mut self) -> Option
<&'a mbe
::TokenTree
> {
60 Frame
::Delimited { tts, idx, .. }
| Frame
::Sequence { tts, idx, .. }
=> {
61 let res
= tts
.get(*idx
);
69 /// This can do Macro-By-Example transcription.
70 /// - `interp` is a map of meta-variables to the tokens (non-terminals) they matched in the
71 /// invocation. We are assuming we already know there is a match.
72 /// - `src` is the RHS of the MBE, that is, the "example" we are filling in.
77 /// macro_rules! foo {
78 /// ($id:ident) => { println!("{}", stringify!($id)); }
84 /// `interp` would contain `$id => bar` and `src` would contain `println!("{}", stringify!($id));`.
86 /// `transcribe` would return a `TokenStream` containing `println!("{}", stringify!(bar));`.
88 /// Along the way, we do some additional error checking.
89 pub(super) fn transcribe
<'a
>(
91 interp
: &FxHashMap
<MacroRulesNormalizedIdent
, NamedMatch
>,
94 transparency
: Transparency
,
95 ) -> PResult
<'a
, TokenStream
> {
96 // Nothing for us to transcribe...
97 if src
.tts
.is_empty() {
98 return Ok(TokenStream
::default());
101 // We descend into the RHS (`src`), expanding things as we go. This stack contains the things
102 // we have yet to expand/are still expanding. We start the stack off with the whole RHS. The
103 // choice of spacing values doesn't matter.
104 let mut stack
: SmallVec
<[Frame
<'_
>; 1]> =
105 smallvec
![Frame
::new(src
, src_span
, DelimSpacing
::new(Spacing
::Alone
, Spacing
::Alone
))];
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, mut spacing, .. }
=> {
160 // Hack to force-insert a space after `]` in certain case.
161 // See discussion of the `hex-literal` crate in #114571.
162 if delim
== Delimiter
::Bracket
{
163 spacing
.close
= Spacing
::Alone
;
165 if result_stack
.is_empty() {
166 // No results left to compute! We are back at the top-level.
167 return Ok(TokenStream
::new(result
));
170 // Step back into the parent Delimited.
171 let tree
= TokenTree
::Delimited(span
, spacing
, delim
, TokenStream
::new(result
));
172 result
= result_stack
.pop().unwrap();
179 // At this point, we know we are in the middle of a TokenTree (the last one on `stack`).
180 // `tree` contains the next `TokenTree` to be processed.
182 // We are descending into a sequence. We first make sure that the matchers in the RHS
183 // and the matches in `interp` have the same shape. Otherwise, either the caller or the
184 // macro writer has made a mistake.
185 seq @ mbe
::TokenTree
::Sequence(_
, delimited
) => {
186 match lockstep_iter_size(seq
, interp
, &repeats
) {
187 LockstepIterSize
::Unconstrained
=> {
188 return Err(cx
.create_err(NoSyntaxVarsExprRepeat { span: seq.span() }
));
191 LockstepIterSize
::Contradiction(msg
) => {
192 // FIXME: this really ought to be caught at macro definition time... It
193 // happens when two meta-variables are used in the same repetition in a
194 // sequence, but they come from different sequence matchers and repeat
195 // different amounts.
196 return Err(cx
.create_err(MetaVarsDifSeqMatchers { span: seq.span(), msg }
));
199 LockstepIterSize
::Constraint(len
, _
) => {
200 // We do this to avoid an extra clone above. We know that this is a
202 let mbe
::TokenTree
::Sequence(sp
, seq
) = seq
else { unreachable!() }
;
204 // Is the repetition empty?
206 if seq
.kleene
.op
== mbe
::KleeneOp
::OneOrMore
{
207 // FIXME: this really ought to be caught at macro definition
208 // time... It happens when the Kleene operator in the matcher and
209 // the body for the same meta-variable do not match.
210 return Err(cx
.create_err(MustRepeatOnce { span: sp.entire() }
));
213 // 0 is the initial counter (we have done 0 repetitions so far). `len`
214 // is the total number of repetitions we should generate.
215 repeats
.push((0, len
));
217 // The first time we encounter the sequence we push it to the stack. It
218 // then gets reused (see the beginning of the loop) until we are done
220 stack
.push(Frame
::Sequence
{
222 sep
: seq
.separator
.clone(),
230 // Replace the meta-var with the matched token tree from the invocation.
231 mbe
::TokenTree
::MetaVar(mut sp
, mut original_ident
) => {
232 // Find the matched nonterminal from the macro invocation, and use it to replace
234 let ident
= MacroRulesNormalizedIdent
::new(original_ident
);
235 if let Some(cur_matched
) = lookup_cur_matched(ident
, interp
, &repeats
) {
237 MatchedTokenTree(tt
) => {
238 // `tt`s are emitted into the output stream directly as "raw tokens",
239 // without wrapping them into groups.
240 result
.push(tt
.clone());
242 MatchedNonterminal(nt
) => {
243 // Other variables are emitted into the output stream as groups with
244 // `Delimiter::Invisible` to maintain parsing priorities.
245 // `Interpolated` is currently used for such groups in rustc parser.
246 marker
.visit_span(&mut sp
);
248 .push(TokenTree
::token_alone(token
::Interpolated(nt
.clone()), sp
));
251 // We were unable to descend far enough. This is an error.
252 return Err(cx
.create_err(VarStillRepeating { span: sp, ident }
));
256 // If we aren't able to match the meta-var, we push it back into the result but
257 // with modified syntax context. (I believe this supports nested macros).
258 marker
.visit_span(&mut sp
);
259 marker
.visit_ident(&mut original_ident
);
260 result
.push(TokenTree
::token_joint_hidden(token
::Dollar
, sp
));
261 result
.push(TokenTree
::Token(
262 Token
::from_ast_ident(original_ident
),
268 // Replace meta-variable expressions with the result of their expansion.
269 mbe
::TokenTree
::MetaVarExpr(sp
, expr
) => {
270 transcribe_metavar_expr(cx
, expr
, interp
, &mut marker
, &repeats
, &mut result
, sp
)?
;
273 // If we are entering a new delimiter, we push its contents to the `stack` to be
274 // processed, and we push all of the currently produced results to the `result_stack`.
275 // We will produce all of the results of the inside of the `Delimited` and then we will
276 // jump back out of the Delimited, pop the result_stack and add the new results back to
277 // the previous results (from outside the Delimited).
278 mbe
::TokenTree
::Delimited(mut span
, spacing
, delimited
) => {
279 mut_visit
::visit_delim_span(&mut span
, &mut marker
);
280 stack
.push(Frame
::Delimited
{
282 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(|mut matched
| {
317 for &(idx
, _
) in repeats
{
319 MatchedTokenTree(_
) | MatchedNonterminal(_
) => break,
320 MatchedSeq(ads
) => matched
= ads
.get(idx
).unwrap(),
328 /// An accumulator over a TokenTree to be used with `fold`. During transcription, we need to make
329 /// sure that the size of each sequence and all of its nested sequences are the same as the sizes
330 /// of all the matched (nested) sequences in the macro invocation. If they don't match, somebody
331 /// has made a mistake (either the macro writer or caller).
333 enum LockstepIterSize
{
334 /// No constraints on length of matcher. This is true for any TokenTree variants except a
335 /// `MetaVar` with an actual `MatchedSeq` (as opposed to a `MatchedNonterminal`).
338 /// A `MetaVar` with an actual `MatchedSeq`. The length of the match and the name of the
339 /// meta-var are returned.
340 Constraint(usize, MacroRulesNormalizedIdent
),
342 /// Two `Constraint`s on the same sequence had different lengths. This is an error.
343 Contradiction(String
),
346 impl LockstepIterSize
{
347 /// Find incompatibilities in matcher/invocation sizes.
348 /// - `Unconstrained` is compatible with everything.
349 /// - `Contradiction` is incompatible with everything.
350 /// - `Constraint(len)` is only compatible with other constraints of the same length.
351 fn with(self, other
: LockstepIterSize
) -> LockstepIterSize
{
353 LockstepIterSize
::Unconstrained
=> other
,
354 LockstepIterSize
::Contradiction(_
) => self,
355 LockstepIterSize
::Constraint(l_len
, l_id
) => match other
{
356 LockstepIterSize
::Unconstrained
=> self,
357 LockstepIterSize
::Contradiction(_
) => other
,
358 LockstepIterSize
::Constraint(r_len
, _
) if l_len
== r_len
=> self,
359 LockstepIterSize
::Constraint(r_len
, r_id
) => {
361 "meta-variable `{}` repeats {} time{}, but `{}` repeats {} time{}",
369 LockstepIterSize
::Contradiction(msg
)
376 /// Given a `tree`, make sure that all sequences have the same length as the matches for the
377 /// appropriate meta-vars in `interpolations`.
379 /// Note that if `repeats` does not match the exact correct depth of a meta-var,
380 /// `lookup_cur_matched` will return `None`, which is why this still works even in the presence of
381 /// multiple nested matcher sequences.
383 /// Example: `$($($x $y)+*);+` -- we need to make sure that `x` and `y` repeat the same amount as
384 /// each other at the given depth when the macro was invoked. If they don't it might mean they were
385 /// declared at depths which weren't equal or there was a compiler bug. For example, if we have 3 repetitions of
386 /// the outer sequence and 4 repetitions of the inner sequence for `x`, we should have the same for
387 /// `y`; otherwise, we can't transcribe them both at the given depth.
388 fn lockstep_iter_size(
389 tree
: &mbe
::TokenTree
,
390 interpolations
: &FxHashMap
<MacroRulesNormalizedIdent
, NamedMatch
>,
391 repeats
: &[(usize, usize)],
392 ) -> LockstepIterSize
{
395 TokenTree
::Delimited(.., delimited
) => {
396 delimited
.tts
.iter().fold(LockstepIterSize
::Unconstrained
, |size
, tt
| {
397 size
.with(lockstep_iter_size(tt
, interpolations
, repeats
))
400 TokenTree
::Sequence(_
, seq
) => {
401 seq
.tts
.iter().fold(LockstepIterSize
::Unconstrained
, |size
, tt
| {
402 size
.with(lockstep_iter_size(tt
, interpolations
, repeats
))
405 TokenTree
::MetaVar(_
, name
) | TokenTree
::MetaVarDecl(_
, name
, _
) => {
406 let name
= MacroRulesNormalizedIdent
::new(*name
);
407 match lookup_cur_matched(name
, interpolations
, repeats
) {
408 Some(matched
) => match matched
{
409 MatchedTokenTree(_
) | MatchedNonterminal(_
) => LockstepIterSize
::Unconstrained
,
410 MatchedSeq(ads
) => LockstepIterSize
::Constraint(ads
.len(), name
),
412 _
=> LockstepIterSize
::Unconstrained
,
415 TokenTree
::MetaVarExpr(_
, expr
) => {
416 let default_rslt
= LockstepIterSize
::Unconstrained
;
417 let Some(ident
) = expr
.ident() else {
420 let name
= MacroRulesNormalizedIdent
::new(ident
);
421 match lookup_cur_matched(name
, interpolations
, repeats
) {
422 Some(MatchedSeq(ads
)) => {
423 default_rslt
.with(LockstepIterSize
::Constraint(ads
.len(), name
))
428 TokenTree
::Token(..) => LockstepIterSize
::Unconstrained
,
432 /// Used solely by the `count` meta-variable expression, counts the outer-most repetitions at a
433 /// given optional nested depth.
435 /// For example, a macro parameter of `$( { $( $foo:ident ),* } )*` called with `{ a, b } { c }`:
437 /// * `[ $( ${count(foo)} ),* ]` will return [2, 1] with a, b = 2 and c = 1
438 /// * `[ $( ${count(foo, 0)} ),* ]` will be the same as `[ $( ${count(foo)} ),* ]`
439 /// * `[ $( ${count(foo, 1)} ),* ]` will return an error because `${count(foo, 1)}` is
440 /// declared inside a single repetition and the index `1` implies two nested repetitions.
441 fn count_repetitions
<'a
>(
444 mut matched
: &NamedMatch
,
445 repeats
: &[(usize, usize)],
447 ) -> PResult
<'a
, usize> {
448 // Recursively count the number of matches in `matched` at given depth
449 // (or at the top-level of `matched` if no depth is given).
454 matched
: &NamedMatch
,
456 ) -> PResult
<'a
, usize> {
458 MatchedTokenTree(_
) | MatchedNonterminal(_
) => Ok(1),
459 MatchedSeq(named_matches
) => {
460 if depth_curr
== depth_max
{
461 Ok(named_matches
.len())
465 .map(|elem
| count(cx
, depth_curr
+ 1, depth_max
, elem
, sp
))
473 fn depth(counter
: usize, matched
: &NamedMatch
) -> usize {
475 MatchedTokenTree(_
) | MatchedNonterminal(_
) => counter
,
476 MatchedSeq(named_matches
) => {
477 let rslt
= counter
+ 1;
478 if let Some(elem
) = named_matches
.first() { depth(rslt, elem) }
else { rslt }
483 let depth_max
= depth(0, matched
)
485 .and_then(|el
| el
.checked_sub(repeats
.len()))
486 .unwrap_or_default();
487 if depth_user
> depth_max
{
488 return Err(out_of_bounds_err(cx
, depth_max
+ 1, sp
.entire(), "count"));
491 // `repeats` records all of the nested levels at which we are currently
492 // matching meta-variables. The meta-var-expr `count($x)` only counts
493 // matches that occur in this "subtree" of the `NamedMatch` where we
494 // are currently transcribing, so we need to descend to that subtree
495 // before we start counting. `matched` contains the various levels of the
496 // tree as we descend, and its final value is the subtree we are currently at.
497 for &(idx
, _
) in repeats
{
498 if let MatchedSeq(ads
) = matched
{
503 if let MatchedTokenTree(_
) | MatchedNonterminal(_
) = matched
{
504 return Err(cx
.create_err(CountRepetitionMisplaced { span: sp.entire() }
));
507 count(cx
, depth_user
, depth_max
, matched
, sp
)
510 /// Returns a `NamedMatch` item declared on the LHS given an arbitrary [Ident]
511 fn matched_from_ident
<'ctx
, 'interp
, 'rslt
>(
514 interp
: &'interp FxHashMap
<MacroRulesNormalizedIdent
, NamedMatch
>,
515 ) -> PResult
<'ctx
, &'rslt NamedMatch
>
519 let span
= ident
.span
;
520 let key
= MacroRulesNormalizedIdent
::new(ident
);
521 interp
.get(&key
).ok_or_else(|| cx
.create_err(MetaVarExprUnrecognizedVar { span, key }
))
524 /// Used by meta-variable expressions when an user input is out of the actual declared bounds. For
525 /// example, index(999999) in an repetition of only three elements.
526 fn out_of_bounds_err
<'a
>(
531 ) -> DiagnosticBuilder
<'a
, ErrorGuaranteed
> {
532 let msg
= if max
== 0 {
534 "meta-variable expression `{ty}` with depth parameter \
535 must be called inside of a macro repetition"
539 "depth parameter of meta-variable expression `{ty}` \
540 must be less than {max}"
543 cx
.struct_span_err(span
, msg
)
546 fn transcribe_metavar_expr
<'a
>(
549 interp
: &FxHashMap
<MacroRulesNormalizedIdent
, NamedMatch
>,
551 repeats
: &[(usize, usize)],
552 result
: &mut Vec
<TokenTree
>,
554 ) -> PResult
<'a
, ()> {
555 let mut visited_span
= || {
556 let mut span
= sp
.entire();
557 marker
.visit_span(&mut span
);
561 MetaVarExpr
::Count(original_ident
, depth
) => {
562 let matched
= matched_from_ident(cx
, original_ident
, interp
)?
;
563 let count
= count_repetitions(cx
, depth
, matched
, repeats
, sp
)?
;
564 let tt
= TokenTree
::token_alone(
565 TokenKind
::lit(token
::Integer
, sym
::integer(count
), None
),
570 MetaVarExpr
::Ignore(original_ident
) => {
571 // Used to ensure that `original_ident` is present in the LHS
572 let _
= matched_from_ident(cx
, original_ident
, interp
)?
;
574 MetaVarExpr
::Index(depth
) => match repeats
.iter().nth_back(depth
) {
575 Some((index
, _
)) => {
576 result
.push(TokenTree
::token_alone(
577 TokenKind
::lit(token
::Integer
, sym
::integer(*index
), None
),
581 None
=> return Err(out_of_bounds_err(cx
, repeats
.len(), sp
.entire(), "index")),
583 MetaVarExpr
::Length(depth
) => match repeats
.iter().nth_back(depth
) {
584 Some((_
, length
)) => {
585 result
.push(TokenTree
::token_alone(
586 TokenKind
::lit(token
::Integer
, sym
::integer(*length
), None
),
590 None
=> return Err(out_of_bounds_err(cx
, repeats
.len(), sp
.entire(), "length")),