// SPDX-License-Identifier: GPL-2.0-or-later
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
//
// Imported from hg/rust/hg-core/src/ancestors.rs@ce6797ef6eab
//
// Copyright 2018  Georges RACINET <georges.racinet@octobus.net>
//           2020  Pacien TRAN-GIRARD <pacien.trangirard@pacien.net>

use crate::graph::{Graph, GraphReadError, Revision, NULL_REVISION};
use std::collections::{BinaryHeap, HashSet};
use std::convert::From;
use std::iter::{IntoIterator, Iterator};
use std::option::Option;
use std::option::Option::Some;
use std::result::Result;
use std::result::Result::{Err, Ok};
use std::vec::Vec;

/// Iterator over the ancestors of a given list of revisions
/// This is a generic type, defined and implemented for any Graph, so that
/// it's easy to
///
/// - unit test in pure Rust
/// - bind to main Mercurial code, potentially in several ways and have these
///   bindings evolve over time
pub struct AncestorsIterator<G: Graph> {
    graph: G,
    visit: BinaryHeap<Revision>,
    seen: HashSet<Revision>,
    stoprev: Revision,
}

/// Lazy ancestors set, backed by AncestorsIterator
pub struct LazyAncestors<G: Graph> {
    graph: G,
    containsiter: AncestorsIterator<G>,
    initrevs: Vec<Revision>,
    stoprev: Revision,
    inclusive: bool,
}

impl<G: Graph> AncestorsIterator<G> {
    /// Constructor.
    ///
    /// if `inclusive` is true, then the init revisions are emitted in
    /// particular, otherwise iteration starts from their parents.
    pub fn new(
        graph: G,
        initrevs: impl IntoIterator<Item = Revision>,
        stoprev: Revision,
        inclusive: bool,
    ) -> Result<Self, GraphReadError> {
        let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
        if inclusive {
            let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
            let seen = visit.iter().map(|&x| x).collect();
            return Ok(AncestorsIterator {
                visit,
                seen,
                stoprev,
                graph,
            });
        }
        let mut this = AncestorsIterator {
            visit: BinaryHeap::new(),
            seen: HashSet::new(),
            stoprev,
            graph,
        };
        this.seen.insert(NULL_REVISION);
        for rev in filtered_initrevs {
            for parent in this.graph.parents(rev)?.into_iter() {
                this.conditionally_push_rev(parent);
            }
        }
        Ok(this)
    }

    #[inline]
    fn conditionally_push_rev(&mut self, rev: Revision) {
        if self.stoprev <= rev && self.seen.insert(rev) {
            self.visit.push(rev);
        }
    }

    /// Consumes partially the iterator to tell if the given target
    /// revision
    /// is in the ancestors it emits.
    /// This is meant for iterators actually dedicated to that kind of
    /// purpose
    pub fn contains(
        &mut self,
        target: Revision,
    ) -> Result<bool, GraphReadError> {
        if self.seen.contains(&target) && target != NULL_REVISION {
            return Ok(true);
        }
        for item in self {
            let rev = item?;
            if rev == target {
                return Ok(true);
            }
            if rev < target {
                return Ok(false);
            }
        }
        Ok(false)
    }

    pub fn peek(&self) -> Option<Revision> {
        self.visit.peek().map(|&r| r)
    }

    /// Tell if the iterator is about an empty set
    ///
    /// The result does not depend whether the iterator has been consumed
    /// or not.
    /// This is mostly meant for iterators backing a lazy ancestors set
    pub fn is_empty(&self) -> bool {
        if self.visit.len() > 0 {
            return false;
        }
        if self.seen.len() > 1 {
            return false;
        }
        // at this point, the seen set is at most a singleton.
        // If not `self.inclusive`, it's still possible that it has only
        // the null revision
        self.seen.is_empty() || self.seen.contains(&NULL_REVISION)
    }
}

/// Main implementation for the iterator
///
/// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
/// with a few non crucial differences:
///
/// - there's no filtering of invalid parent revisions. Actually, it should be
///   consistent and more efficient to filter them from the end caller.
/// - we don't have the optimization for adjacent revisions (i.e., the case
///   where `p1 == rev - 1`), because it amounts to update the first element of
///   the heap without sifting, which Rust's BinaryHeap doesn't let us do.
/// - we save a few pushes by comparing with `stoprev` before pushing
impl<G: Graph> Iterator for AncestorsIterator<G> {
    type Item = Result<Revision, GraphReadError>;

    fn next(&mut self) -> Option<Self::Item> {
        let current = match self.visit.peek() {
            None => {
                return None;
            }
            Some(c) => *c,
        };
        let [p1, p2] = match self.graph.parents(current) {
            Ok(ps) => <[Revision; 2]>::from(ps),
            Err(e) => return Some(Err(e)),
        };

        if p1 < self.stoprev || !self.seen.insert(p1) {
            self.visit.pop();
        } else {
            *(self.visit.peek_mut().unwrap()) = p1;
        };

        self.conditionally_push_rev(p2);
        Some(Ok(current))
    }
}

/// G should implement [`Clone`] as cheap reference cloning.
impl<G: Graph + Clone> LazyAncestors<G> {
    pub fn new(
        graph: G,
        initrevs: impl IntoIterator<Item = Revision>,
        stoprev: Revision,
        inclusive: bool,
    ) -> Result<Self, GraphReadError> {
        let v: Vec<Revision> = initrevs.into_iter().collect();
        Ok(LazyAncestors {
            graph: graph.clone(),
            containsiter: AncestorsIterator::new(
                graph,
                v.iter().cloned(),
                stoprev,
                inclusive,
            )?,
            initrevs: v,
            stoprev,
            inclusive,
        })
    }

    pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphReadError> {
        self.containsiter.contains(rev)
    }

    pub fn is_empty(&self) -> bool {
        self.containsiter.is_empty()
    }

    pub fn iter(&self) -> AncestorsIterator<G> {
        // the arguments being the same as for self.containsiter, we know
        // for sure that AncestorsIterator constructor can't fail
        AncestorsIterator::new(
            self.graph.clone(),
            self.initrevs.iter().cloned(),
            self.stoprev,
            self.inclusive,
        )
        .unwrap()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::GraphReadError;
    use crate::testing::sample_graph::{Corrupted, SampleGraph};
    use std::option::Option::None;

    fn list_ancestors<G: Graph>(
        graph: &G,
        initrevs: Vec<Revision>,
        stoprev: Revision,
        inclusive: bool,
    ) -> Vec<Revision> {
        AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
            .unwrap()
            .map(|res| res.unwrap())
            .collect()
    }

    #[test]
    /// Same tests as test-ancestor.py, without membership
    /// (see also test-ancestor.py.out)
    fn test_list_ancestor() {
        assert_eq!(list_ancestors(&SampleGraph, vec![], 0, false), vec![]);
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 0, false),
            vec![8, 7, 4, 3, 2, 1, 0]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![1, 3], 0, false),
            vec![1, 0]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 0, true),
            vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 6, false),
            vec![8, 7]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 6, true),
            vec![13, 11, 8, 7]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 11, true),
            vec![13, 11]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![11, 13], 12, true),
            vec![13]
        );
        assert_eq!(
            list_ancestors(&SampleGraph, vec![10, 1], 0, true),
            vec![10, 5, 4, 2, 1, 0]
        );
    }

    #[test]
    /// Corner case that's not directly in test-ancestors.py, but
    /// that happens quite often, as demonstrated by running the whole
    /// suite.
    /// For instance, run tests/test-obsolete-checkheads.t
    fn test_nullrev_input() {
        let mut iter =
            AncestorsIterator::new(&SampleGraph, vec![-1], 0, false).unwrap();
        assert_eq!(iter.next(), None)
    }

    #[test]
    fn test_contains() {
        let mut lazy =
            AncestorsIterator::new(&SampleGraph, vec![10, 1], 0, true)
                .unwrap();
        assert!(lazy.contains(1).unwrap());
        assert!(!lazy.contains(3).unwrap());

        let mut lazy =
            AncestorsIterator::new(&SampleGraph, vec![0], 0, false).unwrap();
        assert!(!lazy.contains(NULL_REVISION).unwrap());
    }

    #[test]
    fn test_peek() {
        let mut iter =
            AncestorsIterator::new(&SampleGraph, vec![10], 0, true).unwrap();
        // peek() gives us the next value
        assert_eq!(iter.peek(), Some(10));
        // but it's not been consumed
        assert_eq!(iter.next(), Some(Ok(10)));
        // and iteration resumes normally
        assert_eq!(iter.next(), Some(Ok(5)));

        // let's drain the iterator to test peek() at the end
        while iter.next().is_some() {}
        assert_eq!(iter.peek(), None);
    }

    #[test]
    fn test_empty() {
        let mut iter =
            AncestorsIterator::new(&SampleGraph, vec![10], 0, true).unwrap();
        assert!(!iter.is_empty());
        while iter.next().is_some() {}
        assert!(!iter.is_empty());

        let iter =
            AncestorsIterator::new(&SampleGraph, vec![], 0, true).unwrap();
        assert!(iter.is_empty());

        // case where iter.seen == {NULL_REVISION}
        let iter =
            AncestorsIterator::new(&SampleGraph, vec![0], 0, false).unwrap();
        assert!(iter.is_empty());
    }

    #[test]
    fn test_initrev_out_of_range() {
        // inclusive=false looks up initrev's parents right away
        match AncestorsIterator::new(&SampleGraph, vec![25], 0, false) {
            Ok(_) => panic!("Should have been ParentOutOfRange"),
            Err(e) => assert_eq!(e, GraphReadError::InvalidKey),
        }
    }

    #[test]
    fn test_next_out_of_range() {
        // inclusive=false looks up initrev's parents right away
        let mut iter =
            AncestorsIterator::new(&Corrupted, vec![1], 0, false).unwrap();
        assert_eq!(iter.next(), Some(Err(GraphReadError::InvalidKey)));
    }

    #[test]
    fn test_lazy_iter_contains() {
        let mut lazy =
            LazyAncestors::new(&SampleGraph, vec![11, 13], 0, false).unwrap();

        let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
        // compare with iterator tests on the same initial revisions
        assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);

        // contains() results are correct, unaffected by the fact that
        // we consumed entirely an iterator out of lazy
        assert_eq!(lazy.contains(2), Ok(true));
        assert_eq!(lazy.contains(9), Ok(false));
    }

    #[test]
    fn test_lazy_contains_iter() {
        let mut lazy =
            LazyAncestors::new(&SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0]

        assert_eq!(lazy.contains(2), Ok(true));
        assert_eq!(lazy.contains(6), Ok(false));

        // after consumption of 2 by the inner iterator, results stay
        // consistent
        assert_eq!(lazy.contains(2), Ok(true));
        assert_eq!(lazy.contains(5), Ok(false));

        // iter() still gives us a fresh iterator
        let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
        assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
    }
}