Mercurial > hg
annotate rust/hg-core/src/dagops.rs @ 51259:ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
This is the same optimization that the C index does, we're only catching up
now because this showed up as slow in benchmarking.
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Wed, 29 Nov 2023 10:04:41 -0500 |
parents | 532e74ad3ff6 |
children | c4f1a790bda8 |
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. |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
51259
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
16 use crate::{ancestors::AncestorsIterator, BaseRevision}; |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
17 use std::collections::{BTreeSet, HashSet}; |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
18 |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
19 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
|
20 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
21 rev: Revision, |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
22 set: &mut HashSet<Revision, S>, |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
23 ) -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
24 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
|
25 if *parent != NULL_REVISION { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
26 set.remove(parent); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
27 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
28 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
29 Ok(()) |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
32 /// 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
|
33 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
34 /// 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
|
35 /// among those emitted by the iterator. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
36 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
37 /// # Performance notes |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
38 /// 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
|
39 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
40 /// 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
|
41 /// 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
|
42 /// construct it comes from. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
43 pub fn heads<'a>( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
44 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
45 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
|
46 ) -> Result<HashSet<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
47 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
|
48 heads.remove(&NULL_REVISION); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
49 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
|
50 if *rev != NULL_REVISION { |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
51 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
|
52 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
53 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
54 Ok(heads) |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
57 /// 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
|
58 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
59 /// 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
|
60 /// set is left to the caller. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
61 /// - 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
|
62 /// 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
|
63 /// heads. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
64 /// - 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
|
65 /// |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
66 /// # Performance notes |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
67 /// 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
|
68 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
|
69 graph: &impl Graph, |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
70 revs: &mut HashSet<Revision, S>, |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
71 ) -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
72 revs.remove(&NULL_REVISION); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
73 // 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
|
74 // mutating |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
75 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
|
76 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
|
77 if rev != NULL_REVISION { |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
78 remove_parents(graph, rev, revs)?; |
9060af281be7
rust: itering less on MissingAncestors.bases for max()
Georges Racinet <georges.racinet@octobus.net>
parents:
41242
diff
changeset
|
79 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
80 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
81 Ok(()) |
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 |
51259
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
84 /// Optimized version of `retain_heads` that expects an zeroed array of the size |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
85 /// of the graph, to act as a faster but less space-efficient `HashSet`. |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
86 /// |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
87 /// # Panics |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
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:
51120
diff
changeset
|
89 /// 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:
51120
diff
changeset
|
90 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:
51120
diff
changeset
|
91 graph: &impl Graph, |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
92 not_heads: &mut [bool], |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
93 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:
51120
diff
changeset
|
94 ) -> Result<(), GraphError> { |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
95 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:
51120
diff
changeset
|
96 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:
51120
diff
changeset
|
97 if !not_heads[idx] && filtered_revs.contains(&rev) { |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
98 not_heads[idx] = true; |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
99 continue; |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
100 } |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
101 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:
51120
diff
changeset
|
102 if *parent != NULL_REVISION { |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
103 not_heads[parent.0 as usize] = true; |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
104 } |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
diff
changeset
|
105 } |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
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:
51120
diff
changeset
|
107 Ok(()) |
ed6683d4cb29
rust-index: implement faster retain heads using a vec instead of a hashset
Raphaël Gomès <rgomes@octobus.net>
parents:
51120
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:
51120
diff
changeset
|
109 |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
110 /// Roots of `revs`, passed as a `HashSet` |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
111 /// |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
112 /// They are returned in arbitrary order |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
113 pub fn roots<G: Graph, S: std::hash::BuildHasher>( |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
114 graph: &G, |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
115 revs: &HashSet<Revision, S>, |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
116 ) -> Result<Vec<Revision>, GraphError> { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
117 let mut roots: Vec<Revision> = Vec::new(); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
118 for rev in revs { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
119 if graph |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
120 .parents(*rev)? |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
121 .iter() |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
122 .filter(|p| **p != NULL_REVISION) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
123 .all(|p| !revs.contains(p)) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
124 { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
125 roots.push(*rev); |
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 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
128 Ok(roots) |
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 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
131 /// 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
|
132 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
133 /// This is equivalent to the revset `<roots>::<heads>`. |
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 /// 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
|
136 /// 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
|
137 /// 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
|
138 /// use of `AncestorsIterator` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
139 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
140 /// # Algorithmic details |
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 /// 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
|
143 /// `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
|
144 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
145 /// - 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
|
146 /// 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
|
147 /// `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
|
148 /// - 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
|
149 /// 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
|
150 /// in the range to the results. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
151 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
152 /// # Performance notes |
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 /// 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
|
155 /// 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
|
156 /// 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
|
157 /// 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
|
158 /// for very large repositories with many branches. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
159 pub fn range( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
160 graph: &(impl Graph + Clone), |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
161 roots: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
162 heads: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
163 ) -> Result<BTreeSet<Revision>, GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
164 let mut range = BTreeSet::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
165 let roots: HashSet<Revision> = roots.into_iter().collect(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
166 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
|
167 None => { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
168 return Ok(range); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
169 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
170 Some(r) => r, |
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 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
173 // Internally, AncestorsIterator currently maintains a `HashSet` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
174 // 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
|
175 // 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
|
176 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
|
177 let mut heads_ancestors: Vec<Revision> = Vec::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
178 for revres in ait { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
179 let rev = revres?; |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
180 if roots.contains(&rev) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
181 range.insert(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
182 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
183 heads_ancestors.push(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 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
186 for rev in heads_ancestors.into_iter().rev() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
187 for parent in graph.parents(rev)?.iter() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
188 if *parent != NULL_REVISION && range.contains(parent) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
189 range.insert(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
190 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
191 } |
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 Ok(range) |
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 |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
196 #[cfg(test)] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
197 mod tests { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
198 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
199 use super::*; |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
200 use crate::{testing::SampleGraph, BaseRevision}; |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
201 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
202 /// 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
|
203 fn retain_heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
204 graph: &impl Graph, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
205 revs: &[BaseRevision], |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
206 ) -> Result<Vec<Revision>, GraphError> { |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
207 let mut revs: HashSet<Revision> = |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
208 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
|
209 retain_heads(graph, &mut revs)?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
210 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
|
211 as_vec.sort_unstable(); |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
212 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
213 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
214 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
215 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
216 fn test_retain_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
217 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
|
218 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
219 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
|
220 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
221 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
222 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
223 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
|
224 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
225 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
226 Ok(()) |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
229 /// 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
|
230 fn heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
231 graph: &impl Graph, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
232 revs: &[BaseRevision], |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
233 ) -> Result<Vec<Revision>, GraphError> { |
51120
532e74ad3ff6
rust: run a clippy pass with the latest stable version
Raphaël Gomès <rgomes@octobus.net>
parents:
50979
diff
changeset
|
234 let iter_revs: Vec<_> = revs.iter().cloned().map(Revision).collect(); |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
235 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
|
236 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
|
237 as_vec.sort_unstable(); |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
238 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
239 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
240 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
241 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
242 fn test_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
243 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
|
244 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
245 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
|
246 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
247 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
248 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
249 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
|
250 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
251 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
252 Ok(()) |
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 |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
255 /// Apply `roots()` and sort the result for easier comparison |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
256 fn roots_sorted( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
257 graph: &impl Graph, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
258 revs: &[BaseRevision], |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
259 ) -> Result<Vec<Revision>, GraphError> { |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
260 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
|
261 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
|
262 as_vec.sort_unstable(); |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
263 Ok(as_vec) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
264 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
265 |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
266 #[test] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
267 fn test_roots() -> Result<(), GraphError> { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
268 assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
269 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
270 roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
271 vec![0, 4, 12] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
272 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
273 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
274 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
|
275 vec![1, 8] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
276 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
277 Ok(()) |
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 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
280 /// 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
|
281 fn range_vec( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
282 graph: impl Graph + Clone, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
283 roots: &[BaseRevision], |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
284 heads: &[BaseRevision], |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
285 ) -> Result<Vec<Revision>, GraphError> { |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
286 range( |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
287 &graph, |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
288 roots.iter().cloned().map(Revision), |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
289 heads.iter().cloned().map(Revision), |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
290 ) |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
291 .map(|bs| bs.into_iter().collect()) |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
292 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
293 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
294 #[test] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
295 fn test_range() -> Result<(), GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
296 assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]); |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
297 assert_eq!( |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
298 range_vec(SampleGraph, &[0], &[8])?, |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
299 Vec::<Revision>::new() |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
300 ); |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
301 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
302 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
303 vec![5, 10] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
304 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
305 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
306 range_vec(SampleGraph, &[5, 6], &[10, 12])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
307 vec![5, 6, 9, 10, 12] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
308 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
309 Ok(()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
310 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
311 } |