src/libsyntax/ext/tt/macro_parser.rs

   1 // Copyright 2012-2014 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 //! This is an Earley-like parser, without support for in-grammar nonterminals,
  12 //! only by calling out to the main rust parser for named nonterminals (which it
  13 //! commits to fully when it hits one in a grammar). This means that there are no
  14 //! completer or predictor rules, and therefore no need to store one column per
  15 //! token: instead, there's a set of current Earley items and a set of next
  16 //! ones. Instead of NTs, we have a special case for Kleene star. The big-O, in
  17 //! pathological cases, is worse than traditional Earley parsing, but it's an
  18 //! easier fit for Macro-by-Example-style rules, and I think the overhead is
  19 //! lower. (In order to prevent the pathological case, we'd need to lazily
  20 //! construct the resulting `NamedMatch`es at the very end. It'd be a pain,
  21 //! and require more memory to keep around old items, but it would also save
  22 //! overhead)
  23 //!
  24 //! Quick intro to how the parser works:
  25 //!
  26 //! A 'position' is a dot in the middle of a matcher, usually represented as a
  27 //! dot. For example `· a $( a )* a b` is a position, as is `a $( · a )* a b`.
  28 //!
  29 //! The parser walks through the input a character at a time, maintaining a list
  30 //! of items consistent with the current position in the input string: `cur_eis`.
  31 //!
  32 //! As it processes them, it fills up `eof_eis` with items that would be valid if
  33 //! the macro invocation is now over, `bb_eis` with items that are waiting on
  34 //! a Rust nonterminal like `$e:expr`, and `next_eis` with items that are waiting
  35 //! on a particular token. Most of the logic concerns moving the · through the
  36 //! repetitions indicated by Kleene stars. It only advances or calls out to the
  37 //! real Rust parser when no `cur_eis` items remain
  38 //!
  39 //! Example: Start parsing `a a a a b` against [· a $( a )* a b].
  40 //!
  41 //! Remaining input: `a a a a b`
  42 //! next_eis: [· a $( a )* a b]
  43 //!
  44 //! - - - Advance over an `a`. - - -
  45 //!
  46 //! Remaining input: `a a a b`
  47 //! cur: [a · $( a )* a b]
  48 //! Descend/Skip (first item).
  49 //! next: [a $( · a )* a b]  [a $( a )* · a b].
  50 //!
  51 //! - - - Advance over an `a`. - - -
  52 //!
  53 //! Remaining input: `a a b`
  54 //! cur: [a $( a · )* a b]  next: [a $( a )* a · b]
  55 //! Finish/Repeat (first item)
  56 //! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
  57 //!
  58 //! - - - Advance over an `a`. - - - (this looks exactly like the last step)
  59 //!
  60 //! Remaining input: `a b`
  61 //! cur: [a $( a · )* a b]  next: [a $( a )* a · b]
  62 //! Finish/Repeat (first item)
  63 //! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
  64 //!
  65 //! - - - Advance over an `a`. - - - (this looks exactly like the last step)
  66 //!
  67 //! Remaining input: `b`
  68 //! cur: [a $( a · )* a b]  next: [a $( a )* a · b]
  69 //! Finish/Repeat (first item)
  70 //! next: [a $( a )* · a b]  [a $( · a )* a b]
  71 //!
  72 //! - - - Advance over a `b`. - - -
  73 //!
  74 //! Remaining input: ``
  75 //! eof: [a $( a )* a b ·]
  76
  77 pub use self::NamedMatch::*;
  78 pub use self::ParseResult::*;
  79 use self::TokenTreeOrTokenTreeVec::*;
  80
  81 use ast::Ident;
  82 use syntax_pos::{self, BytePos, Span};
  83 use codemap::Spanned;
  84 use errors::FatalError;
  85 use ext::tt::quoted::{self, TokenTree};
  86 use parse::{Directory, ParseSess};
  87 use parse::parser::{PathStyle, Parser};
  88 use parse::token::{self, DocComment, Token, Nonterminal};
  89 use print::pprust;
  90 use symbol::keywords;
  91 use tokenstream::TokenStream;
  92 use util::small_vector::SmallVector;
  93
  94 use std::mem;
  95 use std::rc::Rc;
  96 use std::collections::HashMap;
  97 use std::collections::hash_map::Entry::{Vacant, Occupied};
  98
  99 // To avoid costly uniqueness checks, we require that `MatchSeq` always has
 100 // a nonempty body.
 101
 102 #[derive(Clone)]
 103 enum TokenTreeOrTokenTreeVec {
 104     Tt(TokenTree),
 105     TtSeq(Vec<TokenTree>),
 106 }
 107
 108 impl TokenTreeOrTokenTreeVec {
 109     fn len(&self) -> usize {
 110         match *self {
 111             TtSeq(ref v) => v.len(),
 112             Tt(ref tt) => tt.len(),
 113         }
 114     }
 115
 116     fn get_tt(&self, index: usize) -> TokenTree {
 117         match *self {
 118             TtSeq(ref v) => v[index].clone(),
 119             Tt(ref tt) => tt.get_tt(index),
 120         }
 121     }
 122 }
 123
 124 /// an unzipping of `TokenTree`s
 125 #[derive(Clone)]
 126 struct MatcherTtFrame {
 127     elts: TokenTreeOrTokenTreeVec,
 128     idx: usize,
 129 }
 130
 131 #[derive(Clone)]
 132 struct MatcherPos {
 133     stack: Vec<MatcherTtFrame>,
 134     top_elts: TokenTreeOrTokenTreeVec,
 135     sep: Option<Token>,
 136     idx: usize,
 137     up: Option<Box<MatcherPos>>,
 138     matches: Vec<Vec<Rc<NamedMatch>>>,
 139     match_lo: usize,
 140     match_cur: usize,
 141     match_hi: usize,
 142     sp_lo: BytePos,
 143 }
 144
 145 pub type NamedParseResult = ParseResult<HashMap<Ident, Rc<NamedMatch>>>;
 146
 147 pub fn count_names(ms: &[TokenTree]) -> usize {
 148     ms.iter().fold(0, |count, elt| {
 149         count + match *elt {
 150             TokenTree::Sequence(_, ref seq) => {
 151                 seq.num_captures
 152             }
 153             TokenTree::Delimited(_, ref delim) => {
 154                 count_names(&delim.tts)
 155             }
 156             TokenTree::MetaVarDecl(..) => {
 157                 1
 158             }
 159             TokenTree::Token(..) => 0,
 160         }
 161     })
 162 }
 163
 164 fn initial_matcher_pos(ms: Vec<TokenTree>, lo: BytePos) -> Box<MatcherPos> {
 165     let match_idx_hi = count_names(&ms[..]);
 166     let matches = create_matches(match_idx_hi);
 167     Box::new(MatcherPos {
 168         stack: vec![],
 169         top_elts: TtSeq(ms),
 170         sep: None,
 171         idx: 0,
 172         up: None,
 173         matches: matches,
 174         match_lo: 0,
 175         match_cur: 0,
 176         match_hi: match_idx_hi,
 177         sp_lo: lo
 178     })
 179 }
 180
 181 /// NamedMatch is a pattern-match result for a single token::MATCH_NONTERMINAL:
 182 /// so it is associated with a single ident in a parse, and all
 183 /// `MatchedNonterminal`s in the NamedMatch have the same nonterminal type
 184 /// (expr, item, etc). Each leaf in a single NamedMatch corresponds to a
 185 /// single token::MATCH_NONTERMINAL in the TokenTree that produced it.
 186 ///
 187 /// The in-memory structure of a particular NamedMatch represents the match
 188 /// that occurred when a particular subset of a matcher was applied to a
 189 /// particular token tree.
 190 ///
 191 /// The width of each MatchedSeq in the NamedMatch, and the identity of the
 192 /// `MatchedNonterminal`s, will depend on the token tree it was applied to:
 193 /// each MatchedSeq corresponds to a single TTSeq in the originating
 194 /// token tree. The depth of the NamedMatch structure will therefore depend
 195 /// only on the nesting depth of `ast::TTSeq`s in the originating
 196 /// token tree it was derived from.
 197
 198 pub enum NamedMatch {
 199     MatchedSeq(Vec<Rc<NamedMatch>>, syntax_pos::Span),
 200     MatchedNonterminal(Rc<Nonterminal>)
 201 }
 202
 203 fn nameize<I: Iterator<Item=Rc<NamedMatch>>>(sess: &ParseSess, ms: &[TokenTree], mut res: I)
 204                                              -> NamedParseResult {
 205     fn n_rec<I: Iterator<Item=Rc<NamedMatch>>>(sess: &ParseSess, m: &TokenTree, mut res: &mut I,
 206              ret_val: &mut HashMap<Ident, Rc<NamedMatch>>)
 207              -> Result<(), (syntax_pos::Span, String)> {
 208         match *m {
 209             TokenTree::Sequence(_, ref seq) => {
 210                 for next_m in &seq.tts {
 211                     n_rec(sess, next_m, res.by_ref(), ret_val)?
 212                 }
 213             }
 214             TokenTree::Delimited(_, ref delim) => {
 215                 for next_m in &delim.tts {
 216                     n_rec(sess, next_m, res.by_ref(), ret_val)?;
 217                 }
 218             }
 219             TokenTree::MetaVarDecl(span, _, id) if id.name == keywords::Invalid.name() => {
 220                 if sess.missing_fragment_specifiers.borrow_mut().remove(&span) {
 221                     return Err((span, "missing fragment specifier".to_string()));
 222                 }
 223             }
 224             TokenTree::MetaVarDecl(sp, bind_name, _) => {
 225                 match ret_val.entry(bind_name) {
 226                     Vacant(spot) => {
 227                         spot.insert(res.next().unwrap());
 228                     }
 229                     Occupied(..) => {
 230                         return Err((sp, format!("duplicated bind name: {}", bind_name)))
 231                     }
 232                 }
 233             }
 234             TokenTree::Token(..) => (),
 235         }
 236
 237         Ok(())
 238     }
 239
 240     let mut ret_val = HashMap::new();
 241     for m in ms {
 242         match n_rec(sess, m, res.by_ref(), &mut ret_val) {
 243             Ok(_) => {},
 244             Err((sp, msg)) => return Error(sp, msg),
 245         }
 246     }
 247
 248     Success(ret_val)
 249 }
 250
 251 pub enum ParseResult<T> {
 252     Success(T),
 253     /// Arm failed to match. If the second parameter is `token::Eof`, it
 254     /// indicates an unexpected end of macro invocation. Otherwise, it
 255     /// indicates that no rules expected the given token.
 256     Failure(syntax_pos::Span, Token),
 257     /// Fatal error (malformed macro?). Abort compilation.
 258     Error(syntax_pos::Span, String)
 259 }
 260
 261 pub fn parse_failure_msg(tok: Token) -> String {
 262     match tok {
 263         token::Eof => "unexpected end of macro invocation".to_string(),
 264         _ => format!("no rules expected the token `{}`", pprust::token_to_string(&tok)),
 265     }
 266 }
 267
 268 /// Perform a token equality check, ignoring syntax context (that is, an unhygienic comparison)
 269 fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
 270     match (t1,t2) {
 271         (&token::Ident(id1),&token::Ident(id2))
 272         | (&token::Lifetime(id1),&token::Lifetime(id2)) =>
 273             id1.name == id2.name,
 274         _ => *t1 == *t2
 275     }
 276 }
 277
 278 fn create_matches(len: usize) -> Vec<Vec<Rc<NamedMatch>>> {
 279     (0..len).into_iter().map(|_| Vec::new()).collect()
 280 }
 281
 282 fn inner_parse_loop(sess: &ParseSess,
 283                     cur_eis: &mut SmallVector<Box<MatcherPos>>,
 284                     next_eis: &mut Vec<Box<MatcherPos>>,
 285                     eof_eis: &mut SmallVector<Box<MatcherPos>>,
 286                     bb_eis: &mut SmallVector<Box<MatcherPos>>,
 287                     token: &Token,
 288                     span: syntax_pos::Span)
 289                     -> ParseResult<()> {
 290     while let Some(mut ei) = cur_eis.pop() {
 291         // When unzipped trees end, remove them
 292         while ei.idx >= ei.top_elts.len() {
 293             match ei.stack.pop() {
 294                 Some(MatcherTtFrame { elts, idx }) => {
 295                     ei.top_elts = elts;
 296                     ei.idx = idx + 1;
 297                 }
 298                 None => break
 299             }
 300         }
 301
 302         let idx = ei.idx;
 303         let len = ei.top_elts.len();
 304
 305         // at end of sequence
 306         if idx >= len {
 307             // We are repeating iff there is a parent
 308             if ei.up.is_some() {
 309                 // Disregarding the separator, add the "up" case to the tokens that should be
 310                 // examined.
 311                 // (remove this condition to make trailing seps ok)
 312                 if idx == len {
 313                     let mut new_pos = ei.up.clone().unwrap();
 314
 315                     // update matches (the MBE "parse tree") by appending
 316                     // each tree as a subtree.
 317
 318                     // I bet this is a perf problem: we're preemptively
 319                     // doing a lot of array work that will get thrown away
 320                     // most of the time.
 321
 322                     // Only touch the binders we have actually bound
 323                     for idx in ei.match_lo..ei.match_hi {
 324                         let sub = ei.matches[idx].clone();
 325                         new_pos.matches[idx]
 326                             .push(Rc::new(MatchedSeq(sub, Span { lo: ei.sp_lo, ..span })));
 327                     }
 328
 329                     new_pos.match_cur = ei.match_hi;
 330                     new_pos.idx += 1;
 331                     cur_eis.push(new_pos);
 332                 }
 333
 334                 // Check if we need a separator
 335                 if idx == len && ei.sep.is_some() {
 336                     // We have a separator, and it is the current token.
 337                     if ei.sep.as_ref().map(|ref sep| token_name_eq(&token, sep)).unwrap_or(false) {
 338                         ei.idx += 1;
 339                         next_eis.push(ei);
 340                     }
 341                 } else { // we don't need a separator
 342                     ei.match_cur = ei.match_lo;
 343                     ei.idx = 0;
 344                     cur_eis.push(ei);
 345                 }
 346             } else {
 347                 // We aren't repeating, so we must be potentially at the end of the input.
 348                 eof_eis.push(ei);
 349             }
 350         } else {
 351             match ei.top_elts.get_tt(idx) {
 352                 /* need to descend into sequence */
 353                 TokenTree::Sequence(sp, seq) => {
 354                     if seq.op == quoted::KleeneOp::ZeroOrMore {
 355                         // Examine the case where there are 0 matches of this sequence
 356                         let mut new_ei = ei.clone();
 357                         new_ei.match_cur += seq.num_captures;
 358                         new_ei.idx += 1;
 359                         for idx in ei.match_cur..ei.match_cur + seq.num_captures {
 360                             new_ei.matches[idx].push(Rc::new(MatchedSeq(vec![], sp)));
 361                         }
 362                         cur_eis.push(new_ei);
 363                     }
 364
 365                     // Examine the case where there is at least one match of this sequence
 366                     let matches = create_matches(ei.matches.len());
 367                     cur_eis.push(Box::new(MatcherPos {
 368                         stack: vec![],
 369                         sep: seq.separator.clone(),
 370                         idx: 0,
 371                         matches: matches,
 372                         match_lo: ei.match_cur,
 373                         match_cur: ei.match_cur,
 374                         match_hi: ei.match_cur + seq.num_captures,
 375                         up: Some(ei),
 376                         sp_lo: sp.lo,
 377                         top_elts: Tt(TokenTree::Sequence(sp, seq)),
 378                     }));
 379                 }
 380                 TokenTree::MetaVarDecl(span, _, id) if id.name == keywords::Invalid.name() => {
 381                     if sess.missing_fragment_specifiers.borrow_mut().remove(&span) {
 382                         return Error(span, "missing fragment specifier".to_string());
 383                     }
 384                 }
 385                 TokenTree::MetaVarDecl(..) => {
 386                     // Built-in nonterminals never start with these tokens,
 387                     // so we can eliminate them from consideration.
 388                     match *token {
 389                         token::CloseDelim(_) => {},
 390                         _ => bb_eis.push(ei),
 391                     }
 392                 }
 393                 seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
 394                     let lower_elts = mem::replace(&mut ei.top_elts, Tt(seq));
 395                     let idx = ei.idx;
 396                     ei.stack.push(MatcherTtFrame {
 397                         elts: lower_elts,
 398                         idx: idx,
 399                     });
 400                     ei.idx = 0;
 401                     cur_eis.push(ei);
 402                 }
 403                 TokenTree::Token(_, ref t) => {
 404                     if token_name_eq(t, &token) {
 405                         ei.idx += 1;
 406                         next_eis.push(ei);
 407                     }
 408                 }
 409             }
 410         }
 411     }
 412
 413     Success(())
 414 }
 415
 416 pub fn parse(sess: &ParseSess, tts: TokenStream, ms: &[TokenTree], directory: Option<Directory>)
 417              -> NamedParseResult {
 418     let mut parser = Parser::new(sess, tts, directory, true);
 419     let mut cur_eis = SmallVector::one(initial_matcher_pos(ms.to_owned(), parser.span.lo));
 420     let mut next_eis = Vec::new(); // or proceed normally
 421
 422     loop {
 423         let mut bb_eis = SmallVector::new(); // black-box parsed by parser.rs
 424         let mut eof_eis = SmallVector::new();
 425         assert!(next_eis.is_empty());
 426
 427         match inner_parse_loop(sess, &mut cur_eis, &mut next_eis, &mut eof_eis, &mut bb_eis,
 428                                &parser.token, parser.span) {
 429             Success(_) => {},
 430             Failure(sp, tok) => return Failure(sp, tok),
 431             Error(sp, msg) => return Error(sp, msg),
 432         }
 433
 434         // inner parse loop handled all cur_eis, so it's empty
 435         assert!(cur_eis.is_empty());
 436
 437         /* error messages here could be improved with links to orig. rules */
 438         if token_name_eq(&parser.token, &token::Eof) {
 439             if eof_eis.len() == 1 {
 440                 let matches = eof_eis[0].matches.iter_mut().map(|mut dv| dv.pop().unwrap());
 441                 return nameize(sess, ms, matches);
 442             } else if eof_eis.len() > 1 {
 443                 return Error(parser.span, "ambiguity: multiple successful parses".to_string());
 444             } else {
 445                 return Failure(parser.span, token::Eof);
 446             }
 447         } else if (!bb_eis.is_empty() && !next_eis.is_empty()) || bb_eis.len() > 1 {
 448             let nts = bb_eis.iter().map(|ei| match ei.top_elts.get_tt(ei.idx) {
 449                 TokenTree::MetaVarDecl(_, bind, name) => {
 450                     format!("{} ('{}')", name, bind)
 451                 }
 452                 _ => panic!()
 453             }).collect::<Vec<String>>().join(" or ");
 454
 455             return Error(parser.span, format!(
 456                 "local ambiguity: multiple parsing options: {}",
 457                 match next_eis.len() {
 458                     0 => format!("built-in NTs {}.", nts),
 459                     1 => format!("built-in NTs {} or 1 other option.", nts),
 460                     n => format!("built-in NTs {} or {} other options.", nts, n),
 461                 }
 462             ));
 463         } else if bb_eis.is_empty() && next_eis.is_empty() {
 464             return Failure(parser.span, parser.token);
 465         } else if !next_eis.is_empty() {
 466             /* Now process the next token */
 467             cur_eis.extend(next_eis.drain(..));
 468             parser.bump();
 469         } else /* bb_eis.len() == 1 */ {
 470             let mut ei = bb_eis.pop().unwrap();
 471             if let TokenTree::MetaVarDecl(span, _, ident) = ei.top_elts.get_tt(ei.idx) {
 472                 let match_cur = ei.match_cur;
 473                 ei.matches[match_cur].push(Rc::new(MatchedNonterminal(
 474                             Rc::new(parse_nt(&mut parser, span, &ident.name.as_str())))));
 475                 ei.idx += 1;
 476                 ei.match_cur += 1;
 477             } else {
 478                 unreachable!()
 479             }
 480             cur_eis.push(ei);
 481         }
 482
 483         assert!(!cur_eis.is_empty());
 484     }
 485 }
 486
 487 fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
 488     match name {
 489         "tt" => {
 490             return token::NtTT(p.parse_token_tree());
 491         }
 492         _ => {}
 493     }
 494     // check at the beginning and the parser checks after each bump
 495     p.process_potential_macro_variable();
 496     match name {
 497         "item" => match panictry!(p.parse_item()) {
 498             Some(i) => token::NtItem(i),
 499             None => {
 500                 p.fatal("expected an item keyword").emit();
 501                 panic!(FatalError);
 502             }
 503         },
 504         "block" => token::NtBlock(panictry!(p.parse_block())),
 505         "stmt" => match panictry!(p.parse_stmt()) {
 506             Some(s) => token::NtStmt(s),
 507             None => {
 508                 p.fatal("expected a statement").emit();
 509                 panic!(FatalError);
 510             }
 511         },
 512         "pat" => token::NtPat(panictry!(p.parse_pat())),
 513         "expr" => token::NtExpr(panictry!(p.parse_expr())),
 514         "ty" => token::NtTy(panictry!(p.parse_ty())),
 515         // this could be handled like a token, since it is one
 516         "ident" => match p.token {
 517             token::Ident(sn) => {
 518                 p.bump();
 519                 token::NtIdent(Spanned::<Ident>{node: sn, span: p.prev_span})
 520             }
 521             _ => {
 522                 let token_str = pprust::token_to_string(&p.token);
 523                 p.fatal(&format!("expected ident, found {}",
 524                                  &token_str[..])).emit();
 525                 panic!(FatalError)
 526             }
 527         },
 528         "path" => {
 529             token::NtPath(panictry!(p.parse_path(PathStyle::Type)))
 530         },
 531         "meta" => token::NtMeta(panictry!(p.parse_meta_item())),
 532         "vis" => token::NtVis(panictry!(p.parse_visibility(true))),
 533         // this is not supposed to happen, since it has been checked
 534         // when compiling the macro.
 535         _ => p.span_bug(sp, "invalid fragment specifier")
 536     }
 537 }