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::{ExpandError, ExpandResult};
  12
  13 pub(crate) fn expand_rules(
  14     rules: &[crate::Rule],
  15     input: &tt::Subtree,
  16 ) -> ExpandResult<tt::Subtree> {
  17     let mut match_: Option<(matcher::Match, &crate::Rule)> = None;
  18     for rule in rules {
  19         let new_match = match matcher::match_(&rule.lhs, input) {
  20             Ok(m) => m,
  21             Err(_e) => {
  22                 // error in pattern parsing
  23                 continue;
  24             }
  25         };
  26         if new_match.err.is_none() {
  27             // If we find a rule that applies without errors, we're done.
  28             // Unconditionally returning the transcription here makes the
  29             // `test_repeat_bad_var` test fail.
  30             let ExpandResult { value, err: transcribe_err } =
  31                 transcriber::transcribe(&rule.rhs, &new_match.bindings);
  32             if transcribe_err.is_none() {
  33                 return ExpandResult::ok(value);
  34             }
  35         }
  36         // Use the rule if we matched more tokens, or had fewer errors
  37         if let Some((prev_match, _)) = &match_ {
  38             if (new_match.unmatched_tts, new_match.err_count)
  39                 < (prev_match.unmatched_tts, prev_match.err_count)
  40             {
  41                 match_ = Some((new_match, rule));
  42             }
  43         } else {
  44             match_ = Some((new_match, rule));
  45         }
  46     }
  47     if let Some((match_, rule)) = match_ {
  48         // if we got here, there was no match without errors
  49         let ExpandResult { value, err: transcribe_err } =
  50             transcriber::transcribe(&rule.rhs, &match_.bindings);
  51         ExpandResult { value, err: match_.err.or(transcribe_err) }
  52     } else {
  53         ExpandResult::only_err(ExpandError::NoMatchingRule)
  54     }
  55 }
  56
  57 /// The actual algorithm for expansion is not too hard, but is pretty tricky.
  58 /// `Bindings` structure is the key to understanding what we are doing here.
  59 ///
  60 /// On the high level, it stores mapping from meta variables to the bits of
  61 /// syntax it should be substituted with. For example, if `$e:expr` is matched
  62 /// with `1 + 1` by macro_rules, the `Binding` will store `$e -> 1 + 1`.
  63 ///
  64 /// The tricky bit is dealing with repetitions (`$()*`). Consider this example:
  65 ///
  66 /// ```not_rust
  67 /// macro_rules! foo {
  68 ///     ($($ i:ident $($ e:expr),*);*) => {
  69 ///         $(fn $ i() { $($ e);*; })*
  70 ///     }
  71 /// }
  72 /// foo! { foo 1,2,3; bar 4,5,6 }
  73 /// ```
  74 ///
  75 /// Here, the `$i` meta variable is matched first with `foo` and then with
  76 /// `bar`, and `$e` is matched in turn with `1`, `2`, `3`, `4`, `5`, `6`.
  77 ///
  78 /// To represent such "multi-mappings", we use a recursive structures: we map
  79 /// variables not to values, but to *lists* of values or other lists (that is,
  80 /// to the trees).
  81 ///
  82 /// For the above example, the bindings would store
  83 ///
  84 /// ```not_rust
  85 /// i -> [foo, bar]
  86 /// e -> [[1, 2, 3], [4, 5, 6]]
  87 /// ```
  88 ///
  89 /// We construct `Bindings` in the `match_lhs`. The interesting case is
  90 /// `TokenTree::Repeat`, where we use `push_nested` to create the desired
  91 /// nesting structure.
  92 ///
  93 /// The other side of the puzzle is `expand_subtree`, where we use the bindings
  94 /// to substitute meta variables in the output template. When expanding, we
  95 /// maintain a `nesting` stack of indices which tells us which occurrence from
  96 /// the `Bindings` we should take. We push to the stack when we enter a
  97 /// repetition.
  98 ///
  99 /// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
 100 /// `tt::TokenTree`, where the index to select a particular `TokenTree` among
 101 /// many is not a plain `usize`, but an `&[usize]`.
 102 #[derive(Debug, Default)]
 103 struct Bindings {
 104     inner: FxHashMap<SmolStr, Binding>,
 105 }
 106
 107 #[derive(Debug)]
 108 enum Binding {
 109     Fragment(Fragment),
 110     Nested(Vec<Binding>),
 111     Empty,
 112 }
 113
 114 #[derive(Debug, Clone)]
 115 enum Fragment {
 116     /// token fragments are just copy-pasted into the output
 117     Tokens(tt::TokenTree),
 118     /// Ast fragments are inserted with fake delimiters, so as to make things
 119     /// like `$i * 2` where `$i = 1 + 1` work as expectd.
 120     Ast(tt::TokenTree),
 121 }
 122
 123 #[cfg(test)]
 124 mod tests {
 125     use syntax::{ast, AstNode};
 126
 127     use super::*;
 128     use crate::ast_to_token_tree;
 129
 130     #[test]
 131     fn test_expand_rule() {
 132         assert_err(
 133             "($($i:ident);*) => ($i)",
 134             "foo!{a}",
 135             ExpandError::BindingError(String::from(
 136                 "expected simple binding, found nested binding `i`",
 137             )),
 138         );
 139
 140         // FIXME:
 141         // Add an err test case for ($($i:ident)) => ($())
 142     }
 143
 144     fn assert_err(macro_body: &str, invocation: &str, err: ExpandError) {
 145         assert_eq!(
 146             expand_first(&create_rules(&format_macro(macro_body)), invocation).err,
 147             Some(err)
 148         );
 149     }
 150
 151     fn format_macro(macro_body: &str) -> String {
 152         format!(
 153             "
 154         macro_rules! foo {{
 155             {}
 156         }}
 157 ",
 158             macro_body
 159         )
 160     }
 161
 162     fn create_rules(macro_definition: &str) -> crate::MacroRules {
 163         let source_file = ast::SourceFile::parse(macro_definition).ok().unwrap();
 164         let macro_definition =
 165             source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap();
 166
 167         let (definition_tt, _) =
 168             ast_to_token_tree(&macro_definition.token_tree().unwrap()).unwrap();
 169         crate::MacroRules::parse(&definition_tt).unwrap()
 170     }
 171
 172     fn expand_first(rules: &crate::MacroRules, invocation: &str) -> ExpandResult<tt::Subtree> {
 173         let source_file = ast::SourceFile::parse(invocation).ok().unwrap();
 174         let macro_invocation =
 175             source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
 176
 177         let (invocation_tt, _) =
 178             ast_to_token_tree(&macro_invocation.token_tree().unwrap()).unwrap();
 179
 180         expand_rules(&rules.rules, &invocation_tt)
 181     }
 182 }