crates/mbe/src/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
   4 use syntax::SmolStr;
   5
   6 use super::ExpandResult;
   7 use crate::{
   8     expander::{Binding, Bindings, Fragment},
   9     parser::{Op, RepeatKind, Separator},
  10     ExpandError, MetaTemplate,
  11 };
  12
  13 impl Bindings {
  14     fn contains(&self, name: &str) -> bool {
  15         self.inner.contains_key(name)
  16     }
  17
  18     fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
  19         let mut b = self.inner.get(name).ok_or_else(|| {
  20             ExpandError::BindingError(format!("could not find binding `{}`", name))
  21         })?;
  22         for nesting_state in nesting.iter_mut() {
  23             nesting_state.hit = true;
  24             b = match b {
  25                 Binding::Fragment(_) => break,
  26                 Binding::Nested(bs) => bs.get(nesting_state.idx).ok_or_else(|| {
  27                     nesting_state.at_end = true;
  28                     ExpandError::BindingError(format!("could not find nested binding `{}`", name))
  29                 })?,
  30                 Binding::Empty => {
  31                     nesting_state.at_end = true;
  32                     return Err(ExpandError::BindingError(format!(
  33                         "could not find empty binding `{}`",
  34                         name
  35                     )));
  36                 }
  37             };
  38         }
  39         match b {
  40             Binding::Fragment(it) => Ok(it),
  41             Binding::Nested(_) => Err(ExpandError::BindingError(format!(
  42                 "expected simple binding, found nested binding `{}`",
  43                 name
  44             ))),
  45             Binding::Empty => Err(ExpandError::BindingError(format!(
  46                 "expected simple binding, found empty binding `{}`",
  47                 name
  48             ))),
  49         }
  50     }
  51 }
  52
  53 pub(super) fn transcribe(
  54     template: &MetaTemplate,
  55     bindings: &Bindings,
  56 ) -> ExpandResult<tt::Subtree> {
  57     assert!(template.delimiter == None);
  58     let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() };
  59     let mut arena: Vec<tt::TokenTree> = Vec::new();
  60     expand_subtree(&mut ctx, template, &mut arena)
  61 }
  62
  63 #[derive(Debug)]
  64 struct NestingState {
  65     idx: usize,
  66     /// `hit` is currently necessary to tell `expand_repeat` if it should stop
  67     /// because there is no variable in use by the current repetition
  68     hit: bool,
  69     /// `at_end` is currently necessary to tell `expand_repeat` if it should stop
  70     /// because there is no more value available for the current repetition
  71     at_end: bool,
  72 }
  73
  74 #[derive(Debug)]
  75 struct ExpandCtx<'a> {
  76     bindings: &'a Bindings,
  77     nesting: Vec<NestingState>,
  78 }
  79
  80 fn expand_subtree(
  81     ctx: &mut ExpandCtx,
  82     template: &MetaTemplate,
  83     arena: &mut Vec<tt::TokenTree>,
  84 ) -> ExpandResult<tt::Subtree> {
  85     // remember how many elements are in the arena now - when returning, we want to drain exactly how many elements we added. This way, the recursive uses of the arena get their own "view" of the arena, but will reuse the allocation
  86     let start_elements = arena.len();
  87     let mut err = None;
  88     for op in template.iter() {
  89         match op {
  90             Op::Leaf(tt) => arena.push(tt.clone().into()),
  91             Op::Subtree(tt) => {
  92                 let ExpandResult { value: tt, err: e } = expand_subtree(ctx, &tt, arena);
  93                 err = err.or(e);
  94                 arena.push(tt.into());
  95             }
  96             Op::Var { name, id, .. } => {
  97                 let ExpandResult { value: fragment, err: e } = expand_var(ctx, &name, *id);
  98                 err = err.or(e);
  99                 push_fragment(arena, fragment);
 100             }
 101             Op::Repeat { subtree, kind, separator } => {
 102                 let ExpandResult { value: fragment, err: e } =
 103                     expand_repeat(ctx, subtree, *kind, separator, arena);
 104                 err = err.or(e);
 105                 push_fragment(arena, fragment)
 106             }
 107         }
 108     }
 109     // drain the elements added in this instance of expand_subtree
 110     let tts = arena.drain(start_elements..arena.len()).collect();
 111     ExpandResult { value: tt::Subtree { delimiter: template.delimiter, token_trees: tts }, err }
 112 }
 113
 114 fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> {
 115     // We already handle $crate case in mbe parser
 116     debug_assert!(v != "crate");
 117
 118     if !ctx.bindings.contains(v) {
 119         // Note that it is possible to have a `$var` inside a macro which is not bound.
 120         // For example:
 121         // ```
 122         // macro_rules! foo {
 123         //     ($a:ident, $b:ident, $c:tt) => {
 124         //         macro_rules! bar {
 125         //             ($bi:ident) => {
 126         //                 fn $bi() -> u8 {$c}
 127         //             }
 128         //         }
 129         //     }
 130         // ```
 131         // We just treat it a normal tokens
 132         let tt = tt::Subtree {
 133             delimiter: None,
 134             token_trees: vec![
 135                 tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone, id }).into(),
 136                 tt::Leaf::from(tt::Ident { text: v.clone(), id }).into(),
 137             ],
 138         }
 139         .into();
 140         ExpandResult::ok(Fragment::Tokens(tt))
 141     } else {
 142         ctx.bindings.get(&v, &mut ctx.nesting).map_or_else(
 143             |e| ExpandResult { value: Fragment::Tokens(tt::TokenTree::empty()), err: Some(e) },
 144             |b| ExpandResult::ok(b.clone()),
 145         )
 146     }
 147 }
 148
 149 fn expand_repeat(
 150     ctx: &mut ExpandCtx,
 151     template: &MetaTemplate,
 152     kind: RepeatKind,
 153     separator: &Option<Separator>,
 154     arena: &mut Vec<tt::TokenTree>,
 155 ) -> ExpandResult<Fragment> {
 156     let mut buf: Vec<tt::TokenTree> = Vec::new();
 157     ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
 158     // Dirty hack to make macro-expansion terminate.
 159     // This should be replaced by a proper macro-by-example implementation
 160     let limit = 65536;
 161     let mut has_seps = 0;
 162     let mut counter = 0;
 163
 164     loop {
 165         let ExpandResult { value: mut t, err: e } = expand_subtree(ctx, template, arena);
 166         let nesting_state = ctx.nesting.last_mut().unwrap();
 167         if nesting_state.at_end || !nesting_state.hit {
 168             break;
 169         }
 170         nesting_state.idx += 1;
 171         nesting_state.hit = false;
 172
 173         counter += 1;
 174         if counter == limit {
 175             log::warn!("expand_tt in repeat pattern exceed limit => {:#?}\n{:#?}", template, ctx);
 176             break;
 177         }
 178
 179         if e.is_some() {
 180             continue;
 181         }
 182
 183         t.delimiter = None;
 184         push_subtree(&mut buf, t);
 185
 186         if let Some(ref sep) = separator {
 187             match sep {
 188                 Separator::Ident(ident) => {
 189                     has_seps = 1;
 190                     buf.push(tt::Leaf::from(ident.clone()).into());
 191                 }
 192                 Separator::Literal(lit) => {
 193                     has_seps = 1;
 194                     buf.push(tt::Leaf::from(lit.clone()).into());
 195                 }
 196
 197                 Separator::Puncts(puncts) => {
 198                     has_seps = puncts.len();
 199                     for punct in puncts {
 200                         buf.push(tt::Leaf::from(*punct).into());
 201                     }
 202                 }
 203             }
 204         }
 205
 206         if RepeatKind::ZeroOrOne == kind {
 207             break;
 208         }
 209     }
 210
 211     ctx.nesting.pop().unwrap();
 212     for _ in 0..has_seps {
 213         buf.pop();
 214     }
 215
 216     // Check if it is a single token subtree without any delimiter
 217     // e.g {Delimiter:None> ['>'] /Delimiter:None>}
 218     let tt = tt::Subtree { delimiter: None, token_trees: buf }.into();
 219
 220     if RepeatKind::OneOrMore == kind && counter == 0 {
 221         return ExpandResult {
 222             value: Fragment::Tokens(tt),
 223             err: Some(ExpandError::UnexpectedToken),
 224         };
 225     }
 226     ExpandResult::ok(Fragment::Tokens(tt))
 227 }
 228
 229 fn push_fragment(buf: &mut Vec<tt::TokenTree>, fragment: Fragment) {
 230     match fragment {
 231         Fragment::Tokens(tt::TokenTree::Subtree(tt)) => push_subtree(buf, tt),
 232         Fragment::Tokens(tt) | Fragment::Ast(tt) => buf.push(tt),
 233     }
 234 }
 235
 236 fn push_subtree(buf: &mut Vec<tt::TokenTree>, tt: tt::Subtree) {
 237     match tt.delimiter {
 238         None => buf.extend(tt.token_trees),
 239         _ => buf.push(tt.into()),
 240     }
 241 }