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-PRESERVING form a collection is mirrored into — the bytes a `sortable` collection's
//! companion column holds, and the trait one element type joins that form by.
//!
//! # What it is for
//!
//! A collection kept in a table of its own has no column on the row being ordered, so
//! [`Unpushable::CollectionTable`](crate::query::Unpushable::CollectionTable) refuses every term
//! over one and the order is completed in memory or the page is refused. The `sortable` word buys
//! the missing column back: the row carries ONE opaque blob per sortable collection, holding the
//! whole collection in a form whose BYTEWISE order is the framework's own collection order —
//! [`compare_collections`](crate::query::compare_collections), element by element with
//! shorter-is-less on a prefix.
//!
//! That is the whole mechanism. The statement orders by an ordinary binary column, the engine
//! indexes it like any other, and nothing about the ordering asks the edge table a question.
//!
//! # The FRAME, and why it is two bytes rather than none
//!
//! ```text
//! []          00
//! [a]         01 <a> 00
//! [a, b]      01 <a> 01 <b> 00
//! ```
//!
//! `0x01` before each element and `0x00` after the last. Every rule of the pin falls out of
//! `0x00 < 0x01` alone:
//!
//! - the EMPTY collection is one byte and every other starts with `0x01`, so it is least;
//! - a PREFIX ends where the longer one continues, and there the shorter has `0x00` against `0x01`;
//! - the FIRST DIFFERING ELEMENT decides, because the elements before it wrote identical bytes at
//!   identical offsets.
//!
//! The offsets stay aligned because [`SortKey`] is PREFIX-FREE — see its contract. Without that the
//! marker bytes would not save the frame: one element's bytes running into the next element's
//! marker is exactly the ambiguity a length-free concatenation has.
//!
//! # It is ONE encoding, and the element half is the house's existing one
//!
//! [`BeU64::to_blob`](crate::BeU64::to_blob) and its two siblings are what the wide-integer storage
//! forms already store, and their rows here CALL those methods rather than writing the bytes again —
//! the discipline `storage`'s own note states, one type promising one thing. What is new is the
//! FRAME above and the escape a variable-width element needs, neither of which any type in this
//! crate had a form for.
//!
//! # Floats have no row, and the absence is the refusal
//!
//! [`compare_collections`](crate::query::compare_collections) demands `Ord` of its elements, which
//! `f32` and `f64` do not implement: there is no pin for a collection of them to agree with, so
//! there is nothing here for one to be encoded into. A `sortable` collection of floats is therefore
//! `E0277` naming [`SortKey`] at the declaration rather than a silent second opinion about `NaN`.
//!
//! # A downstream element joins by writing ONE impl
//!
//! The trait is open for the reason
//! [`PgCollectionStorage`](crate::comparison::sql::PgCollectionStorage) is: what an element type is
//! is the declaring crate's, and a closed list would be a framework deciding which types may be
//! collected. The rows below are the ones this crate ships a collection codec for already.

/// The ORDER-PRESERVING bytes one value of a collection element contributes.
///
/// # The contract is TWO promises, and both are load-bearing
///
/// For any two values `a` and `b` of the implementing type:
///
/// 1. **order-preserving** — comparing the written bytes bytewise gives the same answer as
///    `a.cmp(&b)`. This is what makes a database's ordering over the companion column the
///    framework's ordering over the collection;
/// 2. **prefix-free** — neither value's bytes are a PROPER PREFIX of the other's. This is what keeps
///    the frame's element offsets aligned, and it is the promise a reader is most likely to
///    overlook.
///
/// A FIXED-WIDTH encoding satisfies the second by construction, which is why every integer row below
/// simply writes its big-endian bytes. A VARIABLE-WIDTH one satisfies it with a terminator its own
/// body cannot contain, which is what [`push_escaped`] is.
///
/// Nothing here decodes. The companion column is written and ordered by and never read back into a
/// value — the collection itself is what the edge table holds — so a one-way form is the whole of
/// what this needs, and the round trip [`BeU64::from_blob`](crate::BeU64::from_blob) offers is
/// deliberately not restated.
///
/// # Examples
///
/// The whole of what a downstream element type writes:
///
/// ```
/// use ingraph::SortKey;
///
/// /// A tag, ordered by its text.
/// #[derive(PartialEq, Eq, PartialOrd, Ord)]
/// pub struct Tag(String);
///
/// impl SortKey for Tag {
///   fn write_sort_key(&self, out: &mut Vec<u8>) {
///     self.0.write_sort_key(out);
///   }
/// }
///
/// let mut bytes = Vec::new();
/// Tag("a".to_owned()).write_sort_key(&mut bytes);
/// assert_eq!(bytes, [b'a', 0x00, 0x01]);
/// ```
pub trait SortKey {
  /// Append this value's order-preserving, prefix-free bytes to `out`.
  fn write_sort_key(&self, out: &mut Vec<u8>);
}

/// The byte a frame writes BEFORE each element.
///
/// It is above [`END`] and that is the entire prefix rule: where one collection has run out and
/// another has not, the shorter is at its terminator and the longer at this.
const ITEM: u8 = 0x01;

/// The byte a frame writes after the last element.
const END: u8 = 0x00;

/// The byte a variable-width element's escape doubles up on — the one byte its body may not contain
/// unescaped, so that the terminator is unambiguous.
const ESCAPE: u8 = 0x00;

/// What an escaped `0x00` is followed by. Above [`TERMINATOR`], so a body byte of `0x00` sorts ABOVE
/// the end of a shorter body — which is what makes a prefix least.
const ESCAPED: u8 = 0xFF;

/// What the terminating `0x00` is followed by.
const TERMINATOR: u8 = 0x01;

/// `elements`' order-preserving bytes — the value a `sortable` collection's companion column holds.
///
/// **This is the read of [`compare_collections`](crate::query::compare_collections) that a database
/// can perform.** Comparing two of these bytewise answers exactly as comparing the two collections
/// element by element does, so a `BLOB`/`bytea` column holding them orders the rows the way the
/// framework means.
///
/// It takes an ITERATOR for [`compare_collections`](crate::query::compare_collections)'s own reason:
/// a row holds a `Vec`, a write lane may hold a slice, and the pin is stated over what both are.
///
/// # Examples
///
/// The three rules of the pin, read off the bytes:
///
/// ```
/// use core::cmp::Ordering;
///
/// use ingraph::{collection_sort_key, query::compare_collections};
///
/// let empty = collection_sort_key::<[i32; 0]>([]);
/// let one = collection_sort_key([1i32]);
/// let two = collection_sort_key([1i32, 2]);
/// let other = collection_sort_key([2i32]);
///
/// // the empty collection is least
/// assert_eq!(empty.cmp(&one), Ordering::Less);
/// // a prefix is below what extends it
/// assert_eq!(one.cmp(&two), Ordering::Less);
/// // and the first differing element decides, whatever the lengths are
/// assert_eq!(other.cmp(&two), Ordering::Greater);
///
/// // which is the pin, on the same four collections
/// assert_eq!(compare_collections::<[i32; 0], _>([], [1]), Ordering::Less);
/// assert_eq!(compare_collections([1, 2], [1, 2, 3]), Ordering::Less);
/// assert_eq!(compare_collections([2], [1, 9]), Ordering::Greater);
/// ```
pub fn collection_sort_key<C>(elements: C) -> Vec<u8>
where
  C: IntoIterator,
  C::Item: SortKey,
{
  let mut out = Vec::new();
  push_collection_sort_key(elements, &mut out);
  out
}

/// [`collection_sort_key`], appending to a buffer a caller already holds.
///
/// The form a WRITE lane spends, which encodes one collection per sortable column of a row and has
/// no reason to allocate a `Vec` apiece.
pub fn push_collection_sort_key<C>(elements: C, out: &mut Vec<u8>)
where
  C: IntoIterator,
  C::Item: SortKey,
{
  for element in elements {
    out.push(ITEM);
    element.write_sort_key(out);
  }
  out.push(END);
}

/// Append `bytes` in the ESCAPED form a variable-width element takes: every `0x00` doubled up with
/// `0xFF`, and a `0x00 0x01` terminator no body can spell.
///
/// # Why the pair, rather than a length prefix
///
/// A length prefix is not order-preserving: `"b"` is one byte and `"ab"` is two, so a leading length
/// would put the SHORTER first whatever the content, where the pin puts `"ab"` below `"b"`. The
/// escape has no such leading field — the bytes compare directly — and the terminator is what tells
/// a prefix from a continuation, at the one position where they differ.
///
/// # Both promises, checked
///
/// **Order-preserving.** Where two bodies differ at a byte, the escaped forms differ at the
/// corresponding position with the same relation: an escape ADDS a byte after a `0x00`, and it does
/// so in both forms at every `0x00` they share. Where one body is a prefix of the other, the shorter
/// reaches its terminator's `0x00`; the longer is at its next body byte, which is either above
/// `0x00` or is itself a `0x00` followed by [`ESCAPED`] where the terminator has [`TERMINATOR`], and
/// `0x01 < 0xFF`.
///
/// **Prefix-free.** Inside a body every `0x00` is followed by `0xFF`, and the terminator's is
/// followed by `0x01`, so no encoded value can continue past another's terminator.
pub fn push_escaped(bytes: &[u8], out: &mut Vec<u8>) {
  for &byte in bytes {
    out.push(byte);
    if byte == ESCAPE {
      out.push(ESCAPED);
    }
  }
  out.push(ESCAPE);
  out.push(TERMINATOR);
}

/// A BORROW of an element is that element, which is what lets one signature take a collection of
/// values and a collection of references both.
///
/// A row holds a `Vec<String>` and hands out `&String`s where a write lane may hold a `&[String]`
/// and hand out `&String`s too, so [`collection_sort_key`]'s bound is stated over the ITEM and this
/// is what makes the two spellings satisfy it. `?Sized` because [`str`] and `[u8]` are where the
/// borrow is the only form there is.
impl<T: SortKey + ?Sized> SortKey for &T {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    (**self).write_sort_key(out);
  }
}

/// A boolean is one byte, and `false < true` is what `0 < 1` already says.
impl SortKey for bool {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    out.push(u8::from(*self));
  }
}

/// The UNSIGNED integers, at their own widths: equal-length big-endian blobs compare bytewise
/// exactly as the numbers do, which is the fact
/// [`storage`](crate::BeU64)'s own note states and the reason those carriers exist.
macro_rules! unsigned_sort_keys {
  ($($ty:ty),+ $(,)?) => {
    $(
      impl SortKey for $ty {
        #[inline]
        fn write_sort_key(&self, out: &mut Vec<u8>) {
          out.extend_from_slice(&self.to_be_bytes());
        }
      }
    )+
  };
}

unsigned_sort_keys!(u8, u16, u32, u64, u128);

/// The SIGNED integers, offset by a SIGN-BIT FLIP so the negative range sorts below the positive
/// one.
///
/// Without it `-1` encodes as `ff…ff` and would sort above every positive value — the same
/// correction [`BeI128::to_blob`](crate::BeI128::to_blob) makes, in the same direction, and it is
/// here rather than borrowed from there because that type is `i128`'s alone.
macro_rules! signed_sort_keys {
  ($($ty:ty => $unsigned:ty),+ $(,)?) => {
    $(
      impl SortKey for $ty {
        #[inline]
        fn write_sort_key(&self, out: &mut Vec<u8>) {
          let offset = (*self as $unsigned) ^ (1 << (<$unsigned>::BITS - 1));
          out.extend_from_slice(&offset.to_be_bytes());
        }
      }
    )+
  };
}

signed_sort_keys!(i8 => u8, i16 => u16, i32 => u32, i64 => u64, i128 => u128);

/// The three WIDE-INTEGER storage forms, through the codec each already owns.
///
/// `to_blob` rather than a second encoding: `BeU64` promises the order-preserving eight-byte
/// big-endian blob and `BeI128` promises the sign-flipped sixteen, and two parties writing those
/// bytes would be two encodings that agree today and are free to stop. This is the same call the
/// carrier rows make.
macro_rules! blob_sort_keys {
  ($($ty:ty),+ $(,)?) => {
    $(
      impl SortKey for $ty {
        #[inline]
        fn write_sort_key(&self, out: &mut Vec<u8>) {
          out.extend_from_slice(&self.to_blob());
        }
      }
    )+
  };
}

blob_sort_keys!(crate::BeU64, crate::BeU128, crate::BeI128);

/// Text, as its UTF-8 BYTES — which is what [`Ord`] for [`str`] already compares, so the encoding
/// states no second opinion about characters.
///
/// **A database COLLATION is a different question and this is not it.** The companion column is
/// binary on every dialect, so its ordering is byte order wherever it is stored — where a native
/// array of text is ordered by the column's collation. The two agree under a byte-order collation
/// and differ under any other, which is the ELEMENT-level inheritance
/// [`query::order`](crate::query)'s own note already records for the array path.
impl SortKey for str {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    push_escaped(self.as_bytes(), out);
  }
}

impl SortKey for String {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    self.as_str().write_sort_key(out);
  }
}

/// A byte string, as itself.
impl SortKey for [u8] {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    push_escaped(self, out);
  }
}

impl SortKey for Vec<u8> {
  #[inline]
  fn write_sort_key(&self, out: &mut Vec<u8>) {
    self.as_slice().write_sort_key(out);
  }
}

#[cfg(test)]
mod tests;