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
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.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() {
   // ...
}
213

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.

213

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

Diff 14850

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);
}
for rev in heads_ancestors.into_iter().rev() {
for parent in graph.parents(rev)?.iter() {
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…
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.into_iter().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(())
}
} }