// ancestors.rs

//

// Copyright 2018 Georges Racinet <gracinet@anybox.fr>

//

// This software may be used and distributed according to the terms of the

// GNU General Public License version 2 or any later version.

//! Rust versions of generic DAG ancestors algorithms for Mercurial

use super::{Graph, GraphError, Revision, NULL_REVISION};

use std::cmp::max;

use std::collections::{BinaryHeap, HashSet};

/// 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 + Clone> {

    graph: G,

    containsiter: AncestorsIterator<G>,

    initrevs: Vec<Revision>,

    stoprev: Revision,

    inclusive: bool,

}

pub struct MissingAncestors<G: Graph> {

    graph: G,

    bases: HashSet<Revision>,

}

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, GraphError> {

        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: visit,

                seen: seen,

                stoprev: stoprev,

                graph: graph,

            });

        }

        let mut this = AncestorsIterator {

            visit: BinaryHeap::new(),

            seen: HashSet::new(),

            stoprev: stoprev,

            graph: graph,

        };

        this.seen.insert(NULL_REVISION);

        for rev in filtered_initrevs {

            for parent in this.graph.parents(rev)?.iter().cloned() {

                this.conditionally_push_rev(parent);

            }

        }

        Ok(this)

    }

    #[inline]

    fn conditionally_push_rev(&mut self, rev: Revision) {

        if self.stoprev <= rev && !self.seen.contains(&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, GraphError> {

        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, GraphError>;

    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) => ps,

            Err(e) => return Some(Err(e)),

        };

        if p1 < self.stoprev || self.seen.contains(&p1) {

            self.visit.pop();

        } else {

            *(self.visit.peek_mut().unwrap()) = p1;

            self.seen.insert(p1);

        };

        self.conditionally_push_rev(p2);

        Some(Ok(current))

    }

}

impl<G: Graph + Clone> LazyAncestors<G> {

    pub fn new(

        graph: G,

        initrevs: impl IntoIterator<Item = Revision>,

        stoprev: Revision,

        inclusive: bool,

    ) -> Result<Self, GraphError> {

        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: stoprev,

            inclusive: inclusive,

        })

    }

    pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> {

        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()

    }

}

impl<G: Graph> MissingAncestors<G> {

    pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {

        let mut bases: HashSet<Revision> = bases.into_iter().collect();

        if bases.is_empty() {

            bases.insert(NULL_REVISION);

        }

        MissingAncestors { graph, bases }

    }

    pub fn has_bases(&self) -> bool {

        self.bases.iter().any(|&b| b != NULL_REVISION)

    }

    /// Return a reference to current bases.

    ///

    /// This is useful in unit tests, but also setdiscovery.py does

    /// read the bases attribute of a ancestor.missingancestors instance.

    pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {

        &self.bases

    }

    pub fn add_bases(

        &mut self,

        new_bases: impl IntoIterator<Item = Revision>,

    ) {

        self.bases.extend(new_bases);

    }

    /// Remove all ancestors of self.bases from the revs set (in place)

    pub fn remove_ancestors_from(

        &mut self,

        revs: &mut HashSet<Revision>,

    ) -> Result<(), GraphError> {

        revs.retain(|r| !self.bases.contains(r));

        // the null revision is always an ancestor

        revs.remove(&NULL_REVISION);

        if revs.is_empty() {

            return Ok(());

        }

        // anything in revs > start is definitely not an ancestor of bases

        // revs <= start need to be investigated

        // TODO optim: if a missingancestors is to be used several times,

        // we shouldn't need to iterate each time on bases

        let start = match self.bases.iter().cloned().max() {

            Some(m) => m,

            None => {

                // bases is empty (shouldn't happen, but let's be safe)

                return Ok(());

            }

        };

        // whatever happens, we'll keep at least keepcount of them

        // knowing this gives us a earlier stop condition than

        // going all the way to the root

        let keepcount = revs.iter().filter(|r| **r > start).count();

        let mut curr = start;

        while curr != NULL_REVISION && revs.len() > keepcount {

            if self.bases.contains(&curr) {

                revs.remove(&curr);

                self.add_parents(curr)?;

            }

            curr -= 1;

        }

        Ok(())

    }

    /// Add rev's parents to self.bases

    #[inline]

    fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {

        // No need to bother the set with inserting NULL_REVISION over and

        // over

        for p in self.graph.parents(rev)?.iter().cloned() {

            if p != NULL_REVISION {

                self.bases.insert(p);

            }

        }

        Ok(())

    }

    /// Return all the ancestors of revs that are not ancestors of self.bases

    ///

    /// This may include elements from revs.

    ///

    /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in

    /// revision number order, which is a topological order.

    pub fn missing_ancestors(

        &mut self,

        revs: impl IntoIterator<Item = Revision>,

    ) -> Result<Vec<Revision>, GraphError> {

        // just for convenience and comparison with Python version

        let bases_visit = &mut self.bases;

        let mut revs: HashSet<Revision> = revs

            .into_iter()

            .filter(|r| !bases_visit.contains(r))

            .collect();

        let revs_visit = &mut revs;

        let mut both_visit: HashSet<Revision> =

            revs_visit.intersection(&bases_visit).cloned().collect();

        if revs_visit.is_empty() {

            return Ok(Vec::new());

        }

        let max_bases =

            bases_visit.iter().cloned().max().unwrap_or(NULL_REVISION);

        let max_revs =

            revs_visit.iter().cloned().max().unwrap_or(NULL_REVISION);

        let start = max(max_bases, max_revs);

        // TODO heuristics for with_capacity()?

        let mut missing: Vec<Revision> = Vec::new();

        for curr in (0..=start).rev() {

            if revs_visit.is_empty() {

                break;

            }

            if both_visit.contains(&curr) {

                // curr's parents might have made it into revs_visit through

                // another path

                // TODO optim: Rust's HashSet.remove returns a boolean telling

                // if it happened. This will spare us one set lookup

                both_visit.remove(&curr);

                for p in self.graph.parents(curr)?.iter().cloned() {

                    if p == NULL_REVISION {

                        continue;

                    }