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 }