src/libsyntax/ext/tt/transcribe.rs

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