pub use NamedMatch::*;
pub use ParseResult::*;
use TokenTreeOrTokenTreeSlice::*;
use crate::ast::{Ident, Name};
use crate::ext::tt::quoted::{self, TokenTree};
use crate::parse::{Directory, ParseSess};
use crate::parse::parser::{Parser, PathStyle};
use crate::parse::token::{self, DocComment, Nonterminal, Token};
use crate::print::pprust;
use crate::symbol::{kw, sym, Symbol};
use crate::tokenstream::{DelimSpan, TokenStream};
use errors::FatalError;
use smallvec::{smallvec, SmallVec};
use syntax_pos::Span;
use rustc_data_structures::fx::FxHashMap;
use rustc_data_structures::sync::Lrc;
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> {
top_elts: TokenTreeOrTokenTreeSlice<'tt>,
idx: usize,
sp_open: Span,
matches: Box<[Lrc<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 = Lrc::make_mut(&mut self.matches[idx]);
matches.push(m);
}
}
enum MatcherPosHandle<'root, 'tt> {
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(Token, &'static str),
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<[Lrc<NamedMatchVec>]> {
if len == 0 {
vec![]
} else {
let empty_matches = Lrc::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(Lrc<NamedMatchVec>, DelimSpan),
MatchedNonterminal(Lrc<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 == kw::Invalid => {
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.kind {
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((ident1, is_raw1)), Some((ident2, is_raw2))) = (t1.ident(), t2.ident()) {
ident1.name == ident2.name && is_raw1 == is_raw2
} else if let (Some(ident1), Some(ident2)) = (t1.lifetime(), t2.lifetime()) {
ident1.name == ident2.name
} else {
t1.kind == t2.kind
}
}
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,
) -> 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, token.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(Lrc::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 == kw::Invalid => {
if sess.missing_fragment_specifiers.borrow_mut().remove(&span) {
return Error(span, "missing fragment specifier".to_string());
}
}
TokenTree::MetaVarDecl(_, _, id) => {
if may_begin_with(token, id.name) {
bb_items.push(item);
}
}
seq @ TokenTree::Delimited(..) |
seq @ TokenTree::Token(Token { kind: 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(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,
crate::MACRO_ARGUMENTS,
);
let mut initial = initial_matcher_pos(ms, parser.token.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,
) {
Success(_) => {}
Failure(token, msg) => return Failure(token, msg),
Error(sp, msg) => return Error(sp, msg),
}
assert!(cur_items.is_empty());
if parser.token == token::Eof {
if eof_items.len() == 1 {
let matches = eof_items[0]
.matches
.iter_mut()
.map(|dv| Lrc::make_mut(dv).pop().unwrap());
return nameize(sess, ms, matches);
} else if eof_items.len() > 1 {
return Error(
parser.token.span,
"ambiguity: multiple successful parses".to_string(),
);
} else {
return Failure(
Token::new(token::Eof, if parser.token.span.is_dummy() {
parser.token.span
} else {
sess.source_map().next_point(parser.token.span)
}),
"missing tokens in macro arguments",
);
}
}
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.token.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.token.take(),
"no rules expected this token in macro call",
);
}
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(Lrc::new(parse_nt(&mut parser, span, ident.name))),
);
item.idx += 1;
item.match_cur += 1;
} else {
unreachable!()
}
cur_items.push(item);
}
assert!(!cur_items.is_empty());
}
}
fn get_macro_name(token: &Token) -> Option<(Name, bool)> {
match token.kind {
token::Ident(name, is_raw) if name != kw::Underscore => Some((name, is_raw)),
_ => None,
}
}
fn may_begin_with(token: &Token, name: Name) -> bool {
fn may_be_ident(nt: &token::Nonterminal) -> bool {
match *nt {
token::NtItem(_) | token::NtBlock(_) | token::NtVis(_) => false,
_ => true,
}
}
match name {
sym::expr => token.can_begin_expr()
&& !token.is_keyword(kw::Let),
sym::ty => token.can_begin_type(),
sym::ident => get_macro_name(token).is_some(),
sym::literal => token.can_begin_literal_or_bool(),
sym::vis => match token.kind {
token::Comma | token::Ident(..) | token::Interpolated(_) => true,
_ => token.can_begin_type(),
},
sym::block => match token.kind {
token::OpenDelim(token::Brace) => true,
token::Interpolated(ref nt) => match **nt {
token::NtItem(_)
| token::NtPat(_)
| token::NtTy(_)
| token::NtIdent(..)
| token::NtMeta(_)
| token::NtPath(_)
| token::NtVis(_) => false, _ => true,
},
_ => false,
},
sym::path | sym::meta => match token.kind {
token::ModSep | token::Ident(..) => true,
token::Interpolated(ref nt) => match **nt {
token::NtPath(_) | token::NtMeta(_) => true,
_ => may_be_ident(&nt),
},
_ => false,
},
sym::pat => match token.kind {
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),
_ => false,
},
sym::lifetime => match token.kind {
token::Lifetime(_) => true,
token::Interpolated(ref nt) => match **nt {
token::NtLifetime(_) | token::NtTT(_) => true,
_ => false,
},
_ => false,
},
_ => match token.kind {
token::CloseDelim(_) => false,
_ => true,
},
}
}
fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: Symbol) -> Nonterminal {
if name == sym::tt {
return token::NtTT(p.parse_token_tree());
}
p.process_potential_macro_variable();
match name {
sym::item => match panictry!(p.parse_item()) {
Some(i) => token::NtItem(i),
None => {
p.fatal("expected an item keyword").emit();
FatalError.raise();
}
},
sym::block => token::NtBlock(panictry!(p.parse_block())),
sym::stmt => match panictry!(p.parse_stmt()) {
Some(s) => token::NtStmt(s),
None => {
p.fatal("expected a statement").emit();
FatalError.raise();
}
},
sym::pat => token::NtPat(panictry!(p.parse_pat(None))),
sym::expr => token::NtExpr(panictry!(p.parse_expr())),
sym::literal => token::NtLiteral(panictry!(p.parse_literal_maybe_minus())),
sym::ty => token::NtTy(panictry!(p.parse_ty())),
sym::ident => if let Some((name, is_raw)) = get_macro_name(&p.token) {
let span = p.token.span;
p.bump();
token::NtIdent(Ident::new(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()
}
sym::path => token::NtPath(panictry!(p.parse_path(PathStyle::Type))),
sym::meta => token::NtMeta(panictry!(p.parse_meta_item())),
sym::vis => token::NtVis(panictry!(p.parse_visibility(true))),
sym::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"),
}
}