( )⚙ D6230 rust-dagops: roots

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D6230

rust-dagops: roots
ClosedPublic

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

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGbe0733552984: rust-dagops: roots
Summary

Unsuprisingly, the algorithm is much easier than for heads, provided
we work on a set in the first place.

To improve the signature, a trait for set-likes object would be useful,
but that's not an immediate concern.

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:51 PM
kevincox added inline comments.
rust/hg-core/src/dagops.rs
96

I think it is more clear to write .iter().filter(|p| *p != NULL_REVISION).all(|p| !revs.contains(p)). This separates the NULLs from the revs you care about and makes that condition easier to parse.

gracinet marked an inline comment as done.Apr 15 2019, 6:10 AM
gracinet updated this revision to Diff 14741.
gracinet added inline comments.Apr 15 2019, 6:11 AM
rust/hg-core/src/dagops.rs
96

Thanks for the suggestion.

Anticipating on a discussion to have later, I'd like eventually the Graph::parents() returns an iterator. The advantages will be made obvious by the (not submitted yet) final changesets of the` PartialDiscovery` implementation in hg-core. In other words, NULL_REVISION and the fact to have exactly two parents should be considered implementation details of the underlying storage.

kevincox added inline comments.Apr 15 2019, 6:23 AM
rust/hg-core/src/dagops.rs
96

That sounds great. NULL_REVISION always seemed quite messy to me. It would definitely be best to filter it out as soon as possible.

Closed by commit rHGbe0733552984: rust-dagops: roots (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 (44 lines)

Diff 14719

rust/hg-core/src/dagops.rs

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(())
} }
/// Roots of `revs`, passed as a `HashSet`
///
/// They are returned in arbitrary order
pub fn roots<G: Graph>(
graph: &G,
revs: &HashSet<Revision>,
) -> Result<Vec<Revision>, GraphError> {
let mut roots: Vec<Revision> = Vec::new();
for rev in revs {
if graph
.parents(*rev)?
.iter()
.all(|p| *p == NULL_REVISION || !revs.contains(p))
kevincoxUnsubmitted
Done

I think it is more clear to write .iter().filter(|p| *p != NULL_REVISION).all(|p| !revs.contains(p)). This separates the NULLs from the revs you care about and makes that condition easier to parse.

kevincox: I think it is more clear to write `.iter().filter(|p| *p != NULL_REVISION).all(|p| !revs.
gracinetAuthorUnsubmitted
Not Done

Thanks for the suggestion.

Anticipating on a discussion to have later, I'd like eventually the Graph::parents() returns an iterator. The advantages will be made obvious by the (not submitted yet) final changesets of the` PartialDiscovery` implementation in hg-core. In other words, NULL_REVISION and the fact to have exactly two parents should be considered implementation details of the underlying storage.

gracinet: Thanks for the suggestion. Anticipating on a discussion to have later, I'd like eventually…
kevincoxUnsubmitted
Not Done

That sounds great. NULL_REVISION always seemed quite messy to me. It would definitely be best to filter it out as soon as possible.

kevincox: That sounds great. `NULL_REVISION` always seemed quite messy to me. It would definitely be best…
{
roots.push(*rev);
}
}
Ok(roots)
}
/// Compute the topological range between two collections of revisions /// Compute the topological range between two collections of revisions
/// ///
/// This is equivalent to the revset `<roots>::<heads>`. /// This is equivalent to the revset `<roots>::<heads>`.
/// ///
/// Currently, the given `Graph` has to implement `Clone`, which means /// Currently, the given `Graph` has to implement `Clone`, which means
/// actually cloning just a reference-counted Python pointer if /// actually cloning just a reference-counted Python pointer if
/// it's passed over through `rust-cpython`. This is due to the internal /// it's passed over through `rust-cpython`. This is due to the internal
/// use of `AncestorsIterator` /// use of `AncestorsIterator`
); );
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 `roots()` and sort the result for easier comparison
fn roots_sorted(
graph: &impl Graph,
revs: &[Revision],
) -> Result<Vec<Revision>, GraphError> {
let mut as_vec = roots(graph, &revs.iter().cloned().collect())?;
as_vec.sort();
Ok(as_vec)
}
#[test]
fn test_roots() -> Result<(), GraphError> {
assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]);
assert_eq!(
roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
vec![0, 4, 12]
);
assert_eq!(
roots_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
vec![1, 8]
);
Ok(())
}
/// Apply `range()` and convert the result into a Vec for easier comparison /// Apply `range()` and convert the result into a Vec for easier comparison
fn range_vec( fn range_vec(
graph: impl Graph + Clone, graph: impl Graph + Clone,
roots: &[Revision], roots: &[Revision],
heads: &[Revision], heads: &[Revision],
) -> Result<Vec<Revision>, GraphError> { ) -> Result<Vec<Revision>, GraphError> {
range(&graph, roots.iter().cloned(), heads.iter().cloned()) range(&graph, roots.iter().cloned(), heads.iter().cloned())
.map(|bs| bs.iter().cloned().collect()) .map(|bs| bs.iter().cloned().collect())