1use 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#[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#[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#[derive(Debug, Clone, Serialize, Deserialize)]
53pub struct Tree {
54 pub hash: Hash,
55 pub entries: Vec<TreeEntry>,
56}
57
58impl Tree {
59 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 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 pub fn canonical_bytes(&self) -> Vec<u8> {
99 serialize_entries(&self.entries)
100 }
101
102 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 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 pub fn empty() -> Self {
150 Tree {
151 hash: hash_string(""),
152 entries: Vec::new(),
153 }
154 }
155
156 pub fn empty_hash() -> Hash {
158 hash_string("")
159 }
160
161 pub fn get(&self, name: &str) -> Option<&TreeEntry> {
163 self.entries.iter().find(|e| e.name == name)
164 }
165}
166
167fn 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
196pub 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
207pub 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
228pub fn is_metadata_dir_component(component: &str, dir: &str) -> bool {
233 component
234 .trim_end_matches(['.', ' '])
235 .eq_ignore_ascii_case(dir)
236}
237
238pub 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 return Some("'.oakroot' path component is reserved".to_string());
279 }
280 if is_metadata_dir_component(component, ".oak") {
281 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
297pub 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
316fn 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#[derive(Debug)]
340pub struct BuiltTree {
341 pub root_hash: Hash,
342 pub trees: Vec<Tree>,
343}
344
345pub 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
371pub 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
417pub(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 Tree::new_unchecked(tree_entries)
479}
480
481pub 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
499pub(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
513pub(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
559pub 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
590pub 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
621pub 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
638pub 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
664pub 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
691pub 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
738pub(crate) fn dir_hash(hash: &Hash) -> Option<&Hash> {
740 (hash != &Tree::empty_hash()).then_some(hash)
741}
742
743fn 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 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
848fn 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(¤t).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
870pub(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
883pub(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
891fn 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
948fn 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#[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 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 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 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 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 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 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 #[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 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 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 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 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 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 assert_eq!(fetches, 3);
1532 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 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 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 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 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 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 "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 format!("blob\tf.txt\t{hex}\ttree"),
1733 format!("tree\td\t{hex}\tregular"),
1734 format!("blob\tf.txt\t{hex}\tweird"),
1735 format!("blob\tf.txt\t{hex}\tregular\textra"),
1737 format!("blob\tf.txt\t{hex}"),
1739 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 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}