Show More
@@ -0,0 +1,355 b'' | |||
|
1 | // dirs_multiset.rs | |
|
2 | // | |
|
3 | // Copyright 2019 Raphaël Gomès <rgomes@octobus.net> | |
|
4 | // | |
|
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. | |
|
7 | ||
|
8 | //! A multiset of directory names. | |
|
9 | //! | |
|
10 | //! Used to counts the references to directories in a manifest or dirstate. | |
|
11 | use std::collections::hash_map::Entry; | |
|
12 | use std::collections::HashMap; | |
|
13 | use std::ops::Deref; | |
|
14 | use {DirsIterable, DirstateEntry, DirstateMapError}; | |
|
15 | ||
|
16 | #[derive(PartialEq, Debug)] | |
|
17 | pub struct DirsMultiset { | |
|
18 | inner: HashMap<Vec<u8>, u32>, | |
|
19 | } | |
|
20 | ||
|
21 | impl Deref for DirsMultiset { | |
|
22 | type Target = HashMap<Vec<u8>, u32>; | |
|
23 | ||
|
24 | fn deref(&self) -> &Self::Target { | |
|
25 | &self.inner | |
|
26 | } | |
|
27 | } | |
|
28 | ||
|
29 | impl DirsMultiset { | |
|
30 | /// Initializes the multiset from a dirstate or a manifest. | |
|
31 | /// | |
|
32 | /// If `skip_state` is provided, skips dirstate entries with equal state. | |
|
33 | pub fn new(iterable: DirsIterable, skip_state: Option<i8>) -> Self { | |
|
34 | let mut multiset = DirsMultiset { | |
|
35 | inner: HashMap::new(), | |
|
36 | }; | |
|
37 | ||
|
38 | match iterable { | |
|
39 | DirsIterable::Dirstate(vec) => { | |
|
40 | for (ref filename, DirstateEntry { state, .. }) in vec { | |
|
41 | // This `if` is optimized out of the loop | |
|
42 | if let Some(skip) = skip_state { | |
|
43 | if skip != state { | |
|
44 | multiset.add_path(filename); | |
|
45 | } | |
|
46 | } else { | |
|
47 | multiset.add_path(filename); | |
|
48 | } | |
|
49 | } | |
|
50 | } | |
|
51 | DirsIterable::Manifest(vec) => { | |
|
52 | for ref filename in vec { | |
|
53 | multiset.add_path(filename); | |
|
54 | } | |
|
55 | } | |
|
56 | } | |
|
57 | ||
|
58 | multiset | |
|
59 | } | |
|
60 | ||
|
61 | /// Returns the slice up to the next directory name from right to left, | |
|
62 | /// without trailing slash | |
|
63 | fn find_dir(path: &[u8]) -> &[u8] { | |
|
64 | let mut path = path; | |
|
65 | loop { | |
|
66 | if let Some(new_pos) = path.len().checked_sub(1) { | |
|
67 | if path[new_pos] == b'/' { | |
|
68 | break &path[..new_pos]; | |
|
69 | } | |
|
70 | path = &path[..new_pos]; | |
|
71 | } else { | |
|
72 | break &[]; | |
|
73 | } | |
|
74 | } | |
|
75 | } | |
|
76 | ||
|
77 | /// Increases the count of deepest directory contained in the path. | |
|
78 | /// | |
|
79 | /// If the directory is not yet in the map, adds its parents. | |
|
80 | pub fn add_path(&mut self, path: &[u8]) { | |
|
81 | let mut pos = path.len(); | |
|
82 | ||
|
83 | loop { | |
|
84 | let subpath = Self::find_dir(&path[..pos]); | |
|
85 | if let Some(val) = self.inner.get_mut(subpath) { | |
|
86 | *val += 1; | |
|
87 | break; | |
|
88 | } | |
|
89 | self.inner.insert(subpath.to_owned(), 1); | |
|
90 | ||
|
91 | pos = subpath.len(); | |
|
92 | if pos == 0 { | |
|
93 | break; | |
|
94 | } | |
|
95 | } | |
|
96 | } | |
|
97 | ||
|
98 | /// Decreases the count of deepest directory contained in the path. | |
|
99 | /// | |
|
100 | /// If it is the only reference, decreases all parents until one is | |
|
101 | /// removed. | |
|
102 | /// If the directory is not in the map, something horrible has happened. | |
|
103 | pub fn delete_path( | |
|
104 | &mut self, | |
|
105 | path: &[u8], | |
|
106 | ) -> Result<(), DirstateMapError> { | |
|
107 | let mut pos = path.len(); | |
|
108 | ||
|
109 | loop { | |
|
110 | let subpath = Self::find_dir(&path[..pos]); | |
|
111 | match self.inner.entry(subpath.to_owned()) { | |
|
112 | Entry::Occupied(mut entry) => { | |
|
113 | let val = entry.get().clone(); | |
|
114 | if val > 1 { | |
|
115 | entry.insert(val - 1); | |
|
116 | break; | |
|
117 | } | |
|
118 | entry.remove(); | |
|
119 | } | |
|
120 | Entry::Vacant(_) => { | |
|
121 | return Err(DirstateMapError::PathNotFound(path.to_owned())) | |
|
122 | } | |
|
123 | }; | |
|
124 | ||
|
125 | pos = subpath.len(); | |
|
126 | if pos == 0 { | |
|
127 | break; | |
|
128 | } | |
|
129 | } | |
|
130 | ||
|
131 | Ok(()) | |
|
132 | } | |
|
133 | } | |
|
134 | ||
|
135 | #[cfg(test)] | |
|
136 | mod tests { | |
|
137 | use super::*; | |
|
138 | ||
|
139 | #[test] | |
|
140 | fn test_delete_path_path_not_found() { | |
|
141 | let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None); | |
|
142 | let path = b"doesnotexist/"; | |
|
143 | assert_eq!( | |
|
144 | Err(DirstateMapError::PathNotFound(path.to_vec())), | |
|
145 | map.delete_path(path) | |
|
146 | ); | |
|
147 | } | |
|
148 | ||
|
149 | #[test] | |
|
150 | fn test_delete_path_empty_path() { | |
|
151 | let mut map = | |
|
152 | DirsMultiset::new(DirsIterable::Manifest(vec![vec![]]), None); | |
|
153 | let path = b""; | |
|
154 | assert_eq!(Ok(()), map.delete_path(path)); | |
|
155 | assert_eq!( | |
|
156 | Err(DirstateMapError::PathNotFound(path.to_vec())), | |
|
157 | map.delete_path(path) | |
|
158 | ); | |
|
159 | } | |
|
160 | ||
|
161 | #[test] | |
|
162 | fn test_delete_path_successful() { | |
|
163 | let mut map = DirsMultiset { | |
|
164 | inner: [("", 5), ("a", 3), ("a/b", 2), ("a/c", 1)] | |
|
165 | .iter() | |
|
166 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
167 | .collect(), | |
|
168 | }; | |
|
169 | ||
|
170 | assert_eq!(Ok(()), map.delete_path(b"a/b/")); | |
|
171 | assert_eq!(Ok(()), map.delete_path(b"a/b/")); | |
|
172 | assert_eq!( | |
|
173 | Err(DirstateMapError::PathNotFound(b"a/b/".to_vec())), | |
|
174 | map.delete_path(b"a/b/") | |
|
175 | ); | |
|
176 | ||
|
177 | assert_eq!(2, *map.get(&b"a".to_vec()).unwrap()); | |
|
178 | assert_eq!(1, *map.get(&b"a/c".to_vec()).unwrap()); | |
|
179 | eprintln!("{:?}", map); | |
|
180 | assert_eq!(Ok(()), map.delete_path(b"a/")); | |
|
181 | eprintln!("{:?}", map); | |
|
182 | ||
|
183 | assert_eq!(Ok(()), map.delete_path(b"a/c/")); | |
|
184 | assert_eq!( | |
|
185 | Err(DirstateMapError::PathNotFound(b"a/c/".to_vec())), | |
|
186 | map.delete_path(b"a/c/") | |
|
187 | ); | |
|
188 | } | |
|
189 | ||
|
190 | #[test] | |
|
191 | fn test_add_path_empty_path() { | |
|
192 | let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None); | |
|
193 | let path = b""; | |
|
194 | map.add_path(path); | |
|
195 | ||
|
196 | assert_eq!(1, map.len()); | |
|
197 | } | |
|
198 | ||
|
199 | #[test] | |
|
200 | fn test_add_path_successful() { | |
|
201 | let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None); | |
|
202 | ||
|
203 | map.add_path(b"a/"); | |
|
204 | assert_eq!(1, *map.get(&b"a".to_vec()).unwrap()); | |
|
205 | assert_eq!(1, *map.get(&Vec::new()).unwrap()); | |
|
206 | assert_eq!(2, map.len()); | |
|
207 | ||
|
208 | // Non directory should be ignored | |
|
209 | map.add_path(b"a"); | |
|
210 | assert_eq!(1, *map.get(&b"a".to_vec()).unwrap()); | |
|
211 | assert_eq!(2, map.len()); | |
|
212 | ||
|
213 | // Non directory will still add its base | |
|
214 | map.add_path(b"a/b"); | |
|
215 | assert_eq!(2, *map.get(&b"a".to_vec()).unwrap()); | |
|
216 | assert_eq!(2, map.len()); | |
|
217 | ||
|
218 | // Duplicate path works | |
|
219 | map.add_path(b"a/"); | |
|
220 | assert_eq!(3, *map.get(&b"a".to_vec()).unwrap()); | |
|
221 | ||
|
222 | // Nested dir adds to its base | |
|
223 | map.add_path(b"a/b/"); | |
|
224 | assert_eq!(4, *map.get(&b"a".to_vec()).unwrap()); | |
|
225 | assert_eq!(1, *map.get(&b"a/b".to_vec()).unwrap()); | |
|
226 | ||
|
227 | // but not its base's base, because it already existed | |
|
228 | map.add_path(b"a/b/c/"); | |
|
229 | assert_eq!(4, *map.get(&b"a".to_vec()).unwrap()); | |
|
230 | assert_eq!(2, *map.get(&b"a/b".to_vec()).unwrap()); | |
|
231 | ||
|
232 | map.add_path(b"a/c/"); | |
|
233 | assert_eq!(1, *map.get(&b"a/c".to_vec()).unwrap()); | |
|
234 | ||
|
235 | let expected = DirsMultiset { | |
|
236 | inner: [("", 2), ("a", 5), ("a/b", 2), ("a/b/c", 1), ("a/c", 1)] | |
|
237 | .iter() | |
|
238 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
239 | .collect(), | |
|
240 | }; | |
|
241 | assert_eq!(map, expected); | |
|
242 | } | |
|
243 | ||
|
244 | #[test] | |
|
245 | fn test_dirsmultiset_new_empty() { | |
|
246 | use DirsIterable::{Dirstate, Manifest}; | |
|
247 | ||
|
248 | let new = DirsMultiset::new(Manifest(vec![]), None); | |
|
249 | let expected = DirsMultiset { | |
|
250 | inner: HashMap::new(), | |
|
251 | }; | |
|
252 | assert_eq!(expected, new); | |
|
253 | ||
|
254 | let new = DirsMultiset::new(Dirstate(vec![]), None); | |
|
255 | let expected = DirsMultiset { | |
|
256 | inner: HashMap::new(), | |
|
257 | }; | |
|
258 | assert_eq!(expected, new); | |
|
259 | } | |
|
260 | ||
|
261 | #[test] | |
|
262 | fn test_dirsmultiset_new_no_skip() { | |
|
263 | use DirsIterable::{Dirstate, Manifest}; | |
|
264 | ||
|
265 | let input_vec = ["a/", "b/", "a/c", "a/d/"] | |
|
266 | .iter() | |
|
267 | .map(|e| e.as_bytes().to_vec()) | |
|
268 | .collect(); | |
|
269 | let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)] | |
|
270 | .iter() | |
|
271 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
272 | .collect(); | |
|
273 | ||
|
274 | let new = DirsMultiset::new(Manifest(input_vec), None); | |
|
275 | let expected = DirsMultiset { | |
|
276 | inner: expected_inner, | |
|
277 | }; | |
|
278 | assert_eq!(expected, new); | |
|
279 | ||
|
280 | let input_map = ["a/", "b/", "a/c", "a/d/"] | |
|
281 | .iter() | |
|
282 | .map(|f| { | |
|
283 | ( | |
|
284 | f.as_bytes().to_vec(), | |
|
285 | DirstateEntry { | |
|
286 | state: 0, | |
|
287 | mode: 0, | |
|
288 | mtime: 0, | |
|
289 | size: 0, | |
|
290 | }, | |
|
291 | ) | |
|
292 | }) | |
|
293 | .collect(); | |
|
294 | let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)] | |
|
295 | .iter() | |
|
296 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
297 | .collect(); | |
|
298 | ||
|
299 | let new = DirsMultiset::new(Dirstate(input_map), None); | |
|
300 | let expected = DirsMultiset { | |
|
301 | inner: expected_inner, | |
|
302 | }; | |
|
303 | assert_eq!(expected, new); | |
|
304 | } | |
|
305 | ||
|
306 | #[test] | |
|
307 | fn test_dirsmultiset_new_skip() { | |
|
308 | use DirsIterable::{Dirstate, Manifest}; | |
|
309 | ||
|
310 | let input_vec = ["a/", "b/", "a/c", "a/d/"] | |
|
311 | .iter() | |
|
312 | .map(|e| e.as_bytes().to_vec()) | |
|
313 | .collect(); | |
|
314 | let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)] | |
|
315 | .iter() | |
|
316 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
317 | .collect(); | |
|
318 | ||
|
319 | let new = DirsMultiset::new(Manifest(input_vec), Some('n' as i8)); | |
|
320 | let expected = DirsMultiset { | |
|
321 | inner: expected_inner, | |
|
322 | }; | |
|
323 | // Skip does not affect a manifest | |
|
324 | assert_eq!(expected, new); | |
|
325 | ||
|
326 | let input_map = | |
|
327 | [("a/", 'n'), ("a/b/", 'n'), ("a/c", 'r'), ("a/d/", 'm')] | |
|
328 | .iter() | |
|
329 | .map(|(f, state)| { | |
|
330 | ( | |
|
331 | f.as_bytes().to_vec(), | |
|
332 | DirstateEntry { | |
|
333 | state: *state as i8, | |
|
334 | mode: 0, | |
|
335 | mtime: 0, | |
|
336 | size: 0, | |
|
337 | }, | |
|
338 | ) | |
|
339 | }) | |
|
340 | .collect(); | |
|
341 | ||
|
342 | // "a" incremented with "a/c" and "a/d/" | |
|
343 | let expected_inner = [("", 1), ("a", 2), ("a/d", 1)] | |
|
344 | .iter() | |
|
345 | .map(|(k, v)| (k.as_bytes().to_vec(), *v)) | |
|
346 | .collect(); | |
|
347 | ||
|
348 | let new = DirsMultiset::new(Dirstate(input_map), Some('n' as i8)); | |
|
349 | let expected = DirsMultiset { | |
|
350 | inner: expected_inner, | |
|
351 | }; | |
|
352 | assert_eq!(expected, new); | |
|
353 | } | |
|
354 | ||
|
355 | } |
@@ -1,3 +1,4 b'' | |||
|
1 | pub mod dirs_multiset; | |
|
1 | 2 | pub mod parsers; |
|
2 | 3 | |
|
3 | 4 | #[derive(Debug, PartialEq, Copy, Clone)] |
@@ -26,3 +27,10 b" pub struct CopyVecEntry<'a> {" | |||
|
26 | 27 | } |
|
27 | 28 | |
|
28 | 29 | pub type CopyVec<'a> = Vec<CopyVecEntry<'a>>; |
|
30 | ||
|
31 | /// The Python implementation passes either a mapping (dirstate) or a flat | |
|
32 | /// iterable (manifest) | |
|
33 | pub enum DirsIterable { | |
|
34 | Dirstate(DirstateVec), | |
|
35 | Manifest(Vec<Vec<u8>>), | |
|
36 | } |
@@ -15,8 +15,10 b' mod dirstate;' | |||
|
15 | 15 | pub mod discovery; |
|
16 | 16 | pub mod testing; // unconditionally built, for use from integration tests |
|
17 | 17 | pub use dirstate::{ |
|
18 | dirs_multiset::DirsMultiset, | |
|
18 | 19 | parsers::{pack_dirstate, parse_dirstate}, |
|
19 |
CopyVec, CopyVecEntry, DirstateEntry, DirstateParents, |
|
|
20 | CopyVec, CopyVecEntry, DirsIterable, DirstateEntry, DirstateParents, | |
|
21 | DirstateVec, | |
|
20 | 22 | }; |
|
21 | 23 | mod filepatterns; |
|
22 | 24 | mod utils; |
@@ -73,6 +75,12 b' pub enum DirstatePackError {' | |||
|
73 | 75 | BadSize(usize, usize), |
|
74 | 76 | } |
|
75 | 77 | |
|
78 | #[derive(Debug, PartialEq)] | |
|
79 | pub enum DirstateMapError { | |
|
80 | PathNotFound(Vec<u8>), | |
|
81 | EmptyPath, | |
|
82 | } | |
|
83 | ||
|
76 | 84 | impl From<std::io::Error> for DirstatePackError { |
|
77 | 85 | fn from(e: std::io::Error) -> Self { |
|
78 | 86 | DirstatePackError::CorruptedEntry(e.to_string()) |
General Comments 0
You need to be logged in to leave comments.
Login now