Skip to main content

oak_core/
tree.rs

1//! Tree-structured manifests.
2//!
3//! Each Tree contains its DIRECT children (subtrees + blobs), keyed by name.
4//! A commit references the root tree's hash; subtrees that don't change between
5//! commits are shared by hash reference, giving O(changes × depth) writes
6//! instead of O(files) per commit.
7
8use crate::error::{OakError, Result};
9use crate::hash::{hash_bytes, hash_string, Hash};
10use crate::{FileChange, FileMode, Manifest, ManifestEntry, RenameConfig};
11use serde::{Deserialize, Serialize};
12use std::collections::BTreeMap;
13
14/// What a tree entry refers to: another tree (subdirectory) or a blob (file).
15#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
16#[serde(rename_all = "lowercase")]
17pub enum TreeEntryKind {
18    Tree,
19    Blob,
20}
21
22impl TreeEntryKind {
23    pub fn as_str(&self) -> &'static str {
24        match self {
25            TreeEntryKind::Tree => "tree",
26            TreeEntryKind::Blob => "blob",
27        }
28    }
29
30    pub fn parse(s: &str) -> Option<Self> {
31        match s {
32            "tree" => Some(TreeEntryKind::Tree),
33            "blob" => Some(TreeEntryKind::Blob),
34            _ => None,
35        }
36    }
37}
38
39/// A single entry in a tree: one direct child (file or subdirectory).
40/// `mode` is meaningful only when `kind == Blob`; for trees it is canonicalized
41/// to `Regular` and serialized as `"tree"` in the hash recipe.
42#[derive(Debug, Clone, Serialize, Deserialize)]
43pub struct TreeEntry {
44    pub name: String,
45    pub kind: TreeEntryKind,
46    pub hash: Hash,
47    #[serde(default)]
48    pub mode: FileMode,
49}
50
51/// A content-addressed tree object. `entries` are sorted by `name`.
52#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct Tree {
54    pub hash: Hash,
55    pub entries: Vec<TreeEntry>,
56}
57
58impl Tree {
59    /// Build a tree from its direct children, sorting and computing the hash.
60    /// Rejects entry names that would corrupt the canonical preimage (see
61    /// [`validate_entry_name`]).
62    pub fn new(mut entries: Vec<TreeEntry>) -> Result<Self> {
63        for e in &entries {
64            validate_entry_name(&e.name)?;
65        }
66        entries.sort_by(|a, b| a.name.cmp(&b.name));
67        if let Some(duplicate) = entries
68            .windows(2)
69            .find(|pair| pair[0].name == pair[1].name)
70            .map(|pair| pair[0].name.as_str())
71        {
72            return Err(OakError::InvalidPath(format!(
73                "duplicate tree entry name {duplicate:?}"
74            )));
75        }
76        Ok(Self::new_sorted_unchecked(entries))
77    }
78
79    /// [`Tree::new`] without name validation. Only for callers whose entries
80    /// were already validated ([`build_tree`]) or whose result is never
81    /// stored ([`build_tree_unchecked`] for `Manifest::new`'s hash-only use).
82    fn new_unchecked(mut entries: Vec<TreeEntry>) -> Self {
83        entries.sort_by(|a, b| a.name.cmp(&b.name));
84        Self::new_sorted_unchecked(entries)
85    }
86
87    fn new_sorted_unchecked(entries: Vec<TreeEntry>) -> Self {
88        let hash = hash_bytes(&serialize_entries(&entries));
89        Tree { hash, entries }
90    }
91
92    /// The canonical byte preimage this tree's hash is computed over: one line
93    /// per entry (sorted by name), `kind\tname\thash\tmode`, joined by `\n`.
94    ///
95    /// This is also the on-disk serialized form stored (compressed) in the
96    /// `trees.content` column — keeping the stored bytes identical to the hash
97    /// recipe means integrity is a single `hash_bytes(content) == hash` check.
98    pub fn canonical_bytes(&self) -> Vec<u8> {
99        serialize_entries(&self.entries)
100    }
101
102    /// Reconstruct a tree from its canonical byte form (the inverse of
103    /// [`Tree::canonical_bytes`]). `hash` is taken as the storage key; callers
104    /// that want integrity should compare `hash_bytes(bytes)` against it.
105    ///
106    /// Parsing is strict: names must pass [`validate_entry_name`], hashes must
107    /// be valid hex, and the mode field must round-trip through
108    /// [`mode_string`] exactly. Anything [`serialize_entries`] could not have
109    /// produced is rejected rather than silently mis-parsed — defense against
110    /// malicious wire or database bytes.
111    pub fn from_canonical_bytes(hash: Hash, bytes: &[u8]) -> Result<Self> {
112        let text = std::str::from_utf8(bytes)
113            .map_err(|e| OakError::Database(format!("tree content not utf-8: {e}")))?;
114        let mut entries = Vec::new();
115        if !text.is_empty() {
116            for line in text.split('\n') {
117                let malformed = || OakError::Database(format!("malformed tree entry: {line:?}"));
118                let mut parts = line.splitn(4, '\t');
119                let kind = parts
120                    .next()
121                    .and_then(TreeEntryKind::parse)
122                    .ok_or_else(malformed)?;
123                let name = parts.next().ok_or_else(malformed)?;
124                validate_entry_name(name)
125                    .map_err(|e| OakError::Database(format!("malformed tree entry: {e}")))?;
126                let entry_hash =
127                    Hash::from_hex(parts.next().ok_or_else(malformed)?).map_err(|_| malformed())?;
128                // The mode field is the final `splitn` segment, so crafted
129                // trailing `\t...` bytes land here and fail the exact match.
130                let mode = match (kind, parts.next().ok_or_else(malformed)?) {
131                    (TreeEntryKind::Tree, "tree") => FileMode::Regular,
132                    (TreeEntryKind::Blob, "regular") => FileMode::Regular,
133                    (TreeEntryKind::Blob, "executable") => FileMode::Executable,
134                    (TreeEntryKind::Blob, "symlink") => FileMode::Symlink,
135                    _ => return Err(malformed()),
136                };
137                entries.push(TreeEntry {
138                    name: name.to_string(),
139                    kind,
140                    hash: entry_hash,
141                    mode,
142                });
143            }
144        }
145        Ok(Tree { hash, entries })
146    }
147
148    /// The hash of an empty tree (no entries). Equal to `hash_string("")`.
149    pub fn empty() -> Self {
150        Tree {
151            hash: hash_string(""),
152            entries: Vec::new(),
153        }
154    }
155
156    /// Hash that represents an empty tree. Useful as a sentinel.
157    pub fn empty_hash() -> Hash {
158        hash_string("")
159    }
160
161    /// Find a direct child by name.
162    pub fn get(&self, name: &str) -> Option<&TreeEntry> {
163        self.entries.iter().find(|e| e.name == name)
164    }
165}
166
167/// Why `name` can't be a tree entry name, or `None` if it's fine.
168///
169/// The canonical tree preimage ([`serialize_entries`]) uses `\t` as its field
170/// separator and `\n` as its line separator, so a name containing either
171/// would let distinct trees serialize to identical bytes (hash collision) and
172/// stored bytes parse back into different entries (round-trip corruption).
173/// `\0`, `/`, empty names, and the reserved `.`/`..` components were never
174/// representable as single path components; rejecting `.`/`..` also closes
175/// path traversal out of the working-tree root on materialization.
176fn entry_name_problem(name: &str) -> Option<&'static str> {
177    if name.is_empty() {
178        Some("empty filename")
179    } else if name == "." || name == ".." {
180        Some("'.' and '..' are reserved names")
181    } else if name.contains('\n') {
182        Some("newline in filename")
183    } else if name.contains('\t') {
184        Some("tab in filename")
185    } else if name.contains('\0') {
186        Some("NUL byte in filename")
187    } else if name.chars().any(char::is_control) {
188        Some("control character in filename")
189    } else if name.contains('/') {
190        Some("'/' in filename")
191    } else {
192        None
193    }
194}
195
196/// Validate a single tree entry name (one path component). See
197/// [`entry_name_problem`] for what's rejected and why.
198pub fn validate_entry_name(name: &str) -> Result<()> {
199    match entry_name_problem(name) {
200        Some(problem) => Err(OakError::InvalidPath(format!(
201            "invalid tree entry name {name:?}: {problem}"
202        ))),
203        None => Ok(()),
204    }
205}
206
207/// Validate every component of a manifest path (normalized first, so leading/
208/// trailing/duplicate slashes and backslashes are fine). Rejects components
209/// that can't be tree entry names — including `..`, which would otherwise
210/// escape the root when the path is materialized.
211pub fn validate_tree_path(path: &str) -> Result<()> {
212    let normalized = normalize_path(path);
213    if normalized.is_empty() {
214        return Err(OakError::InvalidPath(format!(
215            "cannot track {path:?}: path is empty"
216        )));
217    }
218    for component in normalized.split('/').filter(|c| !c.is_empty()) {
219        if let Some(problem) = entry_name_problem(component) {
220            return Err(OakError::InvalidPath(format!(
221                "cannot track {path:?}: {problem}"
222            )));
223        }
224    }
225    Ok(())
226}
227
228/// Whether `component` names the metadata directory `dir` (`.oak` or `.git`)
229/// on some filesystem a working tree can live on. Case-insensitive, and
230/// ignoring the trailing dots and spaces Windows strips, because `.OAK` and
231/// `.oak.` open the same directory on default macOS and Windows volumes.
232pub fn is_metadata_dir_component(component: &str, dir: &str) -> bool {
233    component
234        .trim_end_matches(['.', ' '])
235        .eq_ignore_ascii_case(dir)
236}
237
238/// Why a manifest path must not be written into a working tree, or `None`
239/// when it's safe. Trees arrive from servers and other users, so this is the
240/// boundary between repository content and the machine it's checked out on:
241///
242/// - Nothing may land inside `.oak/` except the tracked files Oak defines
243///   (`.oak/attributes`, and the retired but still trackable
244///   `.oak/PERMISSIONS` and `.oak/workflows/**`, which older history holds:
245///   workflows are stored on the server now). The rest of
246///   that directory is the local database, in-progress markers, and
247///   executable hooks, so a tree that could write `.oak/hooks/pre-commit`
248///   would run code on the next `oak commit`.
249/// - No component may be `.git` (git refuses these too) or a nested `.oak`,
250///   which would also change which repository a subdirectory resolves to.
251/// - No component may be `.oakroot`, the local state file `oak root` reads
252///   to decide where a root directory pulls from and pushes to.
253/// - On Windows, `\` and `:` would be path separators or drive prefixes.
254pub fn worktree_path_problem(path: &str) -> Option<String> {
255    let components: Vec<&str> = path.split('/').collect();
256    for (index, component) in components.iter().enumerate() {
257        if let Some(problem) = entry_name_problem(component) {
258            return Some(problem.to_string());
259        }
260        if cfg!(windows)
261            && (component.contains('\\')
262                || component.contains(':')
263                || component.ends_with('.')
264                || component.ends_with(' '))
265        {
266            return Some(
267                "'\\', ':', or a trailing '.' or space in a path component is unsafe on Windows"
268                    .to_string(),
269            );
270        }
271        if is_metadata_dir_component(component, ".git") {
272            return Some("'.git' path component is reserved".to_string());
273        }
274        if is_metadata_dir_component(component, crate::ignore::ROOT_STATE_FILE) {
275            // `oak root` trusts the nearest `.oakroot` above the current
276            // directory (which server, repo and root a directory holds), so
277            // repository content must never be able to plant one.
278            return Some("'.oakroot' path component is reserved".to_string());
279        }
280        if is_metadata_dir_component(component, ".oak") {
281            // Only at the repo root, so a tree can't plant a nested repo.
282            let tracked = *component == ".oak"
283                && index == 0
284                && (crate::ignore::TRACKED_OAK_FILES.contains(&path)
285                    || (components.len() > 2 && components[1] == "workflows"));
286            if !tracked {
287                return Some(
288                    "only .oak/attributes, .oak/PERMISSIONS, and .oak/workflows/ may be tracked inside .oak"
289                        .to_string(),
290                );
291            }
292        }
293    }
294    None
295}
296
297/// [`worktree_path_problem`] as an error.
298pub fn validate_worktree_path(path: &str) -> Result<()> {
299    match worktree_path_problem(path) {
300        Some(problem) => Err(OakError::InvalidPath(format!(
301            "refusing to write {path:?} into the working tree: {problem}"
302        ))),
303        None => Ok(()),
304    }
305}
306
307fn mode_string(kind: TreeEntryKind, mode: FileMode) -> &'static str {
308    match (kind, mode) {
309        (TreeEntryKind::Tree, _) => "tree",
310        (TreeEntryKind::Blob, FileMode::Regular) => "regular",
311        (TreeEntryKind::Blob, FileMode::Executable) => "executable",
312        (TreeEntryKind::Blob, FileMode::Symlink) => "symlink",
313    }
314}
315
316/// Serialize a tree's entries into the canonical byte preimage used both for
317/// hashing ([`Tree::new`]) and for on-disk storage ([`Tree::canonical_bytes`]).
318/// Entries are expected to already be sorted by name.
319fn serialize_entries(entries: &[TreeEntry]) -> Vec<u8> {
320    let mut out = String::new();
321    for (i, e) in entries.iter().enumerate() {
322        if i > 0 {
323            out.push('\n');
324        }
325        out.push_str(e.kind.as_str());
326        out.push('\t');
327        out.push_str(&e.name);
328        out.push('\t');
329        out.push_str(e.hash.as_str());
330        out.push('\t');
331        out.push_str(mode_string(e.kind, e.mode));
332    }
333    out.into_bytes()
334}
335
336/// Output of [`build_tree`]. `root_hash` is the commit-referenced hash;
337/// `trees` contains every tree object produced (root + intermediates) in
338/// arbitrary order. The caller is responsible for storing them all.
339#[derive(Debug)]
340pub struct BuiltTree {
341    pub root_hash: Hash,
342    pub trees: Vec<Tree>,
343}
344
345/// Normalize a path string for use as a tree-keyed lookup:
346/// - replace backslashes with forward slashes
347/// - collapse repeated slashes
348/// - strip leading and trailing slashes
349pub fn normalize_path(path: &str) -> String {
350    let s = path.replace('\\', "/");
351    let mut out = String::with_capacity(s.len());
352    let mut prev_slash = false;
353    for c in s.chars() {
354        if c == '/' {
355            if prev_slash || out.is_empty() {
356                continue;
357            }
358            prev_slash = true;
359            out.push(c);
360        } else {
361            prev_slash = false;
362            out.push(c);
363        }
364    }
365    while out.ends_with('/') {
366        out.pop();
367    }
368    out
369}
370
371/// Build a tree from a flat list of (path, blob_hash, mode) entries.
372///
373/// Paths are normalized (forward slashes, no leading/trailing/duplicate slashes)
374/// and grouped by directory recursively. Returns the root tree hash and every
375/// intermediate tree object that was produced.
376///
377/// Every path component must pass [`validate_tree_path`]; a path that would
378/// corrupt the canonical preimage or escape the root is rejected before any
379/// tree object is built.
380pub fn build_tree(entries: &[ManifestEntry]) -> Result<BuiltTree> {
381    for e in entries {
382        validate_tree_path(&e.path)?;
383    }
384    validate_tree_path_conflicts(entries)?;
385    Ok(build_tree_unchecked(entries))
386}
387
388fn validate_tree_path_conflicts(entries: &[ManifestEntry]) -> Result<()> {
389    let mut paths: Vec<String> = entries
390        .iter()
391        .map(|e| normalize_path(&e.path))
392        .filter(|p| !p.is_empty())
393        .collect();
394    paths.sort();
395
396    for pair in paths.windows(2) {
397        let prev = &pair[0];
398        let next = &pair[1];
399        if prev == next {
400            return Err(OakError::InvalidPath(format!(
401                "cannot build tree with duplicate path {prev:?}"
402            )));
403        }
404        if next
405            .strip_prefix(prev)
406            .is_some_and(|suffix| suffix.starts_with('/'))
407        {
408            return Err(OakError::InvalidPath(format!(
409                "cannot build tree with both file {prev:?} and child path {next:?}"
410            )));
411        }
412    }
413
414    Ok(())
415}
416
417/// [`build_tree`] without path validation. For `Manifest::new`, which only
418/// needs the root hash as a diff identity and never stores the tree objects —
419/// it must stay infallible. Storage paths go through [`build_tree`].
420pub(crate) fn build_tree_unchecked(entries: &[ManifestEntry]) -> BuiltTree {
421    let normalized: Vec<ManifestEntry> = entries
422        .iter()
423        .map(|e| ManifestEntry {
424            path: normalize_path(&e.path),
425            blob_hash: e.blob_hash.clone(),
426            mode: e.mode,
427        })
428        .filter(|e| !e.path.is_empty())
429        .collect();
430
431    let mut trees = Vec::new();
432    let root = build_subtree(normalized, &mut trees);
433    let root_hash = root.hash.clone();
434    trees.push(root);
435    BuiltTree { root_hash, trees }
436}
437
438fn build_subtree(entries: Vec<ManifestEntry>, trees: &mut Vec<Tree>) -> Tree {
439    let mut groups: BTreeMap<String, Vec<ManifestEntry>> = BTreeMap::new();
440    let mut tree_entries: Vec<TreeEntry> = Vec::new();
441
442    for e in entries {
443        match e.path.find('/') {
444            Some(slash) => {
445                let component = e.path[..slash].to_string();
446                let rest = e.path[slash + 1..].to_string();
447                groups.entry(component).or_default().push(ManifestEntry {
448                    path: rest,
449                    blob_hash: e.blob_hash,
450                    mode: e.mode,
451                });
452            }
453            None => {
454                tree_entries.push(TreeEntry {
455                    name: e.path,
456                    kind: TreeEntryKind::Blob,
457                    hash: e.blob_hash,
458                    mode: e.mode,
459                });
460            }
461        }
462    }
463
464    for (name, sub_entries) in groups {
465        let subtree = build_subtree(sub_entries, trees);
466        let sub_hash = subtree.hash.clone();
467        trees.push(subtree);
468        tree_entries.push(TreeEntry {
469            name,
470            kind: TreeEntryKind::Tree,
471            hash: sub_hash,
472            mode: FileMode::Regular,
473        });
474    }
475
476    // Names were validated path-component-wise by `build_tree` (or the caller
477    // accepted unchecked hashing via `build_tree_unchecked`).
478    Tree::new_unchecked(tree_entries)
479}
480
481/// Walk a tree depth-first, producing the equivalent flat list of entries
482/// (with full paths). Subtrees are fetched via the provided closure.
483///
484/// The closure typically reads from a Repository; the closure indirection
485/// keeps oak-core dependency-free.
486pub fn flatten_tree<F>(root: &Hash, fetch: &mut F) -> Result<Vec<ManifestEntry>>
487where
488    F: FnMut(&Hash) -> Result<Tree>,
489{
490    if root == &Tree::empty_hash() {
491        return Ok(Vec::new());
492    }
493    let mut out = Vec::new();
494    let tree = fetch(root)?;
495    flatten_recursive(&tree, "", fetch, &mut out)?;
496    Ok(out)
497}
498
499/// `prefix/name`, allocated at exactly its final length. `format!` reserves
500/// about twice the prefix length here, and a flattened manifest keeps one of
501/// these per file.
502pub(crate) fn child_path(prefix: &str, name: &str) -> String {
503    if prefix.is_empty() {
504        return name.to_string();
505    }
506    let mut path = String::with_capacity(prefix.len() + 1 + name.len());
507    path.push_str(prefix);
508    path.push('/');
509    path.push_str(name);
510    path
511}
512
513/// Append every blob under the tree `root` to `out`, with paths prefixed by
514/// `prefix` (the tree's own path; empty for a root).
515pub(crate) fn flatten_subtree_into<F>(
516    root: &Hash,
517    prefix: &str,
518    fetch: &mut F,
519    out: &mut Vec<ManifestEntry>,
520) -> Result<()>
521where
522    F: FnMut(&Hash) -> Result<Tree>,
523{
524    if root == &Tree::empty_hash() {
525        return Ok(());
526    }
527    let tree = fetch(root)?;
528    flatten_recursive(&tree, prefix, fetch, out)
529}
530
531fn flatten_recursive<F>(
532    tree: &Tree,
533    prefix: &str,
534    fetch: &mut F,
535    out: &mut Vec<ManifestEntry>,
536) -> Result<()>
537where
538    F: FnMut(&Hash) -> Result<Tree>,
539{
540    for entry in &tree.entries {
541        let path = child_path(prefix, &entry.name);
542        match entry.kind {
543            TreeEntryKind::Blob => {
544                out.push(ManifestEntry {
545                    path,
546                    blob_hash: entry.hash.clone(),
547                    mode: entry.mode,
548                });
549            }
550            TreeEntryKind::Tree => {
551                let sub = fetch(&entry.hash)?;
552                flatten_recursive(&sub, &path, fetch, out)?;
553            }
554        }
555    }
556    Ok(())
557}
558
559/// Collect every tree object reachable from `root` (the root tree itself plus
560/// all transitively reachable subtrees), keyed by hash.
561///
562/// Used by push/pull to gather every tree that a commit references for wire
563/// transfer. Empty-tree sentinel is excluded — receivers materialize it
564/// themselves via `Tree::empty()`.
565pub fn collect_tree_objects<F>(root: &Hash, fetch: &mut F) -> Result<Vec<Tree>>
566where
567    F: FnMut(&Hash) -> Result<Tree>,
568{
569    if root == &Tree::empty_hash() {
570        return Ok(Vec::new());
571    }
572    let mut out: Vec<Tree> = Vec::new();
573    let mut seen: std::collections::HashSet<String> = std::collections::HashSet::new();
574    let mut stack: Vec<Hash> = vec![root.clone()];
575    while let Some(h) = stack.pop() {
576        if !seen.insert(h.0.clone()) {
577            continue;
578        }
579        let tree = fetch(&h)?;
580        for entry in &tree.entries {
581            if entry.kind == TreeEntryKind::Tree && !seen.contains(&entry.hash.0) {
582                stack.push(entry.hash.clone());
583            }
584        }
585        out.push(tree);
586    }
587    Ok(out)
588}
589
590/// Resolve a slash-separated path within the tree rooted at `root`.
591/// Returns the final TreeEntry, or None if any component is missing.
592pub fn resolve_path<F>(root: &Hash, path: &str, fetch: &mut F) -> Result<Option<TreeEntry>>
593where
594    F: FnMut(&Hash) -> Result<Tree>,
595{
596    let path = normalize_path(path);
597    if path.is_empty() {
598        return Ok(None);
599    }
600    if root == &Tree::empty_hash() {
601        return Ok(None);
602    }
603    let mut current = fetch(root)?;
604    let mut iter = path.split('/').peekable();
605    while let Some(component) = iter.next() {
606        let entry = match current.entries.iter().find(|e| e.name == component) {
607            Some(e) => e.clone(),
608            None => return Ok(None),
609        };
610        if iter.peek().is_none() {
611            return Ok(Some(entry));
612        }
613        if entry.kind != TreeEntryKind::Tree {
614            return Ok(None);
615        }
616        current = fetch(&entry.hash)?;
617    }
618    Ok(None)
619}
620
621/// Find the subtree rooted at `path` (a directory). Returns `Some(hash)` if the
622/// path exists and is a tree, `None` otherwise. An empty path returns the
623/// original `root`.
624pub fn subtree_at_path<F>(root: &Hash, path: &str, fetch: &mut F) -> Result<Option<Hash>>
625where
626    F: FnMut(&Hash) -> Result<Tree>,
627{
628    let path = normalize_path(path);
629    if path.is_empty() {
630        return Ok(Some(root.clone()));
631    }
632    match resolve_path(root, &path, fetch)? {
633        Some(entry) if entry.kind == TreeEntryKind::Tree => Ok(Some(entry.hash)),
634        _ => Ok(None),
635    }
636}
637
638/// Diff two trees, returning file-level changes with exact-hash rename
639/// detection.
640///
641/// Walks both trees together and descends only into subtrees whose hashes
642/// differ, so a change touching `k` paths fetches O(k × depth) trees instead
643/// of flattening both sides. The changed entries are then classified by
644/// [`Manifest::diff_entries_with_renames`], so the result — rename pairing
645/// included — is exactly what flattening both trees in name order and
646/// diffing those manifests produces.
647pub fn diff_trees<F>(
648    a_root: Option<&Hash>,
649    b_root: Option<&Hash>,
650    fetch: &mut F,
651    _config: &RenameConfig,
652) -> Result<Vec<FileChange>>
653where
654    F: FnMut(&Hash) -> Result<Tree>,
655{
656    let (old_side, new_side) = diff_tree_entries(a_root, b_root, fetch)?;
657    let old = Manifest {
658        hash: a_root.cloned().unwrap_or_else(Tree::empty_hash),
659        entries: old_side,
660    };
661    Ok(old.diff_entries_with_renames(&new_side))
662}
663
664/// The files that differ between trees `a_root` and `b_root`, unpaired: the
665/// first list holds each differing path's `a`-side entry, the second its
666/// `b`-side entry, so a path present on only one side appears in only one
667/// list and a content or mode change appears in both. Walks only subtrees
668/// whose hashes differ, like [`diff_trees`].
669pub fn diff_tree_entries<F>(
670    a_root: Option<&Hash>,
671    b_root: Option<&Hash>,
672    fetch: &mut F,
673) -> Result<(Vec<ManifestEntry>, Vec<ManifestEntry>)>
674where
675    F: FnMut(&Hash) -> Result<Tree>,
676{
677    let empty = Tree::empty_hash();
678    let mut old_side = Vec::new();
679    let mut new_side = Vec::new();
680    diff_subtrees(
681        a_root.unwrap_or(&empty),
682        b_root.unwrap_or(&empty),
683        "",
684        fetch,
685        &mut old_side,
686        &mut new_side,
687    )?;
688    Ok((old_side, new_side))
689}
690
691/// Apply file-level edits to the tree at `root` without flattening it: each
692/// path in `removals` drops the file there (a path that holds no file is left
693/// alone), then each entry in `upserts` adds or replaces the file at its path.
694/// Only the directories on edited paths are fetched and rebuilt —
695/// O(edits × depth) instead of O(files).
696///
697/// The root equals [`build_tree`] over the flattened `root` with the same
698/// edits applied, and fails where that would: a file and a child path at one
699/// path, or two upserts of one path, are an [`OakError::InvalidPath`] error.
700/// `trees` holds only the directories the edits created; unchanged subtrees
701/// are referenced by hash.
702pub fn edit_tree<F>(
703    root: &Hash,
704    upserts: &[ManifestEntry],
705    removals: &[String],
706    fetch: &mut F,
707) -> Result<BuiltTree>
708where
709    F: FnMut(&Hash) -> Result<Tree>,
710{
711    if upserts.is_empty() && removals.is_empty() {
712        return Ok(BuiltTree {
713            root_hash: root.clone(),
714            trees: Vec::new(),
715        });
716    }
717    let mut edits: Vec<(String, Option<&ManifestEntry>)> = Vec::new();
718    for path in removals {
719        let path = normalize_path(path);
720        if !path.is_empty() {
721            edits.push((path, None));
722        }
723    }
724    for entry in upserts {
725        validate_tree_path(&entry.path)?;
726        edits.push((normalize_path(&entry.path), Some(entry)));
727    }
728    let edits: Vec<(&str, Option<&ManifestEntry>)> = edits
729        .iter()
730        .map(|(path, edit)| (path.as_str(), *edit))
731        .collect();
732    let mut trees = Vec::new();
733    let root_hash =
734        edit_dir(dir_hash(root), edits, "", fetch, &mut trees)?.unwrap_or_else(Tree::empty_hash);
735    Ok(BuiltTree { root_hash, trees })
736}
737
738/// A directory hash, with the empty tree normalized to "no directory".
739pub(crate) fn dir_hash(hash: &Hash) -> Option<&Hash> {
740    (hash != &Tree::empty_hash()).then_some(hash)
741}
742
743/// Apply `edits` (paths relative to this directory; `None` removes) to the
744/// directory `dir` at `prefix`. Returns the new directory's hash, or `None`
745/// when it ends up empty.
746fn edit_dir<F>(
747    dir: Option<&Hash>,
748    edits: Vec<(&str, Option<&ManifestEntry>)>,
749    prefix: &str,
750    fetch: &mut F,
751    trees: &mut Vec<Tree>,
752) -> Result<Option<Hash>>
753where
754    F: FnMut(&Hash) -> Result<Tree>,
755{
756    let tree = match dir {
757        Some(hash) => load_tree(hash, fetch)?,
758        None => Tree::empty(),
759    };
760    let mut entries: BTreeMap<String, TreeEntry> = tree
761        .entries
762        .into_iter()
763        .map(|e| (e.name.clone(), e))
764        .collect();
765    let mut here: BTreeMap<&str, Vec<Option<&ManifestEntry>>> = BTreeMap::new();
766    let mut below: BTreeMap<&str, Vec<(&str, Option<&ManifestEntry>)>> = BTreeMap::new();
767    for (path, edit) in edits {
768        match path.split_once('/') {
769            None => here.entry(path).or_default().push(edit),
770            Some((name, rest)) => below.entry(name).or_default().push((rest, edit)),
771        }
772    }
773    let mut names: Vec<&str> = here.keys().chain(below.keys()).copied().collect();
774    names.sort_unstable();
775    names.dedup();
776
777    for name in names {
778        let path = child_path(prefix, name);
779        let direct = here.remove(name).unwrap_or_default();
780        let puts: Vec<&ManifestEntry> = direct.iter().flatten().copied().collect();
781        if puts.len() > 1 {
782            return Err(OakError::InvalidPath(format!(
783                "cannot build tree with duplicate path {path:?}"
784            )));
785        }
786        let mut node = entries.remove(name);
787        if direct.iter().any(Option::is_none)
788            && node.as_ref().is_some_and(|e| e.kind == TreeEntryKind::Blob)
789        {
790            node = None;
791        }
792        if let Some(nested) = below.remove(name) {
793            match node.as_ref() {
794                // Removing files beneath a file is a no-op; adding one clashes.
795                Some(file) if file.kind == TreeEntryKind::Blob => {
796                    if let Some(child) = nested.iter().find_map(|(_, edit)| *edit) {
797                        return Err(OakError::InvalidPath(format!(
798                            "cannot build tree with both file {path:?} and child path {:?}",
799                            normalize_path(&child.path)
800                        )));
801                    }
802                }
803                _ => {
804                    let sub = node.as_ref().map(|e| e.hash.clone());
805                    node = edit_dir(sub.as_ref().and_then(dir_hash), nested, &path, fetch, trees)?
806                        .map(|hash| TreeEntry {
807                            name: name.to_string(),
808                            kind: TreeEntryKind::Tree,
809                            hash,
810                            mode: FileMode::Regular,
811                        });
812                }
813            }
814        }
815        if let Some(file) = puts.first() {
816            if let Some(dir) = node
817                .as_ref()
818                .filter(|e| e.kind == TreeEntryKind::Tree && e.hash != Tree::empty_hash())
819            {
820                let child = first_file_under(&dir.hash, &path, trees, fetch)?;
821                return Err(OakError::InvalidPath(format!(
822                    "cannot build tree with both file {path:?} and child path {child:?}"
823                )));
824            }
825            node = Some(TreeEntry {
826                name: name.to_string(),
827                kind: TreeEntryKind::Blob,
828                hash: file.blob_hash.clone(),
829                mode: file.mode,
830            });
831        }
832        if let Some(node) = node {
833            entries.insert(name.to_string(), node);
834        }
835    }
836
837    if entries.is_empty() {
838        return Ok(None);
839    }
840    let tree = Tree::new(entries.into_values().collect())?;
841    let hash = tree.hash.clone();
842    if Some(&hash) != dir {
843        trees.push(tree);
844    }
845    Ok(Some(hash))
846}
847
848/// Some file path beneath the directory `dir` at `prefix`, for error messages.
849/// `created` holds directories the edit built and hasn't stored.
850fn first_file_under<F>(dir: &Hash, prefix: &str, created: &[Tree], fetch: &mut F) -> Result<String>
851where
852    F: FnMut(&Hash) -> Result<Tree>,
853{
854    let mut load = |hash: &Hash| match created.iter().find(|t| &t.hash == hash) {
855        Some(tree) => Ok(tree.clone()),
856        None => load_tree(hash, fetch),
857    };
858    let mut path = prefix.to_string();
859    let mut current = load(dir)?;
860    while let Some(entry) = entries_by_name(&current).first().copied().cloned() {
861        path = child_path(&path, &entry.name);
862        if entry.kind == TreeEntryKind::Blob {
863            break;
864        }
865        current = load(&entry.hash)?;
866    }
867    Ok(path)
868}
869
870/// Fetch a tree, answering the empty-tree sentinel without a lookup (it is
871/// never stored).
872pub(crate) fn load_tree<F>(hash: &Hash, fetch: &mut F) -> Result<Tree>
873where
874    F: FnMut(&Hash) -> Result<Tree>,
875{
876    if hash == &Tree::empty_hash() {
877        Ok(Tree::empty())
878    } else {
879        fetch(hash)
880    }
881}
882
883/// A tree's entries in name order. Oak trees are stored sorted, but other
884/// backends (git sorts directories as `name/`) need not be.
885pub(crate) fn entries_by_name(tree: &Tree) -> Vec<&TreeEntry> {
886    let mut entries: Vec<&TreeEntry> = tree.entries.iter().collect();
887    entries.sort_by(|a, b| a.name.cmp(&b.name));
888    entries
889}
890
891/// Collect the entries that differ between trees `a` and `b` (both rooted at
892/// `prefix`): `old` gets the `a`-side files, `new` the `b`-side files.
893/// Subtrees with equal hashes are skipped without being fetched.
894fn diff_subtrees<F>(
895    a: &Hash,
896    b: &Hash,
897    prefix: &str,
898    fetch: &mut F,
899    old: &mut Vec<ManifestEntry>,
900    new: &mut Vec<ManifestEntry>,
901) -> Result<()>
902where
903    F: FnMut(&Hash) -> Result<Tree>,
904{
905    if a == b {
906        return Ok(());
907    }
908    let a_tree = load_tree(a, fetch)?;
909    let b_tree = load_tree(b, fetch)?;
910    let a_entries = entries_by_name(&a_tree);
911    let b_entries = entries_by_name(&b_tree);
912    let (mut i, mut j) = (0, 0);
913    while i < a_entries.len() || j < b_entries.len() {
914        let order = match (a_entries.get(i), b_entries.get(j)) {
915            (Some(x), Some(y)) => x.name.cmp(&y.name),
916            (Some(_), None) => std::cmp::Ordering::Less,
917            (None, _) => std::cmp::Ordering::Greater,
918        };
919        match order {
920            std::cmp::Ordering::Less => {
921                push_entry_files(a_entries[i], prefix, fetch, old)?;
922                i += 1;
923            }
924            std::cmp::Ordering::Greater => {
925                push_entry_files(b_entries[j], prefix, fetch, new)?;
926                j += 1;
927            }
928            std::cmp::Ordering::Equal => {
929                let (x, y) = (a_entries[i], b_entries[j]);
930                i += 1;
931                j += 1;
932                if x.kind == y.kind && x.hash == y.hash && x.mode == y.mode {
933                    continue;
934                }
935                if x.kind == TreeEntryKind::Tree && y.kind == TreeEntryKind::Tree {
936                    let path = child_path(prefix, &x.name);
937                    diff_subtrees(&x.hash, &y.hash, &path, fetch, old, new)?;
938                } else {
939                    push_entry_files(x, prefix, fetch, old)?;
940                    push_entry_files(y, prefix, fetch, new)?;
941                }
942            }
943        }
944    }
945    Ok(())
946}
947
948/// Every file at or under `entry` (a direct child of the tree at `prefix`).
949fn push_entry_files<F>(
950    entry: &TreeEntry,
951    prefix: &str,
952    fetch: &mut F,
953    out: &mut Vec<ManifestEntry>,
954) -> Result<()>
955where
956    F: FnMut(&Hash) -> Result<Tree>,
957{
958    let path = child_path(prefix, &entry.name);
959    match entry.kind {
960        TreeEntryKind::Blob => {
961            out.push(ManifestEntry {
962                path,
963                blob_hash: entry.hash.clone(),
964                mode: entry.mode,
965            });
966            Ok(())
967        }
968        TreeEntryKind::Tree => flatten_subtree_into(&entry.hash, &path, fetch, out),
969    }
970}
971
972/// Random small repos for checking tree-level walks against their flat
973/// equivalents.
974#[cfg(test)]
975pub(crate) mod test_support {
976    use super::*;
977    use std::collections::HashMap;
978
979    pub(crate) struct Rng(pub(crate) u64);
980
981    impl Rng {
982        pub(crate) fn below(&mut self, n: u64) -> u64 {
983            // xorshift64*
984            let mut x = self.0 | 1;
985            x ^= x >> 12;
986            x ^= x << 25;
987            x ^= x >> 27;
988            self.0 = x;
989            x.wrapping_mul(0x2545_F491_4F6C_DD1D) % n
990        }
991    }
992
993    // A tiny alphabet and shallow depth make sides collide on names and on
994    // file-vs-directory positions.
995    const NAMES: [&str; 4] = ["a", "b", "c", "d"];
996
997    fn random_path(rng: &mut Rng) -> String {
998        let depth = 1 + rng.below(3);
999        (0..depth)
1000            .map(|_| NAMES[rng.below(NAMES.len() as u64) as usize])
1001            .collect::<Vec<_>>()
1002            .join("/")
1003    }
1004
1005    // Few distinct contents, so exact-hash renames and duplicate blobs occur.
1006    fn random_blob(rng: &mut Rng) -> Hash {
1007        hash_string(&format!("content-{}", rng.below(6)))
1008    }
1009
1010    fn random_mode(rng: &mut Rng) -> FileMode {
1011        match rng.below(8) {
1012            0 => FileMode::Executable,
1013            1 => FileMode::Symlink,
1014            _ => FileMode::Regular,
1015        }
1016    }
1017
1018    fn is_under(path: &str, dir: &str) -> bool {
1019        path.len() > dir.len() && path.starts_with(dir) && path.as_bytes()[dir.len()] == b'/'
1020    }
1021
1022    /// Add `entry`, dropping whatever it would clash with: the same path, a
1023    /// file at one of its ancestor directories, or files beneath it.
1024    fn put(entries: &mut Vec<ManifestEntry>, entry: ManifestEntry) {
1025        entries.retain(|e| {
1026            e.path != entry.path
1027                && !is_under(&entry.path, &e.path)
1028                && !is_under(&e.path, &entry.path)
1029        });
1030        entries.push(entry);
1031    }
1032
1033    pub(crate) fn random_entries(rng: &mut Rng, files: u64) -> Vec<ManifestEntry> {
1034        let mut entries = Vec::new();
1035        for _ in 0..files {
1036            let entry = ManifestEntry {
1037                path: random_path(rng),
1038                blob_hash: random_blob(rng),
1039                mode: random_mode(rng),
1040            };
1041            put(&mut entries, entry);
1042        }
1043        entries
1044    }
1045
1046    /// Apply `edits` random edits: content changes, mode flips, deletes,
1047    /// adds, renames, and file/directory replacements.
1048    pub(crate) fn mutate(rng: &mut Rng, base: &[ManifestEntry], edits: u64) -> Vec<ManifestEntry> {
1049        let mut entries = base.to_vec();
1050        for _ in 0..edits {
1051            let pick = |rng: &mut Rng, entries: &[ManifestEntry]| {
1052                (!entries.is_empty()).then(|| rng.below(entries.len() as u64) as usize)
1053            };
1054            match rng.below(6) {
1055                0 => {
1056                    if let Some(i) = pick(rng, &entries) {
1057                        entries[i].blob_hash = random_blob(rng);
1058                    }
1059                }
1060                1 => {
1061                    if let Some(i) = pick(rng, &entries) {
1062                        entries[i].mode = random_mode(rng);
1063                    }
1064                }
1065                2 => {
1066                    if let Some(i) = pick(rng, &entries) {
1067                        entries.remove(i);
1068                    }
1069                }
1070                3 => {
1071                    if let Some(i) = pick(rng, &entries) {
1072                        let moved = entries.remove(i);
1073                        let path = random_path(rng);
1074                        put(&mut entries, ManifestEntry { path, ..moved });
1075                    }
1076                }
1077                4 => {
1078                    // Replace a directory with a file (or a file with a dir).
1079                    if let Some(i) = pick(rng, &entries) {
1080                        let path = entries[i].path.clone();
1081                        let target = match rng.below(2) {
1082                            0 => path.rsplit_once('/').map(|(dir, _)| dir.to_string()),
1083                            _ => Some(format!("{path}/{}", NAMES[rng.below(4) as usize])),
1084                        };
1085                        if let Some(path) = target {
1086                            let entry = ManifestEntry {
1087                                path,
1088                                blob_hash: random_blob(rng),
1089                                mode: random_mode(rng),
1090                            };
1091                            put(&mut entries, entry);
1092                        }
1093                    }
1094                }
1095                _ => {
1096                    let entry = ManifestEntry {
1097                        path: random_path(rng),
1098                        blob_hash: random_blob(rng),
1099                        mode: random_mode(rng),
1100                    };
1101                    put(&mut entries, entry);
1102                }
1103            }
1104        }
1105        entries
1106    }
1107
1108    /// An in-memory tree store.
1109    #[derive(Default)]
1110    pub(crate) struct Store {
1111        pub(crate) trees: HashMap<Hash, Tree>,
1112    }
1113
1114    impl Store {
1115        pub(crate) fn add_entries(&mut self, entries: &[ManifestEntry]) -> Hash {
1116            let built = build_tree(entries).expect("random entries are clash-free");
1117            for tree in built.trees {
1118                self.trees.insert(tree.hash.clone(), tree);
1119            }
1120            built.root_hash
1121        }
1122
1123        pub(crate) fn add_trees(&mut self, trees: Vec<Tree>) {
1124            for tree in trees {
1125                self.trees.insert(tree.hash.clone(), tree);
1126            }
1127        }
1128
1129        pub(crate) fn fetch(&self, hash: &Hash) -> Result<Tree> {
1130            self.trees
1131                .get(hash)
1132                .cloned()
1133                .ok_or_else(|| OakError::Database(format!("tree not found: {hash}")))
1134        }
1135    }
1136}
1137
1138#[cfg(test)]
1139mod tests {
1140    use super::*;
1141    use std::collections::HashMap;
1142
1143    fn entry(path: &str, content: &str) -> ManifestEntry {
1144        ManifestEntry {
1145            path: path.to_string(),
1146            blob_hash: hash_string(content),
1147            mode: FileMode::Regular,
1148        }
1149    }
1150
1151    fn fetcher(trees: Vec<Tree>) -> impl FnMut(&Hash) -> Result<Tree> {
1152        let map: HashMap<String, Tree> = trees.into_iter().map(|t| (t.hash.0.clone(), t)).collect();
1153        move |h: &Hash| {
1154            map.get(&h.0)
1155                .cloned()
1156                .ok_or_else(|| crate::error::OakError::Database(format!("tree not found: {h}")))
1157        }
1158    }
1159
1160    #[test]
1161    fn empty_tree_hash_matches_sentinel() {
1162        let t = Tree::empty();
1163        assert_eq!(t.hash, Tree::empty_hash());
1164        assert_eq!(t.hash, hash_string(""));
1165    }
1166
1167    #[test]
1168    fn tree_hash_is_deterministic() {
1169        let entries = vec![
1170            TreeEntry {
1171                name: "a".to_string(),
1172                kind: TreeEntryKind::Blob,
1173                hash: hash_string("a"),
1174                mode: FileMode::Regular,
1175            },
1176            TreeEntry {
1177                name: "b".to_string(),
1178                kind: TreeEntryKind::Blob,
1179                hash: hash_string("b"),
1180                mode: FileMode::Regular,
1181            },
1182        ];
1183        let t1 = Tree::new(entries.clone()).unwrap();
1184        // Reverse order — should produce the same hash because Tree::new sorts.
1185        let t2 = Tree::new(entries.into_iter().rev().collect()).unwrap();
1186        assert_eq!(t1.hash, t2.hash);
1187    }
1188
1189    #[test]
1190    fn canonical_bytes_is_hash_preimage() {
1191        let entries = vec![
1192            TreeEntry {
1193                name: "a.txt".to_string(),
1194                kind: TreeEntryKind::Blob,
1195                hash: hash_string("a"),
1196                mode: FileMode::Executable,
1197            },
1198            TreeEntry {
1199                name: "sub".to_string(),
1200                kind: TreeEntryKind::Tree,
1201                hash: hash_string("sub"),
1202                mode: FileMode::Regular,
1203            },
1204            TreeEntry {
1205                name: "link".to_string(),
1206                kind: TreeEntryKind::Blob,
1207                hash: hash_string("l"),
1208                mode: FileMode::Symlink,
1209            },
1210        ];
1211        let t = Tree::new(entries).unwrap();
1212        // The stored bytes are exactly what the hash is computed over.
1213        assert_eq!(hash_bytes(&t.canonical_bytes()), t.hash);
1214    }
1215
1216    #[test]
1217    fn canonical_bytes_round_trips() {
1218        let entries = vec![
1219            TreeEntry {
1220                name: "a.txt".to_string(),
1221                kind: TreeEntryKind::Blob,
1222                hash: hash_string("a"),
1223                mode: FileMode::Executable,
1224            },
1225            TreeEntry {
1226                name: "sub".to_string(),
1227                kind: TreeEntryKind::Tree,
1228                hash: hash_string("sub"),
1229                mode: FileMode::Regular,
1230            },
1231        ];
1232        let t = Tree::new(entries).unwrap();
1233        let bytes = t.canonical_bytes();
1234        let t2 = Tree::from_canonical_bytes(t.hash.clone(), &bytes).unwrap();
1235        assert_eq!(t2.hash, t.hash);
1236        // Equal canonical bytes ⇒ identical names/kinds/hashes/modes and order.
1237        assert_eq!(t2.canonical_bytes(), bytes);
1238    }
1239
1240    #[test]
1241    fn from_canonical_bytes_empty_is_empty_tree() {
1242        let t = Tree::from_canonical_bytes(Tree::empty_hash(), b"").unwrap();
1243        assert!(t.entries.is_empty());
1244    }
1245
1246    #[test]
1247    fn build_tree_groups_by_directory() {
1248        let entries = vec![
1249            entry("src/lib.rs", "lib"),
1250            entry("src/bin/main.rs", "main"),
1251            entry("README.md", "readme"),
1252        ];
1253        let built = build_tree(&entries).unwrap();
1254
1255        let mut fetch = fetcher(built.trees);
1256        let flat = flatten_tree(&built.root_hash, &mut fetch).unwrap();
1257        let paths: Vec<&str> = flat.iter().map(|e| e.path.as_str()).collect();
1258        assert!(paths.contains(&"src/lib.rs"));
1259        assert!(paths.contains(&"src/bin/main.rs"));
1260        assert!(paths.contains(&"README.md"));
1261        assert_eq!(flat.len(), 3);
1262    }
1263
1264    #[test]
1265    fn build_tree_rejects_file_directory_collision() {
1266        let entries = vec![entry("src", "file"), entry("src/main.rs", "main")];
1267        let err = build_tree(&entries).unwrap_err();
1268        assert!(
1269            err.to_string().contains("both file"),
1270            "expected file/directory collision error, got {err}"
1271        );
1272    }
1273
1274    #[test]
1275    fn build_tree_rejects_duplicate_paths() {
1276        let entries = vec![entry("src/main.rs", "one"), entry("src/main.rs", "two")];
1277        let err = build_tree(&entries).unwrap_err();
1278        assert!(
1279            err.to_string().contains("duplicate path"),
1280            "expected duplicate path error, got {err}"
1281        );
1282    }
1283
1284    #[test]
1285    fn build_tree_dedup_subtrees() {
1286        // Same subtree content in two places should produce identical sub-hashes.
1287        let entries_a = vec![entry("dir/a.txt", "same"), entry("dir/b.txt", "same2")];
1288        let entries_b = vec![
1289            entry("other/dir/a.txt", "same"),
1290            entry("other/dir/b.txt", "same2"),
1291        ];
1292        let built_a = build_tree(&entries_a).unwrap();
1293        let built_b = build_tree(&entries_b).unwrap();
1294
1295        let dir_hash_a = {
1296            let mut fetch = fetcher(built_a.trees.clone());
1297            subtree_at_path(&built_a.root_hash, "dir", &mut fetch).unwrap()
1298        };
1299        let dir_hash_b = {
1300            let mut fetch = fetcher(built_b.trees.clone());
1301            subtree_at_path(&built_b.root_hash, "other/dir", &mut fetch).unwrap()
1302        };
1303        assert!(dir_hash_a.is_some());
1304        assert_eq!(dir_hash_a, dir_hash_b);
1305    }
1306
1307    #[test]
1308    fn build_tree_normalizes_paths() {
1309        let entries = vec![
1310            ManifestEntry {
1311                path: "src\\lib.rs".to_string(),
1312                blob_hash: hash_string("lib"),
1313                mode: FileMode::Regular,
1314            },
1315            entry("/leading/slash.txt", "x"),
1316            entry("double//slash.txt", "y"),
1317        ];
1318        let built = build_tree(&entries).unwrap();
1319        let mut fetch = fetcher(built.trees);
1320        let flat = flatten_tree(&built.root_hash, &mut fetch).unwrap();
1321        let paths: Vec<&str> = flat.iter().map(|e| e.path.as_str()).collect();
1322        assert!(paths.contains(&"src/lib.rs"));
1323        assert!(paths.contains(&"leading/slash.txt"));
1324        assert!(paths.contains(&"double/slash.txt"));
1325    }
1326
1327    #[test]
1328    fn flatten_round_trips_through_manifest_hash() {
1329        let entries = vec![
1330            entry("a/b/c.txt", "c"),
1331            entry("a/d.txt", "d"),
1332            entry("e.txt", "e"),
1333        ];
1334        let original = Manifest::new(entries.clone());
1335        let built = build_tree(&entries).unwrap();
1336        let mut fetch = fetcher(built.trees);
1337        let flat = flatten_tree(&built.root_hash, &mut fetch).unwrap();
1338        let round_tripped = Manifest::new(flat);
1339        assert_eq!(original.hash, round_tripped.hash);
1340    }
1341
1342    #[test]
1343    fn resolve_path_finds_blob_and_tree() {
1344        let entries = vec![entry("a/b/c.txt", "c"), entry("a/d.txt", "d")];
1345        let built = build_tree(&entries).unwrap();
1346        let mut fetch = fetcher(built.trees);
1347
1348        let blob = resolve_path(&built.root_hash, "a/b/c.txt", &mut fetch).unwrap();
1349        assert!(matches!(
1350            blob.as_ref().map(|e| e.kind),
1351            Some(TreeEntryKind::Blob)
1352        ));
1353
1354        let dir = resolve_path(&built.root_hash, "a/b", &mut fetch).unwrap();
1355        assert!(matches!(
1356            dir.as_ref().map(|e| e.kind),
1357            Some(TreeEntryKind::Tree)
1358        ));
1359
1360        let missing = resolve_path(&built.root_hash, "a/zzz.txt", &mut fetch).unwrap();
1361        assert!(missing.is_none());
1362    }
1363
1364    #[test]
1365    fn resolve_path_empty_tree_returns_missing_without_fetch() {
1366        let mut fetched = false;
1367        let mut fetch = |_h: &Hash| {
1368            fetched = true;
1369            Err(crate::error::OakError::Database(
1370                "empty tree should not be fetched".to_string(),
1371            ))
1372        };
1373
1374        let missing = resolve_path(&Tree::empty_hash(), "anything.txt", &mut fetch).unwrap();
1375        assert!(missing.is_none());
1376        assert!(!fetched);
1377    }
1378
1379    #[test]
1380    fn subtree_at_path_returns_root_for_empty() {
1381        let entries = vec![entry("x.txt", "x")];
1382        let built = build_tree(&entries).unwrap();
1383        let mut fetch = fetcher(built.trees);
1384        let sub = subtree_at_path(&built.root_hash, "", &mut fetch).unwrap();
1385        assert_eq!(sub.as_ref(), Some(&built.root_hash));
1386    }
1387
1388    #[test]
1389    fn diff_trees_matches_manifest_diff() {
1390        let a_entries = vec![entry("a.txt", "a"), entry("b.txt", "b")];
1391        let b_entries = vec![entry("a.txt", "a-modified"), entry("c.txt", "c")];
1392
1393        let a_built = build_tree(&a_entries).unwrap();
1394        let b_built = build_tree(&b_entries).unwrap();
1395
1396        let mut all = Vec::new();
1397        all.extend(a_built.trees.clone());
1398        all.extend(b_built.trees.clone());
1399        let mut fetch = fetcher(all);
1400
1401        let tree_changes = diff_trees(
1402            Some(&a_built.root_hash),
1403            Some(&b_built.root_hash),
1404            &mut fetch,
1405            &RenameConfig::default(),
1406        )
1407        .unwrap();
1408
1409        let manifest_changes = Manifest::new(a_entries)
1410            .diff_with_renames(&Manifest::new(b_entries), &RenameConfig::default());
1411
1412        assert_eq!(tree_changes.len(), manifest_changes.len());
1413    }
1414
1415    fn change_keys(changes: &[FileChange]) -> Vec<String> {
1416        changes.iter().map(|c| format!("{c:?}")).collect()
1417    }
1418
1419    #[test]
1420    fn diff_trees_matches_flat_diff_on_random_trees() {
1421        use super::test_support::{mutate, random_entries, Rng, Store};
1422        for seed in 0..2000u64 {
1423            let mut rng = Rng(seed.wrapping_mul(0x9E37_79B9_7F4A_7C15));
1424            let files = 1 + rng.below(12);
1425            let base = random_entries(&mut rng, files);
1426            let edits = rng.below(5);
1427            let other = mutate(&mut rng, &base, edits);
1428            let mut store = Store::default();
1429            let a = store.add_entries(&base);
1430            let b = store.add_entries(&other);
1431            let mut fetch = |h: &Hash| store.fetch(h);
1432
1433            let walked =
1434                diff_trees(Some(&a), Some(&b), &mut fetch, &RenameConfig::default()).unwrap();
1435            let a_flat = flatten_tree(&a, &mut fetch).unwrap();
1436            let b_flat = flatten_tree(&b, &mut fetch).unwrap();
1437            let flat = Manifest {
1438                hash: a.clone(),
1439                entries: a_flat,
1440            }
1441            .diff_entries_with_renames(&b_flat);
1442            assert_eq!(change_keys(&walked), change_keys(&flat), "seed {seed}");
1443
1444            let from_nothing = diff_trees(None, Some(&b), &mut fetch, &RenameConfig::default());
1445            assert_eq!(from_nothing.unwrap().len(), b_flat.len(), "seed {seed}");
1446        }
1447    }
1448
1449    #[test]
1450    fn edit_tree_matches_flat_rebuild_on_random_trees() {
1451        use super::test_support::{mutate, random_entries, Rng, Store};
1452        let (mut built, mut rejected) = (0, 0);
1453        for seed in 0..2000u64 {
1454            let mut rng = Rng(seed.wrapping_mul(0xA24B_AED4_963E_E407) ^ 0xed17);
1455            let files = 1 + rng.below(12);
1456            let base = random_entries(&mut rng, files);
1457            let mut store = Store::default();
1458            let root = store.add_entries(&base);
1459            // Upserts from a random mutation (some clash with what stays),
1460            // removals from base paths plus a few that hold no file.
1461            let edits = rng.below(5);
1462            let upserts: Vec<ManifestEntry> = mutate(&mut rng, &base, edits)
1463                .into_iter()
1464                .filter(|_| rng.below(3) == 0)
1465                .collect();
1466            let mut removals: Vec<String> = base
1467                .iter()
1468                .filter(|_| rng.below(4) == 0)
1469                .map(|e| e.path.clone())
1470                .collect();
1471            if rng.below(2) == 0 {
1472                removals.push(["a", "b/c", "d/a/b"][rng.below(3) as usize].to_string());
1473            }
1474
1475            let mut flat: Vec<ManifestEntry> = base
1476                .iter()
1477                .filter(|e| !removals.contains(&e.path))
1478                .cloned()
1479                .collect();
1480            flat.retain(|e| !upserts.iter().any(|u| u.path == e.path));
1481            flat.extend(upserts.iter().cloned());
1482            let expected = build_tree(&flat);
1483            let edited = {
1484                let mut fetch = |h: &Hash| store.fetch(h);
1485                edit_tree(&root, &upserts, &removals, &mut fetch)
1486            };
1487            match (expected, edited) {
1488                (Ok(expected), Ok(edited)) => {
1489                    assert_eq!(edited.root_hash, expected.root_hash, "seed {seed}");
1490                    store.add_trees(edited.trees);
1491                    let mut fetch = |h: &Hash| store.fetch(h);
1492                    let walked = flatten_tree(&edited.root_hash, &mut fetch).unwrap();
1493                    assert_eq!(walked.len(), flat.len(), "seed {seed}");
1494                    built += 1;
1495                }
1496                (Err(_), Err(OakError::InvalidPath(_))) => rejected += 1,
1497                (expected, edited) => panic!(
1498                    "seed {seed}: flat build {:?} vs edit {:?}",
1499                    expected.map(|b| b.root_hash),
1500                    edited.map(|b| b.root_hash)
1501                ),
1502            }
1503        }
1504        assert!(built > 1000, "{built} built");
1505        assert!(rejected > 0, "no file/directory clash cases generated");
1506    }
1507
1508    #[test]
1509    fn edit_tree_rebuilds_only_the_edited_directories() {
1510        let mut entries = Vec::new();
1511        for d in 0..8 {
1512            for f in 0..8 {
1513                entries.push(entry(&format!("d{d}/f{f}.txt"), &format!("{d}{f}")));
1514            }
1515        }
1516        let base = build_tree(&entries).unwrap();
1517        let mut inner = fetcher(base.trees);
1518        let mut fetches = 0;
1519        let mut fetch = |h: &Hash| {
1520            fetches += 1;
1521            inner(h)
1522        };
1523        let edited = edit_tree(
1524            &base.root_hash,
1525            &[entry("d3/f1.txt", "edited"), entry("new/file.txt", "new")],
1526            &["d5/f0.txt".to_string(), "d9/missing.txt".to_string()],
1527            &mut fetch,
1528        )
1529        .unwrap();
1530        // The root plus d3 and d5; `new/` and `d9/` don't exist yet.
1531        assert_eq!(fetches, 3);
1532        // New root, d3, d5 and new/.
1533        assert_eq!(edited.trees.len(), 4);
1534        entries[25].blob_hash = hash_string("edited");
1535        entries.remove(40);
1536        entries.push(entry("new/file.txt", "new"));
1537        assert_eq!(edited.root_hash, build_tree(&entries).unwrap().root_hash);
1538
1539        let mut no_fetch = |h: &Hash| -> Result<Tree> { panic!("unexpected fetch of {h}") };
1540        let unchanged = edit_tree(&edited.root_hash, &[], &[], &mut no_fetch).unwrap();
1541        assert_eq!(unchanged.root_hash, edited.root_hash);
1542        assert!(unchanged.trees.is_empty());
1543    }
1544
1545    #[test]
1546    fn diff_trees_fetches_only_the_changed_path() {
1547        // 8 top-level dirs × 8 subdirs × 8 files; change one file.
1548        let mut entries = Vec::new();
1549        for d in 0..8 {
1550            for s in 0..8 {
1551                for f in 0..8 {
1552                    entries.push(entry(&format!("d{d}/s{s}/f{f}.txt"), &format!("{d}{s}{f}")));
1553                }
1554            }
1555        }
1556        let a = build_tree(&entries).unwrap();
1557        entries[200].blob_hash = hash_string("changed");
1558        let changed_path = entries[200].path.clone();
1559        let b = build_tree(&entries).unwrap();
1560        let mut all = a.trees;
1561        all.extend(b.trees);
1562        let mut inner = fetcher(all);
1563        let mut fetches = 0;
1564        let mut fetch = |h: &Hash| {
1565            fetches += 1;
1566            inner(h)
1567        };
1568        let changes = diff_trees(
1569            Some(&a.root_hash),
1570            Some(&b.root_hash),
1571            &mut fetch,
1572            &RenameConfig::default(),
1573        )
1574        .unwrap();
1575        assert_eq!(changes.len(), 1);
1576        assert_eq!(changes[0].path, changed_path);
1577        assert_eq!(changes[0].change_type, crate::ChangeType::Modified);
1578        // root, d*, s* on each side.
1579        assert_eq!(fetches, 6);
1580    }
1581
1582    #[test]
1583    fn child_paths_are_allocated_exactly() {
1584        let entries = vec![entry("some/long/directory/name/file.txt", "x")];
1585        let built = build_tree(&entries).unwrap();
1586        let mut fetch = fetcher(built.trees);
1587        let flat = flatten_tree(&built.root_hash, &mut fetch).unwrap();
1588        assert_eq!(flat[0].path.capacity(), flat[0].path.len());
1589    }
1590
1591    #[test]
1592    fn empty_root_returns_empty_flatten() {
1593        let mut fetch = |_: &Hash| -> Result<Tree> { Ok(Tree::empty()) };
1594        let flat = flatten_tree(&Tree::empty_hash(), &mut fetch).unwrap();
1595        assert!(flat.is_empty());
1596    }
1597
1598    #[test]
1599    fn build_tree_rejects_empty_paths_without_silently_dropping_entries() {
1600        let entries = vec![
1601            ManifestEntry {
1602                path: "".to_string(),
1603                blob_hash: hash_string("nothing"),
1604                mode: FileMode::Regular,
1605            },
1606            entry("real.txt", "real"),
1607        ];
1608
1609        let err = build_tree(&entries).unwrap_err();
1610
1611        assert!(
1612            err.to_string().contains("path is empty"),
1613            "unexpected error: {err}"
1614        );
1615    }
1616
1617    #[test]
1618    fn normalize_path_idempotent() {
1619        let s = "a/b/c";
1620        assert_eq!(normalize_path(s), s);
1621        assert_eq!(normalize_path("/a//b/"), "a/b");
1622        assert_eq!(normalize_path("a\\b\\c"), "a/b/c");
1623    }
1624
1625    fn blob_named(name: &str) -> TreeEntry {
1626        TreeEntry {
1627            name: name.to_string(),
1628            kind: TreeEntryKind::Blob,
1629            hash: hash_string("content"),
1630            mode: FileMode::Regular,
1631        }
1632    }
1633
1634    #[test]
1635    fn tree_new_rejects_forbidden_names() {
1636        for name in [
1637            "a\nb.txt",
1638            "a\tb.txt",
1639            "a\0b.txt",
1640            "a\u{1b}b.txt",
1641            "a\u{7f}b.txt",
1642            "a/b.txt",
1643            "",
1644            ".",
1645            "..",
1646        ] {
1647            let err = Tree::new(vec![blob_named(name)]).unwrap_err();
1648            assert!(
1649                matches!(err, OakError::InvalidPath(_)),
1650                "{name:?} should be InvalidPath, got {err:?}"
1651            );
1652        }
1653        // A name that merely *contains* dots is fine.
1654        assert!(Tree::new(vec![blob_named("..gitignore-ish")]).is_ok());
1655        assert!(Tree::new(vec![blob_named("a.b")]).is_ok());
1656    }
1657
1658    #[test]
1659    fn tree_new_rejects_duplicate_names() {
1660        let mut first = blob_named("same.txt");
1661        first.hash = hash_string("first");
1662        let mut second = blob_named("same.txt");
1663        second.hash = hash_string("second");
1664
1665        let err = Tree::new(vec![first, second]).unwrap_err();
1666        assert!(
1667            err.to_string().contains("duplicate tree entry name"),
1668            "expected duplicate entry error, got {err}"
1669        );
1670    }
1671
1672    #[test]
1673    fn build_tree_rejects_forbidden_components() {
1674        for path in [
1675            "",
1676            "/",
1677            "///",
1678            "dir/a\nb.txt",
1679            "a\tb/file.txt",
1680            "a\0b",
1681            "a\u{1b}b",
1682            "a\u{7f}b",
1683            "../escape.txt",
1684            "dir/../escape.txt",
1685            "dir/..",
1686            "./self.txt",
1687            "a/./b.txt",
1688        ] {
1689            let err = build_tree(&[entry(path, "x")]).unwrap_err();
1690            assert!(
1691                matches!(err, OakError::InvalidPath(_)),
1692                "{path:?} should be InvalidPath, got {err:?}"
1693            );
1694        }
1695        // Normalization quirks that were always accepted stay accepted.
1696        assert!(build_tree(&[entry("/leading/slash.txt", "x")]).is_ok());
1697        assert!(build_tree(&[entry("double//slash.txt", "x")]).is_ok());
1698    }
1699
1700    #[test]
1701    fn validate_tree_path_messages_name_the_file() {
1702        let err = validate_tree_path("a\nb.txt").unwrap_err();
1703        let msg = err.to_string();
1704        assert!(msg.contains("a\\nb.txt"), "got: {msg}");
1705        assert!(msg.contains("newline"), "got: {msg}");
1706    }
1707
1708    #[test]
1709    fn from_canonical_bytes_rejects_malicious_names() {
1710        let h = hash_string("x");
1711        let hex = h.as_str();
1712        // Forbidden parsed names: '/', '.', '..', empty, NUL.
1713        for name in ["a/b", ".", "..", "", "a\0b"] {
1714            let line = format!("blob\t{name}\t{hex}\tregular");
1715            assert!(
1716                Tree::from_canonical_bytes(hash_string("k"), line.as_bytes()).is_err(),
1717                "name {name:?} should be rejected"
1718            );
1719        }
1720    }
1721
1722    #[test]
1723    fn from_canonical_bytes_rejects_bad_hashes_and_modes() {
1724        let h = hash_string("x");
1725        let hex = h.as_str();
1726        let cases = [
1727            // hash position isn't hex / wrong length / uppercase
1728            "blob\tf.txt\tnot-a-hash\tregular".to_string(),
1729            format!("blob\tf.txt\t{}\tregular", "A".repeat(64)),
1730            format!("blob\tf.txt\t{}\tregular", "a".repeat(63)),
1731            // unknown or kind-mismatched mode
1732            format!("blob\tf.txt\t{hex}\ttree"),
1733            format!("tree\td\t{hex}\tregular"),
1734            format!("blob\tf.txt\t{hex}\tweird"),
1735            // trailing injected field hides in the final splitn segment
1736            format!("blob\tf.txt\t{hex}\tregular\textra"),
1737            // missing mode field entirely
1738            format!("blob\tf.txt\t{hex}"),
1739            // unknown kind
1740            format!("link\tf.txt\t{hex}\tregular"),
1741        ];
1742        for bytes in &cases {
1743            assert!(
1744                Tree::from_canonical_bytes(hash_string("k"), bytes.as_bytes()).is_err(),
1745                "should reject {bytes:?}"
1746            );
1747        }
1748        // The exact lines serialize_entries produces still parse.
1749        for good in [
1750            format!("blob\tf.txt\t{hex}\tregular"),
1751            format!("blob\tf.txt\t{hex}\texecutable"),
1752            format!("blob\tf.txt\t{hex}\tsymlink"),
1753            format!("tree\td\t{hex}\ttree"),
1754        ] {
1755            assert!(
1756                Tree::from_canonical_bytes(hash_string("k"), good.as_bytes()).is_ok(),
1757                "should accept {good:?}"
1758            );
1759        }
1760    }
1761
1762    #[test]
1763    fn worktree_path_allows_tracked_oak_files_only() {
1764        for good in [
1765            "src/main.rs",
1766            ".oak/attributes",
1767            ".oak/PERMISSIONS",
1768            ".oak/workflows/ci.yml",
1769            ".oakignore",
1770            "docs/.oak-notes",
1771            ".github/workflows/ci.yml",
1772            ".oakroots",
1773            "docs/oakroot",
1774        ] {
1775            assert!(
1776                worktree_path_problem(good).is_none(),
1777                "should accept {good:?}"
1778            );
1779        }
1780        for bad in [
1781            ".oak/hooks/pre-commit",
1782            ".oak/oak.db",
1783            ".oak/workflows",
1784            ".OAK/hooks/pre-commit",
1785            ".Oak/attributes",
1786            ".oak./hooks/pre-commit",
1787            "sub/.oak/oak.db",
1788            "apps/web/.oak/workflows/ci.yml",
1789            ".oak/workflows/.oak/x",
1790            ".oak/workflows/.oak/workflows/x",
1791            "sub/.oak/workflows",
1792            "sub/.oak/workflows/nested/x.yml",
1793            "sub/.oak/hooks/x",
1794            "a/.oak/workflows/.oak/workflows/x",
1795            ".git/config",
1796            ".GIT/config",
1797            "vendor/.git/hooks/post-checkout",
1798            "a/../b",
1799            ".oakroot",
1800            ".OakRoot",
1801            ".oakroot.",
1802            ".oakroot ",
1803            "roots/stable/.oakroot",
1804            ".oakroot/x",
1805        ] {
1806            assert!(
1807                worktree_path_problem(bad).is_some(),
1808                "should reject {bad:?}"
1809            );
1810        }
1811    }
1812}