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(

   140         &mut self,

   141         path: impl AsRef<HgPath>,

   142         kind: DirstateEntry,

   143     ) -> Option<Node> {

   144         let InsertResult {

   145             did_insert,

   146             old_entry,

   147         } = self.root.insert(path.as_ref().as_bytes(), kind);

   148         self.files_count += if did_insert { 1 } else { 0 };

   149         old_entry

   150     }

   151 

   152     /// Returns a reference to a node if it exists.

   153     pub fn get_node(&self, path: impl AsRef<HgPath>) -> Option<&Node> {

   154         self.root.get(path.as_ref().as_bytes())

   155     }

   156 

   157     /// Returns a reference to the entry corresponding to `path` if it exists.

   158     pub fn get(&self, path: impl AsRef<HgPath>) -> Option<&DirstateEntry> {

   159         if let Some(node) = self.get_node(&path) {

   160             return match &node.kind {

   161                 NodeKind::Directory(d) => {

   162                     d.was_file.as_ref().map(|f| &f.entry)

   163                 }

   164                 NodeKind::File(f) => Some(&f.entry),

   165             };

   166         }

   167         None

   168     }

   169 

   170     /// Returns `true` if an entry is found for the given `path`.

   171     pub fn contains_key(&self, path: impl AsRef<HgPath>) -> bool {

   172         self.get(path).is_some()

   173     }

   174 

   175     /// Returns a mutable reference to the entry corresponding to `path` if it

   176     /// exists.

   177     pub fn get_mut(

   178         &mut self,

   179         path: impl AsRef<HgPath>,

   180     ) -> Option<&mut DirstateEntry> {

   181         if let Some(kind) = self.root.get_mut(path.as_ref().as_bytes()) {

   182             return match kind {

   183                 NodeKind::Directory(d) => {

   184                     d.was_file.as_mut().map(|f| &mut f.entry)

   185                 }

   186                 NodeKind::File(f) => Some(&mut f.entry),

   187             };

   188         }

   189         None

   190     }

   191 

   192     /// Returns an iterator over the paths and corresponding entries in the

   193     /// tree.

   194     pub fn iter(&self) -> Iter {

   195         Iter::new(&self.root)

   196     }

   197 

   198     /// Returns an iterator of all entries in the tree, with a special

   199     /// filesystem handling for the directories containing said entries. See

   200     /// the documentation of `FsIter` for more.

   201     pub fn fs_iter(&self, root_dir: PathBuf) -> FsIter {

   202         FsIter::new(&self.root, root_dir)

   203     }

   204 

   205     /// Remove the entry at `path` and returns it, if it exists.

   206     pub fn remove(

   207         &mut self,

   208         path: impl AsRef<HgPath>,

   209     ) -> Option<DirstateEntry> {

   210         let RemoveResult { old_entry, .. } =

   211             self.root.remove(path.as_ref().as_bytes());

   212         self.files_count = self

   213             .files_count

   214             .checked_sub(if old_entry.is_some() { 1 } else { 0 })

   215             .expect("removed too many files");

   216         old_entry

   217     }

   218 }

   219 

   220 impl<P: AsRef<HgPath>> Extend<(P, DirstateEntry)> for Tree {

   221     fn extend<T: IntoIterator<Item = (P, DirstateEntry)>>(&mut self, iter: T) {

   222         for (path, entry) in iter {

   223             self.insert(path, entry);

   224         }

   225     }

   226 }

   227 

   228 impl<'a> IntoIterator for &'a Tree {

   229     type Item = (HgPathBuf, DirstateEntry);

   230     type IntoIter = Iter<'a>;

   231 

   232     fn into_iter(self) -> Self::IntoIter {

   233         self.iter()

   234     }

   235 }

   236 

   237 #[cfg(test)]

   238 mod tests {

   239     use super::*;

   240     use crate::dirstate::dirstate_tree::node::File;

   241     use crate::{EntryState, FastHashMap};

   242     use pretty_assertions::assert_eq;

   243 

   244     impl Node {

   245         /// Shortcut for getting children of a node in tests.

   246         fn children(&self) -> Option<&FastHashMap<Vec<u8>, Node>> {

   247             match &self.kind {

   248                 NodeKind::Directory(d) => Some(&d.children),

   249                 NodeKind::File(_) => None,

   250             }

   251         }

   252     }

   253 

   254     #[test]

   255     fn test_dirstate_tree() {

   256         let mut tree = Tree::new();

   257 

   258         assert_eq!(

   259             tree.insert_node(

   260                 HgPath::new(b"we/p"),

   261                 DirstateEntry {

   262                     state: EntryState::Normal,

   263                     mode: 0,

   264                     mtime: 0,

   265                     size: 0

   266                 }

   267             ),

   268             None

   269         );

   270         dbg!(&tree);

   271         assert!(tree.get_node(HgPath::new(b"we")).is_some());

   272         let entry = DirstateEntry {

   273             state: EntryState::Merged,

   274             mode: 41,

   275             mtime: 42,

   276             size: 43,

   277         };

   278         assert_eq!(tree.insert_node(HgPath::new(b"foo/bar"), entry), None);

   279         assert_eq!(

   280             tree.get_node(HgPath::new(b"foo/bar")),

   281             Some(&Node {

   282                 kind: NodeKind::File(File {

   283                     was_directory: None,

   284                     entry

   285                 })

   286             })

   287         );

   288         // We didn't override the first entry we made

   289         assert!(tree.get_node(HgPath::new(b"we")).is_some(),);

   290         // Inserting the same key again

   291         assert_eq!(

   292             tree.insert_node(HgPath::new(b"foo/bar"), entry),

   293             Some(Node {

   294                 kind: NodeKind::File(File {

   295                     was_directory: None,

   296                     entry

   297                 }),

   298             })

   299         );

   300         // Inserting the two levels deep

   301         assert_eq!(tree.insert_node(HgPath::new(b"foo/bar/baz"), entry), None);

   302         // Getting a file "inside a file" should return `None`

   303         assert_eq!(tree.get_node(HgPath::new(b"foo/bar/baz/bap"),), None);

   304 

   305         assert_eq!(

   306             tree.insert_node(HgPath::new(b"wasdir/subfile"), entry),

   307             None,

   308         );

   309         let removed_entry = DirstateEntry {

   310             state: EntryState::Removed,

   311             mode: 0,

   312             mtime: 0,

   313             size: 0,

   314         };

   315         assert!(tree

   316             .insert_node(HgPath::new(b"wasdir"), removed_entry)

   317             .is_some());

   318 

   319         assert_eq!(

   320             tree.get_node(HgPath::new(b"wasdir")),

   321             Some(&Node {

   322                 kind: NodeKind::File(File {

   323                     was_directory: Some(Box::new(Directory {

   324                         was_file: None,

   325                         children: [(

   326                             b"subfile".to_vec(),

   327                             Node {

   328                                 kind: NodeKind::File(File {

   329                                     was_directory: None,

   330                                     entry,

   331                                 })

   332                             }

   333                         )]

   334                         .to_vec()

   335                         .into_iter()

   336                         .collect()

   337                     })),

   338                     entry: removed_entry

   339                 })

   340             })

   341         );

   342 

   343         assert!(tree.get(HgPath::new(b"wasdir/subfile")).is_some())

   344     }

   345 

   346     #[test]

   347     fn test_insert_removed() {

   348         let mut tree = Tree::new();

   349         let entry = DirstateEntry {

   350             state: EntryState::Merged,

   351             mode: 1,

   352             mtime: 2,

   353             size: 3,

   354         };

   355         let removed_entry = DirstateEntry {

   356             state: EntryState::Removed,

   357             mode: 10,

   358             mtime: 20,

   359             size: 30,

   360         };

   361         assert_eq!(tree.insert_node(HgPath::new(b"foo"), entry), None);

   362         assert_eq!(

   363             tree.insert_node(HgPath::new(b"foo/a"), removed_entry),

   364             None

   365         );

   366         // The insert should not turn `foo` into a directory as `foo` is not

   367         // `Removed`.

   368         match tree.get_node(HgPath::new(b"foo")).unwrap().kind {

   369             NodeKind::Directory(_) => panic!("should be a file"),

   370             NodeKind::File(_) => {}

   371         }

   372 

   373         let mut tree = Tree::new();

   374         let entry = DirstateEntry {

   375             state: EntryState::Merged,

   376             mode: 1,

   377             mtime: 2,

   378             size: 3,

   379         };

   380         let removed_entry = DirstateEntry {

   381             state: EntryState::Removed,

   382             mode: 10,

   383             mtime: 20,

   384             size: 30,

   385         };

   386         // The insert *should* turn `foo` into a directory as it is `Removed`.

   387         assert_eq!(tree.insert_node(HgPath::new(b"foo"), removed_entry), None);

   388         assert_eq!(tree.insert_node(HgPath::new(b"foo/a"), entry), None);

   389         match tree.get_node(HgPath::new(b"foo")).unwrap().kind {

   390             NodeKind::Directory(_) => {}

   391             NodeKind::File(_) => panic!("should be a directory"),

   392         }

   393     }

   394 

   395     #[test]

   396     fn test_get() {

   397         let mut tree = Tree::new();

   398         let entry = DirstateEntry {

   399             state: EntryState::Merged,

   400             mode: 1,

   401             mtime: 2,

   402             size: 3,

   403         };

   404         assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);

   405         assert_eq!(tree.files_count, 1);

   406         assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry));

   407         assert_eq!(tree.get(HgPath::new(b"a/b")), None);

   408         assert_eq!(tree.get(HgPath::new(b"a")), None);

   409         assert_eq!(tree.get(HgPath::new(b"a/b/c/d")), None);

   410         let entry2 = DirstateEntry {

   411             state: EntryState::Removed,

   412             mode: 0,

   413             mtime: 5,

   414             size: 1,

   415         };

   416         // was_directory

   417         assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None);

   418         assert_eq!(tree.files_count, 2);

   419         assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2));

   420         assert_eq!(tree.get(HgPath::new(b"a/b/c")), Some(&entry));

   421 

   422         let mut tree = Tree::new();

   423 

   424         // was_file

   425         assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None);

   426         assert_eq!(tree.files_count, 1);

   427         assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None);

   428         assert_eq!(tree.files_count, 2);

   429         assert_eq!(tree.get(HgPath::new(b"a/b")), Some(&entry2));

   430     }

   431 

   432     #[test]

   433     fn test_get_mut() {

   434         let mut tree = Tree::new();

   435         let mut entry = DirstateEntry {

   436             state: EntryState::Merged,

   437             mode: 1,

   438             mtime: 2,

   439             size: 3,

   440         };

   441         assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);

   442         assert_eq!(tree.files_count, 1);

   443         assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry));

   444         assert_eq!(tree.get_mut(HgPath::new(b"a/b")), None);

   445         assert_eq!(tree.get_mut(HgPath::new(b"a")), None);

   446         assert_eq!(tree.get_mut(HgPath::new(b"a/b/c/d")), None);

   447         let mut entry2 = DirstateEntry {

   448             state: EntryState::Removed,

   449             mode: 0,

   450             mtime: 5,

   451             size: 1,

   452         };

   453         // was_directory

   454         assert_eq!(tree.insert(HgPath::new(b"a/b"), entry2), None);

   455         assert_eq!(tree.files_count, 2);

   456         assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2));

   457         assert_eq!(tree.get_mut(HgPath::new(b"a/b/c")), Some(&mut entry));

   458 

   459         let mut tree = Tree::new();

   460 

   461         // was_file

   462         assert_eq!(tree.insert_node(HgPath::new(b"a"), entry), None);

   463         assert_eq!(tree.files_count, 1);

   464         assert_eq!(tree.insert_node(HgPath::new(b"a/b"), entry2), None);

   465         assert_eq!(tree.files_count, 2);

   466         assert_eq!(tree.get_mut(HgPath::new(b"a/b")), Some(&mut entry2));

   467     }

   468 

   469     #[test]

   470     fn test_remove() {

   471         let mut tree = Tree::new();

   472         assert_eq!(tree.files_count, 0);

   473         assert_eq!(tree.remove(HgPath::new(b"foo")), None);

   474         assert_eq!(tree.files_count, 0);

   475 

   476         let entry = DirstateEntry {

   477             state: EntryState::Normal,

   478             mode: 0,

   479             mtime: 0,

   480             size: 0,

   481         };

   482         assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);

   483         assert_eq!(tree.files_count, 1);

   484 

   485         assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry));

   486         assert_eq!(tree.files_count, 0);

   487 

   488         assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None);

   489         assert_eq!(tree.insert_node(HgPath::new(b"a/b/y"), entry), None);

   490         assert_eq!(tree.insert_node(HgPath::new(b"a/b/z"), entry), None);

   491         assert_eq!(tree.insert_node(HgPath::new(b"x"), entry), None);

   492         assert_eq!(tree.insert_node(HgPath::new(b"y"), entry), None);

   493         assert_eq!(tree.files_count, 5);

   494 

   495         assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry));

   496         assert_eq!(tree.files_count, 4);

   497         assert_eq!(tree.remove(HgPath::new(b"a/b/x")), None);

   498         assert_eq!(tree.files_count, 4);

   499         assert_eq!(tree.remove(HgPath::new(b"a/b/y")), Some(entry));

   500         assert_eq!(tree.files_count, 3);

   501         assert_eq!(tree.remove(HgPath::new(b"a/b/z")), Some(entry));

   502         assert_eq!(tree.files_count, 2);

   503 

   504         assert_eq!(tree.remove(HgPath::new(b"x")), Some(entry));

   505         assert_eq!(tree.files_count, 1);

   506         assert_eq!(tree.remove(HgPath::new(b"y")), Some(entry));

   507         assert_eq!(tree.files_count, 0);

   508 

   509         // `a` should have been cleaned up, no more files anywhere in its

   510         // descendents

   511         assert_eq!(tree.get_node(HgPath::new(b"a")), None);

   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"), removed_entry), None);

   519         assert_eq!(tree.insert_node(HgPath::new(b"a/b/x"), entry), None);

   520         assert_eq!(tree.files_count, 2);

   521         dbg!(&tree);

   522         assert_eq!(tree.remove(HgPath::new(b"a")), Some(removed_entry));

   523         assert_eq!(tree.files_count, 1);

   524         dbg!(&tree);

   525         assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(entry));

   526         assert_eq!(tree.files_count, 0);

   527 

   528         // The entire tree should have been cleaned up, no more files anywhere

   529         // in its descendents

   530         assert_eq!(tree.root.children().unwrap().len(), 0);

   531 

   532         let removed_entry = DirstateEntry {

   533             state: EntryState::Removed,

   534             ..entry

   535         };

   536         assert_eq!(tree.insert(HgPath::new(b"a"), entry), None);

   537         assert_eq!(

   538             tree.insert_node(HgPath::new(b"a/b/x"), removed_entry),

   539             None

   540         );

   541         assert_eq!(tree.files_count, 2);

   542         dbg!(&tree);

   543         assert_eq!(tree.remove(HgPath::new(b"a")), Some(entry));

   544         assert_eq!(tree.files_count, 1);

   545         dbg!(&tree);

   546         assert_eq!(tree.remove(HgPath::new(b"a/b/x")), Some(removed_entry));

   547         assert_eq!(tree.files_count, 0);

   548 

   549         dbg!(&tree);

   550         // The entire tree should have been cleaned up, no more files anywhere

   551         // in its descendents

   552         assert_eq!(tree.root.children().unwrap().len(), 0);

   553 

   554         assert_eq!(tree.insert(HgPath::new(b"d"), entry), None);

   555         assert_eq!(tree.insert(HgPath::new(b"d/d/d"), entry), None);

   556         assert_eq!(tree.files_count, 2);

   557 

   558         // Deleting the nested file should not delete the top directory as it

   559         // used to be a file

   560         assert_eq!(tree.remove(HgPath::new(b"d/d/d")), Some(entry));

   561         assert_eq!(tree.files_count, 1);

   562         assert!(tree.get_node(HgPath::new(b"d")).is_some());

   563         assert!(tree.remove(HgPath::new(b"d")).is_some());

   564         assert_eq!(tree.files_count, 0);

   565 

   566         // Deleting the nested file should not delete the top file (other way

   567         // around from the last case)

   568         assert_eq!(tree.insert(HgPath::new(b"a/a"), entry), None);

   569         assert_eq!(tree.files_count, 1);

   570         assert_eq!(tree.insert(HgPath::new(b"a"), entry), None);

   571         assert_eq!(tree.files_count, 2);

   572         dbg!(&tree);

   573         assert_eq!(tree.remove(HgPath::new(b"a/a")), Some(entry));

   574         assert_eq!(tree.files_count, 1);

   575         dbg!(&tree);

   576         assert!(tree.get_node(HgPath::new(b"a")).is_some());

   577         assert!(tree.get_node(HgPath::new(b"a/a")).is_none());

   578     }

   579 

   580     #[test]

   581     fn test_was_directory() {

   582         let mut tree = Tree::new();

   583 

   584         let entry = DirstateEntry {

   585             state: EntryState::Removed,

   586             mode: 0,

   587             mtime: 0,

   588             size: 0,

   589         };

   590         assert_eq!(tree.insert_node(HgPath::new(b"a/b/c"), entry), None);

   591         assert_eq!(tree.files_count, 1);

   592 

   593         assert!(tree.insert_node(HgPath::new(b"a"), entry).is_some());

   594         let new_a = tree.root.children().unwrap().get(&b"a".to_vec()).unwrap();

   595 

   596         match &new_a.kind {

   597             NodeKind::Directory(_) => panic!(),

   598             NodeKind::File(f) => {

   599                 let dir = f.was_directory.clone().unwrap();

   600                 let c = dir

   601                     .children

   602                     .get(&b"b".to_vec())

   603                     .unwrap()

   604                     .children()

   605                     .unwrap()

   606                     .get(&b"c".to_vec())

   607                     .unwrap();

   608 

   609                 assert_eq!(

   610                     match &c.kind {

   611                         NodeKind::Directory(_) => panic!(),

   612                         NodeKind::File(f) => f.entry,

   613                     },

   614                     entry

   615                 );

   616             }

   617         }

   618         assert_eq!(tree.files_count, 2);

   619         dbg!(&tree);

   620         assert_eq!(tree.remove(HgPath::new(b"a/b/c")), Some(entry));

   621         assert_eq!(tree.files_count, 1);

   622         dbg!(&tree);

   623         let a = tree.get_node(HgPath::new(b"a")).unwrap();

   624         match &a.kind {

   625             NodeKind::Directory(_) => panic!(),

   626             NodeKind::File(f) => {

   627                 // Directory in `was_directory` was emptied, should be removed

   628                 assert_eq!(f.was_directory, None);

   629             }

   630         }

   631     }

   632     #[test]

   633     fn test_extend() {

   634         let insertions = [

   635             (

   636                 HgPathBuf::from_bytes(b"d"),

   637                 DirstateEntry {

   638                     state: EntryState::Added,

   639                     mode: 0,

   640                     mtime: -1,

   641                     size: -1,

   642                 },

   643             ),

   644             (

   645                 HgPathBuf::from_bytes(b"b"),

   646                 DirstateEntry {

   647                     state: EntryState::Normal,

   648                     mode: 33188,

   649                     mtime: 1599647984,

   650                     size: 2,

   651                 },

   652             ),

   653             (

   654                 HgPathBuf::from_bytes(b"a/a"),

   655                 DirstateEntry {

   656                     state: EntryState::Normal,

   657                     mode: 33188,

   658                     mtime: 1599647984,

   659                     size: 2,

   660                 },

   661             ),

   662             (

   663                 HgPathBuf::from_bytes(b"d/d/d"),

   664                 DirstateEntry {

   665                     state: EntryState::Removed,

   666                     mode: 0,

   667                     mtime: 0,

   668                     size: 0,

   669                 },

   670             ),

   671         ]

   672         .to_vec();

   673         let mut tree = Tree::new();

   674 

   675         tree.extend(insertions.clone().into_iter());

   676 

   677         for (path, _) in &insertions {

   678             assert!(tree.contains_key(path), true);

   679         }

   680         assert_eq!(tree.files_count, 4);

   681     }

   682 }