lexington 0.3.0

use std::marker::PhantomData;
use crate::Token;

/// A _shift-reduce parser_ processes input one token at a time
/// (currently without backtracking).  Tokens are transformed into
/// terms using two rules: _shift_ and _reduce_.  These operate over a
/// stack of (partially complete) terms.
pub trait ShiftReduceRule : Sized {
    /// Identifies the kind of tokens being processed by this rule.
    type Kind;
    /// Identifies the type of terms being produced by this rule.
    type Term;

    /// A _reduction rule combines a sub-term into its enclosing term.
    /// For example, when parsing arithmetic expressions we might reduce
    /// `1 + 2*x` with `y` to form `1 + 2*x + y`.    
    fn reduce(&self, lhs: Self::Term, rhs: Self::Term) -> Result<Self::Term,()>;

    /// A _shift rule_ reads the next token and decides what to do.  For
    /// example, it can return a completed term or it can begin a new
    /// term.    
    fn shift(&mut self, token: Token<Self::Kind>, stack: &mut Vec<Self::Term>) -> Result<Option<Self::Term>,()>;

    /// Apply a given reduction as necessary when reducing terms.
    fn apply<F:Fn(Self::Term,Self::Term)->Result<Self::Term,()>>(self, rule: F) -> ShiftApplyRule<Self::Kind,F,Self> {
        ShiftApplyRule{rule, rest: self, dummy: PhantomData }
    }

    fn first(self, term: Self::Term) -> ShiftFirstRule<Self::Kind,Self::Term,Self> {
        ShiftFirstRule{ term: Some(term), rest: self, dummy: PhantomData }
    }
    
    /// Handle a terminating token kind using a given parser.  For
    /// example, a token representing a number can be handled directly
    /// using an appropriate parser (e.g. `usize::parse()`).
    fn terminate<F>(self,kind: Self::Kind, rule: F) -> ShiftTerminalRule<Self::Kind,F,Self>
    where F:Fn(Token<Self::Kind>)->Self::Term
    {
        ShiftTerminalRule{kind, rule, rest: self}         
    }

    /// Skip all occurrences of the given token.  For example, if our
    /// language supports `WhiteSpace` tokens then we might want to
    /// skip them and, likewise, for comments, etc.
    fn skip(self,kind: Self::Kind) -> ShiftSkipRule<Self::Kind,Self::Term,Self> {
        ShiftSkipRule{kind, dummy: PhantomData, rest: self}
    }

    /// Begin parsing a new compound term when the given token is
    /// encountered.  The new term is initialised with a given default
    /// value.  For example, when parsing an S-expression (i.e. lisp),
    /// then upon encountering a `(` we start a new empty list.    
    fn open(self,kind: Self::Kind, default: Self::Term) -> ShiftOpenRule<Self::Kind,Self::Term,Self> {
        ShiftOpenRule{kind, default, rest: self}
    }
    
    /// Finish parsing a compound a compound term when the given token
    /// is encountered.  When this happens, the current stack element
    /// is popped off the stack and either reduced into the element
    /// below, or returned.  For example, when parsing an S-expression
    /// (i.e. lisp), the token `)` signifies the end of a list.    
    fn close(self,kind: Self::Kind) -> ShiftCloseRule<Self::Kind,fn(Self::Term)->Self::Term,Self>
    {
        ShiftCloseRule{kind, rule: |t| t, rest: self}
    }

    /// Finish parsing a compound a compound term when the given token
    /// is encountered.  When this happens, the current stack element
    /// is popped off the stack and either reduced into the element
    /// below, or returned.  For example, when parsing an S-expression
    /// (i.e. lisp), the token `)` signifies the end of a list.    
    fn close_with<F>(self,kind: Self::Kind, rule: F) -> ShiftCloseRule<Self::Kind,F,Self>
    where F:Fn(Self::Term)->Self::Term
    {
        ShiftCloseRule{kind, rule, rest: self}
    }
    
    /// Update the current state (i.e. topmost stack term) based on a
    /// given token.
    fn update<F:Fn(Self::Term)->Self::Term>(self, kind: Self::Kind, rule: F) -> ShiftUpdateRule<Self::Kind,F,Self> {
        ShiftUpdateRule{kind, rule, rest: self}
    }

    /// Update the current state (i.e. topmost stack item) based on a
    /// given token.  If the given rule returns `None`, then no action
    /// is taken.  Otherwise, the topmost stack item is replaced with
    /// that returned.
    fn update_with<F:Fn(Self::Term)->Result<(bool,Self::Term),()>>(self, kind: Self::Kind, rule: F) -> ShiftUpdateWithRule<Self::Kind,F,Self> {
        ShiftUpdateWithRule{kind, rule, rest: self}
    }    

    /// Update the current state (i.e. topmost stack item) based on a
    /// given token.  If the given rule returns `false`, then the rule
    /// did not apply and other rules should be considered.
    fn update_as<F:Fn(&mut Self::Term)->Result<bool,()>>(self, kind: Self::Kind, rule: F) -> ShiftUpdateAsRule<Self::Kind,F,Self> {
        ShiftUpdateAsRule{kind, rule, rest: self}
    }    
    
    /// Parse a given token stream and construct a corresponding term
    /// (or report an error).
    fn parse<I>(&mut self, input: I) -> Result<Self::Term,()>
    where I: IntoIterator<Item=Token<Self::Kind>>
    {
        let mut input = input.into_iter();
        // Construct initially empty stack
        let mut stack = Vec::new();
        // Continue reading tokens until nothing is left.
        while let Some(token) = input.next() {
            // Perform shift
            if let Some(t2) = self.shift(token, &mut stack)? {
                match stack.pop() {
                    None => {
                        // Parsing is complete!
                        return Ok(t2);
                    }
                    Some(t1) => {
                        // Perform reduction
                        let reduction = self.reduce(t1,t2)?;
                        // Process reduction                        
                        stack.push(reduction);
                    }
                }
            }
        }
        // If we get here then we reached the end-of-file before
        // parsing was complete.
        Err(())
    }    
}

// ===================================================================
// Empty Shift
// ===================================================================

/// The empty shift rule simply fails immediately with an error.  The
/// intention is that, starting from this rule, we can build up a
/// complete shift rule.
pub struct ShiftReduceParser<K,T>{
    dummy: PhantomData<(K,T)>,
}

impl<K,T> ShiftReduceParser<K,T> {
    pub fn new() -> Self {
        ShiftReduceParser{ dummy: PhantomData}
    }
}

impl<K:PartialEq,T> ShiftReduceRule for ShiftReduceParser<K,T>
{
    type Kind = K;
    type Term = T;
    
    fn shift(&mut self, _token: Token<K>, _stack: &mut Vec<T>) -> Result<Option<T>,()> {        
        Err(())
    }

    fn reduce(&self, _parent: T, _child: T) -> Result<T,()> {
        Err(())
    }    
}

// ===================================================================
// Shift Apply
// ===================================================================

pub struct ShiftApplyRule<K,F,SR> { rule: F, rest: SR, dummy: PhantomData<K>  }

impl<K:PartialEq,T,F:Fn(T,T)->Result<T,()>,SR> ShiftReduceRule for ShiftApplyRule<K,F,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
        
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        self.rest.shift(token,stack)
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        (self.rule)(parent,child)
    }
}

// ===================================================================
// Shift First
// ===================================================================

pub struct ShiftFirstRule<K,T,SR> { term: Option<T>, dummy: PhantomData<K>, rest: SR }

impl<K:PartialEq,T,SR> ShiftReduceRule for ShiftFirstRule<K,T,SR>
    where SR: ShiftReduceRule<Kind=K,Term=T> {
    type Kind = K;
    type Term = T;
    
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        // Push term if first time
        if self.term.is_some() { stack.push(self.term.take().unwrap()); }
        // Continue with whatever comes next
        self.rest.shift(token,stack)            
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }    
}

// ===================================================================
// Shift Terminate
// ===================================================================

/// Handle tokens directly using a given parser.  For example, a
/// number `123` can be handled directly using `parse()`, etc.
pub struct ShiftTerminalRule<K,F,SR> { kind: K, rule: F, rest: SR  }

impl<K:PartialEq,T,F:Fn(Token<K>)->T,SR> ShiftReduceRule for ShiftTerminalRule<K,F,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
        
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind {
            Ok(Some((self.rule)(token)))
        } else {
            self.rest.shift(token,stack)
        }
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }
}

// ===================================================================
// Shift Up
// ===================================================================

/// The given token indicates the start of a new compound element.  As
/// such, a new default element is pushed onto the stack.  For
/// example, when parsing an S-expression (i.e. lisp), then upon
/// encountering a `(` we start a new empty list.
pub struct ShiftOpenRule<K,T,SR> { kind: K, default: T, rest: SR }

impl<K:PartialEq,T:Clone,SR> ShiftReduceRule for ShiftOpenRule<K,T,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
    
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind {
            // Push up the default value
            stack.push(self.default.clone());
            // Done
            Ok(None)
        } else {
            self.rest.shift(token,stack)
        }
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }    
}

// ===================================================================
// Shift Close
// ===================================================================

/// The given token indicates the end of a compound element.  As such,
/// current stack element is popped off the stack and either reduced
/// into the element below, or returned.  For example, when parsing an
/// S-expression (i.e. lisp), the token `)` signifies the end of a
/// list.
pub struct ShiftCloseRule<K,F,SR> { kind: K, rule: F, rest: SR }

impl<K:PartialEq,T,F,SR> ShiftReduceRule for ShiftCloseRule<K,F,SR>
where F:Fn(T)->T,
      SR: ShiftReduceRule<Kind=K,Term=T> {
    
    type Kind =K;
    type Term = T;
    
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind && !stack.is_empty() {
            // Extract term to close.
            let term = stack.pop().unwrap();
            // Close term.
            let closed = (self.rule)(term);
            // Done
            Ok(Some(closed))
        } else {
            self.rest.shift(token,stack)
        }
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }    
}

// ===================================================================
// Shift Skip
// ===================================================================

/// The given token should be ignored.  For example, if it indicates
/// whitespace or comments, etc.
pub struct ShiftSkipRule<K,T,SR> { kind: K, dummy: PhantomData<T>, rest: SR }

impl<K:PartialEq,T,SR> ShiftReduceRule for ShiftSkipRule<K,T,SR>
    where SR: ShiftReduceRule<Kind=K,Term=T> {
    type Kind = K;
    type Term = T;
    
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind {            
            Ok(None)
        } else {
            self.rest.shift(token,stack)
        }
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }    
}

// ===================================================================
// Shift Update
// ===================================================================

pub struct ShiftUpdateRule<K,F,SR> { kind: K, rule: F, rest: SR  }

impl<K:PartialEq,T,F:Fn(T)->T,SR> ShiftReduceRule for ShiftUpdateRule<K,F,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
        
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind && !stack.is_empty(){
            // Extract topmost item
            let top = stack.pop().unwrap();
            // Apply the update rule
            stack.push((self.rule)(top));
            // Done
            Ok(None)
        } else {
            self.rest.shift(token,stack)
        }
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }
}

// ===================================================================
// Shift Update With
// ===================================================================

pub struct ShiftUpdateWithRule<K,F,SR> { kind: K, rule: F, rest: SR  }

impl<K:PartialEq,T,F:Fn(T)->Result<(bool,T),()>,SR> ShiftReduceRule for ShiftUpdateWithRule<K,F,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
        
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind && !stack.is_empty(){
            // Extract topmost item
            let top = stack.pop().unwrap();
            // Apply the update rule
            let (ok,item) = (self.rule)(top)?;
	    // Put what we have back
	    stack.push(item);
            // Apply the update rule
	    if ok { return Ok(None); }
        } 
        self.rest.shift(token,stack)
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }
}


// ===================================================================
// Shift Update As
// ===================================================================

pub struct ShiftUpdateAsRule<K,F,SR> { kind: K, rule: F, rest: SR  }

impl<K:PartialEq,T,F:Fn(&mut T)->Result<bool,()>,SR> ShiftReduceRule for ShiftUpdateAsRule<K,F,SR>
where SR: ShiftReduceRule<Kind=K,Term=T>
{
    type Kind = K;
    type Term = T;
        
    fn shift(&mut self, token: Token<K>, stack: &mut Vec<T>) -> Result<Option<T>,()> {
        if token.kind == self.kind {
	    // Extract topmost item
	    match stack.last_mut() {
		Some(item) => {
		    // Apply the update rule		    
		    if (self.rule)(item)? {
			// Successfully applied
			return Ok(None)
		    }
		}
		_ => {}
	    }
        }
	// Rule didn't apply, so continue trying to shift.
        self.rest.shift(token,stack)
    }

    fn reduce(&self, parent: T, child: T) -> Result<T,()> {
        self.rest.reduce(parent,child)
    }
}