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 ORDER-PRESERVATION proofs — one per shipped element row, and one for the frame that carries
//! them.
//!
//! Every assertion here is the same shape and it is the only shape that proves anything about this
//! module: take values whose [`Ord`] order is known, encode them, and hold the BYTES' order against
//! the values'. A test that only checked a byte pattern would pass for an encoding that is stable
//! and wrong.
//!
//! The collection half holds the frame against
//! [`compare_collections`](crate::query::compare_collections) rather than against a hand-written
//! expectation, so the pin and its byte form cannot drift apart: change one and this reddens.

use core::cmp::Ordering;

use super::{SortKey, collection_sort_key, push_escaped};
use crate::{BeI128, BeU64, BeU128, query::compare_collections};

/// One value's bytes.
fn key<T: SortKey + ?Sized>(value: &T) -> Vec<u8> {
  let mut out = Vec::new();
  value.write_sort_key(&mut out);
  out
}

/// **The element contract, checked over every pair of an ASCENDING corpus.** Both promises at once:
/// the bytes rank as the values do, and no value's bytes are a proper prefix of another's.
fn element_contract<T: SortKey + Ord>(ascending: &[T]) {
  for (at, left) in ascending.iter().enumerate() {
    for (beyond, right) in ascending.iter().enumerate() {
      let (encoded_left, encoded_right) = (key(left), key(right));
      assert_eq!(
        encoded_left.cmp(&encoded_right),
        at.cmp(&beyond),
        "the bytes of element {at} and element {beyond} do not rank as the values do"
      );
      if at != beyond {
        assert!(
          !encoded_left.starts_with(&encoded_right) && !encoded_right.starts_with(&encoded_left),
          "element {at} and element {beyond} encode to a prefix pair, which the frame cannot carry"
        );
      }
    }
  }
}

/// **`false` sorts below `true`**, which is the whole of one byte.
#[test]
fn a_boolean_orders_as_its_two_values_do() {
  element_contract(&[false, true]);
}

/// **The unsigned integers rank bytewise at every width**, including the two boundary values a
/// big-endian blob is most likely to get wrong.
#[test]
fn an_unsigned_integer_orders_as_a_number() {
  element_contract(&[0u8, 1, 127, 128, 254, 255]);
  element_contract(&[0u16, 1, 255, 256, u16::MAX]);
  element_contract(&[0u32, 1, 255, 256, 65535, 65536, u32::MAX]);
  element_contract(&[0u64, 1, 255, 256, u64::from(u32::MAX), u64::MAX]);
  element_contract(&[0u128, 1, u128::from(u64::MAX), u128::MAX]);
}

/// **The signed integers cross ZERO in the right direction**, which is what the sign-bit flip buys
/// and the one thing a plain big-endian encoding gets wrong: without it `-1` is `ff…ff` and outranks
/// every positive value.
#[test]
fn a_signed_integer_orders_across_zero() {
  element_contract(&[i8::MIN, -1, 0, 1, i8::MAX]);
  element_contract(&[i16::MIN, -256, -1, 0, 1, 256, i16::MAX]);
  element_contract(&[i32::MIN, -1, 0, 1, i32::MAX]);
  element_contract(&[i64::MIN, -1, 0, 1, i64::MAX]);
  element_contract(&[i128::MIN, -1, 0, 1, i128::MAX]);
}

/// **The flip is what does it**, stated as the mutation rather than inferred from the row above: the
/// unsigned reading of `-1` is the largest value of its width, so an encoding that skipped the flip
/// would put `-1` last.
#[test]
fn the_sign_flip_is_load_bearing() {
  assert_eq!(key(&-1i32).cmp(&key(&0i32)), Ordering::Less);
  assert_eq!(
    (-1i32 as u32).to_be_bytes().cmp(&0u32.to_be_bytes()),
    Ordering::Greater,
    "the unflipped reading is what this row exists to correct"
  );
}

/// **The three wide-integer storage forms encode as their own `to_blob`** — the house's codec, not a
/// second one written here.
#[test]
fn a_storage_form_spends_the_codec_it_already_owns() {
  assert_eq!(key(&BeU64(7)), BeU64(7).to_blob());
  assert_eq!(key(&BeU128(7)), BeU128(7).to_blob());
  assert_eq!(key(&BeI128(-7)), BeI128(-7).to_blob());

  element_contract(&[BeU64(0), BeU64(1), BeU64(u64::MAX)]);
  element_contract(&[BeU128(0), BeU128(1), BeU128(u128::MAX)]);
  element_contract(&[BeI128(i128::MIN), BeI128(-1), BeI128(0), BeI128(i128::MAX)]);
}

/// **Text orders as its BYTES do**, including the prefix pair a terminator-free concatenation gets
/// wrong.
#[test]
fn text_orders_as_its_bytes_do() {
  element_contract(&[
    String::new(),
    "B".to_owned(),
    "a".to_owned(),
    "ab".to_owned(),
    "b".to_owned(),
  ]);
}

/// **A byte string orders as itself**, over a corpus whose bodies contain the one byte the escape is
/// about.
#[test]
fn a_byte_string_orders_as_itself() {
  element_contract(&[
    Vec::new(),
    vec![0u8],
    vec![0u8, 0],
    vec![0u8, 1],
    vec![1u8],
    vec![1u8, 0],
    vec![255u8],
  ]);
}

/// **The escape's own two promises**, read off the bytes: a body `0x00` is doubled and the
/// terminator is not, so nothing inside a body can be mistaken for the end of one.
#[test]
fn the_escape_keeps_the_terminator_unambiguous() {
  assert_eq!(
    {
      let mut out = Vec::new();
      push_escaped(&[0x00], &mut out);
      out
    },
    [0x00, 0xFF, 0x00, 0x01]
  );
  assert_eq!(
    {
      let mut out = Vec::new();
      push_escaped(&[], &mut out);
      out
    },
    [0x00, 0x01]
  );
}

/// **A borrowed element encodes as the value does**, which is what lets one signature take a
/// collection of values and a collection of references.
#[test]
fn a_borrow_encodes_as_the_value() {
  assert_eq!(key(&&7u32), key(&7u32));
  assert_eq!(key("ab"), key(&"ab".to_owned()));
}

/// **THE PIN, IN BYTES.** For every pair of a corpus, the encoded collections rank exactly as
/// [`compare_collections`](crate::query::compare_collections) ranks them — which is what makes a
/// database's ordering over the companion column the framework's ordering over the collection.
///
/// The corpus is the PostgreSQL walk's own, recorded at
/// [`query::order`](crate::query::compare_collections): the empty array least, a prefix below what
/// extends it, and the first differing element deciding. `{10}` after `{2}` is the assertion that
/// separates ELEMENT order from stored-text order — a JSON or textual encoding puts `["10"]` below
/// `["9"]`.
fn collection_parity<T: SortKey + Ord + Clone>(corpus: &[Vec<T>]) {
  for left in corpus {
    for right in corpus {
      assert_eq!(
        collection_sort_key(left).cmp(&collection_sort_key(right)),
        compare_collections(left, right),
        "the encoded order and the pin disagree"
      );
    }
  }
}

/// The integer walk, which is where the stored-text reading is caught.
#[test]
fn an_integer_collection_encodes_the_pin() {
  collection_parity(&[
    Vec::<i64>::new(),
    vec![1],
    vec![1, 2],
    vec![1, 2, 3],
    vec![2],
    vec![9],
    vec![10],
    vec![-1],
    vec![-1, 0],
  ]);
}

/// The text walk, on the corpus whose collation and byte order disagree.
#[test]
fn a_text_collection_encodes_the_pin() {
  let word = |text: &str| vec![text.to_owned()];
  collection_parity(&[
    Vec::new(),
    word("B"),
    word("a"),
    vec!["a".to_owned(), "a".to_owned(), "a".to_owned()],
    vec!["a".to_owned(), "b".to_owned()],
    word("b"),
  ]);
}

/// The byte-string walk, whose elements carry the escape's own subject.
#[test]
fn a_byte_collection_encodes_the_pin() {
  collection_parity(&[
    Vec::new(),
    vec![vec![0u8]],
    vec![vec![0u8], vec![]],
    vec![vec![0u8, 0]],
    vec![vec![1u8]],
  ]);
}

/// **The three rules, spelled rather than swept up in the parity walk** — so a reader can see which
/// byte does which.
#[test]
fn the_frame_states_the_three_rules() {
  assert_eq!(collection_sort_key::<[i32; 0]>([]), [0x00]);
  assert_eq!(
    collection_sort_key([1u8]).cmp(&collection_sort_key([1u8, 2])),
    Ordering::Less,
    "a prefix is below what extends it"
  );
  assert_eq!(
    collection_sort_key::<[u8; 0]>([]).cmp(&collection_sort_key([0u8])),
    Ordering::Less,
    "the empty collection is least, even against an element whose own bytes are zero"
  );
  assert_eq!(
    collection_sort_key([2u8]).cmp(&collection_sort_key([1u8, 9])),
    Ordering::Greater,
    "the first differing element decides, whatever the lengths are"
  );
}

/// **An owned collection and a borrowed one encode alike**, which is what the write lane spends: a
/// row holds the `Vec` and hands out references.
#[test]
fn the_two_spellings_of_one_collection_agree() {
  let held = vec![1u32, 2, 3];
  assert_eq!(collection_sort_key(&held), collection_sort_key(held.iter()));
  assert_eq!(
    collection_sort_key(&held),
    collection_sort_key(held.clone())
  );
}