use std::collections::HashSet;
use std::hash::Hash;
use crate::policy::MAX_PATH;
pub(crate) trait Walk {
type Pending;
type Entry;
type Key: Eq + Hash;
type Error;
fn cap(&mut self) -> usize;
fn seed(&mut self) -> Result<Seed<Self>, Self::Error>;
fn resolve(&mut self, pending: Self::Pending) -> Result<Self::Entry, Self::Error>;
fn descend_key(&self, entry: &Self::Entry) -> Option<Self::Key>;
fn children(&mut self, entry: &Self::Entry) -> Result<Vec<Self::Pending>, Self::Error>;
fn too_large(limit: usize) -> Self::Error;
}
pub(crate) type Seed<W> = (Vec<<W as Walk>::Pending>, Vec<<W as Walk>::Key>);
pub(crate) fn drive<W, E>(
walk: &mut W,
mut visit: impl FnMut(&mut W, W::Entry) -> Result<(), E>,
) -> Result<(), E>
where
W: Walk,
E: From<W::Error>,
{
let cap = walk.cap();
let mut seen = 0usize;
let mut visited: HashSet<W::Key> = HashSet::new();
let (mut stack, seeded) = walk.seed().map_err(E::from)?;
visited.extend(seeded);
if stack.len() > cap {
return Err(E::from(W::too_large(cap)));
}
while let Some(pending) = stack.pop() {
if seen >= cap {
return Err(E::from(W::too_large(cap)));
}
seen += 1;
let entry = walk.resolve(pending).map_err(E::from)?;
if walk
.descend_key(&entry)
.is_some_and(|key| visited.insert(key))
{
let children = walk.children(&entry).map_err(E::from)?;
if seen
.saturating_add(stack.len())
.saturating_add(children.len())
> cap
{
return Err(E::from(W::too_large(cap)));
}
stack.extend(children);
}
visit(walk, entry)?;
}
Ok(())
}
pub(crate) fn child_path(prefix: &[u8], name: &[u8]) -> Option<Vec<u8>> {
let mut path = Vec::with_capacity(prefix.len() + 1 + name.len());
path.extend_from_slice(prefix);
path.push(b'/');
path.extend_from_slice(name);
(path.len() <= MAX_PATH).then_some(path)
}
#[cfg(test)]
mod tests {
use super::child_path;
use crate::policy::MAX_PATH;
#[test]
fn a_child_path_joins_with_one_separator_and_stops_at_the_bound() {
assert_eq!(child_path(b"", b"etc").as_deref(), Some(&b"/etc"[..]));
assert_eq!(
child_path(b"/etc", b"hostname").as_deref(),
Some(&b"/etc/hostname"[..])
);
let deep = vec![b'a'; MAX_PATH - 1];
assert_eq!(child_path(b"", &deep).map(|p| p.len()), Some(MAX_PATH));
assert_eq!(child_path(b"", &vec![b'a'; MAX_PATH]), None);
}
}