pub use self::NamedMatch::*;
pub use self::ParseResult::*;
use self::TokenTreeOrTokenTreeSlice::*;
use ast::Ident;
use syntax_pos::{self, Span};
use errors::FatalError;
use ext::tt::quoted::{self, TokenTree};
use parse::{Directory, ParseSess};
use parse::parser::{Parser, PathStyle};
use parse::token::{self, DocComment, Nonterminal, Token};
use print::pprust;
use smallvec::SmallVec;
use symbol::keywords;
use tokenstream::{DelimSpan, TokenStream};
use rustc_data_structures::fx::FxHashMap;
use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::mem;
use std::ops::{Deref, DerefMut};
use std::rc::Rc;
#[derive(Clone)]
enum TokenTreeOrTokenTreeSlice<'tt> {
Tt(TokenTree),
TtSeq(&'tt [TokenTree]),
}
impl<'tt> TokenTreeOrTokenTreeSlice<'tt> {
fn len(&self) -> usize {
match *self {
TtSeq(ref v) => v.len(),
Tt(ref tt) => tt.len(),
}
}
fn get_tt(&self, index: usize) -> TokenTree {
match *self {
TtSeq(ref v) => v[index].clone(),
Tt(ref tt) => tt.get_tt(index),
}
}
}
#[derive(Clone)]
struct MatcherTtFrame<'tt> {
elts: TokenTreeOrTokenTreeSlice<'tt>,
idx: usize,
}
type NamedMatchVec = SmallVec<[NamedMatch; 4]>;
#[derive(Clone)]
struct MatcherPos<'root, 'tt: 'root> {
top_elts: TokenTreeOrTokenTreeSlice<'tt>,
idx: usize,
sp_open: Span,
matches: Box<[Rc<NamedMatchVec>]>,
match_lo: usize,
match_cur: usize,
match_hi: usize,
seq_op: Option<quoted::KleeneOp>,
sep: Option<Token>,
up: Option<MatcherPosHandle<'root, 'tt>>,
stack: SmallVec<[MatcherTtFrame<'tt>; 1]>,
}
impl<'root, 'tt> MatcherPos<'root, 'tt> {
fn push_match(&mut self, idx: usize, m: NamedMatch) {
let matches = Rc::make_mut(&mut self.matches[idx]);
matches.push(m);
}
}
enum MatcherPosHandle<'root, 'tt: 'root> {
Ref(&'root mut MatcherPos<'root, 'tt>),
Box(Box<MatcherPos<'root, 'tt>>),
}
impl<'root, 'tt> Clone for MatcherPosHandle<'root, 'tt> {
fn clone(&self) -> Self {
MatcherPosHandle::Box(match *self {
MatcherPosHandle::Ref(ref r) => Box::new((**r).clone()),
MatcherPosHandle::Box(ref b) => b.clone(),
})
}
}
impl<'root, 'tt> Deref for MatcherPosHandle<'root, 'tt> {
type Target = MatcherPos<'root, 'tt>;
fn deref(&self) -> &Self::Target {
match *self {
MatcherPosHandle::Ref(ref r) => r,
MatcherPosHandle::Box(ref b) => b,
}
}
}
impl<'root, 'tt> DerefMut for MatcherPosHandle<'root, 'tt> {
fn deref_mut(&mut self) -> &mut MatcherPos<'root, 'tt> {
match *self {
MatcherPosHandle::Ref(ref mut r) => r,
MatcherPosHandle::Box(ref mut b) => b,
}
}
}
pub enum ParseResult<T> {
Success(T),
Failure(syntax_pos::Span, Token, String),
Error(syntax_pos::Span, String),
}
pub type NamedParseResult = ParseResult<FxHashMap<Ident, Rc<NamedMatch>>>;
pub fn count_names(ms: &[TokenTree]) -> usize {
ms.iter().fold(0, |count, elt| {
count + match *elt {
TokenTree::Sequence(_, ref seq) => seq.num_captures,
TokenTree::Delimited(_, ref delim) => count_names(&delim.tts),
TokenTree::MetaVar(..) => 0,
TokenTree::MetaVarDecl(..) => 1,
TokenTree::Token(..) => 0,
}
})
}
fn create_matches(len: usize) -> Box<[Rc<NamedMatchVec>]> {
if len == 0 {
vec![]
} else {
let empty_matches = Rc::new(SmallVec::new());
vec![empty_matches; len]
}.into_boxed_slice()
}
fn initial_matcher_pos<'root, 'tt>(ms: &'tt [TokenTree], open: Span) -> MatcherPos<'root, 'tt> {
let match_idx_hi = count_names(ms);
let matches = create_matches(match_idx_hi);
MatcherPos {
top_elts: TtSeq(ms), idx: 0,
sp_open: open,
matches,
match_lo: 0,
match_cur: 0,
match_hi: match_idx_hi,
stack: smallvec![],
seq_op: None,
sep: None,
up: None,
}
}
#[derive(Debug, Clone)]
pub enum NamedMatch {
MatchedSeq(Rc<NamedMatchVec>, DelimSpan),
MatchedNonterminal(Rc<Nonterminal>),
}
fn nameize<I: Iterator<Item = NamedMatch>>(
sess: &ParseSess,
ms: &[TokenTree],
mut res: I,
) -> NamedParseResult {
fn n_rec<I: Iterator<Item = NamedMatch>>(
sess: &ParseSess,
m: &TokenTree,
res: &mut I,
ret_val: &mut FxHashMap<Ident, Rc<NamedMatch>>,
) -> Result<(), (syntax_pos::Span, String)> {
match *m {
TokenTree::Sequence(_, ref seq) => for next_m in &seq.tts {
n_rec(sess, next_m, res.by_ref(), ret_val)?
},
TokenTree::Delimited(_, ref delim) => for next_m in &delim.tts {
n_rec(sess, next_m, res.by_ref(), ret_val)?;
},
TokenTree::MetaVarDecl(span, _, id) if id.name == keywords::Invalid.name() => {
if sess.missing_fragment_specifiers.borrow_mut().remove(&span) {
return Err((span, "missing fragment specifier".to_string()));
}
}
TokenTree::MetaVarDecl(sp, bind_name, _) => {
match ret_val.entry(bind_name) {
Vacant(spot) => {
spot.insert(Rc::new(res.next().unwrap()));
}
Occupied(..) => {
return Err((sp, format!("duplicated bind name: {}", bind_name)))
}
}
}
TokenTree::MetaVar(..) | TokenTree::Token(..) => (),
}
Ok(())
}
let mut ret_val = FxHashMap::default();
for m in ms {
match n_rec(sess, m, res.by_ref(), &mut ret_val) {
Ok(_) => {}
Err((sp, msg)) => return Error(sp, msg),
}
}
Success(ret_val)
}
pub fn parse_failure_msg(tok: Token) -> String {
match tok {
token::Eof => "unexpected end of macro invocation".to_string(),
_ => format!(
"no rules expected the token `{}`",
pprust::token_to_string(&tok)
),
}
}
fn token_name_eq(t1: &Token, t2: &Token) -> bool {
if let (Some((id1, is_raw1)), Some((id2, is_raw2))) = (t1.ident(), t2.ident()) {
id1.name == id2.name && is_raw1 == is_raw2
} else if let (Some(id1), Some(id2)) = (t1.lifetime(), t2.lifetime()) {
id1.name == id2.name
} else {
*t1 == *t2
}
}
fn inner_parse_loop<'root, 'tt>(
sess: &ParseSess,
cur_items: &mut SmallVec<[MatcherPosHandle<'root, 'tt>; 1]>,
next_items: &mut Vec<MatcherPosHandle<'root, 'tt>>,
eof_items: &mut SmallVec<[MatcherPosHandle<'root, 'tt>; 1]>,
bb_items: &mut SmallVec<[MatcherPosHandle<'root, 'tt>; 1]>,
token: &Token,
span: syntax_pos::Span,
) -> ParseResult<()> {
while let Some(mut item) = cur_items.pop() {
while item.idx >= item.top_elts.len() {
match item.stack.pop() {
Some(MatcherTtFrame { elts, idx }) => {
item.top_elts = elts;
item.idx = idx + 1;
}
None => break,
}
}
let idx = item.idx;
let len = item.top_elts.len();
if idx >= len {
if item.up.is_some() {
if idx == len {
let mut new_pos = item.up.clone().unwrap();
for idx in item.match_lo..item.match_hi {
let sub = item.matches[idx].clone();
let span = DelimSpan::from_pair(item.sp_open, span);
new_pos.push_match(idx, MatchedSeq(sub, span));
}
new_pos.match_cur = item.match_hi;
new_pos.idx += 1;
cur_items.push(new_pos);
}
if idx == len && item.sep.is_some() {
if item.sep
.as_ref()
.map(|sep| token_name_eq(token, sep))
.unwrap_or(false)
{
item.idx += 1;
next_items.push(item);
}
}
else if item.seq_op != Some(quoted::KleeneOp::ZeroOrOne) {
item.match_cur = item.match_lo;
item.idx = 0;
cur_items.push(item);
}
}
else {
eof_items.push(item);
}
}
else {
match item.top_elts.get_tt(idx) {
TokenTree::Sequence(sp, seq) => {
if seq.op == quoted::KleeneOp::ZeroOrMore
|| seq.op == quoted::KleeneOp::ZeroOrOne
{
let mut new_item = item.clone();
new_item.match_cur += seq.num_captures;
new_item.idx += 1;
for idx in item.match_cur..item.match_cur + seq.num_captures {
new_item.push_match(idx, MatchedSeq(Rc::new(smallvec![]), sp));
}
cur_items.push(new_item);
}
let matches = create_matches(item.matches.len());
cur_items.push(MatcherPosHandle::Box(Box::new(MatcherPos {
stack: smallvec![],
sep: seq.separator.clone(),
seq_op: Some(seq.op),
idx: 0,
matches,
match_lo: item.match_cur,
match_cur: item.match_cur,
match_hi: item.match_cur + seq.num_captures,
up: Some(item),
sp_open: sp.open,
top_elts: Tt(TokenTree::Sequence(sp, seq)),
})));
}
TokenTree::MetaVarDecl(span, _, id) if id.name == keywords::Invalid.name() => {
if sess.missing_fragment_specifiers.borrow_mut().remove(&span) {
return Error(span, "missing fragment specifier".to_string());
}
}
TokenTree::MetaVarDecl(_, _, id) => {
if may_begin_with(&*id.as_str(), token) {
bb_items.push(item);
}
}
seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
let lower_elts = mem::replace(&mut item.top_elts, Tt(seq));
let idx = item.idx;
item.stack.push(MatcherTtFrame {
elts: lower_elts,
idx,
});
item.idx = 0;
cur_items.push(item);
}
TokenTree::Token(_, ref t) if token_name_eq(t, token) => {
item.idx += 1;
next_items.push(item);
}
TokenTree::Token(..) | TokenTree::MetaVar(..) => {}
}
}
}
Success(())
}
pub fn parse(
sess: &ParseSess,
tts: TokenStream,
ms: &[TokenTree],
directory: Option<Directory>,
recurse_into_modules: bool,
) -> NamedParseResult {
let mut parser = Parser::new(sess, tts, directory, recurse_into_modules, true);
let mut initial = initial_matcher_pos(ms, parser.span);
let mut cur_items = smallvec![MatcherPosHandle::Ref(&mut initial)];
let mut next_items = Vec::new();
loop {
let mut bb_items = SmallVec::new();
let mut eof_items = SmallVec::new();
assert!(next_items.is_empty());
match inner_parse_loop(
sess,
&mut cur_items,
&mut next_items,
&mut eof_items,
&mut bb_items,
&parser.token,
parser.span,
) {
Success(_) => {}
Failure(sp, tok, t) => return Failure(sp, tok, t),
Error(sp, msg) => return Error(sp, msg),
}
assert!(cur_items.is_empty());
if token_name_eq(&parser.token, &token::Eof) {
if eof_items.len() == 1 {
let matches = eof_items[0]
.matches
.iter_mut()
.map(|dv| Rc::make_mut(dv).pop().unwrap());
return nameize(sess, ms, matches);
} else if eof_items.len() > 1 {
return Error(
parser.span,
"ambiguity: multiple successful parses".to_string(),
);
} else {
return Failure(
if parser.span.is_dummy() {
parser.span
} else {
sess.source_map().next_point(parser.span)
},
token::Eof,
"missing tokens in macro arguments".to_string(),
);
}
}
drop(eof_items);
if (!bb_items.is_empty() && !next_items.is_empty()) || bb_items.len() > 1 {
let nts = bb_items
.iter()
.map(|item| match item.top_elts.get_tt(item.idx) {
TokenTree::MetaVarDecl(_, bind, name) => format!("{} ('{}')", name, bind),
_ => panic!(),
})
.collect::<Vec<String>>()
.join(" or ");
return Error(
parser.span,
format!(
"local ambiguity: multiple parsing options: {}",
match next_items.len() {
0 => format!("built-in NTs {}.", nts),
1 => format!("built-in NTs {} or 1 other option.", nts),
n => format!("built-in NTs {} or {} other options.", nts, n),
}
),
);
}
else if bb_items.is_empty() && next_items.is_empty() {
return Failure(
parser.span,
parser.token,
"no rules expected this token in macro call".to_string(),
);
}
else if !next_items.is_empty() {
cur_items.extend(next_items.drain(..));
parser.bump();
}
else {
assert_eq!(bb_items.len(), 1);
let mut item = bb_items.pop().unwrap();
if let TokenTree::MetaVarDecl(span, _, ident) = item.top_elts.get_tt(item.idx) {
let match_cur = item.match_cur;
item.push_match(
match_cur,
MatchedNonterminal(Rc::new(parse_nt(&mut parser, span, &ident.as_str()))),
);
item.idx += 1;
item.match_cur += 1;
} else {
unreachable!()
}
cur_items.push(item);
}
assert!(!cur_items.is_empty());
}
}
fn get_macro_ident(token: &Token) -> Option<(Ident, bool)> {
match *token {
token::Ident(ident, is_raw) if ident.name != keywords::Underscore.name() =>
Some((ident, is_raw)),
_ => None,
}
}
fn may_begin_with(name: &str, token: &Token) -> bool {
fn may_be_ident(nt: &token::Nonterminal) -> bool {
match *nt {
token::NtItem(_) | token::NtBlock(_) | token::NtVis(_) => false,
_ => true,
}
}
match name {
"expr" => token.can_begin_expr(),
"ty" => token.can_begin_type(),
"ident" => get_macro_ident(token).is_some(),
"literal" => token.can_begin_literal_or_bool(),
"vis" => match *token {
Token::Comma | Token::Ident(..) | Token::Interpolated(_) => true,
_ => token.can_begin_type(),
},
"block" => match *token {
Token::OpenDelim(token::Brace) => true,
Token::Interpolated(ref nt) => match nt.0 {
token::NtItem(_)
| token::NtPat(_)
| token::NtTy(_)
| token::NtIdent(..)
| token::NtMeta(_)
| token::NtPath(_)
| token::NtVis(_) => false, _ => true,
},
_ => false,
},
"path" | "meta" => match *token {
Token::ModSep | Token::Ident(..) => true,
Token::Interpolated(ref nt) => match nt.0 {
token::NtPath(_) | token::NtMeta(_) => true,
_ => may_be_ident(&nt.0),
},
_ => false,
},
"pat" => match *token {
Token::Ident(..) | Token::OpenDelim(token::Paren) | Token::OpenDelim(token::Bracket) | Token::BinOp(token::And) | Token::BinOp(token::Minus) | Token::AndAnd | Token::Literal(..) | Token::DotDot | Token::DotDotDot | Token::ModSep | Token::Lt | Token::BinOp(token::Shl) => true, Token::Interpolated(ref nt) => may_be_ident(&nt.0),
_ => false,
},
"lifetime" => match *token {
Token::Lifetime(_) => true,
Token::Interpolated(ref nt) => match nt.0 {
token::NtLifetime(_) | token::NtTT(_) => true,
_ => false,
},
_ => false,
},
_ => match *token {
token::CloseDelim(_) => false,
_ => true,
},
}
}
fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
if name == "tt" {
return token::NtTT(p.parse_token_tree());
}
p.process_potential_macro_variable();
match name {
"item" => match panictry!(p.parse_item()) {
Some(i) => token::NtItem(i),
None => {
p.fatal("expected an item keyword").emit();
FatalError.raise();
}
},
"block" => token::NtBlock(panictry!(p.parse_block())),
"stmt" => match panictry!(p.parse_stmt()) {
Some(s) => token::NtStmt(s),
None => {
p.fatal("expected a statement").emit();
FatalError.raise();
}
},
"pat" => token::NtPat(panictry!(p.parse_pat(None))),
"expr" => token::NtExpr(panictry!(p.parse_expr())),
"literal" => token::NtLiteral(panictry!(p.parse_literal_maybe_minus())),
"ty" => token::NtTy(panictry!(p.parse_ty())),
"ident" => if let Some((ident, is_raw)) = get_macro_ident(&p.token) {
let span = p.span;
p.bump();
token::NtIdent(Ident::new(ident.name, span), is_raw)
} else {
let token_str = pprust::token_to_string(&p.token);
p.fatal(&format!("expected ident, found {}", &token_str)).emit();
FatalError.raise()
}
"path" => token::NtPath(panictry!(p.parse_path_common(PathStyle::Type, false))),
"meta" => token::NtMeta(panictry!(p.parse_meta_item())),
"vis" => token::NtVis(panictry!(p.parse_visibility(true))),
"lifetime" => if p.check_lifetime() {
token::NtLifetime(p.expect_lifetime().ident)
} else {
let token_str = pprust::token_to_string(&p.token);
p.fatal(&format!("expected a lifetime, found `{}`", &token_str)).emit();
FatalError.raise();
}
_ => p.span_bug(sp, "invalid fragment specifier"),
}
}