mercurial-scm/hg: rust/hg-core/src/dagops.rs annotate

annotate rust/hg-core/src/dagops.rs @ 52029:88aa21d654e5

rust-dirstate: actually remember the identity This was an oversight that likely had no influence on anything since we have only been writing the dirstate for status. We will start writing the dirstate for more operations now, so we'll need this fixed.

author	Rapha?l Gom?s <rgomes@octobus.net>
date	Mon, 30 Sep 2024 17:43:51 +0200
parents	c4f1a790bda8
children

rev	line source
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	1 // dagops.rs
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	2 //
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	3 // Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	4 //
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	5 // This software may be used and distributed according to the terms of the
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	6 // GNU General Public License version 2 or any later version.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	7
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	8 //! Miscellaneous DAG operations
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	9 //!
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	10 //! # Terminology
42841 ce6797ef6eab rust: apply more formatting fixes Yuya Nishihara <yuya@tcha.org> parents: 42177 diff changeset	11 //! - By relative heads of a collection of revision numbers (`Revision`), we
ce6797ef6eab rust: apply more formatting fixes Yuya Nishihara <yuya@tcha.org> parents: 42177 diff changeset	12 //! mean those revisions that have no children among the collection.
ce6797ef6eab rust: apply more formatting fixes Yuya Nishihara <yuya@tcha.org> parents: 42177 diff changeset	13 //! - Similarly relative roots of a collection of `Revision`, we mean those
ce6797ef6eab rust: apply more formatting fixes Yuya Nishihara <yuya@tcha.org> parents: 42177 diff changeset	14 //! whose parents, if any, don't belong to the collection.
51257 c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	15 use bitvec::slice::BitSlice;
c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	16
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	17 use super::{Graph, GraphError, Revision, NULL_REVISION};
51256 ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	18 use crate::{ancestors::AncestorsIterator, BaseRevision};
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	19 use std::collections::{BTreeSet, HashSet};
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	20
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	21 fn remove_parents<S: std::hash::BuildHasher>(
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	22 graph: &impl Graph,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	23 rev: Revision,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	24 set: &mut HashSet<Revision, S>,
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	25 ) -> Result<(), GraphError> {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	26 for parent in graph.parents(rev)?.iter() {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	27 if *parent != NULL_REVISION {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	28 set.remove(parent);
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	29 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	30 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	31 Ok(())
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	32 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	33
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	34 /// Relative heads out of some revisions, passed as an iterator.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	35 ///
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	36 /// These heads are defined as those revisions that have no children
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	37 /// among those emitted by the iterator.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	38 ///
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	39 /// # Performance notes
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	40 /// Internally, this clones the iterator, and builds a `HashSet` out of it.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	41 ///
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	42 /// This function takes an `Iterator` instead of `impl IntoIterator` to
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	43 /// guarantee that cloning the iterator doesn't result in cloning the full
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	44 /// construct it comes from.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	45 pub fn heads<'a>(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	46 graph: &impl Graph,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	47 iter_revs: impl Clone + Iterator<Item = &'a Revision>,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	48 ) -> Result<HashSet<Revision>, GraphError> {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	49 let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect();
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	50 heads.remove(&NULL_REVISION);
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	51 for rev in iter_revs {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	52 if *rev != NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	53 remove_parents(graph, *rev, &mut heads)?;
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	54 }
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	55 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	56 Ok(heads)
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	57 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	58
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	59 /// Retain in `revs` only its relative heads.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	60 ///
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	61 /// This is an in-place operation, so that control of the incoming
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	62 /// set is left to the caller.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	63 /// - a direct Python binding would probably need to build its own `HashSet`
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	64 /// from an incoming iterable, even if its sole purpose is to extract the
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	65 /// heads.
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	66 /// - a Rust caller can decide whether cloning beforehand is appropriate
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	67 ///
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	68 /// # Performance notes
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	69 /// Internally, this function will store a full copy of `revs` in a `Vec`.
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	70 pub fn retain_heads<S: std::hash::BuildHasher>(
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	71 graph: &impl Graph,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	72 revs: &mut HashSet<Revision, S>,
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	73 ) -> Result<(), GraphError> {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	74 revs.remove(&NULL_REVISION);
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	75 // we need to construct an iterable copy of revs to avoid itering while
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	76 // mutating
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	77 let as_vec: Vec<Revision> = revs.iter().cloned().collect();
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	78 for rev in as_vec {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	79 if rev != NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	80 remove_parents(graph, rev, revs)?;
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41242 diff changeset	81 }
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	82 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	83 Ok(())
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	84 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	85
51257 c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	86 /// Optimized version of `retain_heads` that expects an zeroed bitvec of the
c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	87 /// size of the graph, to act as a faster but less space-efficient `HashSet`.
51256 ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	88 ///
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	89 /// # Panics
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	90 ///
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	91 /// Can panic if `not_heads` is shorten than the length of graph.
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	92 pub fn retain_heads_fast(
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	93 graph: &impl Graph,
51257 c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	94 not_heads: &mut BitSlice,
51256 ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	95 filtered_revs: &HashSet<Revision>,
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	96 ) -> Result<(), GraphError> {
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	97 for idx in (0..not_heads.len()).rev() {
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	98 let rev = Revision(idx as BaseRevision);
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	99 if !not_heads[idx] && filtered_revs.contains(&rev) {
51257 c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	100 not_heads.get_mut(idx).unwrap().commit(true);
51256 ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	101 continue;
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	102 }
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	103 for parent in graph.parents(rev)?.iter() {
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	104 if *parent != NULL_REVISION {
51257 c4f1a790bda8 rust-index: use a `BitVec` instead of plain `Vec` for heads computation Rapha?l Gom?s <rgomes@octobus.net> parents: 51256 diff changeset	105 not_heads.get_mut(parent.0 as usize).unwrap().commit(true);
51256 ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	106 }
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	107 }
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	108 }
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	109 Ok(())
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	110 }
ed6683d4cb29 rust-index: implement faster retain heads using a vec instead of a hashset Rapha?l Gom?s <rgomes@octobus.net> parents: 51117 diff changeset	111
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	112 /// Roots of `revs`, passed as a `HashSet`
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	113 ///
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	114 /// They are returned in arbitrary order
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	115 pub fn roots<G: Graph, S: std::hash::BuildHasher>(
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	116 graph: &G,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	117 revs: &HashSet<Revision, S>,
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	118 ) -> Result<Vec<Revision>, GraphError> {
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	119 let mut roots: Vec<Revision> = Vec::new();
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	120 for rev in revs {
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	121 if graph
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	122 .parents(*rev)?
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	123 .iter()
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	124 .filter(\|p\| **p != NULL_REVISION)
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	125 .all(\|p\| !revs.contains(p))
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	126 {
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	127 roots.push(*rev);
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	128 }
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	129 }
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	130 Ok(roots)
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	131 }
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	132
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	133 /// Compute the topological range between two collections of revisions
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	134 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	135 /// This is equivalent to the revset `<roots>::<heads>`.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	136 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	137 /// Currently, the given `Graph` has to implement `Clone`, which means
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	138 /// actually cloning just a reference-counted Python pointer if
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	139 /// it's passed over through `rust-cpython`. This is due to the internal
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	140 /// use of `AncestorsIterator`
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	141 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	142 /// # Algorithmic details
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	143 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	144 /// This is a two-pass swipe inspired from what `reachableroots2` from
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	145 /// `mercurial.cext.parsers` does to obtain the same results.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	146 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	147 /// - first, we climb up the DAG from `heads` in topological order, keeping
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	148 /// them in the vector `heads_ancestors` vector, and adding any element of
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	149 /// `roots` we find among them to the resulting range.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	150 /// - Then, we iterate on that recorded vector so that a revision is always
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	151 /// emitted after its parents and add all revisions whose parents are already
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	152 /// in the range to the results.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	153 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	154 /// # Performance notes
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	155 ///
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	156 /// The main difference with the C implementation is that
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	157 /// the latter uses a flat array with bit flags, instead of complex structures
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	158 /// like `HashSet`, making it faster in most scenarios. In theory, it's
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	159 /// possible that the present implementation could be more memory efficient
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	160 /// for very large repositories with many branches.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	161 pub fn range(
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	162 graph: &(impl Graph + Clone),
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	163 roots: impl IntoIterator<Item = Revision>,
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	164 heads: impl IntoIterator<Item = Revision>,
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	165 ) -> Result<BTreeSet<Revision>, GraphError> {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	166 let mut range = BTreeSet::new();
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	167 let roots: HashSet<Revision> = roots.into_iter().collect();
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	168 let min_root: Revision = match roots.iter().cloned().min() {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	169 None => {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	170 return Ok(range);
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	171 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	172 Some(r) => r,
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	173 };
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	174
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	175 // Internally, AncestorsIterator currently maintains a `HashSet`
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	176 // of all seen revision, which is also what we record, albeit in an ordered
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	177 // way. There's room for improvement on this duplication.
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	178 let ait = AncestorsIterator::new(graph.clone(), heads, min_root, true)?;
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	179 let mut heads_ancestors: Vec<Revision> = Vec::new();
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	180 for revres in ait {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	181 let rev = revres?;
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	182 if roots.contains(&rev) {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	183 range.insert(rev);
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	184 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	185 heads_ancestors.push(rev);
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	186 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	187
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	188 for rev in heads_ancestors.into_iter().rev() {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	189 for parent in graph.parents(rev)?.iter() {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	190 if *parent != NULL_REVISION && range.contains(parent) {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	191 range.insert(rev);
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	192 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	193 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	194 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	195 Ok(range)
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	196 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	197
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	198 #[cfg(test)]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	199 mod tests {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	200
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	201 use super::*;
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	202 use crate::{testing::SampleGraph, BaseRevision};
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	203
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	204 /// Apply `retain_heads()` to the given slice and return as a sorted `Vec`
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	205 fn retain_heads_sorted(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	206 graph: &impl Graph,
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	207 revs: &[BaseRevision],
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	208 ) -> Result<Vec<Revision>, GraphError> {
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	209 let mut revs: HashSet<Revision> =
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	210 revs.iter().cloned().map(Revision).collect();
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	211 retain_heads(graph, &mut revs)?;
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	212 let mut as_vec: Vec<Revision> = revs.iter().cloned().collect();
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 44973 diff changeset	213 as_vec.sort_unstable();
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	214 Ok(as_vec)
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	215 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	216
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	217 #[test]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	218 fn test_retain_heads() -> Result<(), GraphError> {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	219 assert_eq!(retain_heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	220 assert_eq!(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	221 retain_heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	222 vec![1, 6, 12]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	223 );
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	224 assert_eq!(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	225 retain_heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	226 vec![3, 5, 8, 9]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	227 );
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	228 Ok(())
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	229 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	230
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	231 /// Apply `heads()` to the given slice and return as a sorted `Vec`
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	232 fn heads_sorted(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	233 graph: &impl Graph,
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	234 revs: &[BaseRevision],
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	235 ) -> Result<Vec<Revision>, GraphError> {
51117 532e74ad3ff6 rust: run a clippy pass with the latest stable version Rapha?l Gom?s <rgomes@octobus.net> parents: 50976 diff changeset	236 let iter_revs: Vec<_> = revs.iter().cloned().map(Revision).collect();
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	237 let heads = heads(graph, iter_revs.iter())?;
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	238 let mut as_vec: Vec<Revision> = heads.iter().cloned().collect();
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 44973 diff changeset	239 as_vec.sort_unstable();
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	240 Ok(as_vec)
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	241 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	242
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	243 #[test]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	244 fn test_heads() -> Result<(), GraphError> {
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	245 assert_eq!(heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	246 assert_eq!(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	247 heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	248 vec![1, 6, 12]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	249 );
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	250 assert_eq!(
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	251 heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	252 vec![3, 5, 8, 9]
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	253 );
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	254 Ok(())
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	255 }
47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	256
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	257 /// Apply `roots()` and sort the result for easier comparison
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	258 fn roots_sorted(
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	259 graph: &impl Graph,
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	260 revs: &[BaseRevision],
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	261 ) -> Result<Vec<Revision>, GraphError> {
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	262 let set: HashSet<_> = revs.iter().cloned().map(Revision).collect();
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	263 let mut as_vec = roots(graph, &set)?;
49930 e98fd81bb151 rust-clippy: fix most warnings in `hg-core` Rapha?l Gom?s <rgomes@octobus.net> parents: 44973 diff changeset	264 as_vec.sort_unstable();
42177 be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	265 Ok(as_vec)
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	266 }
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	267
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	268 #[test]
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	269 fn test_roots() -> Result<(), GraphError> {
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	270 assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]);
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	271 assert_eq!(
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	272 roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	273 vec![0, 4, 12]
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	274 );
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	275 assert_eq!(
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	276 roots_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	277 vec![1, 8]
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	278 );
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	279 Ok(())
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	280 }
be0733552984 rust-dagops: roots Georges Racinet <georges.racinet@octobus.net> parents: 42176 diff changeset	281
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	282 /// Apply `range()` and convert the result into a Vec for easier comparison
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	283 fn range_vec(
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	284 graph: impl Graph + Clone,
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	285 roots: &[BaseRevision],
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	286 heads: &[BaseRevision],
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	287 ) -> Result<Vec<Revision>, GraphError> {
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	288 range(
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	289 &graph,
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	290 roots.iter().cloned().map(Revision),
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	291 heads.iter().cloned().map(Revision),
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	292 )
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	293 .map(\|bs\| bs.into_iter().collect())
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	294 }
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	295
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	296 #[test]
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	297 fn test_range() -> Result<(), GraphError> {
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	298 assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]);
50976 4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	299 assert_eq!(
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	300 range_vec(SampleGraph, &[0], &[8])?,
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	301 Vec::<Revision>::new()
4c5f6e95df84 rust: make `Revision` a newtype Rapha?l Gom?s <rgomes@octobus.net> parents: 49930 diff changeset	302 );
42176 3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	303 assert_eq!(
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	304 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?,
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	305 vec![5, 10]
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	306 );
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	307 assert_eq!(
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	308 range_vec(SampleGraph, &[5, 6], &[10, 12])?,
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	309 vec![5, 6, 9, 10, 12]
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	310 );
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	311 Ok(())
3bdb21bbf791 rust-dagops: range of revisions Georges Racinet <georges.racinet@octobus.net> parents: 41717 diff changeset	312 }
41242 47881d2a9d99 rust: dagop.headrevs() Rust counterparts Georges Racinet on ishtar.racinet.fr <georges@racinet.fr> parents: diff changeset	313 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/dagops.rs @ 52029:88aa21d654e5