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