Mercurial > hg
comparison rust/hg-core/src/dirstate/dirstate_tree/tree.rs @ 45562:b51167d70f5a
rust: add `dirstate_tree` module
Mercurial needs to represent the filesystem hierarchy on which it operates, for
example in the dirstate. Its current on-disk representation is an unsorted, flat
structure that gets transformed in the current Rust code into a `HashMap`.
This loses the hierarchical information of the dirstate, leading to some
unfortunate performance and algorithmic compromises.
This module adds an implementation of a radix tree that is specialized for
representing the dirstate: its unit is the path component. I have made no
efforts to optimize either its memory footprint or its insertion speed: they're
pretty bad for now.
Following will be a few patches that modify the dirstate.status logic to use
that new hierarchical information, fixing issue 6335 in the same swing.
Differential Revision: https://phab.mercurial-scm.org/D9085
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Fri, 25 Sep 2020 17:51:34 +0200 |
parents | |
children | c35db907363d |
comparison
equal
deleted
inserted
replaced
45558:80bf7b1ada15 | 45562:b51167d70f5a |
---|---|
1 // tree.rs | |
2 // | |
3 // Copyright 2020, 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 use super::iter::Iter; | |
9 use super::node::{Directory, Node, NodeKind}; | |
10 use crate::dirstate::dirstate_tree::iter::FsIter; | |
11 use crate::dirstate::dirstate_tree::node::{InsertResult, RemoveResult}; | |
12 use crate::utils::hg_path::{HgPath, HgPathBuf}; | |
13 use crate::DirstateEntry; | |
14 use std::path::PathBuf; | |
15 | |
16 /// A specialized tree to represent the Mercurial dirstate. | |
17 /// | |
18 /// # Advantages over a flat structure | |
19 /// | |
20 /// The dirstate is inherently hierarchical, since it's a representation of the | |
21 /// file structure of the project. The current dirstate format is flat, and | |
22 /// while that affords us potentially great (unordered) iteration speeds, the | |
23 /// need to retrieve a given path is great enough that you need some kind of | |
24 /// hashmap or tree in a lot of cases anyway. | |
25 /// | |
26 /// Going with a tree allows us to be smarter: | |
27 /// - Skipping an ignored directory means we don't visit its entire subtree | |
28 /// - Security auditing does not need to reconstruct paths backwards to check | |
29 /// for symlinked directories, this can be done during the iteration in a | |
30 /// very efficient fashion | |
31 /// - We don't need to build the directory information in another struct, | |
32 /// simplifying the code a lot, reducing the memory footprint and | |
33 /// potentially going faster depending on the implementation. | |
34 /// - We can use it to store a (platform-dependent) caching mechanism [1] | |
35 /// - And probably other types of optimizations. | |
36 /// | |
37 /// Only the first two items in this list are implemented as of this commit. | |
38 /// | |
39 /// [1]: https://www.mercurial-scm.org/wiki/DirsCachePlan | |
40 /// | |
41 /// | |
42 /// # Structure | |
43 /// | |
44 /// It's a prefix (radix) tree with no fixed arity, with a granularity of a | |
45 /// folder, allowing it to mimic a filesystem hierarchy: | |
46 /// | |
47 /// ```text | |
48 /// foo/bar | |
49 /// foo/baz | |
50 /// test | |
51 /// ``` | |
52 /// Will be represented (simplified) by: | |
53 /// | |
54 /// ```text | |
55 /// Directory(root): | |
56 /// - File("test") | |
57 /// - Directory("foo"): | |
58 /// - File("bar") | |
59 /// - File("baz") | |
60 /// ``` | |
61 /// | |
62 /// Moreover, it is special-cased for storing the dirstate and as such handles | |
63 /// cases that a simple `HashMap` would handle, but while preserving the | |
64 /// hierarchy. | |
65 /// For example: | |
66 /// | |
67 /// ```shell | |
68 /// $ touch foo | |
69 /// $ hg add foo | |
70 /// $ hg commit -m "foo" | |
71 /// $ hg remove foo | |
72 /// $ rm foo | |
73 /// $ mkdir foo | |
74 /// $ touch foo/a | |
75 /// $ hg add foo/a | |
76 /// $ hg status | |
77 /// R foo | |
78 /// A foo/a | |
79 /// ``` | |
80 /// To represent this in a tree, one needs to keep track of whether any given | |
81 /// file was a directory and whether any given directory was a file at the last | |
82 /// dirstate update. This tree stores that information, but only in the right | |
83 /// circumstances by respecting the high-level rules that prevent nonsensical | |
84 /// structures to exist: | |
85 /// - a file can only be added as a child of another file if the latter is | |
86 /// marked as `Removed` | |
87 /// - a file cannot replace a folder unless all its descendents are removed | |
88 /// | |
89 /// This second rule is not checked by the tree for performance reasons, and | |
90 /// because high-level logic already prevents that state from happening. | |
91 /// | |
92 /// # Ordering | |
93 /// | |
94 /// It makes no guarantee of ordering for now. | |
95 #[derive(Debug, Default, Clone, PartialEq)] | |
96 pub struct Tree { | |
97 pub root: Node, | |
98 files_count: usize, | |
99 } | |
100 | |
101 impl Tree { | |
102 pub fn new() -> Self { | |
103 Self { | |
104 root: Node { | |
105 kind: NodeKind::Directory(Directory { | |
106 was_file: None, | |
107 children: Default::default(), | |
108 }), | |
109 }, | |
110 files_count: 0, | |
111 } | |
112 } | |
113 | |
114 /// How many files (not directories) are stored in the tree, including ones | |
115 /// marked as `Removed`. | |
116 pub fn len(&self) -> usize { | |
117 self.files_count | |
118 } | |
119 | |
120 pub fn is_empty(&self) -> bool { | |
121 self.len() == 0 | |
122 } | |
123 | |
124 /// Inserts a file in the tree and returns the previous entry if any. | |
125 pub fn insert( | |
126 &mut self, | |
127 path: impl AsRef<HgPath>, | |
128 kind: DirstateEntry, | |
129 ) -> Option<DirstateEntry> { | |
130 let old = self.insert_node(path, kind); | |
131 match old?.kind { | |
132 NodeKind::Directory(_) => None, | |
133 NodeKind::File(f) => Some(f.entry), | |
134 } | |
135 } | |
136 | |
137 /// Low-level insertion method that returns the previous node (directories | |
138 /// included). | |
139 fn insert_node(&mut self, path: impl AsRef<HgPath>, kind: DirstateEntry) -> Option<Node> { | |
140 let InsertResult { | |
141 did_insert, | |
142 old_entry, | |
143 } = self.root.insert(path.as_ref().as_bytes(), kind); | |
144 self.files_count += if did_insert { 1 } else { 0 }; | |
145 old_entry | |
146 } | |
147 | |
148 /// Returns a reference to a node if it exists. | |
149 pub fn get_node(&self, path: impl AsRef<HgPath>) -> Option<&Node> { | |
150 self.root.get(path.as_ref().as_bytes()) | |
151 } | |
152 | |
153 /// Returns a reference to the entry corresponding to `path` if it exists. | |
154 pub fn get(&self, path: impl AsRef<HgPath>) -> Option<&DirstateEntry> { | |
155 if let Some(node) = self.get_node(&path) { | |
156 return match &node.kind { | |
157 NodeKind::Directory(d) => d.was_file.as_ref().map(|f| &f.entry), | |
158 NodeKind::File(f) => Some(&f.entry), | |
159 }; | |
160 } | |
161 None | |
162 } | |
163 | |
164 /// Returns `true` if an entry is found for the given `path`. | |
165 pub fn contains_key(&self, path: impl AsRef<HgPath>) -> bool { | |
166 self.get(path).is_some() | |
167 } | |
168 | |
169 /// Returns a mutable reference to the entry corresponding to `path` if it | |
170 /// exists. | |
171 pub fn get_mut(&mut self, path: impl AsRef<HgPath>) -> Option<&mut DirstateEntry> { | |
172 if let Some(kind) = self.root.get_mut(path.as_ref().as_bytes()) { | |
173 return match kind { | |
174 NodeKind::Directory(d) => d.was_file.as_mut().map(|f| &mut f.entry), | |
175 NodeKind::File(f) => Some(&mut f.entry), | |
176 }; | |
177 } | |
178 None | |
179 } | |
180 | |
181 /// Returns an iterator over the paths and corresponding entries in the | |
182 /// tree. | |
183 pub fn iter(&self) -> Iter { | |
184 Iter::new(&self.root) | |
185 } | |
186 | |
187 /// Returns an iterator of all entries in the tree, with a special | |
188 /// filesystem handling for the directories containing said entries. See | |
189 /// the documentation of `FsIter` for more. | |
190 pub fn fs_iter(&self, root_dir: PathBuf) -> FsIter { | |
191 FsIter::new(&self.root, root_dir) | |
192 } | |
193 | |
194 /// Remove the entry at `path` and returns it, if it exists. | |
195 pub fn remove(&mut self, path: impl AsRef<HgPath>) -> Option<DirstateEntry> { | |
196 let RemoveResult { old_entry, .. } = self.root.remove(path.as_ref().as_bytes()); | |
197 self.files_count = self | |
198 .files_count | |
199 .checked_sub(if old_entry.is_some() { 1 } else { 0 }) | |
200 .expect("removed too many files"); | |
201 old_entry | |
202 } | |
203 } | |
204 | |
205 impl<P: AsRef<HgPath>> Extend<(P, DirstateEntry)> for Tree { | |
206 fn extend<T: IntoIterator<Item = (P, DirstateEntry)>>(&mut self, iter: T) { | |
207 for (path, entry) in iter { | |
208 self.insert(path, entry); | |
209 } | |
210 } | |
211 } | |
212 | |
213 impl<'a> IntoIterator for &'a Tree { | |
214 type Item = (HgPathBuf, DirstateEntry); | |
215 type IntoIter = Iter<'a>; | |
216 | |
217 fn into_iter(self) -> Self::IntoIter { | |
218 self.iter() | |
219 } | |
220 } | |
221 | |
222 #[cfg(test)] | |
223 mod tests { | |
224 use super::*; | |
225 use crate::dirstate::dirstate_tree::node::File; | |
226 use crate::{EntryState, FastHashMap}; | |
227 use pretty_assertions::assert_eq; | |
228 | |
229 impl Node { | |
230 /// Shortcut for getting children of a node in tests. | |
231 fn children(&self) -> Option<&FastHashMap<Vec<u8>, Node>> { | |
232 match &self.kind { | |
233 NodeKind::Directory(d) => Some(&d.children), | |
234 NodeKind::File(_) => None, | |
235 } | |
236 } | |
237 } | |
238 | |
239 #[test] | |
240 fn test_dirstate_tree() { | |
241 let mut tree = Tree::new(); | |
242 | |
243 assert_eq!( | |
244 tree.insert_node( | |
245 HgPath::new(b"we/p"), | |
246 DirstateEntry { | |
247 state: EntryState::Normal, | |
248 mode: 0, | |
249 mtime: 0, | |
250 size: 0 | |
251 } | |
252 ), | |
253 None | |
254 ); | |
255 dbg!(&tree); | |
256 assert!(tree.get_node(HgPath::new(b"we")).is_some()); | |
257 let entry = DirstateEntry { | |
258 state: EntryState::Merged, | |
259 mode: 41, | |
260 mtime: 42, | |
261 size: 43, | |
262 }; | |
263 assert_eq!(tree.insert_node(HgPath::new(b"foo/bar"), entry), None); | |
264 assert_eq!( | |
265 tree.get_node(HgPath::new(b"foo/bar")), | |
266 Some(&Node { | |
267 kind: NodeKind::File(File { | |
268 was_directory: None, | |
269 entry | |
270 }) | |
271 }) | |
272 ); | |
273 // We didn't override the first entry we made | |
274 assert!(tree.get_node(HgPath::new(b"we")).is_some(),); | |
275 // Inserting the same key again | |
276 assert_eq!( | |
277 tree.insert_node(HgPath::new(b"foo/bar"), entry), | |
278 Some(Node { | |
279 kind: NodeKind::File(File { | |
280 was_directory: None, | |
281 entry | |
282 }), | |
283 }) | |
284 ); | |
285 // Inserting the two levels deep | |
286 assert_eq!(tree.insert_node(HgPath::new(b"foo/bar/baz"), entry), None); | |
287 // Getting a file "inside a file" should return `None` | |
288 assert_eq!(tree.get_node(HgPath::new(b"foo/bar/baz/bap"),), None); | |
289 | |
290 assert_eq!( | |
291 tree.insert_node(HgPath::new(b"wasdir/subfile"), entry), | |
292 None, | |
293 ); | |
294 let removed_entry = DirstateEntry { | |
295 state: EntryState::Removed, | |
296 mode: 0, | |
297 mtime: 0, | |
298 size: 0, | |
299 }; | |
300 assert!(tree | |
301 .insert_node(HgPath::new(b"wasdir"), removed_entry) | |
302 .is_some()); | |
303 | |
304 assert_eq!( | |
305 tree.get_node(HgPath::new(b"wasdir")), | |
306 Some(&Node { | |
307 kind: NodeKind::File(File { | |
308 was_directory: Some(Box::new(Directory { | |
309 was_file: None, | |
310 children: [( | |
311 b"subfile".to_vec(), | |
312 Node { | |
313 kind: NodeKind::File(File { | |
314 was_directory: None, | |
315 entry, | |
316 }) | |
317 } | |
318 )] | |
319 .to_vec() | |
320 .into_iter() | |
321 .collect() | |
322 })), | |
323 entry: removed_entry | |
324 }) | |
325 }) | |
326 ); | |
327 | |
328 assert!(tree.get(HgPath::new(b"wasdir/subfile")).is_some()) | |
329 } | |
330 | |
331 #[test] | |
332 fn test_insert_removed() { | |
333 let mut tree = Tree::new(); | |
334 let entry = DirstateEntry { | |
335 state: EntryState::Merged, | |
336 mode: 1, | |
337 mtime: 2, | |
338 size: 3, | |
339 }; | |
340 let removed_entry = DirstateEntry { | |
341 state: EntryState::Removed, | |
342 mode: 10, | |
343 mtime: 20, | |
344 size: 30, | |
345 }; | |
346 assert_eq!(tree.insert_node(HgPath::new(b"foo"), entry), None); | |
347 assert_eq!(tree.insert_node(HgPath::new(b"foo/a"), removed_entry), None); | |
348 // The insert should not turn `foo` into a directory as `foo` is not | |
349 // `Removed`. | |
350 match tree.get_node(HgPath::new(b"foo")).unwrap().kind { | |
351 NodeKind::Directory(_) => panic!("should be a file"), | |
352 NodeKind::File(_) => {} | |
353 } | |
354 | |
355 let mut tree = Tree::new(); | |
356 let entry = DirstateEntry { | |
357 state: EntryState::Merged, | |
358 mode: 1, | |
359 mtime: 2, | |
360 size: 3, | |
361 }; | |
362 let removed_entry = DirstateEntry { | |
363 state: EntryState::Removed, | |
364 mode: 10, | |
365 mtime: 20, | |
366 size: 30, | |
367 }; | |
368 // The insert *should* turn `foo` into a directory as it is `Removed`. | |
369 assert_eq!(tree.insert_node(HgPath::new(b"foo"), removed_entry), None); | |
370 assert_eq!(tree.insert_node(HgPath::new(b"foo/a"), entry), None); | |
371 match tree.get_node(HgPath::new(b"foo")).unwrap().kind { | |
372 NodeKind::Directory(_) => {} | |
373 NodeKind::File(_) => panic!("should be a directory"), | |
374 } | |
375 } | |
376 | |
377 #[test] | |
378 fn test_get() { | |
379 let mut tree = Tree::new(); | |
380 let entry = DirstateEntry { | |
381 state: EntryState::Merged, | |
382 mode: 1, | |
383 mtime: 2, | |
384 size: 3, | |
385 }; | |
386 assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None); | |
387 assert_eq!(tree.files_count, 1); | |
388 assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry)); | |
389 assert_eq!(tree.get(HgPath::new(b"a/b")), None); | |
390 assert_eq!(tree.get(HgPath::new(b"a")), None); | |
391 assert_eq!(tree.get(HgPath::new(b"a/b/c/d")), None); | |
392 let entry2 = DirstateEntry { | |
393 state: EntryState::Removed, | |
394 mode: 0, | |
395 mtime: 5, | |
396 size: 1, | |
397 }; | |
398 // was_directory | |
399 assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None); | |
400 assert_eq!(tree.files_count, 2); | |
401 assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2)); | |
402 assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry)); | |
403 | |
404 let mut tree = Tree::new(); | |
405 | |
406 // was_file | |
407 assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None); | |
408 assert_eq!(tree.files_count, 1); | |
409 assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None); | |
410 assert_eq!(tree.files_count, 2); | |
411 assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2)); | |
412 } | |
413 | |
414 #[test] | |
415 fn test_get_mut() { | |
416 let mut tree = Tree::new(); | |
417 let mut entry = DirstateEntry { | |
418 state: EntryState::Merged, | |
419 mode: 1, | |
420 mtime: 2, | |
421 size: 3, | |
422 }; | |
423 assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None); | |
424 assert_eq!(tree.files_count, 1); | |
425 assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry)); | |
426 assert_eq!(tree.get_mut(HgPath::new(b"a/b")), None); | |
427 assert_eq!(tree.get_mut(HgPath::new(b"a")), None); | |
428 assert_eq!(tree.get_mut(HgPath::new(b"a/b/c/d")), None); | |
429 let mut entry2 = DirstateEntry { | |
430 state: EntryState::Removed, | |
431 mode: 0, | |
432 mtime: 5, | |
433 size: 1, | |
434 }; | |
435 // was_directory | |
436 assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None); | |
437 assert_eq!(tree.files_count, 2); | |
438 assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2)); | |
439 assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry)); | |
440 | |
441 let mut tree = Tree::new(); | |
442 | |
443 // was_file | |
444 assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None); | |
445 assert_eq!(tree.files_count, 1); | |
446 assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None); | |
447 assert_eq!(tree.files_count, 2); | |
448 assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2)); | |
449 } | |
450 | |
451 #[test] | |
452 fn test_remove() { | |
453 let mut tree = Tree::new(); | |
454 assert_eq!(tree.files_count, 0); | |
455 assert_eq!(tree.remove(HgPath::new(b"foo")), None); | |
456 assert_eq!(tree.files_count, 0); | |
457 | |
458 let entry = DirstateEntry { | |
459 state: EntryState::Normal, | |
460 mode: 0, | |
461 mtime: 0, | |
462 size: 0, | |
463 }; | |
464 assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None); | |
465 assert_eq!(tree.files_count, 1); | |
466 | |
467 assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry)); | |
468 assert_eq!(tree.files_count, 0); | |
469 | |
470 assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None); | |
471 assert_eq!(tree.insert_node(HgPath::new(b"a/b/y"), entry), None); | |
472 assert_eq!(tree.insert_node(HgPath::new(b"a/b/z"), entry), None); | |
473 assert_eq!(tree.insert_node(HgPath::new(b"x"), entry), None); | |
474 assert_eq!(tree.insert_node(HgPath::new(b"y"), entry), None); | |
475 assert_eq!(tree.files_count, 5); | |
476 | |
477 assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry)); | |
478 assert_eq!(tree.files_count, 4); | |
479 assert_eq!(tree.remove(HgPath::new(b"a/b/x")), None); | |
480 assert_eq!(tree.files_count, 4); | |
481 assert_eq!(tree.remove(HgPath::new(b"a/b/y")), Some(entry)); | |
482 assert_eq!(tree.files_count, 3); | |
483 assert_eq!(tree.remove(HgPath::new(b"a/b/z")), Some(entry)); | |
484 assert_eq!(tree.files_count, 2); | |
485 | |
486 assert_eq!(tree.remove(HgPath::new(b"x")), Some(entry)); | |
487 assert_eq!(tree.files_count, 1); | |
488 assert_eq!(tree.remove(HgPath::new(b"y")), Some(entry)); | |
489 assert_eq!(tree.files_count, 0); | |
490 | |
491 // `a` should have been cleaned up, no more files anywhere in its | |
492 // descendents | |
493 assert_eq!(tree.get_node(HgPath::new(b"a")), None); | |
494 assert_eq!(tree.root.children().unwrap().len(), 0); | |
495 | |
496 let removed_entry = DirstateEntry { | |
497 state: EntryState::Removed, | |
498 ..entry | |
499 }; | |
500 assert_eq!(tree.insert(HgPath::new(b"a"), removed_entry), None); | |
501 assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None); | |
502 assert_eq!(tree.files_count, 2); | |
503 dbg!(&tree); | |
504 assert_eq!(tree.remove(HgPath::new(b"a")), Some(removed_entry)); | |
505 assert_eq!(tree.files_count, 1); | |
506 dbg!(&tree); | |
507 assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry)); | |
508 assert_eq!(tree.files_count, 0); | |
509 | |
510 // The entire tree should have been cleaned up, no more files anywhere | |
511 // in its descendents | |
512 assert_eq!(tree.root.children().unwrap().len(), 0); | |
513 | |
514 let removed_entry = DirstateEntry { | |
515 state: EntryState::Removed, | |
516 ..entry | |
517 }; | |
518 assert_eq!(tree.insert(HgPath::new(b"a"), entry), None); | |
519 assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), removed_entry), None); | |
520 assert_eq!(tree.files_count, 2); | |
521 dbg!(&tree); | |
522 assert_eq!(tree.remove(HgPath::new(b"a")), Some(entry)); | |
523 assert_eq!(tree.files_count, 1); | |
524 dbg!(&tree); | |
525 assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(removed_entry)); | |
526 assert_eq!(tree.files_count, 0); | |
527 | |
528 dbg!(&tree); | |
529 // The entire tree should have been cleaned up, no more files anywhere | |
530 // in its descendents | |
531 assert_eq!(tree.root.children().unwrap().len(), 0); | |
532 | |
533 assert_eq!(tree.insert(HgPath::new(b"d"), entry), None); | |
534 assert_eq!(tree.insert(HgPath::new(b"d/d/d"), entry), None); | |
535 assert_eq!(tree.files_count, 2); | |
536 | |
537 // Deleting the nested file should not delete the top directory as it | |
538 // used to be a file | |
539 assert_eq!(tree.remove(HgPath::new(b"d/d/d")), Some(entry)); | |
540 assert_eq!(tree.files_count, 1); | |
541 assert!(tree.get_node(HgPath::new(b"d")).is_some()); | |
542 assert!(tree.remove(HgPath::new(b"d")).is_some()); | |
543 assert_eq!(tree.files_count, 0); | |
544 | |
545 // Deleting the nested file should not delete the top file (other way | |
546 // around from the last case) | |
547 assert_eq!(tree.insert(HgPath::new(b"a/a"), entry), None); | |
548 assert_eq!(tree.files_count, 1); | |
549 assert_eq!(tree.insert(HgPath::new(b"a"), entry), None); | |
550 assert_eq!(tree.files_count, 2); | |
551 dbg!(&tree); | |
552 assert_eq!(tree.remove(HgPath::new(b"a/a")), Some(entry)); | |
553 assert_eq!(tree.files_count, 1); | |
554 dbg!(&tree); | |
555 assert!(tree.get_node(HgPath::new(b"a")).is_some()); | |
556 assert!(tree.get_node(HgPath::new(b"a/a")).is_none()); | |
557 } | |
558 | |
559 #[test] | |
560 fn test_was_directory() { | |
561 let mut tree = Tree::new(); | |
562 | |
563 let entry = DirstateEntry { | |
564 state: EntryState::Removed, | |
565 mode: 0, | |
566 mtime: 0, | |
567 size: 0, | |
568 }; | |
569 assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None); | |
570 assert_eq!(tree.files_count, 1); | |
571 | |
572 assert!(tree.insert_node(HgPath::new(b"a"), entry).is_some()); | |
573 let new_a = tree.root.children().unwrap().get(&b"a".to_vec()).unwrap(); | |
574 | |
575 match &new_a.kind { | |
576 NodeKind::Directory(_) => panic!(), | |
577 NodeKind::File(f) => { | |
578 let dir = f.was_directory.clone().unwrap(); | |
579 let c = dir | |
580 .children | |
581 .get(&b"b".to_vec()) | |
582 .unwrap() | |
583 .children() | |
584 .unwrap() | |
585 .get(&b"c".to_vec()) | |
586 .unwrap(); | |
587 | |
588 assert_eq!( | |
589 match &c.kind { | |
590 NodeKind::Directory(_) => panic!(), | |
591 NodeKind::File(f) => f.entry, | |
592 }, | |
593 entry | |
594 ); | |
595 } | |
596 } | |
597 assert_eq!(tree.files_count, 2); | |
598 dbg!(&tree); | |
599 assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry)); | |
600 assert_eq!(tree.files_count, 1); | |
601 dbg!(&tree); | |
602 let a = tree.get_node(HgPath::new(b"a")).unwrap(); | |
603 match &a.kind { | |
604 NodeKind::Directory(_) => panic!(), | |
605 NodeKind::File(f) => { | |
606 // Directory in `was_directory` was emptied, should be removed | |
607 assert_eq!(f.was_directory, None); | |
608 } | |
609 } | |
610 } | |
611 #[test] | |
612 fn test_extend() { | |
613 let insertions = [ | |
614 ( | |
615 HgPathBuf::from_bytes(b"d"), | |
616 DirstateEntry { | |
617 state: EntryState::Added, | |
618 mode: 0, | |
619 mtime: -1, | |
620 size: -1, | |
621 }, | |
622 ), | |
623 ( | |
624 HgPathBuf::from_bytes(b"b"), | |
625 DirstateEntry { | |
626 state: EntryState::Normal, | |
627 mode: 33188, | |
628 mtime: 1599647984, | |
629 size: 2, | |
630 }, | |
631 ), | |
632 ( | |
633 HgPathBuf::from_bytes(b"a/a"), | |
634 DirstateEntry { | |
635 state: EntryState::Normal, | |
636 mode: 33188, | |
637 mtime: 1599647984, | |
638 size: 2, | |
639 }, | |
640 ), | |
641 ( | |
642 HgPathBuf::from_bytes(b"d/d/d"), | |
643 DirstateEntry { | |
644 state: EntryState::Removed, | |
645 mode: 0, | |
646 mtime: 0, | |
647 size: 0, | |
648 }, | |
649 ), | |
650 ] | |
651 .to_vec(); | |
652 let mut tree = Tree::new(); | |
653 | |
654 tree.extend(insertions.clone().into_iter()); | |
655 | |
656 for (path, _) in &insertions { | |
657 assert!(tree.contains_key(path), true); | |
658 } | |
659 assert_eq!(tree.files_count, 4); | |
660 } | |
661 } |