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