use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::fmt::Display;

/// The reason parsing failed
#[non_exhaustive]
#[derive(Debug, PartialOrd, Ord, PartialEq, Eq)]
pub enum Reason {
    /// A predicate evaluated to `false`
    PredicateFailed,
    /// The `not` combinator failed  
    NotFailed,
    /// Expected to see the end of input, but didn't
    NotEndOfInput,
    /// Expected more input, but saw the end of input
    EndOfInput,
    /// The [`Debug`] representation of what we expected to find in the input.
    Mismatch(String),
    /// The description of an operation that failed while parsing. Only
    /// [`.and_then()`](crate::Parser::and_then) uses this reason
    Error(String),
    /// A user-provided label describing the item we tried and failed to parse. Only
    /// [`.label()`](crate::Parser::label) uses this reason
    Label(&'static str),
}

impl Reason {
    // We use these weights to tie break when we have multiple `ParserFailure`s at the same input
    // position
    fn weight(&self) -> usize {
        match self {
            Reason::PredicateFailed => 0,
            Reason::NotFailed => 10,
            Reason::NotEndOfInput => 20,
            Reason::EndOfInput => 30,
            Reason::Mismatch(_) => 40,
            Reason::Error(_) => 50,
            Reason::Label(_) => 60,
        }
    }
}

impl Display for Reason {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Reason::PredicateFailed => {
                write!(f, "predicate evaluated to false")
            }
            Reason::NotFailed => {
                write!(f, "unexpected parser success")
            }
            Reason::NotEndOfInput => {
                write!(f, "expected end of input")
            }
            Reason::EndOfInput => {
                write!(f, "unexpected end of input")
            }
            Reason::Mismatch(s) => {
                write!(f, "expected {}", s)
            }
            Reason::Error(e) => {
                write!(f, "unexpected error: {}", e)
            }
            Reason::Label(l) => {
                write!(f, "expected {}", l)
            }
        }
    }
}

/// A parsing error
#[derive(Debug, PartialEq, Eq)]
pub struct ParserFailure {
    pub position: usize,
    pub reason: Reason,
    pub id: usize,
}

impl ParserFailure {
    fn new(reason: Reason, position: usize, id: usize) -> Self {
        Self {
            position,
            reason,
            id,
        }
    }
}

impl Ord for ParserFailure {
    fn cmp(&self, other: &Self) -> Ordering {
        let res = self.position.cmp(&other.position);

        if res != Ordering::Equal {
            return res;
        }

        let res = self.reason.weight().cmp(&other.reason.weight());

        if res != Ordering::Equal {
            return res;
        }

        // reverse the order
        other.id.cmp(&self.id)
    }
}

impl PartialOrd for ParserFailure {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Display for ParserFailure {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{} at position {}", self.reason, self.position)
    }
}

/// A log of parser failures sorted by input position in descending order.
///
/// This is returned when [when parsers fail](crate::Res).
#[derive(Debug)]
pub struct FailureLog {
    counter: usize,
    heap: BinaryHeap<ParserFailure>,
}

impl Default for FailureLog {
    fn default() -> Self {
        Self::new()
    }
}

impl FailureLog {
    /// Creates a new log of failures
    pub fn new() -> Self {
        FailureLog {
            counter: 0,
            heap: BinaryHeap::new(),
        }
    }

    /// Record a new parser failure at a given input position
    pub fn add(&mut self, reason: Reason, position: usize) {
        self.heap
            .push(ParserFailure::new(reason, position, self.counter));
        self.counter += 1;
    }

    /// Pops [`ParserFailure`]s from the log in descending order of input position
    ///
    /// Ties are broken by failure reason. If there are two failures with the same position and
    /// reason, the first one inserted is removed first
    ///
    /// Returns `None` if the log is empty
    pub fn pop(&mut self) -> Option<ParserFailure> {
        self.heap.pop()
    }

    /// Peeks the next [`ParserFailure`] from the log in descending order of input position
    ///
    /// Returns `None` if the log is empty
    pub fn peek(&self) -> Option<&ParserFailure> {
        self.heap.peek()
    }

    /// Consumes the log and returns a vector of [`ParserFailure`]s sorted in ascending order of
    /// input position
    pub fn to_vec(self) -> Vec<ParserFailure> {
        self.heap.into_sorted_vec()
    }
}

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

    #[test]
    fn test_parser_failure_order_by_position() {
        let mut log = FailureLog::new();

        log.add(Reason::NotFailed, 1);
        log.add(Reason::NotFailed, 100);
        log.add(Reason::NotFailed, 34);

        let first = log.pop().unwrap();
        let second = log.pop().unwrap();
        let third = log.pop().unwrap();

        assert!(matches!(first, ParserFailure { position: 100, .. }));
        assert!(matches!(second, ParserFailure { position: 34, .. }));
        assert!(matches!(third, ParserFailure { position: 1, .. }));
    }

    #[test]
    fn test_parser_failure_tie_break_by_reason() {
        let mut log = FailureLog::new();

        log.add(Reason::PredicateFailed, 1);
        log.add(Reason::Label("digit"), 1);
        log.add(Reason::EndOfInput, 1);
        log.add(Reason::Mismatch("9".into()), 1);
        log.add(Reason::NotFailed, 1);
        log.add(Reason::Error("err".into()), 1);
        log.add(Reason::NotEndOfInput, 1);

        // The order in which the failures should be pop()ed should be deterministic
        let label = log.pop().unwrap();
        let err = log.pop().unwrap();
        let mismatch = log.pop().unwrap();
        let eoi = log.pop().unwrap();
        let neoi = log.pop().unwrap();
        let notfailed = log.pop().unwrap();
        let predicate = log.pop().unwrap();

        assert!(matches!(
            label,
            ParserFailure {
                reason: Reason::Label(_),
                ..
            }
        ));
        assert!(matches!(
            err,
            ParserFailure {
                reason: Reason::Error(_),
                ..
            }
        ));
        assert!(matches!(
            mismatch,
            ParserFailure {
                reason: Reason::Mismatch(_),
                ..
            }
        ));
        assert!(matches!(
            eoi,
            ParserFailure {
                reason: Reason::EndOfInput,
                ..
            }
        ));
        assert!(matches!(
            neoi,
            ParserFailure {
                reason: Reason::NotEndOfInput,
                ..
            }
        ));
        assert!(matches!(
            notfailed,
            ParserFailure {
                reason: Reason::NotFailed,
                ..
            }
        ));
        assert!(matches!(
            predicate,
            ParserFailure {
                reason: Reason::PredicateFailed,
                ..
            }
        ));
    }

    #[test]
    fn test_parser_failure_tie_break_by_id() {
        let mut log = FailureLog::new();

        log.add(Reason::Label("c"), 0);
        log.add(Reason::Label("a"), 0);
        log.add(Reason::Label("b"), 0);

        let first = log.pop().unwrap();
        let second = log.pop().unwrap();
        let third = log.pop().unwrap();

        // failures are removed in the order they are inserted if they have the same position and
        // reason
        assert!(matches!(
            first,
            ParserFailure {
                reason: Reason::Label("c"),
                ..
            }
        ));
        assert!(matches!(
            second,
            ParserFailure {
                reason: Reason::Label("a"),
                ..
            }
        ));
        assert!(matches!(
            third,
            ParserFailure {
                reason: Reason::Label("b"),
                ..
            }
        ));
    }
}