Show More
@@ -0,0 +1,14 b'' | |||
|
1 | // dirstate_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 | //! Special-case radix tree that matches a filesystem hierarchy for use in the | |
|
9 | //! dirstate. | |
|
10 | //! It has not been optimized at all yet. | |
|
11 | ||
|
12 | pub mod iter; | |
|
13 | pub mod node; | |
|
14 | pub mod tree; |
@@ -0,0 +1,358 b'' | |||
|
1 | // iter.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::node::{Node, NodeKind}; | |
|
9 | use super::tree::Tree; | |
|
10 | use crate::dirstate::dirstate_tree::node::Directory; | |
|
11 | use crate::dirstate::status::Dispatch; | |
|
12 | use crate::utils::hg_path::{hg_path_to_path_buf, HgPath, HgPathBuf}; | |
|
13 | use crate::DirstateEntry; | |
|
14 | use std::borrow::Cow; | |
|
15 | use std::collections::VecDeque; | |
|
16 | use std::iter::{FromIterator, FusedIterator}; | |
|
17 | use std::path::PathBuf; | |
|
18 | ||
|
19 | impl FromIterator<(HgPathBuf, DirstateEntry)> for Tree { | |
|
20 | fn from_iter<T: IntoIterator<Item = (HgPathBuf, DirstateEntry)>>(iter: T) -> Self { | |
|
21 | let mut tree = Self::new(); | |
|
22 | for (path, entry) in iter { | |
|
23 | tree.insert(path, entry); | |
|
24 | } | |
|
25 | tree | |
|
26 | } | |
|
27 | } | |
|
28 | ||
|
29 | /// Iterator of all entries in the dirstate tree. | |
|
30 | /// | |
|
31 | /// It has no particular ordering. | |
|
32 | pub struct Iter<'a> { | |
|
33 | to_visit: VecDeque<(Cow<'a, [u8]>, &'a Node)>, | |
|
34 | } | |
|
35 | ||
|
36 | impl<'a> Iter<'a> { | |
|
37 | pub fn new(node: &'a Node) -> Iter<'a> { | |
|
38 | let mut to_visit = VecDeque::new(); | |
|
39 | to_visit.push_back((Cow::Borrowed(&b""[..]), node)); | |
|
40 | Self { to_visit } | |
|
41 | } | |
|
42 | } | |
|
43 | ||
|
44 | impl<'a> Iterator for Iter<'a> { | |
|
45 | type Item = (HgPathBuf, DirstateEntry); | |
|
46 | ||
|
47 | fn next(&mut self) -> Option<Self::Item> { | |
|
48 | while let Some((base_path, node)) = self.to_visit.pop_front() { | |
|
49 | match &node.kind { | |
|
50 | NodeKind::Directory(dir) => { | |
|
51 | add_children_to_visit(&mut self.to_visit, &base_path, &dir); | |
|
52 | if let Some(file) = &dir.was_file { | |
|
53 | return Some((HgPathBuf::from_bytes(&base_path), file.entry)); | |
|
54 | } | |
|
55 | } | |
|
56 | NodeKind::File(file) => { | |
|
57 | if let Some(dir) = &file.was_directory { | |
|
58 | add_children_to_visit(&mut self.to_visit, &base_path, &dir); | |
|
59 | } | |
|
60 | return Some((HgPathBuf::from_bytes(&base_path), file.entry)); | |
|
61 | } | |
|
62 | } | |
|
63 | } | |
|
64 | None | |
|
65 | } | |
|
66 | } | |
|
67 | ||
|
68 | impl<'a> FusedIterator for Iter<'a> {} | |
|
69 | ||
|
70 | /// Iterator of all entries in the dirstate tree, with a special filesystem | |
|
71 | /// handling for the directories containing said entries. | |
|
72 | /// | |
|
73 | /// It checks every directory on-disk to see if it has become a symlink, to | |
|
74 | /// prevent a potential security issue. | |
|
75 | /// Using this information, it may dispatch `status` information early: it | |
|
76 | /// returns canonical paths along with `Shortcut`s, which are either a | |
|
77 | /// `DirstateEntry` or a `Dispatch`, if the fate of said path has already been | |
|
78 | /// determined. | |
|
79 | /// | |
|
80 | /// Like `Iter`, it has no particular ordering. | |
|
81 | pub struct FsIter<'a> { | |
|
82 | root_dir: PathBuf, | |
|
83 | to_visit: VecDeque<(Cow<'a, [u8]>, &'a Node)>, | |
|
84 | shortcuts: VecDeque<(HgPathBuf, StatusShortcut)>, | |
|
85 | } | |
|
86 | ||
|
87 | impl<'a> FsIter<'a> { | |
|
88 | pub fn new(node: &'a Node, root_dir: PathBuf) -> FsIter<'a> { | |
|
89 | let mut to_visit = VecDeque::new(); | |
|
90 | to_visit.push_back((Cow::Borrowed(&b""[..]), node)); | |
|
91 | Self { | |
|
92 | root_dir, | |
|
93 | to_visit, | |
|
94 | shortcuts: Default::default(), | |
|
95 | } | |
|
96 | } | |
|
97 | ||
|
98 | /// Mercurial tracks symlinks but *not* what they point to. | |
|
99 | /// If a directory is moved and symlinked: | |
|
100 | /// | |
|
101 | /// ```bash | |
|
102 | /// $ mkdir foo | |
|
103 | /// $ touch foo/a | |
|
104 | /// $ # commit... | |
|
105 | /// $ mv foo bar | |
|
106 | /// $ ln -s bar foo | |
|
107 | /// ``` | |
|
108 | /// We need to dispatch the new symlink as `Unknown` and all the | |
|
109 | /// descendents of the directory it replace as `Deleted`. | |
|
110 | fn dispatch_symlinked_directory(&mut self, path: impl AsRef<HgPath>, node: &Node) { | |
|
111 | let path = path.as_ref(); | |
|
112 | self.shortcuts | |
|
113 | .push_back((path.to_owned(), StatusShortcut::Dispatch(Dispatch::Unknown))); | |
|
114 | for (file, _) in node.iter() { | |
|
115 | self.shortcuts.push_back(( | |
|
116 | path.join(&file), | |
|
117 | StatusShortcut::Dispatch(Dispatch::Deleted), | |
|
118 | )); | |
|
119 | } | |
|
120 | } | |
|
121 | ||
|
122 | /// Returns `true` if the canonical `path` of a directory corresponds to a | |
|
123 | /// symlink on disk. It means it was moved and symlinked after the last | |
|
124 | /// dirstate update. | |
|
125 | /// | |
|
126 | /// # Special cases | |
|
127 | /// | |
|
128 | /// Returns `false` for the repository root. | |
|
129 | /// Returns `false` on io error, error handling is outside of the iterator. | |
|
130 | fn directory_became_symlink(&mut self, path: &HgPath) -> bool { | |
|
131 | if path.is_empty() { | |
|
132 | return false; | |
|
133 | } | |
|
134 | let filename_as_path = match hg_path_to_path_buf(&path) { | |
|
135 | Ok(p) => p, | |
|
136 | _ => return false, | |
|
137 | }; | |
|
138 | let meta = self.root_dir.join(filename_as_path).symlink_metadata(); | |
|
139 | match meta { | |
|
140 | Ok(ref m) if m.file_type().is_symlink() => true, | |
|
141 | _ => return false, | |
|
142 | } | |
|
143 | } | |
|
144 | } | |
|
145 | ||
|
146 | /// Returned by `FsIter`, since the `Dispatch` of any given entry may already | |
|
147 | /// be determined during the iteration. This is necessary for performance | |
|
148 | /// reasons, since hierarchical information is needed to `Dispatch` an entire | |
|
149 | /// subtree efficiently. | |
|
150 | #[derive(Debug, Copy, Clone)] | |
|
151 | pub enum StatusShortcut { | |
|
152 | /// A entry in the dirstate for further inspection | |
|
153 | Entry(DirstateEntry), | |
|
154 | /// The result of the status of the corresponding file | |
|
155 | Dispatch(Dispatch), | |
|
156 | } | |
|
157 | ||
|
158 | impl<'a> Iterator for FsIter<'a> { | |
|
159 | type Item = (HgPathBuf, StatusShortcut); | |
|
160 | ||
|
161 | fn next(&mut self) -> Option<Self::Item> { | |
|
162 | // If any paths have already been `Dispatch`-ed, return them | |
|
163 | while let Some(res) = self.shortcuts.pop_front() { | |
|
164 | return Some(res); | |
|
165 | } | |
|
166 | ||
|
167 | while let Some((base_path, node)) = self.to_visit.pop_front() { | |
|
168 | match &node.kind { | |
|
169 | NodeKind::Directory(dir) => { | |
|
170 | let canonical_path = HgPath::new(&base_path); | |
|
171 | if self.directory_became_symlink(canonical_path) { | |
|
172 | // Potential security issue, don't do a normal | |
|
173 | // traversal, force the results. | |
|
174 | self.dispatch_symlinked_directory(canonical_path, &node); | |
|
175 | continue; | |
|
176 | } | |
|
177 | add_children_to_visit(&mut self.to_visit, &base_path, &dir); | |
|
178 | if let Some(file) = &dir.was_file { | |
|
179 | return Some(( | |
|
180 | HgPathBuf::from_bytes(&base_path), | |
|
181 | StatusShortcut::Entry(file.entry), | |
|
182 | )); | |
|
183 | } | |
|
184 | } | |
|
185 | NodeKind::File(file) => { | |
|
186 | if let Some(dir) = &file.was_directory { | |
|
187 | add_children_to_visit(&mut self.to_visit, &base_path, &dir); | |
|
188 | } | |
|
189 | return Some(( | |
|
190 | HgPathBuf::from_bytes(&base_path), | |
|
191 | StatusShortcut::Entry(file.entry), | |
|
192 | )); | |
|
193 | } | |
|
194 | } | |
|
195 | } | |
|
196 | ||
|
197 | None | |
|
198 | } | |
|
199 | } | |
|
200 | ||
|
201 | impl<'a> FusedIterator for FsIter<'a> {} | |
|
202 | ||
|
203 | fn join_path<'a, 'b>(path: &'a [u8], other: &'b [u8]) -> Cow<'b, [u8]> { | |
|
204 | if path.is_empty() { | |
|
205 | other.into() | |
|
206 | } else { | |
|
207 | [path, &b"/"[..], other].concat().into() | |
|
208 | } | |
|
209 | } | |
|
210 | ||
|
211 | /// Adds all children of a given directory `dir` to the visit queue `to_visit` | |
|
212 | /// prefixed by a `base_path`. | |
|
213 | fn add_children_to_visit<'a>( | |
|
214 | to_visit: &mut VecDeque<(Cow<'a, [u8]>, &'a Node)>, | |
|
215 | base_path: &[u8], | |
|
216 | dir: &'a Directory, | |
|
217 | ) { | |
|
218 | to_visit.extend(dir.children.iter().map(|(path, child)| { | |
|
219 | let full_path = join_path(&base_path, &path); | |
|
220 | (Cow::from(full_path), child) | |
|
221 | })); | |
|
222 | } | |
|
223 | ||
|
224 | #[cfg(test)] | |
|
225 | mod tests { | |
|
226 | use super::*; | |
|
227 | use crate::utils::hg_path::HgPath; | |
|
228 | use crate::{EntryState, FastHashMap}; | |
|
229 | use std::collections::HashSet; | |
|
230 | ||
|
231 | #[test] | |
|
232 | fn test_iteration() { | |
|
233 | let mut tree = Tree::new(); | |
|
234 | ||
|
235 | assert_eq!( | |
|
236 | tree.insert( | |
|
237 | HgPathBuf::from_bytes(b"foo/bar"), | |
|
238 | DirstateEntry { | |
|
239 | state: EntryState::Merged, | |
|
240 | mode: 41, | |
|
241 | mtime: 42, | |
|
242 | size: 43, | |
|
243 | } | |
|
244 | ), | |
|
245 | None | |
|
246 | ); | |
|
247 | ||
|
248 | assert_eq!( | |
|
249 | tree.insert( | |
|
250 | HgPathBuf::from_bytes(b"foo2"), | |
|
251 | DirstateEntry { | |
|
252 | state: EntryState::Merged, | |
|
253 | mode: 40, | |
|
254 | mtime: 41, | |
|
255 | size: 42, | |
|
256 | } | |
|
257 | ), | |
|
258 | None | |
|
259 | ); | |
|
260 | ||
|
261 | assert_eq!( | |
|
262 | tree.insert( | |
|
263 | HgPathBuf::from_bytes(b"foo/baz"), | |
|
264 | DirstateEntry { | |
|
265 | state: EntryState::Normal, | |
|
266 | mode: 0, | |
|
267 | mtime: 0, | |
|
268 | size: 0, | |
|
269 | } | |
|
270 | ), | |
|
271 | None | |
|
272 | ); | |
|
273 | ||
|
274 | assert_eq!( | |
|
275 | tree.insert( | |
|
276 | HgPathBuf::from_bytes(b"foo/bap/nested"), | |
|
277 | DirstateEntry { | |
|
278 | state: EntryState::Normal, | |
|
279 | mode: 0, | |
|
280 | mtime: 0, | |
|
281 | size: 0, | |
|
282 | } | |
|
283 | ), | |
|
284 | None | |
|
285 | ); | |
|
286 | ||
|
287 | assert_eq!(tree.len(), 4); | |
|
288 | ||
|
289 | let results: HashSet<_> = tree.iter().map(|(c, _)| c.to_owned()).collect(); | |
|
290 | dbg!(&results); | |
|
291 | assert!(results.contains(HgPath::new(b"foo2"))); | |
|
292 | assert!(results.contains(HgPath::new(b"foo/bar"))); | |
|
293 | assert!(results.contains(HgPath::new(b"foo/baz"))); | |
|
294 | assert!(results.contains(HgPath::new(b"foo/bap/nested"))); | |
|
295 | ||
|
296 | let mut iter = tree.iter(); | |
|
297 | assert!(iter.next().is_some()); | |
|
298 | assert!(iter.next().is_some()); | |
|
299 | assert!(iter.next().is_some()); | |
|
300 | assert!(iter.next().is_some()); | |
|
301 | assert_eq!(None, iter.next()); | |
|
302 | assert_eq!(None, iter.next()); | |
|
303 | drop(iter); | |
|
304 | ||
|
305 | assert_eq!( | |
|
306 | tree.insert( | |
|
307 | HgPathBuf::from_bytes(b"foo/bap/nested/a"), | |
|
308 | DirstateEntry { | |
|
309 | state: EntryState::Normal, | |
|
310 | mode: 0, | |
|
311 | mtime: 0, | |
|
312 | size: 0, | |
|
313 | } | |
|
314 | ), | |
|
315 | None | |
|
316 | ); | |
|
317 | ||
|
318 | let results: FastHashMap<_, _> = tree.iter().collect(); | |
|
319 | assert!(results.contains_key(HgPath::new(b"foo2"))); | |
|
320 | assert!(results.contains_key(HgPath::new(b"foo/bar"))); | |
|
321 | assert!(results.contains_key(HgPath::new(b"foo/baz"))); | |
|
322 | // Is a dir but `was_file`, so it's listed as a removed file | |
|
323 | assert!(results.contains_key(HgPath::new(b"foo/bap/nested"))); | |
|
324 | assert!(results.contains_key(HgPath::new(b"foo/bap/nested/a"))); | |
|
325 | ||
|
326 | // insert removed file (now directory) after nested file | |
|
327 | assert_eq!( | |
|
328 | tree.insert( | |
|
329 | HgPathBuf::from_bytes(b"a/a"), | |
|
330 | DirstateEntry { | |
|
331 | state: EntryState::Normal, | |
|
332 | mode: 0, | |
|
333 | mtime: 0, | |
|
334 | size: 0, | |
|
335 | } | |
|
336 | ), | |
|
337 | None | |
|
338 | ); | |
|
339 | ||
|
340 | // `insert` returns `None` for a directory | |
|
341 | assert_eq!( | |
|
342 | tree.insert( | |
|
343 | HgPathBuf::from_bytes(b"a"), | |
|
344 | DirstateEntry { | |
|
345 | state: EntryState::Removed, | |
|
346 | mode: 0, | |
|
347 | mtime: 0, | |
|
348 | size: 0, | |
|
349 | } | |
|
350 | ), | |
|
351 | None | |
|
352 | ); | |
|
353 | ||
|
354 | let results: FastHashMap<_, _> = tree.iter().collect(); | |
|
355 | assert!(results.contains_key(HgPath::new(b"a"))); | |
|
356 | assert!(results.contains_key(HgPath::new(b"a/a"))); | |
|
357 | } | |
|
358 | } |
@@ -0,0 +1,377 b'' | |||
|
1 | // node.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 crate::utils::hg_path::HgPathBuf; | |
|
10 | use crate::{DirstateEntry, EntryState, FastHashMap}; | |
|
11 | ||
|
12 | /// Represents a filesystem directory in the dirstate tree | |
|
13 | #[derive(Debug, Default, Clone, PartialEq)] | |
|
14 | pub struct Directory { | |
|
15 | /// Contains the old file information if it existed between changesets. | |
|
16 | /// Happens if a file `foo` is marked as removed, removed from the | |
|
17 | /// filesystem then a directory `foo` is created and at least one of its | |
|
18 | /// descendents is added to Mercurial. | |
|
19 | pub(super) was_file: Option<Box<File>>, | |
|
20 | pub(super) children: FastHashMap<Vec<u8>, Node>, | |
|
21 | } | |
|
22 | ||
|
23 | /// Represents a filesystem file (or symlink) in the dirstate tree | |
|
24 | #[derive(Debug, Clone, PartialEq)] | |
|
25 | pub struct File { | |
|
26 | /// Contains the old structure if it existed between changesets. | |
|
27 | /// Happens all descendents of `foo` marked as removed and removed from | |
|
28 | /// the filesystem, then a file `foo` is created and added to Mercurial. | |
|
29 | pub(super) was_directory: Option<Box<Directory>>, | |
|
30 | pub(super) entry: DirstateEntry, | |
|
31 | } | |
|
32 | ||
|
33 | #[derive(Debug, Clone, PartialEq)] | |
|
34 | pub enum NodeKind { | |
|
35 | Directory(Directory), | |
|
36 | File(File), | |
|
37 | } | |
|
38 | ||
|
39 | #[derive(Debug, Default, Clone, PartialEq)] | |
|
40 | pub struct Node { | |
|
41 | pub kind: NodeKind, | |
|
42 | } | |
|
43 | ||
|
44 | impl Default for NodeKind { | |
|
45 | fn default() -> Self { | |
|
46 | NodeKind::Directory(Default::default()) | |
|
47 | } | |
|
48 | } | |
|
49 | ||
|
50 | impl Node { | |
|
51 | pub fn insert(&mut self, path: &[u8], new_entry: DirstateEntry) -> InsertResult { | |
|
52 | let mut split = path.splitn(2, |&c| c == b'/'); | |
|
53 | let head = split.next().unwrap_or(b""); | |
|
54 | let tail = split.next().unwrap_or(b""); | |
|
55 | ||
|
56 | if let NodeKind::File(file) = &mut self.kind { | |
|
57 | if tail.is_empty() && head.is_empty() { | |
|
58 | // We're modifying the current file | |
|
59 | let new = Self { | |
|
60 | kind: NodeKind::File(File { | |
|
61 | entry: new_entry, | |
|
62 | ..file.clone() | |
|
63 | }), | |
|
64 | }; | |
|
65 | return InsertResult { | |
|
66 | did_insert: false, | |
|
67 | old_entry: Some(std::mem::replace(self, new)), | |
|
68 | }; | |
|
69 | } else { | |
|
70 | match file.entry.state { | |
|
71 | // Only replace the current file with a directory if it's | |
|
72 | // marked as `Removed` | |
|
73 | EntryState::Removed => { | |
|
74 | self.kind = NodeKind::Directory(Directory { | |
|
75 | was_file: Some(Box::from(file.clone())), | |
|
76 | children: Default::default(), | |
|
77 | }) | |
|
78 | } | |
|
79 | _ => return Node::insert_in_file(file, new_entry, head, tail), | |
|
80 | } | |
|
81 | } | |
|
82 | } | |
|
83 | ||
|
84 | match &mut self.kind { | |
|
85 | NodeKind::Directory(directory) => { | |
|
86 | return Node::insert_in_directory(directory, new_entry, head, tail); | |
|
87 | } | |
|
88 | NodeKind::File(_) => unreachable!("The file case has already been handled"), | |
|
89 | } | |
|
90 | } | |
|
91 | ||
|
92 | /// The current file still exists and is not marked as `Removed`. | |
|
93 | /// Insert the entry in its `was_directory`. | |
|
94 | fn insert_in_file( | |
|
95 | file: &mut File, | |
|
96 | new_entry: DirstateEntry, | |
|
97 | head: &[u8], | |
|
98 | tail: &[u8], | |
|
99 | ) -> InsertResult { | |
|
100 | if let Some(d) = &mut file.was_directory { | |
|
101 | Node::insert_in_directory(d, new_entry, head, tail) | |
|
102 | } else { | |
|
103 | let mut dir = Directory { | |
|
104 | was_file: None, | |
|
105 | children: FastHashMap::default(), | |
|
106 | }; | |
|
107 | let res = Node::insert_in_directory(&mut dir, new_entry, head, tail); | |
|
108 | file.was_directory = Some(Box::new(dir)); | |
|
109 | res | |
|
110 | } | |
|
111 | } | |
|
112 | ||
|
113 | /// Insert an entry in the subtree of `directory` | |
|
114 | fn insert_in_directory( | |
|
115 | directory: &mut Directory, | |
|
116 | new_entry: DirstateEntry, | |
|
117 | head: &[u8], | |
|
118 | tail: &[u8], | |
|
119 | ) -> InsertResult { | |
|
120 | let mut res = InsertResult::default(); | |
|
121 | ||
|
122 | if let Some(node) = directory.children.get_mut(head) { | |
|
123 | // Node exists | |
|
124 | match &mut node.kind { | |
|
125 | NodeKind::Directory(subdir) => { | |
|
126 | if tail.is_empty() { | |
|
127 | let becomes_file = Self { | |
|
128 | kind: NodeKind::File(File { | |
|
129 | was_directory: Some(Box::from(subdir.clone())), | |
|
130 | entry: new_entry, | |
|
131 | }), | |
|
132 | }; | |
|
133 | let old_entry = directory.children.insert(head.to_owned(), becomes_file); | |
|
134 | return InsertResult { | |
|
135 | did_insert: true, | |
|
136 | old_entry, | |
|
137 | }; | |
|
138 | } else { | |
|
139 | res = node.insert(tail, new_entry); | |
|
140 | } | |
|
141 | } | |
|
142 | NodeKind::File(_) => { | |
|
143 | res = node.insert(tail, new_entry); | |
|
144 | } | |
|
145 | } | |
|
146 | } else if tail.is_empty() { | |
|
147 | // File does not already exist | |
|
148 | directory.children.insert( | |
|
149 | head.to_owned(), | |
|
150 | Self { | |
|
151 | kind: NodeKind::File(File { | |
|
152 | was_directory: None, | |
|
153 | entry: new_entry, | |
|
154 | }), | |
|
155 | }, | |
|
156 | ); | |
|
157 | res.did_insert = true; | |
|
158 | } else { | |
|
159 | // Directory does not already exist | |
|
160 | let mut nested = Self { | |
|
161 | kind: NodeKind::Directory(Directory { | |
|
162 | was_file: None, | |
|
163 | children: Default::default(), | |
|
164 | }), | |
|
165 | }; | |
|
166 | res = nested.insert(tail, new_entry); | |
|
167 | directory.children.insert(head.to_owned(), nested); | |
|
168 | } | |
|
169 | res | |
|
170 | } | |
|
171 | ||
|
172 | /// Removes an entry from the tree, returns a `RemoveResult`. | |
|
173 | pub fn remove(&mut self, path: &[u8]) -> RemoveResult { | |
|
174 | let empty_result = RemoveResult::default(); | |
|
175 | if path.is_empty() { | |
|
176 | return empty_result; | |
|
177 | } | |
|
178 | let mut split = path.splitn(2, |&c| c == b'/'); | |
|
179 | let head = split.next(); | |
|
180 | let tail = split.next().unwrap_or(b""); | |
|
181 | ||
|
182 | let head = match head { | |
|
183 | None => { | |
|
184 | return empty_result; | |
|
185 | } | |
|
186 | Some(h) => h, | |
|
187 | }; | |
|
188 | if head == path { | |
|
189 | match &mut self.kind { | |
|
190 | NodeKind::Directory(d) => { | |
|
191 | return Node::remove_from_directory(head, d); | |
|
192 | } | |
|
193 | NodeKind::File(f) => { | |
|
194 | if let Some(d) = &mut f.was_directory { | |
|
195 | let RemoveResult { old_entry, .. } = Node::remove_from_directory(head, d); | |
|
196 | return RemoveResult { | |
|
197 | cleanup: false, | |
|
198 | old_entry, | |
|
199 | }; | |
|
200 | } | |
|
201 | } | |
|
202 | } | |
|
203 | empty_result | |
|
204 | } else { | |
|
205 | // Look into the dirs | |
|
206 | match &mut self.kind { | |
|
207 | NodeKind::Directory(d) => { | |
|
208 | if let Some(child) = d.children.get_mut(head) { | |
|
209 | let mut res = child.remove(tail); | |
|
210 | if res.cleanup { | |
|
211 | d.children.remove(head); | |
|
212 | } | |
|
213 | res.cleanup = d.children.len() == 0 && d.was_file.is_none(); | |
|
214 | res | |
|
215 | } else { | |
|
216 | empty_result | |
|
217 | } | |
|
218 | } | |
|
219 | NodeKind::File(f) => { | |
|
220 | if let Some(d) = &mut f.was_directory { | |
|
221 | if let Some(child) = d.children.get_mut(head) { | |
|
222 | let RemoveResult { cleanup, old_entry } = child.remove(tail); | |
|
223 | if cleanup { | |
|
224 | d.children.remove(head); | |
|
225 | } | |
|
226 | if d.children.len() == 0 && d.was_file.is_none() { | |
|
227 | f.was_directory = None; | |
|
228 | } | |
|
229 | ||
|
230 | return RemoveResult { | |
|
231 | cleanup: false, | |
|
232 | old_entry, | |
|
233 | }; | |
|
234 | } | |
|
235 | } | |
|
236 | empty_result | |
|
237 | } | |
|
238 | } | |
|
239 | } | |
|
240 | } | |
|
241 | ||
|
242 | fn remove_from_directory(head: &[u8], d: &mut Directory) -> RemoveResult { | |
|
243 | if let Some(node) = d.children.get_mut(head) { | |
|
244 | return match &mut node.kind { | |
|
245 | NodeKind::Directory(d) => { | |
|
246 | if let Some(f) = &mut d.was_file { | |
|
247 | let entry = f.entry; | |
|
248 | d.was_file = None; | |
|
249 | RemoveResult { | |
|
250 | cleanup: false, | |
|
251 | old_entry: Some(entry), | |
|
252 | } | |
|
253 | } else { | |
|
254 | RemoveResult::default() | |
|
255 | } | |
|
256 | } | |
|
257 | NodeKind::File(f) => { | |
|
258 | let entry = f.entry; | |
|
259 | let mut cleanup = false; | |
|
260 | match &f.was_directory { | |
|
261 | None => { | |
|
262 | if d.children.len() == 1 { | |
|
263 | cleanup = true; | |
|
264 | } | |
|
265 | d.children.remove(head); | |
|
266 | } | |
|
267 | Some(dir) => { | |
|
268 | node.kind = NodeKind::Directory(*dir.clone()); | |
|
269 | } | |
|
270 | } | |
|
271 | ||
|
272 | RemoveResult { | |
|
273 | cleanup: cleanup, | |
|
274 | old_entry: Some(entry), | |
|
275 | } | |
|
276 | } | |
|
277 | }; | |
|
278 | } | |
|
279 | RemoveResult::default() | |
|
280 | } | |
|
281 | ||
|
282 | pub fn get(&self, path: &[u8]) -> Option<&Node> { | |
|
283 | if path.is_empty() { | |
|
284 | return Some(&self); | |
|
285 | } | |
|
286 | let mut split = path.splitn(2, |&c| c == b'/'); | |
|
287 | let head = split.next(); | |
|
288 | let tail = split.next().unwrap_or(b""); | |
|
289 | ||
|
290 | let head = match head { | |
|
291 | None => { | |
|
292 | return Some(&self); | |
|
293 | } | |
|
294 | Some(h) => h, | |
|
295 | }; | |
|
296 | match &self.kind { | |
|
297 | NodeKind::Directory(d) => { | |
|
298 | if let Some(child) = d.children.get(head) { | |
|
299 | return child.get(tail); | |
|
300 | } | |
|
301 | } | |
|
302 | NodeKind::File(f) => { | |
|
303 | if let Some(d) = &f.was_directory { | |
|
304 | if let Some(child) = d.children.get(head) { | |
|
305 | return child.get(tail); | |
|
306 | } | |
|
307 | } | |
|
308 | } | |
|
309 | } | |
|
310 | ||
|
311 | None | |
|
312 | } | |
|
313 | ||
|
314 | pub fn get_mut(&mut self, path: &[u8]) -> Option<&mut NodeKind> { | |
|
315 | if path.is_empty() { | |
|
316 | return Some(&mut self.kind); | |
|
317 | } | |
|
318 | let mut split = path.splitn(2, |&c| c == b'/'); | |
|
319 | let head = split.next(); | |
|
320 | let tail = split.next().unwrap_or(b""); | |
|
321 | ||
|
322 | let head = match head { | |
|
323 | None => { | |
|
324 | return Some(&mut self.kind); | |
|
325 | } | |
|
326 | Some(h) => h, | |
|
327 | }; | |
|
328 | match &mut self.kind { | |
|
329 | NodeKind::Directory(d) => { | |
|
330 | if let Some(child) = d.children.get_mut(head) { | |
|
331 | return child.get_mut(tail); | |
|
332 | } | |
|
333 | } | |
|
334 | NodeKind::File(f) => { | |
|
335 | if let Some(d) = &mut f.was_directory { | |
|
336 | if let Some(child) = d.children.get_mut(head) { | |
|
337 | return child.get_mut(tail); | |
|
338 | } | |
|
339 | } | |
|
340 | } | |
|
341 | } | |
|
342 | ||
|
343 | None | |
|
344 | } | |
|
345 | ||
|
346 | pub fn iter(&self) -> Iter { | |
|
347 | Iter::new(self) | |
|
348 | } | |
|
349 | } | |
|
350 | ||
|
351 | /// Information returned to the caller of an `insert` operation for integrity. | |
|
352 | #[derive(Debug, Default)] | |
|
353 | pub struct InsertResult { | |
|
354 | /// Whether the insertion resulted in an actual insertion and not an | |
|
355 | /// update | |
|
356 | pub(super) did_insert: bool, | |
|
357 | /// The entry that was replaced, if it exists | |
|
358 | pub(super) old_entry: Option<Node>, | |
|
359 | } | |
|
360 | ||
|
361 | /// Information returned to the caller of a `remove` operation integrity. | |
|
362 | #[derive(Debug, Default)] | |
|
363 | pub struct RemoveResult { | |
|
364 | /// If the caller needs to remove the current node | |
|
365 | pub(super) cleanup: bool, | |
|
366 | /// The entry that was replaced, if it exists | |
|
367 | pub(super) old_entry: Option<DirstateEntry>, | |
|
368 | } | |
|
369 | ||
|
370 | impl<'a> IntoIterator for &'a Node { | |
|
371 | type Item = (HgPathBuf, DirstateEntry); | |
|
372 | type IntoIter = Iter<'a>; | |
|
373 | ||
|
374 | fn into_iter(self) -> Self::IntoIter { | |
|
375 | self.iter() | |
|
376 | } | |
|
377 | } |
This diff has been collapsed as it changes many lines, (661 lines changed) Show them Hide them | |||
@@ -0,0 +1,661 b'' | |||
|
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 | } |
General Comments 0
You need to be logged in to leave comments.
Login now