comparison rust/hg-core/src/ancestors.rs @ 41246:619ee4039bd4

rust: MissingAncestors.basesheads()

This new API method on `MissingAncestors` leverages directly the
Rust implementation for relative heads of a set, and also
lowers the cost of returning the results to Python in the context of
discovery.

These interchange costs can probably be further reduced by implementing
the `partialdiscovery` class in Rust, but that will be investigated in the
5.0 development cycle.

Differential Revision: https://phab.mercurial-scm.org/D5584

41245:2a8782cc2e16

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

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

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

    #[test]
    /// Test constructor, add/get bases
    fn test_missing_bases() {
        let mut missing_ancestors =
            MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
        let mut as_vec: Vec<Revision> =
            missing_ancestors.get_bases().iter().cloned().collect();
        as_vec.sort();

        missing_ancestors.add_bases([3, 7, 8].iter().cloned());
        as_vec = missing_ancestors.get_bases().iter().cloned().collect();
        as_vec.sort();
        assert_eq!(as_vec, [1, 3, 5, 7, 8]);
    }

    fn assert_missing_remove(
        bases: &[Revision],
        revs: &[Revision],

41246:619ee4039bd4

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

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

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

    pub fn add_bases(
        &mut self,
        new_bases: impl IntoIterator<Item = Revision>,

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

    #[test]
    /// Test constructor, add/get bases and heads
    fn test_missing_bases() -> Result<(), GraphError> {
        let mut missing_ancestors =
            MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
        let mut as_vec: Vec<Revision> =
            missing_ancestors.get_bases().iter().cloned().collect();
        as_vec.sort();

        missing_ancestors.add_bases([3, 7, 8].iter().cloned());
        as_vec = missing_ancestors.get_bases().iter().cloned().collect();
        as_vec.sort();
        assert_eq!(as_vec, [1, 3, 5, 7, 8]);

        as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
        as_vec.sort();
        assert_eq!(as_vec, [3, 5, 7, 8]);
        Ok(())
    }

    fn assert_missing_remove(
        bases: &[Revision],
        revs: &[Revision],