mbe/expander/
transcriber.rs

1//! Transcriber takes a template, like `fn $ident() {}`, a set of bindings like
2//! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}`
3
4use intern::{Symbol, sym};
5use span::{Edition, Span};
6use tt::{Delimiter, TopSubtreeBuilder, iter::TtElement};
7
8use crate::{
9    ExpandError, ExpandErrorKind, ExpandResult, MetaTemplate,
10    expander::{Binding, Bindings, Fragment},
11    parser::{ConcatMetaVarExprElem, MetaVarKind, Op, RepeatKind, Separator},
12};
13
14impl<'t> Bindings<'t> {
15    fn get(&self, name: &Symbol, span: Span) -> Result<&Binding<'t>, ExpandError> {
16        match self.inner.get(name) {
17            Some(binding) => Ok(binding),
18            None => Err(ExpandError::new(
19                span,
20                ExpandErrorKind::UnresolvedBinding(Box::new(Box::from(name.as_str()))),
21            )),
22        }
23    }
24
25    fn get_fragment(
26        &self,
27        name: &Symbol,
28        mut span: Span,
29        nesting: &mut [NestingState],
30        marker: impl Fn(&mut Span),
31    ) -> Result<Fragment<'t>, ExpandError> {
32        macro_rules! binding_err {
33            ($($arg:tt)*) => { ExpandError::binding_error(span, format!($($arg)*)) };
34        }
35
36        let mut b = self.get(name, span)?;
37        for nesting_state in nesting.iter_mut() {
38            nesting_state.hit = true;
39            b = match b {
40                Binding::Fragment(_) => break,
41                Binding::Missing(_) => {
42                    nesting_state.at_end = true;
43                    break;
44                }
45                Binding::Nested(bs) => bs.get(nesting_state.idx).ok_or_else(|| {
46                    nesting_state.at_end = true;
47                    binding_err!("could not find nested binding `{name}`")
48                })?,
49                Binding::Empty => {
50                    nesting_state.at_end = true;
51                    return Err(binding_err!("could not find empty binding `{name}`"));
52                }
53            };
54        }
55        match b {
56            Binding::Fragment(f) => Ok(f.clone()),
57            // emit some reasonable default expansion for missing bindings,
58            // this gives better recovery than emitting the `$fragment-name` verbatim
59            Binding::Missing(it) => Ok({
60                marker(&mut span);
61                let mut builder = TopSubtreeBuilder::new(tt::Delimiter::invisible_spanned(span));
62                match it {
63                    MetaVarKind::Stmt => {
64                        builder.push(tt::Leaf::Punct(tt::Punct {
65                            span,
66                            char: ';',
67                            spacing: tt::Spacing::Alone,
68                        }));
69                    }
70                    MetaVarKind::Block => {
71                        builder.open(tt::DelimiterKind::Brace, span);
72                        builder.close(span);
73                    }
74                    // FIXME: Meta and Item should get proper defaults
75                    MetaVarKind::Meta | MetaVarKind::Item | MetaVarKind::Tt | MetaVarKind::Vis => {}
76                    MetaVarKind::Path
77                    | MetaVarKind::Ty
78                    | MetaVarKind::Pat
79                    | MetaVarKind::PatParam
80                    | MetaVarKind::Expr(_)
81                    | MetaVarKind::Ident => {
82                        builder.push(tt::Leaf::Ident(tt::Ident {
83                            sym: sym::missing,
84                            span,
85                            is_raw: tt::IdentIsRaw::No,
86                        }));
87                    }
88                    MetaVarKind::Lifetime => {
89                        builder.extend([
90                            tt::Leaf::Punct(tt::Punct {
91                                char: '\'',
92                                span,
93                                spacing: tt::Spacing::Joint,
94                            }),
95                            tt::Leaf::Ident(tt::Ident {
96                                sym: sym::missing,
97                                span,
98                                is_raw: tt::IdentIsRaw::No,
99                            }),
100                        ]);
101                    }
102                    MetaVarKind::Literal => {
103                        builder.push(tt::Leaf::Ident(tt::Ident {
104                            sym: sym::missing,
105                            span,
106                            is_raw: tt::IdentIsRaw::No,
107                        }));
108                    }
109                }
110                Fragment::TokensOwned(builder.build())
111            }),
112            Binding::Nested(_) => {
113                Err(binding_err!("expected simple binding, found nested binding `{name}`"))
114            }
115            Binding::Empty => {
116                Err(binding_err!("expected simple binding, found empty binding `{name}`"))
117            }
118        }
119    }
120}
121
122pub(super) fn transcribe(
123    template: &MetaTemplate,
124    bindings: &Bindings<'_>,
125    marker: impl Fn(&mut Span) + Copy,
126    call_site: Span,
127) -> ExpandResult<tt::TopSubtree<Span>> {
128    let mut ctx = ExpandCtx { bindings, nesting: Vec::new(), call_site };
129    let mut builder = tt::TopSubtreeBuilder::new(tt::Delimiter::invisible_spanned(ctx.call_site));
130    expand_subtree(&mut ctx, template, &mut builder, marker).map(|()| builder.build())
131}
132
133#[derive(Debug)]
134struct NestingState {
135    idx: usize,
136    /// `hit` is currently necessary to tell `expand_repeat` if it should stop
137    /// because there is no variable in use by the current repetition
138    hit: bool,
139    /// `at_end` is currently necessary to tell `expand_repeat` if it should stop
140    /// because there is no more value available for the current repetition
141    at_end: bool,
142}
143
144#[derive(Debug)]
145struct ExpandCtx<'a> {
146    bindings: &'a Bindings<'a>,
147    nesting: Vec<NestingState>,
148    call_site: Span,
149}
150
151fn expand_subtree_with_delimiter(
152    ctx: &mut ExpandCtx<'_>,
153    template: &MetaTemplate,
154    builder: &mut tt::TopSubtreeBuilder<Span>,
155    delimiter: Option<Delimiter<Span>>,
156    marker: impl Fn(&mut Span) + Copy,
157) -> ExpandResult<()> {
158    let delimiter = delimiter.unwrap_or_else(|| tt::Delimiter::invisible_spanned(ctx.call_site));
159    builder.open(delimiter.kind, delimiter.open);
160    let result = expand_subtree(ctx, template, builder, marker);
161    builder.close(delimiter.close);
162    result
163}
164
165fn expand_subtree(
166    ctx: &mut ExpandCtx<'_>,
167    template: &MetaTemplate,
168    builder: &mut tt::TopSubtreeBuilder<Span>,
169    marker: impl Fn(&mut Span) + Copy,
170) -> ExpandResult<()> {
171    let mut err = None;
172    'ops: for op in template.iter() {
173        match op {
174            Op::Literal(it) => builder.push(tt::Leaf::from({
175                let mut it = it.clone();
176                marker(&mut it.span);
177                it
178            })),
179            Op::Ident(it) => builder.push(tt::Leaf::from({
180                let mut it = it.clone();
181                marker(&mut it.span);
182                it
183            })),
184            Op::Punct(puncts) => {
185                builder.extend(puncts.iter().map(|punct| {
186                    tt::Leaf::from({
187                        let mut it = *punct;
188                        marker(&mut it.span);
189                        it
190                    })
191                }));
192            }
193            Op::Subtree { tokens, delimiter } => {
194                let mut delimiter = *delimiter;
195                marker(&mut delimiter.open);
196                marker(&mut delimiter.close);
197                let ExpandResult { value: (), err: e } =
198                    expand_subtree_with_delimiter(ctx, tokens, builder, Some(delimiter), marker);
199                err = err.or(e);
200            }
201            Op::Var { name, id, .. } => {
202                let ExpandResult { value: (), err: e } =
203                    expand_var(ctx, name, *id, builder, marker);
204                err = err.or(e);
205            }
206            Op::Repeat { tokens: subtree, kind, separator } => {
207                let ExpandResult { value: (), err: e } =
208                    expand_repeat(ctx, subtree, *kind, separator.as_deref(), builder, marker);
209                err = err.or(e);
210            }
211            Op::Ignore { name, id } => {
212                // Expand the variable, but ignore the result. This registers the repetition count.
213                let e = ctx.bindings.get_fragment(name, *id, &mut ctx.nesting, marker).err();
214                // FIXME: The error gets dropped if there were any previous errors.
215                // This should be reworked in a way where the errors can be combined
216                // and reported rather than storing the first error encountered.
217                err = err.or(e);
218            }
219            Op::Index { depth } => {
220                let index =
221                    ctx.nesting.get(ctx.nesting.len() - 1 - depth).map_or(0, |nest| nest.idx);
222                builder.push(tt::Leaf::Literal(tt::Literal {
223                    symbol: Symbol::integer(index),
224                    span: ctx.call_site,
225                    kind: tt::LitKind::Integer,
226                    suffix: None,
227                }));
228            }
229            Op::Len { depth } => {
230                let length = ctx.nesting.get(ctx.nesting.len() - 1 - depth).map_or(0, |_nest| {
231                    // FIXME: to be implemented
232                    0
233                });
234                builder.push(tt::Leaf::Literal(tt::Literal {
235                    symbol: Symbol::integer(length),
236                    span: ctx.call_site,
237                    kind: tt::LitKind::Integer,
238                    suffix: None,
239                }));
240            }
241            Op::Count { name, depth } => {
242                let mut binding = match ctx.bindings.get(name, ctx.call_site) {
243                    Ok(b) => b,
244                    Err(e) => {
245                        err = err.or(Some(e));
246                        continue;
247                    }
248                };
249                for state in ctx.nesting.iter_mut() {
250                    state.hit = true;
251                    match binding {
252                        Binding::Fragment(_) | Binding::Missing(_) => {
253                            // `count()` will report an error.
254                            break;
255                        }
256                        Binding::Nested(bs) => {
257                            if let Some(b) = bs.get(state.idx) {
258                                binding = b;
259                            } else {
260                                state.at_end = true;
261                                continue 'ops;
262                            }
263                        }
264                        Binding::Empty => {
265                            state.at_end = true;
266                            // FIXME: Breaking here and proceeding to `count()` isn't the most
267                            // correct thing to do here. This could be a binding of some named
268                            // fragment which we don't know the depth of, so `count()` will just
269                            // return 0 for this no matter what `depth` is. See test
270                            // `count_interaction_with_empty_binding` for example.
271                            break;
272                        }
273                    }
274                }
275
276                let res = count(binding, 0, depth.unwrap_or(0));
277
278                builder.push(tt::Leaf::Literal(tt::Literal {
279                    symbol: Symbol::integer(res),
280                    span: ctx.call_site,
281                    suffix: None,
282                    kind: tt::LitKind::Integer,
283                }));
284            }
285            Op::Concat { elements, span: concat_span } => {
286                let mut concatenated = String::new();
287                for element in elements {
288                    match element {
289                        ConcatMetaVarExprElem::Ident(ident) => {
290                            concatenated.push_str(ident.sym.as_str())
291                        }
292                        ConcatMetaVarExprElem::Literal(lit) => {
293                            // FIXME: This isn't really correct wrt. escaping, but that's what rustc does and anyway
294                            // escaping is used most of the times for characters that are invalid in identifiers.
295                            concatenated.push_str(lit.symbol.as_str())
296                        }
297                        ConcatMetaVarExprElem::Var(var) => {
298                            // Handling of repetitions in `${concat}` isn't fleshed out in rustc, so we currently
299                            // err at it.
300                            // FIXME: Do what rustc does for repetitions.
301                            let var_value = match ctx.bindings.get_fragment(
302                                &var.sym,
303                                var.span,
304                                &mut ctx.nesting,
305                                marker,
306                            ) {
307                                Ok(var) => var,
308                                Err(e) => {
309                                    if err.is_none() {
310                                        err = Some(e);
311                                    };
312                                    continue;
313                                }
314                            };
315                            let values = match &var_value {
316                                Fragment::Tokens(tokens) => {
317                                    let mut iter = tokens.iter();
318                                    (iter.next(), iter.next())
319                                }
320                                Fragment::TokensOwned(tokens) => {
321                                    let mut iter = tokens.iter();
322                                    (iter.next(), iter.next())
323                                }
324                                _ => (None, None),
325                            };
326                            let value = match values {
327                                (Some(TtElement::Leaf(tt::Leaf::Ident(ident))), None) => {
328                                    ident.sym.as_str()
329                                }
330                                (Some(TtElement::Leaf(tt::Leaf::Literal(lit))), None) => {
331                                    lit.symbol.as_str()
332                                }
333                                _ => {
334                                    if err.is_none() {
335                                        err = Some(ExpandError::binding_error(
336                                            var.span,
337                                            "metavariables of `${concat(..)}` must be of type `ident`, `literal` or `tt`",
338                                        ))
339                                    }
340                                    continue;
341                                }
342                            };
343                            concatenated.push_str(value);
344                        }
345                    }
346                }
347
348                // `${concat}` span comes from the macro (at least for now).
349                // See https://github.com/rust-lang/rust/blob/b0af276da341/compiler/rustc_expand/src/mbe/transcribe.rs#L724-L726.
350                let mut result_span = *concat_span;
351                marker(&mut result_span);
352
353                // FIXME: NFC normalize the result.
354                if !rustc_lexer::is_ident(&concatenated) {
355                    if err.is_none() {
356                        err = Some(ExpandError::binding_error(
357                            *concat_span,
358                            "`${concat(..)}` is not generating a valid identifier",
359                        ));
360                    }
361                    // Insert a dummy identifier for better parsing.
362                    concatenated.clear();
363                    concatenated.push_str("__ra_concat_dummy");
364                }
365
366                let needs_raw =
367                    parser::SyntaxKind::from_keyword(&concatenated, Edition::LATEST).is_some();
368                let is_raw = if needs_raw { tt::IdentIsRaw::Yes } else { tt::IdentIsRaw::No };
369                builder.push(tt::Leaf::Ident(tt::Ident {
370                    is_raw,
371                    span: result_span,
372                    sym: Symbol::intern(&concatenated),
373                }));
374            }
375        }
376    }
377    ExpandResult { value: (), err }
378}
379
380fn expand_var(
381    ctx: &mut ExpandCtx<'_>,
382    v: &Symbol,
383    id: Span,
384    builder: &mut tt::TopSubtreeBuilder<Span>,
385    marker: impl Fn(&mut Span) + Copy,
386) -> ExpandResult<()> {
387    // We already handle $crate case in mbe parser
388    debug_assert!(*v != sym::crate_);
389
390    match ctx.bindings.get_fragment(v, id, &mut ctx.nesting, marker) {
391        Ok(fragment) => {
392            match fragment {
393                // rustc spacing is not like ours. Ours is like proc macros', it dictates how puncts will actually be joined.
394                // rustc uses them mostly for pretty printing. So we have to deviate a bit from what rustc does here.
395                // Basically, a metavariable can never be joined with whatever after it.
396                Fragment::Tokens(tt) => builder.extend_with_tt_alone(tt.strip_invisible()),
397                Fragment::TokensOwned(tt) => {
398                    builder.extend_with_tt_alone(tt.view().strip_invisible())
399                }
400                Fragment::Expr(sub) => {
401                    let sub = sub.strip_invisible();
402                    let mut span = id;
403                    marker(&mut span);
404
405                    // Check if this is a simple negative literal (MINUS + LITERAL)
406                    // that should not be wrapped in parentheses
407                    let is_negative_literal = matches!(
408                        sub.flat_tokens(),
409                        [
410                            tt::TokenTree::Leaf(tt::Leaf::Punct(tt::Punct { char: '-', .. })),
411                            tt::TokenTree::Leaf(tt::Leaf::Literal(_))
412                        ]
413                    );
414
415                    let wrap_in_parens = !is_negative_literal
416                        && !matches!(sub.flat_tokens(), [tt::TokenTree::Leaf(_)])
417                        && sub.try_into_subtree().is_none_or(|it| {
418                            it.top_subtree().delimiter.kind == tt::DelimiterKind::Invisible
419                        });
420                    if wrap_in_parens {
421                        builder.open(tt::DelimiterKind::Parenthesis, span);
422                    }
423                    builder.extend_with_tt_alone(sub);
424                    if wrap_in_parens {
425                        builder.close(span);
426                    }
427                }
428                Fragment::Path(tt) => fix_up_and_push_path_tt(ctx, builder, tt),
429                Fragment::Empty => (),
430            };
431            ExpandResult::ok(())
432        }
433        Err(e) if matches!(e.inner.1, ExpandErrorKind::UnresolvedBinding(_)) => {
434            // Note that it is possible to have a `$var` inside a macro which is not bound.
435            // For example:
436            // ```
437            // macro_rules! foo {
438            //     ($a:ident, $b:ident, $c:tt) => {
439            //         macro_rules! bar {
440            //             ($bi:ident) => {
441            //                 fn $bi() -> u8 {$c}
442            //             }
443            //         }
444            //     }
445            // ```
446            // We just treat it a normal tokens
447            builder.extend([
448                tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone, span: id }),
449                tt::Leaf::from(tt::Ident { sym: v.clone(), span: id, is_raw: tt::IdentIsRaw::No }),
450            ]);
451            ExpandResult::ok(())
452        }
453        Err(e) => ExpandResult::only_err(e),
454    }
455}
456
457fn expand_repeat(
458    ctx: &mut ExpandCtx<'_>,
459    template: &MetaTemplate,
460    kind: RepeatKind,
461    separator: Option<&Separator>,
462    builder: &mut tt::TopSubtreeBuilder<Span>,
463    marker: impl Fn(&mut Span) + Copy,
464) -> ExpandResult<()> {
465    ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
466    // Dirty hack to make macro-expansion terminate.
467    // This should be replaced by a proper macro-by-example implementation
468    let limit = 65536;
469    let mut counter = 0;
470    let mut err = None;
471
472    let initial_restore_point = builder.restore_point();
473    let mut restore_point = builder.restore_point();
474    loop {
475        let ExpandResult { value: (), err: e } =
476            expand_subtree_with_delimiter(ctx, template, builder, None, marker);
477        let nesting_state = ctx.nesting.last_mut().unwrap();
478        if nesting_state.at_end || !nesting_state.hit {
479            break;
480        }
481        nesting_state.idx += 1;
482        nesting_state.hit = false;
483
484        builder.remove_last_subtree_if_invisible();
485
486        restore_point = builder.restore_point();
487
488        counter += 1;
489        if counter == limit {
490            // FIXME: This is a bug here, we get here when we shouldn't, see https://github.com/rust-lang/rust-analyzer/issues/18910.
491            // If we don't restore we emit a lot of nodes which causes a stack overflow down the road. For now just ignore them,
492            // there is always an error here anyway.
493            builder.restore(initial_restore_point);
494            err = Some(ExpandError::new(ctx.call_site, ExpandErrorKind::LimitExceeded));
495            break;
496        }
497
498        if e.is_some() {
499            err = err.or(e);
500            continue;
501        }
502
503        if let Some(sep) = separator {
504            match sep {
505                Separator::Ident(ident) => builder.push(tt::Leaf::from(ident.clone())),
506                Separator::Literal(lit) => builder.push(tt::Leaf::from(lit.clone())),
507                Separator::Puncts(puncts) => {
508                    for &punct in puncts {
509                        builder.push(tt::Leaf::from(punct));
510                    }
511                }
512                Separator::Lifetime(punct, ident) => {
513                    builder.push(tt::Leaf::from(*punct));
514                    builder.push(tt::Leaf::from(ident.clone()));
515                }
516            };
517        }
518
519        if RepeatKind::ZeroOrOne == kind {
520            break;
521        }
522    }
523    // Lose the last separator and last after-the-end round.
524    builder.restore(restore_point);
525
526    ctx.nesting.pop().unwrap();
527
528    // Check if it is a single token subtree without any delimiter
529    // e.g {Delimiter:None> ['>'] /Delimiter:None>}
530
531    if RepeatKind::OneOrMore == kind && counter == 0 && err.is_none() {
532        err = Some(ExpandError::new(ctx.call_site, ExpandErrorKind::UnexpectedToken));
533    }
534    ExpandResult { value: (), err }
535}
536
537/// Inserts the path separator `::` between an identifier and its following generic
538/// argument list, and then pushes into the buffer. See [`Fragment::Path`] for why
539/// we need this fixup.
540fn fix_up_and_push_path_tt(
541    ctx: &ExpandCtx<'_>,
542    builder: &mut tt::TopSubtreeBuilder<Span>,
543    subtree: tt::TokenTreesView<'_, Span>,
544) {
545    let mut prev_was_ident = false;
546    // Note that we only need to fix up the top-level `TokenTree`s because the
547    // context of the paths in the descendant `Subtree`s won't be changed by the
548    // mbe transcription.
549    let mut iter = subtree.iter();
550    while let Some(tt) = iter.next_as_view() {
551        if prev_was_ident {
552            // Pedantically, `(T) -> U` in `FnOnce(T) -> U` is treated as a generic
553            // argument list and thus needs `::` between it and `FnOnce`. However in
554            // today's Rust this type of path *semantically* cannot appear as a
555            // top-level expression-context path, so we can safely ignore it.
556            if let [tt::TokenTree::Leaf(tt::Leaf::Punct(tt::Punct { char: '<', .. }))] =
557                tt.flat_tokens()
558            {
559                builder.extend([
560                    tt::Leaf::Punct(tt::Punct {
561                        char: ':',
562                        spacing: tt::Spacing::Joint,
563                        span: ctx.call_site,
564                    }),
565                    tt::Leaf::Punct(tt::Punct {
566                        char: ':',
567                        spacing: tt::Spacing::Alone,
568                        span: ctx.call_site,
569                    }),
570                ]);
571            }
572        }
573        prev_was_ident = matches!(tt.flat_tokens(), [tt::TokenTree::Leaf(tt::Leaf::Ident(_))]);
574        builder.extend_with_tt(tt);
575    }
576}
577
578/// Handles `${count(t, depth)}`. `our_depth` is the recursion depth and `count_depth` is the depth
579/// defined by the metavar expression.
580fn count(binding: &Binding<'_>, depth_curr: usize, depth_max: usize) -> usize {
581    match binding {
582        Binding::Nested(bs) => {
583            if depth_curr == depth_max {
584                bs.len()
585            } else {
586                bs.iter().map(|b| count(b, depth_curr + 1, depth_max)).sum()
587            }
588        }
589        Binding::Empty => 0,
590        Binding::Fragment(_) | Binding::Missing(_) => 1,
591    }
592}
mbe/expander/transcriber.rs

mbe/expander/
transcriber.rs
