~ knotless Search/
↑↓ move↵ open⇧↵ all results
0
0
671 lines · 22.2 KB Raw History
//! The commits the parts write: of random bytes, as the write part's first
//! tables and the first replay table have them, and realistic ones, the same
//! for the same seed, wherever what the bytes are matters (sizes,
//! compression, reads). And an account's state after so many of the
//! realistic ones: its records and the tree over them.
//!
//! A realistic commit is a post of about 300 bytes of DAG-CBOR (a `$type`,
//! a text of common words, `langs`, a `createdAt`, and three times in ten a
//! reply's two CIDs and URIs), two MST nodes of about 1 KB (entries of a
//! key with its prefix shared, a CID, and sometimes a subtree's), a commit
//! block of about 190 bytes (a DID, a rev, the tree's CID, a signature of
//! 64 random bytes) and its event's frame, about 3 KB: a `#commit` with
//! those blocks again in a CAR, and the DID, rev and path as strings.
//! Every CID is the four bytes a CID of a DAG-CBOR block begins with and
//! 32 random ones.

use crate::util::Rng;
use std::sync::LazyLock;

/// The seed of every realistic commit the script writes.
pub const SEED: u64 = 1;

/// A createRecord's blocks, in bytes, as the random commits have them: the
/// commit, the record, two MST nodes; and its event's frame.
const BLOCKS: [usize; 4] = [180, 100, 1000, 1000];
const EVENT: usize = 2500;

/// `n` bytes that do not compress, the same for the same seed.
fn bytes(n: usize, seed: u64) -> Vec<u8> {
    let mut x = seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1;
    (0..n)
        .map(|_| {
            x ^= x << 13;
            x ^= x >> 7;
            x ^= x << 17;
            x as u8
        })
        .collect()
}

/// One commit: its rev, its record's path, its blocks by CID (the commit's,
/// the record's, then the MST nodes), and its event's frame.
pub struct Commit {
    pub op: u64,
    pub rev: String,
    pub path: String,
    pub blocks: Vec<(Vec<u8>, Vec<u8>)>,
    pub event: Vec<u8>,
}

/// A commit of random bytes.
pub fn random(op: u64) -> Commit {
    let rev = format!("3l{op:011}");
    Commit {
        op,
        path: format!("{COLLECTION}/{rev}"),
        rev,
        blocks: BLOCKS
            .iter()
            .enumerate()
            .map(|(i, &n)| {
                (
                    bytes(36, op * 8 + i as u64 + 1),
                    bytes(n, op * 8 + i as u64 + 5),
                )
            })
            .collect(),
        event: bytes(EVENT, op * 8 + 7),
    }
}

/// The MST nodes a commit made, which the account's next takes out.
pub fn nodes(c: &Commit) -> Vec<Vec<u8>> {
    c.blocks[2..].iter().map(|(cid, _)| cid.clone()).collect()
}

// ---- Realistic commits ----------------------------------------------------

const COLLECTION: &str = "app.bsky.feed.post";

/// When the first commit is made, in microseconds since the epoch, how long
/// after it each next one is, and a day.
const BASE: u64 = 1_700_000_000_000_000;
const STEP: u64 = 250_000;
const DAY: u64 = 86_400_000_000;

const WORDS: &str = "the be to of and a in that have I it for not on with he as you do at \
this but his by from they we say her she or an will my one all would there their what so up \
out if about who get which go me when make can like time no just him know take people into \
year your good some could them see other than then now look only come its over think also \
back after use two how our work first well way even new want because any these give day most \
us is was are been has had were said did get may made find long down day did come part over \
new sound take only little work know place year live me back give most very after thing our \
just name good sentence man think say great where help through much before line right too \
mean old any same tell boy follow came want show also around form three small set put end \
does another well large must big even such because turn here why ask went men read need land \
different home move try kind hand picture again change off play spell air away animal house \
point page letter mother answer found study still learn should world high every near add \
food between own below country plant last school father keep tree never start city earth eye \
light thought head under story saw left few while along might close something seem next hard \
open example begin life always those both paper together got group often run important until \
children side feet car mile night walk white sea began grow took river four carry state once \
book hear stop without second later miss idea enough eat face watch far real almost let above \
girl sometimes mountain cut young talk soon list song being leave family morning today \
really love coffee weather music game friend happy week tonight thanks maybe actually";

static LIST: LazyLock<Vec<&'static str>> =
    LazyLock::new(|| WORDS.split_ascii_whitespace().collect());

const B32: &[u8; 32] = b"234567abcdefghijklmnopqrstuvwxyz";

/// A TID: 13 characters that sort as their time does.
fn tid(micros: u64, clock: u64) -> String {
    let v = (micros << 10) | (clock & 0x3ff);
    (0..13)
        .map(|i| B32[((v >> (60 - 5 * i)) & 31) as usize] as char)
        .collect()
}

/// An account's DID.
pub fn did(seed: u64, account: u64) -> String {
    let mut r = Rng::of(&[seed, 3, account]);
    let mut s = String::from("did:plc:");
    s.extend((0..24).map(|_| B32[r.below(32) as usize] as char));
    s
}

/// A CID of a DAG-CBOR block: 36 bytes.
fn cid(r: &mut Rng) -> Vec<u8> {
    let mut out = vec![0x01, 0x71, 0x12, 0x20];
    r.fill(&mut out, 32);
    out
}

/// A time as a record's `createdAt` has it.
fn iso(micros: u64) -> String {
    let (secs, millis) = (micros / 1_000_000, micros / 1000 % 1000);
    let (days, rem) = (secs / 86400, secs % 86400);
    // The civil date of a day since the epoch (Howard Hinnant's).
    let z = days + 719_468;
    let (era, doe) = (z / 146_097, z % 146_097);
    let yoe = (doe - doe / 1460 + doe / 36524 - doe / 146_096) / 365;
    let doy = doe - (365 * yoe + yoe / 4 - yoe / 100);
    let mp = (5 * doy + 2) / 153;
    let (d, m) = (doy - (153 * mp + 2) / 5 + 1, (mp + 2) % 12 + 1);
    let y = yoe + era * 400 + u64::from(m <= 2);
    format!(
        "{y:04}-{m:02}-{d:02}T{:02}:{:02}:{:02}.{millis:03}Z",
        rem / 3600,
        rem / 60 % 60,
        rem % 60
    )
}

// DAG-CBOR, as much of it as these blocks need.

fn head(out: &mut Vec<u8>, major: u8, n: u64) {
    let m = major << 5;
    match n {
        0..=23 => out.push(m | n as u8),
        24..=0xff => out.extend_from_slice(&[m | 24, n as u8]),
        0x100..=0xffff => {
            out.push(m | 25);
            out.extend_from_slice(&(n as u16).to_be_bytes());
        }
        0x1_0000..=0xffff_ffff => {
            out.push(m | 26);
            out.extend_from_slice(&(n as u32).to_be_bytes());
        }
        _ => {
            out.push(m | 27);
            out.extend_from_slice(&n.to_be_bytes());
        }
    }
}

fn text(out: &mut Vec<u8>, s: &str) {
    head(out, 3, s.len() as u64);
    out.extend_from_slice(s.as_bytes());
}

fn blob(out: &mut Vec<u8>, b: &[u8]) {
    head(out, 2, b.len() as u64);
    out.extend_from_slice(b);
}

/// A link to a block: tag 42 over its CID.
fn link(out: &mut Vec<u8>, cid: &[u8]) {
    out.extend_from_slice(&[0xd8, 42]);
    head(out, 2, cid.len() as u64 + 1);
    out.push(0);
    out.extend_from_slice(cid);
}

const NULL: u8 = 0xf6;
const FALSE: u8 = 0xf4;

fn varint(out: &mut Vec<u8>, mut n: u64) {
    while n >= 0x80 {
        out.push(n as u8 | 0x80);
        n >>= 7;
    }
    out.push(n as u8);
}

/// When commit `op`, of `account`, is made.
fn micros(seed: u64, op: u64, account: u64) -> u64 {
    BASE + op * STEP + Rng::of(&[seed, 1, op, account]).below(STEP)
}

/// The path of the record commit `op`, of `account`, puts.
pub fn path(seed: u64, op: u64, account: u64) -> String {
    format!("{COLLECTION}/{}", tid(micros(seed, op, account), account))
}

/// A record: where it is, the rev of the commit that put it, its CID and
/// its bytes.
pub struct Record {
    pub path: String,
    pub rev: String,
    pub cid: Vec<u8>,
    pub bytes: Vec<u8>,
}

/// The record commit `op`, of `account`, puts; or, with `version` over 0,
/// what a later commit put in its place, at the same path.
pub fn record(seed: u64, op: u64, account: u64, version: u64) -> Record {
    let made = micros(seed, op, account);
    let at = made + version * DAY;
    let mut r = Rng::of(&[seed, 2, op, account, version]);
    let own = cid(&mut r);
    let mut out = Vec::with_capacity(640);
    let reply = r.below(10) < 3;
    head(&mut out, 5, 4 + u64::from(reply));
    text(&mut out, "text");
    let list = &*LIST;
    let n = list.len() as u64;
    let mut body = String::new();
    for i in 0..10 + r.below(46) {
        if i > 0 {
            body.push(' ');
        }
        // The first of the list more often than the last, as words go.
        body.push_str(list[(r.below(n) * r.below(n) / n) as usize]);
    }
    text(&mut out, &body);
    text(&mut out, "$type");
    text(&mut out, COLLECTION);
    text(&mut out, "langs");
    head(&mut out, 4, 1);
    text(&mut out, "en");
    if reply {
        text(&mut out, "reply");
        head(&mut out, 5, 2);
        let other = did(seed, r.below(1 << 20));
        for name in ["root", "parent"] {
            text(&mut out, name);
            head(&mut out, 5, 2);
            text(&mut out, "cid");
            let c = cid(&mut r);
            link(&mut out, &c);
            text(&mut out, "uri");
            let uri = format!("at://{other}/{COLLECTION}/{}", tid(at - r.below(DAY), 0));
            text(&mut out, &uri);
        }
    }
    text(&mut out, "createdAt");
    text(&mut out, &iso(at));
    Record {
        path: format!("{COLLECTION}/{}", tid(made, account)),
        rev: tid(at, account),
        cid: own,
        bytes: out,
    }
}

/// An entry of an MST node: a key, its record's CID, and the subtree after
/// it, if there is one.
struct Entry<'a> {
    key: &'a str,
    value: &'a [u8],
    tree: Option<&'a [u8]>,
}

/// An MST node: its left subtree, if any, and its entries, each key less
/// the prefix it shares with the one before.
fn node(left: Option<&[u8]>, entries: &[Entry]) -> Vec<u8> {
    let mut out = Vec::with_capacity(1280);
    head(&mut out, 5, 2);
    text(&mut out, "e");
    head(&mut out, 4, entries.len() as u64);
    let mut before = "";
    for e in entries {
        let shared = before
            .bytes()
            .zip(e.key.bytes())
            .take_while(|(a, b)| a == b)
            .count();
        head(&mut out, 5, 4);
        text(&mut out, "k");
        blob(&mut out, &e.key.as_bytes()[shared..]);
        text(&mut out, "p");
        head(&mut out, 0, shared as u64);
        text(&mut out, "t");
        match e.tree {
            Some(c) => link(&mut out, c),
            None => out.push(NULL),
        }
        text(&mut out, "v");
        link(&mut out, e.value);
        before = e.key;
    }
    text(&mut out, "l");
    match left {
        Some(c) => link(&mut out, c),
        None => out.push(NULL),
    }
    out
}

/// A node of a tree no one holds whole: entries of keys before `own`, each
/// with a subtree one time in `trees`, then `own`.
fn loose_node(r: &mut Rng, at: u64, clock: u64, own: (&str, &[u8]), trees: u64) -> Vec<u8> {
    let n = 10 + r.below(5) as usize;
    let mut times: Vec<u64> = (0..n).map(|_| r.below(4 * 3_600_000_000) + 1).collect();
    // Each key so long before the next.
    for i in (0..n - 1).rev() {
        times[i] += times[i + 1];
    }
    let keys: Vec<String> = times
        .iter()
        .map(|back| format!("{COLLECTION}/{}", tid(at - back, clock)))
        .collect();
    let cids: Vec<(Vec<u8>, Option<Vec<u8>>)> = (0..n)
        .map(|_| (cid(r), (r.below(trees) == 0).then(|| cid(r))))
        .collect();
    let mut entries: Vec<Entry> = keys
        .iter()
        .zip(&cids)
        .map(|(key, (value, tree))| Entry {
            key,
            value,
            tree: tree.as_deref(),
        })
        .collect();
    entries.push(Entry {
        key: own.0,
        value: own.1,
        tree: None,
    });
    let left = (r.below(2) == 0).then(|| cid(r));
    node(left.as_deref(), &entries)
}

/// A commit's block: what a signed commit holds.
fn commit_block(r: &mut Rng, did: &str, rev: &str, data: &[u8]) -> Vec<u8> {
    let mut out = Vec::with_capacity(200);
    head(&mut out, 5, 6);
    text(&mut out, "did");
    text(&mut out, did);
    text(&mut out, "rev");
    text(&mut out, rev);
    text(&mut out, "sig");
    head(&mut out, 2, 64);
    r.fill(&mut out, 64);
    text(&mut out, "data");
    link(&mut out, data);
    text(&mut out, "prev");
    out.push(NULL);
    text(&mut out, "version");
    head(&mut out, 0, 3);
    out
}

/// A commit's event as the firehose sends it: a `#commit` frame, its
/// blocks in a CAR.
fn event(c: &Commit, did: &str, since: &str, time: &str) -> Vec<u8> {
    let commit = &c.blocks[0].0;
    let mut car = Vec::with_capacity(3200);
    let mut header = Vec::with_capacity(64);
    head(&mut header, 5, 2);
    text(&mut header, "roots");
    head(&mut header, 4, 1);
    link(&mut header, commit);
    text(&mut header, "version");
    head(&mut header, 0, 1);
    varint(&mut car, header.len() as u64);
    car.extend_from_slice(&header);
    for (cid, block) in &c.blocks {
        varint(&mut car, (cid.len() + block.len()) as u64);
        car.extend_from_slice(cid);
        car.extend_from_slice(block);
    }
    let mut out = Vec::with_capacity(car.len() + 320);
    head(&mut out, 5, 2);
    text(&mut out, "t");
    text(&mut out, "#commit");
    text(&mut out, "op");
    head(&mut out, 0, 1);
    head(&mut out, 5, 11);
    text(&mut out, "ops");
    head(&mut out, 4, 1);
    head(&mut out, 5, 3);
    text(&mut out, "cid");
    link(&mut out, &c.blocks[1].0);
    text(&mut out, "path");
    text(&mut out, &c.path);
    text(&mut out, "action");
    text(&mut out, "create");
    text(&mut out, "rev");
    text(&mut out, &c.rev);
    text(&mut out, "seq");
    head(&mut out, 0, c.op);
    text(&mut out, "repo");
    text(&mut out, did);
    text(&mut out, "time");
    text(&mut out, time);
    text(&mut out, "blobs");
    head(&mut out, 4, 0);
    text(&mut out, "since");
    text(&mut out, since);
    text(&mut out, "blocks");
    blob(&mut out, &car);
    text(&mut out, "commit");
    link(&mut out, commit);
    text(&mut out, "rebase");
    out.push(FALSE);
    text(&mut out, "tooBig");
    out.push(FALSE);
    out
}

/// Realistic commit `op`, of `account`: the same for the same seed.
pub fn real(seed: u64, op: u64, account: u64) -> Commit {
    let rec = record(seed, op, account, 0);
    let at = micros(seed, op, account);
    let mut r = Rng::of(&[seed, 4, op, account]);
    let did = did(seed, account);
    let own = (rec.path.as_str(), rec.cid.as_slice());
    // The node the record is in, and one above it.
    let leaf = (cid(&mut r), loose_node(&mut r, at, account, own, 4));
    let above = (cid(&mut r), loose_node(&mut r, at, account, own, 2));
    let commit = (cid(&mut r), commit_block(&mut r, &did, &rec.rev, &above.0));
    let since = tid(at - r.below(DAY) - 1, account);
    let mut c = Commit {
        op,
        rev: rec.rev,
        path: rec.path,
        blocks: vec![commit, (rec.cid, rec.bytes), leaf, above],
        event: Vec::new(),
    };
    c.event = event(&c, &did, &since, &iso(at));
    c
}

// ---- An account's state ---------------------------------------------------

/// The entries of a node at the tree's foot, and of one above.
const LEAF: usize = 16;
const FAN: usize = 10;

/// A block of the tree: its CID, its bytes, and the rev of the commit that
/// put it there.
#[derive(Clone)]
pub struct Block {
    pub cid: Vec<u8>,
    pub bytes: Vec<u8>,
    pub rev: String,
}

/// What an account holds after its commits: its records in order of path,
/// and the tree over them, a node at the foot for each 16 records, one
/// above for each 10 of those, and the root.
pub struct State {
    seed: u64,
    account: u64,
    accounts: u64,
    pub records: Vec<Record>,
    leaves: Vec<Block>,
    above: Vec<Block>,
    root: Block,
}

impl State {
    /// The state of `account`, one of `accounts`, after `records` commits:
    /// its record `i` is commit `i * accounts + account + 1`'s, the
    /// accounts' commits taking turns.
    pub fn new(seed: u64, account: u64, accounts: u64, records: usize) -> State {
        let records: Vec<Record> = (0..records as u64)
            .map(|i| record(seed, i * accounts + account + 1, account, 0))
            .collect();
        let empty = Block {
            cid: Vec::new(),
            bytes: Vec::new(),
            rev: String::new(),
        };
        let mut s = State {
            seed,
            account,
            accounts,
            leaves: vec![empty.clone(); records.len().div_ceil(LEAF)],
            above: vec![empty.clone(); records.len().div_ceil(LEAF).div_ceil(FAN)],
            root: empty,
            records,
        };
        for i in 0..s.leaves.len() {
            s.leaf(i, 0);
        }
        for i in 0..s.above.len() {
            s.over(i, 0);
        }
        s.top(0);
        s
    }

    fn cid(&self, level: u64, i: usize, version: u64) -> Vec<u8> {
        cid(&mut Rng::of(&[
            self.seed,
            5,
            self.account,
            level,
            i as u64,
            version,
        ]))
    }

    /// The rev of the latest commit to a record among `records`.
    fn rev(records: &[Record]) -> String {
        records
            .iter()
            .map(|r| r.rev.as_str())
            .max()
            .unwrap_or_default()
            .to_string()
    }

    /// Make node `i` at the foot again, of the records it holds now.
    fn leaf(&mut self, i: usize, version: u64) {
        let mine = &self.records[i * LEAF..self.records.len().min((i + 1) * LEAF)];
        let entries: Vec<Entry> = mine
            .iter()
            .map(|r| Entry {
                key: &r.path,
                value: &r.cid,
                tree: None,
            })
            .collect();
        self.leaves[i] = Block {
            cid: self.cid(0, i, version),
            bytes: node(None, &entries),
            rev: State::rev(mine),
        };
    }

    /// Make node `i` above the foot again, of the nodes under it now.
    fn over(&mut self, i: usize, version: u64) {
        let under = i * FAN..self.leaves.len().min((i + 1) * FAN);
        let entries: Vec<Entry> = under
            .clone()
            .map(|l| Entry {
                key: &self.records[l * LEAF].path,
                value: &self.records[l * LEAF].cid,
                tree: Some(&self.leaves[l].cid),
            })
            .collect();
        self.above[i] = Block {
            cid: self.cid(1, i, version),
            bytes: node(None, &entries),
            rev: State::rev(
                &self.records[under.start * LEAF..self.records.len().min(under.end * LEAF)],
            ),
        };
    }

    /// Make the root again, of the nodes under it now.
    fn top(&mut self, version: u64) {
        let entries: Vec<Entry> = (0..self.above.len())
            .map(|a| Entry {
                key: &self.records[a * FAN * LEAF].path,
                value: &self.records[a * FAN * LEAF].cid,
                tree: Some(&self.above[a].cid),
            })
            .collect();
        self.root = Block {
            cid: self.cid(2, 0, version),
            bytes: node(None, &entries),
            rev: State::rev(&self.records),
        };
    }

    /// The tree's nodes.
    pub fn nodes(&self) -> impl Iterator<Item = &Block> {
        self.leaves
            .iter()
            .chain(&self.above)
            .chain(std::iter::once(&self.root))
    }

    /// Put another record in record `i`'s place, as a commit does: answers
    /// the CIDs of the blocks that takes out of the tree (the record's, and
    /// each node's from it to the root) and the nodes put in their place.
    /// The record is `records[i]` after.
    pub fn rewrite(&mut self, i: usize, version: u64) -> (Vec<Vec<u8>>, Vec<Block>) {
        let (l, a) = (i / LEAF, i / LEAF / FAN);
        let gone = vec![
            self.records[i].cid.clone(),
            self.leaves[l].cid.clone(),
            self.above[a].cid.clone(),
            self.root.cid.clone(),
        ];
        let op = i as u64 * self.accounts + self.account + 1;
        self.records[i] = record(self.seed, op, self.account, version);
        // A version of a node for each record under it and each time.
        let v = version * self.records.len() as u64 + i as u64 + 1;
        self.leaf(l, v);
        self.over(a, v);
        self.top(v);
        let made = vec![
            self.leaves[l].clone(),
            self.above[a].clone(),
            self.root.clone(),
        ];
        (gone, made)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The realistic commits are the sizes the README gives them, and the
    /// same every time.
    #[test]
    fn realistic_commits_are_as_described() {
        let n = 2000u64;
        let mut sums = [0usize; 4];
        for op in 1..=n {
            let c = real(SEED, op, op % 40);
            assert_eq!(c.event, real(SEED, op, op % 40).event);
            sums[0] += c.blocks[0].1.len();
            sums[1] += c.blocks[1].1.len();
            sums[2] += c.blocks[2].1.len() + c.blocks[3].1.len();
            sums[3] += c.event.len();
        }
        let mean = sums.map(|s| s as u64 / n);
        assert!(
            (170..=200).contains(&mean[0]),
            "a commit block of {}",
            mean[0]
        );
        assert!((270..=330).contains(&mean[1]), "a record of {}", mean[1]);
        assert!((1800..=2200).contains(&mean[2]), "two nodes of {}", mean[2]);
        assert!((2500..=3100).contains(&mean[3]), "an event of {}", mean[3]);
    }

    /// An account's state is its commits' records, in order of path, under
    /// a tree whose nodes are about 1 KB.
    #[test]
    fn a_state_holds_its_commits_records() {
        let s = State::new(SEED, 3, 40, 500);
        assert!(s.records.windows(2).all(|w| w[0].path < w[1].path));
        assert_eq!(
            s.records[7].bytes,
            real(SEED, 7 * 40 + 3 + 1, 3).blocks[1].1
        );
        assert_eq!(s.records[7].path, path(SEED, 7 * 40 + 3 + 1, 3));
        let nodes: Vec<&Block> = s.nodes().collect();
        let mean = nodes.iter().map(|n| n.bytes.len()).sum::<usize>() / nodes.len();
        assert!((800..=1200).contains(&mean), "nodes of {mean}");
    }
}