prov_graph/
index.rs

1//! Index — where stable IDs and (later) the materialized graph live.
2//!
3//! An index fuses two natures (DESIGN §5): the **authoritative** id↔path
4//! registry — not rebuildable from the documents — and (to come) the
5//! **derived** resolution cache and adjacency index, which are. Keeping it
6//! behind a trait is deliberate: a sidecar file, an in-memory map, or a
7//! sync-backed store are all valid homes.
8//!
9//! Only the query half is here — [`IdIndex`], the lookups link resolution
10//! needs. Everything that *changes* a registration (`IndexStore`, the
11//! `Rebase` seam, the in-memory and registry-document stores) is
12//! `prov-store`'s `index` module, for the same reason the write half of
13//! [`fs`](crate::fs) is: a read-only consumer must not merely decline to write,
14//! it must have nothing to write with.
15//!
16//! ## Tombstones — IDs are forever
17//!
18//! DESIGN's open question #1 ("does the registry ever need to survive without
19//! its documents?") is answered **yes, minimally**: deleting a document leaves
20//! a *tombstone* — the ID stops resolving but is never forgotten, so it can
21//! never be reminted to mean something else. A dangling `prov:` reference
22//! then stays *diagnosable* (validation can say "that document was deleted")
23//! instead of becoming a silent re-resolution hazard. [`is_known`] is the
24//! question that tells the two apart.
25//!
26//! [`is_known`]: IdIndex::is_known
27
28use std::path::{Path, PathBuf};
29
30use crate::identity::Id;
31
32/// A registration that would displace one the index already holds.
33///
34/// The index is a **bijection**: one id names one path, one path carries one id.
35/// Registering across an existing entry breaks that, and in one of two
36/// directions — worth telling apart, because what the user has to do about them
37/// differs.
38///
39/// Both are ordinary under sync. `id_storage` defaults to `both`, so a document's
40/// id travels *in its own frontmatter*: a transport can land a copy of a document
41/// under a new name, and now two files spell one id with the registry able to
42/// name only one of them. The registry cannot arbitrate that — only the author
43/// can — so an operation that would resolve it silently refuses instead.
44#[derive(Debug, Clone, PartialEq, Eq)]
45pub enum Collision {
46    /// The id already resolves to a *different* live document. Registering would
47    /// take the id away from a document whose frontmatter still spells it.
48    Id {
49        /// The id being registered.
50        id: Id,
51        /// The document that currently holds it.
52        held_by: PathBuf,
53    },
54    /// The path already carries a *different* id. Registering would drop that id
55    /// out of the registry while the document on disk still spells it — turning a
56    /// live id into an unregistered one.
57    Path {
58        /// The path being registered.
59        path: PathBuf,
60        /// The id it currently carries.
61        held: Id,
62    },
63}
64
65impl std::fmt::Display for Collision {
66    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
67        match self {
68            Collision::Id { id, held_by } => {
69                write!(f, "{id} is already registered to {}", held_by.display())
70            }
71            Collision::Path { path, held } => {
72                write!(f, "{} already carries {held}", path.display())
73            }
74        }
75    }
76}
77
78/// The query half of an ID index: the three lookups link resolution needs, and
79/// no way to change what is stored.
80///
81/// This is the trait [`crate::graph`] is generic over, and it is the whole of
82/// what the read core asks of a registry — `id:` resolution
83/// ([`resolve`](IdIndex::resolve)), the reverse lookup a census entry is tagged
84/// with ([`id_for_path`](IdIndex::id_for_path)), and the tombstone question that
85/// distinguishes "never existed" from "retired"
86/// ([`is_known`](IdIndex::is_known)).
87///
88/// Split out of `prov-store`'s `IndexStore` for the same reason
89/// [`ReadStorage`](crate::fs::ReadStorage) is split out of that crate's
90/// `Storage`: a read-only consumer must be able to depend on traversal without
91/// linking the staging machinery, and `IndexStore`'s staging half is not merely
92/// unused by the read core — it is *stated in write vocabulary*, down to
93/// `rebase`, which only a pending mutation has anything to say to.
94pub trait IdIndex {
95    /// Resolve an ID to its current path. `None` for unknown *and* tombstoned
96    /// IDs — use [`is_known`](IdIndex::is_known) to tell them apart.
97    fn resolve(&self, id: &Id) -> Option<PathBuf>;
98
99    /// The ID currently assigned to `path`, if any.
100    fn id_for_path(&self, path: &Path) -> Option<Id>;
101
102    /// Whether `id` has *ever* been issued — live or tombstoned. This is the
103    /// mint-with-rejection predicate: a fresh ID must be `!is_known`.
104    fn is_known(&self, id: &Id) -> bool {
105        self.resolve(id).is_some()
106    }
107}
108
109/// No index — identity-off workspaces. Registers nothing, resolves nothing.
110#[derive(Debug, Clone, Copy, Default)]
111pub struct NoIndex;
112
113impl IdIndex for NoIndex {
114    fn resolve(&self, _id: &Id) -> Option<PathBuf> {
115        None
116    }
117    fn id_for_path(&self, _path: &Path) -> Option<Id> {
118        None
119    }
120}
prov_graph/index.rs

prov_graph/
index.rs
