src/tools/rust-analyzer/crates/mbe/src/expander.rs

   1 //! This module takes a (parsed) definition of `macro_rules` invocation, a
   2 //! `tt::TokenTree` representing an argument of macro invocation, and produces a
   3 //! `tt::TokenTree` for the result of the expansion.
   4
   5 mod matcher;
   6 mod transcriber;
   7
   8 use rustc_hash::FxHashMap;
   9 use syntax::SmolStr;
  10
  11 use crate::{parser::MetaVarKind, tt, ExpandError, ExpandResult};
  12
  13 pub(crate) fn expand_rules(
  14     rules: &[crate::Rule],
  15     input: &tt::Subtree,
  16     is_2021: bool,
  17 ) -> ExpandResult<tt::Subtree> {
  18     let mut match_: Option<(matcher::Match, &crate::Rule)> = None;
  19     for rule in rules {
  20         let new_match = matcher::match_(&rule.lhs, input, is_2021);
  21
  22         if new_match.err.is_none() {
  23             // If we find a rule that applies without errors, we're done.
  24             // Unconditionally returning the transcription here makes the
  25             // `test_repeat_bad_var` test fail.
  26             let ExpandResult { value, err: transcribe_err } =
  27                 transcriber::transcribe(&rule.rhs, &new_match.bindings);
  28             if transcribe_err.is_none() {
  29                 return ExpandResult::ok(value);
  30             }
  31         }
  32         // Use the rule if we matched more tokens, or bound variables count
  33         if let Some((prev_match, _)) = &match_ {
  34             if (new_match.unmatched_tts, -(new_match.bound_count as i32))
  35                 < (prev_match.unmatched_tts, -(prev_match.bound_count as i32))
  36             {
  37                 match_ = Some((new_match, rule));
  38             }
  39         } else {
  40             match_ = Some((new_match, rule));
  41         }
  42     }
  43     if let Some((match_, rule)) = match_ {
  44         // if we got here, there was no match without errors
  45         let ExpandResult { value, err: transcribe_err } =
  46             transcriber::transcribe(&rule.rhs, &match_.bindings);
  47         ExpandResult { value, err: match_.err.or(transcribe_err) }
  48     } else {
  49         ExpandResult::new(
  50             tt::Subtree { delimiter: tt::Delimiter::unspecified(), token_trees: vec![] },
  51             ExpandError::NoMatchingRule,
  52         )
  53     }
  54 }
  55
  56 /// The actual algorithm for expansion is not too hard, but is pretty tricky.
  57 /// `Bindings` structure is the key to understanding what we are doing here.
  58 ///
  59 /// On the high level, it stores mapping from meta variables to the bits of
  60 /// syntax it should be substituted with. For example, if `$e:expr` is matched
  61 /// with `1 + 1` by macro_rules, the `Binding` will store `$e -> 1 + 1`.
  62 ///
  63 /// The tricky bit is dealing with repetitions (`$()*`). Consider this example:
  64 ///
  65 /// ```not_rust
  66 /// macro_rules! foo {
  67 ///     ($($ i:ident $($ e:expr),*);*) => {
  68 ///         $(fn $ i() { $($ e);*; })*
  69 ///     }
  70 /// }
  71 /// foo! { foo 1,2,3; bar 4,5,6 }
  72 /// ```
  73 ///
  74 /// Here, the `$i` meta variable is matched first with `foo` and then with
  75 /// `bar`, and `$e` is matched in turn with `1`, `2`, `3`, `4`, `5`, `6`.
  76 ///
  77 /// To represent such "multi-mappings", we use a recursive structures: we map
  78 /// variables not to values, but to *lists* of values or other lists (that is,
  79 /// to the trees).
  80 ///
  81 /// For the above example, the bindings would store
  82 ///
  83 /// ```not_rust
  84 /// i -> [foo, bar]
  85 /// e -> [[1, 2, 3], [4, 5, 6]]
  86 /// ```
  87 ///
  88 /// We construct `Bindings` in the `match_lhs`. The interesting case is
  89 /// `TokenTree::Repeat`, where we use `push_nested` to create the desired
  90 /// nesting structure.
  91 ///
  92 /// The other side of the puzzle is `expand_subtree`, where we use the bindings
  93 /// to substitute meta variables in the output template. When expanding, we
  94 /// maintain a `nesting` stack of indices which tells us which occurrence from
  95 /// the `Bindings` we should take. We push to the stack when we enter a
  96 /// repetition.
  97 ///
  98 /// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
  99 /// `tt::TokenTree`, where the index to select a particular `TokenTree` among
 100 /// many is not a plain `usize`, but a `&[usize]`.
 101 #[derive(Debug, Default, Clone, PartialEq, Eq)]
 102 struct Bindings {
 103     inner: FxHashMap<SmolStr, Binding>,
 104 }
 105
 106 #[derive(Debug, Clone, PartialEq, Eq)]
 107 enum Binding {
 108     Fragment(Fragment),
 109     Nested(Vec<Binding>),
 110     Empty,
 111     Missing(MetaVarKind),
 112 }
 113
 114 #[derive(Debug, Clone, PartialEq, Eq)]
 115 enum Fragment {
 116     /// token fragments are just copy-pasted into the output
 117     Tokens(tt::TokenTree),
 118     /// Expr ast fragments are surrounded with `()` on insertion to preserve
 119     /// precedence. Note that this impl is different from the one currently in
 120     /// `rustc` -- `rustc` doesn't translate fragments into token trees at all.
 121     ///
 122     /// At one point in time, we tried to to use "fake" delimiters here a-la
 123     /// proc-macro delimiter=none. As we later discovered, "none" delimiters are
 124     /// tricky to handle in the parser, and rustc doesn't handle those either.
 125     Expr(tt::TokenTree),
 126 }