Show More
@@ -1,835 +1,847 b'' | |||||
1 | // ancestors.rs |
|
1 | // ancestors.rs | |
2 | // |
|
2 | // | |
3 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> |
|
3 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> | |
4 | // |
|
4 | // | |
5 | // This software may be used and distributed according to the terms of the |
|
5 | // This software may be used and distributed according to the terms of the | |
6 | // GNU General Public License version 2 or any later version. |
|
6 | // GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | //! Rust versions of generic DAG ancestors algorithms for Mercurial |
|
8 | //! Rust versions of generic DAG ancestors algorithms for Mercurial | |
9 |
|
9 | |||
10 | use super::{Graph, GraphError, Revision, NULL_REVISION}; |
|
10 | use super::{Graph, GraphError, Revision, NULL_REVISION}; | |
11 | use crate::dagops; |
|
11 | use crate::dagops; | |
12 | use std::cmp::max; |
|
12 | use std::cmp::max; | |
13 | use std::collections::{BinaryHeap, HashSet}; |
|
13 | use std::collections::{BinaryHeap, HashSet}; | |
14 |
|
14 | |||
15 | /// Iterator over the ancestors of a given list of revisions |
|
15 | /// Iterator over the ancestors of a given list of revisions | |
16 | /// This is a generic type, defined and implemented for any Graph, so that |
|
16 | /// This is a generic type, defined and implemented for any Graph, so that | |
17 | /// it's easy to |
|
17 | /// it's easy to | |
18 | /// |
|
18 | /// | |
19 | /// - unit test in pure Rust |
|
19 | /// - unit test in pure Rust | |
20 | /// - bind to main Mercurial code, potentially in several ways and have these |
|
20 | /// - bind to main Mercurial code, potentially in several ways and have these | |
21 | /// bindings evolve over time |
|
21 | /// bindings evolve over time | |
22 | pub struct AncestorsIterator<G: Graph> { |
|
22 | pub struct AncestorsIterator<G: Graph> { | |
23 | graph: G, |
|
23 | graph: G, | |
24 | visit: BinaryHeap<Revision>, |
|
24 | visit: BinaryHeap<Revision>, | |
25 | seen: HashSet<Revision>, |
|
25 | seen: HashSet<Revision>, | |
26 | stoprev: Revision, |
|
26 | stoprev: Revision, | |
27 | } |
|
27 | } | |
28 |
|
28 | |||
29 | pub struct MissingAncestors<G: Graph> { |
|
29 | pub struct MissingAncestors<G: Graph> { | |
30 | graph: G, |
|
30 | graph: G, | |
31 | bases: HashSet<Revision>, |
|
31 | bases: HashSet<Revision>, | |
32 | max_base: Revision, |
|
32 | max_base: Revision, | |
33 | } |
|
33 | } | |
34 |
|
34 | |||
35 | impl<G: Graph> AncestorsIterator<G> { |
|
35 | impl<G: Graph> AncestorsIterator<G> { | |
36 | /// Constructor. |
|
36 | /// Constructor. | |
37 | /// |
|
37 | /// | |
38 | /// if `inclusive` is true, then the init revisions are emitted in |
|
38 | /// if `inclusive` is true, then the init revisions are emitted in | |
39 | /// particular, otherwise iteration starts from their parents. |
|
39 | /// particular, otherwise iteration starts from their parents. | |
40 | pub fn new( |
|
40 | pub fn new( | |
41 | graph: G, |
|
41 | graph: G, | |
42 | initrevs: impl IntoIterator<Item = Revision>, |
|
42 | initrevs: impl IntoIterator<Item = Revision>, | |
43 | stoprev: Revision, |
|
43 | stoprev: Revision, | |
44 | inclusive: bool, |
|
44 | inclusive: bool, | |
45 | ) -> Result<Self, GraphError> { |
|
45 | ) -> Result<Self, GraphError> { | |
46 | let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); |
|
46 | let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); | |
47 | if inclusive { |
|
47 | if inclusive { | |
48 | let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); |
|
48 | let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); | |
49 | let seen = visit.iter().cloned().collect(); |
|
49 | let seen = visit.iter().cloned().collect(); | |
50 | return Ok(AncestorsIterator { |
|
50 | return Ok(AncestorsIterator { | |
51 | visit, |
|
51 | visit, | |
52 | seen, |
|
52 | seen, | |
53 | stoprev, |
|
53 | stoprev, | |
54 | graph, |
|
54 | graph, | |
55 | }); |
|
55 | }); | |
56 | } |
|
56 | } | |
57 | let mut this = AncestorsIterator { |
|
57 | let mut this = AncestorsIterator { | |
58 | visit: BinaryHeap::new(), |
|
58 | visit: BinaryHeap::new(), | |
59 | seen: HashSet::new(), |
|
59 | seen: HashSet::new(), | |
60 | stoprev, |
|
60 | stoprev, | |
61 | graph, |
|
61 | graph, | |
62 | }; |
|
62 | }; | |
63 | this.seen.insert(NULL_REVISION); |
|
63 | this.seen.insert(NULL_REVISION); | |
64 | for rev in filtered_initrevs { |
|
64 | for rev in filtered_initrevs { | |
65 | for parent in this.graph.parents(rev)?.iter().cloned() { |
|
65 | for parent in this.graph.parents(rev)?.iter().cloned() { | |
66 | this.conditionally_push_rev(parent); |
|
66 | this.conditionally_push_rev(parent); | |
67 | } |
|
67 | } | |
68 | } |
|
68 | } | |
69 | Ok(this) |
|
69 | Ok(this) | |
70 | } |
|
70 | } | |
71 |
|
71 | |||
72 | #[inline] |
|
72 | #[inline] | |
73 | fn conditionally_push_rev(&mut self, rev: Revision) { |
|
73 | fn conditionally_push_rev(&mut self, rev: Revision) { | |
74 | if self.stoprev <= rev && self.seen.insert(rev) { |
|
74 | if self.stoprev <= rev && self.seen.insert(rev) { | |
75 | self.visit.push(rev); |
|
75 | self.visit.push(rev); | |
76 | } |
|
76 | } | |
77 | } |
|
77 | } | |
78 |
|
78 | |||
79 | /// Consumes partially the iterator to tell if the given target |
|
79 | /// Consumes partially the iterator to tell if the given target | |
80 | /// revision |
|
80 | /// revision | |
81 | /// is in the ancestors it emits. |
|
81 | /// is in the ancestors it emits. | |
82 | /// This is meant for iterators actually dedicated to that kind of |
|
82 | /// This is meant for iterators actually dedicated to that kind of | |
83 | /// purpose |
|
83 | /// purpose | |
84 | pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { |
|
84 | pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { | |
85 | if self.seen.contains(&target) && target != NULL_REVISION { |
|
85 | if self.seen.contains(&target) && target != NULL_REVISION { | |
86 | return Ok(true); |
|
86 | return Ok(true); | |
87 | } |
|
87 | } | |
88 | for item in self { |
|
88 | for item in self { | |
89 | let rev = item?; |
|
89 | let rev = item?; | |
90 | if rev == target { |
|
90 | if rev == target { | |
91 | return Ok(true); |
|
91 | return Ok(true); | |
92 | } |
|
92 | } | |
93 | if rev < target { |
|
93 | if rev < target { | |
94 | return Ok(false); |
|
94 | return Ok(false); | |
95 | } |
|
95 | } | |
96 | } |
|
96 | } | |
97 | Ok(false) |
|
97 | Ok(false) | |
98 | } |
|
98 | } | |
99 |
|
99 | |||
100 | pub fn peek(&self) -> Option<Revision> { |
|
100 | pub fn peek(&self) -> Option<Revision> { | |
101 | self.visit.peek().cloned() |
|
101 | self.visit.peek().cloned() | |
102 | } |
|
102 | } | |
103 |
|
103 | |||
104 | /// Tell if the iterator is about an empty set |
|
104 | /// Tell if the iterator is about an empty set | |
105 | /// |
|
105 | /// | |
106 | /// The result does not depend whether the iterator has been consumed |
|
106 | /// The result does not depend whether the iterator has been consumed | |
107 | /// or not. |
|
107 | /// or not. | |
108 | /// This is mostly meant for iterators backing a lazy ancestors set |
|
108 | /// This is mostly meant for iterators backing a lazy ancestors set | |
109 | pub fn is_empty(&self) -> bool { |
|
109 | pub fn is_empty(&self) -> bool { | |
110 | if self.visit.len() > 0 { |
|
110 | if self.visit.len() > 0 { | |
111 | return false; |
|
111 | return false; | |
112 | } |
|
112 | } | |
113 | if self.seen.len() > 1 { |
|
113 | if self.seen.len() > 1 { | |
114 | return false; |
|
114 | return false; | |
115 | } |
|
115 | } | |
116 | // at this point, the seen set is at most a singleton. |
|
116 | // at this point, the seen set is at most a singleton. | |
117 | // If not `self.inclusive`, it's still possible that it has only |
|
117 | // If not `self.inclusive`, it's still possible that it has only | |
118 | // the null revision |
|
118 | // the null revision | |
119 | self.seen.is_empty() || self.seen.contains(&NULL_REVISION) |
|
119 | self.seen.is_empty() || self.seen.contains(&NULL_REVISION) | |
120 | } |
|
120 | } | |
121 | } |
|
121 | } | |
122 |
|
122 | |||
123 | /// Main implementation for the iterator |
|
123 | /// Main implementation for the iterator | |
124 | /// |
|
124 | /// | |
125 | /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` |
|
125 | /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` | |
126 | /// with a few non crucial differences: |
|
126 | /// with a few non crucial differences: | |
127 | /// |
|
127 | /// | |
128 | /// - there's no filtering of invalid parent revisions. Actually, it should be |
|
128 | /// - there's no filtering of invalid parent revisions. Actually, it should be | |
129 | /// consistent and more efficient to filter them from the end caller. |
|
129 | /// consistent and more efficient to filter them from the end caller. | |
130 | /// - we don't have the optimization for adjacent revisions (i.e., the case |
|
130 | /// - we don't have the optimization for adjacent revisions (i.e., the case | |
131 | /// where `p1 == rev - 1`), because it amounts to update the first element of |
|
131 | /// where `p1 == rev - 1`), because it amounts to update the first element of | |
132 | /// the heap without sifting, which Rust's BinaryHeap doesn't let us do. |
|
132 | /// the heap without sifting, which Rust's BinaryHeap doesn't let us do. | |
133 | /// - we save a few pushes by comparing with `stoprev` before pushing |
|
133 | /// - we save a few pushes by comparing with `stoprev` before pushing | |
134 | impl<G: Graph> Iterator for AncestorsIterator<G> { |
|
134 | impl<G: Graph> Iterator for AncestorsIterator<G> { | |
135 | type Item = Result<Revision, GraphError>; |
|
135 | type Item = Result<Revision, GraphError>; | |
136 |
|
136 | |||
137 | fn next(&mut self) -> Option<Self::Item> { |
|
137 | fn next(&mut self) -> Option<Self::Item> { | |
138 | let current = match self.visit.peek() { |
|
138 | let current = match self.visit.peek() { | |
139 | None => { |
|
139 | None => { | |
140 | return None; |
|
140 | return None; | |
141 | } |
|
141 | } | |
142 | Some(c) => *c, |
|
142 | Some(c) => *c, | |
143 | }; |
|
143 | }; | |
144 | let [p1, p2] = match self.graph.parents(current) { |
|
144 | let [p1, p2] = match self.graph.parents(current) { | |
145 | Ok(ps) => ps, |
|
145 | Ok(ps) => ps, | |
146 | Err(e) => return Some(Err(e)), |
|
146 | Err(e) => return Some(Err(e)), | |
147 | }; |
|
147 | }; | |
148 | if p1 < self.stoprev || !self.seen.insert(p1) { |
|
148 | if p1 < self.stoprev || !self.seen.insert(p1) { | |
149 | self.visit.pop(); |
|
149 | self.visit.pop(); | |
150 | } else { |
|
150 | } else { | |
151 | *(self.visit.peek_mut().unwrap()) = p1; |
|
151 | *(self.visit.peek_mut().unwrap()) = p1; | |
152 | }; |
|
152 | }; | |
153 |
|
153 | |||
154 | self.conditionally_push_rev(p2); |
|
154 | self.conditionally_push_rev(p2); | |
155 | Some(Ok(current)) |
|
155 | Some(Ok(current)) | |
156 | } |
|
156 | } | |
157 | } |
|
157 | } | |
158 |
|
158 | |||
159 | impl<G: Graph> MissingAncestors<G> { |
|
159 | impl<G: Graph> MissingAncestors<G> { | |
160 | pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { |
|
160 | pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { | |
161 | let mut created = MissingAncestors { |
|
161 | let mut created = MissingAncestors { | |
162 | graph, |
|
162 | graph, | |
163 | bases: HashSet::new(), |
|
163 | bases: HashSet::new(), | |
164 | max_base: NULL_REVISION, |
|
164 | max_base: NULL_REVISION, | |
165 | }; |
|
165 | }; | |
166 | created.add_bases(bases); |
|
166 | created.add_bases(bases); | |
167 | created |
|
167 | created | |
168 | } |
|
168 | } | |
169 |
|
169 | |||
170 | pub fn has_bases(&self) -> bool { |
|
170 | pub fn has_bases(&self) -> bool { | |
171 | !self.bases.is_empty() |
|
171 | !self.bases.is_empty() | |
172 | } |
|
172 | } | |
173 |
|
173 | |||
174 | /// Return a reference to current bases. |
|
174 | /// Return a reference to current bases. | |
175 | /// |
|
175 | /// | |
176 | /// This is useful in unit tests, but also setdiscovery.py does |
|
176 | /// This is useful in unit tests, but also setdiscovery.py does | |
177 | /// read the bases attribute of a ancestor.missingancestors instance. |
|
177 | /// read the bases attribute of a ancestor.missingancestors instance. | |
178 | pub fn get_bases(&self) -> &HashSet<Revision> { |
|
178 | pub fn get_bases(&self) -> &HashSet<Revision> { | |
179 | &self.bases |
|
179 | &self.bases | |
180 | } |
|
180 | } | |
181 |
|
181 | |||
182 | /// Computes the relative heads of current bases. |
|
182 | /// Computes the relative heads of current bases. | |
183 | /// |
|
183 | /// | |
184 | /// The object is still usable after this. |
|
184 | /// The object is still usable after this. | |
185 | pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> { |
|
185 | pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> { | |
186 | dagops::heads(&self.graph, self.bases.iter()) |
|
186 | dagops::heads(&self.graph, self.bases.iter()) | |
187 | } |
|
187 | } | |
188 |
|
188 | |||
189 | /// Consumes the object and returns the relative heads of its bases. |
|
189 | /// Consumes the object and returns the relative heads of its bases. | |
190 | pub fn into_bases_heads( |
|
190 | pub fn into_bases_heads( | |
191 | mut self, |
|
191 | mut self, | |
192 | ) -> Result<HashSet<Revision>, GraphError> { |
|
192 | ) -> Result<HashSet<Revision>, GraphError> { | |
193 | dagops::retain_heads(&self.graph, &mut self.bases)?; |
|
193 | dagops::retain_heads(&self.graph, &mut self.bases)?; | |
194 | Ok(self.bases) |
|
194 | Ok(self.bases) | |
195 | } |
|
195 | } | |
196 |
|
196 | |||
197 | /// Add some revisions to `self.bases` |
|
197 | /// Add some revisions to `self.bases` | |
198 | /// |
|
198 | /// | |
199 | /// Takes care of keeping `self.max_base` up to date. |
|
199 | /// Takes care of keeping `self.max_base` up to date. | |
200 | pub fn add_bases( |
|
200 | pub fn add_bases( | |
201 | &mut self, |
|
201 | &mut self, | |
202 | new_bases: impl IntoIterator<Item = Revision>, |
|
202 | new_bases: impl IntoIterator<Item = Revision>, | |
203 | ) { |
|
203 | ) { | |
204 | let mut max_base = self.max_base; |
|
204 | let mut max_base = self.max_base; | |
205 | self.bases.extend( |
|
205 | self.bases.extend( | |
206 | new_bases |
|
206 | new_bases | |
207 | .into_iter() |
|
207 | .into_iter() | |
208 | .filter(|&rev| rev != NULL_REVISION) |
|
208 | .filter(|&rev| rev != NULL_REVISION) | |
209 | .map(|r| { |
|
209 | .map(|r| { | |
210 | if r > max_base { |
|
210 | if r > max_base { | |
211 | max_base = r; |
|
211 | max_base = r; | |
212 | } |
|
212 | } | |
213 | r |
|
213 | r | |
214 | }), |
|
214 | }), | |
215 | ); |
|
215 | ); | |
216 | self.max_base = max_base; |
|
216 | self.max_base = max_base; | |
217 | } |
|
217 | } | |
218 |
|
218 | |||
219 | /// Remove all ancestors of self.bases from the revs set (in place) |
|
219 | /// Remove all ancestors of self.bases from the revs set (in place) | |
220 | pub fn remove_ancestors_from( |
|
220 | pub fn remove_ancestors_from( | |
221 | &mut self, |
|
221 | &mut self, | |
222 | revs: &mut HashSet<Revision>, |
|
222 | revs: &mut HashSet<Revision>, | |
223 | ) -> Result<(), GraphError> { |
|
223 | ) -> Result<(), GraphError> { | |
224 | revs.retain(|r| !self.bases.contains(r)); |
|
224 | revs.retain(|r| !self.bases.contains(r)); | |
225 | // the null revision is always an ancestor. Logically speaking |
|
225 | // the null revision is always an ancestor. Logically speaking | |
226 | // it's debatable in case bases is empty, but the Python |
|
226 | // it's debatable in case bases is empty, but the Python | |
227 | // implementation always adds NULL_REVISION to bases, making it |
|
227 | // implementation always adds NULL_REVISION to bases, making it | |
228 | // unconditionnally true. |
|
228 | // unconditionnally true. | |
229 | revs.remove(&NULL_REVISION); |
|
229 | revs.remove(&NULL_REVISION); | |
230 | if revs.is_empty() { |
|
230 | if revs.is_empty() { | |
231 | return Ok(()); |
|
231 | return Ok(()); | |
232 | } |
|
232 | } | |
233 | // anything in revs > start is definitely not an ancestor of bases |
|
233 | // anything in revs > start is definitely not an ancestor of bases | |
234 | // revs <= start need to be investigated |
|
234 | // revs <= start need to be investigated | |
235 | if self.max_base == NULL_REVISION { |
|
235 | if self.max_base == NULL_REVISION { | |
236 | return Ok(()); |
|
236 | return Ok(()); | |
237 | } |
|
237 | } | |
238 |
|
238 | |||
239 | // whatever happens, we'll keep at least keepcount of them |
|
239 | // whatever happens, we'll keep at least keepcount of them | |
240 | // knowing this gives us a earlier stop condition than |
|
240 | // knowing this gives us a earlier stop condition than | |
241 | // going all the way to the root |
|
241 | // going all the way to the root | |
242 | let keepcount = revs.iter().filter(|r| **r > self.max_base).count(); |
|
242 | let keepcount = revs.iter().filter(|r| **r > self.max_base).count(); | |
243 |
|
243 | |||
244 | let mut curr = self.max_base; |
|
244 | let mut curr = self.max_base; | |
245 | while curr != NULL_REVISION && revs.len() > keepcount { |
|
245 | while curr != NULL_REVISION && revs.len() > keepcount { | |
246 | if self.bases.contains(&curr) { |
|
246 | if self.bases.contains(&curr) { | |
247 | revs.remove(&curr); |
|
247 | revs.remove(&curr); | |
248 | self.add_parents(curr)?; |
|
248 | self.add_parents(curr)?; | |
249 | } |
|
249 | } | |
250 | // We know this revision is safe because we've checked the bounds |
|
250 | // We know this revision is safe because we've checked the bounds | |
251 | // before. |
|
251 | // before. | |
252 | curr = Revision(curr.0 - 1); |
|
252 | curr = Revision(curr.0 - 1); | |
253 | } |
|
253 | } | |
254 | Ok(()) |
|
254 | Ok(()) | |
255 | } |
|
255 | } | |
256 |
|
256 | |||
257 | /// Add the parents of `rev` to `self.bases` |
|
257 | /// Add the parents of `rev` to `self.bases` | |
258 | /// |
|
258 | /// | |
259 | /// This has no effect on `self.max_base` |
|
259 | /// This has no effect on `self.max_base` | |
260 | #[inline] |
|
260 | #[inline] | |
261 | fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> { |
|
261 | fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> { | |
262 | if rev == NULL_REVISION { |
|
262 | if rev == NULL_REVISION { | |
263 | return Ok(()); |
|
263 | return Ok(()); | |
264 | } |
|
264 | } | |
265 | for p in self.graph.parents(rev)?.iter().cloned() { |
|
265 | for p in self.graph.parents(rev)?.iter().cloned() { | |
266 | // No need to bother the set with inserting NULL_REVISION over and |
|
266 | // No need to bother the set with inserting NULL_REVISION over and | |
267 | // over |
|
267 | // over | |
268 | if p != NULL_REVISION { |
|
268 | if p != NULL_REVISION { | |
269 | self.bases.insert(p); |
|
269 | self.bases.insert(p); | |
270 | } |
|
270 | } | |
271 | } |
|
271 | } | |
272 | Ok(()) |
|
272 | Ok(()) | |
273 | } |
|
273 | } | |
274 |
|
274 | |||
275 | /// Return all the ancestors of revs that are not ancestors of self.bases |
|
275 | /// Return all the ancestors of revs that are not ancestors of self.bases | |
276 | /// |
|
276 | /// | |
277 | /// This may include elements from revs. |
|
277 | /// This may include elements from revs. | |
278 | /// |
|
278 | /// | |
279 | /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in |
|
279 | /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in | |
280 | /// revision number order, which is a topological order. |
|
280 | /// revision number order, which is a topological order. | |
281 | pub fn missing_ancestors( |
|
281 | pub fn missing_ancestors( | |
282 | &mut self, |
|
282 | &mut self, | |
283 | revs: impl IntoIterator<Item = Revision>, |
|
283 | revs: impl IntoIterator<Item = Revision>, | |
284 | ) -> Result<Vec<Revision>, GraphError> { |
|
284 | ) -> Result<Vec<Revision>, GraphError> { | |
285 | // just for convenience and comparison with Python version |
|
285 | // just for convenience and comparison with Python version | |
286 | let bases_visit = &mut self.bases; |
|
286 | let bases_visit = &mut self.bases; | |
287 | let mut revs: HashSet<Revision> = revs |
|
287 | let mut revs: HashSet<Revision> = revs | |
288 | .into_iter() |
|
288 | .into_iter() | |
289 | .filter(|r| !bases_visit.contains(r)) |
|
289 | .filter(|r| !bases_visit.contains(r)) | |
290 | .collect(); |
|
290 | .collect(); | |
291 | let revs_visit = &mut revs; |
|
291 | let revs_visit = &mut revs; | |
292 | let mut both_visit: HashSet<Revision> = |
|
292 | let mut both_visit: HashSet<Revision> = | |
293 | revs_visit.intersection(bases_visit).cloned().collect(); |
|
293 | revs_visit.intersection(bases_visit).cloned().collect(); | |
294 | if revs_visit.is_empty() { |
|
294 | if revs_visit.is_empty() { | |
295 | return Ok(Vec::new()); |
|
295 | return Ok(Vec::new()); | |
296 | } |
|
296 | } | |
297 | let max_revs = revs_visit.iter().cloned().max().unwrap(); |
|
297 | let max_revs = revs_visit.iter().cloned().max().unwrap(); | |
298 | let start = max(self.max_base, max_revs); |
|
298 | let start = max(self.max_base, max_revs); | |
299 |
|
299 | |||
300 | // TODO heuristics for with_capacity()? |
|
300 | // TODO heuristics for with_capacity()? | |
301 | let mut missing: Vec<Revision> = Vec::new(); |
|
301 | let mut missing: Vec<Revision> = Vec::new(); | |
302 | for curr in (0..=start.0).rev() { |
|
302 | for curr in (0..=start.0).rev() { | |
303 | if revs_visit.is_empty() { |
|
303 | if revs_visit.is_empty() { | |
304 | break; |
|
304 | break; | |
305 | } |
|
305 | } | |
306 | if both_visit.remove(&Revision(curr)) { |
|
306 | if both_visit.remove(&Revision(curr)) { | |
307 | // curr's parents might have made it into revs_visit through |
|
307 | // curr's parents might have made it into revs_visit through | |
308 | // another path |
|
308 | // another path | |
309 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { |
|
309 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { | |
310 | if p == NULL_REVISION { |
|
310 | if p == NULL_REVISION { | |
311 | continue; |
|
311 | continue; | |
312 | } |
|
312 | } | |
313 | revs_visit.remove(&p); |
|
313 | revs_visit.remove(&p); | |
314 | bases_visit.insert(p); |
|
314 | bases_visit.insert(p); | |
315 | both_visit.insert(p); |
|
315 | both_visit.insert(p); | |
316 | } |
|
316 | } | |
317 | } else if revs_visit.remove(&Revision(curr)) { |
|
317 | } else if revs_visit.remove(&Revision(curr)) { | |
318 | missing.push(Revision(curr)); |
|
318 | missing.push(Revision(curr)); | |
319 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { |
|
319 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { | |
320 | if p == NULL_REVISION { |
|
320 | if p == NULL_REVISION { | |
321 | continue; |
|
321 | continue; | |
322 | } |
|
322 | } | |
323 | if bases_visit.contains(&p) { |
|
323 | if bases_visit.contains(&p) { | |
324 | // p is already known to be an ancestor of revs_visit |
|
324 | // p is already known to be an ancestor of revs_visit | |
325 | revs_visit.remove(&p); |
|
325 | revs_visit.remove(&p); | |
326 | both_visit.insert(p); |
|
326 | both_visit.insert(p); | |
327 | } else if both_visit.contains(&p) { |
|
327 | } else if both_visit.contains(&p) { | |
328 | // p should have been in bases_visit |
|
328 | // p should have been in bases_visit | |
329 | revs_visit.remove(&p); |
|
329 | revs_visit.remove(&p); | |
330 | bases_visit.insert(p); |
|
330 | bases_visit.insert(p); | |
331 | } else { |
|
331 | } else { | |
332 | // visit later |
|
332 | // visit later | |
333 | revs_visit.insert(p); |
|
333 | revs_visit.insert(p); | |
334 | } |
|
334 | } | |
335 | } |
|
335 | } | |
336 | } else if bases_visit.contains(&Revision(curr)) { |
|
336 | } else if bases_visit.contains(&Revision(curr)) { | |
337 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { |
|
337 | for p in self.graph.parents(Revision(curr))?.iter().cloned() { | |
338 | if p == NULL_REVISION { |
|
338 | if p == NULL_REVISION { | |
339 | continue; |
|
339 | continue; | |
340 | } |
|
340 | } | |
341 | if revs_visit.remove(&p) || both_visit.contains(&p) { |
|
341 | if revs_visit.remove(&p) || both_visit.contains(&p) { | |
342 | // p is an ancestor of bases_visit, and is implicitly |
|
342 | // p is an ancestor of bases_visit, and is implicitly | |
343 | // in revs_visit, which means p is ::revs & ::bases. |
|
343 | // in revs_visit, which means p is ::revs & ::bases. | |
344 | bases_visit.insert(p); |
|
344 | bases_visit.insert(p); | |
345 | both_visit.insert(p); |
|
345 | both_visit.insert(p); | |
346 | } else { |
|
346 | } else { | |
347 | bases_visit.insert(p); |
|
347 | bases_visit.insert(p); | |
348 | } |
|
348 | } | |
349 | } |
|
349 | } | |
350 | } |
|
350 | } | |
351 | } |
|
351 | } | |
352 | missing.reverse(); |
|
352 | missing.reverse(); | |
353 | Ok(missing) |
|
353 | Ok(missing) | |
354 | } |
|
354 | } | |
355 | } |
|
355 | } | |
356 |
|
356 | |||
357 | #[cfg(test)] |
|
357 | #[cfg(test)] | |
358 | mod tests { |
|
358 | mod tests { | |
359 |
|
359 | |||
360 | use super::*; |
|
360 | use super::*; | |
361 | use crate::{ |
|
361 | use crate::{ | |
362 | testing::{SampleGraph, VecGraph}, |
|
362 | testing::{SampleGraph, VecGraph}, | |
363 | BaseRevision, |
|
363 | BaseRevision, | |
364 | }; |
|
364 | }; | |
365 |
|
365 | |||
366 | impl From<BaseRevision> for Revision { |
|
366 | impl From<BaseRevision> for Revision { | |
367 | fn from(value: BaseRevision) -> Self { |
|
367 | fn from(value: BaseRevision) -> Self { | |
368 | if !cfg!(test) { |
|
368 | if !cfg!(test) { | |
369 | panic!("should only be used in tests") |
|
369 | panic!("should only be used in tests") | |
370 | } |
|
370 | } | |
371 | Revision(value) |
|
371 | Revision(value) | |
372 | } |
|
372 | } | |
373 | } |
|
373 | } | |
374 |
|
374 | |||
375 | impl PartialEq<BaseRevision> for Revision { |
|
375 | impl PartialEq<BaseRevision> for Revision { | |
376 | fn eq(&self, other: &BaseRevision) -> bool { |
|
376 | fn eq(&self, other: &BaseRevision) -> bool { | |
377 | if !cfg!(test) { |
|
377 | if !cfg!(test) { | |
378 | panic!("should only be used in tests") |
|
378 | panic!("should only be used in tests") | |
379 | } |
|
379 | } | |
380 | self.0.eq(other) |
|
380 | self.0.eq(other) | |
381 | } |
|
381 | } | |
382 | } |
|
382 | } | |
383 |
|
383 | |||
384 | impl PartialEq<u32> for Revision { |
|
384 | impl PartialEq<u32> for Revision { | |
385 | fn eq(&self, other: &u32) -> bool { |
|
385 | fn eq(&self, other: &u32) -> bool { | |
386 | if !cfg!(test) { |
|
386 | if !cfg!(test) { | |
387 | panic!("should only be used in tests") |
|
387 | panic!("should only be used in tests") | |
388 | } |
|
388 | } | |
389 | let check: Result<u32, _> = self.0.try_into(); |
|
389 | let check: Result<u32, _> = self.0.try_into(); | |
390 | match check { |
|
390 | match check { | |
391 | Ok(value) => value.eq(other), |
|
391 | Ok(value) => value.eq(other), | |
392 | Err(_) => false, |
|
392 | Err(_) => false, | |
393 | } |
|
393 | } | |
394 | } |
|
394 | } | |
395 | } |
|
395 | } | |
396 |
|
396 | |||
397 | fn list_ancestors<G: Graph>( |
|
397 | fn list_ancestors<G: Graph>( | |
398 | graph: G, |
|
398 | graph: G, | |
399 | initrevs: Vec<Revision>, |
|
399 | initrevs: Vec<Revision>, | |
400 | stoprev: Revision, |
|
400 | stoprev: Revision, | |
401 | inclusive: bool, |
|
401 | inclusive: bool, | |
402 | ) -> Vec<Revision> { |
|
402 | ) -> Vec<Revision> { | |
403 | AncestorsIterator::new(graph, initrevs, stoprev, inclusive) |
|
403 | AncestorsIterator::new(graph, initrevs, stoprev, inclusive) | |
404 | .unwrap() |
|
404 | .unwrap() | |
405 | .map(|res| res.unwrap()) |
|
405 | .map(|res| res.unwrap()) | |
406 | .collect() |
|
406 | .collect() | |
407 | } |
|
407 | } | |
408 |
|
408 | |||
409 | #[test] |
|
409 | #[test] | |
410 | /// Same tests as test-ancestor.py, without membership |
|
410 | /// Same tests as test-ancestor.py, without membership | |
411 | /// (see also test-ancestor.py.out) |
|
411 | /// (see also test-ancestor.py.out) | |
412 | fn test_list_ancestor() { |
|
412 | fn test_list_ancestor() { | |
413 | assert_eq!( |
|
413 | assert_eq!( | |
414 | list_ancestors(SampleGraph, vec![], 0.into(), false), |
|
414 | list_ancestors(SampleGraph, vec![], 0.into(), false), | |
415 | Vec::<Revision>::new() |
|
415 | Vec::<Revision>::new() | |
416 | ); |
|
416 | ); | |
417 | assert_eq!( |
|
417 | assert_eq!( | |
418 | list_ancestors( |
|
418 | list_ancestors( | |
419 | SampleGraph, |
|
419 | SampleGraph, | |
420 | vec![11.into(), 13.into()], |
|
420 | vec![11.into(), 13.into()], | |
421 | 0.into(), |
|
421 | 0.into(), | |
422 | false |
|
422 | false | |
423 | ), |
|
423 | ), | |
424 | vec![8, 7, 4, 3, 2, 1, 0] |
|
424 | vec![8, 7, 4, 3, 2, 1, 0] | |
425 | ); |
|
425 | ); | |
|
426 | // it works as well on references, because &Graph implements Graph | |||
|
427 | // this is needed as of this writing by RHGitaly | |||
|
428 | assert_eq!( | |||
|
429 | list_ancestors( | |||
|
430 | &SampleGraph, | |||
|
431 | vec![11.into(), 13.into()], | |||
|
432 | 0.into(), | |||
|
433 | false | |||
|
434 | ), | |||
|
435 | vec![8, 7, 4, 3, 2, 1, 0] | |||
|
436 | ); | |||
|
437 | ||||
426 | assert_eq!( |
|
438 | assert_eq!( | |
427 | list_ancestors( |
|
439 | list_ancestors( | |
428 | SampleGraph, |
|
440 | SampleGraph, | |
429 | vec![1.into(), 3.into()], |
|
441 | vec![1.into(), 3.into()], | |
430 | 0.into(), |
|
442 | 0.into(), | |
431 | false |
|
443 | false | |
432 | ), |
|
444 | ), | |
433 | vec![1, 0] |
|
445 | vec![1, 0] | |
434 | ); |
|
446 | ); | |
435 | assert_eq!( |
|
447 | assert_eq!( | |
436 | list_ancestors( |
|
448 | list_ancestors( | |
437 | SampleGraph, |
|
449 | SampleGraph, | |
438 | vec![11.into(), 13.into()], |
|
450 | vec![11.into(), 13.into()], | |
439 | 0.into(), |
|
451 | 0.into(), | |
440 | true |
|
452 | true | |
441 | ), |
|
453 | ), | |
442 | vec![13, 11, 8, 7, 4, 3, 2, 1, 0] |
|
454 | vec![13, 11, 8, 7, 4, 3, 2, 1, 0] | |
443 | ); |
|
455 | ); | |
444 | assert_eq!( |
|
456 | assert_eq!( | |
445 | list_ancestors( |
|
457 | list_ancestors( | |
446 | SampleGraph, |
|
458 | SampleGraph, | |
447 | vec![11.into(), 13.into()], |
|
459 | vec![11.into(), 13.into()], | |
448 | 6.into(), |
|
460 | 6.into(), | |
449 | false |
|
461 | false | |
450 | ), |
|
462 | ), | |
451 | vec![8, 7] |
|
463 | vec![8, 7] | |
452 | ); |
|
464 | ); | |
453 | assert_eq!( |
|
465 | assert_eq!( | |
454 | list_ancestors( |
|
466 | list_ancestors( | |
455 | SampleGraph, |
|
467 | SampleGraph, | |
456 | vec![11.into(), 13.into()], |
|
468 | vec![11.into(), 13.into()], | |
457 | 6.into(), |
|
469 | 6.into(), | |
458 | true |
|
470 | true | |
459 | ), |
|
471 | ), | |
460 | vec![13, 11, 8, 7] |
|
472 | vec![13, 11, 8, 7] | |
461 | ); |
|
473 | ); | |
462 | assert_eq!( |
|
474 | assert_eq!( | |
463 | list_ancestors( |
|
475 | list_ancestors( | |
464 | SampleGraph, |
|
476 | SampleGraph, | |
465 | vec![11.into(), 13.into()], |
|
477 | vec![11.into(), 13.into()], | |
466 | 11.into(), |
|
478 | 11.into(), | |
467 | true |
|
479 | true | |
468 | ), |
|
480 | ), | |
469 | vec![13, 11] |
|
481 | vec![13, 11] | |
470 | ); |
|
482 | ); | |
471 | assert_eq!( |
|
483 | assert_eq!( | |
472 | list_ancestors( |
|
484 | list_ancestors( | |
473 | SampleGraph, |
|
485 | SampleGraph, | |
474 | vec![11.into(), 13.into()], |
|
486 | vec![11.into(), 13.into()], | |
475 | 12.into(), |
|
487 | 12.into(), | |
476 | true |
|
488 | true | |
477 | ), |
|
489 | ), | |
478 | vec![13] |
|
490 | vec![13] | |
479 | ); |
|
491 | ); | |
480 | assert_eq!( |
|
492 | assert_eq!( | |
481 | list_ancestors( |
|
493 | list_ancestors( | |
482 | SampleGraph, |
|
494 | SampleGraph, | |
483 | vec![10.into(), 1.into()], |
|
495 | vec![10.into(), 1.into()], | |
484 | 0.into(), |
|
496 | 0.into(), | |
485 | true |
|
497 | true | |
486 | ), |
|
498 | ), | |
487 | vec![10, 5, 4, 2, 1, 0] |
|
499 | vec![10, 5, 4, 2, 1, 0] | |
488 | ); |
|
500 | ); | |
489 | } |
|
501 | } | |
490 |
|
502 | |||
491 | #[test] |
|
503 | #[test] | |
492 | /// Corner case that's not directly in test-ancestors.py, but |
|
504 | /// Corner case that's not directly in test-ancestors.py, but | |
493 | /// that happens quite often, as demonstrated by running the whole |
|
505 | /// that happens quite often, as demonstrated by running the whole | |
494 | /// suite. |
|
506 | /// suite. | |
495 | /// For instance, run tests/test-obsolete-checkheads.t |
|
507 | /// For instance, run tests/test-obsolete-checkheads.t | |
496 | fn test_nullrev_input() { |
|
508 | fn test_nullrev_input() { | |
497 | let mut iter = AncestorsIterator::new( |
|
509 | let mut iter = AncestorsIterator::new( | |
498 | SampleGraph, |
|
510 | SampleGraph, | |
499 | vec![Revision(-1)], |
|
511 | vec![Revision(-1)], | |
500 | 0.into(), |
|
512 | 0.into(), | |
501 | false, |
|
513 | false, | |
502 | ) |
|
514 | ) | |
503 | .unwrap(); |
|
515 | .unwrap(); | |
504 | assert_eq!(iter.next(), None) |
|
516 | assert_eq!(iter.next(), None) | |
505 | } |
|
517 | } | |
506 |
|
518 | |||
507 | #[test] |
|
519 | #[test] | |
508 | fn test_contains() { |
|
520 | fn test_contains() { | |
509 | let mut lazy = AncestorsIterator::new( |
|
521 | let mut lazy = AncestorsIterator::new( | |
510 | SampleGraph, |
|
522 | SampleGraph, | |
511 | vec![10.into(), 1.into()], |
|
523 | vec![10.into(), 1.into()], | |
512 | 0.into(), |
|
524 | 0.into(), | |
513 | true, |
|
525 | true, | |
514 | ) |
|
526 | ) | |
515 | .unwrap(); |
|
527 | .unwrap(); | |
516 | assert!(lazy.contains(1.into()).unwrap()); |
|
528 | assert!(lazy.contains(1.into()).unwrap()); | |
517 | assert!(!lazy.contains(3.into()).unwrap()); |
|
529 | assert!(!lazy.contains(3.into()).unwrap()); | |
518 |
|
530 | |||
519 | let mut lazy = AncestorsIterator::new( |
|
531 | let mut lazy = AncestorsIterator::new( | |
520 | SampleGraph, |
|
532 | SampleGraph, | |
521 | vec![0.into()], |
|
533 | vec![0.into()], | |
522 | 0.into(), |
|
534 | 0.into(), | |
523 | false, |
|
535 | false, | |
524 | ) |
|
536 | ) | |
525 | .unwrap(); |
|
537 | .unwrap(); | |
526 | assert!(!lazy.contains(NULL_REVISION).unwrap()); |
|
538 | assert!(!lazy.contains(NULL_REVISION).unwrap()); | |
527 | } |
|
539 | } | |
528 |
|
540 | |||
529 | #[test] |
|
541 | #[test] | |
530 | fn test_peek() { |
|
542 | fn test_peek() { | |
531 | let mut iter = AncestorsIterator::new( |
|
543 | let mut iter = AncestorsIterator::new( | |
532 | SampleGraph, |
|
544 | SampleGraph, | |
533 | vec![10.into()], |
|
545 | vec![10.into()], | |
534 | 0.into(), |
|
546 | 0.into(), | |
535 | true, |
|
547 | true, | |
536 | ) |
|
548 | ) | |
537 | .unwrap(); |
|
549 | .unwrap(); | |
538 | // peek() gives us the next value |
|
550 | // peek() gives us the next value | |
539 | assert_eq!(iter.peek(), Some(10.into())); |
|
551 | assert_eq!(iter.peek(), Some(10.into())); | |
540 | // but it's not been consumed |
|
552 | // but it's not been consumed | |
541 | assert_eq!(iter.next(), Some(Ok(10.into()))); |
|
553 | assert_eq!(iter.next(), Some(Ok(10.into()))); | |
542 | // and iteration resumes normally |
|
554 | // and iteration resumes normally | |
543 | assert_eq!(iter.next(), Some(Ok(5.into()))); |
|
555 | assert_eq!(iter.next(), Some(Ok(5.into()))); | |
544 |
|
556 | |||
545 | // let's drain the iterator to test peek() at the end |
|
557 | // let's drain the iterator to test peek() at the end | |
546 | while iter.next().is_some() {} |
|
558 | while iter.next().is_some() {} | |
547 | assert_eq!(iter.peek(), None); |
|
559 | assert_eq!(iter.peek(), None); | |
548 | } |
|
560 | } | |
549 |
|
561 | |||
550 | #[test] |
|
562 | #[test] | |
551 | fn test_empty() { |
|
563 | fn test_empty() { | |
552 | let mut iter = AncestorsIterator::new( |
|
564 | let mut iter = AncestorsIterator::new( | |
553 | SampleGraph, |
|
565 | SampleGraph, | |
554 | vec![10.into()], |
|
566 | vec![10.into()], | |
555 | 0.into(), |
|
567 | 0.into(), | |
556 | true, |
|
568 | true, | |
557 | ) |
|
569 | ) | |
558 | .unwrap(); |
|
570 | .unwrap(); | |
559 | assert!(!iter.is_empty()); |
|
571 | assert!(!iter.is_empty()); | |
560 | while iter.next().is_some() {} |
|
572 | while iter.next().is_some() {} | |
561 | assert!(!iter.is_empty()); |
|
573 | assert!(!iter.is_empty()); | |
562 |
|
574 | |||
563 | let iter = AncestorsIterator::new(SampleGraph, vec![], 0.into(), true) |
|
575 | let iter = AncestorsIterator::new(SampleGraph, vec![], 0.into(), true) | |
564 | .unwrap(); |
|
576 | .unwrap(); | |
565 | assert!(iter.is_empty()); |
|
577 | assert!(iter.is_empty()); | |
566 |
|
578 | |||
567 | // case where iter.seen == {NULL_REVISION} |
|
579 | // case where iter.seen == {NULL_REVISION} | |
568 | let iter = AncestorsIterator::new( |
|
580 | let iter = AncestorsIterator::new( | |
569 | SampleGraph, |
|
581 | SampleGraph, | |
570 | vec![0.into()], |
|
582 | vec![0.into()], | |
571 | 0.into(), |
|
583 | 0.into(), | |
572 | false, |
|
584 | false, | |
573 | ) |
|
585 | ) | |
574 | .unwrap(); |
|
586 | .unwrap(); | |
575 | assert!(iter.is_empty()); |
|
587 | assert!(iter.is_empty()); | |
576 | } |
|
588 | } | |
577 |
|
589 | |||
578 | /// A corrupted Graph, supporting error handling tests |
|
590 | /// A corrupted Graph, supporting error handling tests | |
579 | #[derive(Clone, Debug)] |
|
591 | #[derive(Clone, Debug)] | |
580 | struct Corrupted; |
|
592 | struct Corrupted; | |
581 |
|
593 | |||
582 | impl Graph for Corrupted { |
|
594 | impl Graph for Corrupted { | |
583 | // FIXME what to do about this? Are we just not supposed to get them |
|
595 | // FIXME what to do about this? Are we just not supposed to get them | |
584 | // anymore? |
|
596 | // anymore? | |
585 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { |
|
597 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |
586 | match rev { |
|
598 | match rev { | |
587 | Revision(1) => Ok([0.into(), (-1).into()]), |
|
599 | Revision(1) => Ok([0.into(), (-1).into()]), | |
588 | r => Err(GraphError::ParentOutOfRange(r)), |
|
600 | r => Err(GraphError::ParentOutOfRange(r)), | |
589 | } |
|
601 | } | |
590 | } |
|
602 | } | |
591 | } |
|
603 | } | |
592 |
|
604 | |||
593 | #[test] |
|
605 | #[test] | |
594 | fn test_initrev_out_of_range() { |
|
606 | fn test_initrev_out_of_range() { | |
595 | // inclusive=false looks up initrev's parents right away |
|
607 | // inclusive=false looks up initrev's parents right away | |
596 | match AncestorsIterator::new( |
|
608 | match AncestorsIterator::new( | |
597 | SampleGraph, |
|
609 | SampleGraph, | |
598 | vec![25.into()], |
|
610 | vec![25.into()], | |
599 | 0.into(), |
|
611 | 0.into(), | |
600 | false, |
|
612 | false, | |
601 | ) { |
|
613 | ) { | |
602 | Ok(_) => panic!("Should have been ParentOutOfRange"), |
|
614 | Ok(_) => panic!("Should have been ParentOutOfRange"), | |
603 | Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25.into())), |
|
615 | Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25.into())), | |
604 | } |
|
616 | } | |
605 | } |
|
617 | } | |
606 |
|
618 | |||
607 | #[test] |
|
619 | #[test] | |
608 | fn test_next_out_of_range() { |
|
620 | fn test_next_out_of_range() { | |
609 | // inclusive=false looks up initrev's parents right away |
|
621 | // inclusive=false looks up initrev's parents right away | |
610 | let mut iter = |
|
622 | let mut iter = | |
611 | AncestorsIterator::new(Corrupted, vec![1.into()], 0.into(), false) |
|
623 | AncestorsIterator::new(Corrupted, vec![1.into()], 0.into(), false) | |
612 | .unwrap(); |
|
624 | .unwrap(); | |
613 | assert_eq!( |
|
625 | assert_eq!( | |
614 | iter.next(), |
|
626 | iter.next(), | |
615 | Some(Err(GraphError::ParentOutOfRange(0.into()))) |
|
627 | Some(Err(GraphError::ParentOutOfRange(0.into()))) | |
616 | ); |
|
628 | ); | |
617 | } |
|
629 | } | |
618 |
|
630 | |||
619 | #[test] |
|
631 | #[test] | |
620 | /// Test constructor, add/get bases and heads |
|
632 | /// Test constructor, add/get bases and heads | |
621 | fn test_missing_bases() -> Result<(), GraphError> { |
|
633 | fn test_missing_bases() -> Result<(), GraphError> { | |
622 | let mut missing_ancestors = MissingAncestors::new( |
|
634 | let mut missing_ancestors = MissingAncestors::new( | |
623 | SampleGraph, |
|
635 | SampleGraph, | |
624 | [5.into(), 3.into(), 1.into(), 3.into()].iter().cloned(), |
|
636 | [5.into(), 3.into(), 1.into(), 3.into()].iter().cloned(), | |
625 | ); |
|
637 | ); | |
626 | let mut as_vec: Vec<Revision> = |
|
638 | let mut as_vec: Vec<Revision> = | |
627 | missing_ancestors.get_bases().iter().cloned().collect(); |
|
639 | missing_ancestors.get_bases().iter().cloned().collect(); | |
628 | as_vec.sort_unstable(); |
|
640 | as_vec.sort_unstable(); | |
629 | assert_eq!(as_vec, [1, 3, 5]); |
|
641 | assert_eq!(as_vec, [1, 3, 5]); | |
630 | assert_eq!(missing_ancestors.max_base, 5); |
|
642 | assert_eq!(missing_ancestors.max_base, 5); | |
631 |
|
643 | |||
632 | missing_ancestors |
|
644 | missing_ancestors | |
633 | .add_bases([3.into(), 7.into(), 8.into()].iter().cloned()); |
|
645 | .add_bases([3.into(), 7.into(), 8.into()].iter().cloned()); | |
634 | as_vec = missing_ancestors.get_bases().iter().cloned().collect(); |
|
646 | as_vec = missing_ancestors.get_bases().iter().cloned().collect(); | |
635 | as_vec.sort_unstable(); |
|
647 | as_vec.sort_unstable(); | |
636 | assert_eq!(as_vec, [1, 3, 5, 7, 8]); |
|
648 | assert_eq!(as_vec, [1, 3, 5, 7, 8]); | |
637 | assert_eq!(missing_ancestors.max_base, 8); |
|
649 | assert_eq!(missing_ancestors.max_base, 8); | |
638 |
|
650 | |||
639 | as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect(); |
|
651 | as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect(); | |
640 | as_vec.sort_unstable(); |
|
652 | as_vec.sort_unstable(); | |
641 | assert_eq!(as_vec, [3, 5, 7, 8]); |
|
653 | assert_eq!(as_vec, [3, 5, 7, 8]); | |
642 | Ok(()) |
|
654 | Ok(()) | |
643 | } |
|
655 | } | |
644 |
|
656 | |||
645 | fn assert_missing_remove( |
|
657 | fn assert_missing_remove( | |
646 | bases: &[BaseRevision], |
|
658 | bases: &[BaseRevision], | |
647 | revs: &[BaseRevision], |
|
659 | revs: &[BaseRevision], | |
648 | expected: &[BaseRevision], |
|
660 | expected: &[BaseRevision], | |
649 | ) { |
|
661 | ) { | |
650 | let mut missing_ancestors = MissingAncestors::new( |
|
662 | let mut missing_ancestors = MissingAncestors::new( | |
651 | SampleGraph, |
|
663 | SampleGraph, | |
652 | bases.iter().map(|r| Revision(*r)), |
|
664 | bases.iter().map(|r| Revision(*r)), | |
653 | ); |
|
665 | ); | |
654 | let mut revset: HashSet<Revision> = |
|
666 | let mut revset: HashSet<Revision> = | |
655 | revs.iter().map(|r| Revision(*r)).collect(); |
|
667 | revs.iter().map(|r| Revision(*r)).collect(); | |
656 | missing_ancestors |
|
668 | missing_ancestors | |
657 | .remove_ancestors_from(&mut revset) |
|
669 | .remove_ancestors_from(&mut revset) | |
658 | .unwrap(); |
|
670 | .unwrap(); | |
659 | let mut as_vec: Vec<Revision> = revset.into_iter().collect(); |
|
671 | let mut as_vec: Vec<Revision> = revset.into_iter().collect(); | |
660 | as_vec.sort_unstable(); |
|
672 | as_vec.sort_unstable(); | |
661 | assert_eq!(as_vec.as_slice(), expected); |
|
673 | assert_eq!(as_vec.as_slice(), expected); | |
662 | } |
|
674 | } | |
663 |
|
675 | |||
664 | #[test] |
|
676 | #[test] | |
665 | fn test_missing_remove() { |
|
677 | fn test_missing_remove() { | |
666 | assert_missing_remove( |
|
678 | assert_missing_remove( | |
667 | &[1, 2, 3, 4, 7], |
|
679 | &[1, 2, 3, 4, 7], | |
668 | Vec::from_iter(1..10).as_slice(), |
|
680 | Vec::from_iter(1..10).as_slice(), | |
669 | &[5, 6, 8, 9], |
|
681 | &[5, 6, 8, 9], | |
670 | ); |
|
682 | ); | |
671 | assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]); |
|
683 | assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]); | |
672 | assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]); |
|
684 | assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]); | |
673 | } |
|
685 | } | |
674 |
|
686 | |||
675 | fn assert_missing_ancestors( |
|
687 | fn assert_missing_ancestors( | |
676 | bases: &[BaseRevision], |
|
688 | bases: &[BaseRevision], | |
677 | revs: &[BaseRevision], |
|
689 | revs: &[BaseRevision], | |
678 | expected: &[BaseRevision], |
|
690 | expected: &[BaseRevision], | |
679 | ) { |
|
691 | ) { | |
680 | let mut missing_ancestors = MissingAncestors::new( |
|
692 | let mut missing_ancestors = MissingAncestors::new( | |
681 | SampleGraph, |
|
693 | SampleGraph, | |
682 | bases.iter().map(|r| Revision(*r)), |
|
694 | bases.iter().map(|r| Revision(*r)), | |
683 | ); |
|
695 | ); | |
684 | let missing = missing_ancestors |
|
696 | let missing = missing_ancestors | |
685 | .missing_ancestors(revs.iter().map(|r| Revision(*r))) |
|
697 | .missing_ancestors(revs.iter().map(|r| Revision(*r))) | |
686 | .unwrap(); |
|
698 | .unwrap(); | |
687 | assert_eq!(missing.as_slice(), expected); |
|
699 | assert_eq!(missing.as_slice(), expected); | |
688 | } |
|
700 | } | |
689 |
|
701 | |||
690 | #[test] |
|
702 | #[test] | |
691 | fn test_missing_ancestors() { |
|
703 | fn test_missing_ancestors() { | |
692 | // examples taken from test-ancestors.py by having it run |
|
704 | // examples taken from test-ancestors.py by having it run | |
693 | // on the same graph (both naive and fast Python algs) |
|
705 | // on the same graph (both naive and fast Python algs) | |
694 | assert_missing_ancestors(&[10], &[11], &[3, 7, 11]); |
|
706 | assert_missing_ancestors(&[10], &[11], &[3, 7, 11]); | |
695 | assert_missing_ancestors(&[11], &[10], &[5, 10]); |
|
707 | assert_missing_ancestors(&[11], &[10], &[5, 10]); | |
696 | assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]); |
|
708 | assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]); | |
697 | } |
|
709 | } | |
698 |
|
710 | |||
699 | /// An interesting case found by a random generator similar to |
|
711 | /// An interesting case found by a random generator similar to | |
700 | /// the one in test-ancestor.py. An early version of Rust MissingAncestors |
|
712 | /// the one in test-ancestor.py. An early version of Rust MissingAncestors | |
701 | /// failed this, yet none of the integration tests of the whole suite |
|
713 | /// failed this, yet none of the integration tests of the whole suite | |
702 | /// catched it. |
|
714 | /// catched it. | |
703 | #[allow(clippy::unnecessary_cast)] |
|
715 | #[allow(clippy::unnecessary_cast)] | |
704 | #[test] |
|
716 | #[test] | |
705 | fn test_remove_ancestors_from_case1() { |
|
717 | fn test_remove_ancestors_from_case1() { | |
706 | const FAKE_NULL_REVISION: BaseRevision = -1; |
|
718 | const FAKE_NULL_REVISION: BaseRevision = -1; | |
707 | assert_eq!(FAKE_NULL_REVISION, NULL_REVISION.0); |
|
719 | assert_eq!(FAKE_NULL_REVISION, NULL_REVISION.0); | |
708 | let graph: VecGraph = vec![ |
|
720 | let graph: VecGraph = vec![ | |
709 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
721 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
710 | [0, FAKE_NULL_REVISION], |
|
722 | [0, FAKE_NULL_REVISION], | |
711 | [1, 0], |
|
723 | [1, 0], | |
712 | [2, 1], |
|
724 | [2, 1], | |
713 | [3, FAKE_NULL_REVISION], |
|
725 | [3, FAKE_NULL_REVISION], | |
714 | [4, FAKE_NULL_REVISION], |
|
726 | [4, FAKE_NULL_REVISION], | |
715 | [5, 1], |
|
727 | [5, 1], | |
716 | [2, FAKE_NULL_REVISION], |
|
728 | [2, FAKE_NULL_REVISION], | |
717 | [7, FAKE_NULL_REVISION], |
|
729 | [7, FAKE_NULL_REVISION], | |
718 | [8, FAKE_NULL_REVISION], |
|
730 | [8, FAKE_NULL_REVISION], | |
719 | [9, FAKE_NULL_REVISION], |
|
731 | [9, FAKE_NULL_REVISION], | |
720 | [10, 1], |
|
732 | [10, 1], | |
721 | [3, FAKE_NULL_REVISION], |
|
733 | [3, FAKE_NULL_REVISION], | |
722 | [12, FAKE_NULL_REVISION], |
|
734 | [12, FAKE_NULL_REVISION], | |
723 | [13, FAKE_NULL_REVISION], |
|
735 | [13, FAKE_NULL_REVISION], | |
724 | [14, FAKE_NULL_REVISION], |
|
736 | [14, FAKE_NULL_REVISION], | |
725 | [4, FAKE_NULL_REVISION], |
|
737 | [4, FAKE_NULL_REVISION], | |
726 | [16, FAKE_NULL_REVISION], |
|
738 | [16, FAKE_NULL_REVISION], | |
727 | [17, FAKE_NULL_REVISION], |
|
739 | [17, FAKE_NULL_REVISION], | |
728 | [18, FAKE_NULL_REVISION], |
|
740 | [18, FAKE_NULL_REVISION], | |
729 | [19, 11], |
|
741 | [19, 11], | |
730 | [20, FAKE_NULL_REVISION], |
|
742 | [20, FAKE_NULL_REVISION], | |
731 | [21, FAKE_NULL_REVISION], |
|
743 | [21, FAKE_NULL_REVISION], | |
732 | [22, FAKE_NULL_REVISION], |
|
744 | [22, FAKE_NULL_REVISION], | |
733 | [23, FAKE_NULL_REVISION], |
|
745 | [23, FAKE_NULL_REVISION], | |
734 | [2, FAKE_NULL_REVISION], |
|
746 | [2, FAKE_NULL_REVISION], | |
735 | [3, FAKE_NULL_REVISION], |
|
747 | [3, FAKE_NULL_REVISION], | |
736 | [26, 24], |
|
748 | [26, 24], | |
737 | [27, FAKE_NULL_REVISION], |
|
749 | [27, FAKE_NULL_REVISION], | |
738 | [28, FAKE_NULL_REVISION], |
|
750 | [28, FAKE_NULL_REVISION], | |
739 | [12, FAKE_NULL_REVISION], |
|
751 | [12, FAKE_NULL_REVISION], | |
740 | [1, FAKE_NULL_REVISION], |
|
752 | [1, FAKE_NULL_REVISION], | |
741 | [1, 9], |
|
753 | [1, 9], | |
742 | [32, FAKE_NULL_REVISION], |
|
754 | [32, FAKE_NULL_REVISION], | |
743 | [33, FAKE_NULL_REVISION], |
|
755 | [33, FAKE_NULL_REVISION], | |
744 | [34, 31], |
|
756 | [34, 31], | |
745 | [35, FAKE_NULL_REVISION], |
|
757 | [35, FAKE_NULL_REVISION], | |
746 | [36, 26], |
|
758 | [36, 26], | |
747 | [37, FAKE_NULL_REVISION], |
|
759 | [37, FAKE_NULL_REVISION], | |
748 | [38, FAKE_NULL_REVISION], |
|
760 | [38, FAKE_NULL_REVISION], | |
749 | [39, FAKE_NULL_REVISION], |
|
761 | [39, FAKE_NULL_REVISION], | |
750 | [40, FAKE_NULL_REVISION], |
|
762 | [40, FAKE_NULL_REVISION], | |
751 | [41, FAKE_NULL_REVISION], |
|
763 | [41, FAKE_NULL_REVISION], | |
752 | [42, 26], |
|
764 | [42, 26], | |
753 | [0, FAKE_NULL_REVISION], |
|
765 | [0, FAKE_NULL_REVISION], | |
754 | [44, FAKE_NULL_REVISION], |
|
766 | [44, FAKE_NULL_REVISION], | |
755 | [45, 4], |
|
767 | [45, 4], | |
756 | [40, FAKE_NULL_REVISION], |
|
768 | [40, FAKE_NULL_REVISION], | |
757 | [47, FAKE_NULL_REVISION], |
|
769 | [47, FAKE_NULL_REVISION], | |
758 | [36, 0], |
|
770 | [36, 0], | |
759 | [49, FAKE_NULL_REVISION], |
|
771 | [49, FAKE_NULL_REVISION], | |
760 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
772 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
761 | [51, FAKE_NULL_REVISION], |
|
773 | [51, FAKE_NULL_REVISION], | |
762 | [52, FAKE_NULL_REVISION], |
|
774 | [52, FAKE_NULL_REVISION], | |
763 | [53, FAKE_NULL_REVISION], |
|
775 | [53, FAKE_NULL_REVISION], | |
764 | [14, FAKE_NULL_REVISION], |
|
776 | [14, FAKE_NULL_REVISION], | |
765 | [55, FAKE_NULL_REVISION], |
|
777 | [55, FAKE_NULL_REVISION], | |
766 | [15, FAKE_NULL_REVISION], |
|
778 | [15, FAKE_NULL_REVISION], | |
767 | [23, FAKE_NULL_REVISION], |
|
779 | [23, FAKE_NULL_REVISION], | |
768 | [58, FAKE_NULL_REVISION], |
|
780 | [58, FAKE_NULL_REVISION], | |
769 | [59, FAKE_NULL_REVISION], |
|
781 | [59, FAKE_NULL_REVISION], | |
770 | [2, FAKE_NULL_REVISION], |
|
782 | [2, FAKE_NULL_REVISION], | |
771 | [61, 59], |
|
783 | [61, 59], | |
772 | [62, FAKE_NULL_REVISION], |
|
784 | [62, FAKE_NULL_REVISION], | |
773 | [63, FAKE_NULL_REVISION], |
|
785 | [63, FAKE_NULL_REVISION], | |
774 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
786 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
775 | [65, FAKE_NULL_REVISION], |
|
787 | [65, FAKE_NULL_REVISION], | |
776 | [66, FAKE_NULL_REVISION], |
|
788 | [66, FAKE_NULL_REVISION], | |
777 | [67, FAKE_NULL_REVISION], |
|
789 | [67, FAKE_NULL_REVISION], | |
778 | [68, FAKE_NULL_REVISION], |
|
790 | [68, FAKE_NULL_REVISION], | |
779 | [37, 28], |
|
791 | [37, 28], | |
780 | [69, 25], |
|
792 | [69, 25], | |
781 | [71, FAKE_NULL_REVISION], |
|
793 | [71, FAKE_NULL_REVISION], | |
782 | [72, FAKE_NULL_REVISION], |
|
794 | [72, FAKE_NULL_REVISION], | |
783 | [50, 2], |
|
795 | [50, 2], | |
784 | [74, FAKE_NULL_REVISION], |
|
796 | [74, FAKE_NULL_REVISION], | |
785 | [12, FAKE_NULL_REVISION], |
|
797 | [12, FAKE_NULL_REVISION], | |
786 | [18, FAKE_NULL_REVISION], |
|
798 | [18, FAKE_NULL_REVISION], | |
787 | [77, FAKE_NULL_REVISION], |
|
799 | [77, FAKE_NULL_REVISION], | |
788 | [78, FAKE_NULL_REVISION], |
|
800 | [78, FAKE_NULL_REVISION], | |
789 | [79, FAKE_NULL_REVISION], |
|
801 | [79, FAKE_NULL_REVISION], | |
790 | [43, 33], |
|
802 | [43, 33], | |
791 | [81, FAKE_NULL_REVISION], |
|
803 | [81, FAKE_NULL_REVISION], | |
792 | [82, FAKE_NULL_REVISION], |
|
804 | [82, FAKE_NULL_REVISION], | |
793 | [83, FAKE_NULL_REVISION], |
|
805 | [83, FAKE_NULL_REVISION], | |
794 | [84, 45], |
|
806 | [84, 45], | |
795 | [85, FAKE_NULL_REVISION], |
|
807 | [85, FAKE_NULL_REVISION], | |
796 | [86, FAKE_NULL_REVISION], |
|
808 | [86, FAKE_NULL_REVISION], | |
797 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
809 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
798 | [88, FAKE_NULL_REVISION], |
|
810 | [88, FAKE_NULL_REVISION], | |
799 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
811 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
800 | [76, 83], |
|
812 | [76, 83], | |
801 | [44, FAKE_NULL_REVISION], |
|
813 | [44, FAKE_NULL_REVISION], | |
802 | [92, FAKE_NULL_REVISION], |
|
814 | [92, FAKE_NULL_REVISION], | |
803 | [93, FAKE_NULL_REVISION], |
|
815 | [93, FAKE_NULL_REVISION], | |
804 | [9, FAKE_NULL_REVISION], |
|
816 | [9, FAKE_NULL_REVISION], | |
805 | [95, 67], |
|
817 | [95, 67], | |
806 | [96, FAKE_NULL_REVISION], |
|
818 | [96, FAKE_NULL_REVISION], | |
807 | [97, FAKE_NULL_REVISION], |
|
819 | [97, FAKE_NULL_REVISION], | |
808 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], |
|
820 | [FAKE_NULL_REVISION, FAKE_NULL_REVISION], | |
809 | ] |
|
821 | ] | |
810 | .into_iter() |
|
822 | .into_iter() | |
811 | .map(|[a, b]| [Revision(a), Revision(b)]) |
|
823 | .map(|[a, b]| [Revision(a), Revision(b)]) | |
812 | .collect(); |
|
824 | .collect(); | |
813 | let problem_rev = 28.into(); |
|
825 | let problem_rev = 28.into(); | |
814 | let problem_base = 70.into(); |
|
826 | let problem_base = 70.into(); | |
815 | // making the problem obvious: problem_rev is a parent of problem_base |
|
827 | // making the problem obvious: problem_rev is a parent of problem_base | |
816 | assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev); |
|
828 | assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev); | |
817 |
|
829 | |||
818 | let mut missing_ancestors: MissingAncestors<VecGraph> = |
|
830 | let mut missing_ancestors: MissingAncestors<VecGraph> = | |
819 | MissingAncestors::new( |
|
831 | MissingAncestors::new( | |
820 | graph, |
|
832 | graph, | |
821 | [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6] |
|
833 | [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6] | |
822 | .iter() |
|
834 | .iter() | |
823 | .map(|r| Revision(*r)), |
|
835 | .map(|r| Revision(*r)), | |
824 | ); |
|
836 | ); | |
825 | assert!(missing_ancestors.bases.contains(&problem_base)); |
|
837 | assert!(missing_ancestors.bases.contains(&problem_base)); | |
826 |
|
838 | |||
827 | let mut revs: HashSet<Revision> = |
|
839 | let mut revs: HashSet<Revision> = | |
828 | [4, 12, 41, 28, 68, 38, 1, 30, 56, 44] |
|
840 | [4, 12, 41, 28, 68, 38, 1, 30, 56, 44] | |
829 | .iter() |
|
841 | .iter() | |
830 | .map(|r| Revision(*r)) |
|
842 | .map(|r| Revision(*r)) | |
831 | .collect(); |
|
843 | .collect(); | |
832 | missing_ancestors.remove_ancestors_from(&mut revs).unwrap(); |
|
844 | missing_ancestors.remove_ancestors_from(&mut revs).unwrap(); | |
833 | assert!(!revs.contains(&problem_rev)); |
|
845 | assert!(!revs.contains(&problem_rev)); | |
834 | } |
|
846 | } | |
835 | } |
|
847 | } |
@@ -1,1033 +1,1039 b'' | |||||
1 | // Copyright 2018-2023 Georges Racinet <georges.racinet@octobus.net> |
|
1 | // Copyright 2018-2023 Georges Racinet <georges.racinet@octobus.net> | |
2 | // and Mercurial contributors |
|
2 | // and Mercurial contributors | |
3 | // |
|
3 | // | |
4 | // This software may be used and distributed according to the terms of the |
|
4 | // This software may be used and distributed according to the terms of the | |
5 | // GNU General Public License version 2 or any later version. |
|
5 | // GNU General Public License version 2 or any later version. | |
6 | //! Mercurial concepts for handling revision history |
|
6 | //! Mercurial concepts for handling revision history | |
7 |
|
7 | |||
8 | pub mod node; |
|
8 | pub mod node; | |
9 | pub mod nodemap; |
|
9 | pub mod nodemap; | |
10 | mod nodemap_docket; |
|
10 | mod nodemap_docket; | |
11 | pub mod path_encode; |
|
11 | pub mod path_encode; | |
12 | pub use node::{FromHexError, Node, NodePrefix}; |
|
12 | pub use node::{FromHexError, Node, NodePrefix}; | |
13 | pub mod changelog; |
|
13 | pub mod changelog; | |
14 | pub mod filelog; |
|
14 | pub mod filelog; | |
15 | pub mod index; |
|
15 | pub mod index; | |
16 | pub mod manifest; |
|
16 | pub mod manifest; | |
17 | pub mod patch; |
|
17 | pub mod patch; | |
18 |
|
18 | |||
19 | use std::borrow::Cow; |
|
19 | use std::borrow::Cow; | |
20 | use std::io::Read; |
|
20 | use std::io::Read; | |
21 | use std::ops::Deref; |
|
21 | use std::ops::Deref; | |
22 | use std::path::Path; |
|
22 | use std::path::Path; | |
23 |
|
23 | |||
24 | use flate2::read::ZlibDecoder; |
|
24 | use flate2::read::ZlibDecoder; | |
25 | use sha1::{Digest, Sha1}; |
|
25 | use sha1::{Digest, Sha1}; | |
26 | use std::cell::RefCell; |
|
26 | use std::cell::RefCell; | |
27 | use zstd; |
|
27 | use zstd; | |
28 |
|
28 | |||
29 | use self::node::{NODE_BYTES_LENGTH, NULL_NODE}; |
|
29 | use self::node::{NODE_BYTES_LENGTH, NULL_NODE}; | |
30 | use self::nodemap_docket::NodeMapDocket; |
|
30 | use self::nodemap_docket::NodeMapDocket; | |
31 | use super::index::Index; |
|
31 | use super::index::Index; | |
32 | use super::nodemap::{NodeMap, NodeMapError}; |
|
32 | use super::nodemap::{NodeMap, NodeMapError}; | |
33 | use crate::errors::HgError; |
|
33 | use crate::errors::HgError; | |
34 | use crate::vfs::Vfs; |
|
34 | use crate::vfs::Vfs; | |
35 |
|
35 | |||
36 | /// As noted in revlog.c, revision numbers are actually encoded in |
|
36 | /// As noted in revlog.c, revision numbers are actually encoded in | |
37 | /// 4 bytes, and are liberally converted to ints, whence the i32 |
|
37 | /// 4 bytes, and are liberally converted to ints, whence the i32 | |
38 | pub type BaseRevision = i32; |
|
38 | pub type BaseRevision = i32; | |
39 |
|
39 | |||
40 | /// Mercurial revision numbers |
|
40 | /// Mercurial revision numbers | |
41 | /// In contrast to the more general [`UncheckedRevision`], these are "checked" |
|
41 | /// In contrast to the more general [`UncheckedRevision`], these are "checked" | |
42 | /// in the sense that they should only be used for revisions that are |
|
42 | /// in the sense that they should only be used for revisions that are | |
43 | /// valid for a given index (i.e. in bounds). |
|
43 | /// valid for a given index (i.e. in bounds). | |
44 | #[derive( |
|
44 | #[derive( | |
45 | Debug, |
|
45 | Debug, | |
46 | derive_more::Display, |
|
46 | derive_more::Display, | |
47 | Clone, |
|
47 | Clone, | |
48 | Copy, |
|
48 | Copy, | |
49 | Hash, |
|
49 | Hash, | |
50 | PartialEq, |
|
50 | PartialEq, | |
51 | Eq, |
|
51 | Eq, | |
52 | PartialOrd, |
|
52 | PartialOrd, | |
53 | Ord, |
|
53 | Ord, | |
54 | )] |
|
54 | )] | |
55 | pub struct Revision(pub BaseRevision); |
|
55 | pub struct Revision(pub BaseRevision); | |
56 |
|
56 | |||
57 | impl format_bytes::DisplayBytes for Revision { |
|
57 | impl format_bytes::DisplayBytes for Revision { | |
58 | fn display_bytes( |
|
58 | fn display_bytes( | |
59 | &self, |
|
59 | &self, | |
60 | output: &mut dyn std::io::Write, |
|
60 | output: &mut dyn std::io::Write, | |
61 | ) -> std::io::Result<()> { |
|
61 | ) -> std::io::Result<()> { | |
62 | self.0.display_bytes(output) |
|
62 | self.0.display_bytes(output) | |
63 | } |
|
63 | } | |
64 | } |
|
64 | } | |
65 |
|
65 | |||
66 | /// Unchecked Mercurial revision numbers. |
|
66 | /// Unchecked Mercurial revision numbers. | |
67 | /// |
|
67 | /// | |
68 | /// Values of this type have no guarantee of being a valid revision number |
|
68 | /// Values of this type have no guarantee of being a valid revision number | |
69 | /// in any context. Use method `check_revision` to get a valid revision within |
|
69 | /// in any context. Use method `check_revision` to get a valid revision within | |
70 | /// the appropriate index object. |
|
70 | /// the appropriate index object. | |
71 | #[derive( |
|
71 | #[derive( | |
72 | Debug, |
|
72 | Debug, | |
73 | derive_more::Display, |
|
73 | derive_more::Display, | |
74 | Clone, |
|
74 | Clone, | |
75 | Copy, |
|
75 | Copy, | |
76 | Hash, |
|
76 | Hash, | |
77 | PartialEq, |
|
77 | PartialEq, | |
78 | Eq, |
|
78 | Eq, | |
79 | PartialOrd, |
|
79 | PartialOrd, | |
80 | Ord, |
|
80 | Ord, | |
81 | )] |
|
81 | )] | |
82 | pub struct UncheckedRevision(pub BaseRevision); |
|
82 | pub struct UncheckedRevision(pub BaseRevision); | |
83 |
|
83 | |||
84 | impl format_bytes::DisplayBytes for UncheckedRevision { |
|
84 | impl format_bytes::DisplayBytes for UncheckedRevision { | |
85 | fn display_bytes( |
|
85 | fn display_bytes( | |
86 | &self, |
|
86 | &self, | |
87 | output: &mut dyn std::io::Write, |
|
87 | output: &mut dyn std::io::Write, | |
88 | ) -> std::io::Result<()> { |
|
88 | ) -> std::io::Result<()> { | |
89 | self.0.display_bytes(output) |
|
89 | self.0.display_bytes(output) | |
90 | } |
|
90 | } | |
91 | } |
|
91 | } | |
92 |
|
92 | |||
93 | impl From<Revision> for UncheckedRevision { |
|
93 | impl From<Revision> for UncheckedRevision { | |
94 | fn from(value: Revision) -> Self { |
|
94 | fn from(value: Revision) -> Self { | |
95 | Self(value.0) |
|
95 | Self(value.0) | |
96 | } |
|
96 | } | |
97 | } |
|
97 | } | |
98 |
|
98 | |||
99 | impl From<BaseRevision> for UncheckedRevision { |
|
99 | impl From<BaseRevision> for UncheckedRevision { | |
100 | fn from(value: BaseRevision) -> Self { |
|
100 | fn from(value: BaseRevision) -> Self { | |
101 | Self(value) |
|
101 | Self(value) | |
102 | } |
|
102 | } | |
103 | } |
|
103 | } | |
104 |
|
104 | |||
105 | /// Marker expressing the absence of a parent |
|
105 | /// Marker expressing the absence of a parent | |
106 | /// |
|
106 | /// | |
107 | /// Independently of the actual representation, `NULL_REVISION` is guaranteed |
|
107 | /// Independently of the actual representation, `NULL_REVISION` is guaranteed | |
108 | /// to be smaller than all existing revisions. |
|
108 | /// to be smaller than all existing revisions. | |
109 | pub const NULL_REVISION: Revision = Revision(-1); |
|
109 | pub const NULL_REVISION: Revision = Revision(-1); | |
110 |
|
110 | |||
111 | /// Same as `mercurial.node.wdirrev` |
|
111 | /// Same as `mercurial.node.wdirrev` | |
112 | /// |
|
112 | /// | |
113 | /// This is also equal to `i32::max_value()`, but it's better to spell |
|
113 | /// This is also equal to `i32::max_value()`, but it's better to spell | |
114 | /// it out explicitely, same as in `mercurial.node` |
|
114 | /// it out explicitely, same as in `mercurial.node` | |
115 | #[allow(clippy::unreadable_literal)] |
|
115 | #[allow(clippy::unreadable_literal)] | |
116 | pub const WORKING_DIRECTORY_REVISION: UncheckedRevision = |
|
116 | pub const WORKING_DIRECTORY_REVISION: UncheckedRevision = | |
117 | UncheckedRevision(0x7fffffff); |
|
117 | UncheckedRevision(0x7fffffff); | |
118 |
|
118 | |||
119 | pub const WORKING_DIRECTORY_HEX: &str = |
|
119 | pub const WORKING_DIRECTORY_HEX: &str = | |
120 | "ffffffffffffffffffffffffffffffffffffffff"; |
|
120 | "ffffffffffffffffffffffffffffffffffffffff"; | |
121 |
|
121 | |||
122 | /// The simplest expression of what we need of Mercurial DAGs. |
|
122 | /// The simplest expression of what we need of Mercurial DAGs. | |
123 | pub trait Graph { |
|
123 | pub trait Graph { | |
124 | /// Return the two parents of the given `Revision`. |
|
124 | /// Return the two parents of the given `Revision`. | |
125 | /// |
|
125 | /// | |
126 | /// Each of the parents can be independently `NULL_REVISION` |
|
126 | /// Each of the parents can be independently `NULL_REVISION` | |
127 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>; |
|
127 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError>; | |
128 | } |
|
128 | } | |
129 |
|
129 | |||
130 | #[derive(Clone, Debug, PartialEq)] |
|
130 | #[derive(Clone, Debug, PartialEq)] | |
131 | pub enum GraphError { |
|
131 | pub enum GraphError { | |
132 | ParentOutOfRange(Revision), |
|
132 | ParentOutOfRange(Revision), | |
133 | } |
|
133 | } | |
134 |
|
134 | |||
|
135 | impl<T: Graph> Graph for &T { | |||
|
136 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |||
|
137 | (*self).parents(rev) | |||
|
138 | } | |||
|
139 | } | |||
|
140 | ||||
135 | /// The Mercurial Revlog Index |
|
141 | /// The Mercurial Revlog Index | |
136 | /// |
|
142 | /// | |
137 | /// This is currently limited to the minimal interface that is needed for |
|
143 | /// This is currently limited to the minimal interface that is needed for | |
138 | /// the [`nodemap`](nodemap/index.html) module |
|
144 | /// the [`nodemap`](nodemap/index.html) module | |
139 | pub trait RevlogIndex { |
|
145 | pub trait RevlogIndex { | |
140 | /// Total number of Revisions referenced in this index |
|
146 | /// Total number of Revisions referenced in this index | |
141 | fn len(&self) -> usize; |
|
147 | fn len(&self) -> usize; | |
142 |
|
148 | |||
143 | fn is_empty(&self) -> bool { |
|
149 | fn is_empty(&self) -> bool { | |
144 | self.len() == 0 |
|
150 | self.len() == 0 | |
145 | } |
|
151 | } | |
146 |
|
152 | |||
147 | /// Return a reference to the Node or `None` for `NULL_REVISION` |
|
153 | /// Return a reference to the Node or `None` for `NULL_REVISION` | |
148 | fn node(&self, rev: Revision) -> Option<&Node>; |
|
154 | fn node(&self, rev: Revision) -> Option<&Node>; | |
149 |
|
155 | |||
150 | /// Return a [`Revision`] if `rev` is a valid revision number for this |
|
156 | /// Return a [`Revision`] if `rev` is a valid revision number for this | |
151 | /// index. |
|
157 | /// index. | |
152 | /// |
|
158 | /// | |
153 | /// [`NULL_REVISION`] is considered to be valid. |
|
159 | /// [`NULL_REVISION`] is considered to be valid. | |
154 | #[inline(always)] |
|
160 | #[inline(always)] | |
155 | fn check_revision(&self, rev: UncheckedRevision) -> Option<Revision> { |
|
161 | fn check_revision(&self, rev: UncheckedRevision) -> Option<Revision> { | |
156 | let rev = rev.0; |
|
162 | let rev = rev.0; | |
157 |
|
163 | |||
158 | if rev == NULL_REVISION.0 || (rev >= 0 && (rev as usize) < self.len()) |
|
164 | if rev == NULL_REVISION.0 || (rev >= 0 && (rev as usize) < self.len()) | |
159 | { |
|
165 | { | |
160 | Some(Revision(rev)) |
|
166 | Some(Revision(rev)) | |
161 | } else { |
|
167 | } else { | |
162 | None |
|
168 | None | |
163 | } |
|
169 | } | |
164 | } |
|
170 | } | |
165 | } |
|
171 | } | |
166 |
|
172 | |||
167 | const REVISION_FLAG_CENSORED: u16 = 1 << 15; |
|
173 | const REVISION_FLAG_CENSORED: u16 = 1 << 15; | |
168 | const REVISION_FLAG_ELLIPSIS: u16 = 1 << 14; |
|
174 | const REVISION_FLAG_ELLIPSIS: u16 = 1 << 14; | |
169 | const REVISION_FLAG_EXTSTORED: u16 = 1 << 13; |
|
175 | const REVISION_FLAG_EXTSTORED: u16 = 1 << 13; | |
170 | const REVISION_FLAG_HASCOPIESINFO: u16 = 1 << 12; |
|
176 | const REVISION_FLAG_HASCOPIESINFO: u16 = 1 << 12; | |
171 |
|
177 | |||
172 | // Keep this in sync with REVIDX_KNOWN_FLAGS in |
|
178 | // Keep this in sync with REVIDX_KNOWN_FLAGS in | |
173 | // mercurial/revlogutils/flagutil.py |
|
179 | // mercurial/revlogutils/flagutil.py | |
174 | const REVIDX_KNOWN_FLAGS: u16 = REVISION_FLAG_CENSORED |
|
180 | const REVIDX_KNOWN_FLAGS: u16 = REVISION_FLAG_CENSORED | |
175 | | REVISION_FLAG_ELLIPSIS |
|
181 | | REVISION_FLAG_ELLIPSIS | |
176 | | REVISION_FLAG_EXTSTORED |
|
182 | | REVISION_FLAG_EXTSTORED | |
177 | | REVISION_FLAG_HASCOPIESINFO; |
|
183 | | REVISION_FLAG_HASCOPIESINFO; | |
178 |
|
184 | |||
179 | const NULL_REVLOG_ENTRY_FLAGS: u16 = 0; |
|
185 | const NULL_REVLOG_ENTRY_FLAGS: u16 = 0; | |
180 |
|
186 | |||
181 | #[derive(Debug, derive_more::From, derive_more::Display)] |
|
187 | #[derive(Debug, derive_more::From, derive_more::Display)] | |
182 | pub enum RevlogError { |
|
188 | pub enum RevlogError { | |
183 | InvalidRevision, |
|
189 | InvalidRevision, | |
184 | /// Working directory is not supported |
|
190 | /// Working directory is not supported | |
185 | WDirUnsupported, |
|
191 | WDirUnsupported, | |
186 | /// Found more than one entry whose ID match the requested prefix |
|
192 | /// Found more than one entry whose ID match the requested prefix | |
187 | AmbiguousPrefix, |
|
193 | AmbiguousPrefix, | |
188 | #[from] |
|
194 | #[from] | |
189 | Other(HgError), |
|
195 | Other(HgError), | |
190 | } |
|
196 | } | |
191 |
|
197 | |||
192 | impl From<NodeMapError> for RevlogError { |
|
198 | impl From<NodeMapError> for RevlogError { | |
193 | fn from(error: NodeMapError) -> Self { |
|
199 | fn from(error: NodeMapError) -> Self { | |
194 | match error { |
|
200 | match error { | |
195 | NodeMapError::MultipleResults => RevlogError::AmbiguousPrefix, |
|
201 | NodeMapError::MultipleResults => RevlogError::AmbiguousPrefix, | |
196 | NodeMapError::RevisionNotInIndex(rev) => RevlogError::corrupted( |
|
202 | NodeMapError::RevisionNotInIndex(rev) => RevlogError::corrupted( | |
197 | format!("nodemap point to revision {} not in index", rev), |
|
203 | format!("nodemap point to revision {} not in index", rev), | |
198 | ), |
|
204 | ), | |
199 | } |
|
205 | } | |
200 | } |
|
206 | } | |
201 | } |
|
207 | } | |
202 |
|
208 | |||
203 | fn corrupted<S: AsRef<str>>(context: S) -> HgError { |
|
209 | fn corrupted<S: AsRef<str>>(context: S) -> HgError { | |
204 | HgError::corrupted(format!("corrupted revlog, {}", context.as_ref())) |
|
210 | HgError::corrupted(format!("corrupted revlog, {}", context.as_ref())) | |
205 | } |
|
211 | } | |
206 |
|
212 | |||
207 | impl RevlogError { |
|
213 | impl RevlogError { | |
208 | fn corrupted<S: AsRef<str>>(context: S) -> Self { |
|
214 | fn corrupted<S: AsRef<str>>(context: S) -> Self { | |
209 | RevlogError::Other(corrupted(context)) |
|
215 | RevlogError::Other(corrupted(context)) | |
210 | } |
|
216 | } | |
211 | } |
|
217 | } | |
212 |
|
218 | |||
213 | /// Read only implementation of revlog. |
|
219 | /// Read only implementation of revlog. | |
214 | pub struct Revlog { |
|
220 | pub struct Revlog { | |
215 | /// When index and data are not interleaved: bytes of the revlog index. |
|
221 | /// When index and data are not interleaved: bytes of the revlog index. | |
216 | /// When index and data are interleaved: bytes of the revlog index and |
|
222 | /// When index and data are interleaved: bytes of the revlog index and | |
217 | /// data. |
|
223 | /// data. | |
218 | index: Index, |
|
224 | index: Index, | |
219 | /// When index and data are not interleaved: bytes of the revlog data |
|
225 | /// When index and data are not interleaved: bytes of the revlog data | |
220 | data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>, |
|
226 | data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>, | |
221 | /// When present on disk: the persistent nodemap for this revlog |
|
227 | /// When present on disk: the persistent nodemap for this revlog | |
222 | nodemap: Option<nodemap::NodeTree>, |
|
228 | nodemap: Option<nodemap::NodeTree>, | |
223 | } |
|
229 | } | |
224 |
|
230 | |||
225 | impl Graph for Revlog { |
|
231 | impl Graph for Revlog { | |
226 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { |
|
232 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |
227 | self.index.parents(rev) |
|
233 | self.index.parents(rev) | |
228 | } |
|
234 | } | |
229 | } |
|
235 | } | |
230 |
|
236 | |||
231 | #[derive(Debug, Copy, Clone)] |
|
237 | #[derive(Debug, Copy, Clone)] | |
232 | pub enum RevlogVersionOptions { |
|
238 | pub enum RevlogVersionOptions { | |
233 | V0, |
|
239 | V0, | |
234 | V1 { generaldelta: bool }, |
|
240 | V1 { generaldelta: bool }, | |
235 | V2, |
|
241 | V2, | |
236 | ChangelogV2 { compute_rank: bool }, |
|
242 | ChangelogV2 { compute_rank: bool }, | |
237 | } |
|
243 | } | |
238 |
|
244 | |||
239 | /// Options to govern how a revlog should be opened, usually from the |
|
245 | /// Options to govern how a revlog should be opened, usually from the | |
240 | /// repository configuration or requirements. |
|
246 | /// repository configuration or requirements. | |
241 | #[derive(Debug, Copy, Clone)] |
|
247 | #[derive(Debug, Copy, Clone)] | |
242 | pub struct RevlogOpenOptions { |
|
248 | pub struct RevlogOpenOptions { | |
243 | /// The revlog version, along with any option specific to this version |
|
249 | /// The revlog version, along with any option specific to this version | |
244 | pub version: RevlogVersionOptions, |
|
250 | pub version: RevlogVersionOptions, | |
245 | /// Whether the revlog uses a persistent nodemap. |
|
251 | /// Whether the revlog uses a persistent nodemap. | |
246 | pub use_nodemap: bool, |
|
252 | pub use_nodemap: bool, | |
247 | // TODO other non-header/version options, |
|
253 | // TODO other non-header/version options, | |
248 | } |
|
254 | } | |
249 |
|
255 | |||
250 | impl RevlogOpenOptions { |
|
256 | impl RevlogOpenOptions { | |
251 | pub fn new() -> Self { |
|
257 | pub fn new() -> Self { | |
252 | Self { |
|
258 | Self { | |
253 | version: RevlogVersionOptions::V1 { generaldelta: true }, |
|
259 | version: RevlogVersionOptions::V1 { generaldelta: true }, | |
254 | use_nodemap: false, |
|
260 | use_nodemap: false, | |
255 | } |
|
261 | } | |
256 | } |
|
262 | } | |
257 |
|
263 | |||
258 | fn default_index_header(&self) -> index::IndexHeader { |
|
264 | fn default_index_header(&self) -> index::IndexHeader { | |
259 | index::IndexHeader { |
|
265 | index::IndexHeader { | |
260 | header_bytes: match self.version { |
|
266 | header_bytes: match self.version { | |
261 | RevlogVersionOptions::V0 => [0, 0, 0, 0], |
|
267 | RevlogVersionOptions::V0 => [0, 0, 0, 0], | |
262 | RevlogVersionOptions::V1 { generaldelta } => { |
|
268 | RevlogVersionOptions::V1 { generaldelta } => { | |
263 | [0, if generaldelta { 3 } else { 1 }, 0, 1] |
|
269 | [0, if generaldelta { 3 } else { 1 }, 0, 1] | |
264 | } |
|
270 | } | |
265 | RevlogVersionOptions::V2 => 0xDEADu32.to_be_bytes(), |
|
271 | RevlogVersionOptions::V2 => 0xDEADu32.to_be_bytes(), | |
266 | RevlogVersionOptions::ChangelogV2 { compute_rank: _ } => { |
|
272 | RevlogVersionOptions::ChangelogV2 { compute_rank: _ } => { | |
267 | 0xD34Du32.to_be_bytes() |
|
273 | 0xD34Du32.to_be_bytes() | |
268 | } |
|
274 | } | |
269 | }, |
|
275 | }, | |
270 | } |
|
276 | } | |
271 | } |
|
277 | } | |
272 | } |
|
278 | } | |
273 |
|
279 | |||
274 | impl Default for RevlogOpenOptions { |
|
280 | impl Default for RevlogOpenOptions { | |
275 | fn default() -> Self { |
|
281 | fn default() -> Self { | |
276 | Self::new() |
|
282 | Self::new() | |
277 | } |
|
283 | } | |
278 | } |
|
284 | } | |
279 |
|
285 | |||
280 | impl Revlog { |
|
286 | impl Revlog { | |
281 | /// Open a revlog index file. |
|
287 | /// Open a revlog index file. | |
282 | /// |
|
288 | /// | |
283 | /// It will also open the associated data file if index and data are not |
|
289 | /// It will also open the associated data file if index and data are not | |
284 | /// interleaved. |
|
290 | /// interleaved. | |
285 | pub fn open( |
|
291 | pub fn open( | |
286 | store_vfs: &Vfs, |
|
292 | store_vfs: &Vfs, | |
287 | index_path: impl AsRef<Path>, |
|
293 | index_path: impl AsRef<Path>, | |
288 | data_path: Option<&Path>, |
|
294 | data_path: Option<&Path>, | |
289 | options: RevlogOpenOptions, |
|
295 | options: RevlogOpenOptions, | |
290 | ) -> Result<Self, HgError> { |
|
296 | ) -> Result<Self, HgError> { | |
291 | Self::open_gen(store_vfs, index_path, data_path, options, None) |
|
297 | Self::open_gen(store_vfs, index_path, data_path, options, None) | |
292 | } |
|
298 | } | |
293 |
|
299 | |||
294 | fn open_gen( |
|
300 | fn open_gen( | |
295 | store_vfs: &Vfs, |
|
301 | store_vfs: &Vfs, | |
296 | index_path: impl AsRef<Path>, |
|
302 | index_path: impl AsRef<Path>, | |
297 | data_path: Option<&Path>, |
|
303 | data_path: Option<&Path>, | |
298 | options: RevlogOpenOptions, |
|
304 | options: RevlogOpenOptions, | |
299 | nodemap_for_test: Option<nodemap::NodeTree>, |
|
305 | nodemap_for_test: Option<nodemap::NodeTree>, | |
300 | ) -> Result<Self, HgError> { |
|
306 | ) -> Result<Self, HgError> { | |
301 | let index_path = index_path.as_ref(); |
|
307 | let index_path = index_path.as_ref(); | |
302 | let index = { |
|
308 | let index = { | |
303 | match store_vfs.mmap_open_opt(index_path)? { |
|
309 | match store_vfs.mmap_open_opt(index_path)? { | |
304 | None => Index::new( |
|
310 | None => Index::new( | |
305 | Box::<Vec<_>>::default(), |
|
311 | Box::<Vec<_>>::default(), | |
306 | options.default_index_header(), |
|
312 | options.default_index_header(), | |
307 | ), |
|
313 | ), | |
308 | Some(index_mmap) => { |
|
314 | Some(index_mmap) => { | |
309 | let index = Index::new( |
|
315 | let index = Index::new( | |
310 | Box::new(index_mmap), |
|
316 | Box::new(index_mmap), | |
311 | options.default_index_header(), |
|
317 | options.default_index_header(), | |
312 | )?; |
|
318 | )?; | |
313 | Ok(index) |
|
319 | Ok(index) | |
314 | } |
|
320 | } | |
315 | } |
|
321 | } | |
316 | }?; |
|
322 | }?; | |
317 |
|
323 | |||
318 | let default_data_path = index_path.with_extension("d"); |
|
324 | let default_data_path = index_path.with_extension("d"); | |
319 |
|
325 | |||
320 | // type annotation required |
|
326 | // type annotation required | |
321 | // won't recognize Mmap as Deref<Target = [u8]> |
|
327 | // won't recognize Mmap as Deref<Target = [u8]> | |
322 | let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> = |
|
328 | let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> = | |
323 | if index.is_inline() { |
|
329 | if index.is_inline() { | |
324 | None |
|
330 | None | |
325 | } else { |
|
331 | } else { | |
326 | let data_path = data_path.unwrap_or(&default_data_path); |
|
332 | let data_path = data_path.unwrap_or(&default_data_path); | |
327 | let data_mmap = store_vfs.mmap_open(data_path)?; |
|
333 | let data_mmap = store_vfs.mmap_open(data_path)?; | |
328 | Some(Box::new(data_mmap)) |
|
334 | Some(Box::new(data_mmap)) | |
329 | }; |
|
335 | }; | |
330 |
|
336 | |||
331 | let nodemap = if index.is_inline() || !options.use_nodemap { |
|
337 | let nodemap = if index.is_inline() || !options.use_nodemap { | |
332 | None |
|
338 | None | |
333 | } else { |
|
339 | } else { | |
334 | NodeMapDocket::read_from_file(store_vfs, index_path)?.map( |
|
340 | NodeMapDocket::read_from_file(store_vfs, index_path)?.map( | |
335 | |(docket, data)| { |
|
341 | |(docket, data)| { | |
336 | nodemap::NodeTree::load_bytes( |
|
342 | nodemap::NodeTree::load_bytes( | |
337 | Box::new(data), |
|
343 | Box::new(data), | |
338 | docket.data_length, |
|
344 | docket.data_length, | |
339 | ) |
|
345 | ) | |
340 | }, |
|
346 | }, | |
341 | ) |
|
347 | ) | |
342 | }; |
|
348 | }; | |
343 |
|
349 | |||
344 | let nodemap = nodemap_for_test.or(nodemap); |
|
350 | let nodemap = nodemap_for_test.or(nodemap); | |
345 |
|
351 | |||
346 | Ok(Revlog { |
|
352 | Ok(Revlog { | |
347 | index, |
|
353 | index, | |
348 | data_bytes, |
|
354 | data_bytes, | |
349 | nodemap, |
|
355 | nodemap, | |
350 | }) |
|
356 | }) | |
351 | } |
|
357 | } | |
352 |
|
358 | |||
353 | /// Return number of entries of the `Revlog`. |
|
359 | /// Return number of entries of the `Revlog`. | |
354 | pub fn len(&self) -> usize { |
|
360 | pub fn len(&self) -> usize { | |
355 | self.index.len() |
|
361 | self.index.len() | |
356 | } |
|
362 | } | |
357 |
|
363 | |||
358 | /// Returns `true` if the `Revlog` has zero `entries`. |
|
364 | /// Returns `true` if the `Revlog` has zero `entries`. | |
359 | pub fn is_empty(&self) -> bool { |
|
365 | pub fn is_empty(&self) -> bool { | |
360 | self.index.is_empty() |
|
366 | self.index.is_empty() | |
361 | } |
|
367 | } | |
362 |
|
368 | |||
363 | /// Returns the node ID for the given revision number, if it exists in this |
|
369 | /// Returns the node ID for the given revision number, if it exists in this | |
364 | /// revlog |
|
370 | /// revlog | |
365 | pub fn node_from_rev(&self, rev: UncheckedRevision) -> Option<&Node> { |
|
371 | pub fn node_from_rev(&self, rev: UncheckedRevision) -> Option<&Node> { | |
366 | if rev == NULL_REVISION.into() { |
|
372 | if rev == NULL_REVISION.into() { | |
367 | return Some(&NULL_NODE); |
|
373 | return Some(&NULL_NODE); | |
368 | } |
|
374 | } | |
369 | let rev = self.index.check_revision(rev)?; |
|
375 | let rev = self.index.check_revision(rev)?; | |
370 | Some(self.index.get_entry(rev)?.hash()) |
|
376 | Some(self.index.get_entry(rev)?.hash()) | |
371 | } |
|
377 | } | |
372 |
|
378 | |||
373 | /// Return the revision number for the given node ID, if it exists in this |
|
379 | /// Return the revision number for the given node ID, if it exists in this | |
374 | /// revlog |
|
380 | /// revlog | |
375 | pub fn rev_from_node( |
|
381 | pub fn rev_from_node( | |
376 | &self, |
|
382 | &self, | |
377 | node: NodePrefix, |
|
383 | node: NodePrefix, | |
378 | ) -> Result<Revision, RevlogError> { |
|
384 | ) -> Result<Revision, RevlogError> { | |
379 | if let Some(nodemap) = &self.nodemap { |
|
385 | if let Some(nodemap) = &self.nodemap { | |
380 | nodemap |
|
386 | nodemap | |
381 | .find_bin(&self.index, node)? |
|
387 | .find_bin(&self.index, node)? | |
382 | .ok_or(RevlogError::InvalidRevision) |
|
388 | .ok_or(RevlogError::InvalidRevision) | |
383 | } else { |
|
389 | } else { | |
384 | self.rev_from_node_no_persistent_nodemap(node) |
|
390 | self.rev_from_node_no_persistent_nodemap(node) | |
385 | } |
|
391 | } | |
386 | } |
|
392 | } | |
387 |
|
393 | |||
388 | /// Same as `rev_from_node`, without using a persistent nodemap |
|
394 | /// Same as `rev_from_node`, without using a persistent nodemap | |
389 | /// |
|
395 | /// | |
390 | /// This is used as fallback when a persistent nodemap is not present. |
|
396 | /// This is used as fallback when a persistent nodemap is not present. | |
391 | /// This happens when the persistent-nodemap experimental feature is not |
|
397 | /// This happens when the persistent-nodemap experimental feature is not | |
392 | /// enabled, or for small revlogs. |
|
398 | /// enabled, or for small revlogs. | |
393 | fn rev_from_node_no_persistent_nodemap( |
|
399 | fn rev_from_node_no_persistent_nodemap( | |
394 | &self, |
|
400 | &self, | |
395 | node: NodePrefix, |
|
401 | node: NodePrefix, | |
396 | ) -> Result<Revision, RevlogError> { |
|
402 | ) -> Result<Revision, RevlogError> { | |
397 | // Linear scan of the revlog |
|
403 | // Linear scan of the revlog | |
398 | // TODO: consider building a non-persistent nodemap in memory to |
|
404 | // TODO: consider building a non-persistent nodemap in memory to | |
399 | // optimize these cases. |
|
405 | // optimize these cases. | |
400 | let mut found_by_prefix = None; |
|
406 | let mut found_by_prefix = None; | |
401 | for rev in (-1..self.len() as BaseRevision).rev() { |
|
407 | for rev in (-1..self.len() as BaseRevision).rev() { | |
402 | let rev = Revision(rev as BaseRevision); |
|
408 | let rev = Revision(rev as BaseRevision); | |
403 | let candidate_node = if rev == Revision(-1) { |
|
409 | let candidate_node = if rev == Revision(-1) { | |
404 | NULL_NODE |
|
410 | NULL_NODE | |
405 | } else { |
|
411 | } else { | |
406 | let index_entry = |
|
412 | let index_entry = | |
407 | self.index.get_entry(rev).ok_or_else(|| { |
|
413 | self.index.get_entry(rev).ok_or_else(|| { | |
408 | HgError::corrupted( |
|
414 | HgError::corrupted( | |
409 | "revlog references a revision not in the index", |
|
415 | "revlog references a revision not in the index", | |
410 | ) |
|
416 | ) | |
411 | })?; |
|
417 | })?; | |
412 | *index_entry.hash() |
|
418 | *index_entry.hash() | |
413 | }; |
|
419 | }; | |
414 | if node == candidate_node { |
|
420 | if node == candidate_node { | |
415 | return Ok(rev); |
|
421 | return Ok(rev); | |
416 | } |
|
422 | } | |
417 | if node.is_prefix_of(&candidate_node) { |
|
423 | if node.is_prefix_of(&candidate_node) { | |
418 | if found_by_prefix.is_some() { |
|
424 | if found_by_prefix.is_some() { | |
419 | return Err(RevlogError::AmbiguousPrefix); |
|
425 | return Err(RevlogError::AmbiguousPrefix); | |
420 | } |
|
426 | } | |
421 | found_by_prefix = Some(rev) |
|
427 | found_by_prefix = Some(rev) | |
422 | } |
|
428 | } | |
423 | } |
|
429 | } | |
424 | found_by_prefix.ok_or(RevlogError::InvalidRevision) |
|
430 | found_by_prefix.ok_or(RevlogError::InvalidRevision) | |
425 | } |
|
431 | } | |
426 |
|
432 | |||
427 | /// Returns whether the given revision exists in this revlog. |
|
433 | /// Returns whether the given revision exists in this revlog. | |
428 | pub fn has_rev(&self, rev: UncheckedRevision) -> bool { |
|
434 | pub fn has_rev(&self, rev: UncheckedRevision) -> bool { | |
429 | self.index.check_revision(rev).is_some() |
|
435 | self.index.check_revision(rev).is_some() | |
430 | } |
|
436 | } | |
431 |
|
437 | |||
432 | /// Return the full data associated to a revision. |
|
438 | /// Return the full data associated to a revision. | |
433 | /// |
|
439 | /// | |
434 | /// All entries required to build the final data out of deltas will be |
|
440 | /// All entries required to build the final data out of deltas will be | |
435 | /// retrieved as needed, and the deltas will be applied to the inital |
|
441 | /// retrieved as needed, and the deltas will be applied to the inital | |
436 | /// snapshot to rebuild the final data. |
|
442 | /// snapshot to rebuild the final data. | |
437 | pub fn get_rev_data( |
|
443 | pub fn get_rev_data( | |
438 | &self, |
|
444 | &self, | |
439 | rev: UncheckedRevision, |
|
445 | rev: UncheckedRevision, | |
440 | ) -> Result<Cow<[u8]>, RevlogError> { |
|
446 | ) -> Result<Cow<[u8]>, RevlogError> { | |
441 | if rev == NULL_REVISION.into() { |
|
447 | if rev == NULL_REVISION.into() { | |
442 | return Ok(Cow::Borrowed(&[])); |
|
448 | return Ok(Cow::Borrowed(&[])); | |
443 | }; |
|
449 | }; | |
444 | self.get_entry(rev)?.data() |
|
450 | self.get_entry(rev)?.data() | |
445 | } |
|
451 | } | |
446 |
|
452 | |||
447 | /// [`Self::get_rev_data`] for checked revisions. |
|
453 | /// [`Self::get_rev_data`] for checked revisions. | |
448 | pub fn get_rev_data_for_checked_rev( |
|
454 | pub fn get_rev_data_for_checked_rev( | |
449 | &self, |
|
455 | &self, | |
450 | rev: Revision, |
|
456 | rev: Revision, | |
451 | ) -> Result<Cow<[u8]>, RevlogError> { |
|
457 | ) -> Result<Cow<[u8]>, RevlogError> { | |
452 | if rev == NULL_REVISION { |
|
458 | if rev == NULL_REVISION { | |
453 | return Ok(Cow::Borrowed(&[])); |
|
459 | return Ok(Cow::Borrowed(&[])); | |
454 | }; |
|
460 | }; | |
455 | self.get_entry_for_checked_rev(rev)?.data() |
|
461 | self.get_entry_for_checked_rev(rev)?.data() | |
456 | } |
|
462 | } | |
457 |
|
463 | |||
458 | /// Check the hash of some given data against the recorded hash. |
|
464 | /// Check the hash of some given data against the recorded hash. | |
459 | pub fn check_hash( |
|
465 | pub fn check_hash( | |
460 | &self, |
|
466 | &self, | |
461 | p1: Revision, |
|
467 | p1: Revision, | |
462 | p2: Revision, |
|
468 | p2: Revision, | |
463 | expected: &[u8], |
|
469 | expected: &[u8], | |
464 | data: &[u8], |
|
470 | data: &[u8], | |
465 | ) -> bool { |
|
471 | ) -> bool { | |
466 | let e1 = self.index.get_entry(p1); |
|
472 | let e1 = self.index.get_entry(p1); | |
467 | let h1 = match e1 { |
|
473 | let h1 = match e1 { | |
468 | Some(ref entry) => entry.hash(), |
|
474 | Some(ref entry) => entry.hash(), | |
469 | None => &NULL_NODE, |
|
475 | None => &NULL_NODE, | |
470 | }; |
|
476 | }; | |
471 | let e2 = self.index.get_entry(p2); |
|
477 | let e2 = self.index.get_entry(p2); | |
472 | let h2 = match e2 { |
|
478 | let h2 = match e2 { | |
473 | Some(ref entry) => entry.hash(), |
|
479 | Some(ref entry) => entry.hash(), | |
474 | None => &NULL_NODE, |
|
480 | None => &NULL_NODE, | |
475 | }; |
|
481 | }; | |
476 |
|
482 | |||
477 | hash(data, h1.as_bytes(), h2.as_bytes()) == expected |
|
483 | hash(data, h1.as_bytes(), h2.as_bytes()) == expected | |
478 | } |
|
484 | } | |
479 |
|
485 | |||
480 | /// Build the full data of a revision out its snapshot |
|
486 | /// Build the full data of a revision out its snapshot | |
481 | /// and its deltas. |
|
487 | /// and its deltas. | |
482 | fn build_data_from_deltas( |
|
488 | fn build_data_from_deltas( | |
483 | snapshot: RevlogEntry, |
|
489 | snapshot: RevlogEntry, | |
484 | deltas: &[RevlogEntry], |
|
490 | deltas: &[RevlogEntry], | |
485 | ) -> Result<Vec<u8>, HgError> { |
|
491 | ) -> Result<Vec<u8>, HgError> { | |
486 | let snapshot = snapshot.data_chunk()?; |
|
492 | let snapshot = snapshot.data_chunk()?; | |
487 | let deltas = deltas |
|
493 | let deltas = deltas | |
488 | .iter() |
|
494 | .iter() | |
489 | .rev() |
|
495 | .rev() | |
490 | .map(RevlogEntry::data_chunk) |
|
496 | .map(RevlogEntry::data_chunk) | |
491 | .collect::<Result<Vec<_>, _>>()?; |
|
497 | .collect::<Result<Vec<_>, _>>()?; | |
492 | let patches: Vec<_> = |
|
498 | let patches: Vec<_> = | |
493 | deltas.iter().map(|d| patch::PatchList::new(d)).collect(); |
|
499 | deltas.iter().map(|d| patch::PatchList::new(d)).collect(); | |
494 | let patch = patch::fold_patch_lists(&patches); |
|
500 | let patch = patch::fold_patch_lists(&patches); | |
495 | Ok(patch.apply(&snapshot)) |
|
501 | Ok(patch.apply(&snapshot)) | |
496 | } |
|
502 | } | |
497 |
|
503 | |||
498 | /// Return the revlog data. |
|
504 | /// Return the revlog data. | |
499 | fn data(&self) -> &[u8] { |
|
505 | fn data(&self) -> &[u8] { | |
500 | match &self.data_bytes { |
|
506 | match &self.data_bytes { | |
501 | Some(data_bytes) => data_bytes, |
|
507 | Some(data_bytes) => data_bytes, | |
502 | None => panic!( |
|
508 | None => panic!( | |
503 | "forgot to load the data or trying to access inline data" |
|
509 | "forgot to load the data or trying to access inline data" | |
504 | ), |
|
510 | ), | |
505 | } |
|
511 | } | |
506 | } |
|
512 | } | |
507 |
|
513 | |||
508 | pub fn make_null_entry(&self) -> RevlogEntry { |
|
514 | pub fn make_null_entry(&self) -> RevlogEntry { | |
509 | RevlogEntry { |
|
515 | RevlogEntry { | |
510 | revlog: self, |
|
516 | revlog: self, | |
511 | rev: NULL_REVISION, |
|
517 | rev: NULL_REVISION, | |
512 | bytes: b"", |
|
518 | bytes: b"", | |
513 | compressed_len: 0, |
|
519 | compressed_len: 0, | |
514 | uncompressed_len: 0, |
|
520 | uncompressed_len: 0, | |
515 | base_rev_or_base_of_delta_chain: None, |
|
521 | base_rev_or_base_of_delta_chain: None, | |
516 | p1: NULL_REVISION, |
|
522 | p1: NULL_REVISION, | |
517 | p2: NULL_REVISION, |
|
523 | p2: NULL_REVISION, | |
518 | flags: NULL_REVLOG_ENTRY_FLAGS, |
|
524 | flags: NULL_REVLOG_ENTRY_FLAGS, | |
519 | hash: NULL_NODE, |
|
525 | hash: NULL_NODE, | |
520 | } |
|
526 | } | |
521 | } |
|
527 | } | |
522 |
|
528 | |||
523 | fn get_entry_for_checked_rev( |
|
529 | fn get_entry_for_checked_rev( | |
524 | &self, |
|
530 | &self, | |
525 | rev: Revision, |
|
531 | rev: Revision, | |
526 | ) -> Result<RevlogEntry, RevlogError> { |
|
532 | ) -> Result<RevlogEntry, RevlogError> { | |
527 | if rev == NULL_REVISION { |
|
533 | if rev == NULL_REVISION { | |
528 | return Ok(self.make_null_entry()); |
|
534 | return Ok(self.make_null_entry()); | |
529 | } |
|
535 | } | |
530 | let index_entry = self |
|
536 | let index_entry = self | |
531 | .index |
|
537 | .index | |
532 | .get_entry(rev) |
|
538 | .get_entry(rev) | |
533 | .ok_or(RevlogError::InvalidRevision)?; |
|
539 | .ok_or(RevlogError::InvalidRevision)?; | |
534 | let start = index_entry.offset(); |
|
540 | let start = index_entry.offset(); | |
535 | let end = start + index_entry.compressed_len() as usize; |
|
541 | let end = start + index_entry.compressed_len() as usize; | |
536 | let data = if self.index.is_inline() { |
|
542 | let data = if self.index.is_inline() { | |
537 | self.index.data(start, end) |
|
543 | self.index.data(start, end) | |
538 | } else { |
|
544 | } else { | |
539 | &self.data()[start..end] |
|
545 | &self.data()[start..end] | |
540 | }; |
|
546 | }; | |
541 | let base_rev = self |
|
547 | let base_rev = self | |
542 | .index |
|
548 | .index | |
543 | .check_revision(index_entry.base_revision_or_base_of_delta_chain()) |
|
549 | .check_revision(index_entry.base_revision_or_base_of_delta_chain()) | |
544 | .ok_or_else(|| { |
|
550 | .ok_or_else(|| { | |
545 | RevlogError::corrupted(format!( |
|
551 | RevlogError::corrupted(format!( | |
546 | "base revision for rev {} is invalid", |
|
552 | "base revision for rev {} is invalid", | |
547 | rev |
|
553 | rev | |
548 | )) |
|
554 | )) | |
549 | })?; |
|
555 | })?; | |
550 | let p1 = |
|
556 | let p1 = | |
551 | self.index.check_revision(index_entry.p1()).ok_or_else(|| { |
|
557 | self.index.check_revision(index_entry.p1()).ok_or_else(|| { | |
552 | RevlogError::corrupted(format!( |
|
558 | RevlogError::corrupted(format!( | |
553 | "p1 for rev {} is invalid", |
|
559 | "p1 for rev {} is invalid", | |
554 | rev |
|
560 | rev | |
555 | )) |
|
561 | )) | |
556 | })?; |
|
562 | })?; | |
557 | let p2 = |
|
563 | let p2 = | |
558 | self.index.check_revision(index_entry.p2()).ok_or_else(|| { |
|
564 | self.index.check_revision(index_entry.p2()).ok_or_else(|| { | |
559 | RevlogError::corrupted(format!( |
|
565 | RevlogError::corrupted(format!( | |
560 | "p2 for rev {} is invalid", |
|
566 | "p2 for rev {} is invalid", | |
561 | rev |
|
567 | rev | |
562 | )) |
|
568 | )) | |
563 | })?; |
|
569 | })?; | |
564 | let entry = RevlogEntry { |
|
570 | let entry = RevlogEntry { | |
565 | revlog: self, |
|
571 | revlog: self, | |
566 | rev, |
|
572 | rev, | |
567 | bytes: data, |
|
573 | bytes: data, | |
568 | compressed_len: index_entry.compressed_len(), |
|
574 | compressed_len: index_entry.compressed_len(), | |
569 | uncompressed_len: index_entry.uncompressed_len(), |
|
575 | uncompressed_len: index_entry.uncompressed_len(), | |
570 | base_rev_or_base_of_delta_chain: if base_rev == rev { |
|
576 | base_rev_or_base_of_delta_chain: if base_rev == rev { | |
571 | None |
|
577 | None | |
572 | } else { |
|
578 | } else { | |
573 | Some(base_rev) |
|
579 | Some(base_rev) | |
574 | }, |
|
580 | }, | |
575 | p1, |
|
581 | p1, | |
576 | p2, |
|
582 | p2, | |
577 | flags: index_entry.flags(), |
|
583 | flags: index_entry.flags(), | |
578 | hash: *index_entry.hash(), |
|
584 | hash: *index_entry.hash(), | |
579 | }; |
|
585 | }; | |
580 | Ok(entry) |
|
586 | Ok(entry) | |
581 | } |
|
587 | } | |
582 |
|
588 | |||
583 | /// Get an entry of the revlog. |
|
589 | /// Get an entry of the revlog. | |
584 | pub fn get_entry( |
|
590 | pub fn get_entry( | |
585 | &self, |
|
591 | &self, | |
586 | rev: UncheckedRevision, |
|
592 | rev: UncheckedRevision, | |
587 | ) -> Result<RevlogEntry, RevlogError> { |
|
593 | ) -> Result<RevlogEntry, RevlogError> { | |
588 | if rev == NULL_REVISION.into() { |
|
594 | if rev == NULL_REVISION.into() { | |
589 | return Ok(self.make_null_entry()); |
|
595 | return Ok(self.make_null_entry()); | |
590 | } |
|
596 | } | |
591 | let rev = self.index.check_revision(rev).ok_or_else(|| { |
|
597 | let rev = self.index.check_revision(rev).ok_or_else(|| { | |
592 | RevlogError::corrupted(format!("rev {} is invalid", rev)) |
|
598 | RevlogError::corrupted(format!("rev {} is invalid", rev)) | |
593 | })?; |
|
599 | })?; | |
594 | self.get_entry_for_checked_rev(rev) |
|
600 | self.get_entry_for_checked_rev(rev) | |
595 | } |
|
601 | } | |
596 | } |
|
602 | } | |
597 |
|
603 | |||
598 | /// The revlog entry's bytes and the necessary informations to extract |
|
604 | /// The revlog entry's bytes and the necessary informations to extract | |
599 | /// the entry's data. |
|
605 | /// the entry's data. | |
600 | #[derive(Clone)] |
|
606 | #[derive(Clone)] | |
601 | pub struct RevlogEntry<'revlog> { |
|
607 | pub struct RevlogEntry<'revlog> { | |
602 | revlog: &'revlog Revlog, |
|
608 | revlog: &'revlog Revlog, | |
603 | rev: Revision, |
|
609 | rev: Revision, | |
604 | bytes: &'revlog [u8], |
|
610 | bytes: &'revlog [u8], | |
605 | compressed_len: u32, |
|
611 | compressed_len: u32, | |
606 | uncompressed_len: i32, |
|
612 | uncompressed_len: i32, | |
607 | base_rev_or_base_of_delta_chain: Option<Revision>, |
|
613 | base_rev_or_base_of_delta_chain: Option<Revision>, | |
608 | p1: Revision, |
|
614 | p1: Revision, | |
609 | p2: Revision, |
|
615 | p2: Revision, | |
610 | flags: u16, |
|
616 | flags: u16, | |
611 | hash: Node, |
|
617 | hash: Node, | |
612 | } |
|
618 | } | |
613 |
|
619 | |||
614 | thread_local! { |
|
620 | thread_local! { | |
615 | // seems fine to [unwrap] here: this can only fail due to memory allocation |
|
621 | // seems fine to [unwrap] here: this can only fail due to memory allocation | |
616 | // failing, and it's normal for that to cause panic. |
|
622 | // failing, and it's normal for that to cause panic. | |
617 | static ZSTD_DECODER : RefCell<zstd::bulk::Decompressor<'static>> = |
|
623 | static ZSTD_DECODER : RefCell<zstd::bulk::Decompressor<'static>> = | |
618 | RefCell::new(zstd::bulk::Decompressor::new().ok().unwrap()); |
|
624 | RefCell::new(zstd::bulk::Decompressor::new().ok().unwrap()); | |
619 | } |
|
625 | } | |
620 |
|
626 | |||
621 | fn zstd_decompress_to_buffer( |
|
627 | fn zstd_decompress_to_buffer( | |
622 | bytes: &[u8], |
|
628 | bytes: &[u8], | |
623 | buf: &mut Vec<u8>, |
|
629 | buf: &mut Vec<u8>, | |
624 | ) -> Result<usize, std::io::Error> { |
|
630 | ) -> Result<usize, std::io::Error> { | |
625 | ZSTD_DECODER |
|
631 | ZSTD_DECODER | |
626 | .with(|decoder| decoder.borrow_mut().decompress_to_buffer(bytes, buf)) |
|
632 | .with(|decoder| decoder.borrow_mut().decompress_to_buffer(bytes, buf)) | |
627 | } |
|
633 | } | |
628 |
|
634 | |||
629 | impl<'revlog> RevlogEntry<'revlog> { |
|
635 | impl<'revlog> RevlogEntry<'revlog> { | |
630 | pub fn revision(&self) -> Revision { |
|
636 | pub fn revision(&self) -> Revision { | |
631 | self.rev |
|
637 | self.rev | |
632 | } |
|
638 | } | |
633 |
|
639 | |||
634 | pub fn node(&self) -> &Node { |
|
640 | pub fn node(&self) -> &Node { | |
635 | &self.hash |
|
641 | &self.hash | |
636 | } |
|
642 | } | |
637 |
|
643 | |||
638 | pub fn uncompressed_len(&self) -> Option<u32> { |
|
644 | pub fn uncompressed_len(&self) -> Option<u32> { | |
639 | u32::try_from(self.uncompressed_len).ok() |
|
645 | u32::try_from(self.uncompressed_len).ok() | |
640 | } |
|
646 | } | |
641 |
|
647 | |||
642 | pub fn has_p1(&self) -> bool { |
|
648 | pub fn has_p1(&self) -> bool { | |
643 | self.p1 != NULL_REVISION |
|
649 | self.p1 != NULL_REVISION | |
644 | } |
|
650 | } | |
645 |
|
651 | |||
646 | pub fn p1_entry( |
|
652 | pub fn p1_entry( | |
647 | &self, |
|
653 | &self, | |
648 | ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> { |
|
654 | ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> { | |
649 | if self.p1 == NULL_REVISION { |
|
655 | if self.p1 == NULL_REVISION { | |
650 | Ok(None) |
|
656 | Ok(None) | |
651 | } else { |
|
657 | } else { | |
652 | Ok(Some(self.revlog.get_entry_for_checked_rev(self.p1)?)) |
|
658 | Ok(Some(self.revlog.get_entry_for_checked_rev(self.p1)?)) | |
653 | } |
|
659 | } | |
654 | } |
|
660 | } | |
655 |
|
661 | |||
656 | pub fn p2_entry( |
|
662 | pub fn p2_entry( | |
657 | &self, |
|
663 | &self, | |
658 | ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> { |
|
664 | ) -> Result<Option<RevlogEntry<'revlog>>, RevlogError> { | |
659 | if self.p2 == NULL_REVISION { |
|
665 | if self.p2 == NULL_REVISION { | |
660 | Ok(None) |
|
666 | Ok(None) | |
661 | } else { |
|
667 | } else { | |
662 | Ok(Some(self.revlog.get_entry_for_checked_rev(self.p2)?)) |
|
668 | Ok(Some(self.revlog.get_entry_for_checked_rev(self.p2)?)) | |
663 | } |
|
669 | } | |
664 | } |
|
670 | } | |
665 |
|
671 | |||
666 | pub fn p1(&self) -> Option<Revision> { |
|
672 | pub fn p1(&self) -> Option<Revision> { | |
667 | if self.p1 == NULL_REVISION { |
|
673 | if self.p1 == NULL_REVISION { | |
668 | None |
|
674 | None | |
669 | } else { |
|
675 | } else { | |
670 | Some(self.p1) |
|
676 | Some(self.p1) | |
671 | } |
|
677 | } | |
672 | } |
|
678 | } | |
673 |
|
679 | |||
674 | pub fn p2(&self) -> Option<Revision> { |
|
680 | pub fn p2(&self) -> Option<Revision> { | |
675 | if self.p2 == NULL_REVISION { |
|
681 | if self.p2 == NULL_REVISION { | |
676 | None |
|
682 | None | |
677 | } else { |
|
683 | } else { | |
678 | Some(self.p2) |
|
684 | Some(self.p2) | |
679 | } |
|
685 | } | |
680 | } |
|
686 | } | |
681 |
|
687 | |||
682 | pub fn is_censored(&self) -> bool { |
|
688 | pub fn is_censored(&self) -> bool { | |
683 | (self.flags & REVISION_FLAG_CENSORED) != 0 |
|
689 | (self.flags & REVISION_FLAG_CENSORED) != 0 | |
684 | } |
|
690 | } | |
685 |
|
691 | |||
686 | pub fn has_length_affecting_flag_processor(&self) -> bool { |
|
692 | pub fn has_length_affecting_flag_processor(&self) -> bool { | |
687 | // Relevant Python code: revlog.size() |
|
693 | // Relevant Python code: revlog.size() | |
688 | // note: ELLIPSIS is known to not change the content |
|
694 | // note: ELLIPSIS is known to not change the content | |
689 | (self.flags & (REVIDX_KNOWN_FLAGS ^ REVISION_FLAG_ELLIPSIS)) != 0 |
|
695 | (self.flags & (REVIDX_KNOWN_FLAGS ^ REVISION_FLAG_ELLIPSIS)) != 0 | |
690 | } |
|
696 | } | |
691 |
|
697 | |||
692 | /// The data for this entry, after resolving deltas if any. |
|
698 | /// The data for this entry, after resolving deltas if any. | |
693 | pub fn rawdata(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> { |
|
699 | pub fn rawdata(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> { | |
694 | let mut entry = self.clone(); |
|
700 | let mut entry = self.clone(); | |
695 | let mut delta_chain = vec![]; |
|
701 | let mut delta_chain = vec![]; | |
696 |
|
702 | |||
697 | // The meaning of `base_rev_or_base_of_delta_chain` depends on |
|
703 | // The meaning of `base_rev_or_base_of_delta_chain` depends on | |
698 | // generaldelta. See the doc on `ENTRY_DELTA_BASE` in |
|
704 | // generaldelta. See the doc on `ENTRY_DELTA_BASE` in | |
699 | // `mercurial/revlogutils/constants.py` and the code in |
|
705 | // `mercurial/revlogutils/constants.py` and the code in | |
700 | // [_chaininfo] and in [index_deltachain]. |
|
706 | // [_chaininfo] and in [index_deltachain]. | |
701 | let uses_generaldelta = self.revlog.index.uses_generaldelta(); |
|
707 | let uses_generaldelta = self.revlog.index.uses_generaldelta(); | |
702 | while let Some(base_rev) = entry.base_rev_or_base_of_delta_chain { |
|
708 | while let Some(base_rev) = entry.base_rev_or_base_of_delta_chain { | |
703 | entry = if uses_generaldelta { |
|
709 | entry = if uses_generaldelta { | |
704 | delta_chain.push(entry); |
|
710 | delta_chain.push(entry); | |
705 | self.revlog.get_entry_for_checked_rev(base_rev)? |
|
711 | self.revlog.get_entry_for_checked_rev(base_rev)? | |
706 | } else { |
|
712 | } else { | |
707 | let base_rev = UncheckedRevision(entry.rev.0 - 1); |
|
713 | let base_rev = UncheckedRevision(entry.rev.0 - 1); | |
708 | delta_chain.push(entry); |
|
714 | delta_chain.push(entry); | |
709 | self.revlog.get_entry(base_rev)? |
|
715 | self.revlog.get_entry(base_rev)? | |
710 | }; |
|
716 | }; | |
711 | } |
|
717 | } | |
712 |
|
718 | |||
713 | let data = if delta_chain.is_empty() { |
|
719 | let data = if delta_chain.is_empty() { | |
714 | entry.data_chunk()? |
|
720 | entry.data_chunk()? | |
715 | } else { |
|
721 | } else { | |
716 | Revlog::build_data_from_deltas(entry, &delta_chain)?.into() |
|
722 | Revlog::build_data_from_deltas(entry, &delta_chain)?.into() | |
717 | }; |
|
723 | }; | |
718 |
|
724 | |||
719 | Ok(data) |
|
725 | Ok(data) | |
720 | } |
|
726 | } | |
721 |
|
727 | |||
722 | fn check_data( |
|
728 | fn check_data( | |
723 | &self, |
|
729 | &self, | |
724 | data: Cow<'revlog, [u8]>, |
|
730 | data: Cow<'revlog, [u8]>, | |
725 | ) -> Result<Cow<'revlog, [u8]>, RevlogError> { |
|
731 | ) -> Result<Cow<'revlog, [u8]>, RevlogError> { | |
726 | if self.revlog.check_hash( |
|
732 | if self.revlog.check_hash( | |
727 | self.p1, |
|
733 | self.p1, | |
728 | self.p2, |
|
734 | self.p2, | |
729 | self.hash.as_bytes(), |
|
735 | self.hash.as_bytes(), | |
730 | &data, |
|
736 | &data, | |
731 | ) { |
|
737 | ) { | |
732 | Ok(data) |
|
738 | Ok(data) | |
733 | } else { |
|
739 | } else { | |
734 | if (self.flags & REVISION_FLAG_ELLIPSIS) != 0 { |
|
740 | if (self.flags & REVISION_FLAG_ELLIPSIS) != 0 { | |
735 | return Err(HgError::unsupported( |
|
741 | return Err(HgError::unsupported( | |
736 | "ellipsis revisions are not supported by rhg", |
|
742 | "ellipsis revisions are not supported by rhg", | |
737 | ) |
|
743 | ) | |
738 | .into()); |
|
744 | .into()); | |
739 | } |
|
745 | } | |
740 | Err(corrupted(format!( |
|
746 | Err(corrupted(format!( | |
741 | "hash check failed for revision {}", |
|
747 | "hash check failed for revision {}", | |
742 | self.rev |
|
748 | self.rev | |
743 | )) |
|
749 | )) | |
744 | .into()) |
|
750 | .into()) | |
745 | } |
|
751 | } | |
746 | } |
|
752 | } | |
747 |
|
753 | |||
748 | pub fn data(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> { |
|
754 | pub fn data(&self) -> Result<Cow<'revlog, [u8]>, RevlogError> { | |
749 | let data = self.rawdata()?; |
|
755 | let data = self.rawdata()?; | |
750 | if self.rev == NULL_REVISION { |
|
756 | if self.rev == NULL_REVISION { | |
751 | return Ok(data); |
|
757 | return Ok(data); | |
752 | } |
|
758 | } | |
753 | if self.is_censored() { |
|
759 | if self.is_censored() { | |
754 | return Err(HgError::CensoredNodeError.into()); |
|
760 | return Err(HgError::CensoredNodeError.into()); | |
755 | } |
|
761 | } | |
756 | self.check_data(data) |
|
762 | self.check_data(data) | |
757 | } |
|
763 | } | |
758 |
|
764 | |||
759 | /// Extract the data contained in the entry. |
|
765 | /// Extract the data contained in the entry. | |
760 | /// This may be a delta. (See `is_delta`.) |
|
766 | /// This may be a delta. (See `is_delta`.) | |
761 | fn data_chunk(&self) -> Result<Cow<'revlog, [u8]>, HgError> { |
|
767 | fn data_chunk(&self) -> Result<Cow<'revlog, [u8]>, HgError> { | |
762 | if self.bytes.is_empty() { |
|
768 | if self.bytes.is_empty() { | |
763 | return Ok(Cow::Borrowed(&[])); |
|
769 | return Ok(Cow::Borrowed(&[])); | |
764 | } |
|
770 | } | |
765 | match self.bytes[0] { |
|
771 | match self.bytes[0] { | |
766 | // Revision data is the entirety of the entry, including this |
|
772 | // Revision data is the entirety of the entry, including this | |
767 | // header. |
|
773 | // header. | |
768 | b'\0' => Ok(Cow::Borrowed(self.bytes)), |
|
774 | b'\0' => Ok(Cow::Borrowed(self.bytes)), | |
769 | // Raw revision data follows. |
|
775 | // Raw revision data follows. | |
770 | b'u' => Ok(Cow::Borrowed(&self.bytes[1..])), |
|
776 | b'u' => Ok(Cow::Borrowed(&self.bytes[1..])), | |
771 | // zlib (RFC 1950) data. |
|
777 | // zlib (RFC 1950) data. | |
772 | b'x' => Ok(Cow::Owned(self.uncompressed_zlib_data()?)), |
|
778 | b'x' => Ok(Cow::Owned(self.uncompressed_zlib_data()?)), | |
773 | // zstd data. |
|
779 | // zstd data. | |
774 | b'\x28' => Ok(Cow::Owned(self.uncompressed_zstd_data()?)), |
|
780 | b'\x28' => Ok(Cow::Owned(self.uncompressed_zstd_data()?)), | |
775 | // A proper new format should have had a repo/store requirement. |
|
781 | // A proper new format should have had a repo/store requirement. | |
776 | format_type => Err(corrupted(format!( |
|
782 | format_type => Err(corrupted(format!( | |
777 | "unknown compression header '{}'", |
|
783 | "unknown compression header '{}'", | |
778 | format_type |
|
784 | format_type | |
779 | ))), |
|
785 | ))), | |
780 | } |
|
786 | } | |
781 | } |
|
787 | } | |
782 |
|
788 | |||
783 | fn uncompressed_zlib_data(&self) -> Result<Vec<u8>, HgError> { |
|
789 | fn uncompressed_zlib_data(&self) -> Result<Vec<u8>, HgError> { | |
784 | let mut decoder = ZlibDecoder::new(self.bytes); |
|
790 | let mut decoder = ZlibDecoder::new(self.bytes); | |
785 | if self.is_delta() { |
|
791 | if self.is_delta() { | |
786 | let mut buf = Vec::with_capacity(self.compressed_len as usize); |
|
792 | let mut buf = Vec::with_capacity(self.compressed_len as usize); | |
787 | decoder |
|
793 | decoder | |
788 | .read_to_end(&mut buf) |
|
794 | .read_to_end(&mut buf) | |
789 | .map_err(|e| corrupted(e.to_string()))?; |
|
795 | .map_err(|e| corrupted(e.to_string()))?; | |
790 | Ok(buf) |
|
796 | Ok(buf) | |
791 | } else { |
|
797 | } else { | |
792 | let cap = self.uncompressed_len.max(0) as usize; |
|
798 | let cap = self.uncompressed_len.max(0) as usize; | |
793 | let mut buf = vec![0; cap]; |
|
799 | let mut buf = vec![0; cap]; | |
794 | decoder |
|
800 | decoder | |
795 | .read_exact(&mut buf) |
|
801 | .read_exact(&mut buf) | |
796 | .map_err(|e| corrupted(e.to_string()))?; |
|
802 | .map_err(|e| corrupted(e.to_string()))?; | |
797 | Ok(buf) |
|
803 | Ok(buf) | |
798 | } |
|
804 | } | |
799 | } |
|
805 | } | |
800 |
|
806 | |||
801 | fn uncompressed_zstd_data(&self) -> Result<Vec<u8>, HgError> { |
|
807 | fn uncompressed_zstd_data(&self) -> Result<Vec<u8>, HgError> { | |
802 | let cap = self.uncompressed_len.max(0) as usize; |
|
808 | let cap = self.uncompressed_len.max(0) as usize; | |
803 | if self.is_delta() { |
|
809 | if self.is_delta() { | |
804 | // [cap] is usually an over-estimate of the space needed because |
|
810 | // [cap] is usually an over-estimate of the space needed because | |
805 | // it's the length of delta-decoded data, but we're interested |
|
811 | // it's the length of delta-decoded data, but we're interested | |
806 | // in the size of the delta. |
|
812 | // in the size of the delta. | |
807 | // This means we have to [shrink_to_fit] to avoid holding on |
|
813 | // This means we have to [shrink_to_fit] to avoid holding on | |
808 | // to a large chunk of memory, but it also means we must have a |
|
814 | // to a large chunk of memory, but it also means we must have a | |
809 | // fallback branch, for the case when the delta is longer than |
|
815 | // fallback branch, for the case when the delta is longer than | |
810 | // the original data (surprisingly, this does happen in practice) |
|
816 | // the original data (surprisingly, this does happen in practice) | |
811 | let mut buf = Vec::with_capacity(cap); |
|
817 | let mut buf = Vec::with_capacity(cap); | |
812 | match zstd_decompress_to_buffer(self.bytes, &mut buf) { |
|
818 | match zstd_decompress_to_buffer(self.bytes, &mut buf) { | |
813 | Ok(_) => buf.shrink_to_fit(), |
|
819 | Ok(_) => buf.shrink_to_fit(), | |
814 | Err(_) => { |
|
820 | Err(_) => { | |
815 | buf.clear(); |
|
821 | buf.clear(); | |
816 | zstd::stream::copy_decode(self.bytes, &mut buf) |
|
822 | zstd::stream::copy_decode(self.bytes, &mut buf) | |
817 | .map_err(|e| corrupted(e.to_string()))?; |
|
823 | .map_err(|e| corrupted(e.to_string()))?; | |
818 | } |
|
824 | } | |
819 | }; |
|
825 | }; | |
820 | Ok(buf) |
|
826 | Ok(buf) | |
821 | } else { |
|
827 | } else { | |
822 | let mut buf = Vec::with_capacity(cap); |
|
828 | let mut buf = Vec::with_capacity(cap); | |
823 | let len = zstd_decompress_to_buffer(self.bytes, &mut buf) |
|
829 | let len = zstd_decompress_to_buffer(self.bytes, &mut buf) | |
824 | .map_err(|e| corrupted(e.to_string()))?; |
|
830 | .map_err(|e| corrupted(e.to_string()))?; | |
825 | if len != self.uncompressed_len as usize { |
|
831 | if len != self.uncompressed_len as usize { | |
826 | Err(corrupted("uncompressed length does not match")) |
|
832 | Err(corrupted("uncompressed length does not match")) | |
827 | } else { |
|
833 | } else { | |
828 | Ok(buf) |
|
834 | Ok(buf) | |
829 | } |
|
835 | } | |
830 | } |
|
836 | } | |
831 | } |
|
837 | } | |
832 |
|
838 | |||
833 | /// Tell if the entry is a snapshot or a delta |
|
839 | /// Tell if the entry is a snapshot or a delta | |
834 | /// (influences on decompression). |
|
840 | /// (influences on decompression). | |
835 | fn is_delta(&self) -> bool { |
|
841 | fn is_delta(&self) -> bool { | |
836 | self.base_rev_or_base_of_delta_chain.is_some() |
|
842 | self.base_rev_or_base_of_delta_chain.is_some() | |
837 | } |
|
843 | } | |
838 | } |
|
844 | } | |
839 |
|
845 | |||
840 | /// Calculate the hash of a revision given its data and its parents. |
|
846 | /// Calculate the hash of a revision given its data and its parents. | |
841 | fn hash( |
|
847 | fn hash( | |
842 | data: &[u8], |
|
848 | data: &[u8], | |
843 | p1_hash: &[u8], |
|
849 | p1_hash: &[u8], | |
844 | p2_hash: &[u8], |
|
850 | p2_hash: &[u8], | |
845 | ) -> [u8; NODE_BYTES_LENGTH] { |
|
851 | ) -> [u8; NODE_BYTES_LENGTH] { | |
846 | let mut hasher = Sha1::new(); |
|
852 | let mut hasher = Sha1::new(); | |
847 | let (a, b) = (p1_hash, p2_hash); |
|
853 | let (a, b) = (p1_hash, p2_hash); | |
848 | if a > b { |
|
854 | if a > b { | |
849 | hasher.update(b); |
|
855 | hasher.update(b); | |
850 | hasher.update(a); |
|
856 | hasher.update(a); | |
851 | } else { |
|
857 | } else { | |
852 | hasher.update(a); |
|
858 | hasher.update(a); | |
853 | hasher.update(b); |
|
859 | hasher.update(b); | |
854 | } |
|
860 | } | |
855 | hasher.update(data); |
|
861 | hasher.update(data); | |
856 | *hasher.finalize().as_ref() |
|
862 | *hasher.finalize().as_ref() | |
857 | } |
|
863 | } | |
858 |
|
864 | |||
859 | #[cfg(test)] |
|
865 | #[cfg(test)] | |
860 | mod tests { |
|
866 | mod tests { | |
861 | use super::*; |
|
867 | use super::*; | |
862 | use crate::index::{IndexEntryBuilder, INDEX_ENTRY_SIZE}; |
|
868 | use crate::index::{IndexEntryBuilder, INDEX_ENTRY_SIZE}; | |
863 | use itertools::Itertools; |
|
869 | use itertools::Itertools; | |
864 |
|
870 | |||
865 | #[test] |
|
871 | #[test] | |
866 | fn test_empty() { |
|
872 | fn test_empty() { | |
867 | let temp = tempfile::tempdir().unwrap(); |
|
873 | let temp = tempfile::tempdir().unwrap(); | |
868 | let vfs = Vfs { base: temp.path() }; |
|
874 | let vfs = Vfs { base: temp.path() }; | |
869 | std::fs::write(temp.path().join("foo.i"), b"").unwrap(); |
|
875 | std::fs::write(temp.path().join("foo.i"), b"").unwrap(); | |
870 | let revlog = |
|
876 | let revlog = | |
871 | Revlog::open(&vfs, "foo.i", None, RevlogOpenOptions::new()) |
|
877 | Revlog::open(&vfs, "foo.i", None, RevlogOpenOptions::new()) | |
872 | .unwrap(); |
|
878 | .unwrap(); | |
873 | assert!(revlog.is_empty()); |
|
879 | assert!(revlog.is_empty()); | |
874 | assert_eq!(revlog.len(), 0); |
|
880 | assert_eq!(revlog.len(), 0); | |
875 | assert!(revlog.get_entry(0.into()).is_err()); |
|
881 | assert!(revlog.get_entry(0.into()).is_err()); | |
876 | assert!(!revlog.has_rev(0.into())); |
|
882 | assert!(!revlog.has_rev(0.into())); | |
877 | assert_eq!( |
|
883 | assert_eq!( | |
878 | revlog.rev_from_node(NULL_NODE.into()).unwrap(), |
|
884 | revlog.rev_from_node(NULL_NODE.into()).unwrap(), | |
879 | NULL_REVISION |
|
885 | NULL_REVISION | |
880 | ); |
|
886 | ); | |
881 | let null_entry = revlog.get_entry(NULL_REVISION.into()).ok().unwrap(); |
|
887 | let null_entry = revlog.get_entry(NULL_REVISION.into()).ok().unwrap(); | |
882 | assert_eq!(null_entry.revision(), NULL_REVISION); |
|
888 | assert_eq!(null_entry.revision(), NULL_REVISION); | |
883 | assert!(null_entry.data().unwrap().is_empty()); |
|
889 | assert!(null_entry.data().unwrap().is_empty()); | |
884 | } |
|
890 | } | |
885 |
|
891 | |||
886 | #[test] |
|
892 | #[test] | |
887 | fn test_inline() { |
|
893 | fn test_inline() { | |
888 | let temp = tempfile::tempdir().unwrap(); |
|
894 | let temp = tempfile::tempdir().unwrap(); | |
889 | let vfs = Vfs { base: temp.path() }; |
|
895 | let vfs = Vfs { base: temp.path() }; | |
890 | let node0 = Node::from_hex("2ed2a3912a0b24502043eae84ee4b279c18b90dd") |
|
896 | let node0 = Node::from_hex("2ed2a3912a0b24502043eae84ee4b279c18b90dd") | |
891 | .unwrap(); |
|
897 | .unwrap(); | |
892 | let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12") |
|
898 | let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12") | |
893 | .unwrap(); |
|
899 | .unwrap(); | |
894 | let node2 = Node::from_hex("dd6ad206e907be60927b5a3117b97dffb2590582") |
|
900 | let node2 = Node::from_hex("dd6ad206e907be60927b5a3117b97dffb2590582") | |
895 | .unwrap(); |
|
901 | .unwrap(); | |
896 | let entry0_bytes = IndexEntryBuilder::new() |
|
902 | let entry0_bytes = IndexEntryBuilder::new() | |
897 | .is_first(true) |
|
903 | .is_first(true) | |
898 | .with_version(1) |
|
904 | .with_version(1) | |
899 | .with_inline(true) |
|
905 | .with_inline(true) | |
900 | .with_offset(INDEX_ENTRY_SIZE) |
|
906 | .with_offset(INDEX_ENTRY_SIZE) | |
901 | .with_node(node0) |
|
907 | .with_node(node0) | |
902 | .build(); |
|
908 | .build(); | |
903 | let entry1_bytes = IndexEntryBuilder::new() |
|
909 | let entry1_bytes = IndexEntryBuilder::new() | |
904 | .with_offset(INDEX_ENTRY_SIZE) |
|
910 | .with_offset(INDEX_ENTRY_SIZE) | |
905 | .with_node(node1) |
|
911 | .with_node(node1) | |
906 | .build(); |
|
912 | .build(); | |
907 | let entry2_bytes = IndexEntryBuilder::new() |
|
913 | let entry2_bytes = IndexEntryBuilder::new() | |
908 | .with_offset(INDEX_ENTRY_SIZE) |
|
914 | .with_offset(INDEX_ENTRY_SIZE) | |
909 | .with_p1(Revision(0)) |
|
915 | .with_p1(Revision(0)) | |
910 | .with_p2(Revision(1)) |
|
916 | .with_p2(Revision(1)) | |
911 | .with_node(node2) |
|
917 | .with_node(node2) | |
912 | .build(); |
|
918 | .build(); | |
913 | let contents = vec![entry0_bytes, entry1_bytes, entry2_bytes] |
|
919 | let contents = vec![entry0_bytes, entry1_bytes, entry2_bytes] | |
914 | .into_iter() |
|
920 | .into_iter() | |
915 | .flatten() |
|
921 | .flatten() | |
916 | .collect_vec(); |
|
922 | .collect_vec(); | |
917 | std::fs::write(temp.path().join("foo.i"), contents).unwrap(); |
|
923 | std::fs::write(temp.path().join("foo.i"), contents).unwrap(); | |
918 | let revlog = |
|
924 | let revlog = | |
919 | Revlog::open(&vfs, "foo.i", None, RevlogOpenOptions::new()) |
|
925 | Revlog::open(&vfs, "foo.i", None, RevlogOpenOptions::new()) | |
920 | .unwrap(); |
|
926 | .unwrap(); | |
921 |
|
927 | |||
922 | let entry0 = revlog.get_entry(0.into()).ok().unwrap(); |
|
928 | let entry0 = revlog.get_entry(0.into()).ok().unwrap(); | |
923 | assert_eq!(entry0.revision(), Revision(0)); |
|
929 | assert_eq!(entry0.revision(), Revision(0)); | |
924 | assert_eq!(*entry0.node(), node0); |
|
930 | assert_eq!(*entry0.node(), node0); | |
925 | assert!(!entry0.has_p1()); |
|
931 | assert!(!entry0.has_p1()); | |
926 | assert_eq!(entry0.p1(), None); |
|
932 | assert_eq!(entry0.p1(), None); | |
927 | assert_eq!(entry0.p2(), None); |
|
933 | assert_eq!(entry0.p2(), None); | |
928 | let p1_entry = entry0.p1_entry().unwrap(); |
|
934 | let p1_entry = entry0.p1_entry().unwrap(); | |
929 | assert!(p1_entry.is_none()); |
|
935 | assert!(p1_entry.is_none()); | |
930 | let p2_entry = entry0.p2_entry().unwrap(); |
|
936 | let p2_entry = entry0.p2_entry().unwrap(); | |
931 | assert!(p2_entry.is_none()); |
|
937 | assert!(p2_entry.is_none()); | |
932 |
|
938 | |||
933 | let entry1 = revlog.get_entry(1.into()).ok().unwrap(); |
|
939 | let entry1 = revlog.get_entry(1.into()).ok().unwrap(); | |
934 | assert_eq!(entry1.revision(), Revision(1)); |
|
940 | assert_eq!(entry1.revision(), Revision(1)); | |
935 | assert_eq!(*entry1.node(), node1); |
|
941 | assert_eq!(*entry1.node(), node1); | |
936 | assert!(!entry1.has_p1()); |
|
942 | assert!(!entry1.has_p1()); | |
937 | assert_eq!(entry1.p1(), None); |
|
943 | assert_eq!(entry1.p1(), None); | |
938 | assert_eq!(entry1.p2(), None); |
|
944 | assert_eq!(entry1.p2(), None); | |
939 | let p1_entry = entry1.p1_entry().unwrap(); |
|
945 | let p1_entry = entry1.p1_entry().unwrap(); | |
940 | assert!(p1_entry.is_none()); |
|
946 | assert!(p1_entry.is_none()); | |
941 | let p2_entry = entry1.p2_entry().unwrap(); |
|
947 | let p2_entry = entry1.p2_entry().unwrap(); | |
942 | assert!(p2_entry.is_none()); |
|
948 | assert!(p2_entry.is_none()); | |
943 |
|
949 | |||
944 | let entry2 = revlog.get_entry(2.into()).ok().unwrap(); |
|
950 | let entry2 = revlog.get_entry(2.into()).ok().unwrap(); | |
945 | assert_eq!(entry2.revision(), Revision(2)); |
|
951 | assert_eq!(entry2.revision(), Revision(2)); | |
946 | assert_eq!(*entry2.node(), node2); |
|
952 | assert_eq!(*entry2.node(), node2); | |
947 | assert!(entry2.has_p1()); |
|
953 | assert!(entry2.has_p1()); | |
948 | assert_eq!(entry2.p1(), Some(Revision(0))); |
|
954 | assert_eq!(entry2.p1(), Some(Revision(0))); | |
949 | assert_eq!(entry2.p2(), Some(Revision(1))); |
|
955 | assert_eq!(entry2.p2(), Some(Revision(1))); | |
950 | let p1_entry = entry2.p1_entry().unwrap(); |
|
956 | let p1_entry = entry2.p1_entry().unwrap(); | |
951 | assert!(p1_entry.is_some()); |
|
957 | assert!(p1_entry.is_some()); | |
952 | assert_eq!(p1_entry.unwrap().revision(), Revision(0)); |
|
958 | assert_eq!(p1_entry.unwrap().revision(), Revision(0)); | |
953 | let p2_entry = entry2.p2_entry().unwrap(); |
|
959 | let p2_entry = entry2.p2_entry().unwrap(); | |
954 | assert!(p2_entry.is_some()); |
|
960 | assert!(p2_entry.is_some()); | |
955 | assert_eq!(p2_entry.unwrap().revision(), Revision(1)); |
|
961 | assert_eq!(p2_entry.unwrap().revision(), Revision(1)); | |
956 | } |
|
962 | } | |
957 |
|
963 | |||
958 | #[test] |
|
964 | #[test] | |
959 | fn test_nodemap() { |
|
965 | fn test_nodemap() { | |
960 | let temp = tempfile::tempdir().unwrap(); |
|
966 | let temp = tempfile::tempdir().unwrap(); | |
961 | let vfs = Vfs { base: temp.path() }; |
|
967 | let vfs = Vfs { base: temp.path() }; | |
962 |
|
968 | |||
963 | // building a revlog with a forced Node starting with zeros |
|
969 | // building a revlog with a forced Node starting with zeros | |
964 | // This is a corruption, but it does not preclude using the nodemap |
|
970 | // This is a corruption, but it does not preclude using the nodemap | |
965 | // if we don't try and access the data |
|
971 | // if we don't try and access the data | |
966 | let node0 = Node::from_hex("00d2a3912a0b24502043eae84ee4b279c18b90dd") |
|
972 | let node0 = Node::from_hex("00d2a3912a0b24502043eae84ee4b279c18b90dd") | |
967 | .unwrap(); |
|
973 | .unwrap(); | |
968 | let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12") |
|
974 | let node1 = Node::from_hex("b004912a8510032a0350a74daa2803dadfb00e12") | |
969 | .unwrap(); |
|
975 | .unwrap(); | |
970 | let entry0_bytes = IndexEntryBuilder::new() |
|
976 | let entry0_bytes = IndexEntryBuilder::new() | |
971 | .is_first(true) |
|
977 | .is_first(true) | |
972 | .with_version(1) |
|
978 | .with_version(1) | |
973 | .with_inline(true) |
|
979 | .with_inline(true) | |
974 | .with_offset(INDEX_ENTRY_SIZE) |
|
980 | .with_offset(INDEX_ENTRY_SIZE) | |
975 | .with_node(node0) |
|
981 | .with_node(node0) | |
976 | .build(); |
|
982 | .build(); | |
977 | let entry1_bytes = IndexEntryBuilder::new() |
|
983 | let entry1_bytes = IndexEntryBuilder::new() | |
978 | .with_offset(INDEX_ENTRY_SIZE) |
|
984 | .with_offset(INDEX_ENTRY_SIZE) | |
979 | .with_node(node1) |
|
985 | .with_node(node1) | |
980 | .build(); |
|
986 | .build(); | |
981 | let contents = vec![entry0_bytes, entry1_bytes] |
|
987 | let contents = vec![entry0_bytes, entry1_bytes] | |
982 | .into_iter() |
|
988 | .into_iter() | |
983 | .flatten() |
|
989 | .flatten() | |
984 | .collect_vec(); |
|
990 | .collect_vec(); | |
985 | std::fs::write(temp.path().join("foo.i"), contents).unwrap(); |
|
991 | std::fs::write(temp.path().join("foo.i"), contents).unwrap(); | |
986 |
|
992 | |||
987 | let mut idx = nodemap::tests::TestNtIndex::new(); |
|
993 | let mut idx = nodemap::tests::TestNtIndex::new(); | |
988 | idx.insert_node(Revision(0), node0).unwrap(); |
|
994 | idx.insert_node(Revision(0), node0).unwrap(); | |
989 | idx.insert_node(Revision(1), node1).unwrap(); |
|
995 | idx.insert_node(Revision(1), node1).unwrap(); | |
990 |
|
996 | |||
991 | let revlog = Revlog::open_gen( |
|
997 | let revlog = Revlog::open_gen( | |
992 | &vfs, |
|
998 | &vfs, | |
993 | "foo.i", |
|
999 | "foo.i", | |
994 | None, |
|
1000 | None, | |
995 | RevlogOpenOptions::new(), |
|
1001 | RevlogOpenOptions::new(), | |
996 | Some(idx.nt), |
|
1002 | Some(idx.nt), | |
997 | ) |
|
1003 | ) | |
998 | .unwrap(); |
|
1004 | .unwrap(); | |
999 |
|
1005 | |||
1000 | // accessing the data shows the corruption |
|
1006 | // accessing the data shows the corruption | |
1001 | revlog.get_entry(0.into()).unwrap().data().unwrap_err(); |
|
1007 | revlog.get_entry(0.into()).unwrap().data().unwrap_err(); | |
1002 |
|
1008 | |||
1003 | assert_eq!( |
|
1009 | assert_eq!( | |
1004 | revlog.rev_from_node(NULL_NODE.into()).unwrap(), |
|
1010 | revlog.rev_from_node(NULL_NODE.into()).unwrap(), | |
1005 | Revision(-1) |
|
1011 | Revision(-1) | |
1006 | ); |
|
1012 | ); | |
1007 | assert_eq!(revlog.rev_from_node(node0.into()).unwrap(), Revision(0)); |
|
1013 | assert_eq!(revlog.rev_from_node(node0.into()).unwrap(), Revision(0)); | |
1008 | assert_eq!(revlog.rev_from_node(node1.into()).unwrap(), Revision(1)); |
|
1014 | assert_eq!(revlog.rev_from_node(node1.into()).unwrap(), Revision(1)); | |
1009 | assert_eq!( |
|
1015 | assert_eq!( | |
1010 | revlog |
|
1016 | revlog | |
1011 | .rev_from_node(NodePrefix::from_hex("000").unwrap()) |
|
1017 | .rev_from_node(NodePrefix::from_hex("000").unwrap()) | |
1012 | .unwrap(), |
|
1018 | .unwrap(), | |
1013 | Revision(-1) |
|
1019 | Revision(-1) | |
1014 | ); |
|
1020 | ); | |
1015 | assert_eq!( |
|
1021 | assert_eq!( | |
1016 | revlog |
|
1022 | revlog | |
1017 | .rev_from_node(NodePrefix::from_hex("b00").unwrap()) |
|
1023 | .rev_from_node(NodePrefix::from_hex("b00").unwrap()) | |
1018 | .unwrap(), |
|
1024 | .unwrap(), | |
1019 | Revision(1) |
|
1025 | Revision(1) | |
1020 | ); |
|
1026 | ); | |
1021 | // RevlogError does not implement PartialEq |
|
1027 | // RevlogError does not implement PartialEq | |
1022 | // (ultimately because io::Error does not) |
|
1028 | // (ultimately because io::Error does not) | |
1023 | match revlog |
|
1029 | match revlog | |
1024 | .rev_from_node(NodePrefix::from_hex("00").unwrap()) |
|
1030 | .rev_from_node(NodePrefix::from_hex("00").unwrap()) | |
1025 | .expect_err("Expected to give AmbiguousPrefix error") |
|
1031 | .expect_err("Expected to give AmbiguousPrefix error") | |
1026 | { |
|
1032 | { | |
1027 | RevlogError::AmbiguousPrefix => (), |
|
1033 | RevlogError::AmbiguousPrefix => (), | |
1028 | e => { |
|
1034 | e => { | |
1029 | panic!("Got another error than AmbiguousPrefix: {:?}", e); |
|
1035 | panic!("Got another error than AmbiguousPrefix: {:?}", e); | |
1030 | } |
|
1036 | } | |
1031 | }; |
|
1037 | }; | |
1032 | } |
|
1038 | } | |
1033 | } |
|
1039 | } |
General Comments 0
You need to be logged in to leave comments.
Login now