use std::{
collections::BTreeMap,
error::Error,
ffi::{OsStr, OsString},
fmt, fs, io,
path::{Component, Path, PathBuf},
};
use ignore::WalkBuilder;
use crate::{Entry, Manifest};
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedTree {
pub root: PathBuf,
pub entries: Vec<ResolvedEntry>,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ResolvedEntry {
pub path: PathBuf,
pub kind: ResolvedEntryKind,
pub children: Vec<ResolvedEntry>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ResolvedEntryKind {
File,
Directory,
Symlink,
Other,
}
struct PendingEntry {
path: PathBuf,
kind: ResolvedEntryKind,
children: PendingEntries,
}
type PendingEntries = BTreeMap<OsString, PendingEntry>;
impl PendingEntry {
fn into_resolved(self) -> ResolvedEntry {
ResolvedEntry {
path: self.path,
kind: self.kind,
children: self
.children
.into_values()
.map(Self::into_resolved)
.collect(),
}
}
}
#[derive(Debug)]
pub enum ResolveError {
InvalidManifestPath {
path: String,
},
ReadDirectory {
path: PathBuf,
source: io::Error,
},
ReadMetadata {
path: PathBuf,
source: io::Error,
},
WalkDirectory {
path: PathBuf,
source: ignore::Error,
},
}
impl fmt::Display for ResolveError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::InvalidManifestPath { path } => write!(
formatter,
"manifest path {path:?} must be relative and must not contain `..`"
),
Self::ReadDirectory { path, source } => {
write!(
formatter,
"could not read directory {}: {source}",
path.display()
)
}
Self::ReadMetadata { path, source } => {
write!(formatter, "could not inspect {}: {source}", path.display())
}
Self::WalkDirectory { path, source } => {
write!(formatter, "could not walk {}: {source}", path.display())
}
}
}
}
impl Error for ResolveError {
fn source(&self) -> Option<&(dyn Error + 'static)> {
match self {
Self::InvalidManifestPath { .. } => None,
Self::ReadDirectory { source, .. } | Self::ReadMetadata { source, .. } => Some(source),
Self::WalkDirectory { source, .. } => Some(source),
}
}
}
pub fn resolve_manifest(
manifest: &Manifest,
root: impl AsRef<Path>,
recursive_depth: Option<usize>,
) -> Result<ResolvedTree, ResolveError> {
let root = root.as_ref().to_path_buf();
let entries = resolve_entries(&root, &manifest.entries, recursive_depth)?;
Ok(ResolvedTree {
root,
entries: entries
.into_values()
.map(PendingEntry::into_resolved)
.collect(),
})
}
fn resolve_entries(
directory: &Path,
directives: &[Entry],
recursive_depth: Option<usize>,
) -> Result<PendingEntries, ResolveError> {
let exclusions = directives
.iter()
.filter_map(|entry| match entry {
Entry::Exclude { path } => Some(validate_relative_path(path)),
_ => None,
})
.collect::<Result<Vec<_>, _>>()?;
let mut resolved = BTreeMap::new();
for directive in directives {
match directive {
Entry::Include { path } => {
let relative = validate_relative_path(path)?;
if !is_excluded(&relative, &exclusions) {
insert_literal(&mut resolved, directory, &relative, None)?;
}
}
Entry::Exclude { .. } => {}
Entry::IncludeChildren => {
for (name, entry) in read_children(directory)? {
let relative = Path::new(&name);
if !is_excluded(relative, &exclusions) {
merge_entry(&mut resolved, name, entry);
}
}
}
Entry::IncludeRecursive => {
if recursive_depth != Some(0) {
for (name, entry) in
resolve_recursive_git_aware(directory, recursive_depth, &exclusions)?
{
merge_entry(&mut resolved, name, entry);
}
}
}
Entry::IncludeRecursiveAll => {
if recursive_depth != Some(0) {
for (name, entry) in resolve_recursive(
directory,
Path::new(""),
1,
recursive_depth,
&exclusions,
)? {
merge_entry(&mut resolved, name, entry);
}
}
}
Entry::Descend { path, entries } => {
let relative = validate_relative_path(path)?;
if is_excluded(&relative, &exclusions) {
continue;
}
let full_path = directory.join(&relative);
let Some(kind) = entry_kind_if_present(&full_path)? else {
continue;
};
if kind != ResolvedEntryKind::Directory {
continue;
}
let children = resolve_entries(&full_path, entries, recursive_depth)?;
insert_literal(&mut resolved, directory, &relative, Some(children))?;
}
}
}
Ok(resolved)
}
fn resolve_recursive_git_aware(
directory: &Path,
max_depth: Option<usize>,
exclusions: &[PathBuf],
) -> Result<PendingEntries, ResolveError> {
if let Some(ignore_root) = find_git_ignore_root(directory) {
return resolve_recursive_with_git_ignores(
directory,
&ignore_root,
Path::new(""),
max_depth,
exclusions,
);
}
resolve_recursive_outside_git_repository(directory, Path::new(""), 1, max_depth, exclusions)
}
fn resolve_recursive_outside_git_repository(
directory: &Path,
relative_directory: &Path,
level: usize,
max_depth: Option<usize>,
exclusions: &[PathBuf],
) -> Result<PendingEntries, ResolveError> {
let mut resolved = BTreeMap::new();
for (name, mut entry) in read_children(directory)? {
let relative = relative_directory.join(&name);
if is_excluded(&relative, exclusions) {
continue;
}
if entry.kind == ResolvedEntryKind::Directory && max_depth.is_none_or(|depth| level < depth)
{
entry.children = if is_git_ignore_root(&entry.path) {
let remaining_depth = max_depth.map(|depth| depth - level);
resolve_recursive_with_git_ignores(
&entry.path,
&entry.path,
&relative,
remaining_depth,
exclusions,
)?
} else {
resolve_recursive_outside_git_repository(
&entry.path,
&relative,
level + 1,
max_depth,
exclusions,
)?
};
}
resolved.insert(name, entry);
}
Ok(resolved)
}
fn resolve_recursive_with_git_ignores(
directory: &Path,
ignore_root: &Path,
relative_prefix: &Path,
max_depth: Option<usize>,
exclusions: &[PathBuf],
) -> Result<PendingEntries, ResolveError> {
let is_repository = is_git_repository_root(ignore_root);
let filter_root = directory.to_path_buf();
let filter_prefix = relative_prefix.to_path_buf();
let filter_exclusions = exclusions.to_vec();
let mut walker = WalkBuilder::new(directory);
walker
.standard_filters(false)
.parents(true)
.git_ignore(true)
.git_global(is_repository)
.git_exclude(is_repository)
.require_git(is_repository)
.follow_links(false)
.max_depth(max_depth)
.current_dir(ignore_root)
.sort_by_file_name(OsStr::cmp)
.filter_entry(move |entry| {
let relative = entry
.path()
.strip_prefix(&filter_root)
.unwrap_or(entry.path());
if relative.as_os_str().is_empty() {
return true;
}
if entry.file_name() == OsStr::new(".git") {
return false;
}
filter_exclusions.is_empty()
|| !is_excluded(&filter_prefix.join(relative), &filter_exclusions)
});
let mut resolved = BTreeMap::new();
for result in walker.build() {
let entry = result.map_err(|source| ResolveError::WalkDirectory {
path: directory.to_path_buf(),
source,
})?;
if let Some(source) = entry.error() {
return Err(ResolveError::WalkDirectory {
path: entry.path().to_path_buf(),
source: source.clone(),
});
}
let relative = entry
.path()
.strip_prefix(directory)
.expect("walked entries are always below the recursive root");
if relative.as_os_str().is_empty() {
continue;
}
let kind = kind_from_file_type(
entry
.file_type()
.expect("walked filesystem entries always have a file type"),
);
insert_walked_entry(&mut resolved, relative, entry.path().to_path_buf(), kind);
}
Ok(resolved)
}
fn find_git_ignore_root(directory: &Path) -> Option<PathBuf> {
directory
.ancestors()
.find(|ancestor| is_git_ignore_root(ancestor))
.map(Path::to_path_buf)
}
fn is_git_ignore_root(directory: &Path) -> bool {
is_git_repository_root(directory) || directory.join(".gitignore").is_file()
}
fn is_git_repository_root(directory: &Path) -> bool {
directory.join(".git").exists()
}
fn resolve_recursive(
directory: &Path,
relative_directory: &Path,
level: usize,
max_depth: Option<usize>,
exclusions: &[PathBuf],
) -> Result<PendingEntries, ResolveError> {
let mut resolved = BTreeMap::new();
for (name, mut entry) in read_children(directory)? {
let relative = relative_directory.join(&name);
if is_excluded(&relative, exclusions) {
continue;
}
if entry.kind == ResolvedEntryKind::Directory && max_depth.is_none_or(|depth| level < depth)
{
entry.children =
resolve_recursive(&entry.path, &relative, level + 1, max_depth, exclusions)?;
}
resolved.insert(name, entry);
}
Ok(resolved)
}
fn read_children(directory: &Path) -> Result<PendingEntries, ResolveError> {
let children = fs::read_dir(directory).map_err(|source| ResolveError::ReadDirectory {
path: directory.to_path_buf(),
source,
})?;
let mut resolved = BTreeMap::new();
for child in children {
let child = child.map_err(|source| ResolveError::ReadDirectory {
path: directory.to_path_buf(),
source,
})?;
let path = child.path();
let file_type = child
.file_type()
.map_err(|source| ResolveError::ReadMetadata {
path: path.clone(),
source,
})?;
let kind = kind_from_file_type(file_type);
let name = child.file_name();
resolved.insert(
name,
PendingEntry {
path,
kind,
children: BTreeMap::new(),
},
);
}
Ok(resolved)
}
fn insert_literal(
entries: &mut PendingEntries,
directory: &Path,
relative: &Path,
final_children: Option<PendingEntries>,
) -> Result<(), ResolveError> {
let components = relative
.components()
.filter_map(|component| match component {
Component::Normal(name) => Some(name.to_os_string()),
Component::CurDir => None,
_ => unreachable!("manifest paths are validated before insertion"),
})
.collect::<Vec<_>>();
insert_literal_components(entries, directory, &components, final_children)
}
fn insert_literal_components(
entries: &mut PendingEntries,
directory: &Path,
components: &[OsString],
final_children: Option<PendingEntries>,
) -> Result<(), ResolveError> {
let Some((name, remaining)) = components.split_first() else {
return Ok(());
};
let path = directory.join(name);
let Some(kind) = entry_kind_if_present(&path)? else {
return Ok(());
};
let entry = entries.entry(name.clone()).or_insert_with(|| PendingEntry {
path: path.clone(),
kind,
children: BTreeMap::new(),
});
if remaining.is_empty() {
if let Some(children) = final_children {
merge_entries(&mut entry.children, children);
}
return Ok(());
}
if kind != ResolvedEntryKind::Directory {
return Ok(());
}
insert_literal_components(&mut entry.children, &path, remaining, final_children)
}
fn insert_walked_entry(
entries: &mut PendingEntries,
relative: &Path,
path: PathBuf,
kind: ResolvedEntryKind,
) {
let components = relative
.components()
.filter_map(|component| match component {
Component::Normal(name) => Some(name),
Component::CurDir => None,
_ => unreachable!("walked entries are below the recursive root"),
})
.collect::<Vec<_>>();
let Some((name, parents)) = components.split_last() else {
return;
};
let mut children = entries;
for parent in parents {
children = &mut children
.get_mut(*parent)
.expect("directory walkers visit parents before their children")
.children;
}
children.insert(
(*name).to_os_string(),
PendingEntry {
path,
kind,
children: BTreeMap::new(),
},
);
}
fn merge_entry(entries: &mut PendingEntries, name: OsString, entry: PendingEntry) {
match entries.get_mut(&name) {
Some(existing) => merge_entries(&mut existing.children, entry.children),
None => {
entries.insert(name, entry);
}
}
}
fn merge_entries(existing: &mut PendingEntries, additional: PendingEntries) {
for (name, entry) in additional {
merge_entry(existing, name, entry);
}
}
fn entry_kind_if_present(path: &Path) -> Result<Option<ResolvedEntryKind>, ResolveError> {
match fs::symlink_metadata(path) {
Ok(metadata) => Ok(Some(kind_from_file_type(metadata.file_type()))),
Err(source) if source.kind() == io::ErrorKind::NotFound => Ok(None),
Err(source) => Err(ResolveError::ReadMetadata {
path: path.to_path_buf(),
source,
}),
}
}
fn kind_from_file_type(file_type: fs::FileType) -> ResolvedEntryKind {
if file_type.is_file() {
ResolvedEntryKind::File
} else if file_type.is_dir() {
ResolvedEntryKind::Directory
} else if file_type.is_symlink() {
ResolvedEntryKind::Symlink
} else {
ResolvedEntryKind::Other
}
}
fn validate_relative_path(path: &str) -> Result<PathBuf, ResolveError> {
let mut normalized = PathBuf::new();
for component in Path::new(path).components() {
match component {
Component::Normal(name) => normalized.push(name),
Component::CurDir => {}
Component::ParentDir | Component::RootDir | Component::Prefix(_) => {
return Err(ResolveError::InvalidManifestPath {
path: path.to_owned(),
});
}
}
}
(!normalized.as_os_str().is_empty())
.then_some(normalized)
.ok_or_else(|| ResolveError::InvalidManifestPath {
path: path.to_owned(),
})
}
fn is_excluded(path: &Path, exclusions: &[PathBuf]) -> bool {
exclusions
.iter()
.any(|excluded| path == excluded || path.starts_with(excluded))
}
#[cfg(test)]
mod tests {
use std::{
fs,
sync::atomic::{AtomicUsize, Ordering},
};
use super::*;
use crate::parse_manifest;
static NEXT_TEMP_DIRECTORY: AtomicUsize = AtomicUsize::new(0);
struct TestDirectory(PathBuf);
impl TestDirectory {
fn new() -> Self {
let unique = NEXT_TEMP_DIRECTORY.fetch_add(1, Ordering::Relaxed);
let path = std::env::temp_dir()
.join(format!("fsman-resolver-{}-{unique}", std::process::id()));
fs::create_dir(&path).unwrap();
Self(path)
}
fn create_file(&self, relative: &str) {
let path = self.0.join(relative);
if let Some(parent) = path.parent() {
fs::create_dir_all(parent).unwrap();
}
fs::write(path, "test").unwrap();
}
fn create_directory(&self, relative: &str) {
fs::create_dir_all(self.0.join(relative)).unwrap();
}
}
impl Drop for TestDirectory {
fn drop(&mut self) {
fs::remove_dir_all(&self.0).unwrap();
}
}
fn relative_paths(tree: &ResolvedTree) -> Vec<PathBuf> {
fn collect(root: &Path, entries: &[ResolvedEntry], paths: &mut Vec<PathBuf>) {
for entry in entries {
paths.push(entry.path.strip_prefix(root).unwrap().to_path_buf());
collect(root, &entry.children, paths);
}
}
let mut paths = Vec::new();
collect(&tree.root, &tree.entries, &mut paths);
paths
}
#[test]
fn resolves_literals_children_and_exclusions() {
let directory = TestDirectory::new();
directory.create_file("literal.txt");
directory.create_file("folder/keep.txt");
directory.create_file("folder/skip.txt");
let manifest =
parse_manifest("literal.txt\nmissing.txt\nfolder {\n *\n !skip.txt\n}\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
assert_eq!(
relative_paths(&tree),
["folder", "folder/keep.txt", "literal.txt"]
.map(PathBuf::from)
.to_vec()
);
}
#[test]
fn limits_each_recursive_directive_to_the_requested_depth() {
let directory = TestDirectory::new();
directory.create_file("one/two/three/file.txt");
let manifest = parse_manifest("***\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, Some(2)).unwrap();
assert_eq!(
relative_paths(&tree),
["one", "one/two"].map(PathBuf::from).to_vec()
);
}
#[test]
fn unlimited_recursion_visits_all_descendants() {
let directory = TestDirectory::new();
directory.create_file("one/two/three/file.txt");
let manifest = parse_manifest("***\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
assert_eq!(
relative_paths(&tree),
["one", "one/two", "one/two/three", "one/two/three/file.txt"]
.map(PathBuf::from)
.to_vec()
);
}
#[test]
fn overlapping_directives_merge_without_duplicates_or_lost_children() {
let directory = TestDirectory::new();
directory.create_file("folder/deep/file.txt");
directory.create_file("folder/shallow.txt");
let manifest = parse_manifest("folder/deep/file.txt\n***\nfolder {\n *\n}\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
assert_eq!(
relative_paths(&tree),
[
"folder",
"folder/deep",
"folder/deep/file.txt",
"folder/shallow.txt",
]
.map(PathBuf::from)
.to_vec()
);
}
#[test]
fn git_aware_recursion_applies_gitignore_with_or_without_repository_metadata() {
let directory = TestDirectory::new();
directory.create_file("outside/.gitignore");
fs::write(
directory.0.join("outside/.gitignore"),
"ignored.txt\nnode_modules\n",
)
.unwrap();
directory.create_file("outside/ignored.txt");
directory.create_file("outside/node_modules/package/index.js");
directory.create_directory("repo/.git");
directory.create_file("repo/.gitignore");
fs::write(directory.0.join("repo/.gitignore"), "ignored.txt\n").unwrap();
directory.create_file("repo/ignored.txt");
directory.create_file("repo/keep.txt");
let manifest = parse_manifest("**\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
assert_eq!(
relative_paths(&tree),
[
"outside",
"outside/.gitignore",
"repo",
"repo/.gitignore",
"repo/keep.txt",
]
.map(PathBuf::from)
.to_vec()
);
}
#[test]
fn unfiltered_recursion_keeps_git_ignored_paths() {
let directory = TestDirectory::new();
directory.create_directory("repo/.git");
directory.create_file("repo/.gitignore");
fs::write(directory.0.join("repo/.gitignore"), "ignored.txt\n").unwrap();
directory.create_file("repo/ignored.txt");
let manifest = parse_manifest("***\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
let paths = relative_paths(&tree);
assert!(paths.contains(&PathBuf::from("repo/.git")));
assert!(paths.contains(&PathBuf::from("repo/ignored.txt")));
}
#[cfg(unix)]
#[test]
fn git_aware_recursion_selects_symlinks_without_following_them() {
let directory = TestDirectory::new();
directory.create_directory(".git");
directory.create_file("target/nested.txt");
std::os::unix::fs::symlink("target", directory.0.join("link")).unwrap();
let manifest = parse_manifest("**\n").unwrap();
let tree = resolve_manifest(&manifest, &directory.0, None).unwrap();
let link = tree
.entries
.iter()
.find(|entry| entry.path.ends_with("link"))
.unwrap();
assert_eq!(link.kind, ResolvedEntryKind::Symlink);
assert!(link.children.is_empty());
assert!(!relative_paths(&tree).contains(&PathBuf::from("link/nested.txt")));
}
#[test]
fn rejects_paths_that_escape_the_resolution_root() {
let manifest = parse_manifest("../secret\n").unwrap();
assert!(matches!(
resolve_manifest(&manifest, ".", None),
Err(ResolveError::InvalidManifestPath { .. })
));
}
}