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};
83 use codemap::{BytePos, mk_sp, Span};
85 use parse::lexer::*; //resolve bug?
87 use parse::parser::{LifetimeAndTypesWithoutColons, Parser};
88 use parse::token::{Eof, 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 -> 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) {
207 TokenTree::Sequence(_, ref seq) => {
208 for next_m in &seq.tts {
209 n_rec(p_s, next_m, res, ret_val, idx)
212 TokenTree::Delimited(_, ref delim) => {
213 for next_m in &delim.tts {
214 n_rec(p_s, next_m, res, ret_val, idx)
217 TokenTree::Token(sp, MatchNt(bind_name, _, _, _)) => {
218 match ret_val.entry(bind_name.name) {
220 spot.insert(res[*idx].clone());
224 panic!(p_s.span_diagnostic
226 &format!("duplicated bind name: {}",
231 TokenTree::Token(_, SubstNt(..)) => panic!("Cannot fill in a NT"),
232 TokenTree::Token(_, _) => (),
235 let mut ret_val = HashMap::new();
237 for m in ms { n_rec(p_s, m, res, &mut ret_val, &mut idx) }
241 pub enum ParseResult<T> {
243 Failure(codemap::Span, String),
244 Error(codemap::Span, String)
247 pub type NamedParseResult = ParseResult<HashMap<Name, Rc<NamedMatch>>>;
248 pub type PositionalParseResult = ParseResult<Vec<Rc<NamedMatch>>>;
250 /// Perform a token equality check, ignoring syntax context (that is, an
251 /// unhygienic comparison)
252 pub fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
254 (&token::Ident(id1,_),&token::Ident(id2,_))
255 | (&token::Lifetime(id1),&token::Lifetime(id2)) =>
256 id1.name == id2.name,
261 pub fn parse(sess: &ParseSess,
262 cfg: ast::CrateConfig,
265 -> NamedParseResult {
266 let mut cur_eis = Vec::new();
267 cur_eis.push(initial_matcher_pos(Rc::new(ms.iter()
274 let mut bb_eis = Vec::new(); // black-box parsed by parser.rs
275 let mut next_eis = Vec::new(); // or proceed normally
276 let mut eof_eis = Vec::new();
278 let TokenAndSpan { tok, sp } = rdr.peek();
280 /* we append new items to this while we go */
282 let mut ei = match cur_eis.pop() {
283 None => break, /* for each Earley Item */
287 // When unzipped trees end, remove them
288 while ei.idx >= ei.top_elts.len() {
289 match ei.stack.pop() {
290 Some(MatcherTtFrame { elts, idx }) => {
299 let len = ei.top_elts.len();
301 /* at end of sequence */
303 // can't move out of `match`es, so:
305 // hack: a matcher sequence is repeating iff it has a
306 // parent (the top level is just a container)
309 // disregard separator, try to go up
310 // (remove this condition to make trailing seps ok)
312 // pop from the matcher position
314 let mut new_pos = ei.up.clone().unwrap();
316 // update matches (the MBE "parse tree") by appending
317 // each tree as a subtree.
319 // I bet this is a perf problem: we're preemptively
320 // doing a lot of array work that will get thrown away
323 // Only touch the binders we have actually bound
324 for idx in ei.match_lo..ei.match_hi {
325 let sub = (ei.matches[idx]).clone();
326 (&mut new_pos.matches[idx])
327 .push(Rc::new(MatchedSeq(sub, mk_sp(ei.sp_lo,
331 new_pos.match_cur = ei.match_hi;
333 cur_eis.push(new_pos);
336 // can we go around again?
338 // the *_t vars are workarounds for the lack of unary move
340 Some(ref t) if idx == len => { // we need a separator
341 // i'm conflicted about whether this should be hygienic....
342 // though in this case, if the separators are never legal
343 // idents, it shouldn't matter.
344 if token_name_eq(&tok, t) { //pass the separator
345 let mut ei_t = ei.clone();
346 // ei_t.match_cur = ei_t.match_lo;
351 _ => { // we don't need a separator
353 ei_t.match_cur = ei_t.match_lo;
362 match ei.top_elts.get_tt(idx) {
363 /* need to descend into sequence */
364 TokenTree::Sequence(sp, seq) => {
365 if seq.op == ast::ZeroOrMore {
366 let mut new_ei = ei.clone();
367 new_ei.match_cur += seq.num_captures;
369 //we specifically matched zero repeats.
370 for idx in ei.match_cur..ei.match_cur + seq.num_captures {
371 (&mut new_ei.matches[idx]).push(Rc::new(MatchedSeq(vec![], sp)));
374 cur_eis.push(new_ei);
377 let matches: Vec<_> = (0..ei.matches.len())
378 .map(|_| Vec::new()).collect();
380 cur_eis.push(Box::new(MatcherPos {
382 sep: seq.separator.clone(),
385 match_lo: ei_t.match_cur,
386 match_cur: ei_t.match_cur,
387 match_hi: ei_t.match_cur + seq.num_captures,
390 top_elts: Tt(TokenTree::Sequence(sp, seq)),
393 TokenTree::Token(_, MatchNt(..)) => {
394 // Built-in nonterminals never start with these tokens,
395 // so we can eliminate them from consideration.
397 token::CloseDelim(_) => {},
398 _ => bb_eis.push(ei),
401 TokenTree::Token(sp, SubstNt(..)) => {
402 return Error(sp, "missing fragment specifier".to_string())
404 seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
405 let lower_elts = mem::replace(&mut ei.top_elts, Tt(seq));
407 ei.stack.push(MatcherTtFrame {
414 TokenTree::Token(_, ref t) => {
415 let mut ei_t = ei.clone();
416 if token_name_eq(t,&tok) {
425 /* error messages here could be improved with links to orig. rules */
426 if token_name_eq(&tok, &token::Eof) {
427 if eof_eis.len() == 1 {
428 let mut v = Vec::new();
429 for dv in &mut (&mut eof_eis[0]).matches {
430 v.push(dv.pop().unwrap());
432 return Success(nameize(sess, ms, &v[..]));
433 } else if eof_eis.len() > 1 {
434 return Error(sp, "ambiguity: multiple successful parses".to_string());
436 return Failure(sp, "unexpected end of macro invocation".to_string());
439 if (!bb_eis.is_empty() && !next_eis.is_empty())
440 || bb_eis.len() > 1 {
441 let nts = bb_eis.iter().map(|ei| match ei.top_elts.get_tt(ei.idx) {
442 TokenTree::Token(_, MatchNt(bind, name, _, _)) => {
443 format!("{} ('{}')", name, bind)
446 }).collect::<Vec<String>>().join(" or ");
448 return Error(sp, format!(
449 "local ambiguity: multiple parsing options: {}",
450 match next_eis.len() {
451 0 => format!("built-in NTs {}.", nts),
452 1 => format!("built-in NTs {} or 1 other option.", nts),
453 n => format!("built-in NTs {} or {} other options.", nts, n),
456 } else if bb_eis.is_empty() && next_eis.is_empty() {
457 return Failure(sp, format!("no rules expected the token `{}`",
458 pprust::token_to_string(&tok)));
459 } else if !next_eis.is_empty() {
460 /* Now process the next token */
461 while !next_eis.is_empty() {
462 cur_eis.push(next_eis.pop().unwrap());
465 } else /* bb_eis.len() == 1 */ {
466 let mut rust_parser = Parser::new(sess, cfg.clone(), Box::new(rdr.clone()));
468 let mut ei = bb_eis.pop().unwrap();
469 match ei.top_elts.get_tt(ei.idx) {
470 TokenTree::Token(span, MatchNt(_, ident, _, _)) => {
471 let match_cur = ei.match_cur;
472 (&mut ei.matches[match_cur]).push(Rc::new(MatchedNonterminal(
473 parse_nt(&mut rust_parser, span, &ident.name.as_str()))));
481 for _ in 0..rust_parser.tokens_consumed {
482 let _ = rdr.next_token();
487 assert!(!cur_eis.is_empty());
491 pub fn parse_nt(p: &mut Parser, sp: Span, name: &str) -> Nonterminal {
494 p.quote_depth += 1; //but in theory, non-quoted tts might be useful
495 let res = token::NtTT(P(panictry!(p.parse_token_tree())));
501 // check at the beginning and the parser checks after each bump
502 panictry!(p.check_unknown_macro_variable());
504 "item" => match panictry!(p.parse_item()) {
505 Some(i) => token::NtItem(i),
506 None => panic!(p.fatal("expected an item keyword"))
508 "block" => token::NtBlock(panictry!(p.parse_block())),
509 "stmt" => match panictry!(p.parse_stmt()) {
510 Some(s) => token::NtStmt(s),
511 None => panic!(p.fatal("expected a statement"))
513 "pat" => token::NtPat(panictry!(p.parse_pat())),
514 "expr" => token::NtExpr(panictry!(p.parse_expr())),
515 "ty" => token::NtTy(panictry!(p.parse_ty())),
516 // this could be handled like a token, since it is one
517 "ident" => match p.token {
518 token::Ident(sn,b) => { panictry!(p.bump()); token::NtIdent(Box::new(sn),b) }
520 let token_str = pprust::token_to_string(&p.token);
521 panic!(p.fatal(&format!("expected ident, found {}",
526 token::NtPath(Box::new(panictry!(p.parse_path(LifetimeAndTypesWithoutColons))))
528 "meta" => token::NtMeta(panictry!(p.parse_meta_item())),
530 panic!(p.span_fatal_help(sp,
531 &format!("invalid fragment specifier `{}`", name),
532 "valid fragment specifiers are `ident`, `block`, \
533 `stmt`, `expr`, `pat`, `ty`, `path`, `meta`, `tt` \