use core::iter::Peekable;
use core::marker::PhantomData;
use core::ops::BitOr;
use alloc::boxed::Box;
use alloc::collections::BTreeMap;
use crate::iterators::Pair;
use crate::RuleType;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Assoc {
Left,
Right,
}
type Prec = u32;
const PREC_STEP: Prec = 10;
pub struct Op<R: RuleType> {
rule: R,
affix: Affix,
next: Option<Box<Op<R>>>,
}
enum Affix {
Prefix,
Postfix,
Infix(Assoc),
}
impl<R: RuleType> Op<R> {
pub fn prefix(rule: R) -> Self {
Self {
rule,
affix: Affix::Prefix,
next: None,
}
}
pub fn postfix(rule: R) -> Self {
Self {
rule,
affix: Affix::Postfix,
next: None,
}
}
pub fn infix(rule: R, assoc: Assoc) -> Self {
Self {
rule,
affix: Affix::Infix(assoc),
next: None,
}
}
}
impl<R: RuleType> BitOr for Op<R> {
type Output = Self;
fn bitor(mut self, rhs: Self) -> Self {
fn assign_next<R: RuleType>(op: &mut Op<R>, next: Op<R>) {
if let Some(ref mut child) = op.next {
assign_next(child, next);
} else {
op.next = Some(Box::new(next));
}
}
assign_next(&mut self, rhs);
self
}
}
pub struct PrattParser<R: RuleType> {
prec: Prec,
ops: BTreeMap<R, (Affix, Prec)>,
has_prefix: bool,
has_postfix: bool,
has_infix: bool,
}
impl<R: RuleType> Default for PrattParser<R> {
fn default() -> Self {
Self::new()
}
}
impl<R: RuleType> PrattParser<R> {
pub fn new() -> Self {
Self {
prec: PREC_STEP,
ops: BTreeMap::new(),
has_prefix: false,
has_postfix: false,
has_infix: false,
}
}
pub fn op(mut self, op: Op<R>) -> Self {
self.prec += PREC_STEP;
let mut iter = Some(op);
while let Some(Op { rule, affix, next }) = iter.take() {
match affix {
Affix::Prefix => self.has_prefix = true,
Affix::Postfix => self.has_postfix = true,
Affix::Infix(_) => self.has_infix = true,
}
self.ops.insert(rule, (affix, self.prec));
iter = next.map(|op| *op);
}
self
}
pub fn map_primary<'pratt, 'i, X, T>(
&'pratt self,
primary: X,
) -> PrattParserMap<'pratt, 'i, R, X, T>
where
X: FnMut(Pair<'i, R>) -> T,
R: 'pratt,
{
PrattParserMap {
pratt: self,
primary,
prefix: None,
postfix: None,
infix: None,
phantom: PhantomData,
}
}
}
type PrefixFn<'i, R, T> = Box<dyn FnMut(Pair<'i, R>, T) -> T + 'i>;
type PostfixFn<'i, R, T> = Box<dyn FnMut(T, Pair<'i, R>) -> T + 'i>;
type InfixFn<'i, R, T> = Box<dyn FnMut(T, Pair<'i, R>, T) -> T + 'i>;
pub struct PrattParserMap<'pratt, 'i, R, F, T>
where
R: RuleType,
F: FnMut(Pair<'i, R>) -> T,
{
pratt: &'pratt PrattParser<R>,
primary: F,
prefix: Option<PrefixFn<'i, R, T>>,
postfix: Option<PostfixFn<'i, R, T>>,
infix: Option<InfixFn<'i, R, T>>,
phantom: PhantomData<T>,
}
impl<'pratt, 'i, R, F, T> PrattParserMap<'pratt, 'i, R, F, T>
where
R: RuleType + 'pratt,
F: FnMut(Pair<'i, R>) -> T,
{
pub fn map_prefix<X>(mut self, prefix: X) -> Self
where
X: FnMut(Pair<'i, R>, T) -> T + 'i,
{
self.prefix = Some(Box::new(prefix));
self
}
pub fn map_postfix<X>(mut self, postfix: X) -> Self
where
X: FnMut(T, Pair<'i, R>) -> T + 'i,
{
self.postfix = Some(Box::new(postfix));
self
}
pub fn map_infix<X>(mut self, infix: X) -> Self
where
X: FnMut(T, Pair<'i, R>, T) -> T + 'i,
{
self.infix = Some(Box::new(infix));
self
}
pub fn parse<P: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: P) -> T {
self.expr(&mut pairs.peekable(), 0)
}
fn expr<P: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<P>, rbp: Prec) -> T {
let mut lhs = self.nud(pairs);
while rbp < self.lbp(pairs) {
lhs = self.led(pairs, lhs);
}
lhs
}
fn nud<P: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<P>) -> T {
let pair = pairs.next().expect("Pratt parsing expects non-empty Pairs");
match self.pratt.ops.get(&pair.as_rule()) {
Some((Affix::Prefix, prec)) => {
let rhs = self.expr(pairs, *prec - 1);
match self.prefix.as_mut() {
Some(prefix) => prefix(pair, rhs),
None => panic!("Could not map {}, no `.map_prefix(...)` specified", pair),
}
}
None => (self.primary)(pair),
_ => panic!("Expected prefix or primary expression, found {}", pair),
}
}
fn led<P: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<P>, lhs: T) -> T {
let pair = pairs.next().unwrap();
match self.pratt.ops.get(&pair.as_rule()) {
Some((Affix::Infix(assoc), prec)) => {
let rhs = match *assoc {
Assoc::Left => self.expr(pairs, *prec),
Assoc::Right => self.expr(pairs, *prec - 1),
};
match self.infix.as_mut() {
Some(infix) => infix(lhs, pair, rhs),
None => panic!("Could not map {}, no `.map_infix(...)` specified", pair),
}
}
Some((Affix::Postfix, _)) => match self.postfix.as_mut() {
Some(postfix) => postfix(lhs, pair),
None => panic!("Could not map {}, no `.map_postfix(...)` specified", pair),
},
_ => panic!("Expected postfix or infix expression, found {}", pair),
}
}
fn lbp<P: Iterator<Item = Pair<'i, R>>>(&mut self, pairs: &mut Peekable<P>) -> Prec {
match pairs.peek() {
Some(pair) => match self.pratt.ops.get(&pair.as_rule()) {
Some((_, prec)) => *prec,
None => panic!("Expected operator, found {}", pair),
},
None => 0,
}
}
}