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
//! What the signature is a fingerprint OF, and what a backward walk does to a term.
//!
//! The load-bearing tests here are the two halves of the rename measurement: a
//! `<db>(rename)` must not SPLIT one order into two signatures, and must not ALIAS two
//! orders into one. Both are silent wrong answers — the first refuses a cursor that is perfectly
//! good, the second serves a page computed against the wrong column — and neither is visible in the
//! rendered SQL.

use super::{OrderSignature, OrderTerm, TermName, Walk};
use crate::{ColumnName, ColumnShape, FieldName, OrderDirection, OrderLevel};

/// The two identities the rename measurement is written over.
const CREATED: &TermName = TermName::new("created_at");
const TITLE: &TermName = TermName::new("title");

/// The key tail every written order ends with.
const ID: &TermName = TermName::new("id");

/// One order as SQLite spells its columns — no rename, so every column keeps its declared name.
fn sqlite_order() -> [OrderTerm; 2] {
  [
    OrderTerm::new(CREATED, FieldName::new("created_at"), OrderDirection::Desc),
    OrderTerm::new(ID, FieldName::new("id"), OrderDirection::Asc),
  ]
}

/// The SAME written order as Postgres spells it, where `postgres(rename = "created")` has
/// moved one column's name and nothing else.
fn postgres_order() -> [OrderTerm; 2] {
  [
    OrderTerm::new(CREATED, FieldName::new("created"), OrderDirection::Desc),
    OrderTerm::new(ID, FieldName::new("id"), OrderDirection::Asc),
  ]
}

/// **The first half of the measurement.** A rename moves the COLUMN and not the order, so the two
/// dialects' spellings of one written order fingerprint alike — and a cursor minted while a
/// deployment stored Postgres resumes against its SQLite without a false refusal.
#[test]
fn a_rename_does_not_split_one_order_into_two_signatures() {
  assert_ne!(sqlite_order()[0].column(), postgres_order()[0].column());
  assert_eq!(sqlite_order()[0].identity(), postgres_order()[0].identity());

  assert_eq!(
    OrderSignature::of(&sqlite_order()),
    OrderSignature::of(&postgres_order())
  );
}

/// **The second half.** Two columns whose per-database renames CROSS carry each other's rendered
/// name, so a fingerprint over rendered names would call these two orders the same one. Over
/// identities they are two.
#[test]
fn crossed_renames_do_not_alias_two_orders_into_one() {
  // `title` in this database renders as `created`, which is what the other order's own column
  // renders as — the crossing a rendered-name fingerprint cannot see through.
  let crossed = [
    OrderTerm::new(TITLE, FieldName::new("created"), OrderDirection::Desc),
    OrderTerm::new(ID, FieldName::new("id"), OrderDirection::Asc),
  ];

  assert_eq!(crossed[0].column(), postgres_order()[0].column());
  assert_ne!(
    OrderSignature::of(&crossed),
    OrderSignature::of(&postgres_order())
  );
}

/// A direction is half of a term, so reversing one is a different order — which is what makes a
/// cursor minted under `ASC` refuse a `DESC` replay rather than paging backwards through it.
#[test]
fn a_direction_is_part_of_the_signature() {
  let ascending = [OrderTerm::new(
    CREATED,
    FieldName::new("created_at"),
    OrderDirection::Asc,
  )];
  let descending = [OrderTerm::new(
    CREATED,
    FieldName::new("created_at"),
    OrderDirection::Desc,
  )];

  assert_ne!(
    OrderSignature::of(&ascending),
    OrderSignature::of(&descending)
  );
}

/// The SEQUENCE is part of it too: `ORDER BY a, b` is not `ORDER BY b, a`, and a cursor taken under
/// one pages the other wrongly.
#[test]
fn the_sequence_is_part_of_the_signature() {
  let title_first = [
    OrderTerm::new(TITLE, FieldName::new("title"), OrderDirection::Asc),
    OrderTerm::new(CREATED, FieldName::new("created_at"), OrderDirection::Asc),
  ];
  let created_first = [
    OrderTerm::new(CREATED, FieldName::new("created_at"), OrderDirection::Asc),
    OrderTerm::new(TITLE, FieldName::new("title"), OrderDirection::Asc),
  ];

  assert_ne!(
    OrderSignature::of(&title_first),
    OrderSignature::of(&created_first)
  );
}

/// Each identity is LENGTH-PREFIXED, so a sequence of them has exactly one reading — without which
/// `["ab", "c"]` and `["a", "bc"]` feed the hash the same bytes and two different orders share a
/// fingerprint for a reason that has nothing to do with the hash function.
#[test]
fn identities_are_length_prefixed_so_a_split_cannot_be_moved() {
  let split_early = [
    OrderTerm::new(
      TermName::new("ab"),
      FieldName::new("ab"),
      OrderDirection::Asc,
    ),
    OrderTerm::new(TermName::new("c"), FieldName::new("c"), OrderDirection::Asc),
  ];
  let split_late = [
    OrderTerm::new(TermName::new("a"), FieldName::new("a"), OrderDirection::Asc),
    OrderTerm::new(
      TermName::new("bc"),
      FieldName::new("bc"),
      OrderDirection::Asc,
    ),
  ];

  assert_ne!(
    OrderSignature::of(&split_early),
    OrderSignature::of(&split_late)
  );
}

/// NULLABILITY is deliberately not folded in: it is a schema fact rather than something a client
/// wrote, and a column that becomes nullable changes the ordering and the comparison TOGETHER — so
/// an outstanding cursor still resumes at the right row instead of being refused for a change it
/// was not affected by.
#[test]
fn nullability_is_not_part_of_the_signature() {
  let required = [OrderTerm::new(
    CREATED,
    FieldName::new("created_at"),
    OrderDirection::Asc,
  )];
  let optional = [OrderTerm::nullable(
    CREATED,
    FieldName::new("created_at"),
    OrderDirection::Asc,
  )];

  assert_eq!(OrderSignature::of(&required), OrderSignature::of(&optional));
}

/// The fingerprint is STABLE — a cursor outlives the process that minted it, so the function is
/// this crate's own rather than [`core::hash`]'s, whose `DefaultHasher` is explicitly not stable
/// across releases.
///
/// The numbers are what make the pin real: a changed hash, a changed framing or a changed byte
/// order reds this test rather than silently refusing every cursor a deployment had outstanding.
#[test]
fn the_fingerprint_is_a_fixed_number() {
  assert_eq!(OrderSignature::of(&[]).get(), 0xcbf2_9ce4_8422_2325);
  assert_eq!(
    OrderSignature::of(&sqlite_order()).get(),
    0xdb69_1f89_3575_9e1b
  );
}

/// Eight bytes, big-endian, and the width is CHECKED coming back — the round trip
/// [`BeU64`](crate::BeU64) holds itself to, since a cursor's frame carries these bytes verbatim.
#[test]
fn a_signature_round_trips_through_its_eight_bytes() {
  let signature = OrderSignature::of(&sqlite_order());

  assert_eq!(
    signature.to_blob(),
    signature.get().to_be_bytes(),
    "big-endian, as every durable number in this crate is"
  );
  assert_eq!(
    OrderSignature::from_blob(&signature.to_blob()),
    Some(signature)
  );
  assert_eq!(OrderSignature::from_blob(&[0; 7]), None);
  assert_eq!(OrderSignature::from_blob(&[0; 9]), None);
}

/// A forward walk runs a term as written; a backward walk runs it the other way. That is the whole
/// of what `last`/`before` do to an order — the re-reversal of the rows is the engine's.
#[test]
fn a_backward_walk_inverts_every_term() {
  assert_eq!(
    Walk::Forward.direction(OrderDirection::Asc),
    OrderDirection::Asc
  );
  assert_eq!(
    Walk::Forward.direction(OrderDirection::Desc),
    OrderDirection::Desc
  );
  assert_eq!(
    Walk::Backward.direction(OrderDirection::Asc),
    OrderDirection::Desc
  );
  assert_eq!(
    Walk::Backward.direction(OrderDirection::Desc),
    OrderDirection::Asc
  );
}

/// The inversion is an INVOLUTION, which is what makes a backward page of a backward page the
/// original order rather than a third one.
#[test]
fn walking_back_twice_is_walking_forward() {
  for written in [OrderDirection::Asc, OrderDirection::Desc] {
    assert_eq!(
      Walk::Backward.direction(Walk::Backward.direction(written)),
      written
    );
  }
}

/// A term holds two names of one column, and each accessor answers with its own — the type's own
/// doctest pair is where the SWAP is refused, since a `compile_fail` block inside a `cfg(test)`
/// module is a block rustdoc never collects.
#[test]
fn a_term_keeps_its_two_names_apart() {
  let term = OrderTerm::new(CREATED, FieldName::new("created"), OrderDirection::Desc);

  assert_eq!(term.identity(), CREATED);
  assert_eq!(term.column(), FieldName::new("created"));
  assert_eq!(term.direction(), OrderDirection::Desc);
  assert!(!term.is_nullable());
}

/// The nullable constructor differs in exactly one fact and carries the other three through.
#[test]
fn the_nullable_constructor_changes_nothing_but_nullability() {
  let required = OrderTerm::new(CREATED, FieldName::new("created"), OrderDirection::Desc);
  let optional = OrderTerm::nullable(CREATED, FieldName::new("created"), OrderDirection::Desc);

  assert!(optional.is_nullable());
  assert_eq!(optional.identity(), required.identity());
  assert_eq!(optional.column(), required.column());
  assert_eq!(optional.direction(), required.direction());
}

/// A synthetic citizen carrying ONE leaf of each word, so a level can be minted over each of the
/// three and the compose read off them side by side.
///
/// It is written here rather than borrowed from a shipped type because no shipped type has all
/// three: `MediaTimestamp` has the plain and the nullable, `BoundingBox` has the plain and the
/// derived, and the arm that matters is the one no citizen exercises today — a
/// [`ColumnShape::Derived`] leaf that IS an order level. The area sits in no level of a rectangle
/// (see `BoundingBox`'s own `ORDER`), so this pin is what holds the arm honest until one does.
const THREE_WORDS: &[ColumnShape] = &[
  ColumnShape::Plain(ColumnName::new("value")),
  ColumnShape::Nullable(ColumnName::new("partial")),
  ColumnShape::Derived(ColumnName::new("total")),
];

/// Every leaf of [`THREE_WORDS`] as its own level, in declaration order.
const THREE_LEVELS: &[OrderLevel] = &[OrderLevel::new(0), OrderLevel::new(1), OrderLevel::new(2)];

/// **A LEVEL'S NULLABILITY IS ITS OWN LEAF'S, AND A TOTAL INDEX IS NOT NULLABLE.**
///
/// The expansion asks `leaf_shape` for the level's own column and composes the answer with the
/// field's `optional` marker. Reading `self_nullable` there rather than `holds_value` is the whole
/// of the arm: a derived leaf serves the semantic order, so it is ASKED about — and what it answers
/// is whether that column can be `NULL`, not whether it is part of the value. The middle level takes
/// the `NULL`-partition arms and the outer two do not.
///
/// A level that read `holds_value` instead would put the `NULL` arms on BOTH derived levels and pay
/// for a partition an area column can never be in.
#[test]
fn a_derived_level_is_nullable_only_when_its_own_leaf_may_be() {
  let term = OrderTerm::spanning(
    CREATED,
    FieldName::new("span"),
    THREE_WORDS,
    THREE_LEVELS,
    OrderDirection::Asc,
  );

  assert_eq!(
    term
      .levels()
      .map(|level| level.is_nullable())
      .collect::<Vec<_>>(),
    [false, true, false],
    "plain: required · nullable leaf: nullable · derived-and-total: required"
  );
  assert_eq!(
    term.levels().map(|level| level.leaf()).collect::<Vec<_>>(),
    [Some(0), Some(1), Some(2)],
    "and each level is one column wide, which is what the compose is asked per"
  );
}

/// **THE FIELD'S OWN GRAIN STILL FANS**, and it fans over the total index with everything else.
///
/// The two grains compose at a level exactly as they compose at the DDL: a column admits `NULL`
/// when the FIELD is optional **or** when the LEAF says so. So an optional holder's derived level
/// is nullable — not because the arithmetic can decline, but because the whole value may be absent.
#[test]
fn an_optional_holder_makes_every_level_nullable_including_the_total_index() {
  let term = OrderTerm::spanning_nullable(
    CREATED,
    FieldName::new("span"),
    THREE_WORDS,
    THREE_LEVELS,
    OrderDirection::Asc,
  );

  assert_eq!(
    term
      .levels()
      .map(|level| level.is_nullable())
      .collect::<Vec<_>>(),
    [true, true, true],
    "the marker sits on the field, so it reaches every one of its columns"
  );
}