11 //! - By *relative heads* of a collection of revision numbers (`Revision`), |
11 //! - By *relative heads* of a collection of revision numbers (`Revision`), |
12 //! we mean those revisions that have no children among the collection. |
12 //! we mean those revisions that have no children among the collection. |
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean |
13 //! - Similarly *relative roots* of a collection of `Revision`, we mean |
14 //! those whose parents, if any, don't belong to the collection. |
14 //! those whose parents, if any, don't belong to the collection. |
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
15 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
16 use std::collections::HashSet; |
16 use crate::ancestors::AncestorsIterator; |
|
17 use std::collections::{BTreeSet, HashSet}; |
17 |
18 |
18 fn remove_parents( |
19 fn remove_parents( |
19 graph: &impl Graph, |
20 graph: &impl Graph, |
20 rev: Revision, |
21 rev: Revision, |
21 set: &mut HashSet<Revision>, |
22 set: &mut HashSet<Revision>, |
78 } |
79 } |
79 } |
80 } |
80 Ok(()) |
81 Ok(()) |
81 } |
82 } |
82 |
83 |
|
84 /// Compute the topological range between two collections of revisions |
|
85 /// |
|
86 /// This is equivalent to the revset `<roots>::<heads>`. |
|
87 /// |
|
88 /// Currently, the given `Graph` has to implement `Clone`, which means |
|
89 /// actually cloning just a reference-counted Python pointer if |
|
90 /// it's passed over through `rust-cpython`. This is due to the internal |
|
91 /// use of `AncestorsIterator` |
|
92 /// |
|
93 /// # Algorithmic details |
|
94 /// |
|
95 /// This is a two-pass swipe inspired from what `reachableroots2` from |
|
96 /// `mercurial.cext.parsers` does to obtain the same results. |
|
97 /// |
|
98 /// - first, we climb up the DAG from `heads` in topological order, keeping |
|
99 /// them in the vector `heads_ancestors` vector, and adding any element of |
|
100 /// `roots` we find among them to the resulting range. |
|
101 /// - Then, we iterate on that recorded vector so that a revision is always |
|
102 /// emitted after its parents and add all revisions whose parents are already |
|
103 /// in the range to the results. |
|
104 /// |
|
105 /// # Performance notes |
|
106 /// |
|
107 /// The main difference with the C implementation is that |
|
108 /// the latter uses a flat array with bit flags, instead of complex structures |
|
109 /// like `HashSet`, making it faster in most scenarios. In theory, it's |
|
110 /// possible that the present implementation could be more memory efficient |
|
111 /// for very large repositories with many branches. |
|
112 pub fn range( |
|
113 graph: &(impl Graph + Clone), |
|
114 roots: impl IntoIterator<Item = Revision>, |
|
115 heads: impl IntoIterator<Item = Revision>, |
|
116 ) -> Result<BTreeSet<Revision>, GraphError> { |
|
117 let mut range = BTreeSet::new(); |
|
118 let roots: HashSet<Revision> = roots.into_iter().collect(); |
|
119 let min_root: Revision = match roots.iter().cloned().min() { |
|
120 None => { |
|
121 return Ok(range); |
|
122 } |
|
123 Some(r) => r, |
|
124 }; |
|
125 |
|
126 // Internally, AncestorsIterator currently maintains a `HashSet` |
|
127 // of all seen revision, which is also what we record, albeit in an ordered |
|
128 // way. There's room for improvement on this duplication. |
|
129 let ait = AncestorsIterator::new(graph.clone(), heads, min_root, true)?; |
|
130 let mut heads_ancestors: Vec<Revision> = Vec::new(); |
|
131 for revres in ait { |
|
132 let rev = revres?; |
|
133 if roots.contains(&rev) { |
|
134 range.insert(rev); |
|
135 } |
|
136 heads_ancestors.push(rev); |
|
137 } |
|
138 |
|
139 for rev in heads_ancestors.into_iter().rev() { |
|
140 for parent in graph.parents(rev)?.iter() { |
|
141 if *parent != NULL_REVISION && range.contains(parent) { |
|
142 range.insert(rev); |
|
143 } |
|
144 } |
|
145 } |
|
146 Ok(range) |
|
147 } |
|
148 |
83 #[cfg(test)] |
149 #[cfg(test)] |
84 mod tests { |
150 mod tests { |
85 |
151 |
86 use super::*; |
152 use super::*; |
87 use crate::testing::SampleGraph; |
153 use crate::testing::SampleGraph; |
135 vec![3, 5, 8, 9] |
201 vec![3, 5, 8, 9] |
136 ); |
202 ); |
137 Ok(()) |
203 Ok(()) |
138 } |
204 } |
139 |
205 |
140 } |
206 /// Apply `range()` and convert the result into a Vec for easier comparison |
|
207 fn range_vec( |
|
208 graph: impl Graph + Clone, |
|
209 roots: &[Revision], |
|
210 heads: &[Revision], |
|
211 ) -> Result<Vec<Revision>, GraphError> { |
|
212 range(&graph, roots.iter().cloned(), heads.iter().cloned()) |
|
213 .map(|bs| bs.into_iter().collect()) |
|
214 } |
|
215 |
|
216 #[test] |
|
217 fn test_range() -> Result<(), GraphError> { |
|
218 assert_eq!(range_vec(SampleGraph, &[0], &[4])?, vec![0, 1, 2, 4]); |
|
219 assert_eq!(range_vec(SampleGraph, &[0], &[8])?, vec![]); |
|
220 assert_eq!( |
|
221 range_vec(SampleGraph, &[5, 6], &[10, 11, 13])?, |
|
222 vec![5, 10] |
|
223 ); |
|
224 assert_eq!( |
|
225 range_vec(SampleGraph, &[5, 6], &[10, 12])?, |
|
226 vec![5, 6, 9, 10, 12] |
|
227 ); |
|
228 Ok(()) |
|
229 } |
|
230 |
|
231 } |