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
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: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 (45 lines)

Diff 14851

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()
.filter(|p| **p != NULL_REVISION)
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…
.all(|p| !revs.contains(p))
{
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.into_iter().collect()) .map(|bs| bs.into_iter().collect())