lalrpop 0.12.2

//! Constructs a DFA which picks the longest matching regular
//! expression from the input.

use collections::Set;
use kernel_set::{Kernel, KernelSet};
use std::fmt::{Debug, Display, Formatter, Error};
use std::rc::Rc;
use lexer::re;
use lexer::nfa::{self, NFA, NFAConstructionError, NFAStateIndex, Test};

#[cfg(test)]
mod test;

#[cfg(test)]
pub mod interpret;

pub mod codegen;

mod overlap;

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct DFA {
    pub states: Vec<State>
}

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

#[derive(Debug)]
pub enum DFAConstructionError {
    NFAConstructionError {
        index: NFAIndex,
        error: NFAConstructionError
    },

    /// Either of the two regexs listed could match, and they have equal
    /// priority.
    Ambiguity {
        match0: NFAIndex,
        match1: NFAIndex,
    }
}

pub fn build_dfa(regexs: &[re::Regex],
                 precedences: &[Precedence])
                 -> Result<DFA, DFAConstructionError> {
    assert_eq!(regexs.len(), precedences.len());
    let nfas: Vec<_> = try! {
        regexs.iter()
              .enumerate()
              .map(|(i, r)| match NFA::from_re(r) {
                  Ok(nfa) => Ok(nfa),
                  Err(e) => Err(DFAConstructionError::NFAConstructionError {
                      index: NFAIndex(i),
                      error: e
                  }),
              })
              .collect()
    };
    let builder = DFABuilder { nfas: &nfas, precedences: precedences.to_vec() };
    let dfa = try!(builder.build());
    Ok(dfa)
}

struct DFABuilder<'nfa> {
    nfas: &'nfa [NFA],
    precedences: Vec<Precedence>,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct State {
    item_set: DFAItemSet,
    pub kind: Kind,
    pub test_edges: Vec<(Test, DFAStateIndex)>,
    pub other_edge: DFAStateIndex,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Kind {
    Accepts(NFAIndex),
    Reject,
    Neither,
}

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

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

type DFAKernelSet = KernelSet<DFAItemSet>;

#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct DFAItemSet {
    items: Rc<Vec<Item>>
}

#[derive(Copy, Clone, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct Item {
    // which regular expression?
    nfa_index: NFAIndex,

    // what state within the NFA are we at?
    nfa_state: NFAStateIndex,
}

const START: DFAStateIndex = DFAStateIndex(0);

impl<'nfa> DFABuilder<'nfa> {
    fn build(&self) -> Result<DFA, DFAConstructionError> {
        let mut kernel_set = KernelSet::new();
        let mut states = vec![];

        let start_state_index = self.start_state(&mut kernel_set);
        assert_eq!(start_state_index, START);

        while let Some(item_set) = kernel_set.next() {
            // collect all the specific tests we expect from any of
            // the items in this state
            let tests: Set<Test> =
                item_set.items
                        .iter()
                        .flat_map(|&item| {
                            self.nfa(item)
                                .edges::<Test>(item.nfa_state)
                                .map(|edge| edge.label)
                        })
                        .collect();
            let tests = overlap::remove_overlap(&tests);

            // if any NFA is in an accepting state, that makes this
            // DFA state an accepting state
            let mut all_accepts: Vec<(Precedence, NFAIndex)> =
                item_set.items
                        .iter()
                        .cloned()
                        .filter(|&item| self.nfa(item).is_accepting_state(item.nfa_state))
                        .map(|item| (self.precedences[item.nfa_index.0], item.nfa_index))
                        .collect();

            // if all NFAs are in a rejecting state, that makes this
            // DFA a rejecting state
            let all_rejects: bool =
                item_set.items
                        .iter()
                        .all(|&item| self.nfa(item).is_rejecting_state(item.nfa_state));

            let kind = if all_rejects || item_set.items.is_empty() {
                Kind::Reject
            } else if all_accepts.len() == 0 {
                Kind::Neither
            } else if all_accepts.len() == 1 {
                // accepts just one NFA, easy case
                Kind::Accepts(all_accepts[0].1)
            } else {
                all_accepts.sort(); // sort regex with higher precedence, well, higher
                let (best_priority, best_nfa) = all_accepts[all_accepts.len() - 1];
                let (next_priority, next_nfa) = all_accepts[all_accepts.len() - 2];
                if best_priority == next_priority {
                    return Err(DFAConstructionError::Ambiguity {
                        match0: best_nfa,
                        match1: next_nfa
                    });
                }
                Kind::Accepts(best_nfa)
            };

            // for each specific test, find what happens if we see a
            // character matching that test
            let mut test_edges: Vec<(Test, DFAStateIndex)> =
                tests.iter()
                     .map(|&test| {
                         let items: Vec<_> =
                             item_set.items.iter()
                                           .filter_map(|&item| self.accept_test(item, test))
                                           .collect();

                         // at least one of those items should accept this test
                         assert!(!items.is_empty());

                         (test, kernel_set.add_state(self.transitive_closure(items)))
                     })
                     .collect();

            test_edges.sort();

            // Consider what there is some character that doesn't meet
            // any of the tests. In this case, we can just ignore all
            // the test edges for each of the items and just union all
            // the "other" edges -- because if it were one of those
            // test edges, then that transition is represented above.
            let other_transitions: Vec<_> =
                item_set.items.iter()
                              .filter_map(|&item| self.accept_other(item))
                              .collect();

            // we never know the full set
            assert!(item_set.items.is_empty() || !other_transitions.is_empty());

            let other_edge = kernel_set.add_state(self.transitive_closure(other_transitions));

            let state = State {
                item_set: item_set,
                kind: kind,
                test_edges: test_edges,
                other_edge: other_edge,
            };

            states.push(state);
        }

        Ok(DFA { states: states })
    }

    fn start_state(&self, kernel_set: &mut DFAKernelSet) -> DFAStateIndex {
        // starting state is at the beginning of all regular expressions
        let items: Vec<_> =
            (0..self.nfas.len())
            .map(|i| Item { nfa_index: NFAIndex(i),
                            nfa_state: nfa::START })
            .collect();
        let item_set = self.transitive_closure(items);
        kernel_set.add_state(item_set)
    }

    fn accept_test(&self, item: Item, test: Test) -> Option<Item> {
        let nfa = self.nfa(item);

        let matching_test =
            nfa.edges::<Test>(item.nfa_state)
               .filter(|edge| edge.label.intersects(test))
               .map(|edge| item.to(edge.to));

        let matching_other =
            nfa.edges::<nfa::Other>(item.nfa_state)
               .map(|edge| item.to(edge.to));

        matching_test.chain(matching_other).next()
    }

    fn accept_other(&self, item: Item) -> Option<Item> {
        let nfa = self.nfa(item);
        nfa.edges::<nfa::Other>(item.nfa_state)
            .map(|edge| item.to(edge.to))
            .next()
    }

    fn transitive_closure(&self, mut items: Vec<Item>) -> DFAItemSet {
        let mut observed: Set<Item> = items.iter().cloned().collect();

        let mut counter = 0;
        while counter < items.len() {
            let item = items[counter];
            let derived_states =
                self.nfa(item)
                    .edges::<nfa::Noop>(item.nfa_state)
                    .map(|edge| item.to(edge.to))
                    .filter(|&item| observed.insert(item));
            items.extend(derived_states);
            counter += 1;
        }

        items.sort();
        items.dedup();

        DFAItemSet { items: Rc::new(items) }
    }

    fn nfa(&self, item: Item) -> &NFA {
        &self.nfas[item.nfa_index.0]
    }
}

impl Kernel for DFAItemSet {
    type Index = DFAStateIndex;

    fn index(c: usize) -> DFAStateIndex {
        DFAStateIndex(c)
    }
}

impl DFA {
    fn state(&self, index: DFAStateIndex) -> &State {
        &self.states[index.0]
    }
}

impl Item {
    fn to(&self, s: NFAStateIndex) -> Item {
        Item { nfa_index: self.nfa_index, nfa_state: s }
    }
}

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

impl Display for DFAStateIndex {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
        Debug::fmt(self, fmt)
    }
}

impl NFAIndex {
    pub fn index(&self) -> usize {
        self.0
    }
}

impl DFAStateIndex {
    pub fn index(&self) -> usize {
        self.0
    }
}

impl Debug for Item {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
        write!(fmt, "({:?}:{:?})", self.nfa_index, self.nfa_state)
    }
}