prov_graph/

identity.rs

//! Identity — the id *type*, what makes one well-formed, and when a document
//! earns one.
//!
//! An id is a stable, opaque name for a document. This module holds the [`Id`]
//! newtype, the alphabet and length it is spelled in, [`verify`] — the
//! check-character arithmetic that catches a typo'd `id:` link before it
//! dangles silently — and the *policy* half: the trigger set that decides when
//! a document earns an id ([`Registration`]) and the [`IdentityPolicy`] that
//! produces one ([`Minter`]).
//!
//! Policy lives here rather than a layer up because none of it touches storage.
//! [`IdentityPolicy::mint`] is a seeded PRNG and [`mint_workspace_id`] is a pure
//! function; neither can see a workspace, so neither can write to one. The
//! actual write — mint-with-rejection against the index, retrying until the id
//! is unheard-of — is `prov`'s `Workspace::register`, above this crate's
//! read-only boundary. *Where* ids are stored is [`IdStorage`] and
//! [`crate::index`].
//!
//! Identity is optional throughout. The graph and mutation layers operate on
//! paths and never require an id. The default is [`NoIdentity`] — identity off,
//! no id ever written. The recommended lazy policy registers an id only when
//! something durably refers to a document (a link-by-id or a publish), keeping
//! the authoritative set as small as possible.
//!
//! ## The ID scheme
//!
//! Prov's internal IDs share their lineage with diaryx's ARK blades but
//! carry no NAAN or shoulder — they are workspace-internal, not published
//! permalinks (DESIGN §4's two identity layers). The primitives come from the
//! [`moid`] crate (*minimal opaque ID*): an ID is [`BLADE_RANDOM_LEN`]
//! random characters from the 29-character NOID extended-digit alphabet
//! ([`moid::Alphabet::noid_xdigit`] — digits plus consonants: no vowels, so no
//! accidental words; no `l`, so no ambiguity with `1`) plus one NOID check
//! character, so a typo'd ID is *detected* rather than silently resolving to
//! nothing. The alphabet is the canonical NOID one, so the check character
//! agrees with a real NOID minter and not merely with our own arithmetic. An ID
//! may therefore contain — and begin with — a digit; anything stamping one into
//! metadata must keep it a *string* (see `prov-store`'s `edit::infer_scalar`).
//!
//! Minting is random (opaque for free), with uniqueness enforced by rejection
//! against the index — including its tombstones, so a deleted document's ID is
//! never reissued.

use std::path::Path;

use moid::Alphabet;
use moid::SeededRng;

/// A stable, opaque document identifier.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Id(pub String);

impl Id {
    /// The id as a string slice.
    pub fn as_str(&self) -> &str {
        &self.0
    }
}

impl std::fmt::Display for Id {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(&self.0)
    }
}

/// Random characters per ID (excluding the check character). 29^6 ≈ 595M —
/// collision-free in practice for a workspace, enforced absolutely by
/// mint-with-rejection.
pub const BLADE_RANDOM_LEN: usize = 6;

/// Total ID length: the random body plus one check character.
pub const BLADE_LEN: usize = BLADE_RANDOM_LEN + 1;

/// Whether `id` is a well-formed prov ID: correct length, alphabet-only,
/// and a matching trailing check character. This is what catches a typo'd
/// `prov:` link before it dangles silently.
pub fn verify(id: &str) -> bool {
    moid::Minter::new(Alphabet::noid_xdigit(), BLADE_RANDOM_LEN)
        .validate(id)
        .is_ok()
}

/// Where a document's stable ID is persisted — the identity-storage axis
/// (DESIGN §5). Orthogonal to *when* an ID is minted ([`Registration`]) and to
/// how references are spelled; this is purely the ID's *home*.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub enum IdStorage {
    /// **Registry only** (`registry`): IDs live solely in the registry document —
    /// authoritative, non-derivable, resolved by direct lookup. The cleanest
    /// documents (no `id` clutter), but identity does not travel with a file.
    Registry,
    /// **Frontmatter + registry** (`both`, the default): each document also
    /// carries its own ID in an `id` frontmatter field (a portable, self-describing
    /// shadow), and the registry is retained as a rebuildable cache + tombstone
    /// ledger. The ID travels with the file across copies and out-of-band moves.
    #[default]
    Frontmatter,
    /// **Frontmatter only** (`frontmatter`): the `id` field is the sole home; no
    /// registry document is written and resolution rebuilds the id→path map by
    /// scanning frontmatter. Maximally self-describing, but it forfeits tombstones
    /// (a deleted file takes its ID with it), so an ID can in principle be reminted.
    FrontmatterOnly,
}

impl IdStorage {
    /// Whether this mode writes the ID into each document's `id` frontmatter.
    pub fn stamps_frontmatter(self) -> bool {
        matches!(self, IdStorage::Frontmatter | IdStorage::FrontmatterOnly)
    }

    /// Whether this mode keeps a registry document (the authoritative store, or —
    /// under [`Frontmatter`](IdStorage::Frontmatter) — a rebuildable cache).
    pub fn keeps_registry(self) -> bool {
        matches!(self, IdStorage::Registry | IdStorage::Frontmatter)
    }

    /// Parse the `id_storage` config spelling; unknown → `None`. `both` is the
    /// frontmatter+registry default; `frontmatter` is the registry-less mode.
    pub fn from_config_str(value: &str) -> Option<Self> {
        match value {
            "registry" => Some(Self::Registry),
            "both" => Some(Self::Frontmatter),
            "frontmatter" => Some(Self::FrontmatterOnly),
            _ => None,
        }
    }

    /// The `id_storage` config spelling.
    pub fn as_config_str(self) -> &'static str {
        match self {
            Self::Registry => "registry",
            Self::Frontmatter => "both",
            Self::FrontmatterOnly => "frontmatter",
        }
    }
}

fn canonical_minter() -> moid::Minter {
    moid::Minter::new(Alphabet::noid_xdigit(), BLADE_RANDOM_LEN)
}

/// Random characters in a *minted* workspace name — twice a document blade's
/// [`BLADE_RANDOM_LEN`], for a different uniqueness problem.
///
/// A document ID is unique by *rejection*: the minter can see the registry, so a
/// collision is caught and re-rolled, and six characters (29⁶ ≈ 595M) is ample.
/// A workspace name has no such arbiter — nothing can see the other workspaces
/// in the world, which is exactly why `prov_config::is_valid_workspace_id`
/// refuses to promise uniqueness. So the only defense a minted name has is its
/// width: at 29¹² ≈ 3.5 × 10¹⁷, a million independently minted names collide
/// with probability ~10⁻⁶. That is what makes an unaudited mint honest to call
/// globally unique.
pub const WORKSPACE_NAME_RANDOM_LEN: usize = 12;

/// Total length of a minted workspace name: [`WORKSPACE_NAME_RANDOM_LEN`] plus
/// the check character every [`moid`] blade ends with.
pub const WORKSPACE_NAME_LEN: usize = WORKSPACE_NAME_RANDOM_LEN + 1;

/// Mint an opaque global name for a *workspace*, randomizing from `seed`.
///
/// The name a workspace calls itself is normally the user's to choose — it is
/// read by humans, in `id:<workspace>/<id>` references. This is the escape hatch
/// for when there is no good choice to make: a workspace that must be nameable
/// from anywhere, whose owner has no naming authority to lean on and would
/// rather not gamble that `notes` is theirs alone. So this is offered, never
/// applied: nothing in prov mints a workspace name on its own, because a name is
/// a *commitment* (every reference written elsewhere is spelled with it), and
/// prov does not make commitments on a user's behalf.
///
/// The result is a [`moid`] blade over the same NOID extended-digit alphabet as
/// a document ID, and so is always well-formed by
/// `prov_config::is_valid_workspace_id`: no vowels (nothing accidentally spells
/// a word), and no `/`, `:` or whitespace to break the qualifier position it
/// gets written in. It is deliberately *not* prefixed or otherwise marked as
/// minted — a reader of a reference has no business caring whether the name was
/// chosen or rolled.
pub fn mint_workspace_id(seed: u64) -> String {
    moid::Minter::new(Alphabet::noid_xdigit(), WORKSPACE_NAME_RANDOM_LEN)
        .mint_seeded(&mut SeededRng::new(seed))
}

/// Which events cause a document to be assigned (registered) an ID.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Registration {
    /// Register every document at creation time (eager).
    pub on_create: bool,
    /// Register when a document is first referenced by ID (e.g. a wikilink).
    pub on_link: bool,
    /// Register when a document is published.
    pub on_publish: bool,
}

impl Registration {
    /// Never register — identity is effectively off.
    pub const OFF: Self = Self {
        on_create: false,
        on_link: false,
        on_publish: false,
    };
    /// Register only on a durable reference (link-by-id or publish). Recommended.
    pub const LAZY: Self = Self {
        on_create: false,
        on_link: true,
        on_publish: true,
    };
    /// Register every document the moment it is created.
    pub const EAGER: Self = Self {
        on_create: true,
        on_link: true,
        on_publish: true,
    };

    /// Whether any trigger is active.
    pub fn is_active(&self) -> bool {
        self.on_create || self.on_link || self.on_publish
    }
}

/// The registration event a caller is asking about (for example, a
/// workspace's `register` operation).
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Trigger {
    /// A document was created.
    Create,
    /// Something is about to link to the document by ID.
    Link,
    /// The document is being published.
    Publish,
}

impl Registration {
    /// Whether this trigger set fires for `event`.
    pub fn fires_on(&self, event: Trigger) -> bool {
        match event {
            Trigger::Create => self.on_create,
            Trigger::Link => self.on_link,
            Trigger::Publish => self.on_publish,
        }
    }
}

/// A policy deciding when to register documents and how their IDs are minted.
pub trait IdentityPolicy {
    /// The registration trigger set for this policy.
    fn registration(&self) -> Registration;

    /// Mint a fresh ID for the document at `path`. Only called when a trigger
    /// fires, so a disabled policy need never produce a meaningful value.
    /// Uniqueness is the *caller's* job (mint-with-rejection against the
    /// index); a mint may repeat.
    fn mint(&mut self, path: &Path) -> Id;
}

/// Identity disabled — the default. Paths only; no ID is ever minted or written.
#[derive(Debug, Clone, Copy, Default)]
pub struct NoIdentity;

impl IdentityPolicy for NoIdentity {
    fn registration(&self) -> Registration {
        Registration::OFF
    }

    fn mint(&mut self, _path: &Path) -> Id {
        // Unreachable in practice: `OFF` fires no triggers.
        Id(String::new())
    }
}

/// The bundled minting policy: NOID xdigit + check IDs from a seeded PRNG.
///
/// Minting is delegated to [`moid`]: a [`moid::Minter`] over the canonical
/// alphabet ([`canonical_minter`]) driven by a [`moid::SeededRng`]. The RNG is
/// xorshift64 — *not* cryptographic, and not claimed to be: these are opaque
/// internal handles whose uniqueness is enforced by rejection, not by entropy.
/// Both parts are `Clone`/`Debug`, which keeps this policy (and any workspace
/// carrying it) `Clone`/`Debug`, and a fixed seed makes tests deterministic. A
/// deployment wanting stronger opacity (or ARK permalinks, like diaryx)
/// implements [`IdentityPolicy`] itself.
#[derive(Debug, Clone)]
pub struct Minter {
    registration: Registration,
    minter: moid::Minter,
    rng: SeededRng,
}

impl Minter {
    /// Register only on a durable reference (the recommended default),
    /// randomizing from `seed`.
    pub fn lazy(seed: u64) -> Self {
        Self::with(Registration::LAZY, seed)
    }

    /// Register every document at creation, randomizing from `seed`.
    pub fn eager(seed: u64) -> Self {
        Self::with(Registration::EAGER, seed)
    }

    /// Register on a custom trigger set, randomizing from `seed`. A zero seed is
    /// nudged off xorshift64's fixed point by [`moid::SeededRng`].
    pub fn with(registration: Registration, seed: u64) -> Self {
        Self {
            registration,
            minter: canonical_minter(),
            rng: SeededRng::new(seed),
        }
    }
}

impl IdentityPolicy for Minter {
    fn registration(&self) -> Registration {
        self.registration
    }

    fn mint(&mut self, _path: &Path) -> Id {
        Id(self.minter.mint_seeded(&mut self.rng))
    }
}
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn no_identity_is_off() {
        assert!(!NoIdentity.registration().is_active());
    }

    #[test]
    fn lazy_registers_on_link_and_publish_only() {
        let r = Minter::lazy(1).registration();
        assert!(!r.fires_on(Trigger::Create));
        assert!(r.fires_on(Trigger::Link));
        assert!(r.fires_on(Trigger::Publish));
    }

    #[test]
    fn eager_registers_on_create() {
        assert!(Minter::eager(1).registration().fires_on(Trigger::Create));
    }

    #[test]
    fn mints_verified_distinct_opaque_ids() {
        let mut p = Minter::eager(42);
        let a = p.mint(Path::new("a.md"));
        let b = p.mint(Path::new("b.md"));
        assert_ne!(a, b);
        for id in [&a, &b] {
            assert_eq!(id.as_str().len(), BLADE_LEN);
            assert!(verify(id.as_str()), "{id}");
        }
    }

    #[test]
    fn same_seed_is_deterministic() {
        let a = Minter::lazy(7).mint(Path::new("x"));
        let b = Minter::lazy(7).mint(Path::new("y"));
        assert_eq!(a, b, "path does not participate in the mint");
    }

    #[test]
    fn mints_wide_opaque_workspace_names() {
        let a = mint_workspace_id(42);
        let b = mint_workspace_id(43);
        assert_ne!(a, b);
        for name in [&a, &b] {
            assert_eq!(name.chars().count(), WORKSPACE_NAME_LEN);
            // Every constraint the qualifier position imposes, checked here
            // rather than through `prov-config` (which this crate cannot see):
            // non-empty, and none of the three characters that would break
            // `id:<workspace>/<id>` apart.
            assert!(!name.is_empty());
            assert!(
                !name
                    .chars()
                    .any(|c| c == '/' || c == ':' || c.is_whitespace()),
                "{name} cannot be written as a reference qualifier"
            );
        }
    }

    /// A minted workspace name is *wider* than a document ID, and that width is
    /// the entire uniqueness argument — nothing rejects a colliding one, because
    /// nothing can see the other workspaces it might collide with. Asserted at
    /// compile time, since narrowing the constant is the way this would be lost.
    const _: () = assert!(WORKSPACE_NAME_LEN > BLADE_LEN);

    #[test]
    fn a_workspace_name_is_wider_than_a_document_id() {
        assert!(
            mint_workspace_id(1).chars().count() > Minter::lazy(1).mint(Path::new("x")).0.len()
        );
    }

    #[test]
    fn verify_rejects_typos() {
        let id = Minter::lazy(3).mint(Path::new("x")).0;
        assert!(verify(&id));
        // Flip one body character to another alphabet character.
        let mut chars: Vec<char> = id.chars().collect();
        chars[0] = if chars[0] == 'b' { 'c' } else { 'b' };
        let typo: String = chars.iter().collect();
        assert!(!verify(&typo), "{typo}");
        // Wrong length, wrong alphabet (vowels and `y` are both out).
        assert!(!verify("bcd"));
        assert!(!verify("aeiouAy"));
        assert!(!verify("bcdfghy"));
    }

    #[test]
    fn check_char_matches_the_noid_lineage() {
        // Independently computed: the xdigit alphabet leads with the digits, so
        // ordinals b=10,c=11,d=12,f=13,g=14,h=15 weighted by position 1..=6 →
        // 10+22+36+52+70+90 = 280; 280 % 29 = 19 → the 19th xdigit symbol is
        // 'n'. moid computes the same check character, so a full ID with that
        // body validates.
        assert_eq!(Alphabet::noid_xdigit().check_char("bcdfgh"), 'n');
        assert!(verify("bcdfghn"));
    }

    #[test]
    fn an_id_may_be_all_digits() {
        // The point of the xdigit alphabet: digits are in it, so an ID can look
        // like a number — which is why every stamp writes a string scalar.
        let check = Alphabet::noid_xdigit().check_char("012345");
        assert!(verify(&format!("012345{check}")));
    }

    /// The check character's whole reason to exist, stated as a law.
    ///
    /// `verify_rejects_typos` above flips one character of one ID and confirms
    /// the result is refused. That is a witness, and the claim a check character
    /// actually makes is universal: **no single-character substitution of a
    /// valid ID is ever itself valid.** A check digit that caught most typos and
    /// missed some would still pass every example anyone thought to write, and
    /// would silently let a mistyped `id:` reference resolve to nothing while
    /// looking well-formed — the failure `MalformedId` exists to prevent.
    mod properties {
        use super::*;
        use proptest::prelude::*;

        /// The NOID extended-digit alphabet: the ten digits plus the nineteen
        /// consonants that cannot combine into a word (no vowels, no `y`, no
        /// `l`). Twenty-nine symbols, which is where the crate's own "29^6 ≈
        /// 595M" comes from. Written out here so a substitution can be drawn
        /// from it; `every_minted_character_is_in_the_alphabet` keeps the
        /// transcription honest.
        const XDIGIT: &str = "0123456789bcdfghjkmnpqrstvwxz";

        fn minted() -> impl Strategy<Value = String> {
            any::<u64>().prop_map(|seed| Minter::lazy(seed).mint(Path::new("x")).0)
        }

        proptest! {
            #[test]
            fn every_minted_id_verifies_and_is_the_declared_length(id in minted()) {
                prop_assert_eq!(id.chars().count(), BLADE_LEN);
                prop_assert!(verify(&id), "{id}");
            }

            #[test]
            fn every_minted_character_is_in_the_alphabet(id in minted()) {
                for c in id.chars() {
                    prop_assert!(XDIGIT.contains(c), "`{c}` of `{id}` is not an xdigit");
                }
            }

            /// The law. Substitute any one character of a valid ID — body or
            /// check character — for any *other* alphabet character, and the
            /// result must be refused. Every position, every replacement.
            #[test]
            fn no_single_character_slip_survives_verification(
                id in minted(),
                position in 0..BLADE_LEN,
                replacement in 0..XDIGIT.chars().count(),
            ) {
                let alphabet: Vec<char> = XDIGIT.chars().collect();
                let mut chars: Vec<char> = id.chars().collect();
                let replacement = alphabet[replacement];
                prop_assume!(chars[position] != replacement);
                chars[position] = replacement;
                let typo: String = chars.into_iter().collect();
                prop_assert!(
                    !verify(&typo),
                    "`{typo}` is one character from `{id}` and still verified"
                );
            }

            /// A transposition of two *adjacent, different* characters is the
            /// other slip a check character is chosen to catch — the one a
            /// simple sum cannot see, since addition does not care about order.
            #[test]
            fn no_adjacent_transposition_survives_verification(
                id in minted(),
                position in 0..BLADE_LEN - 1,
            ) {
                let mut chars: Vec<char> = id.chars().collect();
                prop_assume!(chars[position] != chars[position + 1]);
                chars.swap(position, position + 1);
                let swapped: String = chars.into_iter().collect();
                prop_assert!(
                    !verify(&swapped),
                    "`{swapped}` transposes two characters of `{id}` and still verified"
                );
            }
        }
    }
}