dirs_multiset.rs
422 lines
| 13.1 KiB
| application/rls-services+xml
|
RustLexer
|
r42736 | // dirs_multiset.rs | ||
// | ||||
// Copyright 2019 Raphaël Gomès <rgomes@octobus.net> | ||||
// | ||||
// This software may be used and distributed according to the terms of the | ||||
// GNU General Public License version 2 or any later version. | ||||
//! A multiset of directory names. | ||||
//! | ||||
//! Used to counts the references to directories in a manifest or dirstate. | ||||
|
r42994 | use crate::{ | ||
|
r44739 | dirstate::EntryState, | ||
utils::{ | ||||
files, | ||||
|
r44765 | hg_path::{HgPath, HgPathBuf, HgPathError}, | ||
|
r44739 | }, | ||
|
r47863 | DirstateEntry, DirstateMapError, FastHashMap, | ||
|
r42994 | }; | ||
|
r44739 | use std::collections::{hash_map, hash_map::Entry, HashMap, HashSet}; | ||
|
r42736 | |||
|
r43155 | // could be encapsulated if we care API stability more seriously | ||
|
r43227 | pub type DirsMultisetIter<'a> = hash_map::Keys<'a, HgPathBuf, u32>; | ||
|
r43155 | |||
|
r42736 | #[derive(PartialEq, Debug)] | ||
pub struct DirsMultiset { | ||||
|
r44278 | inner: FastHashMap<HgPathBuf, u32>, | ||
|
r42736 | } | ||
impl DirsMultiset { | ||||
|
r43070 | /// Initializes the multiset from a dirstate. | ||
|
r42736 | /// | ||
/// If `skip_state` is provided, skips dirstate entries with equal state. | ||||
|
r47863 | pub fn from_dirstate<'a>( | ||
dirstate: impl IntoIterator<Item = (&'a HgPathBuf, &'a DirstateEntry)>, | ||||
|
r42994 | skip_state: Option<EntryState>, | ||
|
r44315 | ) -> Result<Self, DirstateMapError> { | ||
|
r42736 | let mut multiset = DirsMultiset { | ||
|
r44278 | inner: FastHashMap::default(), | ||
|
r42736 | }; | ||
|
r47863 | for (filename, DirstateEntry { state, .. }) in dirstate { | ||
|
r43070 | // This `if` is optimized out of the loop | ||
if let Some(skip) = skip_state { | ||||
if skip != *state { | ||||
|
r44315 | multiset.add_path(filename)?; | ||
|
r42736 | } | ||
|
r43070 | } else { | ||
|
r44315 | multiset.add_path(filename)?; | ||
|
r42736 | } | ||
} | ||||
|
r44315 | Ok(multiset) | ||
|
r42736 | } | ||
|
r43070 | /// Initializes the multiset from a manifest. | ||
|
r44315 | pub fn from_manifest( | ||
manifest: &[impl AsRef<HgPath>], | ||||
) -> Result<Self, DirstateMapError> { | ||||
|
r43070 | let mut multiset = DirsMultiset { | ||
|
r44278 | inner: FastHashMap::default(), | ||
|
r43070 | }; | ||
|
r44283 | for filename in manifest { | ||
|
r44315 | multiset.add_path(filename.as_ref())?; | ||
|
r43070 | } | ||
|
r44315 | Ok(multiset) | ||
|
r43070 | } | ||
|
r42736 | /// Increases the count of deepest directory contained in the path. | ||
/// | ||||
/// If the directory is not yet in the map, adds its parents. | ||||
|
r44283 | pub fn add_path( | ||
&mut self, | ||||
path: impl AsRef<HgPath>, | ||||
) -> Result<(), DirstateMapError> { | ||||
for subpath in files::find_dirs(path.as_ref()) { | ||||
|
r44227 | if subpath.as_bytes().last() == Some(&b'/') { | ||
// TODO Remove this once PathAuditor is certified | ||||
// as the only entrypoint for path data | ||||
|
r44765 | let second_slash_index = subpath.len() - 1; | ||
return Err(DirstateMapError::InvalidPath( | ||||
HgPathError::ConsecutiveSlashes { | ||||
bytes: path.as_ref().as_bytes().to_owned(), | ||||
second_slash_index, | ||||
}, | ||||
)); | ||||
|
r44227 | } | ||
|
r42736 | if let Some(val) = self.inner.get_mut(subpath) { | ||
*val += 1; | ||||
break; | ||||
} | ||||
self.inner.insert(subpath.to_owned(), 1); | ||||
} | ||||
|
r44227 | Ok(()) | ||
|
r42736 | } | ||
/// Decreases the count of deepest directory contained in the path. | ||||
/// | ||||
/// If it is the only reference, decreases all parents until one is | ||||
/// removed. | ||||
/// If the directory is not in the map, something horrible has happened. | ||||
pub fn delete_path( | ||||
&mut self, | ||||
|
r44283 | path: impl AsRef<HgPath>, | ||
|
r42736 | ) -> Result<(), DirstateMapError> { | ||
|
r44283 | for subpath in files::find_dirs(path.as_ref()) { | ||
|
r42736 | match self.inner.entry(subpath.to_owned()) { | ||
Entry::Occupied(mut entry) => { | ||||
|
r45500 | let val = *entry.get(); | ||
|
r42736 | if val > 1 { | ||
entry.insert(val - 1); | ||||
break; | ||||
} | ||||
entry.remove(); | ||||
} | ||||
Entry::Vacant(_) => { | ||||
|
r42760 | return Err(DirstateMapError::PathNotFound( | ||
|
r44283 | path.as_ref().to_owned(), | ||
|
r42760 | )) | ||
|
r42736 | } | ||
}; | ||||
} | ||||
Ok(()) | ||||
} | ||||
|
r42762 | |||
|
r44283 | pub fn contains(&self, key: impl AsRef<HgPath>) -> bool { | ||
self.inner.contains_key(key.as_ref()) | ||||
|
r42762 | } | ||
|
r43155 | pub fn iter(&self) -> DirsMultisetIter { | ||
|
r42995 | self.inner.keys() | ||
|
r42762 | } | ||
pub fn len(&self) -> usize { | ||||
self.inner.len() | ||||
} | ||||
|
r45500 | |||
pub fn is_empty(&self) -> bool { | ||||
self.len() == 0 | ||||
} | ||||
|
r42736 | } | ||
|
r44739 | /// This is basically a reimplementation of `DirsMultiset` that stores the | ||
/// children instead of just a count of them, plus a small optional | ||||
/// optimization to avoid some directories we don't need. | ||||
#[derive(PartialEq, Debug)] | ||||
pub struct DirsChildrenMultiset<'a> { | ||||
inner: FastHashMap<&'a HgPath, HashSet<&'a HgPath>>, | ||||
only_include: Option<HashSet<&'a HgPath>>, | ||||
} | ||||
impl<'a> DirsChildrenMultiset<'a> { | ||||
pub fn new( | ||||
paths: impl Iterator<Item = &'a HgPathBuf>, | ||||
only_include: Option<&'a HashSet<impl AsRef<HgPath> + 'a>>, | ||||
) -> Self { | ||||
let mut new = Self { | ||||
inner: HashMap::default(), | ||||
only_include: only_include | ||||
|
r45500 | .map(|s| s.iter().map(AsRef::as_ref).collect()), | ||
|
r44739 | }; | ||
for path in paths { | ||||
new.add_path(path) | ||||
} | ||||
new | ||||
} | ||||
fn add_path(&mut self, path: &'a (impl AsRef<HgPath> + 'a)) { | ||||
if path.as_ref().is_empty() { | ||||
return; | ||||
} | ||||
for (directory, basename) in files::find_dirs_with_base(path.as_ref()) | ||||
{ | ||||
if !self.is_dir_included(directory) { | ||||
continue; | ||||
} | ||||
self.inner | ||||
.entry(directory) | ||||
.and_modify(|e| { | ||||
e.insert(basename); | ||||
}) | ||||
.or_insert_with(|| { | ||||
let mut set = HashSet::new(); | ||||
set.insert(basename); | ||||
set | ||||
}); | ||||
} | ||||
} | ||||
fn is_dir_included(&self, dir: impl AsRef<HgPath>) -> bool { | ||||
match &self.only_include { | ||||
None => false, | ||||
Some(i) => i.contains(dir.as_ref()), | ||||
} | ||||
} | ||||
pub fn get( | ||||
&self, | ||||
path: impl AsRef<HgPath>, | ||||
) -> Option<&HashSet<&'a HgPath>> { | ||||
self.inner.get(path.as_ref()) | ||||
} | ||||
} | ||||
|
r42736 | #[cfg(test)] | ||
mod tests { | ||||
use super::*; | ||||
|
r47863 | use crate::StateMap; | ||
|
r42736 | |||
#[test] | ||||
fn test_delete_path_path_not_found() { | ||||
|
r44283 | let manifest: Vec<HgPathBuf> = vec![]; | ||
|
r44315 | let mut map = DirsMultiset::from_manifest(&manifest).unwrap(); | ||
|
r43227 | let path = HgPathBuf::from_bytes(b"doesnotexist/"); | ||
|
r42736 | assert_eq!( | ||
|
r43227 | Err(DirstateMapError::PathNotFound(path.to_owned())), | ||
map.delete_path(&path) | ||||
|
r42736 | ); | ||
} | ||||
#[test] | ||||
fn test_delete_path_empty_path() { | ||||
|
r44315 | let mut map = | ||
DirsMultiset::from_manifest(&vec![HgPathBuf::new()]).unwrap(); | ||||
|
r43227 | let path = HgPath::new(b""); | ||
|
r42736 | assert_eq!(Ok(()), map.delete_path(path)); | ||
assert_eq!( | ||||
|
r43227 | Err(DirstateMapError::PathNotFound(path.to_owned())), | ||
|
r42736 | map.delete_path(path) | ||
); | ||||
} | ||||
#[test] | ||||
fn test_delete_path_successful() { | ||||
let mut map = DirsMultiset { | ||||
inner: [("", 5), ("a", 3), ("a/b", 2), ("a/c", 1)] | ||||
.iter() | ||||
|
r43227 | .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v)) | ||
|
r42736 | .collect(), | ||
}; | ||||
|
r43227 | assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/b/"))); | ||
eprintln!("{:?}", map); | ||||
assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/b/"))); | ||||
eprintln!("{:?}", map); | ||||
|
r42736 | assert_eq!( | ||
|
r43227 | Err(DirstateMapError::PathNotFound(HgPathBuf::from_bytes( | ||
b"a/b/" | ||||
))), | ||||
map.delete_path(HgPath::new(b"a/b/")) | ||||
|
r42736 | ); | ||
|
r43227 | assert_eq!(2, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
assert_eq!(1, *map.inner.get(HgPath::new(b"a/c")).unwrap()); | ||||
|
r42736 | eprintln!("{:?}", map); | ||
|
r43227 | assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/"))); | ||
|
r42736 | eprintln!("{:?}", map); | ||
|
r43227 | assert_eq!(Ok(()), map.delete_path(HgPath::new(b"a/c/"))); | ||
|
r42736 | assert_eq!( | ||
|
r43227 | Err(DirstateMapError::PathNotFound(HgPathBuf::from_bytes( | ||
b"a/c/" | ||||
))), | ||||
map.delete_path(HgPath::new(b"a/c/")) | ||||
|
r42736 | ); | ||
} | ||||
#[test] | ||||
fn test_add_path_empty_path() { | ||||
|
r44283 | let manifest: Vec<HgPathBuf> = vec![]; | ||
|
r44315 | let mut map = DirsMultiset::from_manifest(&manifest).unwrap(); | ||
|
r43227 | let path = HgPath::new(b""); | ||
|
r44342 | map.add_path(path).unwrap(); | ||
|
r42736 | |||
assert_eq!(1, map.len()); | ||||
} | ||||
#[test] | ||||
fn test_add_path_successful() { | ||||
|
r44283 | let manifest: Vec<HgPathBuf> = vec![]; | ||
|
r44315 | let mut map = DirsMultiset::from_manifest(&manifest).unwrap(); | ||
|
r42736 | |||
|
r44342 | map.add_path(HgPath::new(b"a/")).unwrap(); | ||
|
r43227 | assert_eq!(1, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
assert_eq!(1, *map.inner.get(HgPath::new(b"")).unwrap()); | ||||
|
r42736 | assert_eq!(2, map.len()); | ||
// Non directory should be ignored | ||||
|
r44342 | map.add_path(HgPath::new(b"a")).unwrap(); | ||
|
r43227 | assert_eq!(1, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
|
r42736 | assert_eq!(2, map.len()); | ||
// Non directory will still add its base | ||||
|
r44342 | map.add_path(HgPath::new(b"a/b")).unwrap(); | ||
|
r43227 | assert_eq!(2, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
|
r42736 | assert_eq!(2, map.len()); | ||
// Duplicate path works | ||||
|
r44342 | map.add_path(HgPath::new(b"a/")).unwrap(); | ||
|
r43227 | assert_eq!(3, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
|
r42736 | |||
// Nested dir adds to its base | ||||
|
r44342 | map.add_path(HgPath::new(b"a/b/")).unwrap(); | ||
|
r43227 | assert_eq!(4, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
assert_eq!(1, *map.inner.get(HgPath::new(b"a/b")).unwrap()); | ||||
|
r42736 | |||
// but not its base's base, because it already existed | ||||
|
r44342 | map.add_path(HgPath::new(b"a/b/c/")).unwrap(); | ||
|
r43227 | assert_eq!(4, *map.inner.get(HgPath::new(b"a")).unwrap()); | ||
assert_eq!(2, *map.inner.get(HgPath::new(b"a/b")).unwrap()); | ||||
|
r42736 | |||
|
r44342 | map.add_path(HgPath::new(b"a/c/")).unwrap(); | ||
|
r43227 | assert_eq!(1, *map.inner.get(HgPath::new(b"a/c")).unwrap()); | ||
|
r42736 | |||
let expected = DirsMultiset { | ||||
inner: [("", 2), ("a", 5), ("a/b", 2), ("a/b/c", 1), ("a/c", 1)] | ||||
.iter() | ||||
|
r43227 | .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v)) | ||
|
r42736 | .collect(), | ||
}; | ||||
assert_eq!(map, expected); | ||||
} | ||||
#[test] | ||||
fn test_dirsmultiset_new_empty() { | ||||
|
r44283 | let manifest: Vec<HgPathBuf> = vec![]; | ||
|
r44315 | let new = DirsMultiset::from_manifest(&manifest).unwrap(); | ||
|
r42736 | let expected = DirsMultiset { | ||
|
r44278 | inner: FastHashMap::default(), | ||
|
r42736 | }; | ||
assert_eq!(expected, new); | ||||
|
r46185 | let new = | ||
DirsMultiset::from_dirstate(&StateMap::default(), None).unwrap(); | ||||
|
r42736 | let expected = DirsMultiset { | ||
|
r44278 | inner: FastHashMap::default(), | ||
|
r42736 | }; | ||
assert_eq!(expected, new); | ||||
} | ||||
#[test] | ||||
fn test_dirsmultiset_new_no_skip() { | ||||
|
r44283 | let input_vec: Vec<HgPathBuf> = ["a/", "b/", "a/c", "a/d/"] | ||
|
r42736 | .iter() | ||
|
r43227 | .map(|e| HgPathBuf::from_bytes(e.as_bytes())) | ||
|
r42736 | .collect(); | ||
let expected_inner = [("", 2), ("a", 3), ("b", 1), ("a/d", 1)] | ||||
.iter() | ||||
|
r43227 | .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v)) | ||
|
r42736 | .collect(); | ||
|
r44315 | let new = DirsMultiset::from_manifest(&input_vec).unwrap(); | ||
|
r42736 | let expected = DirsMultiset { | ||
inner: expected_inner, | ||||
}; | ||||
assert_eq!(expected, new); | ||||
|
r47863 | let input_map: HashMap<_, _> = ["b/x", "a/c", "a/d/x"] | ||
|
r42736 | .iter() | ||
.map(|f| { | ||||
( | ||||
|
r43227 | HgPathBuf::from_bytes(f.as_bytes()), | ||
|
r42736 | DirstateEntry { | ||
|
r42994 | state: EntryState::Normal, | ||
|
r42736 | mode: 0, | ||
mtime: 0, | ||||
size: 0, | ||||
}, | ||||
) | ||||
}) | ||||
.collect(); | ||||
|
r46185 | let expected_inner = [("", 2), ("a", 2), ("b", 1), ("a/d", 1)] | ||
|
r42736 | .iter() | ||
|
r43227 | .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v)) | ||
|
r42736 | .collect(); | ||
|
r44315 | let new = DirsMultiset::from_dirstate(&input_map, None).unwrap(); | ||
|
r42736 | let expected = DirsMultiset { | ||
inner: expected_inner, | ||||
}; | ||||
assert_eq!(expected, new); | ||||
} | ||||
#[test] | ||||
fn test_dirsmultiset_new_skip() { | ||||
|
r47863 | let input_map: HashMap<_, _> = [ | ||
|
r42994 | ("a/", EntryState::Normal), | ||
|
r46185 | ("a/b", EntryState::Normal), | ||
|
r42994 | ("a/c", EntryState::Removed), | ||
|
r46185 | ("a/d", EntryState::Merged), | ||
|
r42994 | ] | ||
.iter() | ||||
.map(|(f, state)| { | ||||
( | ||||
|
r43227 | HgPathBuf::from_bytes(f.as_bytes()), | ||
|
r42994 | DirstateEntry { | ||
state: *state, | ||||
mode: 0, | ||||
mtime: 0, | ||||
size: 0, | ||||
}, | ||||
) | ||||
}) | ||||
.collect(); | ||||
|
r42736 | |||
// "a" incremented with "a/c" and "a/d/" | ||||
|
r46185 | let expected_inner = [("", 1), ("a", 2)] | ||
|
r42736 | .iter() | ||
|
r43227 | .map(|(k, v)| (HgPathBuf::from_bytes(k.as_bytes()), *v)) | ||
|
r42736 | .collect(); | ||
|
r42994 | let new = | ||
|
r44315 | DirsMultiset::from_dirstate(&input_map, Some(EntryState::Normal)) | ||
.unwrap(); | ||||
|
r42736 | let expected = DirsMultiset { | ||
inner: expected_inner, | ||||
}; | ||||
assert_eq!(expected, new); | ||||
} | ||||
} | ||||