main.rs

/* Cargo.toml dependencies
[dependencies]
combine = "3.8.1"
combine-language = "3.0.2"
derive_more = "0.99.11"
*/

use combine_language::{expression_parser, float, Assoc, Fixity};
#[macro_use]
extern crate combine;
use combine::{
    choice,
    parser::char::{char, spaces, string},
    stream::Stream,
    ParseError, Parser,
};
use derive_more::Deref;
use std::ops::{Add, Div, Mul, Neg, Sub};
use std::rc::Rc;

#[derive(Debug, Clone, Deref)]
#[deref(forward)]
struct RExpr(Rc<Expr>);
impl RExpr {
    fn new(x: Expr) -> Self {
        Self(Rc::new(x))
    }
    fn as_ptr(&self) -> *const Expr {
        Rc::as_ptr(&self.0)
    }
}
#[derive(Debug)]
enum Expr {
    Add(RExpr, RExpr),
    Sub(RExpr, RExpr),
    Mul(RExpr, RExpr),
    Div(RExpr, RExpr),
    Neg(RExpr),
    Pow(RExpr, RExpr),
    Sin(RExpr),
    Cos(RExpr),
    Lit(f64),
    X,
}
use Expr as E;
macro_rules! impl_op_for_RExpr {
    ($Op:ident $op:ident) => {
        impl $Op for RExpr {
            type Output = Self;
            fn $op(self, other: Self) -> Self {
                RExpr::new(E::$Op(self, other))
            }
        }
    };
}
impl_op_for_RExpr!(Add add);
impl_op_for_RExpr!(Sub sub);
impl_op_for_RExpr!(Mul mul);
impl_op_for_RExpr!(Div div);
impl Neg for RExpr {
    type Output = Self;
    fn neg(self) -> Self {
        RExpr::new(E::Neg(self))
    }
}
impl RExpr {
    fn pow(self, other: Self) -> Self {
        RExpr::new(E::Pow(self, other))
    }
    fn sin(self) -> Self {
        RExpr::new(E::Sin(self))
    }
    fn cos(self) -> Self {
        RExpr::new(E::Cos(self))
    }
}
impl From<f64> for RExpr {
    fn from(x: f64) -> Self {
        RExpr::new(E::Lit(x))
    }
}
impl E {
    fn x() -> RExpr {
        RExpr::new(E::X)
    }
}

#[inline]
fn expr_parser<Input>() -> impl Parser<Input = Input, Output = RExpr>
where
    Input: Stream<Item = char>,
    Input::Error: ParseError<Input::Item, Input::Range, Input::Position>,
{
    (spaces().silent(), expr()).map(|(_, r)| r)
}
parser! {
    fn expr[Input]()(Input) -> RExpr
    where [Input: Stream<Item = char>]
    {
        let skip_spaces = || spaces().silent();
        let lex_char = |c| char(c).skip(skip_spaces());
        let lex_string = |s| string(s).skip(skip_spaces());
        let x = char('x').map(|_| E::x());
        let neg_term = (lex_char('-'), expr()).map(|(_, e)| -e);
        let parens_expr = || (lex_char('('), expr(), char(')')).map(|(_, e, _)| e);
        let sin_expr = (lex_string("sin"), parens_expr()).map(|(_, e)| e.sin());
        let cos_expr = (lex_string("cos"), parens_expr()).map(|(_, e)| e.cos());

        let literal = float().map(From::from);
        let term = choice((neg_term, parens_expr(), sin_expr, cos_expr, x, literal)).skip(skip_spaces());

        enum Op { Add, Sub, Mul, Div, Pow };
        use Op::*;
        impl Op {
            fn read(c: char) -> Op {
                match c {
                    '+' => Add,
                    '-' => Sub,
                    '*' => Mul,
                    '/' => Div,
                    '^' => Pow,
                    _ => unreachable!(),
                }
            }
            fn assoc(&self) -> Assoc {
                let precedence = match self {
                    Add => 0,
                    Sub => 0,
                    Mul => 1,
                    Div => 1,
                    Pow => 2,
                };
                let fixity = match self {
                    Pow => Fixity::Right,
                    _ => Fixity::Left,
                };
                Assoc { precedence, fixity }
            }
        }

        let op_parser = choice((char('+'),char('-'),char('*'),char('/'),char('^'))).map(Op::read).skip(skip_spaces());

        let op = |l: RExpr, op, r| match op {
            Add => l + r,
            Sub => l - r,
            Mul => l * r,
            Div => l / r,
            Pow => l.pow(r),
        };

        expression_parser(term, op_parser.map(|op| {let a = op.assoc(); (op, a) }), op)
    }
}

impl Expr {
    // division by zero leads to panics
    fn eval(&self, x: f64) -> f64 {
        use E::*;
        match self {
            Add(l, r) => l.eval(x) + r.eval(x),
            Sub(l, r) => l.eval(x) - r.eval(x),
            Mul(l, r) => l.eval(x) * r.eval(x),
            Div(l, r) => l.eval(x) / r.eval(x),
            Pow(l, r) => l.eval(x).powf(r.eval(x)),
            Neg(e) => -e.eval(x),
            Sin(e) => e.eval(x).sin(),
            Cos(e) => e.eval(x).cos(),
            Lit(l) => *l,
            X => x,
        }
    }
}

impl Expr {
    fn zero() -> RExpr {
        thread_local! {
            static ZERO: RExpr = RExpr::new(E::Lit(0.));
        }
        ZERO.with(|zero| zero.clone())
    }
    fn one() -> RExpr {
        thread_local! {
            static ONE: RExpr = RExpr::new(E::Lit(1.));
        }
        ONE.with(|one| one.clone())
    }
    fn two() -> RExpr {
        thread_local! {
            static TWO: RExpr = RExpr::new(E::Lit(2.));
        }
        TWO.with(|two| two.clone())
    }
}

use std::collections::HashSet;
impl RExpr {
    fn try_derive(&self) -> Option<Self> {
        let ref mut known_constants = HashSet::new();
        self.find_known_constants(known_constants);
        fn d(c: &HashSet<*const Expr>, e: &RExpr) -> Option<RExpr> {
            Some(if c.contains(&e.as_ptr()) {
                E::zero()
            } else {
                use E::*;
                match &**e {
                    Add(l, r) => d(c, l)? + d(c, r)?,
                    Sub(l, r) => d(c, l)? - d(c, r)?,
                    Mul(l, r) => d(c, l)? * r.clone() + l.clone() * d(c, r)?,
                    Div(l, r) => {
                        (d(c, l)? * r.clone() + l.clone() * d(c, r)?) / r.clone().pow(E::two())
                    }
                    Pow(l, r) if c.contains(&r.as_ptr()) => {
                        r.clone() * d(c, l)? * l.clone().pow(r.clone() - E::one())
                    }
                    Neg(e) => -d(c, e)?,
                    Sin(e) => d(c, e)?.cos(),
                    Cos(e) => -d(c, e)?.sin(),
                    X => E::one(),
                    Lit(_) => unreachable!(),
                    Pow(_, _) => None?, // remaining cases for Pow not implemented
                                        // would need extra functions like e.g. exp and log
                }
            })
        }
        d(known_constants, self)
    }
    fn find_known_constants(&self, m: &mut HashSet<*const Expr>) -> bool {
        use E::*;
        let is_const = match &**self {
            Add(l, r) | Sub(l, r) | Mul(l, r) | Div(l, r) | Pow(l, r) => {
                l.find_known_constants(m) & r.find_known_constants(m)
            }
            Neg(e) | Sin(e) | Cos(e) => e.find_known_constants(m),
            Lit(_) => true,
            X => false,
        };
        if is_const {
            m.insert(self.as_ptr());
        }
        is_const
    }
}

fn main() {
    let x = " 1 + 2 + 3 * - ( 4 * x^5^2 ) ";
    let y = expr_parser().easy_parse(x).unwrap_or_else(|e| {
        println!("{}", e);
        panic!()
    });

    println!("{:?}", y);
    println!("{:?}", y.0.try_derive());
    let (e, remaining) = expr_parser().easy_parse("x^2 + 2*x + 1").unwrap();
    assert!(remaining == "");
    println!("{}", e.eval(1.));
    println!("{}", e.eval(2.));
    println!("{}", e.eval(3.));
    let e_prime = e.try_derive().unwrap();
    println!("{}", e_prime.eval(1.));
    println!("{}", e_prime.eval(2.));
    println!("{}", e_prime.eval(3.));
}