src/libsyntax/ext/tt/transcribe.rs

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