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 keyset cursor: typed inside, one opaque string outside.
//!
//! ```text
//! Cursor<V>          the typed face: the order it was minted under, and the row's ordering tuple
//!   .encode()        → one base64url string, which is the whole of what a client ever holds
//!   .decode(&str)    ← that string, checked back into typed values
//!   .resume(order)   → those values, or why this cursor is not this order's
//! ```
//!
//! A page over a written order is resumed by comparing the next row's ordering tuple against the
//! last one served. The tuple is `(sort values…, key values…)`: the sort values are what the client
//! wrote the order over, and the key tail is what makes that order TOTAL, so that a boundary
//! between two rows with equal sort values still has exactly one place in it.
//!
//! # What the string carries, and in which order
//!
//! ```text
//! version : 1 byte      what this build knows how to read
//! order   : 8 bytes     the OrderSignature, big-endian
//! slots   : n × …       1 byte of presence, then — for a value — 4 bytes of length and the bytes
//! ```
//!
//! then base64url with no padding. Nothing about the frame is JSON, and that is
//! [the same law](crate::comparison) the storage side holds to for the same reason: a second schema
//! between a typed value and the column it is compared against is a second set of coercions to be
//! wrong in.
//!
//! Lengths are big-endian, which is what every durable number in this crate is — see
//! [`BeU64`](crate::BeU64), whose `to_blob` the signature's own bytes are.
//!
//! # The presence byte is SQL `NULL`, and it is not an encoding of one
//!
//! A nullable sort column's value at the boundary row may be absent, and absent is a POSITION in
//! the order rather than a missing field: under this framework's pinning it sorts below every
//! value, so the row after it is found by a comparison that names `IS NULL` rather than one that
//! binds something. A slot therefore holds `Option<V>` and the frame spells the `None` — a
//! sentinel inside `V`'s own encoding would be a value of `V` that a real column could also hold.
//!
//! # Everything a client can hand back is CHECKED
//!
//! A cursor is a string the client had. Every step refuses rather than guessing: the alphabet, the
//! padding, the version byte, each slot's own bytes, the count of them, and — last and loudest —
//! whether this cursor was minted under the order it is being replayed against. See [`CursorError`].
//!
//! # It is SESSION-LIVED STATE, not a durable id
//!
//! A page cursor exists so a client can say *carry on from here*. It is minted by a walk, handed
//! back within that walk, and expected to die with the session — nothing stores one, and nothing may
//! assume one still means anything later. Two consequences follow and both are load-bearing:
//!
//! - **An order change invalidates outstanding tokens**, which [`OrderSignature`] already enforces by
//!   name. A cursor minted under another order is refused rather than replayed against columns it was
//!   never read from.
//! - **A storage-engine change invalidates them too**, and that needs no new machinery. A value's
//!   bytes may differ per engine ([`DialectCursor`]), so a token minted at one store and handed to
//!   another is bytes the receiving codec did not write — refused by the width and domain checks
//!   every codec already owes, as [`CursorError::Value`] at the slot's own position. **No dialect tag
//!   rides the frame and no envelope wraps it**: self-description would cost bytes in every token to
//!   improve the message of a case that already refuses.

mod order;
/// `pub(crate)` rather than `pub(super)`: the SEARCH tier's page token wears the same
/// spelling, and one base64url in this crate is what keeps a token from being legal at one tier and
/// illegal at the other. Still crate-private — the alphabet is an implementation of two wire words,
/// not a service this crate publishes.
pub(crate) mod text;
mod value;

pub use order::{OrderFold, OrderLevels, OrderSignature, OrderTerm, TermName, TermSubject, Walk};
pub use value::{CursorCodec, CursorValue, DialectCursor, dialect, read_member, write_member};

/// The one frame version this build writes and reads.
const VERSION: u8 = 1;

/// A slot holding no value — SQL `NULL` at that column of the boundary row.
const ABSENT: u8 = 0;

/// A slot holding a value, followed by its length and its bytes.
const PRESENT: u8 = 1;

/// The width of a slot's length prefix.
const LENGTH: usize = size_of::<u32>();

/// A position in a written order: the ordering tuple of one row, and the signature of the order it
/// was read under.
///
/// # Typed inside
///
/// The values are `V`, the storage type the columns are compared in, and never text. That is what
/// keeps the comparison in SQL, against BOUND parameters, in the column's own type and under the
/// column's own collation — a cursor that carried rendered text would be comparing strings, which
/// is a different order for every column that is not one.
///
/// `V` is ONE type across the tuple, which for a heterogeneous order is the record's own sum over
/// its orderable columns — the arrangement [`SqlKeyIn`](crate::comparison::sql::SqlKeyIn) already
/// takes, where *a key whose columns have DIFFERENT storage types needs a carrier over a
/// heterogeneous tuple*. Here the sum is writable, because the set of columns is the record's and
/// the record's expansion is what writes it.
///
/// # It is minted UNDER an order, and there is no way to give it another signature
///
/// [`at`](Self::at) is the only public constructor and it takes the order. A signature is not a
/// free parameter of a cursor: it IS the order the values were read in, and a constructor taking
/// the two separately would be a place for them to disagree.
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub struct Cursor<V> {
  signature: OrderSignature,
  values: Box<[Option<V>]>,
}

impl<V> Cursor<V> {
  /// The cursor at a row whose ordering tuple is `values`, minted under `order`.
  ///
  /// `values` runs in `order`'s own sequence — one slot per term, sort values then key values, as
  /// the terms were written. Nothing here checks the two are the same length: a mint is the
  /// framework's own call with both halves in hand, and it is [`resume`](Self::resume) — where the
  /// cursor is a client's again — that has something to check.
  #[must_use]
  pub fn at(order: &[OrderTerm], values: impl Into<Box<[Option<V>]>>) -> Self {
    Self {
      signature: OrderSignature::of(order),
      values: values.into(),
    }
  }

  /// The order this cursor was minted under.
  #[inline]
  #[must_use]
  pub const fn signature(&self) -> OrderSignature {
    self.signature
  }

  /// The boundary row's ordering tuple, in the order's own sequence.
  #[inline]
  #[must_use]
  pub fn values(&self) -> &[Option<V>] {
    &self.values
  }

  /// The values this cursor resumes `order` at, or why it cannot.
  ///
  /// **The refusals happen here, before any SQL is rendered.** All three are silent wrong answers
  /// if they are not made: a cursor from another order compares values against columns they were
  /// never read from, a tuple of the wrong width leaves a column comparing against nothing, and a
  /// `NULL` where the column cannot hold one is a comparison that matches no row on an engine that
  /// checks and every row on one that does not.
  ///
  /// # Errors
  ///
  /// [`CursorError::Order`] where the signature is another order's; [`CursorError::Arity`] where
  /// the tuple's width is not the order's; [`CursorError::Null`] where a slot is absent at a
  /// `NOT NULL` term.
  pub fn resume(&self, order: &[OrderTerm]) -> Result<&[Option<V>], CursorError> {
    let presented = OrderSignature::of(order);
    if presented != self.signature {
      return Err(CursorError::Order(OrderMismatch::new(
        self.signature,
        presented,
      )));
    }
    if self.values.len() != order.len() {
      return Err(CursorError::Arity(ArityMismatch::new(
        self.values.len(),
        order.len(),
      )));
    }
    for (term, value) in order.iter().zip(&self.values) {
      if value.is_none() && !term.is_nullable() {
        return Err(CursorError::Null(term.identity()));
      }
    }
    Ok(&self.values)
  }
}

impl<V: CursorValue> Cursor<V> {
  /// This cursor as the one string a client ever sees.
  #[must_use]
  pub fn encode(&self) -> String {
    let mut frame = Vec::with_capacity(1 + self.signature.to_blob().len() + self.values.len() * 8);
    frame.push(VERSION);
    frame.extend_from_slice(&self.signature.to_blob());
    for value in &self.values {
      let Some(value) = value else {
        frame.push(ABSENT);
        continue;
      };
      frame.push(PRESENT);
      // The length is written after the bytes are, because a row appends and only the buffer knows
      // how much it appended. Reserving the four bytes and filling them in is what keeps a value's
      // encoding from having to be produced twice or into a buffer of its own.
      let at = frame.len();
      frame.extend_from_slice(&[0; LENGTH]);
      value.write_cursor(&mut frame);
      let length = u32::try_from(frame.len() - at - LENGTH).unwrap_or(u32::MAX);
      frame[at..at + LENGTH].copy_from_slice(&length.to_be_bytes());
    }
    text::encode(&frame)
  }

  /// The cursor `text` spells, or why it is not one.
  ///
  /// It reads the FRAME and the values, and says nothing about the order — a cursor decodes on its
  /// own and is bound to an order at [`resume`](Self::resume), which is where the signature is
  /// compared. The two are separate because a caller holding a decoded cursor with the wrong
  /// signature has a different thing to say than one holding a mangled string.
  ///
  /// # Errors
  ///
  /// [`CursorError::Alphabet`] where `text` is not base64url; [`CursorError::Truncated`] where the
  /// frame ends inside a field; [`CursorError::Version`] for a version this build does not know;
  /// [`CursorError::Value`] where a slot's bytes are not a value of `V`.
  pub fn decode(text: &str) -> Result<Self, CursorError> {
    let frame = text::decode(text).ok_or(CursorError::Alphabet)?;
    let (version, rest) = frame.split_first().ok_or(CursorError::Truncated)?;
    if *version != VERSION {
      return Err(CursorError::Version(*version));
    }
    let (signature, mut rest) = rest
      .split_at_checked(size_of::<u64>())
      .ok_or(CursorError::Truncated)?;
    let signature = OrderSignature::from_blob(signature).ok_or(CursorError::Truncated)?;

    let mut values = Vec::new();
    while let Some((presence, tail)) = rest.split_first() {
      match *presence {
        ABSENT => {
          values.push(None);
          rest = tail;
        }
        PRESENT => {
          let (length, tail) = tail
            .split_at_checked(LENGTH)
            .ok_or(CursorError::Truncated)?;
          // The claimed length is a client's number, so it is used to SPLIT the bytes that are
          // already here rather than to reserve any: a slice that is not there is `Truncated` and
          // never an allocation.
          let length = usize::try_from(u32::from_be_bytes(
            length.try_into().expect("split_at_checked gave four bytes"),
          ))
          .map_err(|_| CursorError::Truncated)?;
          let (bytes, tail) = tail
            .split_at_checked(length)
            .ok_or(CursorError::Truncated)?;
          values.push(Some(
            V::read_cursor(bytes).ok_or(CursorError::Value(values.len()))?,
          ));
          rest = tail;
        }
        // A presence byte that is neither is a frame this build cannot read, and reading it as
        // either would be reading a slot that was never written.
        _ => return Err(CursorError::Truncated),
      }
    }
    Ok(Self {
      signature,
      values: values.into_boxed_slice(),
    })
  }
}

/// The payload of [`CursorError::Order`]: the order the cursor was minted under, and the one it was
/// replayed against.
///
/// **The refusal the signature exists for.** Both fingerprints travel so that a deployment reading
/// its logs can see a replay under a changed order for what it is.
///
/// It is a MISMATCH rather than an `OrderError`, because what it holds is the disagreement and not
/// one bad order: neither signature is wrong on its own, and the other name is a step from
/// [`SqlOrderError`](crate::comparison::sql::SqlOrderError), which is a different refusal about a
/// different thing.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct OrderMismatch {
  minted: OrderSignature,
  presented: OrderSignature,
}

impl OrderMismatch {
  /// Record that a cursor minted under `minted` was replayed against `presented`.
  #[inline]
  pub(crate) const fn new(minted: OrderSignature, presented: OrderSignature) -> Self {
    Self { minted, presented }
  }

  /// The order the cursor carries.
  #[inline]
  pub const fn minted(&self) -> OrderSignature {
    self.minted
  }

  /// The order it was replayed against.
  #[inline]
  pub const fn presented(&self) -> OrderSignature {
    self.presented
  }
}

/// The payload of [`CursorError::Arity`]: how wide the cursor's tuple is, and how wide the order
/// is.
///
/// A MISMATCH for the reason [`OrderMismatch`] is: a width is not wrong by itself, and what this
/// carries is the two of them disagreeing.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct ArityMismatch {
  values: usize,
  terms: usize,
}

impl ArityMismatch {
  /// Record that a cursor of `values` slots was replayed against an order of `terms` terms.
  #[inline]
  pub(crate) const fn new(values: usize, terms: usize) -> Self {
    Self { values, terms }
  }

  /// How many values the cursor carries.
  #[inline]
  pub const fn values(&self) -> usize {
    self.values
  }

  /// How many terms the order has.
  #[inline]
  pub const fn terms(&self) -> usize {
    self.terms
  }
}

/// Why a cursor cannot be honoured.
///
/// One type for two moments, because the caller is one and the answer is one — this cursor does
/// not page this query. The variants say which moment: the first four are
/// [`decode`](Cursor::decode)'s, over a string a client handed back, and the last three are
/// [`resume`](Cursor::resume)'s, over a cursor that decoded perfectly well and belongs to another
/// query.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CursorError {
  /// The string is not base64url with no padding — a symbol outside the alphabet, a `=`, or a
  /// group that no encoding produces.
  Alphabet,
  /// The frame ends inside a field, or holds a presence byte that is neither of the two.
  Truncated,
  /// A frame version this build does not know, carried so a deployment can see which one arrived.
  ///
  /// There is no version below the current one, so this is a cursor from the FUTURE — a client
  /// holding one minted by a newer build, which is an ordinary thing during a rollout and an
  /// ordinary refusal rather than a bug.
  Version(u8),
  /// A slot's bytes are not a value of the cursor's type, at the slot's own position — carried as
  /// which slot, counting from the first.
  Value(usize),
  /// The cursor was minted under another order — see [`OrderMismatch`].
  Order(OrderMismatch),
  /// The cursor's tuple is not as wide as the order has terms — see [`ArityMismatch`].
  Arity(ArityMismatch),
  /// A slot is absent where its term's column cannot hold `NULL` — carried as the term whose column
  /// is `NOT NULL`.
  Null(&'static TermName),
}

impl core::fmt::Display for CursorError {
  fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
    match self {
      Self::Alphabet => f.write_str("this cursor is not base64url"),
      Self::Truncated => f.write_str("this cursor's frame ends inside a field"),
      Self::Version(version) => write!(
        f,
        "this cursor is version {version} and this build reads version {VERSION}"
      ),
      Self::Value(at) => write!(f, "this cursor's value {at} is not a value of that column"),
      Self::Order(mismatch) => write!(
        f,
        "this cursor was minted under another order ({:#018x}, replayed against {:#018x})",
        mismatch.minted().get(),
        mismatch.presented().get()
      ),
      Self::Arity(mismatch) => write!(
        f,
        "this cursor carries {} values and the order has {} terms",
        mismatch.values(),
        mismatch.terms()
      ),
      Self::Null(term) => {
        let term: &str = term;
        write!(f, "this cursor is null at `{term}`, which is NOT NULL")
      }
    }
  }
}

impl core::error::Error for CursorError {}

#[cfg(test)]
mod tests;