Mercurial > hg
annotate rust/hg-core/src/dagops.rs @ 49930:e98fd81bb151
rust-clippy: fix most warnings in `hg-core`
All of these are simple changes that for the most part are clear improvements
and the rest are at most equivalent.
The remaining warnings have to be fixed either with a bigger refactor like for
the nested "revlog" module, or in the dependency `bytes-cast`, which we own.
This will be done sometime in the future.
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Mon, 09 Jan 2023 19:18:43 +0100 |
parents | 26114bd6ec60 |
children | 4c5f6e95df84 |
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::*; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
174 use crate::testing::SampleGraph; |
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, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
179 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
180 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
181 let mut revs: HashSet<Revision> = revs.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
182 retain_heads(graph, &mut revs)?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
183 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
|
184 as_vec.sort_unstable(); |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
185 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
186 } |
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 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
189 fn test_retain_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
190 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
|
191 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
192 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
|
193 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
194 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
195 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
196 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
|
197 vec![3, 5, 8, 9] |
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 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
200 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
201 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
202 /// 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
|
203 fn heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
204 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
205 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
206 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
207 let heads = heads(graph, revs.iter())?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
208 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
|
209 as_vec.sort_unstable(); |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
210 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
211 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
212 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
213 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
214 fn test_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
215 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
|
216 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
217 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
|
218 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
219 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
220 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
221 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
|
222 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
223 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
224 Ok(()) |
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 |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
227 /// Apply `roots()` and sort the result for easier comparison |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
228 fn roots_sorted( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
229 graph: &impl Graph, |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
230 revs: &[Revision], |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
231 ) -> Result<Vec<Revision>, GraphError> { |
44973
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
232 let set: HashSet<_> = revs.iter().cloned().collect(); |
26114bd6ec60
rust: do a clippy pass
Raphaël Gomès <rgomes@octobus.net>
parents:
42841
diff
changeset
|
233 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
|
234 as_vec.sort_unstable(); |
42177
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
235 Ok(as_vec) |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
236 } |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
237 |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
238 #[test] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
239 fn test_roots() -> Result<(), GraphError> { |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
240 assert_eq!(roots_sorted(&SampleGraph, &[4, 5, 6])?, vec![4]); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
241 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
242 roots_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?, |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
243 vec![0, 4, 12] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
244 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
245 assert_eq!( |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
246 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
|
247 vec![1, 8] |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
248 ); |
be0733552984
rust-dagops: roots
Georges Racinet <georges.racinet@octobus.net>
parents:
42176
diff
changeset
|
249 Ok(()) |
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 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
252 /// 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
|
253 fn range_vec( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
254 graph: impl Graph + Clone, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
255 roots: &[Revision], |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
256 heads: &[Revision], |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
257 ) -> Result<Vec<Revision>, GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
258 range(&graph, roots.iter().cloned(), heads.iter().cloned()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
259 .map(|bs| bs.into_iter().collect()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
260 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
261 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
262 #[test] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
263 fn test_range() -> Result<(), GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
264 assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
265 assert_eq!(range_vec(SampleGraph, &[0], &[8])?, vec![]); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
266 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
267 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
268 vec![5, 10] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
269 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
270 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
271 range_vec(SampleGraph, &[5, 6], &[10, 12])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
272 vec![5, 6, 9, 10, 12] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
273 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
274 Ok(()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
275 } |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
276 } |