verdant_runtime/

tree.rs

use crate::cas::{CasError, ManifestEntry, TreeBlobStore, TreeManifest};
use crate::tree_txn::{transact, DirReplace, Source};
use std::os::unix::fs::MetadataExt;
use std::path::{Path, PathBuf};
use std::{fs, io};

#[derive(Debug, thiserror::Error)]
pub enum TreeError {
    #[error("io error: {0}")]
    Io(#[from] io::Error),
    #[error("cas error: {0}")]
    Cas(#[from] CasError),
    #[error("blob missing for {path}")]
    BlobMissing { path: PathBuf },
    #[error("restore path escapes destination root: {path}")]
    PathEscape { path: PathBuf },
    #[error("replay would remove the non-empty directory {path}")]
    NonEmptyDirectory { path: PathBuf },
    #[error("replay expects a directory at {path}, where the tree holds none")]
    NotADirectory { path: PathBuf },
    #[error("replay would create {path} where another entry exists")]
    Occupied { path: PathBuf },
    #[error("{cause}; undoing the part already applied failed: {}", failures.join("; "))]
    RollbackIncomplete {
        cause: Box<TreeError>,
        failures: Vec<String>,
    },
}

pub fn capture_tree(blobs: &TreeBlobStore, root: &Path) -> Result<TreeManifest, TreeError> {
    let mut entries: Vec<ManifestEntry> = Vec::new();
    collect_entries(blobs, root, root, &mut entries)?;
    entries.sort_by(|a, b| a.path.cmp(&b.path));
    Ok(TreeManifest::new(entries, vec![]))
}

fn collect_entries(
    blobs: &TreeBlobStore,
    root: &Path,
    dir: &Path,
    entries: &mut Vec<ManifestEntry>,
) -> Result<(), TreeError> {
    for entry in fs::read_dir(dir)? {
        let entry = entry?;
        let path = entry.path();
        let file_type = entry.file_type()?;

        if file_type.is_symlink() {
            // symlinks out of scope for M4
            continue;
        }

        if file_type.is_dir() {
            collect_entries(blobs, root, &path, entries)?;
        } else if file_type.is_file() {
            let metadata = fs::metadata(&path)?;
            let content = fs::read(&path)?;
            let key = blobs.put_file_blob(&content)?;
            let mode = (metadata.mode() & 0o7777) as u32;
            let mtime_secs = metadata.mtime();
            let mtime_nanos = metadata.mtime_nsec() as u32;
            let rel = path
                .strip_prefix(root)
                .expect("path must be under root")
                .to_path_buf();
            entries.push(ManifestEntry::entry_for(
                rel,
                key,
                mode,
                (mtime_secs, mtime_nanos),
            ));
        }
    }
    Ok(())
}

/// Replays a manifest onto `dest`, which may have changed since the run it
/// records, so a deleted directory is removed only while it is empty. Any
/// failure leaves `dest` as it was (see [`transact`]).
pub fn restore_tree(
    blobs: &TreeBlobStore,
    manifest: &TreeManifest,
    dest: &Path,
) -> Result<(), TreeError> {
    // restore may target a dest that does not exist yet (a build output dir
    // wiped before replay), so create it before canonicalizing for the
    // symlink bounds check.
    fs::create_dir_all(dest)?;
    transact(dest, DirReplace::EmptyOnly, |txn| {
        for dir in &manifest.dir_attrs {
            let mtime = dir
                .mtime
                .map(|(secs, nanos)| filetime::FileTime::from_unix_time(secs, nanos));
            txn.set_dir_attrs(&dir.path, dir.mode, mtime)?;
        }
        for deleted in &manifest.deleted {
            txn.remove(deleted)?;
        }
        for dir in &manifest.dirs {
            let mtime = filetime::FileTime::from_unix_time(dir.mtime_secs, dir.mtime_nanos);
            txn.create_dir(&dir.path, dir.mode, mtime)?;
        }
        for link in &manifest.links {
            let mtime = filetime::FileTime::from_unix_time(link.mtime_secs, link.mtime_nanos);
            txn.create_symlink(&link.path, &link.target, mtime)?;
        }
        for entry in &manifest.entries {
            let bytes = blobs.get_file_blob(&entry.content_hash)?.ok_or_else(|| {
                TreeError::BlobMissing {
                    path: entry.path.clone(),
                }
            })?;
            let mtime = filetime::FileTime::from_unix_time(entry.mtime_secs, entry.mtime_nanos);
            txn.write_file(&entry.path, Source::Bytes(&bytes), entry.mode, mtime)?;
        }
        Ok(())
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::cas::{ManifestDir, ManifestDirAttrs, ManifestLink, TreeBlobStore};
    use crate::store::FileStore;
    use filetime::FileTime;
    use std::os::unix::fs::PermissionsExt;
    use std::path::PathBuf;
    use tempfile::TempDir;

    fn setup_store() -> (TempDir, FileStore) {
        let dir = TempDir::new().unwrap();
        let store = FileStore::open(dir.path()).unwrap();
        (dir, store)
    }

    #[test]
    fn round_trip_fidelity() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);

        let src_dir = TempDir::new().unwrap();
        let nested = src_dir.path().join("sub/dir");
        fs::create_dir_all(&nested).unwrap();

        let file_a = src_dir.path().join("top.txt");
        fs::write(&file_a, b"hello top").unwrap();

        let file_b = nested.join("deep.bin");
        fs::write(&file_b, b"\x00\x01\x02\x03").unwrap();

        // Set a precise mtime with non-zero nanoseconds on file_a.
        let known_mtime = FileTime::from_unix_time(1_700_000_000, 123_456_789);
        filetime::set_file_mtime(&file_a, known_mtime).unwrap();

        // Capture permissions before capture so we can verify restoration.
        use std::os::unix::fs::PermissionsExt;
        let mode_a = fs::metadata(&file_a).unwrap().permissions().mode() & 0o7777;
        let mode_b = fs::metadata(&file_b).unwrap().permissions().mode() & 0o7777;
        let mtime_b = {
            use std::os::unix::fs::MetadataExt;
            let md = fs::metadata(&file_b).unwrap();
            FileTime::from_unix_time(md.mtime(), md.mtime_nsec() as u32)
        };

        let manifest = capture_tree(&blobs, src_dir.path()).unwrap();
        assert_eq!(manifest.entries.len(), 2);
        assert!(manifest.deleted.is_empty());

        let dest_dir = TempDir::new().unwrap();
        restore_tree(&blobs, &manifest, dest_dir.path()).unwrap();

        // Verify contents.
        let restored_a = fs::read(dest_dir.path().join("top.txt")).unwrap();
        assert_eq!(restored_a, b"hello top");
        let restored_b = fs::read(dest_dir.path().join("sub/dir/deep.bin")).unwrap();
        assert_eq!(restored_b, b"\x00\x01\x02\x03");

        // Verify permissions.
        let restored_mode_a = fs::metadata(dest_dir.path().join("top.txt"))
            .unwrap()
            .permissions()
            .mode()
            & 0o7777;
        let restored_mode_b = fs::metadata(dest_dir.path().join("sub/dir/deep.bin"))
            .unwrap()
            .permissions()
            .mode()
            & 0o7777;
        assert_eq!(restored_mode_a, mode_a);
        assert_eq!(restored_mode_b, mode_b);

        // Verify mtimes including nanoseconds.
        use std::os::unix::fs::MetadataExt;
        let md_a = fs::metadata(dest_dir.path().join("top.txt")).unwrap();
        assert_eq!(md_a.mtime(), 1_700_000_000);
        assert_eq!(md_a.mtime_nsec() as u32, 123_456_789);

        let md_b = fs::metadata(dest_dir.path().join("sub/dir/deep.bin")).unwrap();
        assert_eq!(
            FileTime::from_unix_time(md_b.mtime(), md_b.mtime_nsec() as u32),
            mtime_b
        );
    }

    #[test]
    fn deletion_removes_file_from_dest() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);

        let dest_dir = TempDir::new().unwrap();
        let target = dest_dir.path().join("to_delete.txt");
        fs::write(&target, b"present").unwrap();
        assert!(target.exists());

        let manifest = TreeManifest::new(vec![], vec![PathBuf::from("to_delete.txt")]);
        restore_tree(&blobs, &manifest, dest_dir.path()).unwrap();

        assert!(!target.exists(), "deleted path must be removed from dest");
    }

    #[test]
    fn restore_refuses_symlink_escaping_root() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);

        let outside = TempDir::new().unwrap();
        let victim = outside.path().join("victim.txt");
        fs::write(&victim, b"original").unwrap();

        let dest_dir = TempDir::new().unwrap();
        let link = dest_dir.path().join("link");
        std::os::unix::fs::symlink(&victim, &link).unwrap();

        let key = blobs.put_file_blob(b"pwned").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("link"), key, 0o644, (0, 0));
        let manifest = TreeManifest::new(vec![entry], vec![]);

        let err = restore_tree(&blobs, &manifest, dest_dir.path())
            .expect_err("must refuse a symlink escaping root");
        assert!(
            matches!(err, TreeError::PathEscape { .. }),
            "unexpected error variant: {err:?}"
        );
        assert_eq!(fs::read(&victim).unwrap(), b"original", "victim untouched");
    }

    #[test]
    fn restore_allows_symlink_inside_root() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);

        let dest_dir = TempDir::new().unwrap();
        let real = dest_dir.path().join("real.txt");
        fs::write(&real, b"original").unwrap();
        let link = dest_dir.path().join("link");
        std::os::unix::fs::symlink(&real, &link).unwrap();

        let key = blobs.put_file_blob(b"updated").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("link"), key, 0o644, (0, 0));
        let manifest = TreeManifest::new(vec![entry], vec![]);

        restore_tree(&blobs, &manifest, dest_dir.path()).unwrap();
        assert_eq!(fs::read(&real).unwrap(), b"updated");
    }

    #[test]
    fn missing_blob_returns_error() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest_dir = TempDir::new().unwrap();

        let phantom_key = crate::store::Key::from_bytes(b"never-stored");
        let entry =
            ManifestEntry::entry_for(PathBuf::from("ghost.txt"), phantom_key, 0o644, (0, 0));
        let manifest = TreeManifest::new(vec![entry], vec![]);
        let err = restore_tree(&blobs, &manifest, dest_dir.path())
            .expect_err("must error on missing blob");
        assert!(
            matches!(err, TreeError::BlobMissing { .. }),
            "unexpected error variant: {err:?}"
        );
    }
    fn mtime_of(path: &Path) -> (i64, i64) {
        let meta = fs::symlink_metadata(path).unwrap();
        (meta.mtime(), meta.mtime_nsec())
    }

    #[test]
    fn deletion_removes_an_empty_directory() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest_dir = TempDir::new().unwrap();
        fs::create_dir(dest_dir.path().join("dist")).unwrap();
        fs::write(dest_dir.path().join("log"), b"a\n").unwrap();

        let key = blobs.put_file_blob(b"a\nx\n").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("log"), key, 0o644, (0, 0));
        let manifest = TreeManifest::new(vec![entry], vec![PathBuf::from("dist")]);
        restore_tree(&blobs, &manifest, dest_dir.path()).unwrap();

        assert!(!dest_dir.path().join("dist").exists());
        assert_eq!(fs::read(dest_dir.path().join("log")).unwrap(), b"a\nx\n");
    }

    #[test]
    fn a_file_replaces_an_empty_directory() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest_dir = TempDir::new().unwrap();
        fs::create_dir(dest_dir.path().join("dist")).unwrap();

        let key = blobs.put_file_blob(b"now a file").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("dist"), key, 0o644, (0, 0));
        restore_tree(
            &blobs,
            &TreeManifest::new(vec![entry], vec![]),
            dest_dir.path(),
        )
        .unwrap();

        assert_eq!(
            fs::read(dest_dir.path().join("dist")).unwrap(),
            b"now a file"
        );
    }

    #[test]
    fn a_replay_never_removes_a_non_empty_directory_and_writes_nothing() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest_dir = TempDir::new().unwrap();
        let dest = dest_dir.path();
        fs::create_dir(dest.join("dist")).unwrap();
        fs::write(dest.join("dist/kept"), b"kept").unwrap();
        fs::write(dest.join("log"), b"a\n").unwrap();

        let key = blobs.put_file_blob(b"a\nx\n").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("log"), key, 0o644, (0, 0));
        let manifest = TreeManifest::new(vec![entry], vec![PathBuf::from("dist")]);
        let err = restore_tree(&blobs, &manifest, dest).expect_err("must refuse");

        assert!(
            matches!(err, TreeError::NonEmptyDirectory { .. }),
            "unexpected error variant: {err:?}"
        );
        assert_eq!(fs::read(dest.join("dist/kept")).unwrap(), b"kept");
        assert_eq!(fs::read(dest.join("log")).unwrap(), b"a\n");
    }

    #[test]
    fn a_failed_restore_leaves_the_tree_as_it_was() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let outside = TempDir::new().unwrap();
        let victim = outside.path().join("victim.txt");
        fs::write(&victim, b"original").unwrap();

        let dest_dir = TempDir::new().unwrap();
        let dest = dest_dir.path();
        fs::write(dest.join("a.txt"), b"old").unwrap();
        fs::set_permissions(dest.join("a.txt"), fs::Permissions::from_mode(0o600)).unwrap();
        filetime::set_file_mtime(
            dest.join("a.txt"),
            FileTime::from_unix_time(1_600_000_000, 5),
        )
        .unwrap();
        fs::create_dir(dest.join("gone")).unwrap();
        fs::write(dest.join("gone.txt"), b"still here").unwrap();
        std::os::unix::fs::symlink(&victim, dest.join("z_link")).unwrap();
        let before = mtime_of(&dest.join("a.txt"));

        let entries = vec![
            ManifestEntry::entry_for(
                PathBuf::from("a.txt"),
                blobs.put_file_blob(b"new").unwrap(),
                0o644,
                (0, 0),
            ),
            ManifestEntry::entry_for(
                PathBuf::from("fresh/dir/b.txt"),
                blobs.put_file_blob(b"b").unwrap(),
                0o644,
                (0, 0),
            ),
            ManifestEntry::entry_for(
                PathBuf::from("z_link"),
                blobs.put_file_blob(b"pwned").unwrap(),
                0o644,
                (0, 0),
            ),
        ];
        let deleted = vec![PathBuf::from("gone"), PathBuf::from("gone.txt")];
        let err = restore_tree(&blobs, &TreeManifest::new(entries, deleted), dest)
            .expect_err("the escaping symlink must fail the restore");

        assert!(
            matches!(err, TreeError::PathEscape { .. }),
            "unexpected error variant: {err:?}"
        );
        assert_eq!(fs::read(dest.join("a.txt")).unwrap(), b"old");
        let meta = fs::metadata(dest.join("a.txt")).unwrap();
        assert_eq!(meta.permissions().mode() & 0o7777, 0o600);
        assert_eq!(mtime_of(&dest.join("a.txt")), before);
        assert!(!dest.join("fresh").exists(), "created dirs must be removed");
        assert!(dest.join("gone").is_dir(), "removed dir must come back");
        assert_eq!(fs::read(dest.join("gone.txt")).unwrap(), b"still here");
        assert_eq!(fs::read(&victim).unwrap(), b"original");
        let mut names: Vec<_> = fs::read_dir(dest)
            .unwrap()
            .map(|e| e.unwrap().file_name())
            .collect();
        names.sort();
        assert_eq!(
            names,
            ["a.txt", "gone", "gone.txt", "z_link"],
            "no backups left"
        );
    }

    #[test]
    fn restore_refuses_a_write_through_a_parent_symlink_escaping_root() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let outside = TempDir::new().unwrap();
        let dest_dir = TempDir::new().unwrap();
        std::os::unix::fs::symlink(outside.path(), dest_dir.path().join("sub")).unwrap();

        let key = blobs.put_file_blob(b"pwned").unwrap();
        let entry = ManifestEntry::entry_for(PathBuf::from("sub/new/x.txt"), key, 0o644, (0, 0));
        let err = restore_tree(
            &blobs,
            &TreeManifest::new(vec![entry], vec![]),
            dest_dir.path(),
        )
        .expect_err("must refuse");

        assert!(
            matches!(err, TreeError::PathEscape { .. }),
            "unexpected error variant: {err:?}"
        );
        assert!(!outside.path().join("new").exists());
    }

    #[test]
    fn a_deletion_through_a_parent_symlink_escaping_root_is_refused() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let outside = TempDir::new().unwrap();
        fs::write(outside.path().join("victim.txt"), b"original").unwrap();
        let dest_dir = TempDir::new().unwrap();
        std::os::unix::fs::symlink(outside.path(), dest_dir.path().join("sub")).unwrap();

        let manifest = TreeManifest::new(vec![], vec![PathBuf::from("sub/victim.txt")]);
        let err = restore_tree(&blobs, &manifest, dest_dir.path()).expect_err("must refuse");

        assert!(
            matches!(err, TreeError::PathEscape { .. }),
            "unexpected error variant: {err:?}"
        );
        assert!(outside.path().join("victim.txt").exists());
    }

    #[test]
    fn restore_replaces_a_deleted_link_with_a_created_directory_before_its_files() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest = TempDir::new().unwrap();
        fs::create_dir(dest.path().join("kept")).unwrap();
        std::os::unix::fs::symlink("kept", dest.path().join("current")).unwrap();
        let key = blobs.put_file_blob(b"x").unwrap();
        let mut manifest = TreeManifest::new(
            vec![ManifestEntry::entry_for(
                PathBuf::from("current/f"),
                key,
                0o644,
                (1, 0),
            )],
            vec![PathBuf::from("current")],
        );
        manifest.dirs.push(ManifestDir {
            path: PathBuf::from("current"),
            mode: 0o555,
            mtime_secs: 1_700_000_000,
            mtime_nanos: 9,
        });

        restore_tree(&blobs, &manifest, dest.path()).unwrap();

        let current = fs::symlink_metadata(dest.path().join("current")).unwrap();
        assert!(current.is_dir());
        assert_eq!(current.permissions().mode() & 0o7777, 0o555);
        assert_eq!(
            FileTime::from_last_modification_time(&current),
            FileTime::from_unix_time(1_700_000_000, 9)
        );
        assert_eq!(fs::read(dest.path().join("current/f")).unwrap(), b"x");
        assert_eq!(fs::read_dir(dest.path().join("kept")).unwrap().count(), 0);
        fs::set_permissions(
            dest.path().join("current"),
            fs::Permissions::from_mode(0o700),
        )
        .unwrap();
    }

    #[test]
    fn restore_replays_links_and_the_attributes_of_kept_directories() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let dest = TempDir::new().unwrap();
        let d = dest.path().join("d");
        fs::create_dir(&d).unwrap();
        fs::write(d.join("old"), b"x").unwrap();
        fs::write(dest.path().join("f"), b"x").unwrap();
        let mut manifest =
            TreeManifest::new(vec![], vec![PathBuf::from("d/old"), PathBuf::from("f")]);
        for (path, target) in [("f", "t"), ("d/l", "../nowhere")] {
            manifest.links.push(ManifestLink {
                path: PathBuf::from(path),
                target: PathBuf::from(target),
                mtime_secs: 1_600_000_000,
                mtime_nanos: 3,
            });
        }
        manifest.dir_attrs.push(ManifestDirAttrs {
            path: PathBuf::from("d"),
            mode: Some(0o500),
            mtime: Some((1_700_000_000, 9)),
        });

        restore_tree(&blobs, &manifest, dest.path()).unwrap();

        assert_eq!(
            fs::read_link(dest.path().join("f")).unwrap(),
            Path::new("t")
        );
        let link = fs::symlink_metadata(d.join("l")).unwrap();
        assert_eq!(fs::read_link(d.join("l")).unwrap(), Path::new("../nowhere"));
        assert_eq!(
            FileTime::from_last_modification_time(&link),
            FileTime::from_unix_time(1_600_000_000, 3)
        );
        let meta = fs::metadata(&d).unwrap();
        assert_eq!(meta.permissions().mode() & 0o7777, 0o500);
        assert_eq!(
            FileTime::from_last_modification_time(&meta),
            FileTime::from_unix_time(1_700_000_000, 9)
        );
        fs::set_permissions(&d, fs::Permissions::from_mode(0o700)).unwrap();
        let names: Vec<_> = fs::read_dir(&d)
            .unwrap()
            .map(|e| e.unwrap().file_name())
            .collect();
        assert_eq!(names, ["l"]);
    }

    #[test]
    fn a_failed_restore_leaves_a_recorded_directory_as_it_was() {
        let (_store_dir, store) = setup_store();
        let blobs = TreeBlobStore::new(&store);
        let new_blob = blobs.put_file_blob(b"new").unwrap();
        let gone_blob = blobs.put_file_blob(b"gone").unwrap();
        store.remove(&gone_blob).unwrap();
        let before = FileTime::from_unix_time(1_600_000_000, 7);

        let occupied_link = {
            let mut m = TreeManifest::new(vec![], vec![PathBuf::from("d/old")]);
            m.links.push(ManifestLink {
                path: PathBuf::from("d/taken"),
                target: PathBuf::from("t"),
                mtime_secs: 1,
                mtime_nanos: 0,
            });
            m
        };
        let missing_blob = TreeManifest::new(
            vec![
                ManifestEntry::entry_for(PathBuf::from("d/new"), new_blob, 0o644, (1, 0)),
                ManifestEntry::entry_for(PathBuf::from("e"), gone_blob, 0o644, (1, 0)),
            ],
            vec![],
        );
        for mut manifest in [occupied_link, missing_blob] {
            let dest = TempDir::new().unwrap();
            let d = dest.path().join("d");
            fs::create_dir(&d).unwrap();
            fs::write(d.join("old"), b"x").unwrap();
            fs::write(d.join("taken"), b"x").unwrap();
            fs::set_permissions(&d, fs::Permissions::from_mode(0o751)).unwrap();
            filetime::set_file_mtime(&d, before).unwrap();
            manifest.dir_attrs.push(ManifestDirAttrs {
                path: PathBuf::from("d"),
                mode: Some(0o500),
                mtime: Some((1_700_000_000, 9)),
            });

            let err = restore_tree(&blobs, &manifest, dest.path())
                .expect_err("a later entry cannot be replayed");

            assert!(
                matches!(
                    err,
                    TreeError::Occupied { .. } | TreeError::BlobMissing { .. }
                ),
                "{err:?}"
            );
            let meta = fs::metadata(&d).unwrap();
            assert_eq!(meta.permissions().mode() & 0o7777, 0o751);
            assert_eq!(FileTime::from_last_modification_time(&meta), before);
            let mut names: Vec<_> = fs::read_dir(&d)
                .unwrap()
                .map(|e| e.unwrap().file_name())
                .collect();
            names.sort();
            assert_eq!(names, ["old", "taken"]);
        }
    }
}