use alloc::borrow::Cow;
use alloc::boxed::Box;
use alloc::vec::Vec;
use core::iter::Peekable;
use core::ops::BitOr;
use crate::iterators::Pair;
use crate::RuleType;
#[cfg(feature = "const_prec_climber")]
#[macro_export]
macro_rules! prec_climber {
(
$( $assoc:ident $rule:ident $( | $rules:ident )* ),+ $(,)?
) => {{
prec_climber!(
@precedences { 1u32 }
$( [ $rule $( $rules )* ] )*
);
$crate::prec_climber::PrecClimber::new_const(
prec_climber!(
@array
$( $assoc $rule $(, $assoc $rules )* ),*
)
)
}};
( @assoc L ) => { $crate::prec_climber::Assoc::Left };
( @assoc R ) => { $crate::prec_climber::Assoc::Right };
(
@array
$(
$assoc:ident $rule:ident
),*
) => {
&[
$(
(
Rule::$rule,
$rule,
prec_climber!( @assoc $assoc ),
)
),*
]
};
(
@precedences { $precedence:expr }
) => {};
(
@precedences { $precedence:expr }
[ $( $rule:ident )* ]
$( [ $( $rules:ident )* ] )*
) => {
$(
#[allow(non_upper_case_globals)]
const $rule: u32 = $precedence;
)*
prec_climber!(
@precedences { 1u32 + $precedence }
$( [ $( $rules )* ] )*
);
};
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Assoc {
Left,
Right,
}
#[derive(Debug)]
pub struct Operator<R: RuleType> {
rule: R,
assoc: Assoc,
next: Option<Box<Operator<R>>>,
}
impl<R: RuleType> Operator<R> {
pub fn new(rule: R, assoc: Assoc) -> Operator<R> {
Operator {
rule,
assoc,
next: None,
}
}
}
impl<R: RuleType> BitOr for Operator<R> {
type Output = Self;
fn bitor(mut self, rhs: Self) -> Self {
fn assign_next<R: RuleType>(op: &mut Operator<R>, next: Operator<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
}
}
#[derive(Debug)]
pub struct PrecClimber<R: Clone + 'static> {
ops: Cow<'static, [(R, u32, Assoc)]>,
}
#[cfg(feature = "const_prec_climber")]
impl<R: Clone + 'static> PrecClimber<R> {
pub const fn new_const(ops: &'static [(R, u32, Assoc)]) -> PrecClimber<R> {
PrecClimber {
ops: Cow::Borrowed(ops),
}
}
}
impl<R: RuleType> PrecClimber<R> {
fn get(&self, rule: &R) -> Option<(u32, Assoc)> {
self.ops
.iter()
.find(|(r, _, _)| r == rule)
.map(|(_, precedence, assoc)| (*precedence, *assoc))
}
pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
let ops = ops
.into_iter()
.zip(1..)
.fold(Vec::new(), |mut vec, (op, prec)| {
let mut next = Some(op);
while let Some(op) = next.take() {
let Operator {
rule,
assoc,
next: op_next,
} = op;
vec.push((rule, prec, assoc));
next = op_next.map(|op| *op);
}
vec
});
PrecClimber {
ops: Cow::Owned(ops),
}
}
pub fn climb<'i, P, F, G, T>(&self, mut pairs: P, mut primary: F, mut infix: G) -> T
where
P: Iterator<Item = Pair<'i, R>>,
F: FnMut(Pair<'i, R>) -> T,
G: FnMut(T, Pair<'i, R>, T) -> T,
{
let lhs = primary(
pairs
.next()
.expect("precedence climbing requires a non-empty Pairs"),
);
self.climb_rec(lhs, 0, &mut pairs.peekable(), &mut primary, &mut infix)
}
fn climb_rec<'i, P, F, G, T>(
&self,
mut lhs: T,
min_prec: u32,
pairs: &mut Peekable<P>,
primary: &mut F,
infix: &mut G,
) -> T
where
P: Iterator<Item = Pair<'i, R>>,
F: FnMut(Pair<'i, R>) -> T,
G: FnMut(T, Pair<'i, R>, T) -> T,
{
while pairs.peek().is_some() {
let rule = pairs.peek().unwrap().as_rule();
if let Some((prec, _)) = self.get(&rule) {
if prec >= min_prec {
let op = pairs.next().unwrap();
let mut rhs = primary(pairs.next().expect(
"infix operator must be followed by \
a primary expression",
));
while pairs.peek().is_some() {
let rule = pairs.peek().unwrap().as_rule();
if let Some((new_prec, assoc)) = self.get(&rule) {
if new_prec > prec || assoc == Assoc::Right && new_prec == prec {
rhs = self.climb_rec(rhs, new_prec, pairs, primary, infix);
} else {
break;
}
} else {
break;
}
}
lhs = infix(lhs, op, rhs);
} else {
break;
}
} else {
break;
}
}
lhs
}
}