1 // dirs_multiset.rs

     2 //

     3 // Copyright 2019 Raphaël Gomès <rgomes@octobus.net>

     4 //

     5 // This software may be used and distributed according to the terms of the

     6 // GNU General Public License version 2 or any later version.

     7 

     8 //! A multiset of directory names.

     9 //!

    10 //! Used to counts the references to directories in a manifest or dirstate.

    11 use std::collections::hash_map::Entry;

    12 use std::collections::HashMap;

    13 use std::ops::Deref;

    14 use {DirsIterable, DirstateEntry, DirstateMapError};

    15 

    16 #[derive(PartialEq, Debug)]

    17 pub struct DirsMultiset {

    18     inner: HashMap<Vec<u8>, u32>,

    19 }

    20 

    21 impl Deref for DirsMultiset {

    22     type Target = HashMap<Vec<u8>, u32>;

    23 

    24     fn deref(&self) -> &Self::Target {

    25         &self.inner

    26     }

    27 }

    28 

    29 impl DirsMultiset {

    30     /// Initializes the multiset from a dirstate or a manifest.

    31     ///

    32     /// If `skip_state` is provided, skips dirstate entries with equal state.

    33     pub fn new(iterable: DirsIterable, skip_state: Option<i8>) -> Self {

    34         let mut multiset = DirsMultiset {

    35             inner: HashMap::new(),

    36         };

    37 

    38         match iterable {

    39             DirsIterable::Dirstate(vec) => {

    40                 for (ref filename, DirstateEntry { state, .. }) in vec {

    41                     // This `if` is optimized out of the loop

    42                     if let Some(skip) = skip_state {

    43                         if skip != state {

    44                             multiset.add_path(filename);

    45                         }

    46                     } else {

    47                         multiset.add_path(filename);

    48                     }

    49                 }

    50             }

    51             DirsIterable::Manifest(vec) => {

    52                 for ref filename in vec {

    53                     multiset.add_path(filename);

    54                 }

    55             }

    56         }

    57 

    58         multiset

    59     }

    60 

    61     /// Returns the slice up to the next directory name from right to left,

    62     /// without trailing slash

    63     fn find_dir(path: &[u8]) -> &[u8] {

    64         let mut path = path;

    65         loop {

    66             if let Some(new_pos) = path.len().checked_sub(1) {

    67                 if path[new_pos] == b'/' {

    68                     break &path[..new_pos];

    69                 }

    70                 path = &path[..new_pos];

    71             } else {

    72                 break &[];

    73             }

    74         }

    75     }

    76 

    77     /// Increases the count of deepest directory contained in the path.

    78     ///

    79     /// If the directory is not yet in the map, adds its parents.

    80     pub fn add_path(&mut self, path: &[u8]) {

    81         let mut pos = path.len();

    82 

    83         loop {

    84             let subpath = Self::find_dir(&path[..pos]);

    85             if let Some(val) = self.inner.get_mut(subpath) {

    86                 *val += 1;

    87                 break;

    88             }

    89             self.inner.insert(subpath.to_owned(), 1);

    90 

    91             pos = subpath.len();

    92             if pos == 0 {

    93                 break;

    94             }

    95         }

    96     }

    97 

    98     /// Decreases the count of deepest directory contained in the path.

    99     ///

   100     /// If it is the only reference, decreases all parents until one is

   101     /// removed.

   102     /// If the directory is not in the map, something horrible has happened.

   103     pub fn delete_path(

   104         &mut self,

   105         path: &[u8],

   106     ) -> Result<(), DirstateMapError> {

   107         let mut pos = path.len();

   108 

   109         loop {

   110             let subpath = Self::find_dir(&path[..pos]);

   111             match self.inner.entry(subpath.to_owned()) {

   112                 Entry::Occupied(mut entry) => {

   113                     let val = entry.get().clone();

   114                     if val > 1 {

   115                         entry.insert(val - 1);

   116                         break;

   117                     }

   118                     entry.remove();

   119                 }

   120                 Entry::Vacant(_) => {

   121                     return Err(DirstateMapError::PathNotFound(path.to_owned()))

   122                 }

   123             };

   124 

   125             pos = subpath.len();

   126             if pos == 0 {

   127                 break;

   128             }

   129         }

   130 

   131         Ok(())

   132     }

   133 }

   134 

   135 #[cfg(test)]

   136 mod tests {

   137     use super::*;

   138 

   139     #[test]

   140     fn test_delete_path_path_not_found() {

   141         let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None);

   142         let path = b"doesnotexist/";

   143         assert_eq!(

   144             Err(DirstateMapError::PathNotFound(path.to_vec())),

   145             map.delete_path(path)

   146         );

   147     }

   148 

   149     #[test]

   150     fn test_delete_path_empty_path() {

   151         let mut map =

   152             DirsMultiset::new(DirsIterable::Manifest(vec![vec![]]), None);

   153         let path = b"";

   154         assert_eq!(Ok(()), map.delete_path(path));

   155         assert_eq!(

   156             Err(DirstateMapError::PathNotFound(path.to_vec())),

   157             map.delete_path(path)

   158         );

   159     }

   160 

   161     #[test]

   162     fn test_delete_path_successful() {

   163         let mut map = DirsMultiset {

   164             inner: [("", 5), ("a", 3), ("a/b", 2), ("a/c", 1)]

   165                 .iter()

   166                 .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   167                 .collect(),

   168         };

   169 

   170         assert_eq!(Ok(()), map.delete_path(b"a/b/"));

   171         assert_eq!(Ok(()), map.delete_path(b"a/b/"));

   172         assert_eq!(

   173             Err(DirstateMapError::PathNotFound(b"a/b/".to_vec())),

   174             map.delete_path(b"a/b/")

   175         );

   176 

   177         assert_eq!(2, *map.get(&b"a".to_vec()).unwrap());

   178         assert_eq!(1, *map.get(&b"a/c".to_vec()).unwrap());

   179         eprintln!("{:?}", map);

   180         assert_eq!(Ok(()), map.delete_path(b"a/"));

   181         eprintln!("{:?}", map);

   182 

   183         assert_eq!(Ok(()), map.delete_path(b"a/c/"));

   184         assert_eq!(

   185             Err(DirstateMapError::PathNotFound(b"a/c/".to_vec())),

   186             map.delete_path(b"a/c/")

   187         );

   188     }

   189 

   190     #[test]

   191     fn test_add_path_empty_path() {

   192         let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None);

   193         let path = b"";

   194         map.add_path(path);

   195 

   196         assert_eq!(1, map.len());

   197     }

   198 

   199     #[test]

   200     fn test_add_path_successful() {

   201         let mut map = DirsMultiset::new(DirsIterable::Manifest(vec![]), None);

   202 

   203         map.add_path(b"a/");

   204         assert_eq!(1, *map.get(&b"a".to_vec()).unwrap());

   205         assert_eq!(1, *map.get(&Vec::new()).unwrap());

   206         assert_eq!(2, map.len());

   207 

   208         // Non directory should be ignored

   209         map.add_path(b"a");

   210         assert_eq!(1, *map.get(&b"a".to_vec()).unwrap());

   211         assert_eq!(2, map.len());

   212 

   213         // Non directory will still add its base

   214         map.add_path(b"a/b");

   215         assert_eq!(2, *map.get(&b"a".to_vec()).unwrap());

   216         assert_eq!(2, map.len());

   217 

   218         // Duplicate path works

   219         map.add_path(b"a/");

   220         assert_eq!(3, *map.get(&b"a".to_vec()).unwrap());

   221 

   222         // Nested dir adds to its base

   223         map.add_path(b"a/b/");

   224         assert_eq!(4, *map.get(&b"a".to_vec()).unwrap());

   225         assert_eq!(1, *map.get(&b"a/b".to_vec()).unwrap());

   226 

   227         // but not its base's base, because it already existed

   228         map.add_path(b"a/b/c/");

   229         assert_eq!(4, *map.get(&b"a".to_vec()).unwrap());

   230         assert_eq!(2, *map.get(&b"a/b".to_vec()).unwrap());

   231 

   232         map.add_path(b"a/c/");

   233         assert_eq!(1, *map.get(&b"a/c".to_vec()).unwrap());

   234 

   235         let expected = DirsMultiset {

   236             inner: [("", 2), ("a", 5), ("a/b", 2), ("a/b/c", 1), ("a/c", 1)]

   237                 .iter()

   238                 .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   239                 .collect(),

   240         };

   241         assert_eq!(map, expected);

   242     }

   243 

   244     #[test]

   245     fn test_dirsmultiset_new_empty() {

   246         use DirsIterable::{Dirstate, Manifest};

   247 

   248         let new = DirsMultiset::new(Manifest(vec![]), None);

   249         let expected = DirsMultiset {

   250             inner: HashMap::new(),

   251         };

   252         assert_eq!(expected, new);

   253 

   254         let new = DirsMultiset::new(Dirstate(vec![]), None);

   255         let expected = DirsMultiset {

   256             inner: HashMap::new(),

   257         };

   258         assert_eq!(expected, new);

   259     }

   260 

   261     #[test]

   262     fn test_dirsmultiset_new_no_skip() {

   263         use DirsIterable::{Dirstate, Manifest};

   264 

   265         let input_vec = ["a/", "b/", "a/c", "a/d/"]

   266             .iter()

   267             .map(|e| e.as_bytes().to_vec())

   268             .collect();

   269         let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)]

   270             .iter()

   271             .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   272             .collect();

   273 

   274         let new = DirsMultiset::new(Manifest(input_vec), None);

   275         let expected = DirsMultiset {

   276             inner: expected_inner,

   277         };

   278         assert_eq!(expected, new);

   279 

   280         let input_map = ["a/", "b/", "a/c", "a/d/"]

   281             .iter()

   282             .map(|f| {

   283                 (

   284                     f.as_bytes().to_vec(),

   285                     DirstateEntry {

   286                         state: 0,

   287                         mode: 0,

   288                         mtime: 0,

   289                         size: 0,

   290                     },

   291                 )

   292             })

   293             .collect();

   294         let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)]

   295             .iter()

   296             .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   297             .collect();

   298 

   299         let new = DirsMultiset::new(Dirstate(input_map), None);

   300         let expected = DirsMultiset {

   301             inner: expected_inner,

   302         };

   303         assert_eq!(expected, new);

   304     }

   305 

   306     #[test]

   307     fn test_dirsmultiset_new_skip() {

   308         use DirsIterable::{Dirstate, Manifest};

   309 

   310         let input_vec = ["a/", "b/", "a/c", "a/d/"]

   311             .iter()

   312             .map(|e| e.as_bytes().to_vec())

   313             .collect();

   314         let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)]

   315             .iter()

   316             .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   317             .collect();

   318 

   319         let new = DirsMultiset::new(Manifest(input_vec), Some('n' as i8));

   320         let expected = DirsMultiset {

   321             inner: expected_inner,

   322         };

   323         // Skip does not affect a manifest

   324         assert_eq!(expected, new);

   325 

   326         let input_map =

   327             [("a/", 'n'), ("a/b/", 'n'), ("a/c", 'r'), ("a/d/", 'm')]

   328                 .iter()

   329                 .map(|(f, state)| {

   330                     (

   331                         f.as_bytes().to_vec(),

   332                         DirstateEntry {

   333                             state: *state as i8,

   334                             mode: 0,

   335                             mtime: 0,

   336                             size: 0,

   337                         },

   338                     )

   339                 })

   340                 .collect();

   341 

   342         // "a" incremented with "a/c" and "a/d/"

   343         let expected_inner = [("", 1), ("a", 2), ("a/d", 1)]

   344             .iter()

   345             .map(|(k, v)| (k.as_bytes().to_vec(), *v))

   346             .collect();

   347 

   348         let new = DirsMultiset::new(Dirstate(input_map), Some('n' as i8));

   349         let expected = DirsMultiset {

   350             inner: expected_inner,

   351         };

   352         assert_eq!(expected, new);

   353     }

   354 

   355 }