// 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 crate::dagops;

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,

}

pub struct MissingAncestors<G: Graph> {

    graph: G,

    bases: HashSet<Revision>,

    max_base: 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().cloned().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)?.iter().cloned() {

                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, 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().cloned()

    }

    /// 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.insert(p1) {

            self.visit.pop();

        } else {

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

        };

        self.conditionally_push_rev(p2);

        Some(Ok(current))

    }

}

impl<G: Graph> MissingAncestors<G> {

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

        let mut created = MissingAncestors {

            graph,

            bases: HashSet::new(),

            max_base: NULL_REVISION,

        };

        created.add_bases(bases);

        created

    }

    pub fn has_bases(&self) -> bool {

        !self.bases.is_empty()

    }

    /// 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

    }

    /// Computes the relative heads of current bases.

    ///

    /// The object is still usable after this.

    pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {

        dagops::heads(&self.graph, self.bases.iter())

    }

    /// Consumes the object and returns the relative heads of its bases.

    pub fn into_bases_heads(

        mut self,

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

        dagops::retain_heads(&self.graph, &mut self.bases)?;

        Ok(self.bases)

    }

    /// Add some revisions to `self.bases`

    ///

    /// Takes care of keeping `self.max_base` up to date.

    pub fn add_bases(

        &mut self,

        new_bases: impl IntoIterator<Item = Revision>,

    ) {

        let mut max_base = self.max_base;

        self.bases.extend(

            new_bases

                .into_iter()

                .filter(|&rev| rev != NULL_REVISION)

                .map(|r| {

                    if r > max_base {

                        max_base = r;

                    }

                    r

                }),

        );

        self.max_base = max_base;

    }

    /// 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. Logically speaking

        // it's debatable in case bases is empty, but the Python

        // implementation always adds NULL_REVISION to bases, making it

        // unconditionnally true.

        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

        if self.max_base == NULL_REVISION {

            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 > self.max_base).count();

        let mut curr = self.max_base;

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

            if self.bases.contains(&curr) {

                revs.remove(&curr);

                self.add_parents(curr)?;

            }

            curr -= 1;

        }

        Ok(())

    }

    /// Add the parents of `rev` to `self.bases`

    ///

    /// This has no effect on `self.max_base`

    #[inline]

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

        if rev == NULL_REVISION {

            return Ok(());

        }

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

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

            // over

            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_revs = revs_visit.iter().cloned().max().unwrap();

        let start = max(self.max_base, 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.remove(&curr) {

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

                // another path

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

                    if p == NULL_REVISION {

                        continue;

                    }

                    revs_visit.remove(&p);

                    bases_visit.insert(p);

                    both_visit.insert(p);

                }

            } else if revs_visit.remove(&curr) {

                missing.push(curr);

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

                    if p == NULL_REVISION {

                        continue;

                    }

                    if bases_visit.contains(&p) {

                        // p is already known to be an ancestor of revs_visit

                        revs_visit.remove(&p);

                        both_visit.insert(p);

                    } else if both_visit.contains(&p) {

                        // p should have been in bases_visit

                        revs_visit.remove(&p);

                        bases_visit.insert(p);

                    } else {

                        // visit later

                        revs_visit.insert(p);

                    }

                }

            } else if bases_visit.contains(&curr) {

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

                    if p == NULL_REVISION {

                        continue;

                    }

                    if revs_visit.remove(&p) || both_visit.contains(&p) {

                        // p is an ancestor of bases_visit, and is implicitly

                        // in revs_visit, which means p is ::revs & ::bases.

                        bases_visit.insert(p);

                        both_visit.insert(p);

                    } else {

                        bases_visit.insert(p);

                    }