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.
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.
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
24 //! Quick intro to how the parser works:
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`.
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`.
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
39 //! Example: Start parsing `a a a a b` against [· a $( a )* a b].
41 //! Remaining input: `a a a a b`
42 //! next_eis: [· a $( a )* a b]
44 //! - - - Advance over an `a`. - - -
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].
51 //! - - - Advance over an `a`. - - -
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]
58 //! - - - Advance over an `a`. - - - (this looks exactly like the last step)
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]
65 //! - - - Advance over an `a`. - - - (this looks exactly like the last step)
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]
72 //! - - - Advance over a `b`. - - -
74 //! Remaining input: ``
75 //! eof: [a $( a )* a b ·]
77 pub use self::NamedMatch::*;
78 pub use self::ParseResult::*;
79 use self::TokenTreeOrTokenTreeVec::*;
82 use ast::{TokenTree, Name, Ident};
83 use codemap::{BytePos, mk_sp, Span, Spanned};
85 use parse::lexer::*; //resolve bug?
87 use parse::parser::{LifetimeAndTypesWithoutColons, Parser};
88 use parse::token::{DocComment, MatchNt, SubstNt};
89 use parse::token::{Token, Nonterminal};
96 use std::collections::HashMap;
97 use std::collections::hash_map::Entry::{Vacant, Occupied};
99 // To avoid costly uniqueness checks, we require that `MatchSeq` always has
103 enum TokenTreeOrTokenTreeVec {
105 TtSeq(Rc<Vec<ast::TokenTree>>),
108 impl TokenTreeOrTokenTreeVec {
109 fn len(&self) -> usize {
111 TtSeq(ref v) => v.len(),
112 Tt(ref tt) => tt.len(),
116 fn get_tt(&self, index: usize) -> TokenTree {
118 TtSeq(ref v) => v[index].clone(),
119 Tt(ref tt) => tt.get_tt(index),
124 /// an unzipping of `TokenTree`s
126 struct MatcherTtFrame {
127 elts: TokenTreeOrTokenTreeVec,
132 pub struct MatcherPos {
133 stack: Vec<MatcherTtFrame>,
134 top_elts: TokenTreeOrTokenTreeVec,
137 up: Option<Box<MatcherPos>>,
138 matches: Vec<Vec<Rc<NamedMatch>>>,
145 pub fn count_names(ms: &[TokenTree]) -> usize {
146 ms.iter().fold(0, |count, elt| {
148 TokenTree::Sequence(_, ref seq) => {
151 TokenTree::Delimited(_, ref delim) => {
152 count_names(&delim.tts)
154 TokenTree::Token(_, MatchNt(..)) => {
157 TokenTree::Token(_, _) => 0,
162 pub fn initial_matcher_pos(ms: Rc<Vec<TokenTree>>, sep: Option<Token>, lo: BytePos)
164 let match_idx_hi = count_names(&ms[..]);
165 let matches: Vec<_> = (0..match_idx_hi).map(|_| Vec::new()).collect();
166 Box::new(MatcherPos {
175 match_hi: match_idx_hi,
180 /// NamedMatch is a pattern-match result for a single token::MATCH_NONTERMINAL:
181 /// so it is associated with a single ident in a parse, and all
182 /// `MatchedNonterminal`s in the NamedMatch have the same nonterminal type
183 /// (expr, item, etc). Each leaf in a single NamedMatch corresponds to a
184 /// single token::MATCH_NONTERMINAL in the TokenTree that produced it.
186 /// The in-memory structure of a particular NamedMatch represents the match
187 /// that occurred when a particular subset of a matcher was applied to a
188 /// particular token tree.
190 /// The width of each MatchedSeq in the NamedMatch, and the identity of the
191 /// `MatchedNonterminal`s, will depend on the token tree it was applied to:
192 /// each MatchedSeq corresponds to a single TTSeq in the originating
193 /// token tree. The depth of the NamedMatch structure will therefore depend
194 /// only on the nesting depth of `ast::TTSeq`s in the originating
195 /// token tree it was derived from.
197 pub enum NamedMatch {
198 MatchedSeq(Vec<Rc<NamedMatch>>, codemap::Span),
199 MatchedNonterminal(Nonterminal)
202 pub fn nameize(p_s: &ParseSess, ms: &[TokenTree], res: &[Rc<NamedMatch>])
203 -> ParseResult<HashMap<Name, Rc<NamedMatch>>> {
204 fn n_rec(p_s: &ParseSess, m: &TokenTree, res: &[Rc<NamedMatch>],
205 ret_val: &mut HashMap<Name, Rc<NamedMatch>>, idx: &mut usize)
206 -> Result<(), (codemap::Span, String)> {
208 TokenTree::Sequence(_, ref seq) => {
209 for next_m in &seq.tts {
210 try!(n_rec(p_s, next_m, res, ret_val, idx))
213 TokenTree::Delimited(_, ref delim) => {
214 for next_m in &delim.tts {
215 try!(n_rec(p_s, next_m, res, ret_val, idx));
218 TokenTree::Token(sp, MatchNt(bind_name, _, _, _)) => {
219 match ret_val.entry(bind_name.name) {
221 spot.insert(res[*idx].clone());
225 return Err((sp, format!("duplicated bind name: {}", bind_name)))
229 TokenTree::Token(sp, SubstNt(..)) => {
230 return Err((sp, "missing fragment specifier".to_string()))
232 TokenTree::Token(_, _) => (),
238 let mut ret_val = HashMap::new();
241 match n_rec(p_s, m, res, &mut ret_val, &mut idx) {
243 Err((sp, msg)) => return Error(sp, msg),
250 pub enum ParseResult<T> {
252 /// Arm failed to match
253 Failure(codemap::Span, String),
254 /// Fatal error (malformed macro?). Abort compilation.
255 Error(codemap::Span, String)
258 pub type NamedParseResult = ParseResult<HashMap<Name, Rc<NamedMatch>>>;
259 pub type PositionalParseResult = ParseResult<Vec<Rc<NamedMatch>>>;
261 /// Perform a token equality check, ignoring syntax context (that is, an
262 /// unhygienic comparison)
263 pub fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
265 (&token::Ident(id1,_),&token::Ident(id2,_))
266 | (&token::Lifetime(id1),&token::Lifetime(id2)) =>
267 id1.name == id2.name,
272 pub fn parse(sess: &ParseSess,
273 cfg: ast::CrateConfig,
276 -> NamedParseResult {
277 let mut cur_eis = Vec::new();
278 cur_eis.push(initial_matcher_pos(Rc::new(ms.iter()
285 let mut bb_eis = Vec::new(); // black-box parsed by parser.rs
286 let mut next_eis = Vec::new(); // or proceed normally
287 let mut eof_eis = Vec::new();
289 let TokenAndSpan { tok, sp } = rdr.peek();
291 /* we append new items to this while we go */
293 let mut ei = match cur_eis.pop() {
294 None => break, /* for each Earley Item */
298 // When unzipped trees end, remove them
299 while ei.idx >= ei.top_elts.len() {
300 match ei.stack.pop() {
301 Some(MatcherTtFrame { elts, idx }) => {
310 let len = ei.top_elts.len();
312 /* at end of sequence */
314 // can't move out of `match`es, so:
316 // hack: a matcher sequence is repeating iff it has a
317 // parent (the top level is just a container)
320 // disregard separator, try to go up
321 // (remove this condition to make trailing seps ok)
323 // pop from the matcher position
325 let mut new_pos = ei.up.clone().unwrap();
327 // update matches (the MBE "parse tree") by appending
328 // each tree as a subtree.
330 // I bet this is a perf problem: we're preemptively
331 // doing a lot of array work that will get thrown away
334 // Only touch the binders we have actually bound
335 for idx in ei.match_lo..ei.match_hi {
336 let sub = (ei.matches[idx]).clone();
337 (&mut new_pos.matches[idx])
338 .push(Rc::new(MatchedSeq(sub, mk_sp(ei.sp_lo,
342 new_pos.match_cur = ei.match_hi;
344 cur_eis.push(new_pos);
347 // can we go around again?
349 // the *_t vars are workarounds for the lack of unary move
351 Some(ref t) if idx == len => { // we need a separator
352 // i'm conflicted about whether this should be hygienic....
353 // though in this case, if the separators are never legal
354 // idents, it shouldn't matter.
355 if token_name_eq(&tok, t) { //pass the separator
356 let mut ei_t = ei.clone();
357 // ei_t.match_cur = ei_t.match_lo;
362 _ => { // we don't need a separator
364 ei_t.match_cur = ei_t.match_lo;
373 match ei.top_elts.get_tt(idx) {
374 /* need to descend into sequence */
375 TokenTree::Sequence(sp, seq) => {
376 if seq.op == ast::ZeroOrMore {
377 let mut new_ei = ei.clone();
378 new_ei.match_cur += seq.num_captures;
380 //we specifically matched zero repeats.
381 for idx in ei.match_cur..ei.match_cur + seq.num_captures {
382 (&mut new_ei.matches[idx]).push(Rc::new(MatchedSeq(vec![], sp)));
385 cur_eis.push(new_ei);
388 let matches: Vec<_> = (0..ei.matches.len())
389 .map(|_| Vec::new()).collect();
391 cur_eis.push(Box::new(MatcherPos {
393 sep: seq.separator.clone(),
396 match_lo: ei_t.match_cur,
397 match_cur: ei_t.match_cur,
398 match_hi: ei_t.match_cur + seq.num_captures,
401 top_elts: Tt(TokenTree::Sequence(sp, seq)),
404 TokenTree::Token(_, MatchNt(..)) => {
405 // Built-in nonterminals never start with these tokens,
406 // so we can eliminate them from consideration.
408 token::CloseDelim(_) => {},
409 _ => bb_eis.push(ei),
412 TokenTree::Token(sp, SubstNt(..)) => {
413 return Error(sp, "missing fragment specifier".to_string())
415 seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
416 let lower_elts = mem::replace(&mut ei.top_elts, Tt(seq));
418 ei.stack.push(MatcherTtFrame {
425 TokenTree::Token(_, ref t) => {
426 let mut ei_t = ei.clone();
427 if token_name_eq(t,&tok) {
436 /* error messages here could be improved with links to orig. rules */
437 if token_name_eq(&tok, &token::Eof) {
438 if eof_eis.len() == 1 {
439 let mut v = Vec::new();
440 for dv in &mut (&mut eof_eis[0]).matches {
441 v.push(dv.pop().unwrap());
443 return nameize(sess, ms, &v[..]);
444 } else if eof_eis.len() > 1 {
445 return Error(sp, "ambiguity: multiple successful parses".to_string());
447 return Failure(sp, "unexpected end of macro invocation".to_string());
450 if (!bb_eis.is_empty() && !next_eis.is_empty())
451 || bb_eis.len() > 1 {
452 let nts = bb_eis.iter().map(|ei| match ei.top_elts.get_tt(ei.idx) {
453 TokenTree::Token(_, MatchNt(bind, name, _, _)) => {
454 format!("{} ('{}')", name, bind)
457 }).collect::<Vec<String>>().join(" or ");
459 return Error(sp, format!(
460 "local ambiguity: multiple parsing options: {}",
461 match next_eis.len() {
462 0 => format!("built-in NTs {}.", nts),
463 1 => format!("built-in NTs {} or 1 other option.", nts),
464 n => format!("built-in NTs {} or {} other options.", nts, n),
467 } else if bb_eis.is_empty() && next_eis.is_empty() {
468 return Failure(sp, format!("no rules expected the token `{}`",
469 pprust::token_to_string(&tok)));
470 } else if !next_eis.is_empty() {
471 /* Now process the next token */
472 while !next_eis.is_empty() {
473 cur_eis.push(next_eis.pop().unwrap());
476 } else /* bb_eis.len() == 1 */ {
477 let mut rust_parser = Parser::new(sess, cfg.clone(), Box::new(rdr.clone()));
479 let mut ei = bb_eis.pop().unwrap();
480 match ei.top_elts.get_tt(ei.idx) {
481 TokenTree::Token(span, MatchNt(_, ident, _, _)) => {
482 let match_cur = ei.match_cur;
483 (&mut ei.matches[match_cur]).push(Rc::new(MatchedNonterminal(
484 parse_nt(&mut rust_parser, span, &ident.name.as_str()))));
492 for _ in 0..rust_parser.tokens_consumed {
493 let _ = rdr.next_token();
498 assert!(!cur_eis.is_empty());
502 pub fn parse_nt(p: &mut Parser, sp: Span, name: &str) -> Nonterminal {
505 p.quote_depth += 1; //but in theory, non-quoted tts might be useful
506 let res = token::NtTT(P(panictry!(p.parse_token_tree())));
512 // check at the beginning and the parser checks after each bump
513 panictry!(p.check_unknown_macro_variable());
515 "item" => match panictry!(p.parse_item()) {
516 Some(i) => token::NtItem(i),
517 None => panic!(p.fatal("expected an item keyword"))
519 "block" => token::NtBlock(panictry!(p.parse_block())),
520 "stmt" => match panictry!(p.parse_stmt()) {
521 Some(s) => token::NtStmt(s),
522 None => panic!(p.fatal("expected a statement"))
524 "pat" => token::NtPat(panictry!(p.parse_pat())),
525 "expr" => token::NtExpr(panictry!(p.parse_expr())),
526 "ty" => token::NtTy(panictry!(p.parse_ty())),
527 // this could be handled like a token, since it is one
528 "ident" => match p.token {
529 token::Ident(sn,b) => {
531 token::NtIdent(Box::new(Spanned::<Ident>{node: sn, span: p.span}),b)
534 let token_str = pprust::token_to_string(&p.token);
535 panic!(p.fatal(&format!("expected ident, found {}",
540 token::NtPath(Box::new(panictry!(p.parse_path(LifetimeAndTypesWithoutColons))))
542 "meta" => token::NtMeta(panictry!(p.parse_meta_item())),
544 panic!(p.span_fatal_help(sp,
545 &format!("invalid fragment specifier `{}`", name),
546 "valid fragment specifiers are `ident`, `block`, \
547 `stmt`, `expr`, `pat`, `ty`, `path`, `meta`, `tt` \