Mercurial > hg
annotate rust/hg-core/src/dagops.rs @ 51120:532e74ad3ff6
rust: run a clippy pass with the latest stable version
Our current version of clippy is older than the latest stable.
The newest version has new lints that are moslty good advice, so let's apply
them ahead of time. This has the added benefit of reducing the noise for
developpers like myself that use clippy as an IDE helper, as well as being
more prepared for a future clippy upgrade.
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Mon, 06 Nov 2023 11:06:08 +0100 |
parents | 4c5f6e95df84 |
children | ed6683d4cb29 |
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}; |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
16 use crate::ancestors::AncestorsIterator; |
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 |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
84 /// Roots of `revs`, passed as a `HashSet` |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
85 /// |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
86 /// They are returned in arbitrary order |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
87 pub fn roots<G: Graph, S: std::hash::BuildHasher>( |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
88 graph: &G, |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
89 revs: &HashSet<Revision, S>, |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
90 ) -> Result<Vec<Revision>, GraphError> { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
91 let mut roots: Vec<Revision> = Vec::new(); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
92 for rev in revs { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
93 if graph |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
94 .parents(*rev)? |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
95 .iter() |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
96 .filter(|p| **p != NULL_REVISION) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
97 .all(|p| !revs.contains(p)) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
98 { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
99 roots.push(*rev); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
100 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
101 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
102 Ok(roots) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
103 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
104 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
105 /// 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
|
106 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
107 /// This is equivalent to the revset `<roots>::<heads>`. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
108 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
109 /// 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
|
110 /// 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
|
111 /// 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
|
112 /// use of `AncestorsIterator` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
113 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
114 /// # Algorithmic details |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
115 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
116 /// 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
|
117 /// `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
|
118 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
119 /// - 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
|
120 /// 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
|
121 /// `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
|
122 /// - 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
|
123 /// 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
|
124 /// in the range to the results. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
125 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
126 /// # Performance notes |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
127 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
128 /// 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
|
129 /// 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
|
130 /// 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
|
131 /// 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
|
132 /// for very large repositories with many branches. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
133 pub fn range( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
134 graph: &(impl Graph + Clone), |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
135 roots: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
136 heads: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
137 ) -> Result<BTreeSet<Revision>, GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
138 let mut range = BTreeSet::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
139 let roots: HashSet<Revision> = roots.into_iter().collect(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
140 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
|
141 None => { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
142 return Ok(range); |
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 Some(r) => r, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
145 }; |
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 // Internally, AncestorsIterator currently maintains a `HashSet` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
148 // 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
|
149 // 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
|
150 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
|
151 let mut heads_ancestors: Vec<Revision> = Vec::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
152 for revres in ait { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
153 let rev = revres?; |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
154 if roots.contains(&rev) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
155 range.insert(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
156 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
157 heads_ancestors.push(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
158 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
159 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
160 for rev in heads_ancestors.into_iter().rev() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
161 for parent in graph.parents(rev)?.iter() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
162 if *parent != NULL_REVISION && range.contains(parent) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
163 range.insert(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
164 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
165 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
166 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
167 Ok(range) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
168 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
169 |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
170 #[cfg(test)] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
171 mod tests { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
172 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
173 use super::*; |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
174 use crate::{testing::SampleGraph, BaseRevision}; |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
175 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
176 /// 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
|
177 fn retain_heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
178 graph: &impl Graph, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
179 revs: &[BaseRevision], |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
180 ) -> Result<Vec<Revision>, GraphError> { |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
181 let mut revs: HashSet<Revision> = |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
182 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
|
183 retain_heads(graph, &mut revs)?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
184 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
|
185 as_vec.sort_unstable(); |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
186 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
187 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
188 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
189 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
190 fn test_retain_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
191 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
|
192 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
193 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
|
194 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
195 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
196 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
197 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
|
198 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
199 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
200 Ok(()) |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
203 /// 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
|
204 fn heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
205 graph: &impl Graph, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
206 revs: &[BaseRevision], |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
207 ) -> 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
|
208 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
|
209 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
|
210 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
|
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_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
217 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
|
218 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
219 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 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 |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
229 /// Apply `roots()` and sort the result for easier comparison |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
230 fn roots_sorted( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
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], |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
233 ) -> Result<Vec<Revision>, GraphError> { |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
234 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
|
235 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
|
236 as_vec.sort_unstable(); |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
237 Ok(as_vec) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
238 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
239 |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
240 #[test] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
241 fn test_roots() -> Result<(), GraphError> { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
242 assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
243 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
244 roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
245 vec![0, 4, 12] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
246 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
247 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
248 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
|
249 vec![1, 8] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
250 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
251 Ok(()) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
252 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
253 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
254 /// 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
|
255 fn range_vec( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
256 graph: impl Graph + Clone, |
50979
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
257 roots: &[BaseRevision], |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
258 heads: &[BaseRevision], |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
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 range( |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
261 &graph, |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
262 roots.iter().cloned().map(Revision), |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
263 heads.iter().cloned().map(Revision), |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
264 ) |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
265 .map(|bs| bs.into_iter().collect()) |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
266 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
267 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
268 #[test] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
269 fn test_range() -> Result<(), GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
270 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
|
271 assert_eq!( |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
272 range_vec(SampleGraph, &[0], &[8])?, |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
273 Vec::<Revision>::new() |
4c5f6e95df84
rust: make `Revision` a newtype
Raphaël Gomès <rgomes@octobus.net>
parents:
49930
diff
changeset
|
274 ); |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
275 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
276 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
277 vec![5, 10] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
278 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
279 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
280 range_vec(SampleGraph, &[5, 6], &[10, 12])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
281 vec![5, 6, 9, 10, 12] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
282 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
283 Ok(()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
284 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
285 } |