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 opaque spelling: base64url, no padding.
//!
//! # Why the crate writes it rather than taking one
//!
//! `store::fs` already writes RFC 4648 base32 for the same class of reason — a rendering the crate
//! must be able to state exactly, in both directions, and keep stating the same way for as long as
//! the values it renders are durable. A cursor outlives the process that minted it, so the encoder
//! and the decoder here are one authority and a dependency would be a second one under someone
//! else's release schedule. It is thirty lines.
//!
//! # Base64url and not base64, and no padding
//!
//! RFC 4648 §5's alphabet: `-` and `_` where §4 has `+` and `/`, so a cursor is a URL query
//! parameter, a JSON string and a header value with nothing to escape at any of them. `=` padding
//! is not written — a cursor's length is carried by the string itself — and it is REFUSED coming
//! back rather than tolerated, for the reason the base32 renderer states about its own prefix: two
//! spellings of one cursor is one spelling too many.
//!
//! # This is not the NO-JSON law's exception
//!
//! The law is about the CHANNEL a typed value travels: elements ride typed columns or typed rows,
//! never a JSON text encoding. Base64url is a transfer encoding over the framework's own frame —
//! it re-spells bytes and reads nothing inside them — where a JSON cursor would be a second
//! schema, a second parser and a second set of type coercions between the values and the columns
//! they are compared against.

/// The RFC 4648 §5 alphabet.
const BASE64URL: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_";

/// `bytes` as base64url with no padding.
pub(crate) fn encode(bytes: &[u8]) -> String {
  // Four symbols per three bytes, and the remainder's own two or three.
  let mut out = String::with_capacity(bytes.len().div_ceil(3) * 4);
  for chunk in bytes.chunks(3) {
    // Pack up to three bytes big-endian into 24 bits, then take six bits at a time. The output
    // length is ceil(bits / 6), which is what makes the encoding injective with no padding.
    let mut buf = [0u8; 3];
    buf[..chunk.len()].copy_from_slice(chunk);
    let packed = u32::from_be_bytes([0, buf[0], buf[1], buf[2]]);
    let symbols = chunk.len() * 8 / 6 + usize::from(chunk.len() * 8 % 6 != 0);
    for i in 0..symbols {
      let shift = 18 - i * 6;
      out.push(BASE64URL[((packed >> shift) & 0x3f) as usize] as char);
    }
  }
  out
}

/// The bytes `text` spells, or [`None`] where it is not this alphabet, this padding and this
/// grouping.
///
/// # Three refusals, and the third is the one a lenient decoder gets wrong
///
/// A symbol outside the alphabet — `=` included, so padding is refused rather than skipped. A final
/// group of ONE symbol, which no encoding of any byte string produces: six bits is not a byte, and
/// a decoder that dropped them would accept two spellings of the same cursor. And any group whose
/// unused low bits are not zero, for the same reason — `QQ` and `QR` would otherwise both decode to
/// `A`.
pub(crate) fn decode(text: &str) -> Option<Vec<u8>> {
  let symbols = text.as_bytes();
  let mut out = Vec::with_capacity(symbols.len() / 4 * 3);
  for group in symbols.chunks(4) {
    // A trailing group of one symbol carries six bits, which is not a byte. Every other length is
    // a whole number of bytes plus the leftover bits checked below.
    if group.len() == 1 {
      return None;
    }
    let mut packed = 0u32;
    for symbol in group {
      packed = (packed << 6) | u32::from(value_of(*symbol)?);
    }
    let bytes = group.len() * 6 / 8;
    // The bits the group carries beyond whole bytes belong to no byte, so they must be zero — the
    // encoder writes them zero, and any other value is a second spelling of this same output.
    let spare = group.len() * 6 - bytes * 8;
    if packed & ((1 << spare) - 1) != 0 {
      return None;
    }
    let packed = packed << (24 - group.len() * 6);
    out.extend_from_slice(&packed.to_be_bytes()[1..=bytes]);
  }
  Some(out)
}

/// The six bits `symbol` stands for, or [`None`] where it is not in the alphabet.
///
/// A linear scan of 64 bytes rather than a table: a cursor is decoded once per request and the
/// table would be a second statement of the alphabet, which is the thing that has to be right.
#[inline]
fn value_of(symbol: u8) -> Option<u8> {
  BASE64URL
    .iter()
    .position(|candidate| *candidate == symbol)
    .map(|index| index as u8)
}

#[cfg(test)]
mod tests;