1 use crate::base::ExtCtxt;
3 use crate::mbe::macro_parser::{MatchedNonterminal, MatchedSeq, NamedMatch};
5 use rustc_data_structures::fx::FxHashMap;
6 use rustc_data_structures::sync::Lrc;
7 use rustc_errors::pluralize;
8 use rustc_span::hygiene::{ExpnId, Transparency};
10 use syntax::ast::{Ident, Mac};
11 use syntax::mut_visit::{self, MutVisitor};
12 use syntax::token::{self, NtTT, Token};
13 use syntax::tokenstream::{DelimSpan, TokenStream, TokenTree, TreeAndJoint};
15 use smallvec::{smallvec, SmallVec};
18 // A Marker adds the given mark to the syntax context.
19 struct Marker(ExpnId, Transparency);
21 impl MutVisitor for Marker {
22 fn visit_span(&mut self, span: &mut Span) {
23 *span = span.apply_mark(self.0, self.1)
26 fn visit_mac(&mut self, mac: &mut Mac) {
27 mut_visit::noop_visit_mac(mac, self)
31 /// An iterator over the token trees in a delimited token tree (`{ ... }`) or a sequence (`$(...)`).
33 Delimited { forest: Lrc<mbe::Delimited>, idx: usize, span: DelimSpan },
34 Sequence { forest: Lrc<mbe::SequenceRepetition>, idx: usize, sep: Option<Token> },
38 /// Construct a new frame around the delimited set of tokens.
39 fn new(tts: Vec<mbe::TokenTree>) -> Frame {
40 let forest = Lrc::new(mbe::Delimited { delim: token::NoDelim, tts });
41 Frame::Delimited { forest, idx: 0, span: DelimSpan::dummy() }
45 impl Iterator for Frame {
46 type Item = mbe::TokenTree;
48 fn next(&mut self) -> Option<mbe::TokenTree> {
50 Frame::Delimited { ref forest, ref mut idx, .. } => {
52 forest.tts.get(*idx - 1).cloned()
54 Frame::Sequence { ref forest, ref mut idx, .. } => {
56 forest.tts.get(*idx - 1).cloned()
62 /// This can do Macro-By-Example transcription.
63 /// - `interp` is a map of meta-variables to the tokens (non-terminals) they matched in the
64 /// invocation. We are assuming we already know there is a match.
65 /// - `src` is the RHS of the MBE, that is, the "example" we are filling in.
70 /// macro_rules! foo {
71 /// ($id:ident) => { println!("{}", stringify!($id)); }
77 /// `interp` would contain `$id => bar` and `src` would contain `println!("{}", stringify!($id));`.
79 /// `transcribe` would return a `TokenStream` containing `println!("{}", stringify!(bar));`.
81 /// Along the way, we do some additional error checking.
82 pub(super) fn transcribe(
84 interp: &FxHashMap<Ident, NamedMatch>,
85 src: Vec<mbe::TokenTree>,
86 transparency: Transparency,
88 // Nothing for us to transcribe...
90 return TokenStream::default();
93 // We descend into the RHS (`src`), expanding things as we go. This stack contains the things
94 // we have yet to expand/are still expanding. We start the stack off with the whole RHS.
95 let mut stack: SmallVec<[Frame; 1]> = smallvec![Frame::new(src)];
97 // As we descend in the RHS, we will need to be able to match nested sequences of matchers.
98 // `repeats` keeps track of where we are in matching at each level, with the last element being
99 // the most deeply nested sequence. This is used as a stack.
100 let mut repeats = Vec::new();
102 // `result` contains resulting token stream from the TokenTree we just finished processing. At
103 // the end, this will contain the full result of transcription, but at arbitrary points during
104 // `transcribe`, `result` will contain subsets of the final result.
106 // Specifically, as we descend into each TokenTree, we will push the existing results onto the
107 // `result_stack` and clear `results`. We will then produce the results of transcribing the
108 // TokenTree into `results`. Then, as we unwind back out of the `TokenTree`, we will pop the
109 // `result_stack` and append `results` too it to produce the new `results` up to that point.
111 // Thus, if we try to pop the `result_stack` and it is empty, we have reached the top-level
112 // again, and we are done transcribing.
113 let mut result: Vec<TreeAndJoint> = Vec::new();
114 let mut result_stack = Vec::new();
115 let mut marker = Marker(cx.current_expansion.id, transparency);
118 // Look at the last frame on the stack.
119 let tree = if let Some(tree) = stack.last_mut().unwrap().next() {
120 // If it still has a TokenTree we have not looked at yet, use that tree.
123 // The else-case never produces a value for `tree` (it `continue`s or `return`s).
125 // Otherwise, if we have just reached the end of a sequence and we can keep repeating,
126 // go back to the beginning of the sequence.
127 if let Frame::Sequence { idx, sep, .. } = stack.last_mut().unwrap() {
128 let (repeat_idx, repeat_len) = repeats.last_mut().unwrap();
130 if repeat_idx < repeat_len {
132 if let Some(sep) = sep {
133 result.push(TokenTree::Token(sep.clone()).into());
139 // We are done with the top of the stack. Pop it. Depending on what it was, we do
140 // different things. Note that the outermost item must be the delimited, wrapped RHS
141 // that was passed in originally to `transcribe`.
142 match stack.pop().unwrap() {
143 // Done with a sequence. Pop from repeats.
144 Frame::Sequence { .. } => {
148 // We are done processing a Delimited. If this is the top-level delimited, we are
149 // done. Otherwise, we unwind the result_stack to append what we have produced to
150 // any previous results.
151 Frame::Delimited { forest, span, .. } => {
152 if result_stack.is_empty() {
153 // No results left to compute! We are back at the top-level.
154 return TokenStream::new(result);
157 // Step back into the parent Delimited.
159 TokenTree::Delimited(span, forest.delim, TokenStream::new(result).into());
160 result = result_stack.pop().unwrap();
161 result.push(tree.into());
167 // At this point, we know we are in the middle of a TokenTree (the last one on `stack`).
168 // `tree` contains the next `TokenTree` to be processed.
170 // We are descending into a sequence. We first make sure that the matchers in the RHS
171 // and the matches in `interp` have the same shape. Otherwise, either the caller or the
172 // macro writer has made a mistake.
173 seq @ mbe::TokenTree::Sequence(..) => {
174 match lockstep_iter_size(&seq, interp, &repeats) {
175 LockstepIterSize::Unconstrained => {
177 seq.span(), /* blame macro writer */
178 "attempted to repeat an expression containing no syntax variables \
179 matched as repeating at this depth",
183 LockstepIterSize::Contradiction(ref msg) => {
184 // FIXME: this really ought to be caught at macro definition time... It
185 // happens when two meta-variables are used in the same repetition in a
186 // sequence, but they come from different sequence matchers and repeat
187 // different amounts.
188 cx.span_fatal(seq.span(), &msg[..]);
191 LockstepIterSize::Constraint(len, _) => {
192 // We do this to avoid an extra clone above. We know that this is a
194 let (sp, seq) = if let mbe::TokenTree::Sequence(sp, seq) = seq {
200 // Is the repetition empty?
202 if seq.kleene.op == mbe::KleeneOp::OneOrMore {
203 // FIXME: this really ought to be caught at macro definition
204 // time... It happens when the Kleene operator in the matcher and
205 // the body for the same meta-variable do not match.
206 cx.span_fatal(sp.entire(), "this must repeat at least once");
209 // 0 is the initial counter (we have done 0 repretitions so far). `len`
210 // is the total number of reptitions we should generate.
211 repeats.push((0, len));
213 // The first time we encounter the sequence we push it to the stack. It
214 // then gets reused (see the beginning of the loop) until we are done
216 stack.push(Frame::Sequence {
218 sep: seq.separator.clone(),
226 // Replace the meta-var with the matched token tree from the invocation.
227 mbe::TokenTree::MetaVar(mut sp, mut ident) => {
228 // Find the matched nonterminal from the macro invocation, and use it to replace
230 if let Some(cur_matched) = lookup_cur_matched(ident, interp, &repeats) {
231 if let MatchedNonterminal(ref nt) = cur_matched {
232 // FIXME #2887: why do we apply a mark when matching a token tree meta-var
233 // (e.g. `$x:tt`), but not when we are matching any other type of token
235 if let NtTT(ref tt) = **nt {
236 result.push(tt.clone().into());
238 marker.visit_span(&mut sp);
239 let token = TokenTree::token(token::Interpolated(nt.clone()), sp);
240 result.push(token.into());
243 // We were unable to descend far enough. This is an error.
245 sp, /* blame the macro writer */
246 &format!("variable '{}' is still repeating at this depth", ident),
250 // If we aren't able to match the meta-var, we push it back into the result but
251 // with modified syntax context. (I believe this supports nested macros).
252 marker.visit_span(&mut sp);
253 marker.visit_ident(&mut ident);
254 result.push(TokenTree::token(token::Dollar, sp).into());
255 result.push(TokenTree::Token(Token::from_ast_ident(ident)).into());
259 // If we are entering a new delimiter, we push its contents to the `stack` to be
260 // processed, and we push all of the currently produced results to the `result_stack`.
261 // We will produce all of the results of the inside of the `Delimited` and then we will
262 // jump back out of the Delimited, pop the result_stack and add the new results back to
263 // the previous results (from outside the Delimited).
264 mbe::TokenTree::Delimited(mut span, delimited) => {
265 mut_visit::visit_delim_span(&mut span, &mut marker);
266 stack.push(Frame::Delimited { forest: delimited, idx: 0, span });
267 result_stack.push(mem::take(&mut result));
270 // Nothing much to do here. Just push the token to the result, being careful to
271 // preserve syntax context.
272 mbe::TokenTree::Token(token) => {
273 let mut tt = TokenTree::Token(token);
274 marker.visit_tt(&mut tt);
275 result.push(tt.into());
278 // There should be no meta-var declarations in the invocation of a macro.
279 mbe::TokenTree::MetaVarDecl(..) => panic!("unexpected `TokenTree::MetaVarDecl"),
284 /// Lookup the meta-var named `ident` and return the matched token tree from the invocation using
285 /// the set of matches `interpolations`.
287 /// See the definition of `repeats` in the `transcribe` function. `repeats` is used to descend
288 /// into the right place in nested matchers. If we attempt to descend too far, the macro writer has
289 /// made a mistake, and we return `None`.
290 fn lookup_cur_matched<'a>(
292 interpolations: &'a FxHashMap<Ident, NamedMatch>,
293 repeats: &[(usize, usize)],
294 ) -> Option<&'a NamedMatch> {
295 interpolations.get(&ident).map(|matched| {
296 let mut matched = matched;
297 for &(idx, _) in repeats {
299 MatchedNonterminal(_) => break,
300 MatchedSeq(ref ads) => matched = ads.get(idx).unwrap(),
308 /// An accumulator over a TokenTree to be used with `fold`. During transcription, we need to make
309 /// sure that the size of each sequence and all of its nested sequences are the same as the sizes
310 /// of all the matched (nested) sequences in the macro invocation. If they don't match, somebody
311 /// has made a mistake (either the macro writer or caller).
313 enum LockstepIterSize {
314 /// No constraints on length of matcher. This is true for any TokenTree variants except a
315 /// `MetaVar` with an actual `MatchedSeq` (as opposed to a `MatchedNonterminal`).
318 /// A `MetaVar` with an actual `MatchedSeq`. The length of the match and the name of the
319 /// meta-var are returned.
320 Constraint(usize, Ident),
322 /// Two `Constraint`s on the same sequence had different lengths. This is an error.
323 Contradiction(String),
326 impl LockstepIterSize {
327 /// Find incompatibilities in matcher/invocation sizes.
328 /// - `Unconstrained` is compatible with everything.
329 /// - `Contradiction` is incompatible with everything.
330 /// - `Constraint(len)` is only compatible with other constraints of the same length.
331 fn with(self, other: LockstepIterSize) -> LockstepIterSize {
333 LockstepIterSize::Unconstrained => other,
334 LockstepIterSize::Contradiction(_) => self,
335 LockstepIterSize::Constraint(l_len, ref l_id) => match other {
336 LockstepIterSize::Unconstrained => self,
337 LockstepIterSize::Contradiction(_) => other,
338 LockstepIterSize::Constraint(r_len, _) if l_len == r_len => self,
339 LockstepIterSize::Constraint(r_len, r_id) => {
341 "meta-variable `{}` repeats {} time{}, but `{}` repeats {} time{}",
349 LockstepIterSize::Contradiction(msg)
356 /// Given a `tree`, make sure that all sequences have the same length as the matches for the
357 /// appropriate meta-vars in `interpolations`.
359 /// Note that if `repeats` does not match the exact correct depth of a meta-var,
360 /// `lookup_cur_matched` will return `None`, which is why this still works even in the presnece of
361 /// multiple nested matcher sequences.
362 fn lockstep_iter_size(
363 tree: &mbe::TokenTree,
364 interpolations: &FxHashMap<Ident, NamedMatch>,
365 repeats: &[(usize, usize)],
366 ) -> LockstepIterSize {
369 TokenTree::Delimited(_, ref delimed) => {
370 delimed.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
371 size.with(lockstep_iter_size(tt, interpolations, repeats))
374 TokenTree::Sequence(_, ref seq) => {
375 seq.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
376 size.with(lockstep_iter_size(tt, interpolations, repeats))
379 TokenTree::MetaVar(_, name) | TokenTree::MetaVarDecl(_, name, _) => {
380 match lookup_cur_matched(name, interpolations, repeats) {
381 Some(matched) => match matched {
382 MatchedNonterminal(_) => LockstepIterSize::Unconstrained,
383 MatchedSeq(ref ads) => LockstepIterSize::Constraint(ads.len(), name),
385 _ => LockstepIterSize::Unconstrained,
388 TokenTree::Token(..) => LockstepIterSize::Unconstrained,