This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6229

rust-dagops: range of revisions
ClosedPublic

Authored by gracinet on Apr 12 2019, 2:33 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG3bdb21bbf791: rust-dagops: range of revisions
Summary

This is a Rust implementation for what reachableroots2() does if
includepath is True.

The algorithmic details and performance notes are included in the
documentation comment.

Our main use case for now is a Rust counterpart of the partialdiscovery
object, so we don't really need bindings yet.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.Apr 12 2019, 2:33 PM
kevincox accepted this revision.Apr 14 2019, 3:45 PM
kevincox added inline comments.
rust/hg-core/src/dagops.rs
140

Can you use:

for rev in heads_ancestors.into_iter().rev() {
   // ...
}
215

Can you use .into_iter() instead of .iter().cloned()?

gracinet marked 2 inline comments as done.Apr 15 2019, 5:50 AM
gracinet added inline comments.
rust/hg-core/src/dagops.rs
140

Ah yes, thanks, I've been looking for something like that on DoubleEndedIterator and couldn't find it, because it's actually on Iterator with a where Self: DoubleEndedIterator.

215

Sure, I should probably take more advantage of such cases, where we don't need the original object anymore.

gracinet marked 2 inline comments as done.Apr 15 2019, 6:10 AM
gracinet updated this revision to Diff 14740.
gracinet added a comment.Apr 15 2019, 6:13 AM

@kevincox, thanks for the review, updated version available.

Closed by commit rHG3bdb21bbf791: rust-dagops: range of revisions (authored by gracinet). · Explain WhyApr 18 2019, 7:25 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/dagops.rs (95 lines)

Diff 14718

rust/hg-core/src/dagops.rs

// dagops.rs // dagops.rs
// //
// Copyright 2019 Georges Racinet <georges.racinet@octobus.net> // Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
// //
// 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.
//! Miscellaneous DAG operations //! Miscellaneous DAG operations
//! //!
//! # Terminology //! # Terminology
//! - By *relative heads* of a collection of revision numbers (`Revision`), //! - By *relative heads* of a collection of revision numbers (`Revision`),
//! we mean those revisions that have no children among the collection. //! we mean those revisions that have no children among the collection.
//! - Similarly *relative roots* of a collection of `Revision`, we mean //! - Similarly *relative roots* of a collection of `Revision`, we mean
//! those whose parents, if any, don't belong to the collection. //! those whose parents, if any, don't belong to the collection.
use super::{Graph, GraphError, Revision, NULL_REVISION}; use super::{Graph, GraphError, Revision, NULL_REVISION};
use std::collections::HashSet; use crate::ancestors::AncestorsIterator;
use std::collections::{BTreeSet, HashSet};
fn remove_parents( fn remove_parents(
graph: &impl Graph, graph: &impl Graph,
rev: Revision, rev: Revision,
set: &mut HashSet<Revision>, set: &mut HashSet<Revision>,
) -> Result<(), GraphError> { ) -> Result<(), GraphError> {
for parent in graph.parents(rev)?.iter() { for parent in graph.parents(rev)?.iter() {
if *parent != NULL_REVISION { if *parent != NULL_REVISION {
for rev in as_vec { for rev in as_vec {
if rev != NULL_REVISION { if rev != NULL_REVISION {
remove_parents(graph, rev, revs)?; remove_parents(graph, rev, revs)?;
} }
} }
Ok(()) Ok(())
} }
/// Compute the topological range between two collections of revisions
///
/// This is equivalent to the revset `<roots>::<heads>`.
///
/// Currently, the given `Graph` has to implement `Clone`, which means
/// actually cloning just a reference-counted Python pointer if
/// it's passed over through `rust-cpython`. This is due to the internal
/// use of `AncestorsIterator`
///
/// # Algorithmic details
///
/// This is a two-pass swipe inspired from what `reachableroots2` from
/// `mercurial.cext.parsers` does to obtain the same results.
///
/// - first, we climb up the DAG from `heads` in topological order, keeping
/// them in the vector `heads_ancestors` vector, and adding any element of
/// `roots` we find among them to the resulting range.
/// - Then, we iterate on that recorded vector so that a revision is always
/// emitted after its parents and add all revisions whose parents are already
/// in the range to the results.
///
/// # Performance notes
///
/// The main difference with the C implementation is that
/// the latter uses a flat array with bit flags, instead of complex structures
/// like `HashSet`, making it faster in most scenarios. In theory, it's
/// possible that the present implementation could be more memory efficient
/// for very large repositories with many branches.
pub fn range(
graph: &(impl Graph + Clone),
roots: impl IntoIterator<Item = Revision>,
heads: impl IntoIterator<Item = Revision>,
) -> Result<BTreeSet<Revision>, GraphError> {
let mut range = BTreeSet::new();
let roots: HashSet<Revision> = roots.into_iter().collect();
let min_root: Revision = match roots.iter().cloned().min() {
None => {
return Ok(range);
}
Some(r) => r,
};
// Internally, AncestorsIterator currently maintains a `HashSet`
// of all seen revision, which is also what we record, albeit in an ordered
// way. There's room for improvement on this duplication.
let ait = AncestorsIterator::new(graph.clone(), heads, min_root, true)?;
let mut heads_ancestors: Vec<Revision> = Vec::new();
for revres in ait {
let rev = revres?;
if roots.contains(&rev) {
range.insert(rev);
}
heads_ancestors.push(rev);
}
let l = heads_ancestors.len();
for i in 1..=l {
kevincoxUnsubmitted
Done

Can you use:

for rev in heads_ancestors.into_iter().rev() {
   // ...
}
kevincox: Can you use: ``` for rev in heads_ancestors.into_iter().rev() { // ... } ```
gracinetAuthorUnsubmitted
Not Done

Ah yes, thanks, I've been looking for something like that on DoubleEndedIterator and couldn't find it, because it's actually on Iterator with a where Self: DoubleEndedIterator.

gracinet: Ah yes, thanks, I've been looking for something like that on `DoubleEndedIterator` and couldn't…
let rev = heads_ancestors[l - i];
for parent in graph.parents(rev)?.iter() {
if *parent != NULL_REVISION && range.contains(parent) {
range.insert(rev);
}
}
}
Ok(range)
}
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use crate::testing::SampleGraph; use crate::testing::SampleGraph;
/// Apply `retain_heads()` to the given slice and return as a sorted `Vec` /// Apply `retain_heads()` to the given slice and return as a sorted `Vec`
fn retain_heads_sorted( fn retain_heads_sorted(
); );
assert_eq!( assert_eq!(
heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?, heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
vec![3, 5, 8, 9] vec![3, 5, 8, 9]
); );
Ok(()) Ok(())
} }
/// Apply `range()` and convert the result into a Vec for easier comparison
fn range_vec(
graph: impl Graph + Clone,
roots: &[Revision],
heads: &[Revision],
) -> Result<Vec<Revision>, GraphError> {
range(&graph, roots.iter().cloned(), heads.iter().cloned())
.map(|bs| bs.iter().cloned().collect())
kevincoxUnsubmitted
Done

Can you use .into_iter() instead of .iter().cloned()?

kevincox: Can you use `.into_iter()` instead of `.iter().cloned()`?
gracinetAuthorUnsubmitted
Not Done

Sure, I should probably take more advantage of such cases, where we don't need the original object anymore.

gracinet: Sure, I should probably take more advantage of such cases, where we don't need the original…
}
#[test]
fn test_range() -> Result<(), GraphError> {
assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]);
assert_eq!(range_vec(SampleGraph, &[0], &[8])?, vec![]);
assert_eq!(
range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?,
vec![5, 10]
);
assert_eq!(
range_vec(SampleGraph, &[5, 6], &[10, 12])?,
vec![5, 6, 9, 10, 12]
);
Ok(())
}
} }