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 repeated(&mut self, entry: &Self::Entry) -> Result<(), 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 let Some(key) = walk.descend_key(&entry) {
if 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);
} else {
walk.repeated(&entry).map_err(E::from)?;
}
}
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(any(feature = "fat", feature = "exfat", feature = "apfs"))]
const ELIDED: &[u8] = "\u{2026}".as_bytes();
#[cfg(any(feature = "fat", feature = "exfat", feature = "apfs"))]
pub(crate) fn label(prefix: &[u8], name: &[u8]) -> Vec<u8> {
let mut label = Vec::with_capacity(prefix.len() + 1 + name.len());
label.extend_from_slice(prefix);
label.push(b'/');
label.extend_from_slice(name);
if label.len() <= MAX_PATH {
return label;
}
let tail = &label[label.len() - (MAX_PATH - ELIDED.len())..];
let from = tail.iter().position(|&b| b == b'/').unwrap_or(0);
let mut elided = Vec::with_capacity(ELIDED.len() + tail.len() - from);
elided.extend_from_slice(ELIDED);
elided.extend_from_slice(&tail[from..]);
elided
}
#[cfg(any(feature = "btrfs", feature = "apfs"))]
pub(crate) fn frontier<T, E>(
path: &[u8],
entries: impl IntoIterator<Item = (Vec<u8>, T)>,
hostile: impl Fn(Vec<u8>) -> E,
too_long: impl Fn(Vec<u8>) -> E,
) -> Result<Vec<(Vec<u8>, T)>, E> {
frontier_by(path, entries, hostile, |path, name| {
child_path(path, name).ok_or_else(|| {
let mut long = path.to_vec();
long.push(b'/');
long.extend_from_slice(name);
too_long(long)
})
})
}
#[cfg(feature = "apfs")]
pub(crate) fn labelled_frontier<T, E>(
prefix: &[u8],
entries: impl IntoIterator<Item = (Vec<u8>, T)>,
hostile: impl Fn(Vec<u8>) -> E,
) -> Result<Vec<(Vec<u8>, T)>, E> {
frontier_by(prefix, entries, hostile, |prefix, name| {
Ok(label(prefix, name))
})
}
#[cfg(any(feature = "btrfs", feature = "apfs"))]
fn frontier_by<T, E>(
prefix: &[u8],
entries: impl IntoIterator<Item = (Vec<u8>, T)>,
hostile: impl Fn(Vec<u8>) -> E,
join: impl Fn(&[u8], &[u8]) -> Result<Vec<u8>, E>,
) -> Result<Vec<(Vec<u8>, T)>, E> {
let mut out = Vec::new();
for (name, keep) in entries {
if crate::path::is_hostile_component(&name) {
return Err(hostile(name));
}
out.push((join(prefix, &name)?, keep));
}
out.reverse();
Ok(out)
}
#[cfg(test)]
mod tests {
use super::{Seed, Walk, child_path, drive};
use crate::policy::MAX_PATH;
struct Graph {
children: Vec<Vec<(&'static str, u32)>>,
refuse: bool,
repeats: Vec<Vec<u8>>,
}
impl Walk for Graph {
type Pending = (Vec<u8>, u32);
type Entry = (Vec<u8>, u32);
type Key = u32;
type Error = Vec<u8>;
fn cap(&mut self) -> usize {
100
}
fn seed(&mut self) -> Result<Seed<Self>, Vec<u8>> {
let root = (Vec::new(), 0);
Ok((self.children(&root)?, vec![0]))
}
fn resolve(&mut self, pending: (Vec<u8>, u32)) -> Result<(Vec<u8>, u32), Vec<u8>> {
Ok(pending)
}
fn descend_key(&self, entry: &(Vec<u8>, u32)) -> Option<u32> {
Some(entry.1)
}
fn children(&mut self, entry: &(Vec<u8>, u32)) -> Result<Vec<(Vec<u8>, u32)>, Vec<u8>> {
Ok(self.children[entry.1 as usize]
.iter()
.rev()
.map(|(name, number)| (child_path(&entry.0, name.as_bytes()).unwrap(), *number))
.collect())
}
fn repeated(&mut self, entry: &(Vec<u8>, u32)) -> Result<(), Vec<u8>> {
if self.refuse {
return Err(entry.0.clone());
}
self.repeats.push(entry.0.clone());
Ok(())
}
fn too_large(_: usize) -> Vec<u8> {
b"too large".to_vec()
}
}
#[test]
fn a_directory_reached_again_is_judged_by_the_family_and_never_descended_twice() {
let graph = |refuse| Graph {
children: vec![vec![("a", 1)], vec![("b", 0)]],
refuse,
repeats: Vec::new(),
};
let mut lenient = graph(false);
let mut seen = Vec::new();
drive(
&mut lenient,
|_, entry: (Vec<u8>, u32)| -> Result<(), Vec<u8>> {
seen.push(entry.0);
Ok(())
},
)
.expect("a lenient walk passes the repeat over");
assert_eq!(seen, vec![b"/a".to_vec(), b"/a/b".to_vec()]);
assert_eq!(lenient.repeats, vec![b"/a/b".to_vec()]);
let mut strict = graph(true);
let refused = drive(&mut strict, |_, _: (Vec<u8>, u32)| -> Result<(), Vec<u8>> {
Ok(())
});
assert_eq!(refused, Err(b"/a/b".to_vec()));
}
#[cfg(any(feature = "fat", feature = "exfat", feature = "apfs"))]
#[test]
fn a_label_is_the_path_to_the_bound_and_the_end_of_it_past_the_bound() {
use super::{ELIDED, label};
assert_eq!(label(b"", b"etc"), b"/etc");
assert_eq!(label(b"/etc", b"hostname"), b"/etc/hostname");
let at = vec![b'a'; MAX_PATH - 1];
assert_eq!(label(b"", &at).len(), MAX_PATH);
assert!(!label(b"", &at).starts_with(ELIDED));
let name = [b'n'; 100];
let mut path = Vec::new();
let mut labelled = Vec::new();
for _ in 0..50 {
path.push(b'/');
path.extend_from_slice(&name);
labelled = label(&labelled, &name);
assert!(labelled.len() <= MAX_PATH);
if path.len() <= MAX_PATH {
assert_eq!(labelled, path);
} else {
let rest = labelled.strip_prefix(ELIDED).expect("an elided label");
assert_eq!(
rest.first(),
Some(&b'/'),
"an elided label begins at a component"
);
assert!(path.ends_with(rest));
assert!(rest.len() + 1 + name.len() > MAX_PATH - ELIDED.len());
}
}
assert_eq!(path.len(), 50 * 101);
}
#[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);
}
}