hyperdir 0.7.0

//! Physical S3 layout for directories and files.
//!
//! Every directory and every file is stored under a UUID-named prefix, with
//! directories and files segregated into two top-level namespaces:
//!
//! ```text
//! s3://<bucket>/[<base>]DIR/<uuid>/      a directory's hyperfile
//! s3://<bucket>/[<base>]FILE/<uuid>/     a file's hyperfile
//! ```
//!
//! The root directory is the directory whose UUID is the nil UUID
//! ([`ROOT_DIR_UUID`]), i.e. `…/DIR/00000000-0000-0000-0000-000000000000/`.
//!
//! Because identity is a UUID rather than a path, a rename never moves any
//! object: only the name->uuid mapping held in the parent directory changes.
//! A child's prefix carries no information about its parent, so the parent
//! context must always be supplied explicitly (it cannot be derived from the
//! child's key).
//!
//! `base` is an opaque prefix placed before `DIR/` and `FILE/`. It is empty
//! by default. A higher layer (e.g. a multi-filesystem host) may set it to
//! namespace several independent trees in one bucket; this crate attaches no
//! meaning to its contents beyond "prepend it".

use uuid::Uuid;

/// UUID of the root directory. The root has no parent and therefore no
/// scatter notification path.
pub const ROOT_DIR_UUID: Uuid = Uuid::nil();

const DIR_NAMESPACE: &str = "DIR";
const FILE_NAMESPACE: &str = "FILE";
const TXN_NAMESPACE: &str = "_TXN";
/// Open-lease objects `_OPEN/<file-uuid>/<mount-id>` (opt-in cross-mount
/// open-but-unlinked). Outside DIR/FILE/_TXN so it is never confused with a
/// directory's scatter, a rename/reclaim intent, or a file's storage.
const OPEN_NAMESPACE: &str = "_OPEN";

/// What an S3 object key denotes within a tree, as classified by
/// [`HyperDirLayout::classify_key`]. Lets an external maintainer (e.g.
/// `hyperfs-keeper`) route an S3 event / Inventory key to the right action
/// without re-encoding the physical layout.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum KeyKind {
    /// A directory scatter object `DIR/<uuid>/!/.../*.{inode,tombstone}`
    /// (a pending create/update/delete). Carries the directory's UUID, the
    /// compaction target.
    DirScatter(Uuid),
    /// A cross-directory rename intent `_TXN/<ulid>.intent`.
    RenameIntent,
    /// A displaced-child reclaim intent `_TXN/<ulid>.reclaim`.
    ReclaimIntent,
    /// A hard-link intent `_TXN/<ulid>.link` (recover a crashed `fs_link`).
    LinkIntent,
    /// A nlink-decrement marker `FILE/<uuid>/*.unref` (rename replaced one of
    /// the file's hard links). Carries the file's UUID, the reclaim candidate.
    UnrefMarker(Uuid),
    /// A second-level inline ("blob") version object `FILE/<uuid>/<ulid>.blob`
    /// (see `docs/second-level-inline.md`). Carries the file's UUID; the
    /// version GC / orphan sweep reclaim candidate.
    InlineBlob(Uuid),
    /// Anything else under this tree (inode/segment/xattr/lease/lock/...).
    Other,
}

/// Builds the S3 keys / URIs for directories and files in a single tree.
#[derive(Debug, Clone, Default)]
pub struct HyperDirLayout {
    /// Opaque prefix prepended to every key, already normalized to either
    /// empty or to end with a single `/`.
    base: String,
}

impl HyperDirLayout {
    /// Layout rooted directly at the bucket: keys are `DIR/<uuid>` etc.
    pub fn new() -> Self {
        Self { base: String::new() }
    }

    /// Layout under an opaque prefix. A trailing `/` is added if missing; an
    /// empty `base` is equivalent to [`HyperDirLayout::new`].
    pub fn with_base(base: &str) -> Self {
        let base = base.trim_end_matches('/');
        let base = if base.is_empty() {
            String::new()
        } else {
            format!("{base}/")
        };
        Self { base }
    }

    /// Key (no bucket, no scheme) of a directory's prefix.
    pub fn dir_key(&self, uuid: &Uuid) -> String {
        format!("{}{DIR_NAMESPACE}/{}", self.base, uuid)
    }

    /// Key (no bucket, no scheme) of a file's prefix.
    pub fn file_key(&self, uuid: &Uuid) -> String {
        format!("{}{FILE_NAMESPACE}/{}", self.base, uuid)
    }

    /// Full `s3://` URI of a directory's prefix.
    pub fn dir_uri(&self, bucket: &str, uuid: &Uuid) -> String {
        format!("s3://{}/{}", bucket, self.dir_key(uuid))
    }

    /// Full `s3://` URI of a file's prefix.
    pub fn file_uri(&self, bucket: &str, uuid: &Uuid) -> String {
        format!("s3://{}/{}", bucket, self.file_key(uuid))
    }

    /// Full `s3://` URI of the root directory's prefix.
    pub fn root_dir_uri(&self, bucket: &str) -> String {
        self.dir_uri(bucket, &ROOT_DIR_UUID)
    }

    /// Key of a cross-directory rename intent object, identified by `txn_id`.
    pub fn txn_key(&self, txn_id: &str) -> String {
        format!("{}{TXN_NAMESPACE}/{}.intent", self.base, txn_id)
    }

    /// Key of a displaced-child reclaim intent object (rename replace-over-
    /// existing), identified by `txn_id`.
    pub fn reclaim_key(&self, txn_id: &str) -> String {
        format!("{}{TXN_NAMESPACE}/{}.reclaim", self.base, txn_id)
    }

    /// Key of a hard-link intent object (`fs_link` crash recovery), identified
    /// by `txn_id` (a ULID, so its age is readable for staleness).
    pub fn link_key(&self, txn_id: &str) -> String {
        format!("{}{TXN_NAMESPACE}/{}.link", self.base, txn_id)
    }

    /// Key of a mount's liveness heartbeat object. Its S3 `last_modified` is the
    /// mount's last-alive time; a stale/absent heartbeat lets the trash reaper
    /// reclaim that mount's open-but-unlinked leftovers after a crash.
    pub fn heartbeat_key(&self, mount_id: &str) -> String {
        format!("{}{TXN_NAMESPACE}/hb.{}", self.base, mount_id)
    }

    /// Key of one mount's **open-lease** for a file: its presence means
    /// `mount_id` holds the (keep-open) file `file_uuid` open. Liveness is
    /// judged by the mount's heartbeat (not this object's mtime); the last
    /// close deletes it, and the trash reaper cleans up a crashed holder's
    /// leftover.
    pub fn open_lease_key(&self, file_uuid: &Uuid, mount_id: &str) -> String {
        format!("{}{OPEN_NAMESPACE}/{}/{}", self.base, file_uuid, mount_id)
    }

    /// LIST prefix covering every mount's open-lease for `file_uuid`.
    pub fn open_lease_prefix(&self, file_uuid: &Uuid) -> String {
        format!("{}{OPEN_NAMESPACE}/{}/", self.base, file_uuid)
    }

    /// LIST prefix covering **all** open-leases in the tree (for the orphan
    /// open-lease sweep).
    pub fn open_lease_sweep_prefix(&self) -> String {
        format!("{}{OPEN_NAMESPACE}/", self.base)
    }

    /// Key of an nlink-decrement marker `FILE/<uuid>/<ulid>.unref` (rename
    /// replaced one of the file's hard links). One per displaced reference,
    /// keyed by the displacement's ULID so the write is idempotent; orphan
    /// reclamation uses `real_nlink = nlink - count(.unref)` with no dir scan.
    pub fn unref_key(&self, file_uuid: &Uuid, ulid: &str) -> String {
        format!("{}/{}.unref", self.file_key(file_uuid), ulid)
    }

    /// Key of a second-level inline ("blob") version object
    /// `FILE/<uuid>/<ulid>.blob`. Each write is a new ULID-named version
    /// (write-once); the current version is pinned by the dirent's `blob_ulid`.
    /// See `docs/second-level-inline.md`.
    pub fn blob_key(&self, file_uuid: &Uuid, ulid: &str) -> String {
        format!("{}/{}.blob", self.file_key(file_uuid), ulid)
    }

    /// Full `s3://` URI of a blob version object.
    pub fn blob_uri(&self, bucket: &str, file_uuid: &Uuid, ulid: &str) -> String {
        format!("s3://{}/{}", bucket, self.blob_key(file_uuid, ulid))
    }

    /// LIST prefix covering every blob version of `file_uuid` (for version GC).
    pub fn blob_prefix(&self, file_uuid: &Uuid) -> String {
        format!("{}/", self.file_key(file_uuid))
    }

    /// LIST prefix covering all rename intent objects.
    pub fn txn_prefix(&self) -> String {
        format!("{}{TXN_NAMESPACE}/", self.base)
    }

    /// LIST prefix covering every directory's prefix (use with delimiter `/`
    /// to enumerate `DIR/<uuid>/` common prefixes).
    pub fn dir_prefix(&self) -> String {
        format!("{}{DIR_NAMESPACE}/", self.base)
    }

    /// LIST prefix covering every file's prefix (use with delimiter `/`
    /// to enumerate `FILE/<uuid>/` common prefixes).
    pub fn file_prefix(&self) -> String {
        format!("{}{FILE_NAMESPACE}/", self.base)
    }

    /// Classify an S3 object key (as delivered by an S3 event / Inventory) into
    /// the maintenance-relevant [`KeyKind`], parsing UUIDs from the key alone
    /// (no object read). Returns `None` if the key is not under this layout's
    /// `base` (so a shared queue's foreign keys are dropped).
    pub fn classify_key(&self, key: &str) -> Option<KeyKind> {
        let rest = key.strip_prefix(&self.base)?;
        if let Some(txn) = rest.strip_prefix(&format!("{TXN_NAMESPACE}/")) {
            if txn.ends_with(".intent") { return Some(KeyKind::RenameIntent); }
            if txn.ends_with(".reclaim") { return Some(KeyKind::ReclaimIntent); }
            if txn.ends_with(".link") { return Some(KeyKind::LinkIntent); }
            return Some(KeyKind::Other);
        }
        if let Some(d) = rest.strip_prefix(&format!("{DIR_NAMESPACE}/")) {
            if let Some((uuid_s, tail)) = d.split_once('/') {
                if tail.starts_with("!/") && (tail.ends_with(".inode") || tail.ends_with(".tombstone")) {
                    if let Ok(u) = Uuid::parse_str(uuid_s) { return Some(KeyKind::DirScatter(u)); }
                }
            }
            return Some(KeyKind::Other);
        }
        if let Some(f) = rest.strip_prefix(&format!("{FILE_NAMESPACE}/")) {
            if let Some((uuid_s, tail)) = f.split_once('/') {
                if tail.ends_with(".unref") {
                    if let Ok(u) = Uuid::parse_str(uuid_s) { return Some(KeyKind::UnrefMarker(u)); }
                }
                if tail.ends_with(".blob") {
                    if let Ok(u) = Uuid::parse_str(uuid_s) { return Some(KeyKind::InlineBlob(u)); }
                }
            }
            return Some(KeyKind::Other);
        }
        Some(KeyKind::Other)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn keys_without_base() {
        let l = HyperDirLayout::new();
        let u = Uuid::nil();
        assert_eq!(l.dir_key(&u), "DIR/00000000-0000-0000-0000-000000000000");
        assert_eq!(l.file_key(&u), "FILE/00000000-0000-0000-0000-000000000000");
        assert_eq!(l.dir_uri("b", &u), "s3://b/DIR/00000000-0000-0000-0000-000000000000");
        assert_eq!(l.root_dir_uri("b"), "s3://b/DIR/00000000-0000-0000-0000-000000000000");
    }

    #[test]
    fn base_is_normalized() {
        assert_eq!(HyperDirLayout::with_base("fs1").dir_key(&Uuid::nil()),
                   "fs1/DIR/00000000-0000-0000-0000-000000000000");
        assert_eq!(HyperDirLayout::with_base("fs1/").dir_key(&Uuid::nil()),
                   "fs1/DIR/00000000-0000-0000-0000-000000000000");
        assert_eq!(HyperDirLayout::with_base("").dir_key(&Uuid::nil()),
                   "DIR/00000000-0000-0000-0000-000000000000");
    }

    #[test]
    fn classify_key_cases() {
        let u = Uuid::parse_str("11111111-1111-1111-1111-111111111111").unwrap();
        for l in [HyperDirLayout::new(), HyperDirLayout::with_base("fs1")] {
            let p = &l.base; // "" or "fs1/"
            // dir scatter (create/update/delete) -> DirScatter(uuid)
            assert_eq!(l.classify_key(&format!("{p}DIR/{u}/!/QQ/01_{u}_1.inode")), Some(KeyKind::DirScatter(u)));
            assert_eq!(l.classify_key(&format!("{p}DIR/{u}/!/QQ/01_{u}_4.tombstone")), Some(KeyKind::DirScatter(u)));
            // dir inode / segment / lease -> Other (note `…/inode` is not `.inode`)
            assert_eq!(l.classify_key(&format!("{p}DIR/{u}/inode")), Some(KeyKind::Other));
            assert_eq!(l.classify_key(&format!("{p}DIR/{u}/_compact.lease")), Some(KeyKind::Other));
            // txn intents
            assert_eq!(l.classify_key(&format!("{p}_TXN/01ABC.intent")), Some(KeyKind::RenameIntent));
            assert_eq!(l.classify_key(&format!("{p}_TXN/01ABC.reclaim")), Some(KeyKind::ReclaimIntent));
            assert_eq!(l.classify_key(&format!("{p}_TXN/01ABC.link")), Some(KeyKind::LinkIntent));
            // unref marker -> UnrefMarker(uuid); plain file inode -> Other
            assert_eq!(l.classify_key(&format!("{p}FILE/{u}/01ABC.unref")), Some(KeyKind::UnrefMarker(u)));
            assert_eq!(l.classify_key(&format!("{p}FILE/{u}/01ABC.blob")), Some(KeyKind::InlineBlob(u)));
            assert_eq!(l.classify_key(&format!("{p}FILE/{u}/inode")), Some(KeyKind::Other));
        }
        // foreign base -> None
        assert_eq!(HyperDirLayout::with_base("fs1").classify_key("fs2/_TXN/x.intent"), None);
        assert_eq!(HyperDirLayout::with_base("fs1").classify_key(&format!("DIR/{u}/inode")), None);
    }
}