use std::collections;
use std::error;
use std::fmt;
use std::rc;
use std::result;

use grammar;
use parse_tree;

#[derive(Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
pub enum Error {
    InvalidInput {
        offset: usize,
        got: char,
        expected: collections::BTreeSet<char>,
    },
}

impl error::Error for Error {}

impl<'a> fmt::Display for Error {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Error::InvalidInput {
                offset,
                got,
                expected,
            } => write!(
                f,
                "Invalid input at offset {offset}:
                    got {got:?},
                    expected one of {expected:?}",
                offset = offset,
                got = got,
                expected = expected
            ),
        }
    }
}

pub type Result<T> = result::Result<T, Error>;

#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
struct Item<'a> {
    start: usize,
    dot: usize,
    rule: &'a grammar::Rule,
}

impl<'a> Item<'a> {
    pub fn new(start: usize, rule: &'a grammar::Rule) -> Item<'a> {
        let dot = 0;
        Item { start, rule, dot }
    }

    pub fn peek(&self) -> Option<&grammar::Symbol> {
        self.rule.symbol_at(self.dot)
    }

    pub fn advance<'s>(&'s self) -> Item<'a> {
        Item {
            start: self.start,
            rule: self.rule,
            dot: self.dot + 1,
        }
    }

    pub fn at_call_to(&self, name: &rc::Rc<str>) -> bool {
        if let Some(grammar::Symbol::NonTerminal(nt)) = self.peek() {
            nt == name
        } else {
            false
        }
    }

    pub fn is_complete(&self) -> bool {
        self.dot == self.rule.symbols().len()
    }
}

impl<'a> fmt::Display for Item<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{} ->", self.rule.name())?;
        for (i, each) in self.rule.symbols().iter().enumerate() {
            if i == self.dot {
                write!(f, " •")?;
            }
            write!(f, " {}", each)?;
        }

        if self.dot == self.rule.symbols().len() {
            write!(f, " •")?;
        }

        write!(f, " ({})", self.start)
    }
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Parser<'a> {
    /// the grammar whose rules we'll use to parse the input
    grammar: &'a grammar::Grammar,
    /// the offset of the next input character we get
    offset: usize,
    /// our array of Items at each input offset
    items_by_offset: Vec<collections::BTreeSet<Item<'a>>>,
    /// our cache of right-recursion reductions
    reductions_by_offset_and_symbol:
        collections::BTreeMap<(usize, rc::Rc<str>), Item<'a>>,
    /// our parse-forest in progress
    tree_builder: parse_tree::Builder,
}

impl<'a> Parser<'a> {
    pub fn new(grammar: &'a grammar::Grammar) -> Result<Parser<'a>> {
        let mut res = Parser {
            grammar: grammar,
            offset: 0,
            items_by_offset: vec![
                grammar
                    .rules(&grammar.start())
                    .expect(
                        "grammar start symbol was checked by GrammarBuilder",
                    ).map(|r| Item::new(0, r))
                    .collect(),
            ],
            reductions_by_offset_and_symbol: collections::BTreeMap::new(),
            tree_builder: parse_tree::Builder::new(),
        };

        res.propagate_implications()?;

        Ok(res)
    }

    fn reduce_right_recursion<'s>(
        &'s mut self,
        item: &Item<'a>,
    ) -> Option<Item<'a>> {
        // If we have already calculated the topmost recursion of an item,
        // just return it as-is.
        if let Some(result) = self
            .reductions_by_offset_and_symbol
            .get(&(self.offset, item.rule.name()))
        {
            return Some(*result);
        }

        // Look for possible reductions of this completed item.
        let maybe_reductions = self.items_by_offset[item.start]
            .iter()
            .filter(|each| each.at_call_to(&item.rule.name()))
            .take(2)
            .map(|each| each.advance())
            .collect::<Vec<_>>();

        if maybe_reductions.len() != 1 {
            // There's no reduction, or there are multiple reductions
            // (i.e. the reduction is not deterministic).
            return None;
        }

        // We have reduced our original item by one level!
        let reduction = maybe_reductions[0];

        if !reduction.is_complete() {
            // This is not a right-recursive reduction,
            // so we don't care about it.
            return None;
        }

        // But maybe our new item is not the *ultimate* reduction.
        // If our new reduction can itself be reduced,
        // we want *that* item...
        let result = self
            .reductions_by_offset_and_symbol
            .get(&(item.start, reduction.rule.name()))
            .map(Item::clone)
            // ...otherwise we're happy with the one we've got.
            .unwrap_or(reduction);

        // Cache our result for next time.
        self.reductions_by_offset_and_symbol
            .insert((self.offset, item.rule.name()), result);

        Some(result)
    }

    fn propagate_implications(&mut self) -> Result<()> {
        // current_items represents the items we already know about,
        // whose implications we want to propagate.
        // We remove them from self.items_by_offset to separate "old items
        // that have been fully propagated" from "new items that need to be
        // propagated."
        let mut current_items = collections::BTreeSet::new();
        current_items.append(&mut self.items_by_offset[self.offset]);

        // implied_items represents the new items implied by the contents of
        // current_items.
        let mut implied_items = collections::BTreeSet::new();

        loop {
            for item in current_items.iter() {
                match item.peek() {
                    // "Scan" step
                    // We don't have any input character here, so we can
                    // ignore these items.
                    Some(grammar::Symbol::Terminal(_)) => (),

                    // "Prediction" step
                    // If an item says to expect a NonTerminal at this offset,
                    // add all the rules for that NonTerminal as new items.
                    Some(grammar::Symbol::NonTerminal(name)) => {
                        // If this non-terminal is nullable, it might already
                        // be completed, so let's also generate an advanced
                        // item to represent that possibility..
                        if let Some(true) = self.grammar.nullable(name) {
                            let completed = item.advance();
                            self.tree_builder.rule_completed(
                                completed.start..self.offset,
                                completed.rule.name(),
                                completed.rule.symbols(),
                            );
                            implied_items.insert(completed);
                        }

                        let maybe_new_items = self
                            .grammar
                            .rules(name)
                            .expect("grammar rules are self consistent")
                            .map(|r| Item::new(self.offset, r));
                        for item in maybe_new_items {
                            implied_items.insert(item);
                        }
                    }

                    // "Completion" step
                    // The character at this offset has completed a
                    // non-terminal item added by some previous "Prediction"
                    // step.
                    None => {
                        // An item has been completed!
                        // Let's add it to the collection.
                        self.tree_builder.rule_completed(
                            item.start..self.offset,
                            item.rule.name(),
                            item.rule.symbols(),
                        );

                        // If a grammar has a rule whose last symbol is
                        // recursive, there might be an excessive number of
                        // items for successive matches, but only the earliest
                        // item can contribute to the final parse. Therefore,
                        // we can skip over all the deterministic
                        // right-recursions here and just use the top-most one.
                        if let Some(reduced) = self.reduce_right_recursion(item)
                        {
                            implied_items.insert(reduced);
                            continue;
                        }

                        // Otherwise (the caller is not right-recursive, or
                        // there are multiple possible callers) we need to add
                        // all the items that might have called this item to
                        // the set, so they can make progress too.
                        // Said items must exist at the offset where this item
                        // started...
                        let parent_items = &self.items_by_offset[item.start];
                        let maybe_new_items = parent_items
                            .iter()
                            // ...its next symbol must be the NonTerminal
                            // symbol we've just completed...
                            .filter(|each| each.at_call_to(&item.rule.name()))
                            // ...and the new completion will be that original
                            // item, advanced past the NonTerminal we've just
                            // completed.
                            .map(|each| each.advance());
                        for item in maybe_new_items {
                            implied_items.insert(item);
                        }
                    }
                }
            }

            // The implications of current_items have been processed,
            // so let's stick them back into self.items_by_offset.
            self.items_by_offset[self.offset].append(&mut current_items);

            // Remove from implied_items all the items that have already been
            // propagated.
            implied_items = implied_items
                .difference(&self.items_by_offset[self.offset])
                .map(Item::clone)
                .collect();

            // If current_items did not imply any new items, we're done here.
            if implied_items.is_empty() {
                break;
            }

            // Otherwise, we need to process the implications of these new
            // items. Move them to current_items and loop around.
            current_items.append(&mut implied_items);
        }

        Ok(())
    }

    pub fn feed(
        &mut self,
        c: char,
    ) -> Result<collections::BTreeSet<parse_tree::Node>> {
        let next_items = self.items_by_offset[self.offset]
            .iter()
            .filter_map(|item| match item.peek() {
                Some(&grammar::Symbol::Terminal(expected)) if c == expected => {
                    Some(item.advance())
                }
                _ => None,
            }).collect::<collections::BTreeSet<Item>>();

        // If this character we received did not advance any items,
        // the input does not match the grammar we're parsing,
        // and so we return an error.
        if next_items.is_empty() {
            return Err(Error::InvalidInput {
                offset: self.offset,
                got: c,
                expected: self.items_by_offset[self.offset]
                    .iter()
                    .filter_map(|item| match item.peek() {
                        Some(&grammar::Symbol::Terminal(c)) => Some(c),
                        _ => None,
                    }).collect(),
            });
        }

        self.items_by_offset.push(next_items);

        self.offset += 1;
        self.propagate_implications()?;

        // To get the set of completed parses at this offset...
        let res = self
            // ...we get all the completed rules ending here...
            .tree_builder
            .get(..self.offset, self.grammar.start())
            .iter()
            // ...and filter for the ones that start at 0.
            .filter(|each| each.span == (0..self.offset))
            .cloned()
            .collect();

        Ok(res)
    }
}

impl<'a> fmt::Display for Parser<'a> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for (i, each) in self.items_by_offset.iter().enumerate() {
            write!(f, "=== {} ===\n", i)?;
            for item in each.iter() {
                write!(f, "{}\n", item)?;
            }
        }
        Ok(())
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn ambiguous_grammar() {
        let mut builder = grammar::GrammarBuilder::new("Statement");
        builder.rule("Statement").terminal('{').terminal('}').add();
        builder
            .rule("Statement")
            .terminal('i')
            .terminal('f')
            .terminal(' ')
            .nonterminal("Statement")
            .add();
        builder
            .rule("Statement")
            .terminal('i')
            .terminal('f')
            .terminal(' ')
            .nonterminal("Statement")
            .terminal(' ')
            .terminal('e')
            .terminal('l')
            .terminal('s')
            .terminal('e')
            .terminal(' ')
            .nonterminal("Statement")
            .add();

        let grammar = builder.build().expect("Could not build valid grammar?");
        let mut parser =
            Parser::new(&grammar).expect("Could not build valid parser?");

        let mut trees = Default::default();;
        for c in "if if {} else {}".chars() {
            trees = parser.feed(c).expect("parser rejected valid input?");
        }

        for each in trees.iter() {
            each.dump(0);
        }
        assert_eq!(trees.len(), 2);
    }

    #[test]
    fn infinitely_ambiguous_grammar() {
        let mut builder = grammar::GrammarBuilder::new("A");
        builder.rule("A").terminal('x').add();
        builder.rule("A").nonterminal("B").add();
        builder.rule("B").nonterminal("A").add();

        let grammar = builder.build().expect("Could not build valid grammar?");
        let mut parser =
            Parser::new(&grammar).expect("Could not build valid parser?");

        let trees = parser
            .feed('x')
            .expect("Could not feed a char to the parser?");

        for each in trees.iter() {
            each.dump(0);
        }

        assert_eq!(trees.len(), 2);
    }

    #[test]
    fn right_recursion_in_linear_space() {
        let mut builder = grammar::GrammarBuilder::new("A");
        builder.rule("A").add();
        builder.rule("A").terminal('a').nonterminal("A").add();

        let grammar = builder.build().expect("Could not build valid grammar?");
        let mut parser =
            Parser::new(&grammar).expect("Could not build valid parser?");

        for c in "aaaaa".chars() {
            parser.feed(c).expect("parser could not parse?");
        }

        println!("{}", parser);

        // If we're not properly reducing right-recursion,
        // we'll have more than five items in the final item set,
        // probably 8.
        assert_eq!(parser.items_by_offset[5].len(), 5);
    }
}