nom-operator 0.0.2

// Copyright 2017 The nom-operator project developers
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

#![cfg_attr(feature="clippy", feature(plugin))]
#![cfg_attr(feature="clippy", plugin(clippy))]

#![cfg_attr(not(feature="clippy"), deny(unstable_features))]

#![deny(missing_docs,
        //missing_debug_implementations,
        missing_copy_implementations,
        trivial_casts,
        trivial_numeric_casts,
        unsafe_code,
        unused_import_braces,
        unused_qualifications)]

// Remove this
#![allow(dead_code,
         unused_variables,
         unused_macros,
         unused_imports)]

//#![deny(warnings)]
#![doc(test(attr(allow(unused_variables), deny(warnings))))]

//! This crate exposes convinient macros that can parse expressions
//! based on set parameters

#[cfg_attr(test, macro_use)]
extern crate nom;

#[macro_use]
mod macros;

pub mod expr;
pub mod operator;

pub use expr::Expr;
pub use operator::Operator;
pub use nom::IResult;
use std::fmt::Debug;
use operator::OperatorSize::*;

type Parser = Box<Fn(&[u8]) -> IResult<&[u8], &[u8]>>;

/// Operator parser state
/// Is generic over the Atom return type and
/// the Operator type (Usually an enum)
//TODO: Should we require the Clone on `OperatorEnum`?
//TODO: Remove the debug requirement from this
pub struct OpParser<'a, OperatorEnum> where OperatorEnum: Sized + Copy + Debug {
    /// List of operators
    operators: Vec<Operator<OperatorEnum>>,

    /// Atom parser
    atom_parser: Parser,

    expr_stack: Vec<Expr<&'a [u8], OperatorEnum>>,
    op_stack: Vec<OperatorEnum>,
}

impl<'a, OpEnum> OpParser<'a, OpEnum>
    where OpEnum: PartialEq + Copy + Debug {
    /// Creates a new Operator parser
    pub fn new(ap: Parser) -> Self {
        OpParser {
            operators: vec![],
            atom_parser: ap,
            expr_stack: vec![],
            op_stack: vec![],
        }
    }

    /// Adds a new operator to the list
    pub fn add(&mut self, op: Operator<OpEnum>) {
        self.operators.push(op)
    }

    fn log(&self, i: String, action: &'static str) {
        use std::cmp::{min, max};
        print!("{:?}\t", self.op_stack);

        //let mod_stack = self.expr_stack.iter().map(|l| d(l)).collect();
        print!("{:?}", self.expr_stack);
        let l = format!("{:?}", self.expr_stack).len();
        for i in 0..l + 20 - l  {
            print!(" ");
        }
        print!("\t");
        println!("{}\t{}", i, action);
    }

    fn find_operator(&self, openum: &OpEnum) -> Option<&Operator<OpEnum>> {
        self.operators.iter()
            .filter(|o| o.op == *openum)
            .nth(0)
    }

    // if op != next
    //  false when next.prec > op.prec
    //  true when next.prec < op.prec
    //
    // if op == next
    //  false when next.assoc == right
    //  true when next.assoc == left
    fn should_reduce(&self, next: OpEnum) -> bool {
        use operator::OperatorSize::*;
        use operator::Associativity;
        if let Some(op) = self.op_stack.iter().peekable().peek() {
            let operator = self.find_operator(*op)
                .expect("Could not find operator in store");

            let next_operator = self.find_operator(&next)
                .expect("Could not find operator in store");

            if operator.op == next {
                return next_operator.associativity == Associativity::Left;
            } else {
                return next_operator.precedence <= operator.precedence;
            }
        }
        false
    }

    fn reduce(&mut self) {
        self.log(String::new(), "Reduce");
        if self.expr_stack.len() < 1 { // TODO: TMP
            return;
        }
        if let Some(op) = self.op_stack.pop() {
            let operator = self.operators.iter()
                .filter(|o| o.op == op)
                .nth(0)
                .expect("Could not find operator in store");

            match operator.size {
                Binary => {
                    let right = self.expr_stack.pop().unwrap();
                    let left = self.expr_stack.pop().unwrap();
                    self.expr_stack.push(Expr::BinExpr{
                        left: Box::new(left),
                        op,
                        right: Box::new(right)
                    })
                }
                Unary => {
                    let e = self.expr_stack.pop().unwrap();
                    self.expr_stack.push(Expr::UnExpr{
                        op,
                        item: Box::new(e)
                    })

                }
            }

        }
    }


    fn shift<'b: 'a>(&mut self, i: &'b [u8]) -> Result<&'b [u8], &'b [u8]> {
        self.log(d(i), "Shift");
        for op in &self.operators {
            if let IResult::Done(s, m) = (*op.parser)(i) {
                self.op_stack.push(op.op);
                return Ok(s);
            }
        }

        if let IResult::Done(s, m) = (*self.atom_parser)(i) {
                self.expr_stack.push(Expr::Atom(m));
                return Ok(s);
        }
        Err(i)
    }

    fn try_parse_operator(&self, i: &[u8]) -> Option<OpEnum> {
        for op in &self.operators {
            if let IResult::Done(s, m) = (*op.parser)(i) {
                return Some(op.op);
            }
        }
        None
    }

    /// Parses a slice of bytes
    // TODO: Change this back to IResult<&'b [u8], Expr<&'_ [u8], OpEnum>>
    // when done
    pub fn parse<'b: 'a>(&mut self, input: &'b [u8]) -> IResult<&'b [u8], &Expr<&[u8], OpEnum>> {

        let mut mut_input = input;
        while let Ok(rest) = self.shift(mut_input) {
            mut_input = rest;

            if let Some(op) = self.try_parse_operator(mut_input) {
                if self.should_reduce(op) {
                    self.reduce();
                }
            }
        }

        for o in 0..self.op_stack.len() {
            self.reduce();
        }
        self.log(String::new(), "Done\n\n");

        IResult::Done(mut_input, &self.expr_stack[0])
    }

}
fn d(i: &[u8]) -> String {
    let mut v = Vec::new();
    v.extend_from_slice(i);
    String::from_utf8(v).unwrap()
}

#[cfg(test)]
mod tests {
    use IResult;
    use Expr;
    use {OpParser, Operator};
    use operator::Associativity::{Left, Right};
    use operator::OperatorSize::{Unary, Binary};

    use nom::digit;
    #[derive(Debug, Clone, Copy, PartialEq)]
    enum Ops {
        Mul,
        Add,
        Sub,
        Exp,
        PreIncrement,
        PreDecrement,
    }

    fn empty_parser(i: &[u8]) -> IResult<&[u8], &[u8]> {
        panic!("Attempted to run empty_parser");
    }

    fn opparser_factory<'a>() -> OpParser<'a, Ops> {
        let mut opp = OpParser::new(Box::new(|i| digit(i)));

        opp.add(Operator::new(Ops::PreIncrement, Right, Unary,  8, Box::new(|i| tag!(i, "++"))));
        opp.add(Operator::new(Ops::PreDecrement, Right, Unary,  7, Box::new(|i| tag!(i, "--"))));
        opp.add(Operator::new(Ops::Add, Left, Binary, 10, Box::new(|i| tag!(i, "+"))));
        opp.add(Operator::new(Ops::Mul, Left, Binary, 11, Box::new(|i| tag!(i, "*"))));
        opp.add(Operator::new(Ops::Sub, Left, Binary,  9, Box::new(|i| tag!(i, "-"))));
        opp.add(Operator::new(Ops::Exp, Right, Binary,  13, Box::new(|i| tag!(i, "^"))));

        opp
    }

    #[test]
    fn test() {
        let mut p = opparser_factory();
        println!("");

        p.parse(b"--++10");
    }

    testcase!(parse_binary, b"20+10^43",
              &t!(t!(20), Ops::Add, t!(t!(10), Ops::Exp, t!(43))));
    testcase!(parse_unary, b"++10", &t!(Ops::PreIncrement, t!(10)));

    testcase!(parse_unary_double,
              b"++--10",
              &t!(Ops::PreIncrement, t!(Ops::PreDecrement, t!(10))));
}