Mercurial > hg
annotate rust/hg-core/src/dagops.rs @ 42176:3bdb21bbf791
rust-dagops: range of revisions
This is a Rust implementation for what reachableroots2() does if
includepath is True.
The algorithmic details and performance notes are included in the
documentation comment.
Our main use case for now is a Rust counterpart of the partialdiscovery
object, so we don't really need bindings yet.
Differential Revision: https://phab.mercurial-scm.org/D6229
author | Georges Racinet <georges.racinet@octobus.net> |
---|---|
date | Tue, 19 Feb 2019 23:41:57 +0100 |
parents | 9060af281be7 |
children | be0733552984 |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
11 //! - By *relative heads* of a collection of revision numbers (`Revision`), |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
12 //! we mean those revisions that have no children among the collection. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
14 //! those whose parents, if any, don't belong to the collection. |
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 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
19 fn remove_parents( |
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, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
22 set: &mut HashSet<Revision>, |
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`. |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
68 pub fn retain_heads( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
69 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
70 revs: &mut HashSet<Revision>, |
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 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
84 /// 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
|
85 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
86 /// This is equivalent to the revset `<roots>::<heads>`. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
87 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
88 /// 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
|
89 /// 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
|
90 /// 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
|
91 /// use of `AncestorsIterator` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
92 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
93 /// # Algorithmic details |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
94 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
95 /// 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
|
96 /// `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
|
97 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
98 /// - 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
|
99 /// 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
|
100 /// `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
|
101 /// - 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
|
102 /// 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
|
103 /// in the range to the results. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
104 /// |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
105 /// # Performance notes |
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 /// 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
|
108 /// 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
|
109 /// 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
|
110 /// 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
|
111 /// for very large repositories with many branches. |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
112 pub fn range( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
113 graph: &(impl Graph + Clone), |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
114 roots: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
115 heads: impl IntoIterator<Item = Revision>, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
116 ) -> Result<BTreeSet<Revision>, GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
117 let mut range = BTreeSet::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
118 let roots: HashSet<Revision> = roots.into_iter().collect(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
119 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
|
120 None => { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
121 return Ok(range); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
122 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
123 Some(r) => r, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
124 }; |
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 // Internally, AncestorsIterator currently maintains a `HashSet` |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
127 // 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
|
128 // 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
|
129 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
|
130 let mut heads_ancestors: Vec<Revision> = Vec::new(); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
131 for revres in ait { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
132 let rev = revres?; |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
133 if roots.contains(&rev) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
134 range.insert(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
135 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
136 heads_ancestors.push(rev); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
137 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
138 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
139 for rev in heads_ancestors.into_iter().rev() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
140 for parent in graph.parents(rev)?.iter() { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
141 if *parent != NULL_REVISION && range.contains(parent) { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
142 range.insert(rev); |
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 } |
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 Ok(range) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
147 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
148 |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
149 #[cfg(test)] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
150 mod tests { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
151 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
152 use super::*; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
153 use crate::testing::SampleGraph; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
154 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
155 /// 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
|
156 fn retain_heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
157 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
158 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
159 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
160 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
|
161 retain_heads(graph, &mut revs)?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
162 let mut 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
|
163 as_vec.sort(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
164 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
165 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
166 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
167 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
168 fn test_retain_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
169 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
|
170 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
171 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
|
172 vec![1, 6, 12] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
173 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
174 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
175 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
|
176 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
177 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
178 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
179 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
180 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
181 /// 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
|
182 fn heads_sorted( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
183 graph: &impl Graph, |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
184 revs: &[Revision], |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
185 ) -> Result<Vec<Revision>, GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
186 let heads = heads(graph, revs.iter())?; |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
187 let mut as_vec: Vec<Revision> = heads.iter().cloned().collect(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
188 as_vec.sort(); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
189 Ok(as_vec) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
190 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
191 |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
192 #[test] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
193 fn test_heads() -> Result<(), GraphError> { |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
194 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
|
195 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
196 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
|
197 vec![1, 6, 12] |
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 assert_eq!( |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
200 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
|
201 vec![3, 5, 8, 9] |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
202 ); |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
203 Ok(()) |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
204 } |
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
205 |
42176
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
206 /// 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
|
207 fn range_vec( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
208 graph: impl Graph + Clone, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
209 roots: &[Revision], |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
210 heads: &[Revision], |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
211 ) -> Result<Vec<Revision>, GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
212 range(&graph, roots.iter().cloned(), heads.iter().cloned()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
213 .map(|bs| bs.into_iter().collect()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
214 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
215 |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
216 #[test] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
217 fn test_range() -> Result<(), GraphError> { |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
218 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
|
219 assert_eq!(range_vec(SampleGraph, &[0], &[8])?, vec![]); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
220 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
221 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
222 vec![5, 10] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
223 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
224 assert_eq!( |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
225 range_vec(SampleGraph, &[5, 6], &[10, 12])?, |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
226 vec![5, 6, 9, 10, 12] |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
227 ); |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
228 Ok(()) |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
229 } |
3bdb21bbf791
rust-dagops: range of revisions
Georges Racinet <georges.racinet@octobus.net>
parents:
41717
diff
changeset
|
230 |
41242
47881d2a9d99
rust: dagop.headrevs() Rust counterparts
Georges Racinet on ishtar.racinet.fr <georges@racinet.fr>
parents:
diff
changeset
|
231 } |