This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5584

rust: MissingAncestors.basesheads()
ClosedPublic

Authored by gracinet on Jan 14 2019, 9:14 PM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG619ee4039bd4: rust: MissingAncestors.basesheads()
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

gracinet created this revision.Jan 14 2019, 9:14 PM
Closed by commit rHG619ee4039bd4: rust: MissingAncestors.basesheads() (authored by gracinet). · Explain WhyJan 16 2019, 7:44 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 13255

rust/hg-core/src/ancestors.rs

// ancestors.rs // ancestors.rs
// //
// Copyright 2018 Georges Racinet <gracinet@anybox.fr> // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Rust versions of generic DAG ancestors algorithms for Mercurial //! Rust versions of generic DAG ancestors algorithms for Mercurial
use super::{Graph, GraphError, Revision, NULL_REVISION}; use super::{Graph, GraphError, Revision, NULL_REVISION};
use std::cmp::max; use std::cmp::max;
use std::collections::{BinaryHeap, HashSet}; use std::collections::{BinaryHeap, HashSet};
use crate::dagops;
/// Iterator over the ancestors of a given list of revisions /// Iterator over the ancestors of a given list of revisions
/// This is a generic type, defined and implemented for any Graph, so that /// This is a generic type, defined and implemented for any Graph, so that
/// it's easy to /// it's easy to
/// ///
/// - unit test in pure Rust /// - unit test in pure Rust
/// - bind to main Mercurial code, potentially in several ways and have these /// - bind to main Mercurial code, potentially in several ways and have these
/// bindings evolve over time /// bindings evolve over time
/// Return a reference to current bases. /// Return a reference to current bases.
/// ///
/// This is useful in unit tests, but also setdiscovery.py does /// This is useful in unit tests, but also setdiscovery.py does
/// read the bases attribute of a ancestor.missingancestors instance. /// read the bases attribute of a ancestor.missingancestors instance.
pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> { pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
&self.bases &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( pub fn add_bases(
&mut self, &mut self,
new_bases: impl IntoIterator<Item = Revision>, new_bases: impl IntoIterator<Item = Revision>,
) { ) {
self.bases.extend(new_bases); self.bases.extend(new_bases);
} }
/// Remove all ancestors of self.bases from the revs set (in place) /// Remove all ancestors of self.bases from the revs set (in place)
assert_eq!(lazy.contains(5), Ok(false)); assert_eq!(lazy.contains(5), Ok(false));
// iter() still gives us a fresh iterator // iter() still gives us a fresh iterator
let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
} }
#[test] #[test]
/// Test constructor, add/get bases /// Test constructor, add/get bases and heads
fn test_missing_bases() { fn test_missing_bases() -> Result<(), GraphError> {
let mut missing_ancestors = let mut missing_ancestors =
MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
let mut as_vec: Vec<Revision> = let mut as_vec: Vec<Revision> =
missing_ancestors.get_bases().iter().cloned().collect(); missing_ancestors.get_bases().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [1, 3, 5]); assert_eq!(as_vec, [1, 3, 5]);
missing_ancestors.add_bases([3, 7, 8].iter().cloned()); missing_ancestors.add_bases([3, 7, 8].iter().cloned());
as_vec = missing_ancestors.get_bases().iter().cloned().collect(); as_vec = missing_ancestors.get_bases().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [1, 3, 5, 7, 8]); 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( fn assert_missing_remove(
bases: &[Revision], bases: &[Revision],
revs: &[Revision], revs: &[Revision],
expected: &[Revision], expected: &[Revision],
) { ) {
let mut missing_ancestors = let mut missing_ancestors =

rust/hg-cpython/src/ancestors.rs

// so let's return an explicit None // so let's return an explicit None
Ok(py.None()) Ok(py.None())
} }
def bases(&self) -> PyResult<PyObject> { def bases(&self) -> PyResult<PyObject> {
py_set(py, self.inner(py).borrow().get_bases()) py_set(py, self.inner(py).borrow().get_bases())
} }
def basesheads(&self) -> PyResult<PyObject> {
let inner = self.inner(py).borrow();
py_set(py, &inner.bases_heads().map_err(|e| GraphError::pynew(py, e))?)
}
def removeancestorsfrom(&self, revs: PyObject) -> PyResult<PyObject> { def removeancestorsfrom(&self, revs: PyObject) -> PyResult<PyObject> {
let mut inner = self.inner(py).borrow_mut(); let mut inner = self.inner(py).borrow_mut();
// this is very lame: we convert to a Rust set, update it in place // this is very lame: we convert to a Rust set, update it in place
// and then convert back to Python, only to have Python remove the // and then convert back to Python, only to have Python remove the
// excess (thankfully, Python is happy with a list or even an iterator) // excess (thankfully, Python is happy with a list or even an iterator)
// Leads to improve this: // Leads to improve this:
// - have the CoreMissing instead do something emit revisions to // - have the CoreMissing instead do something emit revisions to
// discard // discard

tests/test-rust-ancestor.py

def testmissingancestors(self): def testmissingancestors(self):
idx = self.parseindex() idx = self.parseindex()
missanc = MissingAncestors(idx, [1]) missanc = MissingAncestors(idx, [1])
self.assertTrue(missanc.hasbases()) self.assertTrue(missanc.hasbases())
self.assertEqual(missanc.missingancestors([3]), [2, 3]) self.assertEqual(missanc.missingancestors([3]), [2, 3])
missanc.addbases({2}) missanc.addbases({2})
self.assertEqual(missanc.bases(), {1, 2}) self.assertEqual(missanc.bases(), {1, 2})
self.assertEqual(missanc.missingancestors([3]), [3]) self.assertEqual(missanc.missingancestors([3]), [3])
self.assertEqual(missanc.basesheads(), {2})
def testmissingancestorsremove(self): def testmissingancestorsremove(self):
idx = self.parseindex() idx = self.parseindex()
missanc = MissingAncestors(idx, [1]) missanc = MissingAncestors(idx, [1])
revs = {0, 1, 2, 3} revs = {0, 1, 2, 3}
missanc.removeancestorsfrom(revs) missanc.removeancestorsfrom(revs)
self.assertEqual(revs, {2, 3}) self.assertEqual(revs, {2, 3})