ingraph 0.1.0

A declaration-driven indexing framework: records and nodes are written as Rust types, and the storage rows, the dataflow between them and the GraphQL query surface are emitted from the declaration.
Documentation
//! **THE RETIRED MIRROR**: which root keys are out, answered without a lock and without a database.
//!
//! The ledger is the truth and a truth in a database is not a thing a read path may consult per hit.
//! So the keys a family has retired are held a second time, in memory, in the one shape whose read
//! side costs a pointer dereference: [`left_right`]'s pair. One writer — the [`Keeper`](super::Keeper)
//! — appends and publishes; every reader holds its own handle and never blocks, never waits, and
//! never contends with another reader.
//!
//! # IT IS EVENTUALLY CONSISTENT, and that is a promise rather than a shortcoming
//!
//! A reader sees a retirement once the writer has PUBLISHED it, and not before. What that costs is
//! bounded and nameable: for the window between the durable row and the publish, a read path still
//! answers *present* for a key that is out. What it buys is that the window is on the SAFE side of
//! the two — the ledger already says retired, so a restart, a re-read or the next publish all
//! converge on the truth, and nothing is ever hidden that the ledger did not first agree to hide.
//!
//! The opposite ordering is what this module exists to make unwritable. A mirror published BEFORE
//! the row would hide a key that a crash then un-retires: the reader saw a retirement the ledger
//! never recorded, and no restart repairs it because nothing durable disagrees. See
//! [`Keeper`](super::Keeper), where the ordering is performed.
//!
//! # WHAT IT IS NOT
//!
//! It is not the read side's filter. Nothing here rewrites a query, batches a membership probe or
//! joins anything — those are the visibility knife's, and this is only the fact they will ask. What
//! is here is the fact, its single writer, and the two ops that move it.

use core::hash::Hash;

use std::{
  collections::HashSet,
  sync::{Mutex, MutexGuard},
};

use left_right::{Absorb, ReadHandle, ReadHandleFactory, WriteHandle};

use crate::drive::registry::RootKey;

/// ONE OP ON THE MIRROR — the two, and there are only two.
///
/// They are [`Retirement`](crate::Retirement)'s own pair seen from the cache side: a row written is
/// a key marked, a row erased is a key unmarked. Nothing else can happen to a mirror, which is why
/// this is an enum a reader can hold in their head rather than a command language.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
enum Mark<Root> {
  /// `Root` is OUT — the ledger's row already exists.
  Mark(Root),
  /// `Root` is back — the ledger's row is already gone.
  Unmark(Root),
}

/// THE SET, wearing a name so it can absorb.
///
/// A newtype purely because [`Absorb`] is `left_right`'s and [`HashSet`] is the standard library's;
/// nothing is added to the set and nothing is taken away.
#[derive(Debug, Clone, Default)]
struct Retirees<Root>(HashSet<Root>);

impl<Root> Absorb<Mark<Root>> for Retirees<Root>
where
  Root: Clone + Eq + Hash,
{
  /// The FIRST copy takes the op by `&mut`, so the key is cloned rather than moved — the second
  /// copy needs the same op, and an op that gave its key away could not be replayed.
  fn absorb_first(&mut self, operation: &mut Mark<Root>, _other: &Self) {
    match operation {
      Mark::Mark(key) => {
        self.0.insert(key.clone());
      }
      Mark::Unmark(key) => {
        self.0.remove(key);
      }
    }
  }

  /// The SECOND copy takes the op BY VALUE and is the last to see it, so the key moves.
  ///
  /// Written rather than left to the default (which forwards to
  /// [`absorb_first`](Absorb::absorb_first)) for exactly that: the default would clone a key this
  /// call could consume, on every retirement, forever.
  fn absorb_second(&mut self, operation: Mark<Root>, _other: &Self) {
    match operation {
      Mark::Mark(key) => {
        self.0.insert(key);
      }
      Mark::Unmark(key) => {
        self.0.remove(&key);
      }
    }
  }

  /// The two copies are one set, so catching up is taking the other's.
  ///
  /// A clone rather than a replay, on the trait's own instruction: what `sync_with` owes is that
  /// `self` matches `first` EXACTLY afterwards, and a [`HashSet`] re-built by replay could differ
  /// from one built by insertion order in nothing that matters here — but the clone is the answer
  /// that cannot be wrong, and it happens once, at the first publish.
  fn sync_with(&mut self, first: &Self) {
    self.0.clone_from(&first.0);
  }
}

/// **ONE READER'S OWN HANDLE** onto the mirror — a wait-free membership test.
///
/// It is per-THREAD and deliberately so: a handle is what makes the read wait-free, and a handle
/// shared between threads would be the shared word this whole shape exists not to have. Mint one
/// per worker from a [`RetiredReaders`], which IS shareable.
pub struct RetiredReader<Root> {
  handle: ReadHandle<Retirees<Root>>,
}

impl<Root> core::fmt::Debug for RetiredReader<Root> {
  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
    f.debug_struct("RetiredReader").finish_non_exhaustive()
  }
}

impl<Root> RetiredReader<Root>
where
  Root: RootKey,
{
  /// **IS `key` OUT?** — as of the last publish this reader has seen.
  ///
  /// `false` where the mirror has been dropped, which is a deployment shutting down rather than an
  /// answer about the key: a reader that outlives its writer answers *nothing is retired*, which is
  /// the same posture the framework takes everywhere a cache is gone — the truth is the ledger, and
  /// a torn-down world has no read path to protect.
  #[must_use]
  pub fn retired(&self, key: &Root) -> bool {
    self.handle.enter().is_some_and(|held| held.0.contains(key))
  }

  /// **HOW MANY KEYS ARE OUT** — as of the last publish this reader has seen.
  #[must_use]
  pub fn held(&self) -> usize {
    self.handle.enter().map_or(0, |held| held.0.len())
  }
}

/// **THE MINT FOR READERS** — shareable, cloneable, and the only thing a worker needs to be handed.
///
/// [`RetiredReader`] is per-thread; this is what crosses. It is what a resident is given at wiring
/// time so that each worker can take its own handle once and keep it.
pub struct RetiredReaders<Root> {
  factory: ReadHandleFactory<Retirees<Root>>,
}

impl<Root> Clone for RetiredReaders<Root> {
  fn clone(&self) -> Self {
    Self {
      factory: self.factory.clone(),
    }
  }
}

impl<Root> core::fmt::Debug for RetiredReaders<Root> {
  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
    f.debug_struct("RetiredReaders").finish_non_exhaustive()
  }
}

impl<Root> RetiredReaders<Root> {
  /// This thread's own handle.
  #[must_use]
  pub fn reader(&self) -> RetiredReader<Root> {
    RetiredReader {
      handle: self.factory.handle(),
    }
  }
}

/// **THE MIRROR**: the single writer's side, and the mint every reader comes from.
///
/// # ONE WRITER, and the [`Mutex`] is how that is stated rather than hoped for
///
/// `left_right`'s [`WriteHandle`] needs `&mut` and there is exactly one party that has anything to
/// write — the [`Keeper`](super::Keeper) for this family. So the handle sits behind a mutex that is
/// never contended in a correct deployment, and the mutex is doing the job a `&mut` would if the
/// mirror were not shared: making *two writers* impossible rather than merely improbable.
///
/// # `mark`/`unmark` PUBLISH, and that is the door's whole shape
///
/// A staged op nobody has published is invisible, so a door that appended without publishing would
/// be a door whose effect a caller could not observe. Both verbs therefore append and publish in
/// one act, and the ORDERING that matters — the durable write first — is the caller's, one type
/// over, where a store's future is awaited before either verb is reached.
pub struct RetiredMirror<Root: RootKey> {
  /// The one writer's handle. See the type note for why it is behind a lock.
  writer: Mutex<WriteHandle<Retirees<Root>, Mark<Root>>>,
  /// The mint every reader comes from.
  readers: RetiredReaders<Root>,
}

impl<Root: RootKey> core::fmt::Debug for RetiredMirror<Root> {
  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
    f.debug_struct("RetiredMirror")
      .field("held", &self.held())
      .finish_non_exhaustive()
  }
}

impl<Root: RootKey> Default for RetiredMirror<Root> {
  fn default() -> Self {
    Self::new()
  }
}

impl<Root: RootKey> RetiredMirror<Root> {
  /// An empty mirror — nothing retired, which is what a deployment starts at before its boot road
  /// has read the ledger.
  #[must_use]
  pub fn new() -> Self {
    // `new_from_empty` rather than `new`, on the crate's own warning: `HashSet::default` mints a
    // fresh `RandomState` per call, so two `Default`-built copies would iterate differently — and
    // the trait asks for two instances that behave EXACTLY the same. Cloning one empty set gives
    // both halves the same hasher.
    let (writer, reader) =
      left_right::new_from_empty::<Retirees<Root>, Mark<Root>>(Retirees(HashSet::new()));
    Self {
      readers: RetiredReaders {
        factory: reader.factory(),
      },
      writer: Mutex::new(writer),
    }
  }

  /// A mirror already holding `keys` — the BOOT shape, built from what the ledger's `roll` said.
  ///
  /// One publish for the whole set rather than one per key: a rebuild has no reader to be
  /// eventually consistent WITH yet, and a publish per row would pay the two-copy absorb twice for
  /// every retiree a deployment has ever had.
  #[must_use]
  pub fn rebuilt(keys: impl IntoIterator<Item = Root>) -> Self {
    let mirror = Self::new();
    {
      let mut writer = mirror.writer();
      for key in keys {
        writer.append(Mark::Mark(key));
      }
      writer.publish();
    }
    mirror
  }

  /// The mint every reader comes from.
  #[inline]
  #[must_use]
  pub fn readers(&self) -> RetiredReaders<Root> {
    self.readers.clone()
  }

  /// One reader of this writer's own — the door a single-threaded caller and a test both take.
  #[inline]
  #[must_use]
  pub fn reader(&self) -> RetiredReader<Root> {
    self.readers.reader()
  }

  /// **`key` IS OUT** — published, so the next read on any handle sees it.
  ///
  /// Called AFTER the ledger's row has landed. See the module note for what the other order would
  /// cost.
  pub fn mark(&self, key: Root) {
    self.writer().append(Mark::Mark(key)).publish();
  }

  /// **`key` IS BACK** — published, for [`mark`](Self::mark)'s reasons in the other direction.
  ///
  /// Called AFTER the ledger's row has been erased.
  pub fn unmark(&self, key: Root) {
    self.writer().append(Mark::Unmark(key)).publish();
  }

  /// **HOW MANY KEYS ARE OUT**, as a reader would see them.
  #[must_use]
  pub fn held(&self) -> usize {
    self.published(|held| held.0.len())
  }

  /// Whether `key` is out, as a reader would see it — the door a boot check and a test take, where
  /// minting a reader to ask one question would be ceremony.
  #[must_use]
  pub fn retired(&self, key: &Root) -> bool {
    self.published(|held| held.0.contains(key))
  }

  /// **WHAT A READER WOULD SEE**, read through the writer's own handle.
  ///
  /// `left_right`'s [`WriteHandle`] derefs to a [`ReadHandle`], so the writer already holds the door
  /// onto the PUBLISHED copy — which is the honest thing for these two doors to answer. A door that
  /// read the writer's unpublished side would report a staged op as visible, and both verbs above
  /// publish, so there is never a staged op for it to be right about.
  ///
  /// A closure rather than a borrow handed out, because what it borrows lives inside a guard that
  /// is about to drop.
  fn published<T>(&self, read: impl FnOnce(&Retirees<Root>) -> T) -> T {
    let writer = self.writer();
    let held = writer
      .enter()
      .expect("a mirror whose own writer is held has a copy to read");
    read(&held)
  }

  /// The one writer's handle.
  ///
  /// A poisoned lock is READ THROUGH rather than propagated — `unwrap_or_else(into_inner)`, this
  /// crate's own idiom, and the same one [`Registry::shard`](crate::Registry) states its reasoning
  /// at: a panic while an op was staged leaves a handle that has not published, and the recovery
  /// from that is the next act over it, not a deployment that refuses to retire anything ever
  /// again.
  fn writer(&self) -> MutexGuard<'_, WriteHandle<Retirees<Root>, Mark<Root>>> {
    self.writer.lock().unwrap_or_else(|held| held.into_inner())
  }
}