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         let op = match op {
  90             Ok(op) => op,
  91             Err(e) => {
  92                 err = Some(e.clone());
  93                 break;
  94             }
  95         };
  96         match op {
  97             Op::Leaf(tt) => arena.push(tt.clone().into()),
  98             Op::Subtree(tt) => {
  99                 let ExpandResult { value: tt, err: e } = expand_subtree(ctx, &tt, arena);
 100                 err = err.or(e);
 101                 arena.push(tt.into());
 102             }
 103             Op::Var { name, id, .. } => {
 104                 let ExpandResult { value: fragment, err: e } = expand_var(ctx, &name, *id);
 105                 err = err.or(e);
 106                 push_fragment(arena, fragment);
 107             }
 108             Op::Repeat { subtree, kind, separator } => {
 109                 let ExpandResult { value: fragment, err: e } =
 110                     expand_repeat(ctx, subtree, *kind, separator, arena);
 111                 err = err.or(e);
 112                 push_fragment(arena, fragment)
 113             }
 114         }
 115     }
 116     // drain the elements added in this instance of expand_subtree
 117     let tts = arena.drain(start_elements..arena.len()).collect();
 118     ExpandResult { value: tt::Subtree { delimiter: template.delimiter, token_trees: tts }, err }
 119 }
 120
 121 fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> {
 122     // We already handle $crate case in mbe parser
 123     debug_assert!(v != "crate");
 124
 125     if !ctx.bindings.contains(v) {
 126         // Note that it is possible to have a `$var` inside a macro which is not bound.
 127         // For example:
 128         // ```
 129         // macro_rules! foo {
 130         //     ($a:ident, $b:ident, $c:tt) => {
 131         //         macro_rules! bar {
 132         //             ($bi:ident) => {
 133         //                 fn $bi() -> u8 {$c}
 134         //             }
 135         //         }
 136         //     }
 137         // ```
 138         // We just treat it a normal tokens
 139         let tt = tt::Subtree {
 140             delimiter: None,
 141             token_trees: vec![
 142                 tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone, id }).into(),
 143                 tt::Leaf::from(tt::Ident { text: v.clone(), id }).into(),
 144             ],
 145         }
 146         .into();
 147         ExpandResult::ok(Fragment::Tokens(tt))
 148     } else {
 149         ctx.bindings.get(&v, &mut ctx.nesting).map_or_else(
 150             |e| ExpandResult { value: Fragment::Tokens(tt::TokenTree::empty()), err: Some(e) },
 151             |b| ExpandResult::ok(b.clone()),
 152         )
 153     }
 154 }
 155
 156 fn expand_repeat(
 157     ctx: &mut ExpandCtx,
 158     template: &MetaTemplate,
 159     kind: RepeatKind,
 160     separator: &Option<Separator>,
 161     arena: &mut Vec<tt::TokenTree>,
 162 ) -> ExpandResult<Fragment> {
 163     let mut buf: Vec<tt::TokenTree> = Vec::new();
 164     ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
 165     // Dirty hack to make macro-expansion terminate.
 166     // This should be replaced by a proper macro-by-example implementation
 167     let limit = 65536;
 168     let mut has_seps = 0;
 169     let mut counter = 0;
 170
 171     loop {
 172         let ExpandResult { value: mut t, err: e } = expand_subtree(ctx, template, arena);
 173         let nesting_state = ctx.nesting.last_mut().unwrap();
 174         if nesting_state.at_end || !nesting_state.hit {
 175             break;
 176         }
 177         nesting_state.idx += 1;
 178         nesting_state.hit = false;
 179
 180         counter += 1;
 181         if counter == limit {
 182             log::warn!("expand_tt in repeat pattern exceed limit => {:#?}\n{:#?}", template, ctx);
 183             break;
 184         }
 185
 186         if e.is_some() {
 187             continue;
 188         }
 189
 190         t.delimiter = None;
 191         push_subtree(&mut buf, t);
 192
 193         if let Some(ref sep) = separator {
 194             match sep {
 195                 Separator::Ident(ident) => {
 196                     has_seps = 1;
 197                     buf.push(tt::Leaf::from(ident.clone()).into());
 198                 }
 199                 Separator::Literal(lit) => {
 200                     has_seps = 1;
 201                     buf.push(tt::Leaf::from(lit.clone()).into());
 202                 }
 203
 204                 Separator::Puncts(puncts) => {
 205                     has_seps = puncts.len();
 206                     for punct in puncts {
 207                         buf.push(tt::Leaf::from(*punct).into());
 208                     }
 209                 }
 210             }
 211         }
 212
 213         if RepeatKind::ZeroOrOne == kind {
 214             break;
 215         }
 216     }
 217
 218     ctx.nesting.pop().unwrap();
 219     for _ in 0..has_seps {
 220         buf.pop();
 221     }
 222
 223     // Check if it is a single token subtree without any delimiter
 224     // e.g {Delimiter:None> ['>'] /Delimiter:None>}
 225     let tt = tt::Subtree { delimiter: None, token_trees: buf }.into();
 226
 227     if RepeatKind::OneOrMore == kind && counter == 0 {
 228         return ExpandResult {
 229             value: Fragment::Tokens(tt),
 230             err: Some(ExpandError::UnexpectedToken),
 231         };
 232     }
 233     ExpandResult::ok(Fragment::Tokens(tt))
 234 }
 235
 236 fn push_fragment(buf: &mut Vec<tt::TokenTree>, fragment: Fragment) {
 237     match fragment {
 238         Fragment::Tokens(tt::TokenTree::Subtree(tt)) => push_subtree(buf, tt),
 239         Fragment::Tokens(tt) | Fragment::Ast(tt) => buf.push(tt),
 240     }
 241 }
 242
 243 fn push_subtree(buf: &mut Vec<tt::TokenTree>, tt: tt::Subtree) {
 244     match tt.delimiter {
 245         None => buf.extend(tt.token_trees),
 246         _ => buf.push(tt.into()),
 247     }
 248 }