lexington 0.3.0

use lexington::{Lexer,Match,Matcher,Scanner,Within};
use lexington::{ShiftReduceParser,ShiftReduceRule};
use Expr::*;
use PartExpr::*;

/// A simple definition of the components of a polynomial.
#[derive(Copy,Clone,Debug,PartialEq)]    
enum Kind {
    LeftBrace,
    RightBrace,
    Plus,
    Star,
    Number,
    Identifier,
    Eof
}

/// A simple definition of a polynomial expression.
#[derive(Clone,Debug,PartialEq)]    
enum Expr<'a> {
    // An integer coefficient
    Int(isize),
    // A variable
    Var(&'a str),
    // A sum e1 + .. + en
    Sum(Vec<Expr<'a>>),
    // A product e1 * .. * .. en
    Product(Vec<Expr<'a>>),
}

impl<'a> Expr<'a> {
    // Swap out self with dummy
    pub fn take(&mut self) -> Expr<'a> {
	let mut res : Expr<'a> = Int(0);
	// Swap out e with dummy value
	std::mem::swap(self,&mut res);
	//
	res
    }
}

/// A partial expression respresents an expression which is
/// potentially in the process of being parsed (i.e. may not have beeN-
/// fully parsed yet).
#[derive(Clone,Debug,PartialEq)]
enum PartExpr<'a> {
    // Indicates an expression is expected, but nothing has yet been
    // parsed for it.
    Empty,
    // Indicates parsing an expression has begun, but is not yet
    // closed (i.e. completed).
    Open(Expr<'a>),
    // Indicates an expression for which parsing has completed.
    Closed(Expr<'a>)
}

impl<'a> PartExpr<'a> {
    // Unwrap partial expression as a completed (i.e. closed)
    // expression.  This can fail if `self` is not, in fact, closed.
    fn unwrap(self) -> Expr<'a> {
	match self {
	    Closed(t) => t,
	    _ => { panic!("cannot unwrap incomplete expression"); }                
	}
    }

    // Close this expression (assuming it is open).
    fn close(self) -> PartExpr<'a> {
	match self {
            Open(t) => Closed(t),
            _ => self
	}
    }
    // Evolve partial expression into a sum.  Note that, in some
    // cases, this evolution should be prevented.  For example, a
    // product cannot evolve into a sum as that represents an
    // ambiguous expression such as `x*y+z` which we choose to
    // prohibit.
    fn into_sum(&mut self) -> Result<bool,()> {
	match self {
	    // Sum is already a sum
	    Open(Sum(_)) => Ok(true),
	    // Close expression becomes sum
	    Closed(e) => { *self = Open(Sum(vec![e.take()])); Ok(true)}
	    // Otherwise, rule does not apply
	    _ => Ok(false)
	}
    }
    // Evolve partial expression into a product.  Note that, in some
    // cases, this evolution should be prevented.  For example, a sum
    // cannot evolve into a product as that represents an ambiguous
    // expression such as `x*y+z` which we choose to prohibit.
    fn into_product(&mut self) -> Result<bool,()> {
	match self {
	    // Product is already a sum
	    Open(Product(_)) => Ok(true),
	    // Close expression becomes product
	    Closed(e) => { *self = Open(Product(vec![e.take()])); Ok(true)}
	    // Otherwise, rule does not apply
	    _ => Ok(false)
	}
    }    
}

fn scanner() -> impl Scanner<Item=char,Token=Kind> {
    // [0..9]+
    let number = Within('0'..='9').one_or_more();
    // [a..zA..Z_]([0..9a..zA..Z_]*)
    let identifier_start = Within('a'..='z')
        .or(Within('A'..='Z')).or('_');
    let identifier_rest = Within('0'..='9').or(Within('a'..='z'))
        .or(Within('A'..='Z')).or('_').zero_or_more();
    let identifier = identifier_start.then(identifier_rest);
    // Construct scanner    
    Match(number,Kind::Number)
        .and_match(identifier,Kind::Identifier)
        .and_match('+',Kind::Plus)
        .and_match('*',Kind::Star)            
        .and_match('(',Kind::LeftBrace)
        .and_match(')',Kind::RightBrace)
        .eof(Kind::Eof)
}

fn parse<'a>(input: &'a str) -> Result<Expr<'a>,()> {
    let scanner = scanner();
    // Construct Lexer
    let lexer = Lexer::new(input,scanner);
    // Rule for combining s-expressions
    let reduction_rule = |mut l:PartExpr<'a>,r:PartExpr<'a>| {
        match (&mut l,&r) {
            (Empty,_) => Ok(r),
            (Open(Sum(es)),_) => { es.push(r.unwrap()); Ok(l) }
            (Open(Product(es)),_) => { es.push(r.unwrap()); Ok(l) }            
            (_,_) => todo!("Reducing {l:?} <= {r:?})")
        }
    };
    // Rule for parsing strings into numbers
    let st = ShiftReduceParser::new()
        .apply(reduction_rule)
        .terminate(Kind::Number,|tok| Closed(Int(input[tok.range()].parse().unwrap())))
        .terminate(Kind::Identifier,|tok| Closed(Var(&input[tok.range()])))
	.update_as(Kind::Plus, |t| t.into_sum())
        .update_as(Kind::Star, |t| t.into_product())        
        .open(Kind::LeftBrace, Empty)        
        .close_with(Kind::RightBrace, |e| e.close())
        .close_with(Kind::Eof, |e| e.close())        
        .first(Empty)
        .parse(lexer)?;
    // Extract the term
    Ok(st.unwrap())
}

fn check_ok(input: &str, expecting: Expr) {
    // Parse tokens into expression
    let actual = parse(input).unwrap();
    // Check what we got
    assert_eq!(actual,expecting);
}

#[test]
fn arith_01() {
    check_ok("x",Var("x"));
}

#[test]
fn arith_02() {
    check_ok("(x)",Var("x"));
}

#[test]
fn arith_03() {
    check_ok("123",Int(123));
}

#[test]
fn arith_04() {
    check_ok("(123)",Int(123));
}

#[test]
fn arith_05() {
    check_ok("x+1",Sum(vec![Var("x"),Int(1)]));
}

#[test]
fn arith_06() {
    check_ok("1+x",Sum(vec![Int(1),Var("x")]));
}

#[test]
fn arith_07() {
    check_ok("x+y",Sum(vec![Var("x"),Var("y")]));
}

#[test]
fn arith_08() {
    check_ok("1+x+y",Sum(vec![Int(1),Var("x"),Var("y")]));
}

#[test]
fn arith_09() {
    check_ok("x+2+y",Sum(vec![Var("x"),Int(2),Var("y")]));
}

#[test]
fn arith_10() {
    check_ok("x+y+z",Sum(vec![Var("x"),Var("y"),Var("z")]));
}

#[test]
fn arith_11() {
    check_ok("x*1",Product(vec![Var("x"),Int(1)]));
}

#[test]
fn arith_12() {
    check_ok("1*x",Product(vec![Int(1),Var("x")]));
}

#[test]
fn arith_13() {
    check_ok("x*y",Product(vec![Var("x"),Var("y")]));
}

#[test]
fn arith_14() {
    check_ok("(x+1)*y",Product(vec![Sum(vec![Var("x"),Int(1)]),Var("y")]));
}

#[test]
fn arith_15() {
    check_ok("x*(y+1)",Product(vec![Var("x"),Sum(vec![Var("y"),Int(1)])]));
}

// #[test]
// fn arith_16() {
//     check_err("x*y+1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)]));
// }

// #[test]
// fn arith_17() {
//     check_ok("1*x*y+1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)]));
// }

// #[test]
// fn arith_18() {
//     check_ok("x+y*1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)]));
// }

// #[test]
// fn arith_19() {
//     check_ok("1+x+y*1",Sum(vec![Product(vec![Var("x"),Var("y")]),Int(1)]));
// }