use std::collections::HashMap;
use std::iter::Peekable;
use std::ops::BitOr;
use RuleType;
use iterators::Pair;
#[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: RuleType> {
ops: HashMap<R, (u32, Assoc)>
}
impl<R: RuleType> PrecClimber<R> {
pub fn new(ops: Vec<Operator<R>>) -> PrecClimber<R> {
let ops = ops.into_iter()
.zip(1..)
.fold(HashMap::new(), |mut map, (op, prec)| {
let mut next = Some(op);
while let Some(op) = next.take() {
match op {
Operator {
rule,
assoc,
next: op_next
} => {
map.insert(rule, (prec, assoc));
next = op_next.map(|op| *op);
}
}
}
map
});
PrecClimber { 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.ops.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.ops.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
}
}