use std::collections::VecDeque;
use crate::path::canonical_parts;
use crate::policy::MAX_SYMLINK_HOPS;
pub(crate) trait Resolve {
type Ancestor: Copy;
type Node;
type Error;
fn root_node(&mut self) -> Result<Self::Node, Self::Error>;
fn ancestor_of(&self, node: &Self::Node) -> Self::Ancestor;
fn node_at(&mut self, ancestor: Self::Ancestor) -> Result<Self::Node, Self::Error>;
fn is_directory(&self, node: &Self::Node) -> bool;
fn find_name(
&mut self,
dir: &Self::Node,
name: &[u8],
) -> Result<Option<Self::Node>, Self::Error>;
fn read_link(
&mut self,
node: &Self::Node,
path: &[u8],
) -> Result<Option<Vec<u8>>, Self::Error> {
let (_, _) = (node, path);
Ok(None)
}
fn not_found(&self, path: &[u8]) -> Self::Error;
fn not_a_directory(&self, node: &Self::Node, path: &[u8]) -> Self::Error;
fn too_many_links(&self, path: &[u8]) -> Self::Error {
self.not_found(path)
}
}
pub(crate) fn drive<R>(reader: &mut R, path: &[u8], follow_final: bool) -> Result<R::Node, R::Error>
where
R: Resolve,
{
let mut pending: VecDeque<Vec<u8>> = canonical_parts(path)
.into_iter()
.map(<[u8]>::to_vec)
.collect();
let mut node = reader.root_node()?;
let mut descended: Vec<R::Ancestor> = Vec::new();
let mut hops = 0u32;
while let Some(part) = pending.pop_front() {
if !reader.is_directory(&node) {
return Err(reader.not_a_directory(&node, path));
}
if part == b".." {
if let Some(ancestor) = descended.pop() {
node = reader.node_at(ancestor)?;
}
continue;
}
let Some(next) = reader.find_name(&node, &part)? else {
return Err(reader.not_found(path));
};
if let Some(target) = (follow_final || !pending.is_empty())
.then(|| reader.read_link(&next, path))
.transpose()?
.flatten()
{
hops += 1;
if hops > MAX_SYMLINK_HOPS {
return Err(reader.too_many_links(path));
}
if target.is_empty() {
return Err(reader.not_found(path));
}
if target.starts_with(b"/") {
descended.clear();
node = reader.root_node()?;
}
for component in canonical_parts(&target).into_iter().rev() {
pending.push_front(component.to_vec());
}
continue;
}
descended.push(reader.ancestor_of(&node));
node = next;
}
Ok(node)
}
#[cfg(test)]
mod tests {
use super::*;
struct Tiny {
nodes: Vec<Kind>,
}
#[derive(Clone)]
enum Kind {
Dir(Vec<(&'static [u8], usize)>),
File,
Link(&'static [u8]),
}
#[derive(Debug, PartialEq, Eq)]
enum Refused {
NotFound,
NotADirectory,
TooManyLinks,
}
impl Resolve for Tiny {
type Ancestor = usize;
type Node = usize;
type Error = Refused;
fn root_node(&mut self) -> Result<usize, Refused> {
Ok(0)
}
fn ancestor_of(&self, node: &usize) -> usize {
*node
}
fn node_at(&mut self, ancestor: usize) -> Result<usize, Refused> {
Ok(ancestor)
}
fn is_directory(&self, node: &usize) -> bool {
matches!(self.nodes[*node], Kind::Dir(_))
}
fn find_name(&mut self, dir: &usize, name: &[u8]) -> Result<Option<usize>, Refused> {
let Kind::Dir(entries) = &self.nodes[*dir] else {
return Ok(None);
};
Ok(entries
.iter()
.find(|(entry, _)| *entry == name)
.map(|(_, at)| *at))
}
fn read_link(&mut self, node: &usize, _path: &[u8]) -> Result<Option<Vec<u8>>, Refused> {
match self.nodes[*node] {
Kind::Link(target) => Ok(Some(target.to_vec())),
_ => Ok(None),
}
}
fn not_found(&self, _path: &[u8]) -> Refused {
Refused::NotFound
}
fn not_a_directory(&self, _node: &usize, _path: &[u8]) -> Refused {
Refused::NotADirectory
}
fn too_many_links(&self, _path: &[u8]) -> Refused {
Refused::TooManyLinks
}
}
fn tree() -> Tiny {
Tiny {
nodes: vec![
Kind::Dir(vec![
(b"usr", 1),
(b"etc", 4),
(b"bin", 6),
(b"here", 7),
(b"there", 8),
]),
Kind::Dir(vec![(b"bin", 2), (b"lib", 3)]),
Kind::Dir(vec![(b"sh", 10), (b"lib", 9)]),
Kind::Dir(vec![(b"libc.so", 11)]),
Kind::Dir(vec![(b"hostname", 5)]),
Kind::File,
Kind::Link(b"usr/bin"),
Kind::Link(b"/there"),
Kind::Link(b"/here"),
Kind::Link(b"../lib"),
Kind::File,
Kind::File,
],
}
}
fn at(path: &[u8]) -> Result<usize, Refused> {
drive(&mut tree(), path, true)
}
#[test]
fn a_parent_component_ascends_through_what_was_descended() {
assert_eq!(at(b"/usr/bin/../lib/libc.so"), Ok(11));
assert_eq!(at(b"/usr/bin/.."), Ok(1));
assert_eq!(at(b"/usr/./bin/./../lib"), Ok(3));
}
#[test]
fn a_relative_link_that_ascends_is_one_a_resolution_follows() {
assert_eq!(at(b"/usr/bin/lib"), Ok(3));
assert_eq!(at(b"/usr/bin/lib/libc.so"), Ok(11));
assert_eq!(drive(&mut tree(), b"/usr/bin/lib", false), Ok(9));
assert_eq!(at(b"/bin/lib/libc.so"), Ok(11));
}
#[test]
fn nothing_outside_the_filesystem_can_be_named() {
for path in [&b"/.."[..], b"/../..", b"..", b"../../.."] {
assert_eq!(at(path), Ok(0), "{}", String::from_utf8_lossy(path));
}
assert_eq!(at(b"/../etc/hostname"), Ok(5));
assert_eq!(at(b"../../../../etc/hostname"), Ok(5));
assert_eq!(at(b"/usr/bin/../../etc/hostname"), Ok(5));
assert_eq!(at(b"/usr/bin/../../../../etc/hostname"), Ok(5));
}
#[test]
fn a_component_below_something_that_is_not_a_directory_is_refused() {
assert_eq!(at(b"/etc/hostname/x"), Err(Refused::NotADirectory));
assert_eq!(at(b"/etc/hostname/.."), Err(Refused::NotADirectory));
}
#[test]
fn a_name_no_directory_holds_is_not_found_rather_than_refused_by_name() {
assert_eq!(at(b"/etc/nothing"), Err(Refused::NotFound));
assert_eq!(at(b"/etc/host\0name"), Err(Refused::NotFound));
}
#[test]
fn a_cycle_of_links_is_spent_rather_than_followed() {
assert_eq!(at(b"/here"), Err(Refused::TooManyLinks));
}
#[test]
fn a_link_in_the_middle_is_expanded_whether_or_not_the_last_one_is() {
assert_eq!(drive(&mut tree(), b"/bin/sh", true), Ok(10));
assert_eq!(drive(&mut tree(), b"/bin/sh", false), Ok(10));
assert_eq!(drive(&mut tree(), b"/bin", true), Ok(2));
assert_eq!(drive(&mut tree(), b"/bin", false), Ok(6));
}
#[test]
fn the_root_is_what_an_empty_path_names() {
for path in [&b""[..], b"/", b"//", b"/./"] {
assert_eq!(at(path), Ok(0), "{}", String::from_utf8_lossy(path));
}
}
}