lalrpop 0.12.2

//! The NFA we construct for each regex. Since the states are not
//! really of interest, we represent this just as a vector of labeled
//! edges.

use lexer::re::Regex;
use regex_syntax::{ClassRange, Expr, Repeater};
use std::char;
use std::fmt::{Debug, Formatter, Error as FmtError};
use std::usize;

#[cfg(test)]
mod interpret;

#[cfg(test)]
mod test;

#[derive(Debug)]
pub struct NFA {
    states: Vec<State>,
    edges: Edges
}

/// An edge label representing a range of characters, inclusive. Note
/// that this range may contain some endpoints that are not valid
/// unicode, hence we store u32.
#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct Test {
    pub start: u32,
    pub end: u32,
}

/// An "epsilon" edge -- no input
#[derive(Debug, PartialEq, Eq)]
pub struct Noop;

/// An "other" edge -- fallback if no other edges apply
#[derive(Debug, PartialEq, Eq)]
pub struct Other;

/// For each state, we just store the indices of the first char and
/// test edges, or usize::MAX if no such edge. You can then find all
/// edges by enumerating subsequent edges in the vectors until you
/// find one with a different `from` value.
#[derive(Debug)]
pub struct State {
    kind: StateKind,
    first_noop_edge: usize,
    first_test_edge: usize,
    first_other_edge: usize,
}

#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum StateKind {
    Accept, Reject, Neither
}

#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub struct NFAStateIndex(usize);

/// A set of edges for the state machine. Edges are kept sorted by the
/// type of label they have. Within a vector, all edges with the same
/// `from` are grouped together so they can be enumerated later (for
/// now we just ensure this during construction, but one could easily
/// sort).
#[derive(Debug)]
pub struct Edges {
    noop_edges: Vec<Edge<Noop>>,

    // edges where we are testing the character in some way; for any
    // given state, there should not be multiple edges with the same
    // test
    test_edges: Vec<Edge<Test>>,

    // fallback rules if no test_edge applies
    other_edges: Vec<Edge<Other>>,
}

#[derive(PartialEq, Eq)]
pub struct Edge<L> {
    pub from: NFAStateIndex,
    pub label: L,
    pub to: NFAStateIndex,
}

pub const ACCEPT: NFAStateIndex = NFAStateIndex(0);
pub const REJECT: NFAStateIndex = NFAStateIndex(1);
pub const START: NFAStateIndex = NFAStateIndex(2);

#[derive(Debug, PartialEq, Eq)]
pub enum NFAConstructionError {
    NamedCaptures,
    NonGreedy,
    WordBoundary,
    LineBoundary,
    TextBoundary,
}

impl NFA {
    pub fn from_re(regex: &Regex) -> Result<NFA, NFAConstructionError> {
        let mut nfa = NFA::new();
        let s0 = try!(nfa.expr(regex, ACCEPT, REJECT));
        nfa.push_edge(START, Noop, s0);
        Ok(nfa)
    }

    ///////////////////////////////////////////////////////////////////////////
    // Public methods for querying an NFA

    pub fn edges<L:EdgeLabel>(&self, from: NFAStateIndex) -> EdgeIterator<L> {
        let vec = L::vec(&self.edges);
        let first = *L::first(&self.states[from.0]);
        EdgeIterator { edges: vec, from: from, index: first }
    }

    pub fn kind(&self, from: NFAStateIndex) -> StateKind {
        self.states[from.0].kind
    }

    pub fn is_accepting_state(&self, from: NFAStateIndex) -> bool {
        self.states[from.0].kind == StateKind::Accept
    }

    pub fn is_rejecting_state(&self, from: NFAStateIndex) -> bool {
        self.states[from.0].kind == StateKind::Reject
    }

    ///////////////////////////////////////////////////////////////////////////
    // Private methods for building an NFA

    fn new() -> NFA {
        let mut nfa = NFA {
            states: vec![],
            edges: Edges {
                noop_edges: vec![],
                test_edges: vec![],
                other_edges: vec![],
            }
        };

        // reserve the ACCEPT, REJECT, and START states ahead of time
        assert!(nfa.new_state(StateKind::Accept) == ACCEPT);
        assert!(nfa.new_state(StateKind::Reject) == REJECT);
        assert!(nfa.new_state(StateKind::Neither) == START);

        // the ACCEPT state, given another token, becomes a REJECT
        nfa.push_edge(ACCEPT, Other, REJECT);

        // the REJECT state loops back to itself no matter what
        nfa.push_edge(REJECT, Other, REJECT);

        nfa
    }

    fn new_state(&mut self, kind: StateKind) -> NFAStateIndex {
        let index = self.states.len();

        // these edge indices will be patched later by patch_edges()
        self.states.push(State { kind: kind,
                                 first_noop_edge: usize::MAX,
                                 first_test_edge: usize::MAX,
                                 first_other_edge: usize::MAX });

        NFAStateIndex(index)
    }

    // pushes an edge: note that all outgoing edges from a particular
    // state should be pushed together, so that the edge vectors are
    // suitably sorted
    fn push_edge<L:EdgeLabel>(&mut self, from: NFAStateIndex, label: L, to: NFAStateIndex) {
        let edge_vec = L::vec_mut(&mut self.edges);
        let edge_index = edge_vec.len();
        edge_vec.push(Edge { from: from, label: label, to: to });

        // if this is the first edge from the `from` state, set the
        // index
        let first_index = L::first_mut(&mut self.states[from.0]);
        if *first_index == usize::MAX {
            *first_index = edge_index;
        } else{
            // otherwise, check that all edges are continuous
            assert_eq!(edge_vec[edge_index - 1].from, from);
        }
    }

    fn expr(&mut self, expr: &Expr, accept: NFAStateIndex, reject: NFAStateIndex)
            -> Result<NFAStateIndex, NFAConstructionError> {
        match *expr {
            Expr::Empty => {
                Ok(accept)
            }

            Expr::Literal { ref chars, casei } => {
                // for e.g. "abc":
                // [s0] -a-> [ ] -b-> [ ] -c-> [accept]
                //   |        |        |
                //   +--------+--------+--otherwise-> [reject]

                Ok(if casei {
                    chars.iter()
                         .rev()
                         .fold(accept, |s, &ch| {
                             let s1 = self.new_state(StateKind::Neither);
                             for ch1 in ch.to_lowercase().chain(ch.to_uppercase()) {
                                 self.push_edge(s1, Test::char(ch1), s);
                             }
                             self.push_edge(s1, Other, reject);
                             s1
                         })
                } else {
                    chars.iter()
                         .rev()
                         .fold(accept, |s, &ch| {
                             let s1 = self.new_state(StateKind::Neither);
                             self.push_edge(s1, Test::char(ch), s);
                             self.push_edge(s1, Other, reject);
                             s1
                         })
                })
            }

            Expr::AnyCharNoNL => {
                // [s0] -otherwise-> [accept]
                //   |
                // '\n' etc
                //   |
                //   v
                // [reject]

                let s0 = self.new_state(StateKind::Neither);
                for nl_char in "\n\r".chars() {
                    self.push_edge(s0, Test::char(nl_char), reject);
                }
                self.push_edge(s0, Other, accept);
                Ok(s0)
            }

            Expr::AnyChar => {
                // [s0] -otherwise-> [accept]

                let s0 = self.new_state(StateKind::Neither);
                self.push_edge(s0, Other, accept);
                Ok(s0)
            }

            Expr::Class(ref class) => {
                // [s0] --c0--> [accept]
                //  | |            ^
                //  | |   ...      |
                //  | |            |
                //  | +---cn-------+
                //  +---------------> [reject]

                let s0 = self.new_state(StateKind::Neither);
                for &range in class {
                    let test: Test = range.into();
                    self.push_edge(s0, test, accept);
                }
                self.push_edge(s0, Other, reject);
                Ok(s0)
            }

            // currently we don't support any boundaries because
            // I was too lazy to code them up or think about them
            Expr::StartLine | Expr::EndLine => {
                Err(NFAConstructionError::LineBoundary)
            }

            Expr::StartText | Expr::EndText => {
                Err(NFAConstructionError::TextBoundary)
            }

            Expr::WordBoundary | Expr::NotWordBoundary => {
                Err(NFAConstructionError::WordBoundary)
            }

            // currently we treat all groups the same, whether they
            // capture or not; but we don't permit named groups,
            // in case we want to give them significance in the future 
            Expr::Group { ref e, i: _, name: None } => {
                self.expr(e, accept, reject)
            }
            Expr::Group { name: Some(_), .. } => {
                Err(NFAConstructionError::NamedCaptures)
            }

            // currently we always report the longest match possible
            Expr::Repeat { greedy: false, .. } => {
                Err(NFAConstructionError::NonGreedy)
            }

            Expr::Repeat { ref e, r: Repeater::ZeroOrOne, greedy: true } => {
                self.optional_expr(e, accept, reject)
            }

            Expr::Repeat { ref e, r: Repeater::ZeroOrMore, greedy: true } => {
                self.star_expr(e, accept, reject)
            }

            Expr::Repeat { ref e, r: Repeater::OneOrMore, greedy: true } => {
                self.plus_expr(e, accept, reject)
            }

            Expr::Repeat { ref e,
                           r: Repeater::Range { min, max: None },
                           greedy: true } => {
                // +---min times----+
                // |                |
                //
                // [s0] --..e..-- [s1] --..e*..--> [accept]
                //          |      |
                //          |      v
                //          +-> [reject]

                let mut s = try!(self.star_expr(e, accept, reject));
                for _ in 0..min {
                    s = try!(self.expr(e, s, reject));
                }
                Ok(s)
            }

            Expr::Repeat { ref e,
                           r: Repeater::Range { min, max: Some(max) },
                           greedy: true } => {
                let mut s = accept;
                for _ in min..max {
                    s = try!(self.optional_expr(e, s, reject));
                }
                for _ in 0..min {
                    s = try!(self.expr(e, s, reject));
                }
                Ok(s)
            }

            Expr::Concat(ref exprs) => {
                let mut s = accept;
                for expr in exprs.iter().rev() {
                    s = try!(self.expr(expr, s, reject));
                }
                Ok(s)
            }

            Expr::Alternate(ref exprs) => {
                // [s0] --exprs[0]--> [accept/reject]
                //   |                   ^
                //   |                   |
                //   +----exprs[..]------+
                //   |                   |
                //   |                   |
                //   +----exprs[n-1]-----+

                let s0 = self.new_state(StateKind::Neither);
                let targets: Vec<_> =
                    try!(exprs.iter()
                         .map(|expr| self.expr(expr, accept, reject))
                         .collect());

                // push edges from s0 all together so they are
                // adjacant in the edge array
                for target in targets {
                    self.push_edge(s0, Noop, target);
                }
                Ok(s0)
            }
        }
    }

    fn optional_expr(&mut self,
                     expr: &Expr,
                     accept: NFAStateIndex,
                     reject: NFAStateIndex)
                     -> Result<NFAStateIndex, NFAConstructionError> {
        // [s0] ----> [accept]
        //   |           ^
        //   v           |
        // [s1] --...----+
        //         |
        //         v
        //      [reject]

        let s1 = try!(self.expr(expr, accept, reject));

        let s0 = self.new_state(StateKind::Neither);
        self.push_edge(s0, Noop, accept); // they might supply nothing
        self.push_edge(s0, Noop, s1);

        Ok(s0)
    }

    fn star_expr(&mut self,
                 expr: &Expr,
                 accept: NFAStateIndex,
                 reject: NFAStateIndex)
                 -> Result<NFAStateIndex, NFAConstructionError> {
        // [s0] ----> [accept]
        //  | ^
        //  | |
        //  | +----------+
        //  v            |
        // [s1] --...----+
        //         |
        //         v
        //      [reject]

        let s0 = self.new_state(StateKind::Neither);

        let s1 = try!(self.expr(expr, s0, reject));

        self.push_edge(s0, Noop, accept);
        self.push_edge(s0, Noop, s1);

        Ok(s0)
    }

    fn plus_expr(&mut self,
                 expr: &Expr,
                 accept: NFAStateIndex,
                 reject: NFAStateIndex)
                 -> Result<NFAStateIndex, NFAConstructionError> {
        //            [accept]
        //               ^
        //               |
        //    +----------+
        //    v          |
        // [s0] --...--[s1]
        //         |
        //         v
        //      [reject]

        let s1 = self.new_state(StateKind::Neither);

        let s0 = try!(self.expr(expr, s1, reject));

        self.push_edge(s1, Noop, accept);
        self.push_edge(s1, Noop, s0);

        Ok(s0)
    }
}

pub trait EdgeLabel: Sized {
    fn vec_mut(nfa: &mut Edges) -> &mut Vec<Edge<Self>>;
    fn vec(nfa: &Edges) -> &Vec<Edge<Self>>;
    fn first_mut(state: &mut State) -> &mut usize;
    fn first(state: &State) -> &usize;
}

impl EdgeLabel for Noop {
    fn vec_mut(nfa: &mut Edges) -> &mut Vec<Edge<Noop>> { &mut nfa.noop_edges }
    fn first_mut(state: &mut State) -> &mut usize { &mut state.first_noop_edge }
    fn vec(nfa: &Edges) -> &Vec<Edge<Noop>> { &nfa.noop_edges }
    fn first(state: &State) -> &usize { &state.first_noop_edge }
}

impl EdgeLabel for Other {
    fn vec_mut(nfa: &mut Edges) -> &mut Vec<Edge<Other>> { &mut nfa.other_edges }
    fn first_mut(state: &mut State) -> &mut usize { &mut state.first_other_edge }
    fn vec(nfa: &Edges) -> &Vec<Edge<Other>> { &nfa.other_edges }
    fn first(state: &State) -> &usize { &state.first_other_edge }
}

impl EdgeLabel for Test {
    fn vec_mut(nfa: &mut Edges) -> &mut Vec<Edge<Test>> { &mut nfa.test_edges }
    fn first_mut(state: &mut State) -> &mut usize { &mut state.first_test_edge }
    fn vec(nfa: &Edges) -> &Vec<Edge<Test>> { &nfa.test_edges }
    fn first(state: &State) -> &usize { &state.first_test_edge }
}

pub struct EdgeIterator<'nfa,L:EdgeLabel+'nfa> {
    edges: &'nfa [Edge<L>],
    from: NFAStateIndex,
    index: usize,
}

impl<'nfa,L:EdgeLabel> Iterator for EdgeIterator<'nfa,L> {
    type Item = &'nfa Edge<L>;

    fn next(&mut self) -> Option<&'nfa Edge<L>> {
        let index = self.index;
        if index == usize::MAX {
            return None;
        }

        let next_index = index + 1;
        if next_index >= self.edges.len() || self.edges[next_index].from != self.from {
            self.index = usize::MAX;
        } else {
            self.index = next_index;
        }

        Some(&self.edges[index])
    }
}

impl Test {
    pub fn char(c: char) -> Test {
        let c = c as u32;
        Test { start: c, end: c + 1 }
    }

    pub fn inclusive_range(s: char, e: char) -> Test {
        Test { start: s as u32, end: e as u32 + 1 }
    }


    pub fn exclusive_range(s: char, e: char) -> Test {
        Test { start: s as u32, end: e as u32 }
    }

    pub fn is_char(self) -> bool {
        self.len() == 1
    }

    pub fn len(self) -> u32 {
        self.end - self.start
    }

    pub fn contains_u32(self, c: u32) -> bool {
        c >= self.start && c < self.end
    }

    pub fn contains_char(self, c: char) -> bool {
        self.contains_u32(c as u32)
    }

    pub fn intersects(self, r: Test) -> bool {
        !self.is_empty() && !r.is_empty() && (
            self.contains_u32(r.start) || r.contains_u32(self.start))
    }

    pub fn is_disjoint(self, r: Test) -> bool {
        !self.intersects(r)
    }

    pub fn is_empty(self) -> bool {
        self.start == self.end
    }
}

impl From<ClassRange> for Test {
    fn from(range: ClassRange) -> Test {
        Test::inclusive_range(range.start, range.end)
    }
}

impl Debug for Test {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), FmtError> {
        match (char::from_u32(self.start), char::from_u32(self.end)) {
            (Some(start), Some(end)) => {
                if self.is_char() {
                    if ".[]()?+*!".contains(start) {
                        write!(fmt, "\\{}", start)
                    } else {
                        write!(fmt, "{}", start)
                    }
                } else {
                    write!(fmt, "[{:?}..{:?}]", start, end)
                }
            }
            _ => {
                write!(fmt, "[{:?}..{:?}]", self.start, self.end)
            }
        }
    }
}

impl Debug for NFAStateIndex {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), FmtError> {
        write!(fmt, "NFA{}", self.0)
    }
}

impl<L:Debug> Debug for Edge<L> {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), FmtError> {
        write!(fmt, "{:?} -{:?}-> {:?}", self.from, self.label, self.to)
    }
}