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