src/libsyntax/ext/tt/transcribe.rs

   1 use crate::ast::Ident;
   2 use crate::ext::base::ExtCtxt;
   3 use crate::ext::expand::Marker;
   4 use crate::ext::tt::macro_parser::{MatchedNonterminal, MatchedSeq, NamedMatch};
   5 use crate::ext::tt::quoted;
   6 use crate::mut_visit::noop_visit_tt;
   7 use crate::parse::token::{self, NtTT, Token};
   8 use crate::tokenstream::{DelimSpan, TokenStream, TokenTree, TreeAndJoint};
   9
  10 use smallvec::{smallvec, SmallVec};
  11 use syntax_pos::DUMMY_SP;
  12
  13 use rustc_data_structures::fx::FxHashMap;
  14 use rustc_data_structures::sync::Lrc;
  15 use std::mem;
  16 use std::ops::Add;
  17 use std::rc::Rc;
  18
  19 /// An iterator over the token trees in a delimited token tree (`{ ... }`) or a sequence (`$(...)`).
  20 enum Frame {
  21     Delimited { forest: Lrc<quoted::Delimited>, idx: usize, span: DelimSpan },
  22     Sequence { forest: Lrc<quoted::SequenceRepetition>, idx: usize, sep: Option<Token> },
  23 }
  24
  25 impl Frame {
  26     fn new(tts: Vec<quoted::TokenTree>) -> Frame {
  27         let forest = Lrc::new(quoted::Delimited { delim: token::NoDelim, tts: tts });
  28         Frame::Delimited { forest: forest, idx: 0, span: DelimSpan::dummy() }
  29     }
  30 }
  31
  32 impl Iterator for Frame {
  33     type Item = quoted::TokenTree;
  34
  35     fn next(&mut self) -> Option<quoted::TokenTree> {
  36         match *self {
  37             Frame::Delimited { ref forest, ref mut idx, .. } => {
  38                 *idx += 1;
  39                 forest.tts.get(*idx - 1).cloned()
  40             }
  41             Frame::Sequence { ref forest, ref mut idx, .. } => {
  42                 *idx += 1;
  43                 forest.tts.get(*idx - 1).cloned()
  44             }
  45         }
  46     }
  47 }
  48
  49 /// This can do Macro-By-Example transcription. On the other hand, if `src` contains no
  50 /// `TokenTree::{Sequence, MetaVar, MetaVarDecl}`s, `interp` can (and should) be `None`.
  51 pub fn transcribe(
  52     cx: &ExtCtxt<'_>,
  53     interp: Option<FxHashMap<Ident, Rc<NamedMatch>>>,
  54     src: Vec<quoted::TokenTree>,
  55 ) -> TokenStream {
  56     let mut stack: SmallVec<[Frame; 1]> = smallvec![Frame::new(src)];
  57     let interpolations = interp.unwrap_or_else(FxHashMap::default); /* just a convenience */
  58     let mut repeats = Vec::new();
  59     let mut result: Vec<TreeAndJoint> = Vec::new();
  60     let mut result_stack = Vec::new();
  61
  62     loop {
  63         let tree = if let Some(tree) = stack.last_mut().unwrap().next() {
  64             tree
  65         } else {
  66             if let Frame::Sequence { ref mut idx, ref sep, .. } = *stack.last_mut().unwrap() {
  67                 let (ref mut repeat_idx, repeat_len) = *repeats.last_mut().unwrap();
  68                 *repeat_idx += 1;
  69                 if *repeat_idx < repeat_len {
  70                     *idx = 0;
  71                     if let Some(sep) = sep.clone() {
  72                         // repeat same span, I guess
  73                         let prev_span = match result.last() {
  74                             Some((tt, _)) => tt.span(),
  75                             None => DUMMY_SP,
  76                         };
  77                         result.push(TokenTree::Token(prev_span, sep).into());
  78                     }
  79                     continue;
  80                 }
  81             }
  82
  83             match stack.pop().unwrap() {
  84                 Frame::Sequence { .. } => {
  85                     repeats.pop();
  86                 }
  87                 Frame::Delimited { forest, span, .. } => {
  88                     if result_stack.is_empty() {
  89                         return TokenStream::new(result);
  90                     }
  91                     let tree =
  92                         TokenTree::Delimited(span, forest.delim, TokenStream::new(result).into());
  93                     result = result_stack.pop().unwrap();
  94                     result.push(tree.into());
  95                 }
  96             }
  97             continue;
  98         };
  99
 100         match tree {
 101             quoted::TokenTree::Sequence(sp, seq) => {
 102                 // FIXME(pcwalton): Bad copy.
 103                 match lockstep_iter_size(
 104                     &quoted::TokenTree::Sequence(sp, seq.clone()),
 105                     &interpolations,
 106                     &repeats,
 107                 ) {
 108                     LockstepIterSize::Unconstrained => {
 109                         cx.span_fatal(
 110                             sp.entire(), /* blame macro writer */
 111                             "attempted to repeat an expression \
 112                              containing no syntax \
 113                              variables matched as repeating at this depth",
 114                         );
 115                     }
 116                     LockstepIterSize::Contradiction(ref msg) => {
 117                         // FIXME #2887 blame macro invoker instead
 118                         cx.span_fatal(sp.entire(), &msg[..]);
 119                     }
 120                     LockstepIterSize::Constraint(len, _) => {
 121                         if len == 0 {
 122                             if seq.op == quoted::KleeneOp::OneOrMore {
 123                                 // FIXME #2887 blame invoker
 124                                 cx.span_fatal(sp.entire(), "this must repeat at least once");
 125                             }
 126                         } else {
 127                             repeats.push((0, len));
 128                             stack.push(Frame::Sequence {
 129                                 idx: 0,
 130                                 sep: seq.separator.clone(),
 131                                 forest: seq,
 132                             });
 133                         }
 134                     }
 135                 }
 136             }
 137             // FIXME #2887: think about span stuff here
 138             quoted::TokenTree::MetaVar(mut sp, ident) => {
 139                 if let Some(cur_matched) = lookup_cur_matched(ident, &interpolations, &repeats) {
 140                     if let MatchedNonterminal(ref nt) = *cur_matched {
 141                         if let NtTT(ref tt) = **nt {
 142                             result.push(tt.clone().into());
 143                         } else {
 144                             sp = sp.apply_mark(cx.current_expansion.mark);
 145                             let token = TokenTree::Token(sp, Token::Interpolated(nt.clone()));
 146                             result.push(token.into());
 147                         }
 148                     } else {
 149                         cx.span_fatal(
 150                             sp, /* blame the macro writer */
 151                             &format!("variable '{}' is still repeating at this depth", ident),
 152                         );
 153                     }
 154                 } else {
 155                     let ident =
 156                         Ident::new(ident.name, ident.span.apply_mark(cx.current_expansion.mark));
 157                     sp = sp.apply_mark(cx.current_expansion.mark);
 158                     result.push(TokenTree::Token(sp, token::Dollar).into());
 159                     result.push(TokenTree::Token(sp, token::Token::from_ast_ident(ident)).into());
 160                 }
 161             }
 162             quoted::TokenTree::Delimited(mut span, delimited) => {
 163                 span = span.apply_mark(cx.current_expansion.mark);
 164                 stack.push(Frame::Delimited { forest: delimited, idx: 0, span: span });
 165                 result_stack.push(mem::replace(&mut result, Vec::new()));
 166             }
 167             quoted::TokenTree::Token(sp, tok) => {
 168                 let mut marker = Marker(cx.current_expansion.mark);
 169                 let mut tt = TokenTree::Token(sp, tok);
 170                 noop_visit_tt(&mut tt, &mut marker);
 171                 result.push(tt.into());
 172             }
 173             quoted::TokenTree::MetaVarDecl(..) => panic!("unexpected `TokenTree::MetaVarDecl"),
 174         }
 175     }
 176 }
 177
 178 fn lookup_cur_matched(
 179     ident: Ident,
 180     interpolations: &FxHashMap<Ident, Rc<NamedMatch>>,
 181     repeats: &[(usize, usize)],
 182 ) -> Option<Rc<NamedMatch>> {
 183     interpolations.get(&ident).map(|matched| {
 184         let mut matched = matched.clone();
 185         for &(idx, _) in repeats {
 186             let m = matched.clone();
 187             match *m {
 188                 MatchedNonterminal(_) => break,
 189                 MatchedSeq(ref ads, _) => matched = Rc::new(ads[idx].clone()),
 190             }
 191         }
 192
 193         matched
 194     })
 195 }
 196
 197 #[derive(Clone)]
 198 enum LockstepIterSize {
 199     Unconstrained,
 200     Constraint(usize, Ident),
 201     Contradiction(String),
 202 }
 203
 204 impl Add for LockstepIterSize {
 205     type Output = LockstepIterSize;
 206
 207     fn add(self, other: LockstepIterSize) -> LockstepIterSize {
 208         match self {
 209             LockstepIterSize::Unconstrained => other,
 210             LockstepIterSize::Contradiction(_) => self,
 211             LockstepIterSize::Constraint(l_len, ref l_id) => match other {
 212                 LockstepIterSize::Unconstrained => self,
 213                 LockstepIterSize::Contradiction(_) => other,
 214                 LockstepIterSize::Constraint(r_len, _) if l_len == r_len => self,
 215                 LockstepIterSize::Constraint(r_len, r_id) => {
 216                     let msg = format!(
 217                         "inconsistent lockstep iteration: \
 218                          '{}' has {} items, but '{}' has {}",
 219                         l_id, l_len, r_id, r_len
 220                     );
 221                     LockstepIterSize::Contradiction(msg)
 222                 }
 223             },
 224         }
 225     }
 226 }
 227
 228 fn lockstep_iter_size(
 229     tree: &quoted::TokenTree,
 230     interpolations: &FxHashMap<Ident, Rc<NamedMatch>>,
 231     repeats: &[(usize, usize)],
 232 ) -> LockstepIterSize {
 233     use quoted::TokenTree;
 234     match *tree {
 235         TokenTree::Delimited(_, ref delimed) => {
 236             delimed.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
 237                 size + lockstep_iter_size(tt, interpolations, repeats)
 238             })
 239         }
 240         TokenTree::Sequence(_, ref seq) => {
 241             seq.tts.iter().fold(LockstepIterSize::Unconstrained, |size, tt| {
 242                 size + lockstep_iter_size(tt, interpolations, repeats)
 243             })
 244         }
 245         TokenTree::MetaVar(_, name) | TokenTree::MetaVarDecl(_, name, _) => {
 246             match lookup_cur_matched(name, interpolations, repeats) {
 247                 Some(matched) => match *matched {
 248                     MatchedNonterminal(_) => LockstepIterSize::Unconstrained,
 249                     MatchedSeq(ref ads, _) => LockstepIterSize::Constraint(ads.len(), name),
 250                 },
 251                 _ => LockstepIterSize::Unconstrained,
 252             }
 253         }
 254         TokenTree::Token(..) => LockstepIterSize::Unconstrained,
 255     }
 256 }