Introduction

Welcome to the Tribles Book. This first chapter is your map to Trible Space—the problems it tackles, the core ideas behind the triblespace crate, and the kinds of projects it was built to support. By the end of these opening pages you should be able to recognize when TribleSpace is the right tool, whether you are prototyping something new, extending an existing system, or adapting it for your own research purposes.

Why TribleSpace exists

TribleSpace exists because teams need to steward complex, diverse, and interconnected datasets without losing context. Research groups, startups, and digital libraries must pair large binary payloads with fine-grained facts, synchronize findings across laptops, servers, and mobile devices, and prove that derived results trace back to their inputs. Combining a conventional database, object store, and version-control workflow rarely delivers that outcome: blobs drift away from their provenance, merges become brittle, and auditing which observations justified a decision or model is tedious.

TribleSpace closes those gaps with a single substrate that stores heavyweight assets and the relationships that explain them. Think of it as a library catalog for blobs and a lab notebook for the annotations, measurements, and discussions that give those blobs meaning. Because facts and payloads travel together, features like version control, verifiability, and provenance fall naturally out of the data model instead of bolting on as afterthoughts.

That same structure also lets you support offline edits, reconcile concurrent changes safely, and ship datasets to partners with the evidence needed to trust them.

To deliver those outcomes, TribleSpace blends ideas from databases, version control, and content-addressed storage. Information is encoded as fixed-width tribles: 64-byte entity–attribute–value facts. Each trible stores two 16-byte extrinsic identifiers plus a 32-byte typed value. When a value exceeds the inline slot it becomes a schema-qualified hash pointing to an immutable content-addressed blob. The blob holds the heavyweight payload, while the trible remains a compact fact that fits neatly into indexes, caches, and query engines. Because both tribles and blobs are immutable, you can keep them in memory, on disk, or in remote object stores without transformation. Content hashes serve as identifiers, so every payload has a stable address and integrity is easy to verify when data is shared or synchronized.

This design unlocks capabilities that are difficult to achieve together in traditional stacks:

• Trustworthy collaboration – hashes and immutable histories provide the audit trail needed to review changes, merge branches, and reproduce results across teams.
• Content-addressed storage – values are stored and looked up by their contents, making caches and replicas safe even when they live on untrusted infrastructure.
• Flexible querying – the query engine blends indexes on the fly, letting a single query range across trible sets, succinct indexes, and familiar Rust collections such as hash maps in one pass.

Taken together, these traits make it feasible to build systems with rich histories, reproducible computations, and verifiable data exchange while keeping the developer experience approachable.

Who this book is for

If you are new to Tribles, the opening chapters build vocabulary and provide a guided tour of the core data structures. Developers who already understand the problem space can skim ahead to detailed sections on schema design, query semantics, and the Atreides join algorithm. The book also points to the API documentation whenever you are ready to explore the crate directly.

How to read this book

The book is organized so you can either read it front-to-back or jump straight to the material that answers your questions. Each chapter layers new ideas onto the previous ones:

1. Getting Started walks through installing the tooling, creating your first trible store, and issuing simple queries.
2. Architecture and Query Engine explain how the runtime is structured so you can reason about performance and extensibility.
3. Later sections explore schema design, incremental queries, repository workflows, and formal verification so you can grow from experiments to production systems.

Inline links lead to deeper resources and code samples. The Glossary offers quick refreshers on terminology, while Developing Locally covers how to set up a development environment and contribute back to the project. Whenever the book introduces a new concept, look for references to the crate documentation so you can inspect the corresponding APIs and examples.

By the end of this chapter you should have a mental model for why TribleSpace is structured the way it is. From there, head to the chapters that match your goals—whether that means learning to query data effectively or integrating Tribles into a larger system.

Philosophy

Triblespace was designed to feel approachable without sacrificing rigor. This chapter collects the guiding values that shape everything from the storage format to the public APIs. Treat it as a companion to the rest of the deep-dive sections: when you wonder "why does it work this way?", the answer usually traces back to one of these principles.

Clarity before cleverness

We favour predictable, mechanically simple components over opaque heuristics. Each subsystem should be understandable on its own, with behaviours that are obvious when composed with the rest of the stack. When a trade-off appears between a clever optimisation and debuggability, we err on the side of the latter and document the costs so future work can revisit the decision with better evidence.

Productive developer experience

APIs should read like regular Rust. Where backends demand asynchronous capabilities—such as object-store repositories—we wrap them in blocking entry points so typical workflows stay synchronous while still supporting advanced integrations. Well-documented patterns and composable macros let readers experiment in a REPL or test harness without extra scaffolding, and examples in the book mirror the crates users import so copy-and-paste snippets behave as advertised.

Soundness and data integrity

The engine must reject malformed data early, surface explicit error paths, and make invariants easy to audit. Safety checks live close to the data structures that rely on them, and proofs or tests accompany subtle invariants when feasible. Correctness remains the baseline for every optimisation.

Performance with headroom

Efficient data structures keep the core fast, but we prioritise predictable latency over micro-benchmarks that complicate maintenance. Hot paths receive focused tuning backed by benchmarks so we can understand the impact of each change.

Practical implications

These principles surface in day-to-day workflows:

• Documentation favours runnable snippets and end-to-end walkthroughs, lowering the barrier to experimentation.
• Internal abstractions expose minimal, intentional APIs, reducing the amount of context a contributor needs before making a change.
• Tooling—such as the preflight.sh convenience script, targeted Kani verification harnesses, and runnable doc tests—keeps quality checks accessible so they are run regularly rather than only in CI.

Taken together, the philosophy is simple: build a reliable system whose pieces are easy to reason about, teach, and extend.

Getting Started

This chapter walks you through creating a brand-new repository, committing your first entity, and understanding the pieces involved. It assumes you have Rust installed and are comfortable with running cargo commands from a terminal.

1. Add the dependencies

Create a new binary crate (for example with cargo new tribles-demo) and add the dependencies needed for the example. The triblespace crate provides the database, ed25519-dalek offers an implementation of the signing keys used for authentication, and rand supplies secure randomness.

cargo add triblespace ed25519-dalek rand

2. Build the example program

The walkthrough below mirrors the quick-start program featured in the README. It defines the attributes your application needs, stages and queries book data, publishes the first commit with automatic retries, and finally shows how to use try_push when you want to inspect and reconcile a conflict manually.

use ed25519_dalek::SigningKey;
use rand::rngs::OsRng;
use triblespace::prelude::*;

mod literature {
    use triblespace::prelude::*;
    use triblespace::prelude::blobencodings::LongString;
    use triblespace::prelude::inlineencodings::{Blake3, GenId, Handle, R256, ShortString};

    // Each shared attribute is declared with a stable 128-bit anchor. Its
    // identity is derived from (anchor, value encoding), so `title` is only
    // the human-readable Rust binding inside this module and changing the
    // encoding truthfully creates a different attribute.
    // Renaming the binding (or another codebase calling the same
    // field `name`) doesn't break compatibility, because everyone derives
    // the same underlying id from the shared anchor and encoding. See the
    // [Identifiers chapter](./deep-dive/identifiers.md#abstract-vs-semantic-identifiers)
    // for why abstract ids + local semantic names is the
    // recommended split.
    attributes! {
        /// The title of a work.
        ///
        /// Small doc paragraph used in the book examples.
        "A74AA63539354CDA47F387A4C3A8D54C" as pub title: ShortString;

        /// A quote from a work.
        "6A03BAF6CFB822F04DA164ADAAEB53F6" as pub quote: Handle<LongString>;

        /// The author of a work.
        "8F180883F9FD5F787E9E0AF0DF5866B9" as pub author: GenId;

        /// The first name of an author.
        "0DBB530B37B966D137C50B943700EDB2" as pub firstname: ShortString;

        /// The last name of an author.
        "6BAA463FD4EAF45F6A103DB9433E4545" as pub lastname: ShortString;

        /// The number of pages in the work.
        "FCCE870BECA333D059D5CD68C43B98F0" as pub page_count: R256;

        /// A pen name or alternate spelling for an author.
        "D2D1B857AC92CEAA45C0737147CA417E" as pub alias: ShortString;

        /// A throwaway prototype field; omit the id to derive it from the name and encoding.
        pub prototype_note: Handle<LongString>;
    }
}

// The examples anchor shared attributes independently of their Rust names. For
// quick prototypes you can omit the hex literal and `attributes!` will derive
// a deterministic id from the attribute name and encoding. The rare
// `"HEX_ID" unsafe as ...` form pins the literal bytes themselves; use it only
// to preserve an already-published attribute whose encoding cannot participate
// in identity.

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Repositories manage shared history; MemoryRepo keeps everything in-memory
    // for quick experiments. Swap in a `Pile` when you need durable storage.
    let storage = MemoryRepo::default();
    let mut repo = Repository::new(storage, SigningKey::generate(&mut OsRng), TribleSet::new())?;
    let branch_id = repo
        .create_branch("main", None)
        .expect("create branch");
    let mut ws = repo.pull(*branch_id).expect("pull workspace");

    // The entity! macro returns a Fragment carrying facts, descriptions of
    // the attributes actually used, and one blob store shared by both sets.
    // Accumulate into another Fragment with `+=` so every channel composes.
    let herbert = ufoid();
    let dune = ufoid();
    let mut library = Fragment::empty();

    library += entity! { &herbert @
        literature::firstname: "Frank",
        literature::lastname: "Herbert",
    };

    library += entity! { &dune @
        literature::title: "Dune",
        literature::author: &herbert,
        literature::quote: "I must not fear. Fear is the mind-killer.",
    };

    // This introductory repository API is legacy: Workspace::commit archives
    // the content facts and blobs but not Fragment::metafacts. New collection
    // code passes the Fragment directly to publish_fragment_commit, which
    // archives facts as data and metafacts as metadata.
    ws.commit(library, "import dune");

    // `checkout(..)` returns a Checkout — a TribleSet paired with the
    // commits that produced it, usable for incremental delta queries.
    let catalog = ws.checkout(..)?;
    let title = "Dune";

    // Multi-entity join: find quotes by authors of a given title.
    // `_?author` is a pattern-local variable that joins without projecting.
    for (f, l, quote) in find!(
        (first: String, last: String, quote),
        pattern!(&catalog, [
            { _?author @
                literature::firstname: ?first,
                literature::lastname: ?last
            },
            { _?book @
                literature::title: title,
                literature::author: _?author,
                literature::quote: ?quote
            }
        ])
    ) {
        let quote: View<str> = ws.get(quote)?;
        let quote = quote.as_ref();
        println!("'{quote}'\n - from {title} by {f} {l}.");
    }

    repo.push(&mut ws).expect("publish initial library");

    // ── Conflict resolution ────────────────────────────────────────
    // We rename the author; a collaborator independently records a
    // different name. try_push detects the conflict.

    ws.commit(
        entity! { &herbert @ literature::firstname: "Francis" },
        "use pen name",
    );

    let mut collaborator = repo.pull(*branch_id).expect("pull");
    collaborator.commit(
        entity! { &herbert @ literature::firstname: "Franklin" },
        "record legal first name",
    );
    repo.push(&mut collaborator).expect("publish collaborator");

    // try_push fails because the branch advanced. The returned
    // workspace carries the collaborator's history.
    if let Some(mut conflict_ws) = repo
        .try_push(&mut ws)
        .expect("attempt push")
    {
        // Inspect what the collaborator wrote.
        let their_catalog = conflict_ws.checkout(..)?;
        for first in find!(
            first: String,
            pattern!(&their_catalog, [{ &herbert @ literature::firstname: ?first }])
        ) {
            println!("Collaborator recorded: '{first}'.");
        }

        // Accept their history — abandon our conflicting firstname
        // commit and continue from the collaborator's state instead.
        ws = conflict_ws;

        // Record our preferred name as an alias rather than overwriting.
        ws.commit(
            entity! { &herbert @ literature::alias: "Francis" },
            "keep pen-name as alias",
        );

        repo.push(&mut ws).expect("publish resolution");
    }

    Ok(())
}

3. Run the program

Compile and execute the example with cargo run. The example uses an in-memory repository (MemoryRepo) so no files are created on disk — everything lives in RAM for the duration of the run.

cargo run

To persist data across runs, swap MemoryRepo::default() for Pile::open(&path)? backed by a file on disk.

Understanding the pieces

• Branch setup. Repository::create_branch registers the branch and returns an ExclusiveId guard. Dereference the guard (or call ExclusiveId::release) to obtain the Id that Repository::pull expects when creating a Workspace.
• Minting attributes. The attributes! macro names the fields that can be stored in the repository. Attribute identifiers are global—if two crates use the same identifier they will read each other's data—so give them meaningful project-specific names.
• Committing data. The entity! macro builds a set of attribute/value assertions. When paired with the ws.commit call it records a transaction in the workspace that becomes visible to others once pushed.
• Publishing changes. Repository::push merges any concurrent history into the workspace and retries automatically, making it ideal for monotonic updates where you are happy to accept the merged result.
• Manual conflict resolution. Repository::try_push performs a single optimistic attempt and returns a conflict workspace when the branch has advanced. Inspect that workspace to see the competing history, then decide whether to merge your changes or abandon them — as the example does by accepting the collaborator's name and recording ours as an alias.
• Closing repositories. When working with pile-backed repositories it is important to close them explicitly so buffered data is flushed and any errors are reported while you can still decide how to handle them. Calling repo.close()?; surfaces those errors; if the repository were only dropped, failures would have to be logged or panic instead. Alternatively, you can recover the underlying pile with Repository::into_storage and call Pile::close() yourself.

See the crate documentation for additional modules and examples.

Switching signing identities

The setup above generates a single signing key for brevity, but collaborating authors typically hold individual keys. Call Repository::set_signing_key before branching or pulling when you need a different default identity, or use Repository::create_branch_with_key and Repository::pull_with_key to choose a specific key per branch or workspace. The Managing signing identities section covers this workflow in more detail.

Developing Locally

Tribles is developed with stable Rust tooling and a small collection of helper scripts. This chapter walks through preparing a development environment, running tests, and rebuilding the documentation so you can iterate with confidence.

Prerequisites

1. Install a recent Rust toolchain from rustup.rs. The default stable channel is what the project targets.

2. Clone the repository and switch into it:

   git clone https://github.com/TribleSpace/triblespace-rs.git
   cd triblespace-rs
   

3. (Optional) Install mdbook with cargo install mdbook if you would like to preview the rendered documentation locally.

Everyday workflows

The repository includes several scripts that keep formatting, tests, and book builds in sync:

• ./scripts/devtest.sh executes the most relevant unit and integration tests for fast feedback while you are iterating.
• ./scripts/preflight.sh runs formatting, the full test suite, and rebuilds this book. Run it before committing to ensure your branch is in good shape.
• ./scripts/build_book.sh regenerates the documentation after you modify Markdown chapters or code snippets.

You can always fall back to the standard Cargo commands (cargo fmt, cargo test, etc.) if you prefer to run specific tools by hand.

Rebuilding the book

Once mdbook is installed you can rebuild the documentation with:

./scripts/build_book.sh

This script compiles the chapters into book/book, allowing you to open the HTML output in a browser. Rebuilding regularly helps catch stale examples and keeps the published copy aligned with the codebase.

Identifiers for Distributed Systems

Distributed systems are assembled from independently authored pieces of data. Keeping those pieces addressable requires names that survive replication, concurrent edits, and local conventions. We have found it useful to categorize identifier schemes along two axes:

UFOID = Universal Forgettable Ordered ID — a 128-bit identifier built from a 32-bit time prefix (the low 32 bits of the UNIX time in milliseconds) plus 96 random bits. The prefix gives recently-minted ids high locality: they sort roughly by mint time, so a system can range-scan "everything created in the last N hours" directly off the id. Forgettable refers to that prefix wrapping around about every 50 days — the high bits of absolute time are intentionally dropped, leaving a rolling window rather than a monotonic-forever clock. Within the window the ordering is exact; outside it the prefix repeats. That's the right trade for systems that only reason over a bounded recent horizon and garbage-collect older data — caches, robotics pipelines, event streams — where the time-locality is worth far more than a globally unique timestamp. (Use timestamp_distance to compare two prefixes correctly across the rollover.)

FUCID = Fast Unsafe Compressible ID — a 128-bit identifier generated by XOR-ing a per-source salt with a monotonic counter, so consecutive ids from the same source compress extremely well at the cost of being predictable per source. See the Comparison of Identifier Types table below for when to reach for which.

• Rows — derivability. An intrinsic identifier can be recomputed from the entity alone: anyone holding the bytes can produce the same id independently. An extrinsic identifier is assigned separately from the entity — the entity carries no hint of what its id should be.
• Columns — content encoding. An abstract identifier is opaque: its bits carry no readable meaning about the entity. A semantic identifier encodes meaning (words, codes, URL paths) that humans or machines can consume as signal without a lookup.

The axes are independent — every cell is populated — but the quadrants have different structural properties (see Quadrant Properties below). Classifying an identifier along both axes makes its trade-offs explicit and clarifies when a workflow needs to combine multiple schemes.

Abstract vs. Semantic Identifiers

Semantic identifiers

Semantic identifiers (names, URLs, descriptive labels, embeddings) carry meaning about the thing they reference. Humans don't work well with opaque bit patterns — we think in names. Any usable system has to expose some semantic layer, which is why semantic identifiers are structurally essential rather than merely convenient.

The power of the semantic layer scales inversely with its scope:

• Locally, semantic names are exactly what you want. A bibliography's [Herbert1965], a codebase's firstname, a paper's "the agent" — each is unique enough within its scope, collides with nothing outside it, and can evolve as your understanding improves.
• Globally, the same names get expensive. Semantic content is low-entropy (there are only so many sensible names for a thing), so two parties naming independently will collide. Avoiding collisions requires coordination — an authority, or an unbounded scope prefix whose root is still an authority (see Quadrant Properties).

Distributed systems get the best of both worlds by pairing a shared abstract identifier for global identity with many local semantic names on top. The same attribute id can be timestamp in my codebase, legacy_timestamp in yours, and created_at in a third — all binding to the same underlying id, each name authoritative within its scope. Three concrete benefits fall out:

• Decoupling. Groups don't have to agree on vocabulary to share data. The id is the shared ontology; names are each group's business.
• Evolution. You can rename your local label when the meaning clarifies ("height" → "stature") without breaking anyone else's system, because the global binding is unchanged.
• No bike-shedding. The hardest coordination problem in any shared system is naming. Making names purely local reduces that cost to zero.

Embeddings deserve a special mention. They encode meaning in a machine-friendly form that can be compared for similarity instead of exact equality. That makes them great for recommendations and clustering but still unsuitable as primary identifiers: two distinct entities can legitimately share similar embeddings, and embeddings can change whenever the underlying model is retrained.

Abstract identifiers

Abstract identifiers (UUIDs, UFOIDs, FUCIDs, hashes, signatures) strip all meaning away in favor of uniqueness. They can be minted without coordination, usually by drawing from a high-entropy space and trusting probability to keep collisions effectively impossible. Abstract identifiers shine when you need:

• Stable handles that survive across replicas and through refactors.
• Globally unique names without a centralized registrar.
• Cheap, constant-time generation so every component can allocate identifiers on demand.

Because they carry no inherent semantics, abstract identifiers are almost always paired with richer metadata. They provide the skeleton that keeps references consistent while semantic identifiers supply the narrative that humans consume.

Intrinsic vs. Extrinsic Identifiers

The intrinsic/extrinsic axis captures whether an identifier can be recomputed from the entity itself or whether it is assigned externally.

Intrinsic identifiers

Intrinsic identifiers (cryptographic hashes, digital signatures, content-based addresses) are derived from the bytes they describe. They function as fingerprints: if two values share the same intrinsic identifier then they are bit-for-bit identical. This property gives us:

• Immutability. Changing the content produces a different identifier, which immediately signals tampering or corruption.
• Self-validation. Replicas can verify received data locally instead of trusting a third party.
• Stronger adversarial guarantees. Because an attacker must find collisions deliberately, intrinsic identifiers rely on cryptographic strength rather than purely statistical rarity.

Extrinsic identifiers

Extrinsic identifiers (names, URLs, DOIs, UUIDs, UFOIDs, FUCIDs) are assigned by policy instead of by content. They track a conceptual entity as it evolves through versions, formats, or migrations. In other words, extrinsic identifiers carry the "story" of a thing while intrinsic identifiers nail down individual revisions.

Thinking about the classic ship of Theseus thought experiment makes the distinction concrete: the restored ship and the reconstructed ship share the same extrinsic identity (they are both "Theseus' ship") but have different intrinsic identities because their planks differ.

A note on signatures and public keys

Signatures are a special form of hash: a digest over (content, private_key). Used as identifiers they sit in the intrinsic-abstract cell — anyone holding the content and the author's public key can recompute and verify.

Public keys used as actor identities (identifying a person, agent, or service) are a different animal: a pubkey doesn't derive from the person it identifies — it's assigned by whoever generated the keypair. That makes pubkey-as-identity extrinsic abstract, essentially a high-entropy UUID with a bonus cryptographic capability.

Quadrant Properties

Classifying along two independent axes leaves four quadrants, and each has a structural property worth calling out because it constrains system design.

Extrinsic + Semantic (global) ⇒ an authority. If an identifier carries meaning, can't be derived from the entity, and has to be unique across all actors, someone had to assign that meaning globally. Semantic content is low-entropy by nature — the space of sensible names is small, so two parties minting independently will often collide — and avoiding collisions requires coordination. That coordinator is the authority, whether explicit (DOI registrar, ICANN, ISBN agency) or implicit. You can postpone this by adding scope prefix ("global tree of local ids" — DNS, Java packages, DOIs with publisher/journal structure) but the tree has a root, and the root is still an authority. The identifier also grows unboundedly as scopes stack: com.triblespace.core.repo.branch::metadata is already longer than some of the values it names.

Extrinsic + Semantic (local) is essential and free. The same property reverses once scope is bounded. A bibliography's [Herbert1965] is unique within the paper; a codebase's firstname is unique within its namespace. Local authority is trivial because it is the scope. Most of the human-facing vocabulary in any working system lives here, riding on top of abstract identifiers for global identity.

Extrinsic + Abstract can be fully decentralized. A 128-bit random identifier collides only statistically. Two parties minting UUIDs (or UFOIDs, or pubkeys) independently will never see each other's values in practice, so no coordinator is needed — the decentralization is paid for in entropy, not consensus.

Intrinsic + anything is decentralized by construction. The entity is the authority: any two parties with the same bytes produce the same id (for hashes) or the same neighborhood in embedding space (for embeddings). No registrar exists, because none is needed.

The upshot: if you want a decentralized naming system, you have two moves: use extrinsic abstract ids globally, and extrinsic semantic names locally. Don't promote semantic identifiers to global scope. Every centralized naming system in practice (domains, ISBNs, DOIs, academic affiliations) exists because it violated that rule.

Picking entity ids in code

TribleSpace lets you mix intrinsic and extrinsic identifiers depending on what you are modeling. The entity! macro mirrors that split:

#![allow(unused)]
fn main() {
use triblespace::examples::literature;
use triblespace::prelude::*;

// Intrinsic identity (default): the id is derived deterministically from the
// canonical fact rows, so identical record literals unify.
let record = entity! {
    literature::firstname: "Frank",
    literature::lastname: "Herbert",
};

// Extrinsic identity: supply an id expression when you want a stable subject
// whose facts can evolve across edits and commits.
let alice = ufoid();
let subject = entity! { &alice @
    literature::firstname: "Frank",
};

// `_ @` is an explicit synonym for the intrinsic form.
let also_intrinsic = entity! { _ @ literature::firstname: "Frank" };

// Optional facts: use `?:` with an `Option<T>` value to omit missing data
// without resorting to branching.
let maybe_alias: Option<&str> = None;
let with_optional = entity! { _ @
    literature::firstname: "Frank",
    literature::alias?: maybe_alias,
};

// Repeated facts: use `*:` with an `IntoIterator<Item = T>` to emit multiple
// facts for the same attribute.
let aliases = ["Frank", "F.H."];
let with_repeated = entity! { _ @
    literature::firstname: "Frank",
    literature::alias*: aliases,
};
}

For the intrinsic form, entity! first represents every encoded fact as NIL || attribute || value, using the ordinary 64-byte trible layout with an empty entity column. It sorts and deduplicates those rows, hashes the complete contiguous sequence with BLAKE3, takes the final 16 digest bytes as the entity id, and fills that id into every row. Identity therefore depends on the raw projected facts, not source order or Rust conversion history. An explicit entity id bypasses this derivation.

These two forms intentionally have different ownership types. An explicit subject must be supplied as an ExclusiveId, which is the capability to add facts to that extrinsic identity. An intrinsic entity instead exports its reproducible root as a plain Id. Its defining rows are exactly the rows that participated in the hash; constructing it does not mint, acquire, or register an ExclusiveId. Turning that root into an ExclusiveId merely to append unhashed facts would break the content-addressed meaning of the root. Choose an explicit subject from the beginning when an entity needs to grow independently of its current facts.

This canonical-row protocol deliberately defines a new intrinsic-identity epoch relative to the historical hash of concatenated attribute || value pairs. Existing persisted intrinsic ids must be migrated or re-ingested when adopting this epoch; the implementation must never silently mix both schemes.

Embeddings as Semantic Intrinsic Identifiers

Embeddings blur our neat taxonomy. They are intrinsic because they are computed from the underlying data, yet they are overtly semantic because similar content produces nearby points in the embedding space. That duality makes them powerful for discovery:

• Systems can exchange embeddings as a "lingua franca" without exposing raw documents.
• Expensive feature extraction can happen once and power many downstream indexes, decentralizing search infrastructure.
• Embeddings let us compare otherwise incomparable artifacts (for example, a caption and an illustration) by projecting them into a shared space.

Despite those advantages, embeddings should still point at a durable abstract identifier rather than act as the identifier. Collisions are expected, model updates can shift the space, and floating-point representations can lose determinism across hardware.

High-Entropy Identifiers

For a truly distributed system, the creation of identifiers must avoid the bottlenecks and overhead associated with a central coordinating authority. At the same time, we must ensure that these identifiers are unique.

To guarantee uniqueness, we use abstract identifiers containing a large amount of entropy, making collisions statistically irrelevant. However, the entropy requirements differ based on the type of identifier:

• Extrinsic abstract identifiers need enough entropy to prevent accidental collisions in normal operation.
• Intrinsic abstract identifiers must also resist adversarial forging attempts, requiring significantly higher entropy.

From an information-theoretic perspective, the length of an identifier determines the maximum amount of entropy it can encode. For example, a 128-bit identifier can represent ( 2^{128} ) unique values, which is sufficient to make collisions statistically negligible even for large-scale systems.

For intrinsic identifiers, 256 bits is widely considered sufficient when modern cryptographic hash functions (e.g., SHA-256) are used. These hash functions provide strong guarantees of collision resistance, preimage resistance, and second-preimage resistance. Even in the event of weaknesses being discovered in a specific algorithm, it is more practical to adopt a new hash function than to increase the bit size of identifiers.

Additionally, future advances such as quantum computing are unlikely to undermine this length. Grover's algorithm would halve the effective security of a 256-bit hash, reducing it to ( 2^{128} ) operations—still infeasible with current or theoretical technology. As a result, 256 bits remains a future-proof choice for intrinsic identifiers.

Such 256-bit intrinsic identifiers are represented by the types Hash and Handle.

Not every workflow needs cryptographic strength. We therefore ship three high-entropy abstract identifier families—RNGID, UFOID, and FUCID—that keep 128 bits of global uniqueness while trading off locality, compressibility, and predictability to suit different scenarios.

Comparison of Identifier Types

"Predictability" here is a tradeoff axis, not a quality: higher predictability enables tighter compression and cache-friendly scans, but reveals mint metadata (time or source) and is therefore unsuitable whenever adversarial unpredictability matters. For those cases prefer RNGID's fully random bits, or step up to a 256-bit cryptographic Hash.

Example: Scientific Publishing

A published paper fuses several distinct identifier roles into a single centralized name (the DOI) — and a single centralized registry for authors (the ORCID). The quadrant framing suggests pulling these apart so each lives where it fits:

• Artifact identity → intrinsic-abstract. Identify each .html/.pdf by a cryptographic hash of its bytes. Any two parties referencing the same digest look at bit-for-bit identical content; verification is self-contained.
• Revision-group identity ("the same paper across revisions") → extrinsic-abstract. Mint a UFOID/FUCID at first publication and attach each later revision's content hash to it. Stable across rewrites, decentralizable, no registrar needed.
• Author identity → extrinsic-abstract, specifically the author's public key. A pubkey is extrinsic (you assign it by generating a keypair), abstract (the bits carry no meaning about the person), high-entropy (no collisions), and bundles a cryptographic capability: the author can sign the paper and anyone can verify it against their pubkey without a registrar. ORCID solves the same problem with central authority; pubkeys solve it with entropy plus cryptography.
• Human-readable labels → extrinsic-semantic, kept local. Citation keys ([Herbert1965]), reading-list tags, display titles, abbreviations in a bibliography — all semantic, all scoped to the document or reader that uses them. They're the human layer riding on top of the three abstract ids above, free to evolve and diverge across contexts without coordination.

DOIs land in the extrinsic-semantic, global-scope quadrant: a publisher prefix, a journal stem, often a human-recognizable slug — all assigned by a registrar and meant to be unique across every paper in the world. By the quadrant properties above that quadrant structurally requires a central authority, for collision avoidance (low semantic entropy across a global namespace) and for resolution (translating the id to a concrete artifact). DOIs-as-centralized isn't a design flaw; it's the price of asking one identifier to play the artifact-identity, revision-grouping, and human-label roles at global scope.

What triblespace recommends isn't "replace DOIs with something better in the same quadrant" — it's to decompose the role DOIs try to play into identifiers that each live in a quadrant they fit: content hashes for artifacts, abstract extrinsic ids (UFOID for revision groups, pubkeys for authors) for anything that needs global identity, and semantic labels (including DOIs and ORCIDs, when you need citation-compatibility with the outside world) as per-context references on top. Each role lands where decentralization is cheap or free.

ID Ownership

In distributed systems, consistency requires monotonicity due to the CALM principle ("Consistency As Logical Monotonicity" — any program that only grows its state can be eventually consistent without coordination; anything that can retract state requires coordination). However, this is not necessary for single-writer systems. By assigning each ID an owner, we ensure that only the current owner can write new information about an entity associated with that ID. This allows for fine-grained synchronization and concurrency control.

To create a transaction, you can uniquely own all entities involved and write new data for them simultaneously. Since there can only be one owner for each ID at any given time, you can be confident that no other information has been written about the entities in question.

By default, all minted ExclusiveIds are associated with the thread they are dropped from. These IDs can be found in queries via the local_ids function.

Once the IDs are back in scope you can either work with them directly as ExclusiveIds or move them into an explicit IdOwner for a longer lived transaction. The example below shows both approaches in action:

#![allow(unused)]
fn main() {
use triblespace::examples::literature;
use triblespace::prelude::*;

let mut kb = TribleSet::new();
{
    let isaac = ufoid();
    let jules = ufoid();
    kb += entity! { &isaac @
        literature::firstname: "Isaac",
        literature::lastname: "Asimov",
    };
    kb += entity! { &jules @
        literature::firstname: "Jules",
        literature::lastname: "Verne",
    };
} // `isaac` and `jules` fall back to this thread's implicit IdOwner here.

let mut txn_owner = IdOwner::new();
let mut updates = TribleSet::new();

for (author, name) in find!(
    (author: ExclusiveId, name: String),
    and!(
        local_ids(author),
        pattern!(&kb, [{
            ?author @ literature::firstname: ?name
        }])
    )
) {
    // `author` is an ExclusiveId borrowed from the implicit thread owner.
    let author_id = txn_owner.insert(author);

    {
        let borrowed = txn_owner
            .borrow(&author_id)
            .expect("the ID was inserted above");
        updates += entity! { &borrowed @ literature::lastname: name.clone() };
    } // `borrowed` drops here and returns the ID to `txn_owner`.
}
}

The entity! macro accepts ExclusiveIds by value or reference, so you can pass either an owned guard or a borrowed one.

Sometimes you want to compare two attributes without exposing the comparison variable outside the pattern. Prefixing the binding with _?, such as _?name, allocates a scoped variable local to the macro invocation. Both pattern! and pattern_changes! will reuse the same generated query variable whenever the _? form appears again, letting you express equality constraints inline without touching the outer find! signature.

Binding the variable as an ExclusiveId means the closure that find! installs will run the TryFromInline implementation for ExclusiveId. The conversion invokes Id::acquire and would silently skip the row if the current thread did not own the identifier (filter semantics). The local_ids constraint keeps the query safe by only enumerating IDs already owned by this thread, so no rows are filtered in practice. In the example we immediately move the acquired guard into txn_owner, enabling subsequent calls to IdOwner::borrow that yield OwnedIds. Dropping an OwnedId automatically returns the identifier to its owner so you can borrow it again later. If you only need the ID for a quick update you can skip the explicit owner entirely, bind the variable as a plain Id, and call Id::acquire when exclusive access is required.

Ownership and Eventual Consistency

While a simple grow set (like the commit histories backing a branch) already constitutes a conflict-free replicated data type (CRDT), it is also limited in expressiveness. To provide richer semantics while guaranteeing conflict-free mergeability we allow only "owned" IDs to be used in the entity position of newly generated triples. As owned IDs are [Send] but not [Sync] owning a set of them essentially constitutes a single-writer transaction domain, allowing for some non-monotonic operations like if-does-not-exist over the set of contained entities. Note that this does not make operations that would break CALM (consistency as logical monotonicity) safe — e.g. delete.

The trible module defines the Trible struct, the smallest unit of knowledge the system stores. Instances of Tribles live inside TribleSets, which index each fact in several complementary ways so that queries can be answered with as little work as possible.

┌────────────────────────────64 byte───────────────────────────┐
┌──────────────┐┌──────────────┐┌──────────────────────────────┐
│  entity-id   ││ attribute-id ││        inlined value         │
└──────────────┘└──────────────┘└──────────────────────────────┘
└────16 byte───┘└────16 byte───┘└────────────32 byte───────────┘
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─▶

At a high level a trible is a three-tuple consisting of an entity, an attribute, and a value. The entity and attribute are both 128‑bit abstract extrinsic identifiers as described in [triblespace::core::id], while the value is an arbitrary 256‑bit [triblespace::core::inline::Inline]. The value width deliberately matches the size of an intrinsic identifier so larger payloads can be referenced via blobs without inflating the inlined representation.

Abstract identifiers

Entities and attributes are purely extrinsic; their identifiers do not encode any meaning beyond uniqueness. An entity may accrue additional tribles over time and attributes simply name relationships without prescribing a schema. This keeps the format agnostic to external ontologies and minimises accidental coupling between datasets.

The value slot can carry any 256‑bit payload. Its size is dictated by the need to embed an intrinsic identifier for out‑of‑line data. When a fact exceeds this space the value typically stores a blob handle pointing to the larger payload.

Tribles are stored as a contiguous 64‑byte array with the entity occupying the first 16 bytes, the attribute the next 16, and the value the final 32 bytes. The name "trible" is a portmanteau of triple and byte and is pronounced like "tribble" from Star Trek – hence the project's mascot, Robert the tribble. This rigid layout keeps the representation friendly to SIMD optimisations and allows the storage layer to compute sizes deterministically.

Index permutations

TribleSets index each fact under all six permutations of entity (E), attribute (A) and value (V) so any combination of bound variables can be resolved efficiently. Regardless of which columns a query fixes the search can reach matching leaves with a handful of comparisons:

┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐  ┌─────┐
│ EAV │  │ EVA │  │ AEV │  │ AVE │  │ VEA │  │ VAE │
└──┬──┘  └──┬──┘  └──┬──┘  └──┬──┘  └──┬──┘  └──┬──┘
   │        │        │        │        │        │
┌───────────────────────────────────────────────────────┐
│            order-specific inner nodes                 │
└───────────────────────────────────────────────────────┘ 
   │        │        │        │        │        │
   ▼        ▼        ▼        ▼        ▼        ▼

┌───────────────────────────────────────────────────────┐
│                   SHARED LEAVES                       │
│     single canonical E–A–V tribles used by all        │
└───────────────────────────────────────────────────────┘

Each permutation maintains its own inner nodes, but all six share leaf nodes containing the 64‑byte trible. This avoids a naïve six‑fold memory cost while still letting the search pick the most selective ordering, keeping joins resistant to skew even when cardinalities vary widely.

Advantages

• A total order over tribles enables efficient storage and canonicalisation.
• Simple byte‑wise segmentation supports indexing and querying without an interning mechanism, keeping memory usage low and parallelisation easy while avoiding the need for garbage collection.
• Schemas describe the value portion directly, making serialisation and deserialisation straightforward.
• The fixed 64‑byte layout makes it easy to estimate the physical size of a dataset as a function of the number of tribles stored.
• The minimalistic design aims to minimise entropy while retaining collision resistance, making it likely that a similar format would emerge through convergent evolution and could serve as a universal data interchange format.

Set operations and monotonic semantics

TribleSets provide familiar set-theoretic helpers such as TribleSet::union, TribleSet::intersect and TribleSet::difference. union consumes the right-hand operand and merges its contents into the receiver in place, while intersect and difference each produce a fresh TribleSet without mutating their inputs. Together these helpers make it straightforward to merge datasets, locate their overlap or identify the facts that still need to propagate between replicas while keeping the original sources intact.

This design reflects the crate's commitment to CALM-friendly, monotonic semantics. New information can be added freely, but existing facts are never destroyed. Consequently, difference is intended for comparing snapshots (e.g. "which facts are present in the remote set that I have not yet indexed?") rather than for destructive deletion. This keeps workflows declarative and convergent: sets can be combined in any order without introducing conflicts, and subtraction simply reports the gaps that remain to be filled.

Direction and consistency

In many triple stores the direction of an edge is chosen incidentally—there is no intrinsic preference for hasColor over colorOf. This ambiguity often leads to confusion, duplication, or both as different writers pick different conventions. Common mitigations either mirror every edge automatically (as done by OWL and RDF through inverseOf, doubling storage or demanding runtime inference) or devolve into bikeshedding about the "correct" orientation.

tribles avoids that trap by giving edge direction explicit semantics: the arrow points from the entity making the claim to the entity being described. The observer owns the identifier and is responsible for the consistency of the facts it asserts—see ID Ownership. This rule naturally fits the distributed setting where each entity has a single authoritative writer.

Viewed another way, edges always flow from describing to described entities, while cycles represent consensus between the parties involved. For example, hasColor must point from the object that exhibits the colour to the entity representing that colour. The orientation is therefore a consequence of the statement's meaning, not an arbitrary modelling choice.

Query Language

This chapter introduces the core query facilities provided by triblespace. A query is described in a small declarative language that states which values should match instead of spelling out the iteration strategy. When you read a query, you are effectively looking at a logical statement about the data: if the constraints can all be satisfied, then the variable bindings are produced as results. The declarative style gives the engine freedom to reorder work and choose efficient execution strategies.

Every macro shown here is a convenience wrapper around a concrete Constraint implementation. When you need finer control—or want to assemble constraints manually outside the provided macros—reach for the corresponding builder types in triblespace::core::query.

Declaring a query

The find! macro builds a Query by declaring variables and a constraint expression. The macro mirrors Datalog syntax: the head ((...)) lists the variables you want back, and the body describes the conditions they must meet. A minimal invocation looks like this:

let results = find!((a), a.is(1.into())).collect::<Vec<_>>();

find! returns an Iterator over the bound variables. Matches can be consumed lazily or collected into common collections.

The head is an ordered projection with BAG semantics. The engine emits one row every time a complete binding is found, and the head selects which of its variables you get back. Hidden variables therefore multiply: an assignment proved by eight different witnesses is emitted eight times. Deduplication is the consumer's job — collect into a HashSet, or ask the question with exists! so the fan-out is never enumerated. The Query Engine chapter explains why the engine does not deduplicate for you.

When the head declares a single variable, omit the parentheses to get bare values instead of 1-tuples:

for a in find!(a, a.is(1.into())) {
    println!("match: {a}");
}

When the head declares multiple variables, wrap them in parentheses to get tuples:

for (a, b) in find!((a, b), and!(a.is(1.into()), b.is(2.into()))) {
    println!("{a}, {b}");
}

Adding more variables is as simple as expanding the list: find!((a, b, c), ...) yields (a, b, c) tuples. Variables declared in the head can be reused multiple times inside the constraint to express joins. When a variable appears in several clauses the engine ensures every occurrence binds to the same value. Repeating a variable in two patterns, for example, restricts the result set to entities that satisfy both attribute assignments simultaneously. The order of declarations defines the shape of the tuple in the iterator, so reorganising the head changes how you destructure results.

Typed variables

Variables optionally include a concrete type to convert the underlying value. The constraint phase still works with untyped Inline instances; conversion happens when results are emitted. These conversions use TryFromInline.

By default, if a conversion fails the entire row is silently skipped — like a constraint that doesn't match. For types whose TryFromInline::Error is Infallible the error branch is dead code and no rows can ever be accidentally filtered.

Append ? to a variable to receive the raw Result<T, E> instead. Both Ok and Err values pass through without filtering, matching Rust's ? semantics of "bubble the error to the caller."

// `x` is filtered (rows where conversion fails are skipped).
// `y` is passed through as Result (no filtering).
find!((x: i32, y: Inline<ShortString>?),
      and!(x.is(1.into()), y.is("foo".to_inline())))

The query engine explores assignments that satisfy the constraint and yields the declared variables in head order, one row per satisfying assignment. Variables omitted from the head still participate in the search — they decide whether an assignment exists, and each distinct value they take is a separate row. A repeated variable in the head is rejected because it would not add a new projected column.

The empty head find!((), constraint) therefore yields one () per satisfying assignment, which makes find!((), ...).count() a way to count them. When you only want to know whether any assignment exists, use exists!: it stops at the first one instead of draining the fan-out.

Collecting results

Any type that implements FromIterator can collect the results of a query. Vec<_> is common for tests and examples, while HashSet<_> is useful when the match order is irrelevant. When you only need the first result, call iterator adapters such as next, find, or try_fold to avoid materializing the full result set.

Built-in constraints

find! queries combine a small set of constraint operators to form a declarative language for matching tribles. Each operator implements Constraint and can therefore be mixed and nested freely.

Any data structure that can iterate its contents, test membership, and report its size can implement ContainsConstraint. Membership constraints are particularly handy for single-column collections such as sets or map key views, while multi-position sources like TribleSet rely on pattern! to keep entity, attribute, and value bindings aligned.

Constant matches (is)

Call Variable::is when you need a binding to equal a specific value. The method returns a ConstantConstraint that checks whether the solver can assign the variable to the provided Inline. Constant constraints behave like any other clause: combine them with and! to narrow a variable after other constraints have proposed candidates, or place them inside or! branches to accept multiple literals.

find!((title: Inline<_>),
      and!(dataset.has(title), title.is("Dune".to_inline())));

The snippet above keeps only the rows where title equals "Dune". Because is constrains the variable's value rather than projecting a new binding, it is also handy for helpers such as temp! when you want to filter hidden bindings without exposing them in the result tuple.

pattern! and pattern_changes! fold literal values (and attribute constants) directly into the pattern constraint as constant Terms — no variable is allocated for them — so you often get the same behaviour simply by writing the desired value in the pattern:

find!((friend: Inline<_>),
      pattern!(&dataset,
               [{ _?person @ social::friend: ?friend,
                  social::city: "Caladan" }]));

Repeating .is(...) on the same variable with different values causes the query to fail—just as conflicting pattern! clauses would—so prefer or! (or switch to a membership helper such as .has(...)) when you want to accept several constants.

Intersections (and!)

and! combines multiple constraints that must all hold simultaneously. Each sub-clause can introduce new bindings or further narrow existing ones, and the solver is free to reorder the work to reduce the search space. When a sub-constraint fails to produce a candidate that is compatible with the current bindings, the whole conjunction rejects that branch and moves on. The macro accepts any number of arguments, so and!(...) is often a convenient way to keep related clauses together without nesting additional find! calls:

let favourites = favourite_titles(); // e.g. a HashSet<Id> built elsewhere
find!((book: Inline<_>, author: Inline<_>),
      and!(favourites.has(book),
           pattern!(&dataset,
                    [{ ?book @ literature::title: "Dune",
                       literature::author: ?author }])));

Here the membership test over favourites and the attribute pattern from dataset run as part of the same conjunction. The solver joins them on their shared bindings (book and author) so only tuples that satisfy every clause make it into the result set. Because and! simply returns a constraint, you can nest it inside other combinators such as temp! or or! to structure queries however you like.

Alternatives (or!)

Use or! to express alternatives. Each branch behaves like an independent constraint and may introduce additional bindings that participate in the surrounding query, provided every branch mentions the same set of variables:

find!((alias: Inline<_>),
      temp!((entity),
            or!(pattern!(&dataset,
                         [{ ?entity @ profile::nickname: ?alias }]),
                pattern!(&dataset,
                         [{ ?entity @ profile::display_name: ?alias }]))));

Each branch contributes every match it can produce given the current bindings. Results are a bag of complete bindings: one row per witness of the declared variables (here entity and alias), so a nickname and display name with different raw values contribute two rows, equal values for the same entity collapse (the union is a set per binding step), and the same alias witnessed by different entities yields one row per entity — dedup of projected columns belongs to the consumer. Branches that cannot match simply contribute nothing.

All branches of an or! must bind exactly the same set of variables; branch-local variables are not supported. This is a consequence of the engine's flat result schema — every result row binds the same variable set exactly once, so there is no way to represent a variable that only exists in some alternatives. (It is not a semantic or monotonicity limitation: the union itself is monotonic.) Attribute constants and literal values do not count towards a branch's variable set: pattern! folds them into the constraint as constant Terms rather than allocating hidden variables, which is what lets the branches above use different attributes (nickname vs. display_name) while still declaring the identical set {entity, alias}. Only genuine query variables must align: if two branches reference different variables the constraint panics at construction time, naming the mismatched sets. Note that an anonymous entity ({ attr: ?v } without an ?entity @ id) introduces a fresh variable scoped to its own pattern!, so bind entities explicitly — as the example does with temp!((entity), ...) — when combining such patterns with or!.

Temporary variables (temp!)

Real queries often need helper bindings that participate in the joins but do not show up in the result tuple. Wrap the relevant constraint with temp!((...vars...), expr) to mint hidden variables and evaluate expr with them in scope:

find!((person: Inline<_>),
      temp!((friend),
            and!(pattern!(&dataset,
                          [{ _?p @ social::person: ?person, social::friend: ?friend }]),
                 pattern!(&dataset,
                          [{ ?friend @ social::city: "Caladan" }]))));

The helper binding friend links the two patterns, ensuring the same entity is used across both clauses without expanding the result tuple. temp! can create multiple variables at once (temp!((street, city), ...)). You always wrap the hidden bindings in a tuple, so each invocation reads temp!((...vars...), ...). Here social would be a namespace module exporting the person, friend, and city attributes. The variables adopt the value schemas implied by the constraints they appear in, so no extra annotations are required. When working outside the query macros, call VariableContext::next_variable directly instead.

Temporary variables are hidden from the result tuple, but they are not hidden from the search: several friends that prove the same projected person produce that person several times. Collect into a set when you want each person once, or restructure the query so the inner condition is an exists! check and the fan-out is never enumerated at all.

When the helper variable lives entirely within a single pattern, consider using _?alias instead of temp!. Both pattern! and pattern_changes! support _?ident placeholders that mint fresh bindings scoped to that one macro invocation. They behave like non-projected variables: you can reuse the _?ident multiple times inside the pattern to relate attributes, but the binding vanishes once control leaves the macro. Reach for temp! when the helper must span several constraints or when you need to reuse the same hidden binding across multiple patterns.

Example

use triblespace::prelude::*;
use triblespace::core::examples::{self, literature};

let dataset = examples::dataset();

for (title,) in find!((title: Inline<_>),
                     and!(dataset.has(title), title.is("Dune".to_inline()))) {
    println!("Found {}", title.from_inline::<&str>());
}

This query searches the example dataset for the book titled "Dune". The variables and constraint can be adapted to express more complex joins and filters. For instance, you can introduce additional variables to retrieve both the title and the author while sharing the same dataset predicate:

for (title, author) in find!((title: Inline<_>, author: Inline<_>),
                             and!(title.is("Dune".to_inline()),
                                  pattern!(&dataset,
                                           [{ _?book @ literature::title: ?title,
                                              literature::author: ?author }]))) {
    println!("{title} was written by {}", author.from_inline::<&str>());
}

The extra variables participate in the join automatically; no explicit loop nesting or indexing is required.

Attribute patterns (pattern!)

The pattern! macro provides a concise way to match entities by attribute assignments. It expands to a constraint that can be used directly inside find!.

Important: in pattern! values prefixed with ? refer to variables declared in the surrounding find! head while string/number literals and more complex expressions are treated as literal values. Use _?name when you need a fresh variable that is scoped to a single macro invocation; you can reference it multiple times within the same pattern without adding it to the find! head. Parenthesised expressions remain supported for explicit literals.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod literature {
    use triblespace::prelude::*;
    attributes! {
        "0DBB530B37B966D137C50B943700EDB2" as firstname: inlineencodings::ShortString;
        "6BAA463FD4EAF45F6A103DB9433E4545" as lastname: inlineencodings::ShortString;
    }
}
let mut kb = TribleSet::new();
let e = ufoid();
kb += entity! { &e @ literature::firstname: "William", literature::lastname: "Shakespeare" };

let results: Vec<_> = find!((ee: Id), pattern!(&kb, [{ ?ee @ literature::firstname: "William" }])).collect();
assert_eq!(results.len(), 1);
}

Patterns may contain multiple clauses and reuse _? bindings to relate attributes without introducing extra columns in the result set. A single _?person variable can connect several attribute/value pairs while staying scoped to the pattern:

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod literature {
    use triblespace::prelude::*;
    attributes! {
        "0DBB530B37B966D137C50B943700EDB2" as firstname: inlineencodings::ShortString;
        "6BAA463FD4EAF45F6A103DB9433E4545" as lastname: inlineencodings::ShortString;
    }
}
let mut kb = TribleSet::new();
let e = ufoid();
kb += entity! { &e @ literature::firstname: "Frank", literature::lastname: "Herbert" };

let author_last_names: Vec<_> = find!((last: Inline<_>),
    pattern!(&kb, [{ _?person @ literature::firstname: "Frank", literature::lastname: ?last }])
).collect();
}

Here _?person remains scoped to the pattern while ensuring both attributes are drawn from the same entity. When a pattern references collections other than a TribleSet, ensure the collection implements TriblePattern so that the macro can materialize the requested triples.

To share a hidden binding across multiple patterns, declare it once with temp! and reference it with ?name from each clause:

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    attributes! {
        "A19EC1D9DD534BA9896223A457A6B9C9" as name: inlineencodings::ShortString;
        "C21DE0AA5BA3446AB886C9640BA60244" as friend: inlineencodings::GenId;
    }
}
let mut kb = TribleSet::new();
let alice = ufoid();
let bob = ufoid();
kb += entity! { &alice @ social::name: "Alice", social::friend: &bob };
kb += entity! { &bob @ social::name: "Bob" };

let results: Vec<_> = find!((friend_name: Inline<_>),
    temp!((friend),
          and!(pattern!(&kb, [{ _?person @ social::friend: ?friend,
                                  social::name: ?friend_name }]),
               pattern!(&kb, [{ ?friend @ social::name: "Bob" }]))))
.collect();
}

The _?person variable is still local to the first pattern, while friend joins the two constraints without changing the projected results. As above, social denotes a namespace that defines the name and friend attributes.

exists!

Sometimes you only want to check whether a constraint has any solutions. The exists! macro mirrors the find! syntax but returns a boolean:

use triblespace::prelude::*;

assert!(exists!((x), x.is(1.into())));
assert!(!exists!((x), and!(x.is(1.into()), x.is(2.into()))));

Internally, exists! stops as soon as the first result is found. It is a lightweight alternative to find! when the mere existence of a match matters more than the actual bindings.

Custom constraints

Every building block implements the Constraint trait. You can implement this trait on your own types to integrate custom data sources or query operators with the solver. Collections that want to power pattern! implement TriblePattern so they can materialize the entity/attribute/value triples a pattern asks for. Membership-style helpers such as has(...) work with anything that implements ContainsConstraint, making it easy to join against pre-existing indexes, caches, or service clients without copying data into a TribleSet.

use std::collections::HashSet;

use triblespace::prelude::*;
use triblespace::prelude::inlineencodings::ShortString;
use triblespace::core::query::hashsetconstraint::SetConstraint;

struct ExternalTags<'a> {
    tags: &'a HashSet<String>,
}

impl<'a> ContainsConstraint<'a, ShortString> for ExternalTags<'a> {
    type Constraint = SetConstraint<ShortString, &'a HashSet<String>, String>;

    fn has(self, variable: Variable<ShortString>) -> Self::Constraint {
        SetConstraint::new(variable, self.tags)
    }
}

let tags: HashSet<String> = ["rust", "datalog"].into_iter().map(String::from).collect();
let external = ExternalTags { tags: &tags };
let matches: Vec<_> =
    find!((tag: Inline<ShortString>), external.has(tag)).collect();

The example wraps an external HashSet so it can be queried directly. A TriblePattern implementation follows the same shape: create a constraint type that reads from your backing store and return it from pattern. The query engine drives both traits through Constraint, so any data source that speaks the protocol can participate in find!. Four methods are required:

propose and confirm take a Frontier — a batch of parent bindings, of which a single binding is the width-1 case. Loop over Frontier::rows, calling ProposalBuffer::open(row) before each row's candidates; on the confirm side, ignore the parent tags if your verdict does not depend on the binding, or walk the region with Candidates::for_each_parent if it does.

Two more methods have defaults you can override: satisfied (defaulting to true) and influence (defaulting to "every variable I touch except this one").

The rules a custom constraint has to respect are short:

• estimate is a cost quote. It steers variable ordering and nothing else. A wrong estimate makes the search slower, never incorrect. None means "not my variable", not "no candidates".
• propose only appends. Entries already in the buffer belong to a sibling constraint in an enclosing composite; leave them alone. Within one chunked enumeration, never deliver the same value twice — a duplicate inflates row multiplicity.
• confirm only kills. It may never add a candidate or revive a dead one, and it may skip entries that are already dead. This is what lets several confirmers write into the same region in any order, or in parallel, and still compute their conjunction.
• satisfied may be optimistic, but only upward. Returning true while a relevant variable is unbound is fine; returning false must mean there is genuinely no completion. Once every variable the constraint touches is bound, the answer must be exact — or! relies on that to discard dead alternatives, and a fully constant constraint is settled by a single satisfied call at construction with no search to correct it later.

The Query Engine chapter explains the protocol, the search that drives it, and the reasoning behind these rules in detail.

Recursive traversal

Queries in this chapter all have a fixed number of clauses, which means a fixed number of hops. Genuinely recursive questions — "everyone reachable through a chain of follows", "all ancestors via repeated parent" — cannot be written this way.

Earlier versions of the crate answered them with a path! macro that evaluated a regular expression over edge attributes inside the query engine. That macro and its evaluator have been removed: query-time traversal needs per-activation state, which the stateless constraint protocol has no place for, and keeping it inside the protocol meant every constraint paid for machinery only paths used.

The stable replacement is the standalone triblespace-paths crate. Its PathExpr builder describes sequence, alternatives, repetition, optionality, and inverse steps, then compiles them to a fixed epsilon-free automaton. The crate combines that automaton with graph edges to materialize an accepted endpoint relation, exposed through an ordinary two-variable constraint. That constraint composes directly with find!, and!, and pattern!; see Regular Path Indexes for expression construction, the low-level automaton escape hatch, and range-native repository maintenance.

For a fixed small number of hops, explicit pattern clauses joined on temp! variables remain simpler. For unbounded traversal, use the path index or drive a one-off frontier search from application code when materializing a potentially dense endpoint relation would not pay for itself.

Macro Cookbook

This chapter is a quick map of the macro surface. The goal is not to replace the deeper chapters, but to make the everyday question easy:

"I know roughly what I want to do. Which macro should I reach for?"

The macros fall into three layers:

• Encoding definition: attributes!
• Fact construction: entity!
• Query construction: find!, exists!, pattern!, pattern_changes!, and!, or!, temp!

Define attributes with attributes!

Use attributes! to declare typed attributes once, then reuse them everywhere else.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;

mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::{GenId, ShortString};

    attributes! {
        /// A person's display name.
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;

        /// Another person this person knows.
        pub friend: GenId;
    }
}

assert_ne!(social::name.id(), social::friend.id());
}

The three declaration forms differ in what determines identity:

• "HEX_ANCHOR" as name: Encoding derives the id from the stable anchor and encoding. This is the safe default for shared schemas: renaming the Rust binding is free, while changing the encoding creates a different attribute.
• name: Encoding derives the id from the name and encoding. It is convenient when the source name itself is the shared identifier.
• "HEX_ID" unsafe as name: Encoding uses the literal id without incorporating the encoding. Reserve it for compatibility with an already-published id; the caller must ensure the type still matches the stored rows.

Reach for this macro when:

• you are defining a namespace or encoding module
• you want attributes with stable ids and inline encodings
• you want doc comments to become attribute metadata

If you already have attributes, you usually do not need attributes! in the rest of the code you are writing.

Build facts with entity!

Use entity! when you want to create tribles for one entity.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::ShortString;
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
    }
}
let alice = fucid();
let facts = entity! { &alice @
    social::name: "Alice",
};

assert_eq!(facts.root(), Some(alice.id));
assert_eq!(facts.len(), 1);
}

If you omit the entity id, entity! derives one deterministically from the facts. It encodes each fact as a 64-byte NIL || attribute || value row, sorts and deduplicates the rows, hashes their complete contiguous byte sequence with BLAKE3, and uses the final 16 digest bytes as the entity id. It then fills that id into every row before constructing the TribleSet. Field order and duplicate repeated values therefore do not affect identity; an absent optional field contributes no row.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::ShortString;
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
    }
}
let facts = entity! { _
    @ social::name: "Alice"
};

assert!(facts.root().is_some());
assert_eq!(facts.len(), 1);
}

The macro also supports optional and repeated fields:

let aliases = ["Al", "A."];
let maybe_nickname = Some("Ace");

let facts = entity! { &alice @
    social::name: "Alice",
    social::nickname?: maybe_nickname,
    social::alias*: aliases,
};

Reach for this macro when:

• you are constructing new data
• you want optional/repeated attribute ergonomics
• you want a deterministic derived id for a value object

Match facts with pattern!

Use pattern! to turn trible-shaped structure into a query constraint.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::{GenId, ShortString};
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
        "B74AA63539354CDA47F387A4C3A8D54C" as pub friend: GenId;
    }
}
let mut kb = TribleSet::new();
let alice = fucid();
let bob = fucid();
kb += entity! { &alice @ social::friend: &bob };
kb += entity! { &bob @ social::name: "Bob" };
let results: Vec<Id> = find!(
    friend: Id,
    pattern!(&kb, [
        { alice.id @ social::friend: ?friend },
        { ?friend @ social::name: "Bob" }
    ])
).collect();

assert_eq!(results, vec![bob.id]);
}

Inside a pattern:

• ?name refers to a query variable from the surrounding query
• _?name introduces a local helper variable scoped to that pattern
• literal expressions become equality constraints automatically

Use pattern! when you are querying the current contents of a TribleSet, Checkout, or another pattern-capable source.

Query for results with find!

Use find! when you want rows back.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::ShortString;
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
    }
}
let mut kb = TribleSet::new();
let alice = fucid();
kb += entity! { &alice @ social::name: "Alice" };
let names: Vec<Inline<_>> = find!(
    name: Inline<_>,
    pattern!(&kb, [{ _?person @ social::name: ?name }])
).collect();

let first: &str = names[0].try_from_inline().unwrap();
assert_eq!(first, "Alice");
}

There are three common shapes:

• find!(value, constraint) for one projected variable as a bare value
• find!((a, b), constraint) for tuples
• find!((), constraint) when you want to count satisfying assignments without projecting any of them (reach for exists! if you only need yes/no)

find! heads have BAG semantics: one row per complete binding, with the head selecting which variables come back. Hidden variables introduced by temp! or _?name still multiply the result — an entity proved by eight witnesses is emitted eight times, and the empty head returns one () per satisfying assignment. Deduplicate on your side (collect::<HashSet<_>>()), or use exists! for the inner condition so the fan-out is never enumerated.

Typed projections happen in the head:

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::ShortString;
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
    }
}
let mut kb = TribleSet::new();
let alice = fucid();
kb += entity! { &alice @ social::name: "Alice" };
let ids: Vec<_> = find!(
    person: Id,
    pattern!(&kb, [{ ?person @ social::name: "Alice" }])
).collect();

assert_eq!(ids, vec![alice.id]);
}

Use ? on a projected variable when you want conversion failures as Result<T, E> instead of dropping the row.

Ask existence questions with exists!

Use exists! when you only need yes/no.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::ShortString;
    attributes! {
        "A74AA63539354CDA47F387A4C3A8D54C" as pub name: ShortString;
    }
}
let mut kb = TribleSet::new();
let bob = fucid();
kb += entity! { &bob @ social::name: "Bob" };
let has_bob = exists!(
    pattern!(&kb, [{ _?person @ social::name: "Bob" }])
);

assert!(has_bob);
}

You can also keep the typed-head form when the projection itself matters to the check:

let has_name = exists!(
    (name: Inline<_>),
    pattern!(&kb, [{ ?person @ social::name: ?name }])
);

Use exists!(constraint) for pure existence checks instead of find!((), constraint).next().is_some().

Match only new results with pattern_changes!

Use pattern_changes! for incremental queries: matches are allowed to join against the full current state, but at least one contributing trible must come from the change set.

for (work,) in find!(
    (work: Inline<_>),
    pattern_changes!(&full, &delta, [
        { ?work @ literature::author: &shakespeare }
    ])
) {
    // process only newly introduced matches
}

Reach for this macro when:

• you already have full and delta
• you want monotonic incremental processing
• pattern! would re-emit old matches every time

See Incremental Queries for the full workflow.

Combine constraints with and! and or!

Use and! when every clause must hold:

find!(
    (friend: Inline<_>),
    and!(
        pattern!(&kb, [{ ?person @ social::name: "Alice" }]),
        pattern!(&kb, [{ ?person @ social::friend: ?friend }])
    )
)

Use or! when any branch may hold:

find!(
    (alias: Inline<_>),
    or!(
        pattern!(&kb, [{ ?person @ social::nickname: ?alias }]),
        pattern!(&kb, [{ ?person @ social::name: ?alias }])
    )
)

or! branches must mention the same variable set.

Introduce helpers with temp!

Use temp! when you need a fresh variable only inside a sub-expression.

find!(
    (person: Inline<_>),
    temp!((friend), and!(
        pattern!(&kb, [{ ?person @ social::friend: ?friend }]),
        pattern!(&kb, [{ ?friend @ social::name: "Bob" }])
    ))
)

This is useful when the helper participates in joins but should not be projected. When the helper lives entirely within a single pattern!, prefer a _?var placeholder: it enforces equality across its occurrences inside that pattern without being projected.

Which macro should I use?

If you are:

• defining encodings: use attributes!
• building facts for one entity: use entity!
• matching trible structure: use pattern!
• matching only newly added results: use pattern_changes!
• asking for rows back: use find!
• asking for a boolean: use exists!
• requiring all clauses: use and!
• allowing alternatives: use or!
• introducing a fresh helper variable: use temp! (or _?var inside a single pattern!)

From here, the best next stops are:

• Query Language for the execution model
• Patterns & Recipes for modeling patterns
• Incremental Queries for pattern_changes!

Encodings

TribleSpace stores data in strongly typed values and blobs. An encoding describes the language‑agnostic byte layout for these types: [Inline]s always occupy exactly 32 bytes while [Blob]s may be any length. Encodings translate those raw bytes to concrete application types and decouple persisted data from a particular implementation. This separation lets you refactor to new libraries or frameworks without rewriting what's already stored or coordinating live migrations. The crate ships with a collection of ready‑made encodings located in triblespace::core::inline::encodings and triblespace::core::blob::encodings.

When data crosses the FFI boundary or is consumed by a different language, the encoding is the contract both sides agree on. Consumers only need to understand the byte layout and identifier to read the data—they never have to link against your Rust types. Likewise, the Rust side can evolve its internal representations—add helper methods, change struct layouts, or introduce new types—without invalidating existing datasets.

Why 32 bytes?

Storing arbitrary Rust types requires a portable representation. Instead of human‑readable identifiers like RDF's URIs, Tribles uses a fixed 32‑byte array for all values. This size provides enough entropy to embed intrinsic identifiers—typically cryptographic hashes—when a value references data stored elsewhere in a blob. Keeping the width constant avoids platform‑specific encoding concerns and makes it easy to reason about memory usage.

Conversion traits

Conversion goes through the Encodes<Source> trait, which lives on the encoding (the encoding is the impl target; the source is the trait parameter). This is the same direction as std's From<T> — and for the same reason: it trivially satisfies Rust's orphan rule, so you can write impl Encodes<SomeForeignType> for MyLocalEncoding without any "trait position 0" gymnastics.

The ergonomic source-side methods .to_inline() / .to_blob() / .into_encoded() are auto-derived blanket implementations — users never implement them directly, the same way you never implement Into<T> in Rust:

User implements:     Auto-derived via blanket:
  Encodes<T> for S     IntoEncoded<S> for T  (+ IntoInline / IntoBlob aliases)

For fallible conversions where the error type is part of the contract (parsing a hex string into a hash, validating a timestamp range, rejecting reserved bits), use TryToInline / TryFromInline — kept as separate traits because the error type is per‑source.

#![allow(unused)]
fn main() {
use triblespace::core::inline::encodings::shortstring::ShortString;
use triblespace::core::inline::{TryFromInline, TryToInline, Inline};

struct Username(String);

impl TryToInline<ShortString> for Username {
    type Error = &'static str;

    fn try_to_inline(self) -> Result<Inline<ShortString>, Self::Error> {
        if self.0.is_empty() {
            Err("username must not be empty")
        } else {
            self.0
                .as_str()
                .try_to_inline()
                .map_err(|_| "username too long or contains NULs")
        }
    }
}

impl TryFromInline<'_, ShortString> for Username {
    type Error = &'static str;

    fn try_from_inline(value: &Inline<ShortString>) -> Result<Self, Self::Error> {
        String::try_from_inline(value)
            .map(Username)
            .map_err(|_| "invalid utf-8 or too long")
    }
}
}

Encoding identifiers

Every encoding declares a unique 128‑bit identifier, accessible via the MetaDescribe::id method (for example, ShortString::id()). Persisting these IDs keeps serialized data self describing so other tooling can make sense of the payload without linking against your Rust types. Dynamic language bindings (like the Python crate) inspect the stored encoding identifier to choose the correct decoder, while internal metadata stored inside Trible Space can use the same IDs to describe which encoding governs a value, blob, or hash protocol.

Identifiers also make it possible to derive deterministic attribute IDs when you ingest external formats. Wrap the source field name in an entity-core fragment — Attribute::<S>::from(entity!{ metadata::name: <name handle>, metadata::value_encoding: <S as MetaDescribe>::id() }) — to combine the encoding ID with the source field name and produce a stable attribute so re-importing the same data always targets the same column. The attributes! macro offers three identity origins. Omitting the literal derives identity from (name, encoding), which is useful for quick experiments or source-shaped internal attributes. "HEX_ANCHOR" as name: Encoding derives identity from (anchor, encoding), which is the preferred form for attributes shared across binaries or languages: the Rust name can change freely, while a type change truthfully creates a different column. The exceptional "HEX_ID" unsafe as name: Encoding form uses the literal bytes verbatim. It is for preserving an already-published identity and carries the unchecked obligation that the encoding still agrees with all rows under that id.

Built‑in inline encodings

The crate provides the following inline encodings out of the box:

• GenId – an abstract 128 bit identifier.
• ShortString – a UTF-8 string up to 32 bytes.
• U256BE / U256LE – 256-bit unsigned integers.
• I256BE / I256LE – 256-bit signed integers.
• R256BE / R256LE – 256-bit rational numbers.
• F64 – IEEE-754 double-precision floating point number (little-endian).
• F256BE / F256LE – 256-bit floating point numbers.
• Hash and Handle – cryptographic digests and blob handles (see hash.rs).
• ED25519RComponent, ED25519SComponent and ED25519PublicKey – signature fields and keys.
• NsTAIInterval to encode time intervals.
• Boolean – all-zero for false, all-0xFF for true.
• LineLocation – a (start_line, start_col, end_line, end_col) span encoded as four big-endian u64 values.
• RangeU128 – a half-open (start, end) range of two big-endian u128 values.
• RangeInclusiveU128 – an inclusive (start, end) range of two big-endian u128 values.
• UnknownInline as a fallback when no specific encoding is known.

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
use triblespace::core::metadata::MetaDescribe;
use triblespace::core::inline::encodings::shortstring::ShortString;
use triblespace::core::inline::{IntoInline, InlineEncoding};

let v: Inline<ShortString> = "hi".to_inline();
let raw_bytes = v.raw; // Persist alongside the encoding's metadata id.
let encoding_id = ShortString::id(); // derived via describe(&mut scratch).root()
}

Built‑in blob encodings

The crate also ships with these blob encodings:

• LongString for arbitrarily long UTF‑8 strings.
• RawBytes for opaque file-backed byte payloads.
• SimpleArchive which stores a raw sequence of tribles.
• SuccinctArchiveBlob which stores the SuccinctArchive index type for offline queries. It contains only deterministic Ring/wavelet data and EOF metadata. SuccinctArchiveRank9IndexBlob is the separately content-addressed, source-bound native Rank9/select accelerator; its first 32 bytes identify the exact raw archive it indexes. The SuccinctArchive helper exposes high-level iterators, returns both artifacts with to_blob_pair, and attaches an existing pair with from_blob_pair. SuccinctArchiveBlob::build_from_simple_archive derives the canonical raw artifact without constructing query indexes, while SuccinctArchiveBlob::merge computes an exact-validated raw set union with no runtime or Rank9 attachment.
• WasmCode for WebAssembly bytecode stored as a blob.
• UnknownBlob for data of unknown type.

#![allow(unused)]
fn main() {
use triblespace::core::metadata::MetaDescribe;
use triblespace::core::blob::encodings::longstring::LongString;
use triblespace::core::blob::{Blob, BlobEncoding, IntoBlob};

let b: Blob<LongString> = "example".to_blob();
let encoding_id = LongString::id(); // derived via describe(&mut scratch).root()
}

Both value and blob encodings can emit optional discovery metadata. Calling MetaDescribe::describe returns a rooted Fragment (exporting the encoding id) whose facts tag the encoding entity with metadata::KIND_INLINE_ENCODING or metadata::KIND_BLOB_ENCODING and may attach a metadata::name and metadata::description (LongString handles). Persist the description blobs alongside the metadata tribles if you want the text to remain readable.

Choosing the right encoding

When defining an attribute, the encoding determines how the 32-byte value slot is interpreted. Use this decision tree to pick the right one:

What are you storing?
│
├─ A reference to another entity?
│  └─ GenId
│
├─ A tag, category, or enum-like classifier?
│  └─ metadata::tag (GenId) — tags are entities with their own ID.
│     Use metadata::name to give them a human-readable label.
│     ⚠ Do NOT define a separate ShortString tag attribute —
│     use the canonical metadata::tag and mint tag IDs.
│
├─ A short label or display name?
│  ├─ Fits in 32 bytes (≤32 UTF-8 bytes)?
│  │  └─ ShortString
│  └─ Longer text?
│     └─ Handle<LongString>  (blob)
│
├─ A number?
│  ├─ Integer
│  │  ├─ Fits in 64 bits? → U256BE (zero-extended) or custom u64 encoding
│  │  └─ Needs full 256 bits? → U256BE / I256BE
│  ├─ Floating point
│  │  ├─ Standard double? → F64
│  │  └─ Extended precision? → F256BE
│  └─ Rational? → R256
│
├─ A timestamp or time range?
│  └─ NsTAIInterval
│
├─ A cryptographic value?
│  ├─ Content hash? → Hash<Blake3>
│  ├─ Reference to a blob? → Handle<BlobEncoding>
│  └─ Signature? → ED25519RComponent / ED25519SComponent / ED25519PublicKey
│
├─ A file or binary payload?
│  └─ Handle<RawBytes>  (blob)
│
├─ A large structured dataset?
│  └─ Handle<SimpleArchive>  (blob, stores a TribleSet)
│
└─ Something else?
   ├─ Fits in 32 bytes? → define a custom InlineEncoding
   └─ Larger? → define a custom BlobEncoding + use Handle

Rules of thumb:

• If two values should be joinable (appear in the same query variable), they must share an encoding. Choose the most specific encoding that covers both uses.
• Prefer ShortString over LongString when the text fits — inline values avoid a blob lookup.
• Use GenId for relationships between entities. Never store entity references as strings.
• When in doubt between an inline encoding and a blob, ask: "will I ever want to query or join on this directly?" If yes, it should be inline. If it's opaque content you just retrieve, use a blob handle.

Defining new encodings

Custom formats implement [InlineEncoding] or [BlobEncoding]. A unique identifier serves as the encoding ID. The example below defines a little-endian u64 inline encoding and a simple blob encoding for arbitrary bytes.

pub struct U64LE;

impl MetaDescribe for U64LE {
    fn describe() -> triblespace::core::trible::Fragment {
        let id: Id = id_hex!("0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A");
        entity! { ExclusiveId::force_ref(&id) @
            metadata::name: "u64le",
            metadata::tag:  metadata::KIND_INLINE_ENCODING,
        }
    }
}

impl InlineEncoding for U64LE {
    type ValidationError = Infallible;
    type Encoding = Self;
}

impl Encodes<u64> for U64LE {
    type Output = Inline<U64LE>;
    fn encode(source: u64) -> Inline<U64LE> {
        let mut raw = [0u8; INLINE_LEN];
        raw[..8].copy_from_slice(&source.to_le_bytes());
        Inline::new(raw)
    }
}

impl TryFromInline<'_, U64LE> for u64 {
    type Error = std::convert::Infallible;
    fn try_from_inline(v: &Inline<U64LE>) -> Result<Self, std::convert::Infallible> {
        Ok(u64::from_le_bytes(v.raw[..8].try_into().unwrap()))
    }
}

pub struct BytesBlob;

impl MetaDescribe for BytesBlob {
    fn describe() -> triblespace::core::trible::Fragment {
        let id: Id = id_hex!("B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0B0");
        entity! { ExclusiveId::force_ref(&id) @
            metadata::name: "bytesblob",
            metadata::tag:  metadata::KIND_BLOB_ENCODING,
        }
    }
}

impl BlobEncoding for BytesBlob {}

impl Encodes<Bytes> for BytesBlob {
    type Output = Blob<BytesBlob>;
    fn encode(source: Bytes) -> Blob<BytesBlob> {
        Blob::new(source)
    }
}

impl TryFromBlob<BytesBlob> for Bytes {
    type Error = Infallible;
    fn try_from_blob(b: Blob<BytesBlob>) -> Result<Self, Self::Error> {
        Ok(b.bytes)
    }
}

See examples/custom_schema.rs for the full source.

Versioning and evolution

Schemas form part of your persistence contract. When evolving them consider the following guidelines:

1. Prefer additive changes. Introduce a new encoding identifier when breaking compatibility. Consumers can continue to read the legacy data while new writers use the replacement ID.
2. Annotate data with migration paths. Store both the encoding ID and a logical version number if the consumer needs to know which rules to apply. UnknownInline/UnknownBlob allow you to safely defer decoding until a newer binary is available.
3. Keep validation centralized. Place invariants in your encoding conversions so migrations cannot accidentally create invalid values.

By keeping encoding identifiers alongside stored values and blobs you can roll out new representations incrementally: ship readers that understand both IDs, update your import pipelines, and finally switch writers once everything recognizes the replacement encoding.

Inline formatters (WASM)

Binary formats are great for portability and performance, but they can be painful to inspect if you don’t know the encoding ahead of time. TribleSpace supports an optional encoding-level formatter mechanism: an inline encoding can point to a small sandboxed WebAssembly module that turns its raw 32 bytes into a human-readable string.

The formatter is stored as a blob (blobencodings::WasmCode) and referenced from the encoding identifier entity via the metadata attribute metadata::value_formatter.

The built-in runner lives behind the wasm feature flag (enabled by default in the triblespace facade crate) and uses wasmi with tight limits (fuel, memory pages, output size). Modules must not import anything and use the following minimal ABI:

• memory (linear memory)
• format(w0: i64, w1: i64, w2: i64, w3: i64) -> i64

The format arguments are the raw 32 bytes split into 4×8-byte chunks (little-endian). The return value packs the output pointer and output length:

• Success returns (output_len << 32) | output_ptr with output_ptr != 0.
• Failure returns (error_code << 32) | 0 (i.e. output_ptr == 0).

The core crate can optionally ship built-in formatters for its built-in value encodings. Enable the wasm feature to have MetaDescribe::describe (which is fallible) attach metadata::value_formatter entries for the standard encodings. This feature requires the wasm32-unknown-unknown Rust target at build time because the bundled formatters are compiled to WebAssembly via the #[value_formatter] proc macro.

Incremental Queries

The query engine normally evaluates a pattern against a complete TribleSet, recomputing every match from scratch. Applications that ingest data continuously often only need to know which results are introduced by new tribles. Tribles supports this with semi-naive evaluation, a classic incremental query technique. Instead of running the whole query again, we focus solely on the parts of the query that can see the newly inserted facts and reuse the conclusions we already derived from the base dataset.

The Checkout pattern

Workspace::checkout returns a [Checkout] — a TribleSet paired with the set of commits that produced it. That commit set acts as a continuation token: pass it as the start of a range selector on the next checkout to exclude already-seen commits.

// Initial load — full starts as a clone of the first checkout.
let mut changed = repo.pull(branch_id)?.checkout(..)?;
let mut full = changed.clone();

loop {
    // Process new results. full already includes changed.
    for title in find!(title: String, pattern_changes!(&full, &changed, [
        { _?author @ literature::firstname: "Frank" },
        { _?book @ literature::author: _?author, literature::title: ?title }
    ])) {
        println!("new: {title}");
    }

    // Advance: exclude all commits we've already processed.
    changed = repo.pull(branch_id)?.checkout(full.commits()..)?;
    full += &changed;
}

Checkout dereferences to TribleSet, so it works directly with find!, pattern!, and pattern_changes!. The full accumulator is a Checkout that grows monotonically. The += operator merges both the TribleSet facts and the CommitSet. The changed checkout carries the commit set forward automatically.

This pattern avoids building shadow data models in Rust structs. Query the TribleSet directly with find! — it has sub-microsecond point lookups and single-digit microsecond joins.

Delta evaluation

Given a full dataset and a set of changed tribles, the engine runs the original query multiple times. Each run restricts a different triple constraint to the changed set while the remaining constraints see the full set. The union of these runs yields solutions supported by at least one changed trible. A tuple emitted by an earlier invocation may legitimately recur when a later delta adds another witness. The process is:

1. accumulate changed into full with full += &changed, which merges both the facts and the commit set,
2. for every triple in the query, evaluate a variant where that triple matches against changed,
3. union all per-triple results to obtain the incremental answers.

Because each variant touches only one triple from the changed set, the work grows with the number of constraints and the size of the delta rather than the size of the full dataset.

The variants are combined with or!, and a union deduplicates the candidate values it proposes for each variable before the search descends. Two variants that support the same assignment therefore contribute one candidate at every level, so that assignment is enumerated once per query rather than once per supporting variant.

That is the only deduplication involved. find! heads have bag semantics like everywhere else: hidden variables still multiply the projected answer, so an entity proved by several changed witnesses is emitted once per witness. Collect into a set when you want each projected tuple once.

Nothing is remembered between invocations. A later delta can return the same projected tuple again when a newly added fact supplies a new proof — that reports support which is new in that delta, not a claim that the tuple was absent from every earlier result. Applications that need global once-only delivery should retain the tuples they have already consumed (in a set, say), while applications that need distinct witness events should project the witness identity explicitly.

Monotonicity and CALM

Removed results are not tracked. Tribles follow the CALM principle: a program whose outputs are monotonic in its inputs needs no coordination. Updates simply add new facts and previously derived conclusions remain valid. When conflicting information arises, applications append fresh tribles describing their preferred view instead of retracting old ones. Stores may forget obsolete data, but semantically tribles are never deleted.

Exclusive IDs and absence checks

Exclusive identifiers tighten the blast radius of non-monotonic logic without abandoning CALM. Holding an ExclusiveId proves that no other writer can add tribles for that entity, so checking for the absence of a triple about that entity becomes stable: once you observe a missing attribute, no concurrent peer will later introduce it. This permits existence/absence queries in the narrow scope of entities you own while keeping global queries monotonic.

Even with that safety net, prefer monotonic reads and writes when possible because they compose cleanly across repositories. Absence checks should be reserved for workflows where the ExclusiveId guarantees a closed world for the entity — such as asserting a default value when none exists or verifying invariants before emitting additional facts. Outside that boundary, stick to append-only predicates so derived results remain valid as new data arrives from other collaborators.

Example

The pattern_changes! macro expresses these delta queries. It takes the full TribleSet (which must include the changed tribles) and the changed subset. The macro unions variants of the query where each triple is constrained to the changed set, matching only results that involve at least one new trible.

    let storage = MemoryRepo::default();
    let mut repo =
        Repository::new(storage, SigningKey::generate(&mut OsRng), TribleSet::new()).unwrap();
    let branch_id = repo.create_branch("main", None).expect("branch");

    // ── commit initial data ──────────────────────────────────────────
    let herbert = ufoid();
    let dune = ufoid();
    let mut ws = repo.pull(*branch_id).expect("pull");
    let mut initial = TribleSet::new();
    initial +=
        entity! { &herbert @ literature::firstname: "Frank", literature::lastname: "Herbert" };
    initial += entity! { &dune @ literature::title: "Dune", literature::author: &herbert };
    ws.commit(initial, "initial");
    repo.push(&mut ws).unwrap();

    // ── first checkout: load everything ──────────────────────────────
    // `full` starts as a clone of the first checkout.
    let mut changed = repo
        .pull(*branch_id)
        .expect("pull")
        .checkout(..)
        .expect("checkout");
    let mut full = changed.clone();

    // On the first iteration, everything is "new".
    let all_titles: Vec<String> = find!(
        title: String,
        pattern_changes!(&full, &changed, [
            { _?author @ literature::firstname: "Frank" },
            { _?book @ literature::author: _?author, literature::title: ?title }
        ])
    )
    .collect();
    assert_eq!(all_titles, vec!["Dune".to_string()]);

    // ── simulate an external update ──────────────────────────────────
    let messiah = ufoid();
    let mut ws = repo.pull(*branch_id).expect("pull");
    ws.commit(
        entity! { &messiah @ literature::title: "Dune Messiah", literature::author: &herbert },
        "add Dune Messiah",
    );
    repo.push(&mut ws).unwrap();

    // ── incremental update ───────────────────────────────────────────
    // Pull fresh, exclude all commits we've already processed.
    changed = repo
        .pull(*branch_id)
        .expect("pull")
        .checkout(full.commits()..)
        .expect("delta");
    full += &changed;

    // Only Dune Messiah shows up — Dune was in the previous checkout.
    let new_titles: Vec<String> = find!(
        title: String,
        pattern_changes!(&full, &changed, [
            { _?author @ literature::firstname: "Frank" },
            { _?book @ literature::author: _?author, literature::title: ?title }
        ])
    )
    .collect();
    assert_eq!(new_titles, vec!["Dune Messiah".to_string()]);
    println!("New titles: {new_titles:?}");

The example commits Herbert and Dune, simulates an external update that adds Dune Messiah, then uses the Checkout pattern to discover only the newly added title. The multi-entity join links books to their author via _?author, yet pattern_changes! returns only results where at least one trible is new — Dune does not reappear. The first checkout loads the full history; the second uses changed.commits().. to exclude already-processed commits and fetch only new ones.

Comparing history points

Workspace::checkout accepts commit selectors which can describe ranges in repository history. Checking out a range like a..b walks the history from b back toward a, unioning the contents of every commit that appears along the way but excluding commits already returned by the a selector. When commits contain only the tribles they introduce, that checkout matches exactly the fresh facts added after a. Feeding that delta into pattern_changes! lets us ask, "What new matches did commit b introduce over a?"

The Checkout type makes this ergonomic: checkout(..) returns both the data and the commit set, so the next checkout(commits()..) produces exactly the delta without manual bookkeeping.

Trade-offs

• Applications must compute and supply the changed set; the engine does not track changes automatically.
• Queries must remain monotonic since deletions are ignored.
• Each triple incurs an extra variant, so highly selective constraints keep incremental evaluation efficient.
• Changed sets that grow unboundedly lose their advantage. Regularly draining or compacting the changeset keeps semi-naive evaluation responsive.

Regular Path Indexes

Regular path queries ask whether two graph terms are connected by a path whose edge labels are accepted by a finite automaton. TribleSpace keeps that recursive work outside the core query solver: the standalone triblespace-paths crate materializes the accepted endpoint relation, then exposes it as an ordinary two-variable Constraint.

This separation keeps query-time constraints stateless. The expensive fixpoint is built once per graph snapshot; find!, and!, constants, and the normal dynamic variable ordering then treat the result like any other relation.

Add the companion crate alongside the facade crate:

[dependencies]
triblespace = "0.47"
triblespace-paths = "0.47"

Describe the path, then materialize it

Most callers describe a regular path with PathExpr. Each leaf is a graph property Step; the expression builders add concatenation, alternatives, and repetition. compile freezes that description into the fixed, epsilon-free automaton consumed by PathIndex and PathRollup.

For example, friend+ means one or more forward friend edges:

use triblespace::prelude::*;
use triblespace::prelude::inlineencodings::GenId;
use triblespace_paths::{PathExpr, PathIndex, Step};

mod social {
    use triblespace::prelude::*;
    use triblespace::prelude::inlineencodings::{GenId, ShortString};

    attributes! {
        "A19EC1D9DD534BA9896223A457A6B9C9" as pub name: ShortString;
        "C21DE0AA5BA3446AB886C9640BA60244" as pub friend: GenId;
    }
}

let friend = social::friend.id().into();
let friend_plus = PathExpr::from(Step::Forward(friend)).plus();
let friend_automaton = friend_plus.compile();

let alice = fucid();
let bob = fucid();
let carol = fucid();
let mut graph = TribleSet::new();
graph += entity! { &alice @ social::friend: &bob };
graph += entity! { &bob @ social::friend: &carol, social::name: "Bob" };
graph += entity! { &carol @ social::name: "Carol" };

let paths = PathIndex::from_tribles(friend_automaton.clone(), graph.iter())?;

Every trible is viewed as a directed graph edge from its entity to its inline value, labeled by its attribute id. Values do not have to encode entity ids, although a path endpoint must use a compatible inline encoding when it shares a query variable with another constraint.

The expression operations are regular-language operations:

• a.then(b) matches a followed by b;
• a.or(b) matches either expression;
• star, plus, and optional mean zero-or-more, one-or-more, and zero-or-one repetitions; and
• inverse reverses the complete path. It flips each atomic step, reverses sequence order, distributes over alternatives, and preserves repetition.

Step::Forward and Step::Reverse match one exact attribute in either graph direction. ForwardExcept and ReverseExcept match every attribute except a provided list; an empty exclusion list is a wildcard, available as Step::forward_any() or Step::reverse_any(). Inverting an exclusion or wildcard changes only its direction.

Canonical expressions and compilation

PathExpr canonicalizes structure as it is assembled. Nested sequences are flattened while retaining their order. Nested alternatives are flattened, sorted by a stable explicit order, and deduplicated. Exclusion lists are also sorted and deduplicated. Thus independently assembled expressions that differ only by alternative ordering, duplicate alternatives, sequence association, or exclusion ordering compile to the same canonical automaton and fingerprint.

This is structural canonicalization, not regular-language minimization. Distributively equivalent expressions, or identities such as a nested star, may still compile to different language-equivalent automata. Do not use automaton equality to decide arbitrary regular-language equivalence.

Compilation uses the Glushkov position construction. State zero is the sole initial state, and each atomic Step occurrence contributes one additional state. First-position and follow-position relations become transitions; nullable expressions make state zero accepting. The result is a fixed NFA with no epsilon transitions and no determinization pass. Repetition changes the finite follow relation rather than unrolling an unbounded machine.

The current high-level surface is the Rust builder API, not a string parser or path! macro. Every PathExpr contains at least one atomic step, so a pure epsilon language or the empty language must be expressed with a manual automaton. State ids are u32; compile panics if the expression contains u32::MAX atomic occurrences, because no valid Automaton can represent it.

Manual automata are the low-level escape hatch

Construct Automaton directly when importing the output of another compiler, when a deliberately shared state topology matters, or when the language has no atomic step. The friend+ expression above is equivalent to this explicit two-state NFA:

use triblespace_paths::{Automaton, Step, Transition};

let friend_automaton = Automaton::new(
    2,
    [0],
    [1],
    [
        Transition::new(0, 1, Step::Forward(friend)),
        Transition::new(1, 1, Step::Forward(friend)),
    ],
)?;

Automaton::new validates state numbers and canonicalizes duplicate or out-of-order transitions and exclusion lists. Its input must already be epsilon-free. Represent nullability by making an initial state accepting; for example, one initial-and-accepting state with no transitions accepts only the empty path.

Join paths with ordinary constraints

PathIndex::constraint(start, end) creates the two-column relation. Either term may be a query variable or an inline constant, and using the same variable twice asks for the accepted diagonal. The relation composes directly with pattern! and every other constraint:

let alice_value: Inline<GenId> = (&alice).to_inline();

let reachable_people: Vec<(Id, String)> = find!(
    (person: Id, name: String),
    and!(
        paths.constraint(alice_value, person),
        pattern!(&graph, [{ ?person @ social::name: ?name }]),
    )
)
.collect();

The index also has direct read methods when no join is needed: contains, reachable_from, reaching, accepted_pairs, starts, ends, and diagonal. All endpoint fibers are sorted and duplicate-free. The path relation therefore contains one pair per accepted (start, end), not one row per distinct route between them; ordinary query joins can still introduce bag multiplicity through their other witnesses.

Keep the index current with a repository

For a durable branch, wrap the same automaton in a PathRollup and register it before the branch's first data push:

use triblespace_paths::PathRollup;

let rollup = PathRollup::new(friend_automaton);
repo.register_index(rollup.clone());

let branch_id = *repo.create_branch("main", None)?;
let mut ws = repo.pull(branch_id)?;
ws.commit(graph, "add social graph");
repo.push(&mut ws)?;

// Hook errors do not roll back the source commit. Surface or repair them
// before treating the derived index as current.
if let Some(failure) = repo.take_hook_errors().into_iter().next() {
    return Err(failure.error);
}

// Attachment reads the branch metadata directly; no checkout is required.
let paths = rollup.attach_exact(repo.storage_mut(), branch_id)?;

Repository::register_index installs an on-commit hook. Each newly reachable commit becomes one inclusive [commit, commit] logical range, even when the commit is contentless or produces no path artifact. The range record and the source branch head are published together in the same branch-metadata CAS. IndexHome applies base-FANOUT LSM compaction while appending those logical leaves.

Registration is not retrospective. Register before the first relevant push, or explicitly build and audit a covering manifest for existing history. If a hook fails, the source commit still lands and Repository::take_hook_errors records the failure; a later attach_exact then rejects the stale frontier rather than silently serving an old relation.

What a persisted summary means

The automaton is part of the recipe identity. Two PathRollups with different automata have different fingerprints, manifests, and range artifacts even when they cover the same commits.

Each nonempty range stores a canonical PathSummaryBlob containing only:

• the sorted endpoint domain required by the fixed automaton, and
• the sorted direct arcs of the graph × automaton product.

Those summaries are sparse constructional data, not independently closed path relations. Compaction is canonical set union. At attachment, PathRollup::attach_exact unions every live range summary and computes the accepted endpoint relation once over the whole union. That order is essential: one path may take its first edge from range A, its next edge from range B, and later re-enter A. Unioning closures built independently per range would miss such paths.

This design also makes merge order irrelevant. PathSummary::merge is associative, commutative, and idempotent for one fixed automaton; closure is derived only after the summaries have been combined.

Nullable paths and the vertex universe

A nullable expression uses an accepting initial state. Its zero-hop answers are the identity pairs (v, v) for the summary's complete vertex universe. The universe includes both endpoints of every supplied trible, even when that trible's attribute matches no automaton transition. Without those unmatched terms, a nullable index would incorrectly lose valid zero-hop answers.

Non-nullable summaries omit those unmatched endpoints entirely. Nullable summaries retain them as the identity universe, but the SCC and bitset closure still runs only over endpoints incident to matching product arcs; the index then maps that relation back into the full universe and adds the diagonal. Unrelated attributes therefore do not widen the quadratic closure workspace.

An entirely empty source has no graph terms and therefore no identity pairs. Its range still exists as a certified contentless record, but it has no PathSummaryBlob handle. “Covered and empty” is distinct from “not indexed.”

Freshness and the trust boundary

attach_exact reads the branch metadata pin, source commit head, and typed manifest from one snapshot. It checks that the manifest claims exactly that head and validates every summary's canonical bytes and automaton fingerprint. A mismatch fails with IndexError::StaleCoverage or an artifact error.

The hot attachment path intentionally does not walk the full commit DAG to prove that all manifest ranges form an exact cover. Metadata produced by Repository::register_index earns that trust through its monotone, same-CAS maintenance path. For imported, manually assembled, or otherwise untrusted metadata, read the IndexHome snapshot and call Manifest::audit_exact_cover against a blob reader before trusting it, or rebuild the manifest. See Range-Native Derived Indexes for the inclusive frontier and exact-cover rules.

Cost model: sparse input, potentially dense answer

Range summaries retain an endpoint domain and direct product arcs, so they can remain close to the sparse input and merge cheaply. Attachment is a different operation: it materializes the complete accepted endpoint relation as CSR plus reverse and domain views. Some regular paths accept every pair of vertices, making that relation Θ(|V|²). No exact materialized representation can avoid paying for that output, and the closure construction also uses bitset scratch space.

The current canonical blob stores product endpoints as full-domain u32 ordinals. Persisted nullable summaries consequently require |universe| × |automaton states| <= u32::MAX, even though attachment closes only the smaller matched support. Crossing that format ceiling is an explicit error rather than ordinal truncation.

Use a PathRollup when the automaton is stable and many queries will amortize attachment, or when fast membership and joins matter. For a one-off traversal on a large sparse graph, an application-side graph search may use less memory; for a fixed small number of hops, explicit pattern! clauses remain the simplest answer. The path index is a deliberate materialized-view trade, not a hidden lazy traversal.

Query Engine

Queries describe the patterns you want to retrieve. There is no query planner and no compiled plan. Every operator and every data source implements the same Constraint protocol, and the engine consults those constraints while it searches, so binding order is chosen from the values already found instead of being fixed before evaluation.

This chapter describes that protocol, the search that drives it, the result semantics that fall out of both, and — just as importantly — the things the engine deliberately refuses to do. The refusals are load-bearing: each one is what buys a property the engine does provide.

The constraint protocol

A constraint restricts the values that query variables may take. It is not a node in a plan; it is a participant the engine interrogates. The whole interface is six methods, and the engine calls them in a fixed rhythm:

estimate returns None for a variable the constraint does not touch, which is how "irrelevant" is distinguished from "unknown cost". An estimate is a cost quote and nothing else: it steers variable ordering, never correctness. A constraint that lies about its cardinality makes the search slower, not wrong. Whether the answer is Some or None must depend only on which variables are bound, never on their values — a batch shares one bound set, and composites read relevance off the batch.

Only four of the six need an implementation: satisfied defaults to true and influence defaults to "every variable I touch except this one". A new data source therefore joins the engine with variables, estimate, propose, and confirm — iteration and point queries, nothing more. That minimum is what keeps hash maps, PATCHes, succinct archives and device-resident structures all admissible; a seek or leapfrog requirement would disqualify half of them.

Composition is by two constraints rather than by an algebra: IntersectionConstraint (built by and!) and UnionConstraint (built by or!). Both are ordinary constraints implementing the same six methods, so a TribleSet pattern, a HashSet membership test, and an application predicate mix in one query without any of them knowing about the others.

Propose and confirm take a batch

propose and confirm do not take one binding. They take a Frontier: the whole collection of parent bindings sitting at one point of the search. A single binding is a frontier of one, which is exactly the older single-binding protocol.

The reason is measured. With a width-1 frontier only the root level ever proposes widely; every deeper level asks a source for the candidates of one parent, and over real data (a region-size census on dblp) that is a median of 1–7 candidates at every scale, p95 around 200. Any batched tier — a GPU dispatch that pays off at 16 384 candidates, a SIMD probe — therefore engaged once at the root and never again. Batching the parents is what makes a level's region large at every depth.

A frontier is cheap because bindings are indexes, not values (see below): it is an index matrix over the shared level buffers plus a select list of row numbers, so restricting one to a subset costs four bytes per row and never copies a row. Correspondingly, the ProposalBuffer is segmented: a proposer calls open(row) before appending a row's candidates, and every entry carries that parent tag. Candidates exposes the tags, so one region can span a whole batch and a confirmer can still tell whose each candidate is.

Sources split cleanly along that seam. A verdict that does not depend on the parent binding — set membership, a byte range, a constant — ignores the tags and filters the whole region in one pass. One that does walks the region with Candidates::for_each_parent, which yields maximal runs of equal tag, so a per-binding setup is paid once per run instead of once per candidate.

Nothing about the batch changes what the query means. Worst-case optimality is untouched — expanding n prefixes together is the same total work as expanding them one at a time, and the AGM bound is a statement about output size, not traversal order. The cost is frontier memory, O(width × variables × depth): depth-first's O(depth) frontier traded for a wide one.

Statelessness is the load-bearing choice

Every method receives the current Binding — or a batch of them — as a parameter. A constraint keeps no cursor, no half-finished enumeration, no record of where the search has been.

That single decision pays for most of the engine's structure:

• Backtracking is free. The engine unsets a variable in the binding and moves on. There is nothing to notify, unwind, or roll back, because no constraint holds state that could be stale.
• The constraint tree can be cloned. Parallel execution splits by cloning the engine's state; the constraint tree is shared behind an Arc. If constraints held live iterators, a split would have to duplicate or hand off those iterators, and a borrowed enumeration would tie the constraint's lifetime to the engine's — the self-referential trap that a stateful protocol cannot avoid.
• A level is proposed once. Because no source is ever asked to resume, a level's buffer is written exactly once and never appended to while its variable is bound. That makes "a bound variable's buffer is stable for the lifetime of its binding" an unconditional invariant, which is what lets a binding be an index into that buffer instead of a copy of the value.

Depth-first search with dynamic variable ordering

The ordering is the engine's core performance idea, not an implementation detail.

Query::new asks every variable for an estimate against the empty binding. Then the search repeats one step, over a whole frontier at a time:

1. For each row of the frontier, pick its most specific unbound variable from that row's own estimates.
2. Partition the frontier by that choice and take the next group.
3. Ask the constraint tree to propose candidates for the group's variable, over all of the group's rows in one call. An intersection internally lets each row's tightest child propose and runs the remaining children as confirmers over that output, so the buffer the engine sees has already survived every clause.
4. Turn the next chunk of surviving candidates into the child frontier and descend. Each child row inherits its parent's estimates and refreshes exactly the ones the new binding could have changed — the influence set of the variable just bound.
5. When a level runs out of live candidates, retire it and continue with the next group, then with the next chunk one level up.

The width is a ceiling, and the frontier ramps from one row

DEFAULT_FRONTIER_WIDTH is how wide a chunk may get, not how wide the first one is. A level's first chunk is INITIAL_FRONTIER_WIDTH = 1 binding. Later chunks multiply by FRONTIER_RAMP_BASE = 8 until they reach the ceiling. If the final remainder would be smaller than the chunk before it, the engine merges that tail early; the caller's ceiling remains a hard bound.

That is what keeps time-to-first-result honest. A caller who stops after one row — exists!, .next() — must not pay to build a 16 384-wide frontier it will never look at, and with a first chunk of one it does exactly the work the single-binding engine did. Measured on a first-row-only join, a flat full-width engine is 8.8x slower than the pre-batching engine; one narrow chunk closes the entire gap.

The base is the latency/throughput trade, not an incidental tuning detail. A base-2 ramp was measured and rejected: its last chunk is only about half a drain, so it cut a fixture's useful frontier from 2048 rows to 512 and raised expansions from 3 to 74. The failure was the base, not geometric growth. At base 8, the last term is asymptotically seven eighths of the drain and a 16 384 ceiling takes six rungs rather than doubling's fifteen. Across the 100-query registry on three backings, base 8 retained 99.61% of aggregate widest-frontier width and 93.30% of GPU-routed candidate work (against 97.46% for the flat schedule), at 44.7% more expansions. It therefore keeps almost all useful batch width while avoiding the flat schedule's enormous overshoot for callers that want only a handful of rows. The first row is protected exactly; larger short demands pay at most the next base-8 rung.

A 1:1 descent copies nothing

Step 4 normally builds the child frontier by copying each drawn candidate's parent row and filling in the newly bound slot. When the draw is 1:1 — one surviving child per parent row, in order, covering the whole frontier, with nothing left pending — that copy is pure waste: no row was gained, lost or reordered, so the child block is the parent block with one more slot written, and the child's estimate rows are bit-identical to the parent's.

The two standing invariants are what make it sound. Confirmers may only kill candidates, never revive them, so a surviving row keeps its identity. Buffers are write-once, so the newly bound variable's slot in every row was previously unwritten and filling it destroys nothing. And because such a draw leaves the level spent, the parent frontier is never asked for anything again, so its matrices are handed down rather than shared — which is what lets a whole chain of 1:1 descents run without a single matrix copy instead of only the first one.

Ownership needs no separate flag. The matrices already sit behind Arc so a rayon split copies refcounts, and Arc::get_mut therefore succeeds exactly when no split or steal holds the other half; when it says no, the copying path runs. FrontierStats counts both paths.

The fast path is gated so that it costs nothing when it cannot fire. Recognising a 1:1 draw means deferring the child rows until the draw's shape is known, and that deferral is a second pass — measured at +10% and +20% on two fixtures when charged to every descent. So the engine asks first, from what it already knows: a level holding proposed candidates for rows parents can only yield one child per parent if proposed == rows. Every fan-out level fails that O(1) test and runs the fused single-pass build exactly as before.

This matters most for the shape batching can never help: a chain with fan-out one at every level has no sibling parents to widen the frontier with, so it can only ever be charged for the machinery. Removing the per-level row copy is what brings it back to the single-binding engine's cost.

A row is never moved onto a variable it did not choose, however tempting that is for batch size. propose owns candidate support and first-seen order, and the protocol supplies no cross-variable support-equivalence law, so an estimate-compatible variable is not an interchangeable action. All the leeway lives in the bucketing described next — which is exactly why agreement, and so an unsplit batch, is the common case. FrontierStats counts expansions, rows and groups, so fragmentation is observed rather than assumed.

Specificity is deliberately coarse. The sort key is the bit length of the estimate (ilog2(n) + 1), so counts inside the same power-of-two bucket are treated as equally specific; the tie-break then prefers the variable with the largest influence set — the one whose binding will sharpen the most other estimates. Two effects follow. Small differences between two sources' guesses cannot flip the order, which keeps the search stable when estimates are rough. And when the engine genuinely cannot tell two variables apart on cardinality, it picks the one that buys the most information.

Re-sorting on every step is what makes the ordering dynamic. A planner chooses one order from global statistics and lives with it for the whole query; here each level chooses from the estimates under the current partial binding. On skewed data this is the difference between a good average and a good worst case: the popular entity and the rare one take different paths through the same query, because after binding an entity the remaining estimates are no longer the same numbers. Nothing is cached, so nothing has to be invalidated. See the Atreides Join chapter for how estimate fidelity ranks and why this is worst-case optimal.

Proposals: one write-once buffer per level

propose writes into a ProposalBuffer — the engine's candidate store for one variable at one level. Entries are plain 32-byte RawInline values at fixed stride. Alongside them the buffer keeps a liveness bit per entry, packed 32 to a u32, and a u32 parent tag naming the frontier row the entry was proposed for.

Entries are effectively write-once. A proposer may rewrite the region it appended in the current call before it returns — that is how a union applies its sort-dedup — but once the caller can see the region, the indices are frozen, because kills bind to them.

Nothing is ever compacted. A candidate that fails confirmation has its liveness bit cleared and stays exactly where it was; the engine iterates the live entries. That costs a scan over dead entries and buys two things: an entry's index is stable for the lifetime of the level, so a kill can be recorded by index alone, and no confirmer ever has to agree with another about where a candidate now lives.

Packing liveness 32 to a word is what makes that scan cheap: count_live and next_live fold whole words through count_ones and trailing_zeros rather than looking at candidates one at a time. Two things get harder in exchange, and both are paid for inside the buffer's own module. A kill becomes a read-modify-write on a word shared with 31 neighbours. And a region no longer starts on a word boundary — nor does a per-parent run inside one — so its first and last words carry liveness bits owned by neighbouring regions of the same buffer. The invariant is enforced at the boundary of the type: every write path masks to the owned bits and every read path zeroes the bits it does not own, so no caller — the device confirm path included, see below — can reach a neighbour's liveness.

Confirmation is kill-only

Candidates is the region handed to confirm: values are read-only, liveness words are killable, and there is no way to revive an entry or add one.

That restriction is the whole reason confirmation needs no coordination. If a confirmer can only remove, then several confirmers writing into the same region compute their conjunction no matter how they are scheduled:

• Sequentially, each skipping entries that are already dead — the CPU path.
• In parallel, each on its own copy of the liveness words, merged with and_words — the path a batching accelerator takes.

Both schedules are legal, produce identical liveness, and the engine does not have to choose between them ahead of time. A union inverts the merge: it runs each live arm on a scratch copy and combines with or_words, so a value survives if any arm accepts it.

This is also what makes an accelerator safe to bolt on. A device that computes verdicts for a whole region cannot corrupt the search, because the only thing it can do with its answer is clear bits that the CPU would also have cleared.

What the engine refuses: resumable narrowing

An earlier design let a source deliver a level in geometrically growing chunks through a resumable cursor, so a level with a million candidates would not have to materialize a million before the engine could try the first one. It is gone, and the reasons are worth recording because the idea recurs.

It was never adopted by a single leaf source, so the machinery only ever ran its own default. It answers a time-to-first-result question that a pure conjunctive query does not ask — depth-first already yields the instant the stack bottoms out, and the measurement bore that out (0.004 ms against 0.017 ms for the design it was meant to improve). And its one real case, a wide root, is a lottery on iteration order rather than a saving: chunking helps only if the surviving candidates happen to sort early.

What did survive is the geometric part. The deleted cursor carried an INITIAL_CHUNK/WIDEN_FACTOR pair, and the residual engine before it grew its search width geometrically after negative work; both are the same idea, and both were attached to the wrong object. Attached to a level, growth asks a source to resume. Attached to the frontier, it asks nothing of anyone — the engine already owns how many parent rows it expands at a time, so INITIAL_FRONTIER_WIDTH and FRONTIER_RAMP_BASE buy the time-to-first-result property the cursor was reaching for with none of its protocol cost.

Narrowing a wide level is still a real problem; galloping intersection is the standing candidate for it. What the engine will not do is require a seek from sources, because that requirement is what would disqualify half of them.

Parallel execution

With the parallel feature a query is also a rayon producer: find!(...).into_par_iter(). There is no second solver behind it. Splitting walks the same state machine and transfers a whole frontier unit to a sibling:

• Once planning has partitioned a frontier by the rows' preferred next variable, one complete group may be transferred. The left producer advances its group cursor; the sibling is re-rooted at that frontier and fenced to the single group it received. Both share the immutable plan and frontier matrices behind Arc; proposal buffers are not divided.
• A published proposal buffer is immutable, so sibling binding stores share it behind Arc and copy only their consumption cursors. If one sibling later refills that variable, it installs a fresh empty buffer before proposing; the other sibling's indexes keep resolving through the old snapshot. A uniquely owned buffer keeps and reuses its allocation.
• A complete terminal page may likewise be transferred as one unit. This is how a one-variable query can expose parallel work without slicing its result frontier.
• A transfer is admitted only when the left producer has a distinct future: another group at this frontier, or an ancestor level with an unconsumed candidate suffix. A sole group or page with no such continuation stays in place and the producer descends serially; that descent may expose genuinely independent groups deeper in the search.
• The sibling owns no ancestor continuation. Once its fenced group or page is exhausted it ends instead of unwinding into work still owned by the left producer.
• Geometric pages and preferred-variable groups therefore remain intact. A split never turns one accelerator-sized proposal/confirmation batch into two smaller batches merely to feed rayon.
• A leaf just drives the ordinary sequential Iterator::next and folds the results. No engine logic is duplicated for the parallel path.

The ownership rule is itself the split bound: every successful split removes one group or page from the left producer and fences it into the right. Work cannot be handed back or rediscovered, so rayon's pressure splitter needs no engine-specific budget or thread-count tuning knob.

The guarantee is the same bag of rows, not the same order. Constraint trees are shared behind an Arc, so a split is a refcount bump rather than a tree clone; code that wants aggregate observations across shards needs its own synchronization (an Arc<AtomicU64>, say) because clone-local interior state is not a global counter.

Bag semantics at the interface

The engine emits one row per complete binding. When the unbound set empties, that assignment is a result. Nothing deduplicates it.

Hidden variables therefore surface as multiplicity. If an entity has n outgoing edges and a query projects only the entity while a temp! or _? variable ranges over the target, that entity is emitted n times:

#![allow(unused)]
fn main() {
use std::collections::HashSet;

use triblespace::prelude::*;

mod social {
    use triblespace::prelude::*;
    attributes! {
        "C21DE0AA5BA3446AB886C9640BA60244" as friend: inlineencodings::GenId;
    }
}

let mut kb = TribleSet::new();
let alice = ufoid();
let bob = ufoid();
let carol = ufoid();
kb += entity! { &alice @ social::friend: &bob };
kb += entity! { &alice @ social::friend: &carol };

// One row per complete binding: the hidden `_?friend` multiplies `?person`.
let rows: Vec<_> = find!(
    (person: Id),
    pattern!(&kb, [{ ?person @ social::friend: _?friend }])
)
.collect();
assert_eq!(rows.len(), 2);

// Deduplication is the consumer's job.
let distinct: HashSet<_> = find!(
    (person: Id),
    pattern!(&kb, [{ ?person @ social::friend: _?friend }])
)
.collect();
assert_eq!(distinct.len(), 1);
}

This replaced an engine that projected with SET semantics. That engine kept a claims table: an ordered key derived from the head's raw bytes, claimed before conversion, so a second binding with the same public identity was discarded. It was removed because the cost was structural rather than incidental. The table's memory grows with the result set, not with the query; under rayon the claim domain has to be shared across workers, which puts a synchronization point on the hot path of an otherwise share-nothing search; and once user code runs behind a claim, a conversion failure or a panic consumes the key, so another witness cannot retry it — a rule that is difficult to explain and easy to trip over. Worst of all, the multiplicity is genuine information about the data, and the engine was throwing it away on the way out.

Bag semantics is not the absence of a feature so much as the decision about where the feature belongs. Two idioms cover what the claims table used to do:

• Collect into a set. HashSet<_> (or BTreeSet<_>) after find! costs memory proportional to the distinct results — the same memory the claims table cost — but only when the caller actually wants it, and it deduplicates on the converted Rust values rather than on raw bytes.
• Two queries. Enumerate the outer variable, and use exists! for the inner condition. exists! stops at the first witness, so the fan-out is never enumerated at all. This is usually the faster answer, and it is the one that reads like the question being asked: "entities that have a friend", not "entities paired with a friend, deduplicated".

The unit head follows the same rule rather than getting an exception: find!((), constraint) yields one () per satisfying assignment. Use exists! when the question is existence.

Note that or! is a genuine exception at the binding step, not at the interface: a union sorts and deduplicates the candidate values it proposes for a single variable, so two arms that offer the same value for the same variable contribute one candidate, not two. That is a property of the candidate buffer for one level, and it does not extend to complete rows — the same alias witnessed by two different entities is still two rows.

Constants live below the variable layer

A pattern position is a Term: either a Var the engine solves for, or a Const pinned at construction. The macro layer folds attribute constants, literal values, and constant entity ids into Const terms.

Constants never enter a Binding, are never proposed, and are excluded from variables(). They behave exactly like a variable that was already bound — RawTerm::position_value returns the pinned value where it would return the binding's value — so every backend's bound/unbound dispatch handles them with no extra match arms.

Keeping them below the variable layer is what makes or! usable. Every arm of a union must declare the same variable set, because the result schema is flat: one row binds one variable set exactly once, so a variable that only exists in some alternatives has nowhere to live. If a literal allocated a hidden variable, then two arms matching different attributes would declare different sets and the union would be rejected at construction — which was exactly the symptom before constants became Term-native. As folded constants they cost no variable, so an arm on profile::nickname and an arm on profile::display_name declare the identical set and compose.

Two more consequences fall out. Literals do not consume the 128-variable budget, so a pattern with 161 constants allocates zero variables. And a pattern whose positions are all constant has an empty variable set, which the search would never visit — so Query::new settles it once, up front, with a single satisfied call against the empty binding. This is why satisfied must be exact once every variable it touches is bound: for a constant subtree there is no variable through which the search could later discover failure.

Where the GPU fits

The optional triblespace-gpu crate accelerates one operation: WgpuSuccinctArchive keeps a succinct archive's value universe, per-axis occupancy boundaries, and six Jerky wavelet matrices resident on the device, and routes a confirm region to a kernel when it has at least DEFAULT_MIN_CONFIRM_BATCH live candidates.

It is not a second engine and not a planner. Estimates, proposals, prefix walks, and satisfaction checks stay on the CPU; a region below the threshold and any device error fall through to the canonical CPU arm, which the crate's parity suite holds to identical liveness words. The substitution is legal precisely because of the kill-only contract: verdicts computed anywhere merge back by word-wise AND, and a device can never revive a dead entry.

The packed liveness layout shapes how a kernel writes its verdicts. The flat index of a verdict kernel is the bit position in the region's liveness words — so candidate i sits at bit bit_offset + i — and one plane_ballot per 32-lane plane produces a whole packed verdict word with every bit already in place, stored by a single lane. No rotation, no read-modify-write, no atomic. The AND and the write-back are ordinary word operations, because the device works on a private copy taken through live_words() and merged through set_live_words(), and those two mask the neighbouring regions' bits out and back in. The kernel needs one device property for this — planes exactly 32 lanes wide — which the host checks before dispatching, demoting to the CPU arm if it does not hold.

The threshold is measured, not guessed. On an Apple M4 Max (Metal via wgpu), against a 262,135-trible archive with fully live regions, the GPU round trip is nearly flat at ~1.4–2.2 ms while CPU cost scales linearly — putting the crossover near 8k live candidates for the range shape (two wavelet ranks per candidate) and near 22k for the lighter membership shape. 16,384 is the single-knob compromise between them; the full crossover table lives in the constant's doc comment. WgpuSuccinctArchive::stats exposes dispatch and fallback counters, so the routing economics stay observable instead of being hidden inside a heuristic.

Where regular paths went

Regular path queries — "everyone reachable through a chain of follows", "all ancestors via repeated parent" — are no longer part of the engine. The path! macro and its query-time evaluator have been removed.

The reason is the stateless protocol. A triple pattern is a relation over a fixed set of variables, and the engine can ask it for candidates under any binding. A regular path is an automaton product traversal: evaluating it inside the search needs per-activation state — where the frontier is, which automaton branch produced which value, what has already been visited — and that state belongs to one live traversal, not to a binding the engine can hand back later. Every attempt to keep it inside the protocol grew the protocol, and the growth did not stay confined to paths: pager hooks, activation receipts, and novelty keys became things every constraint had to reason about, including the ones that only ever wanted to answer "is this triple present".

So paths moved out of query time entirely. The replacement is a materialized closure index: compile the graph edges and an epsilon-free automaton into a product graph and maintain its reflexive transitive closure, then let queries read the closure as an ordinary relation. Reachability becomes a lookup rather than a traversal, which is the right shape for a data model where facts are only ever added — the closure grows monotonically with the edge set.

The stable implementation lives in the standalone triblespace-paths crate. Its PathExpr builder compiles the normal regular-language operations into a fixed epsilon-free automaton; direct Automaton construction remains the low-level escape hatch. The crate persists unionable direct-product summaries per repository range, closes their global union, and exposes the resulting endpoint relation through the ordinary two-variable constraint protocol. See Regular Path Indexes for the expression API, lifecycle, freshness boundary, and dense-output trade-off.

What the engine will not do

Four refusals, and what each one buys:

• No cost-based optimizer. There is no plan to compile, no statistics to collect, no cardinality model to keep calibrated, and no plan cache to invalidate. What replaces it is the per-step ordering above, which sees the actual partial binding instead of a summary of the data. The cost is that a genuinely bad estimate cannot be corrected by anything but a better estimate; the benefit is that adding a data source means implementing four methods, not teaching a planner about a new operator.
• No negation. There is no MINUS, no FILTER NOT EXISTS, no OPTIONAL. This is a data-model decision reaching up into the engine: the trible model is monotonic, and a non-monotonic operator would make a query's answer depend on facts not being present — which stops being a stable statement the moment another replica merges in. Monotonicity is what makes pattern_changes! sound, what makes distributed merge coordination-free, and what makes a query result something you can still believe after a pull.
• No query-time recursion. See the section above. Recursion returns as a maintained index, where the fixpoint is computed once against the data rather than repeatedly inside every search.
• No projection dedup. Covered above: the multiplicity is real, the deduplication has a cost, and the consumer is the one who knows whether it wants to pay it.

What the engine does provide in exchange is a short list, but a durable one: predictable latency, skew resistance, no tuning knobs, and one protocol that a TribleSet, a compressed on-disk archive, a HashSet, a search index, and an application predicate all speak equally well.

Queries as Schemas

You might notice that trible.space does not define a global ontology or schema beyond associating attributes with a InlineEncoding or BlobEncoding. This is deliberate. The semantic web taught us that per-value typing, while desirable, was awkward in RDF: literal datatypes are optional, custom types need globally scoped IRIs and there is no enforcement, so most data degenerates into untyped strings. Trying to regain structure through global ontologies and class hierarchies made schemas rigid and reasoning computationally infeasible. Real-world data often arrives with missing, duplicate or additional fields, which clashes with these global, class-based constraints.

Our approach is to be sympathetic to edge cases and have the system deal only with the data it declares capable of handling. These application-specific schema declarations are exactly the shapes and constraints expressed by our queries¹. Data not conforming to these queries is simply ignored by definition, as a query only returns data satisfying its constraints.²

Join Strategy

The query engine uses the Atreides family of worst-case optimal join algorithms. These algorithms leverage the same cardinality estimates surfaced through Constraint::estimate to guide variable choice over partial bindings, providing skew-resistant and predictable performance. Estimates are recomputed from the current binding rather than cached, so there is no invalidation protocol and no separate planning artifact to maintain. For a detailed discussion, see the Atreides Join chapter.

Query Languages

Instead of a single query language, the engine exposes small composable constraints that combine with logical operators such as and and or. These constraints are simple yet flexible, enabling a wide variety of operators while still allowing the engine to explore the search space efficiently.

The query engine and data model are flexible enough to support many query styles, including graph, relational and document-oriented queries. Constraints may originate from the database itself (such as attribute lookups), from custom application logic, or from entirely external sources.

For example, the pattern! and entity! macros—available at the crate root and re-exported via triblespace::prelude (for instance with use triblespace::prelude::*;)—generate constraints for a given trible pattern in a query-by-example style reminiscent of SPARQL or GraphQL but tailored to a document-graph data model. It would also be possible to layer a property-graph language like Cypher or a relational language like Datalog on top of the engine.³

use std::collections::HashSet;

use triblespace::core::examples::literature;
use triblespace::core::query::ContainsConstraint;
use triblespace::prelude::*;
use triblespace::prelude::inlineencodings::ShortString;

fn main() {
    let mut kb = TribleSet::new();

    let author = ufoid();
    let book = ufoid();

    kb += entity! { &author @
        literature::firstname: "Frank",
        literature::lastname: "Herbert",
    };
    kb += entity! { &book @
        literature::author: &author,
        literature::title: "Dune",
    };

    let mut allowed = HashSet::<Inline<ShortString>>::new();
    allowed.insert("Frank".to_inline());

    let results: Vec<_> = find!((title: Inline<_>, firstname: Inline<_>),
        and!(
            allowed.has(firstname),
            pattern!(&kb, [{
                _?person @
                    literature::firstname: ?firstname,
                    literature::lastname: "Herbert",
            }, {
                literature::author: _?person,
                literature::title: ?title,
            }])
        )
    )
    .collect();

    assert_eq!(results.len(), 1);
    assert_eq!(results[0].0, "Dune".to_inline());
}

The snippet above demonstrates how typed attribute constraints, user-defined predicates (the HashSet::has filter), and reusable namespaces can mix seamlessly within a single query.

Great care has been taken to ensure that query languages with different styles and semantics can coexist and even be mixed with other languages and data models within the same query. For practical examples of the current facilities, see the Query Language chapter.

The Atreides Family of Worst-case Optimal Join Algorithms

The query engine reasons about data by solving a set of constraints over variables. Instead of constructing a traditional left-deep or bushy join plan, it performs a guided depth-first search that binds one variable at a time. The approach draws on the broader theory of worst-case optimal joins and lets us navigate the search space directly rather than materialising intermediate results.

Constraints as the search frontier

Every constraint implements the Constraint trait, whose methods shape the search:

1. variables – returns the set of variables this constraint touches.
2. estimate – predicts how many candidates remain for a variable under the current partial binding, or None when the variable is not this constraint's business.
3. propose – enumerates candidate values for a variable, for every binding in the current frontier.
4. confirm – kills candidates proposed by another constraint, without re-enumerating them.
5. satisfied – returns false when the constraint has no completion from the current binding. Used by UnionConstraint to prune dead variants.

Traditional databases rely on a query planner to combine statistics into a join plan. Atreides instead consults the constraints directly while it searches. Each constraint can base its estimates on whatever structure it maintains—hash maps, precomputed counts, or even constant values for predicates that admit at most one match—so long as it can provide a quick cost quote. Every binding decision asks for fresh estimates under the binding that exists at that moment. Nothing is cached, so there is no invalidation protocol to get wrong.

An estimate affects cost ordering only. It cannot change whether a constraint is relevant, which candidates it proposes, or which rows the query returns. A constraint that misreports its cardinality by a large factor makes the search slower; it does not make it wrong.

Because the heuristics are derived entirely from the constraints themselves, we do not need a separate query planner or multiple join implementations. Any custom constraint can participate in the same search by providing sensible estimates, proposal generation, and confirmation.

A spectrum of Atreides variants

The Atreides "family" refers to the spectrum of heuristics a constraint can use when implementing Constraint::estimate. Each variant exposes the same guided depth-first search, but with progressively tighter cardinality guidance. Every binding decision revisits its estimates; what differs is what quantity they approximate:

• Row-count Join (Jessica) estimates the remaining search volume for the entire constraint. If one variable is bound but two others are not, Jessica multiplies the candidate counts for the unbound pair (|b| × |c|) and reports that larger product. The number can wildly overshoot the next variable's frontier, yet it often tracks the overall work the constraint will perform.
• Distinct-value Join (Paul) narrows the focus to a single variable at a time. It returns the smallest proposal buffer the constraint could produce for any still-unbound variable, ignoring later confirmation filters. This is the behaviour exercised by Query::new today, which keeps the tightest candidate list on hand while the search walks forward.
• Partial-binding Join (Ghanima) goes further by measuring the size of the actual proposal the composite constraint can deliver for the current binding and chosen variable. For an and constraint this corresponds to the intersection of its children after they have applied their own filtering, revealing how many candidates truly survive the local checks.
• Exact-result Join (Leto) is an idealised limit where a constraint predicts how many of those proposed values extend all the way to full results once the remaining variables are also bound. Although no constraint currently achieves this omniscience, the interface supports it conceptually.

All four share the same implementation machinery; the difference lies in how aggressively estimate compresses the constraint's knowledge. Even when only partial information is available the search still functions, but better estimates steer the traversal directly toward the surviving tuples.

Every constraint can decide which rung of this ladder it occupies. Simple wrappers that only track total counts behave like Jessica, those that surface their tightest per-variable proposals behave like Paul, and structures capable of intersecting their children on the fly approach Ghanima's accuracy. The engine does not need to know which variant it is running—estimate supplies whatever fidelity the data structure can provide.

Guided depth-first search

At query start, Query::new asks every variable for an estimate against the empty binding, settles any constraint that is already fully determined by its constants, and orders the unbound variables. The solver then repeats one negotiation per binding:

1. Refresh the estimates that the most recent binding could have disturbed — the influence sets of the variables bound since the last refresh, minus the ones already bound.
2. Re-sort the unbound variables and take the most specific one. The ordering is by candidate-count bit length (smaller first), so counts in the same power-of-two bucket are deliberately treated as equally specific; ties go to the variable that influences the most others.
3. Ask the constraint tree to propose for that variable. An intersection lets its tightest child propose and runs the remaining children as confirmers over that child's output, most selective first, so what reaches the engine has already survived every clause.
4. Bind the first surviving candidate and descend.
5. When a level's candidates are exhausted, unbind the variable, return it to the unbound set, and continue one level up.

Traditional databases rely on sorted indexes to make the above iteration tractable. Atreides still performs random lookups when confirming each candidate, but the cardinality hints let it enumerate the most selective constraint sequentially and probe only a handful of values in the wider ones. Because the search is depth-first, the memory footprint stays small and the engine can stream results as soon as they are found.

Consider a query that relates ?person to ?parent and ?city. The search begins with all three variables unbound. If ?city only has a handful of possibilities, its estimate will be the smallest, so the engine binds ?city first. Each city candidate is checked against the parent and person constraints before the search continues, quickly rejecting infeasible branches before the higher-cardinality relationships are explored.

Per-variable estimates in practice

Suppose we want to answer the following query:

(find [?person ?parent ?city]
  [?person :lives-in ?city]
  [?person :parent ?parent]
  [?parent :lives-in ?city])

There are three variables and three constraints. Every constraint can provide a cardinality hint for each variable it touches, and the combined query records the tightest estimate for each variable:

The estimates are scoped to individual variables even when no single constraint covers the whole tuple. The engine chooses the variable with the tightest bound, ?parent, and asks the constraints that mention it for proposals. Each candidate parent immediately passes through the ?parent :lives-in ?city constraint, which usually narrows the possible cities to a handful. Those cities, in turn, constrain the possible ?person bindings. If a branch fails — for example because no child of the selected parent lives in the same city — the engine backtracks and tries the next parent. The smallest estimated constraints therefore guide the search towards promising combinations and keep the depth-first traversal from thrashing through unrelated values.

Implementation notes

• The search state is a stack of row frontiers over reusable per-variable candidate buffers. Retiring a frontier unsets its variable and pops; because constraints are stateless, nothing has to be notified or unwound.
• Constraints propose a complete candidate region for each parent batch; they do not implement cursors or seek. The engine resumably consumes its own buffer into child frontiers whose width ramps through 1, 8, 64, 512, … up to the query ceiling. This protects the first result from batching overhead while still presenting accelerators with wide regions deeper in the search.
• Highly skewed data still behaves predictably: even if one attribute dominates the dataset, the other constraints continue to bound the search space tightly and prevent runaway exploration. This is the payoff of re-estimating per binding rather than once per query — the popular entity and the rare one take different orders through the same query text.
• A uniquely owned per-variable proposal buffer is reused across sibling levels, so ordinary backtracking does not reallocate. Rayon clones share a published buffer immutably and keep independent cursors; the first clone to refill that slot installs a fresh buffer rather than copying data it will immediately clear.
• Under the parallel feature the same state machine is the rayon producer: splitting transfers one whole preferred-variable group (or terminal page) to a fenced sibling only when the left side retains another continuation. Candidate regions and geometric frontier pages stay intact. Results are the same bag of rows in an unspecified order.

Why worst-case optimal?

"Worst-case optimal" does not mean output size plus a constant factor: a query with an empty result may still need to inspect substantial input. It means matching, up to implementation and logarithmic factors, the worst-case output bound implied by the input relation cardinalities (the AGM/fractional-edge-cover bound), rather than materialising pairwise intermediates that can be asymptotically larger.

The Atreides family follows the generic-join shape behind that result: choose a variable, let the tightest participating constraint enumerate its possible values, and intersect those values through the other constraints before descending. Dynamic cardinality estimates choose among valid variable orders; they improve the realised work on skewed data, while the propose/confirm intersection is the part that avoids oversized binary-join intermediates. The precise guarantee still depends on participating constraints providing complete proposals and sound confirmations—the scheduler cannot manufacture those laws for an arbitrary custom data source.

This combination of simple heuristics, incremental estimates, and a disciplined search strategy keeps the implementation straightforward while delivering the performance characteristics we need for real-world workloads.

The Type Algebra of TribleSpace

Queries as Types, Data as Proofs

TribleSpace grew out of a pragmatic goal: keep data declarative, composable, and statically checkable in Rust. Along the way we discovered that the core operations already form a type algebra. The macros used to define attributes, entities, and queries map directly onto familiar type-theoretic constructions, yielding an isomorphism between relations over triples and types over records.

Attributes Introduce Atomic Types

Each attribute introduced with attributes! defines an atomic type — a unary relation between an entity identifier and the attribute’s value:

"A74AA..." as pub title : ShortString

Formally this is a function title : Id → ValueTitle, or, in relational terms, the set { (id, value) }. In the codebase the macro emits a static LazyLock<Attribute<S>> for each declared attribute, so the generated binding already carries the InlineEncoding that governs the value column. The derived form (omit the hex id) hashes the attribute name together with the schema metadata via the entity-core mechanism — equivalent to Attribute::<S>::named(name) — which is convenient for quick experiments; shared protocols should still pin explicit ids so collaborators and other languages read the same column. These atomic pieces are the building blocks for everything else.

Entities as Intersection Types

An entity! expression forms a record type by intersecting atomic ones. Semantically it is the meet (∧) of its constituent relations:

Entity{A, B}  ≡  { A : ValueA } ∧ { B : ValueB }

At runtime entity! expands to a small Fragment: exported entity ids, a TribleSet containing the asserted facts, descriptive metafacts for the attributes that emitted those facts, and one blob store shared by both sets. The description channel does not participate in intrinsic entity identity or ordinary content queries. Use += to union every channel, and use root()/exports() when you want the produced entity id(s) back alongside the facts. At the type level it represents their conjunction. Records are therefore intersection types: every additional field refines the shape without invalidating existing data.

Merge Drives Dataset Composition

For content facts, the += operator delegates to TribleSet::union, exposed through the AddAssign implementation. Fragment composition applies the same set union independently to facts and metafacts, unions exports, and structurally joins the shared blob stores. TribleSet::union performs set union on the six internal indexes that back a TribleSet. When the entity identifiers are disjoint the effect is classic dataset union; when they coincide we get field conjunction—record extension. This dual role is what keeps TribleSpace’s algebra compact.

One Operator, Two Readings

Everything that looks like “add another field” or “add another record” derives from the single law

union(facts₁, facts₂) = facts₁ ∪ facts₂.

The surrounding context determines how to read the result:

The behaviour follows from the idempotent, commutative nature of TribleSet::union; no special cases are required in the implementation.

Patterns as Row-Type Predicates

A find!/pattern! pair behaves like a row-type predicate:

pattern!([A, B])  ≈  ∀r. {A, B} ⊆ r.

Read this as “find every entity whose row type r is a supertype of this shape.” The macro expands to an IntersectionConstraint built from TriblePattern constraints, so queries literally evaluate the conjunction of the row predicates.

Patterns compose intersectionally as well: combining two patterns is equivalent to requiring both row predicates simultaneously, mirroring intersection types at the query level.

The Lattice Perspective

TribleSets form a join-semilattice under union:

union(a, b) = a ∪ b
a ≤ b  ⇔  a ⊆ b.

Projection, join, and filtering are lattice homomorphisms: they preserve joins and the partial order. Because the same algebra handles both data and metadata, the implementation remains uniform and performant—merging facts is always the same low-level operation.

Practical Payoffs

Seeing the primitives through a type-theoretic lens clarifies several ergonomic choices:

• Queries as proofs. Successful find! rows witness that an entity inhabits the requested type; absence is simply failure to prove the predicate.
• Descriptive schemas. Structural typing drops the need for globally declared records—the type system is implicit in the patterns you write.
• Composable extensions. Adding new attributes is monotonic: existing entities continue to satisfy prior predicates, and refined queries simply intersect more row constraints.

Summary Table

With a single associative, commutative, idempotent union, we obtain both row extension and dataset union, and a unified logical framework that bridges data engineering with type theory. That economy of primitives allows the system to feel simple on the surface yet provide rich type theory underneath.

Architecture Overview

TribleSpace is designed to keep data management simple, safe and fast. The README introduces these goals in more detail, emphasizing a lean design with predictable performance and straightforward developer experience. This chapter explains how the pieces fit together and why they are organised this way.

Design Goals

A full discussion of the motivation behind TribleSpace can be found in the Philosophy section. At a high level we want a self‑contained data store that offers:

• Simplicity – minimal moving parts and predictable behaviour.
• Developer Experience – a clear API that avoids complex servers or background processes.
• Safety and Performance – sound data structures backed by efficient content addressed blobs.

These goals grew out of earlier "semantic" technologies that attempted to model knowledge as graphs. While systems like RDF promised great flexibility, in practice they often became difficult to host, query and synchronise. TribleSpace keeps the idea of describing the world with simple statements but stores them in a form that is easy to exchange and reason about.

Design Principles

Three load-bearing decisions shape everything else in TribleSpace. Understanding them up front makes the rest of the architecture — the six indexes, the append-only storage, the branch/commit model, the absence of delete — read as consequences rather than costs.

1. Content Addressing

Every blob is identified by the hash of its bytes. Identical data deduplicates automatically, integrity is verifiable offline, and repositories can share data through any common storage without coordination. Handles are 32-byte hashes, which means they fit inline in a trible's value slot: a value either is its data (for short payloads) or points to its data (via a blob hash). This is what lets TribleSpace be "content-addressed all the way down" — schemas, commits, branch metadata, and application data all use the same primitive.

2. Monotonic Facts

Tribles are only added, never retracted. A TribleSet is a mathematical set of facts, and merging two sets is simply set union. There is no delete operation and no "latest wins" heuristic inside the data model. This follows the CALM principle: monotonic operations are coordination-free, so distributed replicas can merge without consensus. It is also what makes TribleSet a CRDT — two workspaces can edit independently and always reconcile cleanly.

The apparent limitation (how do you model mutable state?) is resolved by the next principle.

3. Entity Ownership

This is the decision that distinguishes TribleSpace from other triple stores. In RDF and similar systems, triple direction has no semantics — parentOf and childOf are interchangeable and systems typically auto-infer one from the other. TribleSpace gives direction provenance semantics: a trible A → attribute → B is always a claim made by A about B, and only the current owner of an entity ID may assert new facts with that entity in the subject position.

This ownership discipline is enforced through ExclusiveId guards, which are Send but not Sync — holding one guarantees that no other process is writing about that entity. In other words, each entity forms its own transactional shard. You can think of it as Rust's ownership model applied to data: just as the borrow checker prevents two threads from mutating the same variable, the ID ownership system prevents two processes from asserting conflicting attributes about the same entity.

The consequences are profound:

• Merges cannot conflict by construction. Two workspaces that edit different entities can always merge, because neither can have written about the other's entities. The "merge conflict resolution" problem that plagues distributed databases simply doesn't exist in this model.
• Non-monotonic operations become safe within an ownership scope. While the global data model stays monotonic, an owner holding a set of ExclusiveIds has a closed-world view of those entities. Operations like if-does-not-exist are well-defined within that transaction domain because no other writer can intervene.
• Mutable state is modelled as ownership + replacement. To "update" an entity's attribute, you mint a new entity and reference it from the owner. The old fact remains in the history; the current view is determined by what the owner currently points to. This is the same pattern as immutable data structures: mutation becomes a new version, and the "current" value is a pointer that gets swapped.

Entity ownership handles per-entity consistency, but some workflows need stronger guarantees — transactions that span multiple entities, or invariants like "these two facts must be visible atomically." For those cases the branch store's compare-and-set update provides defense in depth: a workspace stages its changes locally, and push only succeeds if the branch head hasn't moved since the workspace was pulled. On conflict, the caller merges the incoming changes and retries. This gives you serializable multi-entity transactions on top of the monotonic data model, at the cost of a retry loop under contention.

Together the two layers cover the full transaction story: entity ownership for "I own this thing, let me just update it," and branch CAS for "these N things must move as one." Neither requires the user to think about distributed coordination protocols.

The ID ownership system is documented in depth in Identifiers; the rest of this chapter assumes these three principles as given.

Architectural Layers

The system is organised into a small set of layers that compose cleanly:

┌─────────────────────────────────────────────┐
│  Application                                │
│  find!, pattern!, entity!, and!, or!        │
├─────────────────────────────────────────────┤
│  Workspace                                  │
│  in-memory editing surface, blob read/write │
├─────────────────────────────────────────────┤
│  Repository                                 │
│  branches, commits, push/pull, merge        │
├─────────────────────────────────────────────┤
│  Store (Pile / MemoryRepo / S3)             │
│  append-only blob + branch storage          │
├─────────────────────────────────────────────┤
│  Data Model                                 │
│  Trible (64 bytes) → TribleSet (6 indexes)  │
└─────────────────────────────────────────────┘

1. Data model – the immutable trible structures that encode facts.
2. Stores – generic blob and branch storage traits that abstract over persistence backends.
3. Repository – the coordination layer that combines stores into a versioned history.
4. Workspaces – the in‑memory editing surface used by applications and tools.

Each layer has a tight, well defined boundary. Code that manipulates tribles never needs to know if bytes ultimately land on disk or in memory, and repository level operations never reach inside the data model. This separation keeps interfaces small, allows incremental optimisation and makes it easy to swap pieces during experimentation.

Data Model

The fundamental unit of information is a Trible. Its 64 byte layout is described in Trible Structure. A Trible links a subject entity to an attribute and value. Multiple tribles are stored in a TribleSet, which behaves like a hashmap with three columns — subject, attribute and value.

The 64 byte boundary allows tribles to live comfortably on cache lines and makes deduplication trivial. Because tribles are immutable, the runtime can copy, hash and serialise them without coordinating with other threads. Higher level features like schema checking and query evaluation are therefore free to assume that every fact they observe is stable for the lifetime of a query.

Trible Sets

TribleSets provide fast querying and cheap copy‑on‑write semantics. They can be merged, diffed and searched entirely in memory. When durability is needed the set is serialised into a blob and tracked by the repository layer.

To keep joins skew‑resistant, each set maintains all six orderings of entity, attribute and value. The trees reuse the same leaf nodes so a trible is stored only once, avoiding a naïve six‑fold memory cost while still letting the search loop pick the most selective permutation using the constraint heuristics.

Blob Storage

All persistent data lives in a BlobStore. Each blob is addressed by the hash of its contents, so identical data occupies space only once and readers can verify integrity by recomputing the hash. The trait exposes simple get and put operations, leaving caching and eviction strategies to the backend. Implementations decide where bytes reside: an in‑memory MemoryBlobStore, an on‑disk Pile described in Pile Format or a remote object store. Because handles are just 32‑byte hashes, repositories can copy or cache blobs without coordination. Trible sets, user blobs and commit records all share this mechanism.

Content addressing also means that blob stores can be layered. Applications commonly use a fast local cache backed by a slower durable store. Only the outermost layer needs to implement eviction; inner layers simply re-use the same hash keys, so cache misses fall through cleanly.

Branch Store

A BranchStore keeps track of the tips of each branch. Updates use a simple compare‑and‑set operation so concurrent writers detect conflicts. Both the in‑memory and pile repositories implement this trait.

Branch stores are intentionally dumb. They neither understand commits nor the shape of the working tree. Instead they focus on a single atomic pointer per branch. This reduces the surface area for race conditions and keeps multi‑writer deployments predictable even on eventually consistent filesystems.

Because only this single operation mutates repository state, nearly all other logic is value oriented and immutable. Conflicts surface only at the branch store update step, which simplifies concurrent use and reasoning about changes.

Repository

The Repository combines a blob store with a branch store. Commits store a trible set blob along with a parent link and signature. Because everything is content addressed, multiple repositories can share blobs or synchronize through a basic file copy.

Repository logic performs a few critical duties:

• Validation – ensure referenced blobs exist and signatures line up with the claimed authorship.
• Blob synchronization – upload staged data through the content-addressed blob store, which skips already-present bytes and reports integrity errors.
• History traversal – provide iterators that let clients walk parent chains efficiently.

All of these operations rely only on hashes and immutable blobs, so repositories can be mirrored easily and verified offline.

Workspaces

A Workspace represents mutable state during editing. Checking out or branching yields a workspace backed by a fresh MemoryBlobStore. Commits are created locally and only become visible to others when pushed, as described in Repository Workflows.

Workspaces behave like sandboxes. They host application caches, pending trible sets and user blobs. Because they speak the same blob language as repositories, synchronisation is just a matter of copying hashes from the workspace store into the shared store once a commit is finalised.

Commits and History

TribleSets written to blobs form immutable commits. Each commit references its parent, creating an append‑only chain signed by the author. This is the durable history shared between repositories.

Because commits are immutable, rollback and branching are cheap. Diverging histories can coexist until a user merges them by applying query language operations over the underlying trible sets. The repository simply tracks which commit each branch tip points to.

Putting It Together

+-----------------------------------------------+
|                   Repository                  |
|   BlobStore (content addressed)               |
|   BranchStore (compare-and-set head)          |
+----------------------------+------------------+
           ^ push/try_push        pull
           |                         |
           |                         v
+----------------------------+------------------+
|                   Workspace                   |
|   base_blobs reader (view of repo blobs)      |
|   MemoryBlobStore (staged blobs)              |
|   current head (latest commit reference)      |
+----------------------------+------------------+
        ^             ^             |
        |             |         checkout
     commit       add_blob          |
        |             |             v
+----------------------------+------------------+
|                 Application                  |
+----------------------------------------------+

Repository::pull reads the branch metadata, loads the referenced commit, and couples that history with a fresh MemoryBlobStore staged area plus a reader for the repository's existing blobs.【F:src/repo.rs†L820-L848】 Workspace methods then stage edits locally: Workspace::put (the helper that adds blobs) writes application data into the in-memory store while Workspace::commit converts the new TribleSet into blobs and advances the current head pointer.【F:src/repo.rs†L1514-L1568】 Applications hydrate their views with Workspace::checkout, which gathers the selected commits and returns the assembled trible set to the caller.【F:src/repo.rs†L1681-L1697】 When the changes are ready to publish, Repository::try_push enumerates the staged blobs, uploads them into the repository blob store, creates updated branch metadata, and performs the compare-and-set branch update before clearing the staging area.【F:src/repo.rs†L881-L1014】 Because every blob is addressed by its hash, repositories can safely share data through any common storage without coordination.

The boundaries between layers encourage modular tooling. A CLI client can operate entirely within a workspace while a sync service automates pushes and pulls between repositories. As long as components honour the blob and branch store contracts they can evolve independently without risking the core guarantees of TribleSpace.

Patterns & Recipes

This chapter collects idiomatic solutions to common problems. Each recipe is self-contained — jump to the one that matches your situation.

Modeling relationships

One-to-one

An entity links to exactly one other entity via a GenId attribute:

attributes! {
    "..." as author: GenId;
}

let book = fucid();
let writer = fucid();
change += entity! { &book @ literature::author: &writer };

Query both directions: the attribute stores the forward link, and the query engine can traverse it in reverse by binding the value and querying for the entity:

// Forward: who wrote this book?
find!(author: Id, pattern!(&catalog, [{ book_id @ literature::author: ?author }]))

// Reverse: what did this author write?
find!(book: Id, pattern!(&catalog, [{ ?book @ literature::author: author_id }]))

Many-to-many

Use a repeated attribute — the same entity can have multiple values for one attribute. The entity! macro supports this with the * spread syntax:

let paper = fucid();
let tag_ml = fucid();
let tag_neuro = fucid();
change += entity! { &paper @ metadata::tag: &tag_ml };
change += entity! { &paper @ metadata::tag: &tag_neuro };

Or in a single entity expression:

let tags = vec![tag_ml, tag_neuro];
change += entity! { &paper @ metadata::tag*: tags.iter() };

Query all tags for an entity, or all entities with a tag:

// All tags on this paper
find!(tag: Id, pattern!(&catalog, [{ paper_id @ metadata::tag: ?tag }]))

// All papers with this tag
find!(paper: Id, pattern!(&catalog, [{ ?paper @ metadata::tag: tag_id }]))

Hierarchies (parent/child)

Model with a parent attribute. Children point up to their parent:

attributes! {
    "..." as parent: GenId;
}
change += entity! { &child @ tree::parent: &parent_node };

A fixed number of hops is just a chain of clauses, joined on temp! variables:

// Grandparents: two hops up.
find!(grandparent: Id,
      temp!((mid),
            and!(pattern!(&catalog, [{ node_id @ tree::parent: ?mid }]),
                 pattern!(&catalog, [{ ?mid @ tree::parent: ?grandparent }]))))

Unbounded traversal — all ancestors, all descendants — is handled by the standalone triblespace-paths closure index rather than by query-time recursion. Describe one-or-more parent edges with PathExpr, compile the expression, materialize it once, and use its endpoint relation as an ordinary constraint:

let parent = tree::parent.id().into();
let parent_plus = PathExpr::from(Step::Forward(parent)).plus();
let ancestors = PathIndex::from_tribles(parent_plus.compile(), catalog.iter())?;
let node: Inline<GenId> = node_id.to_inline();

for ancestor in find!(
    ancestor: Id,
    ancestors.constraint(node, ancestor)
) {
    println!("ancestor: {ancestor:?}");
}

For repository-backed maintenance and the cost of a potentially dense closure, see Regular Path Indexes. The core query engine stays non-recursive and stateless; the index turns the recursive result into a normal relation before the query begins.

Entity classification with tags

Use metadata::tag with minted GenId tag entities. Give tags human-readable names via metadata::name:

// Mint a tag once
let kind_paper = id_hex!("A1B2C3...");  // or use trible genid for random IDs
change += entity! { &kind_paper @ metadata::name: "paper" };

// Tag an entity
change += entity! { &my_paper @ metadata::tag: &kind_paper };

// Find all papers
find!(paper: Id, pattern!(&catalog, [{ ?paper @ metadata::tag: kind_paper }]))

This is the pattern used by wiki.rs (KIND_VERSION_ID), compass.rs (KIND_GOAL_ID), and files.rs (KIND_FILE, KIND_DIRECTORY, KIND_IMPORT). Tags are entities, not strings — they can carry metadata, participate in queries, and be shared across systems.

Working with blobs

Values larger than 32 bytes live in blobs. The workspace manages their lifecycle:

// Inline a blob payload — entity!{} auto-puts the bytes into the
// workspace's blob store and stores the resulting handle in the trible.
change += entity! { &doc @ article::body: "A very long string..." };

// Read a blob back via the handle stored in the trible:
let body: View<str> = ws.get(some_body_handle)?;
println!("{}", body.as_ref());

// If you do want the handle in hand before the entity!{} call —
// to reuse it across multiple entities, log it, ship it across
// the wire — `ws.put` still does that:
let text_handle = ws.put("A very long string...".to_owned());
change += entity! { &doc @ article::body: text_handle };

When to use blobs vs values:

• If you need to join or filter on the data → value (inline, 32 bytes)
• If it's opaque content you just store and retrieve → blob (Handle)
• Rule of thumb: names and tags are values, content and payloads are blobs

Building entities from optional attributes

When some attributes are always present and others are conditional, build the required part first, then conditionally extend:

let id = ufoid();
let mut change = TribleSet::new();

// Required attributes — always written together
change += entity! { &id @
    metadata::tag: &KIND_REQUEST,
    request::command: command_handle,
    request::created_at: now,
};

// Optional attributes — only if present
if let Some(cwd) = default_cwd {
    change += entity! { &id @ request::cwd: cwd };
}

When querying, use a multi-attribute pattern for the required fields (the query engine proves they exist), and separate queries for optional fields:

// Required: one pattern, no Option<> needed
for (id, command, created_at) in find!(
    (id: Id, cmd: TextHandle, at: Inline<NsTAIInterval>),
    pattern!(&catalog, [{
        ?id @
        metadata::tag: &KIND_REQUEST,
        request::command: ?cmd,
        request::created_at: ?at,
    }])
) {
    // Optional: separate query
    let cwd = find!(
        handle: TextHandle,
        pattern!(&catalog, [{ id @ request::cwd: ?handle }])
    ).next();
}

Schema evolution

Adding a new attribute to existing entities is free — just start writing it. Existing entities that lack the attribute are unaffected; queries that require it simply won't match them. This is the monotonic property at work.

// V1: papers have title and author
change += entity! { &paper @ literature::title: "Dune", literature::author: &herbert };

// V2: add page_count to new papers — old papers still work fine
change += entity! { &new_paper @
    literature::title: "Foundation",
    literature::author: &asimov,
    literature::page_count: 255u64.to_inline(),
};

// Query: papers with page_count (only new ones match)
find!((paper: Id, pages: Inline<U256BE>),
    pattern!(&catalog, [{ ?paper @ literature::page_count: ?pages }]))

// Query: all papers (both old and new match)
find!(paper: Id,
    pattern!(&catalog, [{ ?paper @ literature::title: _?t }]))

Removing an attribute is not directly supported — triblesets are monotonic. Instead, add a new attribute that supersedes the old one, and update your queries to prefer it. The old data remains but stops being used.

Multi-dataset queries

Queries can span multiple TribleSets and even native Rust collections in a single find! call using and!:

let local_facts = TribleSet::new();
let remote_facts = TribleSet::new();

find!((entity: Id, name: String),
    and!(
        pattern!(&local_facts, [{ ?entity @ schema::tag: &KIND_PERSON }]),
        pattern!(&remote_facts, [{ ?entity @ schema::name: ?name }])
    ))

The engine handles the join — it doesn't matter which dataset holds which attributes.

Repository Workflows

Working with a Tribles repository feels familiar to Git users, but the types make data ownership and lifecycle explicit. Keep the following vocabulary in mind when exploring the API:

• Repository – top-level object that tracks history through BlobStore and BranchStore implementations.
• Workspace – mutable view of a branch, similar to Git's working directory and index combined. Workspaces buffer commits and custom blobs until you push them back to the repository.
• BlobStore – storage backend for commits and payload blobs.
• BranchStore – records branch metadata and head pointers.

Both stores can be in memory, on disk or backed by a remote service. The examples in examples/repo.rs and examples/workspace.rs showcase these APIs and are a great place to start if you are comfortable with Git but new to Tribles.

Publishing an append-only collection

Applications that only need to publish independent facts do not need to mint a branch or select a mutable head. Collection<S> is the narrow publication facade for that case. It combines a storage backend, one canonical collection descriptor, and a signing key; every call to Collection::commit(Fragment) publishes one independent signed membership assertion:

use triblespace::prelude::{Collection, Fragment};

// `storage` implements BlobStorePut + CollectionStore + StorageFlush.
// `scope` is the stable Id of this dataset.
let mut collection = Collection::new(storage, scope, signing_key);
let commit = collection.commit(fragment)?;
let snapshot = collection.snapshot()?;
let facts = snapshot.facts();
let exact_commits = snapshot.commits();
let storage = collection.into_storage();

A collection descriptor is a canonical SimpleArchive containing exactly the dataset scope, blob representation, and algebraic recipe. Its 32-byte content handle is the CollectionId. COMMIT, MERGE, and DERIVE records carry descriptor handles directly, so any claim can resolve and verify its own collection semantics through the ordinary blob store. There is no separate definition record or registry whose synchronization could make an otherwise complete claim ambiguous. Collection::new constructs the canonical SimpleArchive-union descriptor for the supplied scope.

The fragment remains self-contained across the publication boundary: its facts become the collection's canonical SimpleArchive data element, its metafacts become the commit's canonical metadata archive, and attachments from its shared blob store are copied alongside those two archives. Publication flushes all dependencies, including the descriptor blob, before inserting the signed commit record. Identical retries are idempotent, while distinct commits coexist; there is no branch head, CAS retry, or implied "latest" member.

When the backend also provides a blob reader with metadata lookup, Collection::materialize() returns the complete known union of commits signed by the facade's own key for this exact scoped collection. Commits signed by other keys are not admitted. A failed signature authenticates none of its record fields and is therefore an inert diagnostic, never an owner-attributed veto. Every strictly verified own commit is ground truth: its descriptor, data archive, and exact metadata archive must all validate or the read fails instead of silently returning a partial set. Valid resident MERGE records may provide a compact physical cover. Validation is the intersection of two reachability walks: backwards from resident result identities (through nonresident intermediates when needed), then forwards from authenticated leaves. Optional result bytes are exact-checked against their computed canonical identity before a tentative physical cover is accepted. Missing, corrupt, invalid, ungrounded, or irrelevant unsigned merge evidence is merely a cache miss, so it cannot erase committed leaves or drive demand-born blob fetches.

This read boundary assumes that collection records have already passed the deployment's admission policy. It bounds blob authority, not arbitrary CPU work: each distinct admitted equation may still require canonical union validation. A network service must therefore authenticate and bound record admission (or retain immutable validation receipts) before placing untrusted claims in its durable CollectionStore; otherwise both validation CPU and temporary resource use scale with the admitted equation graph.

Materialization has the same observed-prefix concurrency contract as native record listing. It first discovers one deterministic record view and then opens a blob-reader snapshot. A concurrent commit not observed during that discovery appears on a later call; all own commits that were observed are included or the call returns an error. This is deliberately not a global "latest" transaction. Collection::snapshot() carries the materialized facts, that exact authorized commit set, and the reader used for validation together. Physically visible blobs from a later commit remain inert unless its signed record belongs to the returned commit set, so derived-index builders cannot accidentally pair an old fact view with a newer source ticket. Collection::materialize() is the facts- only projection and retains its empty-collection fast path without opening a reader.

Pile, MemoryRepo, and the storage composition wrappers implement the native CollectionStore surface. ObjectStoreRemote exposes the corresponding async surface and can be used with Collection through Blocking. Under the configured object-store prefix, each record is a create-only object at collection-records/<intrinsic-record-id> whose bytes are the record's canonical SimpleArchive. Listing is an observed monotone view rather than a global snapshot: a concurrent immutable insert may appear on this list or the next, but any observed object is decoded and checked against the ID in its path. Descriptor blobs use the ordinary blob namespace; CollectionStore contains only COMMIT, MERGE, and DERIVE.

This collection path coexists with the branch-oriented Repository and Workspace APIs documented below. Native collection records are not pin updates; choosing the headless path does not change the semantics of existing branches.

Opening a repository

Repositories are constructed from any storage that implements the appropriate traits. The choice largely depends on your deployment scenario:

1. Pick or compose a storage backend (see Storage Backends and Composition).
2. Create a signing key for the identity that will author commits.
3. Call Repository::new(storage, signing_key, commit_metadata) to obtain a handle. Pass TribleSet::new() for commit_metadata when you do not need custom metadata on commits.

Most applications perform the above steps once during start-up and then reuse the resulting Repository. If initialization may fail (for example when opening an on-disk pile), bubble the error to the caller so the process can retry or surface a helpful message to operators.

Storage Backends and Composition

Repository accepts any storage that implements both the BlobStore and BranchStore traits, so you can combine backends to fit your deployment. The crate ships with a few ready-made options:

• MemoryRepo stores everything in memory and is ideal for tests or short-lived tooling where persistence is optional.
• Pile persists blobs and branch metadata in a single append-only file. It is the default choice for durable local repositories and integrates with the pile tooling described in Pile Format.
• ObjectStoreRemote connects to object_store endpoints (S3, local filesystems, etc.). It keeps all repository data in the remote service and is useful when you want a shared blob store without running a dedicated server.
• HybridStore lets you split responsibilities, e.g. storing blobs on disk while keeping branch heads in memory or another backend. Any combination that satisfies the trait bounds works.

Backends that need explicit shutdown can implement StorageClose. When the repository type exposes that trait bound you can call repo.close()? to flush and release resources instead of relying on Drop to run at an unknown time. This is especially handy for automation where the process may terminate soon after completing a task.

use triblespace::core::repo::hybridstore::HybridStore;
use triblespace::core::repo::memoryrepo::MemoryRepo;
use triblespace::core::repo::objectstore::ObjectStoreRemote;
use triblespace::core::repo::Repository;
use triblespace::core::inline::encodings::hash::Blake3;
use url::Url;

let blob_remote: ObjectStoreRemote<Blake3> =
    ObjectStoreRemote::with_url(&Url::parse("s3://bucket/prefix")?)?;
let branch_store = MemoryRepo::default();
let storage = HybridStore::new(blob_remote, branch_store);
let mut repo = Repository::new(storage, signing_key, TribleSet::new())?;

// Work with repo as usual …
// repo.close()?; // if the underlying storage supports StorageClose

Branching

A branch records a line of history and carries the metadata that identifies who controls updates to that history. Creating one writes initial metadata to the underlying store and returns an ExclusiveId guarding the branch head. Dereference that ID when you need a plain Id for queries or workspace operations.

Typical steps for working on a branch look like:

1. Create a repository backed by blob and branch stores via Repository::new.
2. Initialize or look up a branch ID with helpers like Repository::create_branch. When interacting with an existing branch call Repository::pull directly.
3. Commit changes in the workspace using Workspace::commit.
4. Push the workspace with Repository::push (or handle conflicts manually via Repository::try_push) to publish those commits.

The example below demonstrates bootstrapping a new branch and opening multiple workspaces on it. Each workspace holds its own staging area, so remember to push before sharing work or starting another task.

let mut repo = Repository::new(pile, SigningKey::generate(&mut OsRng), TribleSet::new())?;
let branch_id = repo.create_branch("main", None).expect("create branch");

let mut ws = repo.pull(*branch_id).expect("pull branch");
let mut ws2 = repo.pull(ws.branch_id()).expect("open branch");

After committing changes you can push the workspace back. push will retry on contention and attempt to merge, while try_push performs a single attempt and returns Ok(Some(conflict_ws)) when the branch head moved. Choose the latter when you need explicit conflict handling:

ws.commit(change, "initial commit");
repo.push(&mut ws)?;

Managing signing identities

The key passed to Repository::new becomes the default signing identity for branch metadata and commits. Collaborative projects often need to switch between multiple authors or assign a dedicated key to automation. You can adjust the active identity in three ways:

• Repository::set_signing_key replaces the repository's default key. Subsequent calls to helpers such as Repository::create_branch or Repository::pull use the new key for any commits created from those workspaces.
• Repository::create_branch_with_key signs a branch's metadata with an explicit key, allowing each branch to advertise the author responsible for updating it.
• Repository::pull_with_key opens a workspace that will sign its future commits with the provided key, regardless of the repository default.

The snippet below demonstrates giving an automation bot its own identity while letting a human collaborator keep theirs:

use ed25519_dalek::SigningKey;
use rand::rngs::OsRng;
use triblespace::core::repo::Repository;

let alice = SigningKey::generate(&mut OsRng);
let automation = SigningKey::generate(&mut OsRng);

// Assume `pile` was opened earlier, e.g. via `Pile::open` as shown in previous sections.
let mut repo = Repository::new(pile, alice.clone(), TribleSet::new())?;

// Create a dedicated branch for the automation pipeline using its key.
let automation_branch = repo
    .create_branch_with_key("automation", None, automation.clone())?
    .release();

// Point automation jobs at their dedicated identity by default.
repo.set_signing_key(automation.clone());
let mut bot_ws = repo.pull(automation_branch)?;

// Humans can opt into their own signing identity even while automation remains
// the repository default.
let mut human_ws = repo.pull_with_key(automation_branch, alice.clone())?;

human_ws and bot_ws now operate on the same branch but will sign their commits with different keys. This pattern is useful when rotating credentials or running scheduled jobs under a service identity while preserving authorship in the history. You can swap identities at any time; existing workspaces keep the key they were created with until you explicitly call Repository::set_signing_key.

Inspecting History

You can explore previous commits using Workspace::checkout which returns a Checkout (which derefs to TribleSet and also tracks the CommitSet) with the union of the specified commit contents. Passing a single commit returns just that commit. To include its history you can use the ancestors helper. Commit ranges are supported for convenience. The expression a..b yields every commit reachable from b that is not reachable from a, treating missing endpoints as empty (..b) or the current HEAD (a.. and ..). These selectors compose with filters, so you can slice history to only the entities you care about.

let history = ws.checkout(commit_a..commit_b)?;
let full = ws.checkout(ancestors(commit_b))?;

The history_of helper builds on the filter selector to retrieve only the commits affecting a specific entity. Commit selectors are covered in more detail in the next chapter:

let entity_changes = ws.checkout(history_of(my_entity))?;

Working with Custom Blobs

Workspaces keep a private blob store that mirrors the repository's backing store. This makes it easy to stage large payloads alongside the trible sets you plan to commit. The Workspace::put helper stores any type implementing ToBlob and returns a typed handle you can embed like any other value. Handles are Copy, so you can commit them and reuse them to fetch the blob later.

The example below stages a quote and an archived TribleSet, commits both, then retrieves them again with strongly typed and raw views. In practice you might use this pattern to attach schema migrations, binary artifacts, or other payloads that should travel with the commit:

use ed25519_dalek::SigningKey;
use rand::rngs::OsRng;
use triblespace::core::blob::Blob;
use triblespace::core::examples::{self, literature};
use triblespace::prelude::*;
use triblespace::core::repo::{self, memoryrepo::MemoryRepo, Repository};
use blobencodings::{LongString, SimpleArchive};

let storage = MemoryRepo::default();
let mut repo = Repository::new(storage, SigningKey::generate(&mut OsRng), TribleSet::new())?;
let branch_id = repo.create_branch("main", None).expect("create branch");
let mut ws = repo.pull(*branch_id).expect("pull branch");

// `entity!{}` auto-puts blob payloads into the workspace's blob
// store — the value side of a `Handle<S>`-typed field becomes the
// content-addressed handle that lives in the trible.
//
// When you also need the handle in hand (to read back, log, share,
// or reuse across multiple entities), call `ws.put` explicitly.
let quote_handle: Inline<Handle<LongString>> =
    ws.put("Fear is the mind-killer".to_owned());
let archive_handle: Inline<Handle<SimpleArchive>> =
    ws.put(&examples::dataset());

let mut change = entity! {
    literature::title: "Dune (annotated)",
    literature::quote: quote_handle.clone(),
};
change += entity! { repo::content: archive_handle.clone() };

ws.commit(change, "Attach annotated dataset");
// Single-attempt push. Use `push` to let the repository merge and retry automatically.
repo.try_push(&mut ws).expect("try_push");

// Fetch the staged blobs back with the desired representation.
let restored_quote: String = ws
    .get(quote_handle)
    .expect("load quote");
let restored_set: TribleSet = ws
    .get(archive_handle)
    .expect("load dataset");
let archive_bytes: Blob<SimpleArchive> = ws
    .get(archive_handle)
    .expect("load raw blob");
std::fs::write("dataset.car", archive_bytes.bytes.as_ref()).expect("persist archive");

Rust infers the blob encoding for both put and get from the handles and the assignment context, so the calls stay concise without explicit turbofish annotations.

Blobs staged this way stay local to the workspace until you push the commit. Workspace::get searches the workspace-local store first and falls back to the repository if necessary, so the handles remain valid after you publish the commit. This round trip lets you persist logs, archives, or other auxiliary files next to your structured data without inventing a separate storage channel.

Merging and Conflict Handling

When pushing a workspace another client might have already updated the branch. There are two ways to handle this:

• Repository::try_push — a single-attempt push that uploads local blobs and attempts a CAS update once. If the branch advanced concurrently it returns Ok(Some(conflict_ws)) so callers can merge and retry explicitly:

ws.commit(content, "codex-turn");
let mut current_ws = ws;
while let Some(mut incoming) = repo.try_push(&mut current_ws)? {
    // Merge the local staged changes into the incoming workspace and retry.
    incoming.merge(&mut current_ws)?;
    current_ws = incoming;
}

• Repository::push — a convenience wrapper that performs the merge-and-retry loop for you. Call this when you prefer the repository to handle conflicts automatically; it either succeeds (returns Ok(())) or returns an error.

ws.commit(content, "codex-turn");
repo.push(&mut ws)?; // will internally merge and retry until success

Troubleshooting: Workspace::merge succeeds only when both workspaces share a blob store. Merging a workspace pulled from a different pile or remote returns MergeError::DifferentRepos. Decide which repository will own the combined history, transfer the other branch's reachable blobs into it with repo::transfer(reachable(...)), create a branch for that imported head, and merge locally once both workspaces target the same store.

After a successful push the branch may have advanced further than the head supplied, because the repository refreshes its view after releasing the lock. An error indicating a corrupted pile does not necessarily mean the push failed; the update might have been written before the corruption occurred.

This snippet is taken from examples/workspace.rs. The examples/repo.rs example demonstrates the same pattern with two separate workspaces. The returned Workspace already contains the remote commits, so after merging your changes you push that new workspace to continue.

Typical CLI Usage

There is a small command line front-end in the trible repository. It exposes push and merge operations over simple commands and follows the same API presented in the examples. The tool is currently experimental and may lag behind the library, but it demonstrates how repository operations map onto a CLI.

Diagram

A simplified view of the push/merge cycle:

        ┌───────────┐         pull          ┌───────────┐
        | local ws  |◀───────────────────── |   repo    |
        └─────┬─────┘                       └───────────┘
              │
              │ commit
              │                                                                      
              ▼                                   
        ┌───────────┐         push          ┌───────────┐
        │  local ws │ ─────────────────────▶│   repo    │
        └─────┬─────┘                       └─────┬─────┘
              │                                   │
              │ merge                             │ conflict?
              └──────▶┌─────────────┐◀────────────┘
                      │ conflict ws │       
                      └───────┬─────┘
                              │             ┌───────────┐
                              └────────────▶|   repo    │
                                     push   └───────────┘
   

Each push either succeeds or returns a workspace containing the other changes. Merging incorporates your commits and the process repeats until no conflicts remain.

Troubleshooting push, branch, and pull failures

Repository::push, Repository::create_branch, and Repository::pull surface errors from the underlying blob and branch stores. These APIs intentionally do not hide storage issues, because diagnosing an I/O failure or a corrupt commit usually requires operator intervention. The table below lists the error variants along with common causes and remediation steps.

Remote Stores

Remote deployments use the ObjectStoreRemote backend to speak to any service supported by the object_store crate (S3, Google Cloud Storage, Azure Blob Storage, HTTP-backed stores, the local filesystem, and the in-memory memory:/// adapter). ObjectStoreRemote implements both BlobStore and BranchStore, so the rest of the repository API continues to work unchanged – the only difference is the URL you pass to with_url.

use ed25519_dalek::SigningKey;
use rand::rngs::OsRng;
use triblespace::prelude::*;
use triblespace::core::repo::objectstore::ObjectStoreRemote;
use triblespace::core::repo::Repository;
use triblespace::core::inline::encodings::hash::Blake3;
use url::Url;

fn open_remote_repo(raw_url: &str) -> anyhow::Result<()> {
    let url = Url::parse(raw_url)?;
    let storage = ObjectStoreRemote::<Blake3>::with_url(&url)?;
    let mut repo = Repository::new(storage, SigningKey::generate(&mut OsRng), TribleSet::new())?;

    let branch_id = repo.create_branch("main", None)?;
    let mut ws = repo.pull(*branch_id)?;
    ws.commit(TribleSet::new(), "initial commit");

    while let Some(mut incoming) = repo.try_push(&mut ws)? {
        incoming.merge(&mut ws)?;
        ws = incoming;
    }

    Ok(())
}

ObjectStoreRemote writes directly through to the backing service. It implements StorageClose, but the implementation is a no-op, so dropping the repository handle is usually sufficient. Call repo.close() if you prefer an explicit shutdown step.

Credential configuration follows the object_store backend you select. For example, S3 endpoints consume AWS access keys or IAM roles, while memory:///foo provides a purely in-memory store for local testing. Once the URL resolves, repositories backed by piles and remote stores share the same workflow APIs.

Attaching a Foreign History (merge-import)

Sometimes you want to graft an existing branch from another pile into your current repository without rewriting its commits. Tribles supports a conservative, schema‑agnostic import followed by a single merge commit:

1. Copy all reachable blobs from the source branch head into the target pile by streaming the reachable walker into repo::transfer. The traversal scans every 32‑byte aligned chunk and enqueues any candidate that dereferences in the source.
2. Create a single merge commit that has two parents: your current branch head and the imported head. No content is attached to the merge; it simply ties the DAGs together.

This yields a faithful attachment of the foreign history — commits and their content are copied verbatim, and a one‑off merge connects both histories.

The trible CLI exposes this as:

trible branch merge-import \
  --from-pile /path/to/src.pile --from-name source-branch \
  --to-pile   /path/to/dst.pile --to-name   self

Internally this uses the reachable walker in combination with repo::transfer plus Workspace::merge_commit. Because the traversal scans aligned 32‑byte chunks, it is forward‑compatible with new formats as long as embedded handles remain 32‑aligned.

Sidebar — Choosing a copy routine

• repo::transfer pairs the reachability walker (or any other iterator you provide) with targeted copies, returning (old_handle, new_handle) pairs for the supplied handles. Feed it the reachable iterator when you only want live blobs, the output of potential_handles when scanning metadata, or the .handle values projected from BlobInfo items returned by BlobStoreList::blobs() when duplicating an entire store.
• MemoryBlobStore::keep (and other BlobStoreKeep implementations) retain whichever handles you stream to them, making it easy to drop unreachable blobs once you've walked your roots.

Reachable copy keeps imports minimal; the transfer helper lets you rewrite specific handles while duplicating data into another store.

Programmatic example (Rust)

The same flow can be used directly from Rust when you have two piles on disk and want to attach the history of one branch to another:

use ed25519_dalek::SigningKey;
use rand::rngs::OsRng;
use triblespace::prelude::*;
use triblespace::core::repo::{self, pile::Pile, Repository};
use triblespace::core::inline::encodings::hash::Blake3;
use triblespace::core::inline::encodings::hash::Handle;

fn merge_import_example(
    src_path: &std::path::Path,
    src_branch_id: triblespace::id::Id,
    dst_path: &std::path::Path,
    dst_branch_id: triblespace::id::Id,
) -> anyhow::Result<()> {
    // 1) Open source (read) and destination (write) piles. `refresh`
    //    loads the existing records and fails loud on a corrupt tail
    //    (repair is a separate, explicit step: `Pile::amputate` /
    //    `trible pile amputate`).
    let mut src = Pile::open(src_path)?;
    src.refresh()?;
    let mut dst = Pile::open(dst_path)?;
    dst.refresh()?;

    // 2) Resolve source head commit handle
    let src_head: Inline<Handle<blobencodings::SimpleArchive>> =
        src.head(src_branch_id)?.ok_or_else(|| anyhow::anyhow!("source head not found"))?;

    // 3) Conservatively copy all reachable blobs from source → destination
    let reader = src.reader()?;
    let mapping: Vec<_> = repo::transfer(
        &reader,
        &mut dst,
        repo::reachable(&reader, [src_head.transmute()]),
    )
    .collect::<Result<_, _>>()?;
    eprintln!("copied {} reachable blobs", mapping.len());

    // 4) Attach via a single merge commit in the destination branch
    let mut repo = Repository::new(dst, SigningKey::generate(&mut OsRng), TribleSet::new())?;
    let mut ws = repo.pull(dst_branch_id)?;
    ws.merge_commit(src_head)?; // parents = { current HEAD, src_head }

    // 5) Push with standard conflict resolution
    while let Some(mut incoming) = repo.try_push(&mut ws)? {
        incoming.merge(&mut ws)?;
        ws = incoming;
    }

    drop(ws);
    repo.close()?;
    drop(reader);
    src.close()?;
    Ok(())
}

Optional telemetry sink

The facade crate exposes an optional telemetry feature that turns tracing spans into TribleSpace commits. This is useful for profiling services, import pipelines, or long-running agents while keeping telemetry noise in a dedicated pile.

use triblespace::telemetry::Telemetry;

let _guard = Telemetry::install_global_from_env("archive import");

Set TELEMETRY_PILE and a 32-character hexadecimal TELEMETRY_COLLECTION_SCOPE to enable the sink. Every flushed batch becomes an independent signed collection commit carrying its telemetry schema as metafacts; no mutable branch head or compare-and-set retry is involved. You can tune batching via TELEMETRY_FLUSH_MS.

Range-Native Derived Indexes

Derived indexes are replaceable views over repository history. Their identity should therefore describe which source commits they cover, while the chosen index representation remains an open attribute on that source range.

The repo::index_range module supplies this artifact-neutral foundation. It does not assign a generic kind tag or erase every artifact into one blob field. A consumer instead defines typed attributes such as a Succinct archive, Rank9 accelerator, BM25 segment, or HNSW graph and attaches those facts to a stable range entity.

Inclusive DAG frontiers

A commit history is a DAG, so a source region cannot generally be represented by one linear start and end cursor. Each range has two repeated attributes:

• commit_start*: the minimal included commits;
• commit_end*: the maximal included commits.

Both frontiers are nonempty antichains and both are inclusive. A one-commit leaf—including a genesis commit—is [C,C]. There is no null or exclusive cursor sentinel.

For start frontier S and end frontier E, the range denotes the union of closed commit-poset intervals:

R(S,E) = { x | some s in S and e in E satisfy s <= x <= e }

The frontiers must be exact: S must equal the minima of R(S,E) and E must equal its maxima. This rejects comparable values within one frontier and disconnected boundaries.

A diamond illustrates why the values are repeated:

       A
      / \
     G   M
      \ /
       B

• the sibling region {A,B} has start={A,B}, end={A,B};
• the full diamond has start={G}, end={M};
• the merge commit alone is the leaf start={M}, end={M} and does not include either parent.

Stable range identity and open facts

The RangeRecord identity is the intrinsic core (index_recipe, commit_start*, commit_end*). A raw Succinct archive and the Rank9 accelerator built specifically for it can therefore share one recipe slot and lifecycle, while BM25, HNSW, or even another configuration over the same commits receives a different recipe and cannot collapse into that entity. Artifact handles themselves never participate in the id.

RangeRecord retains every fact whose subject is its real entity id, including attributes unknown to the current binary, and refreshes only the intrinsic recipe-plus-frontier core when it is serialized. select_range_record_facts is the preferred carry-forward primitive because it copies selected entity facts verbatim without parsing or reconstruction.

Independent typed maintenance uses replace_range_attributes: it removes only the selected (entity, typed attribute) facts and preserves all co-located and unknown attributes. The recipe/range core remains even with zero typed handles; that is the canonical completed-empty projection. replace_range_records removes every fact under a retired entity and is used when compacting the complete recipe/range slot and all artifacts owned by it.

Typed index-home manifests

repo::index_home gives the artifact-neutral range model a typed maintenance surface. An IndexKind supplies one deterministic, inline-only recipe_fragment() with exactly one exported root. That recipe entity is also the manifest header and carries a self-marker:

recipe @ index_recipe: recipe

The marker makes even an empty manifest discoverable during a generic branch metadata rebuild. All facts on a discovered recipe or range subject are copied verbatim, including attributes unknown to the current binary. Parsing checks the known control fields without reconstructing those real entities from a lossy Rust projection.

The header's repeated index_head* values are the maximal antichain currently certified by the manifest. Empty history uses an empty frontier; a fully caught-up branch normally uses the singleton {HEAD}. A partial durable replay across a fork may instead use several tips. The exact-cover audit compares the live ranges with the union of every frontier tip's ancestor closure.

Each logical range entity has exactly one seg_level and seg_seq, plus zero or more recipe-typed physical artifacts. Fanout and compaction count logical range records, not their physical shards. store_artifact can therefore persist independently prepared shards as they finish, while append_stored_range publishes all of their typed handles on one shared source range. The prepared convenience stores the vector first and then performs the same logical append.

The Succinct recipe emits both repeated attributes for every shard:

range @ seg_succinct*: raw_archives,
        seg_succinct_rank9*: rank9_accelerators

The facts are intentionally unordered. Parsing loads each Rank9 header, reads its embedded raw-source handle, and requires a bijection: every declared raw archive has exactly one accelerator, every accelerator names a declared raw archive, and no source is claimed twice. Attachment then uses SuccinctArchive::from_blob_pair and never rebuilds Rank9 data on the read path. A range with no pairs remains a complete empty/contentless certificate.

The BM25 recipe instead emits seg_bm25* handles to PortableBM25Blob. Its durable logical value is the document set plus sparse positive exact u32 term frequencies; compaction is document union and pointwise maximum frequency. Native SuccinctBM25Blob / CompressedUniverse layout is deliberately absent from range identity and persistence. The portable carrier derives document lengths, IDF, and scores only after the selected cover has been canonically joined, so physical LSM shape cannot alter ranking. HNSW remains a separately typed native succinct artifact.

Exact compaction

Compaction may merge ranges only when their logical commit sets are disjoint and their union is order-convex. The algorithm is deliberately proof-shaped:

1. Expand and validate every victim's exact interval.
2. Form their set union U, rejecting overlap.
3. Derive S' = minima(U) and E' = maxima(U).
4. Accept only if R(S',E') == U.

The equality check is the correctness gate. In a chain A < B < C, compacting [A,A] with [C,C] is rejected because the candidate hull [A,C] would add the missing commit B. Adjacent [A,A] + [B,B] correctly becomes [A,B].

The base-FANOUT LSM carry normally merges consecutive blocks of the global parents-first commit order, so its victim unions are convex. Imported or manually assembled manifests receive no such assumption and must fail closed when the equality does not hold.

Whole-cover audit

For each recipe, live ranges across all LSM levels form one partition:

pairwise-disjoint union(ranges) == ancestors(branch HEAD)

validate_exact_frontier_cover performs this audit and catches interior holes, overlapping live ranges, and artifacts from unreachable forks. The singleton helper validate_exact_cover covers the common branch-HEAD case. An empty frontier requires zero ranges. Different recipes may use different partitions; overlap across those independent covers is expected.

Filtered or contentless commits still belong to a cover. Their canonical empty range record contains the recipe and boundaries with zero typed handles; omitting the record could not distinguish “certified empty” from “missing or stale.”

Commit batches

range_for_commit_set derives the inclusive boundaries of a nonempty convex commit batch. For repository push hooks, its input is exactly the newly reachable parents-first commit set. The prior base_head is an exclusion cursor, not an inclusive range start.

For example, after a conflict where winner A and losing sibling B are joined by merge M, retrying from base A introduces {B,M} and produces the range [B,M]. Before extending an existing cover, the integration must also prove that the old base is an ancestor of the new head. Rewinds and unrelated head replacements require a rebuild; certifying them incrementally would retain commits outside the new head's history.

Commit Selectors

Commit selectors describe which commits to load from a workspace. They give callers a reusable vocabulary for requests such as "let me work with the changes from last week" or "show the commits that touched this entity". The selector itself only decides which commits participate; the data behind those commits is materialized into a Checkout (which derefs to TribleSet) by Workspace::checkout so the rest of the system can query it like any other dataset.

At checkout time the Workspace::checkout method accepts any type implementing the CommitSelector trait and returns a Checkout built from the selected commits. Selectors can be as small as a single commit handle or as expressive as a filtered slice of history. This chapter walks through the available building blocks, how they compose, and how they relate to Git's revision grammar.

Range semantics

Range selectors mirror Git's two‑dot syntax. A selector of the form a..b starts from b and walks its reachable ancestors. The walk continues until it encounters a commit selected by a, at which point the descent along that branch stops. The start boundary is exclusive while the end boundary is inclusive: commits selected by a are omitted from the result, but the commit(s) provided by b are included alongside any additional ancestors reached through other branches. The shorthands behave as follows:

• ..b is equivalent to empty()..b and gathers b plus all of its ancestors.
• a.. defaults the end boundary to HEAD, collecting HEAD and its ancestors until the walk meets a.
• .. expands to HEAD and every ancestor reachable from it.

Because the range semantics differ slightly from Git, you can wrap the start boundary in ancestors to reproduce Git's set-difference behaviour when parity is required: ancestors(a)..b matches git log a..b.

// Check out the entire history of the current branch.
// `..` walks all history from head.
let history = ws.checkout(..)?;

// Equivalent to `git log feature..main`
let delta = ws.checkout(ancestors(feature_tip)..main_tip)?;

Ranges are concise and map directly onto the ancestry walks exposed by the repository. Combinations such as "ancestors of B that exclude commits reachable from A" fall out naturally from existing selectors (ancestors(A)..B). When a query needs additional refinement, layer selectors like filter, reach for helpers such as symmetric_diff, or implement a small CommitSelector that post-processes the resulting CommitSet with union, intersection, or difference before handing it back to checkout.

Short-circuiting at the boundary avoids re-walking history that previous selectors already covered, but it still requires visiting every reachable commit when the start selector is empty. Long-lived queries that continuously ingest history can avoid that re-walk by carrying forward a specific commit as the new start boundary. If a prior run stopped at previous_head, the next iteration can use the range previous_head..new_head to gather only the commits introduced since the last checkout.

Implemented selectors

CommitSelector is implemented for:

• CommitHandle – a single commit.
• CommitSet – implements CommitSelector by returning itself. Useful as checkout(full.commits()..) for incremental deltas.
• Option<CommitHandle> – None returns the empty set, Some(h) returns a singleton.
• Vec<CommitHandle> and &[CommitHandle] – explicit lists of commits.
• ancestors(selector) – all commits reachable from any commit in the selector, plus the commits themselves. Accepts any CommitSelector, not just CommitHandle.
• nth_ancestors(selector, n) – walks every commit in selector back n parent steps through all parent links (merges included).
• parents(selector) – direct parents of the commits in the selector. Accepts any CommitSelector.
• symmetric_diff(a, b) – commits reachable from either a or b but not both. Both arguments accept any CommitSelector.
• Set combinators that operate on two selectors:
  • union(left, right) – commits returned by either selector.
  • intersect(left, right) – commits returned by both selectors.
  • difference(left, right) – commits from left that are not also returned by right.
• Standard ranges: a..b, a.., ..b and .. that stop walking once the start boundary is encountered.
• filter(selector, predicate) – retains commits for which predicate returns true.
• history_of(entity) – commits touching a specific entity (built on filter).
• time_range(start, end) – commits whose timestamps intersect the inclusive range.

The range primitives intentionally diverge from Git's subtraction semantics. a..b walks the history from b toward the start boundary and stops as soon as it rediscovers a commit yielded by a. Workspace checkouts frequently reuse an earlier selector—such as previous_head..new_head—so short-circuiting at the boundary saves re-walking the entire ancestor closure every time the selector runs. When you need Git's behaviour you can wrap the start in ancestors, trading the extra reachability work for parity with git log.

Because selectors already operate on CommitSet patches, composing new behaviour is largely a matter of combining those sets. The existing selectors in this chapter are implemented using the same building blocks that are available to library users, making it straightforward to prototype project-specific combinators without altering the Workspace::checkout API.

Set combinators

union, intersect, and difference wrap two other selectors and forward the results through the equivalent set operations exposed by PATCH. Reach for these helpers when you want to combine selectors without writing a custom CommitSelector implementation. Each helper accepts any selector combination and returns the corresponding CommitSet:

use triblespace::core::repo::{ancestors, difference, intersect, union};

// Everything reachable from either branch tip.
let combined = ws.checkout(union(ancestors(main), ancestors(feature)))?;

// Only the commits both branches share.
let shared = ws.checkout(intersect(ancestors(main), ancestors(feature)))?;

// Feature-only commits without the mainline history.
let feature_delta = ws.checkout(difference(ancestors(feature), ancestors(main)))?;

Composing selectors

Selectors implement the CommitSelector trait, so they can wrap one another to express complex logic. The pattern is to start with a broad set—often ancestors(ws.head())—and then refine it. The first snippet below layers a time window with an entity filter before handing the selector to Workspace::checkout, and the follow-up demonstrates the built-in intersect selector to combine two existing selectors.

use hifitime::Epoch;
use triblespace::core::repo::{filter, history_of, intersect, time_range};

let cutoff = Epoch::from_unix_seconds(1_701_696_000.0); // 2023-12-01
let recent = filter(time_range(cutoff, Epoch::now().unwrap()), |_, payload| {
    payload.iter().any(|trible| trible.e() == &my_entity)
});

let relevant = ws.checkout(recent)?;

// Start from the result and zero in on a single entity.
let entity_history = ws.checkout(history_of(my_entity))?;

let recent_entity_commits = ws.checkout(intersect(
    time_range(cutoff, Epoch::now().unwrap()),
    history_of(my_entity),
))?;

Filtering commits

The filter selector wraps another selector and keeps only the commits for which a user provided closure returns true. The closure receives the commit metadata and its payload, allowing inspection of authors, timestamps or the data itself. Selectors compose, so you can further narrow a range:

use hifitime::Epoch;
use triblespace::core::repo::{filter, time_range};

let since = Epoch::from_unix_seconds(1_609_459_200.0); // 2020-12-01
let now = Epoch::now().unwrap();
let recent = ws.checkout(filter(time_range(since, now), |_, payload| {
    payload.iter().any(|t| t.e() == &my_entity)
}))?;

Higher level helpers can build on this primitive. For example history_of(entity) filters ancestors(HEAD) to commits touching a specific entity:

let changes = ws.checkout(history_of(my_entity))?;

When debugging a complicated selector, start by checking out the wider range and logging the commit metadata. Verifying the intermediate results catches off-by-one errors early and helps spot situations where a filter excludes or includes more history than expected.

Git Comparison

The table below summarizes Git's revision grammar. Each row links back to the official documentation. Forms that rely on reflogs or reference objects other than commits are listed for completeness but are unlikely to be implemented.

Only a subset of Git's revision grammar will likely be supported. Selectors relying on reflog history, remote configuration, or searching commits and blobs add complexity with little benefit for workspace checkout. They are listed above for completeness but remain unplanned for now.

Note: range(A, B) differs subtly from Git's two-dot syntax. It walks parents from B until a commit from A is encountered instead of subtracting the entire ancestor closure of A. Use ancestors(A)..B for Git's behaviour.

TimeRange

Commits record when they were made via a timestamp attribute of type NsTAIInterval. When creating a commit this interval defaults to (now, now) but other tools could provide a wider range if the clock precision is uncertain. The TimeRange selector uses this interval to gather commits whose timestamps fall between two Epoch values:

use hifitime::Epoch;
use triblespace::core::repo::time_range;

let since = Epoch::from_unix_seconds(1_609_459_200.0); // 2020-12-01
let now = Epoch::now().unwrap();
let tribles = ws.checkout(time_range(since, now))?;

This walks the history from HEAD and returns only those commits whose timestamp interval intersects the inclusive range.

Internally it uses filter(ancestors(HEAD), ..) to check each commit's timestamp range.

Garbage Collection and Forgetting

Repositories grow over time as commits, branch metadata, and user blobs accumulate. Because every blob is content addressed and immutable, nothing is ever overwritten and there is no automatic reclamation when branches move or objects become orphaned. To keep disk usage in check a repository can periodically forget blobs that are no longer referenced.

Forgetting is deliberately conservative. It only removes local copies, so re-synchronising from a peer or pushing a commit that references an "forgotten" blob will transparently restore it. Forgetting therefore complements the monotonic model: history never disappears globally, but any node can opt-out of retaining data it no longer needs.

The main challenge is deciding which blobs are still reachable without reconstructing every TribleSet. The sections below outline how the repository module solves that problem and how you can compose the building blocks in your own tools.

Understanding the Roots

The walk begins with a root set—the handles you know must stay alive. In a typical repository this includes the metadata blob for each branch (which in turn names the commit heads), tags, or any additional anchors your deployment requires. Roots are cheap to enumerate: walk the branch store via BranchStore::branches and load each branch head, or read the subset of metadata relevant to the retention policy you are enforcing. Everything reachable from those handles will be retained by the traversal; everything else is eligible for forgetting.

Direct and Recursive Policy Roots

Not every hash written inside a retained blob is an ownership edge. Collection ledger records are the important counterexample: a MERGE names its inputs and result to state an algebraic equation, but retaining that record should not by itself pin every historical physical input forever. RetentionRoots therefore has two sorts:

• a direct root retains exactly the named blob; and
• a recursive root retains the blob and all resident descendants found by conservative traversal.

Strong collection retention follows only signed ground truth. For every locally authorized, admitted COMMIT, the descriptor, signed data, and metadata handles are recursive roots, so all of their resident attachments remain owned. The descriptor is the canonical (scope, representation, recipe) SimpleArchive; its 32-byte content handle is the CollectionId carried by the commit. The native commit record is preserved by CollectionStore rather than represented as a blob root. Planning fails if any required descriptor, data, or metadata blob is absent.

Unsigned MERGE and DERIVE records are reproducible cache work. They add no strong roots even when validation accepts them and their equations are active; their named inputs, results, and otherwise-unowned descriptor blobs may all be collected. Conservative Pile and Yard rewrites preserve the equation records themselves as immutable ledger evidence, but that preservation creates no blob ownership edge. A future cache planner can choose useful materializations under a separate budget without letting append-only unsigned claims manufacture durable ownership. This boundary also means the strong planner needs neither a requested-view set nor persistent validation-verdict machinery: admitted commits themselves determine the collections that are retained.

The resulting roots compose with both storage paths. Yard's collect and compact require them as explicit policy roots; callers pass an empty RetentionRoots deliberately when legacy strong pins are the only strong roots. Both Yard collection and Pile::rewrite_retained_into strictly verify a native COMMIT signature before its fields can add implicit roots. They preserve every immutable record, including invalid and partially synchronized records, but recursively retain only dependencies named by valid commits which are resident in the relevant Pile snapshot or live in the Yard. An absent dependency therefore remains available for later synchronization instead of permanently poisoning local retention. Caller-supplied RetentionRoots keep their existing backend semantics; in particular, a retained Pile rewrite still fails loud when an explicitly selected blob is absent.

The Pile rewrite also recursively retains and recreates every active branch pin. Legacy V3 collection records are different: their 16-byte definition identities predate descriptor handles, so they are preserved byte-for-byte as inert physical evidence but grant no current collection authority and own no blobs. Current LocalCellStore values are recursive local roots and are recreated by retained pile rewrites. That keeps operational policy alive without granting collection authority or exposing a branch to gossip. Weak wants are an explicit rewrite choice. Preserving them copies their demand markers but does not promote the requested blob to an ownership root; dropping them omits the markers entirely.

RetentionRoots is deliberately a pure, ephemeral plan rather than a retained collection registry. Every later collection or rewrite must rediscover records, apply the local signer/authorization policy, resolve the claims, and supply a fresh plan for all admitted commits. Ordinary Pile and Yard rewrites independently apply the conservative rule above: preserve every native record, then recursively retain the resident descriptor, data, and metadata closure of every strictly verified current COMMIT.

Generic-envelope records whose kind is unknown to the running binary form a harder boundary: their bytes have a known span and ordinary replay can safely project them away, but the reader cannot know whether their semantics own known blobs. Pile::rewrite_retained_into and Yard collection, compaction, and reclaim therefore refuse before changing destination bytes or live sets when any opaque record is present. Upgrade to tooling that understands the kind before performing destructive retention.

Conservative Reachability

Every commit and branch metadata record is stored as a SimpleArchive. The archive encodes a canonical TribleSet as 64-byte tribles, each containing a 32-byte value column. The blob store does not track which handles correspond to archives, so the collector treats every blob identically: it scans the raw bytes in 32-byte chunks and treats each chunk as a candidate handle. Chunks that are not value columns—for example the combined entity/attribute half of a trible or arbitrary attachment bytes—are discarded when the candidate lookup fails. If a chunk matches the hash of a blob in the store we assume it is a reference, regardless of the attribute type. With 32-byte hashes the odds of a random collision are negligible, so the scan may keep extra blobs but will not drop a referenced one.

Content blobs that are not SimpleArchive instances (for example large binary attachments) therefore behave as leaves: the traversal still scans them, but because no additional lookups succeed they contribute no further handles. They become reachable when some archive references their handle and are otherwise eligible for forgetting.

Traversal Algorithm

1. Enumerate all branches and load their metadata blobs.
2. Extract candidate handles from the metadata. This reveals the current commit head along with any other referenced blobs.
3. Recursively walk the discovered commits and content blobs. Each blob is scanned in 32-byte steps; any chunk whose lookup succeeds is enqueued instead of deserialising the archive.
4. Stream the discovered handles into whatever operation you need. The reachable helper returns an iterator of handles, so you can retain them, transfer them into another store, or collect them into whichever structure your workflow expects.

Because the traversal is purely additive you can compose additional filters or instrumentation as needed—for example to track how many objects are held alive by a particular branch or to export a log of missing blobs for diagnostics.

Automating the Walk

The repository module already provides most of the required plumbing. The reachable helper exposes the traversal as a reusable iterator so you can compose other operations along the way, while transfer duplicates whichever handles you feed it. The in-memory MemoryBlobStore can retain live blobs, duplicate them into a scratch store, and report how many handles were touched without writing bespoke walkers:

use triblespace::core::blob::memoryblobstore::MemoryBlobStore;
use triblespace::core::repo::{self, BlobStoreKeep, BlobStoreList, BranchStore};
use triblespace::core::inline::encodings::hash::Blake3;

let mut store = MemoryBlobStore::default();
// ... populate the store or import data ...

let mut branch_store = /* your BranchStore implementation */;
let reader = store.reader()?;

// Collect the branch metadata handles we want to keep alive.
let mut roots = Vec::new();
for branch_id in branch_store.branches()? {
    if let Some(meta) = branch_store.head(branch_id?)? {
        roots.push(meta.transmute());
    }
}

// Trim unreachable blobs in-place.
store.keep(repo::reachable(&reader, roots.clone()));

// Optionally copy the same reachable blobs into another store.
let mut scratch = MemoryBlobStore::default();
let visited = repo::reachable(&reader, roots.clone()).count();
let mapping: Vec<_> = repo::transfer(
    &reader,
    &mut scratch,
    repo::reachable(&reader, roots),
)
.collect::<Result<_, _>>()?;

println!("visited {} blobs, copied {}", visited, mapping.len());
println!("rewrote {} handles", mapping.len());

In practice you will seed the walker with the handles extracted from branch metadata or other root sets instead of iterating the entire store. The helper takes any IntoIterator of handles, so once branch heads (and other roots) have been identified, they can be fed directly into the traversal without writing custom queues or visitor logic. Passing the resulting iterator to MemoryBlobStore::keep or repo::transfer makes it easy to implement mark-and-sweep collectors or selective replication pipelines without duplicating traversal code.

When you already have metadata represented as a TribleSet, the potential_handles helper converts its value column into the conservative stream of Handle<H, UnknownBlob> instances expected by these operations.

Operational Tips

• Schedule forgetting deliberately. Trigger it after large merges or imports rather than on every commit so you amortise the walk over meaningful changes.
• Watch available storage. Because forgetting only affects the local node, replicating from a peer may temporarily reintroduce forgotten blobs. Consider monitoring disk usage and budgeting headroom for such bursts.
• Keep a safety margin. If you are unsure whether a handle should be retained, include it in the root set. Collisions between 32-byte handles are effectively impossible, so cautious root selection simply preserves anything that might be referenced.

Future Work

The public API for triggering garbage collection is still evolving. The composition-friendly walker introduced above is one building block; future work could layer additional convenience helpers or integrate with external retention policies. Conservative reachability by scanning SimpleArchive bytes remains the foundation for safe space reclamation.

Distributed Sync

The triblespace-net crate adds peer-to-peer synchronization over iroh: gossip for HEAD announcements, a DHT for content discovery, direct QUIC for bulk transfer. The user-visible surface is a single wrapper type — Peer<S> — that makes any triblespace store also a node on a distributed graph, without changing how the storage traits look from outside.

Enable it through the facade crate's net feature:

[dependencies]
triblespace = { version = "x.y.z", features = ["net"] }

use triblespace::net::peer::{Peer, PeerConfig};

Mental Model

Peer<S> takes any S: BlobStore + BlobStorePut + BranchStore<Blake3> and wraps it into a node that participates in the iroh network. Two layers of behavior are bolted onto the normal storage trait calls:

• Reads auto-drain incoming gossip. Every call through reader(), head(id), or branches() transparently pulls any pending NetEvents from the network thread into the wrapped store and re-publishes any deltas from external writers (e.g. another process appended to the same pile file). Mirrors Pile::refresh — the explicit Peer::refresh method is available for tight loops, but normal storage use Just Works.
• Writes auto-publish. Calls through put / update delegate to the inner store and then announce blobs to the DHT and gossip branch HEADs to the topic mesh, all via the background network thread.

The network thread is a private implementation detail: Peer::new spawns it; Peer::drop winds it down. Async stays jailed inside that thread — the storage traits stay sync.

use std::collections::HashSet;

let pile = triblespace::core::repo::pile::Pile::open(path)?;
let peer = Peer::new(pile, signing_key.clone(), PeerConfig {
    peers: vec![bootstrap_endpoint_id],
    gossip: true,                            // false = pull/serve-only
    // Auth is mandatory — see the Capability Auth chapter for the
    // team-root + self_cap setup, or run `trible team create`.
    // The team root pubkey doubles as the gossip mesh id when
    // `gossip = true`.
    team_root: signing_key.verifying_key(),  // single-user team-of-one
    self_cap: [0u8; 32],
});
let mut repo = Repository::new(peer, signing_key, TribleSet::new())?;
// From here it's just a Repository — commit, push, pull, query.

Tracking Branches

When a peer learns about a remote HEAD — via gossip arrival or an explicit track call — it materializes the data as a tracking branch: a local branch whose metadata carries tracking_remote_branch (the remote branch id), tracking_peer (the publisher's key), and remote_name (instead of the usual metadata::name). This keeps tracking branches invisible to normal discovery: ensure_branch(name) won't find them, lookup_branch(name) returns only your own branches, and the is_tracking_branch filter lets the Peer avoid re-gossiping its mirrors back to the network.

Tracking branches are your sandbox for remote state. Merging them into your own same-named branch is how you "accept" the remote changes (see the Merge Flow section below).

Local renewal decisions, pending capability requests, and the node's current team capabilities are not branches at all. They live behind LocalCellStore, which has no enumeration or gossip operation; a peer therefore cannot publish them as HEAD updates. During migration, the publisher still recognizes and suppresses the old local_only_pin marker so merely upgrading a node cannot leak policy heads written by an older binary. The guard checks snapshot membership without reading a missing blob, so classification cannot turn a private or damaged legacy head into a network want.

Transports

Three protocols ride on the same iroh endpoint:

• Gossip mesh (HyParView + PlumTree via iroh-gossip): all peers on the same topic receive every branch HEAD announcement. 81-byte messages: a 1-byte tag, 16-byte branch id, 32-byte HEAD hash, 32-byte publisher key. Eventual delivery; duplicates deduped on the wire.
• DHT (via iroh-dht): content discovery for blobs. On write, announce_provider(blob_hash) tells the DHT "I have this blob." On read, find_providers(blob_hash) returns peers to fetch from. Content-addressed by design — any provider with the right bytes passes blake3 verification.
• Direct QUIC RPC (PILE_SYNC_ALPN = "/triblespace/pile-sync/4"): point-to-point operations that don't fit the gossip model — listing a peer's branches, asking for a specific branch's HEAD, fetching a single blob by hash, enumerating a blob's child references. One stream per operation, stream FIN signals end, nil sentinels (zero branch ids / zero hashes) terminate sequences. The protocol's first stream on every connection must be OP_AUTH — see the Capability Auth chapter for the full handshake and scope-gating semantics.

track vs fetch

Two primitives cover the two levels of "go get this":

• peer.track(endpoint_id, branch_id) — fire-and-forget. Opens a QUIC stream to the remote, asks for its HEAD, then walks the reachable closure of blobs (BFS over the parent-to-children graph via op_children, pulling each blob through DHT-first then peer-fallback). When the whole closure has landed locally, emits a NetEvent::Head that the Peer drains into a freshly-materialized tracking branch. The tracking branch only advances after every referenced blob is in the pile — external readers either see the old HEAD (with its complete closure) or the new HEAD (with its closure), never a half-torn state.
• peer.fetch::<T, Sch>(endpoint_id, handle) — blocking single-blob RPC. Pass a typed handle, pick what comes out: Blob<Sch> for bytes-only with zero decode cost, or the decoded type (TribleSet, anybytes::View<str>, etc.) for the deserialized value. The bytes land in the wrapped store via BlobStorePut::put and the return value is decoded from those same bytes.

For the common "pull a branch by name" workflow, peer.pull_branch( endpoint_id, name) composes them: list the remote's branches, pull each metadata blob via fetch, query for metadata::name, find the match, hand off to track, block until the tracking branch materializes. Returns the local tracking branch id ready to merge.

Merge Flow

Once a tracking branch exists, merging it into its same-named local branch is the normal Repository workflow plus one helper:

use triblespace::net::tracking::{merge_tracking_into_local, MergeOutcome};

match merge_tracking_into_local(&mut repo, tracking_id, "main")? {
    MergeOutcome::Empty      => { /* tracking had no head yet */ }
    MergeOutcome::UpToDate   => { /* local already at that state */ }
    MergeOutcome::Merged { new_head } => {
        // local "main" advanced — either fast-forward or a real
        // merge commit, decided by Workspace::merge_commit.
    }
}

Under the hood that's ensure_branch("main") + pull tracking workspace + pull local workspace + merge_commit(remote_head) + conditional push. The merge_commit call picks no-op / fast-forward / merge commit based on ancestor-walking.

For long-running sync daemons, the same helper runs in a loop over every tracking branch on every refresh tick.

Convergence rounds. When two peers diverge on the same branch:

• Sequential gossip (one peer's merge lands before the other's starts) converges in one round-pair. The first side produces a merge commit AM containing both original commits as parents; the second side sees AM, finds its own head in ancestors(AM), and fast-forwards.
• Parallel gossip (both peers merge before either sees the other's merge) also converges in one round-pair — and without producing a merge commit on the second side. Merge commits are content-addressed: they carry no author-specific bits (no signature, no created_at, entity id derived intrinsically from the parent set via entity!'s content-hash form), so two peers merging the same parent set produce bit-identical merge commits that dedup via blob hash alone.

Either way the system converges in one round-pair. The tests in triblespace-net/tests/two_peer_convergence.rs exercise both cases and serve as regression coverage for the property. Content-addressed merges are also why merge_tracking_into_local is safe to run in a tight polling loop without worrying about merge-commit churn.

Ordering Under Pressure

Gossip is eventually consistent, which means a flood of HEAD updates can arrive out of order: HEAD_1 → HEAD_2 → HEAD_3 where HEAD_1's closure happens to take longer over the DHT and completes after HEAD_3 has already advanced the tracking branch. Without protection, HEAD_1 would clobber HEAD_3 and the branch would regress.

To prevent this, branch_metadata stamps every published branch metadata blob with metadata::updated_at: NsTAIInterval from Epoch::now(). TAI is strictly monotone (no leap-second jumps). update_tracking_branch reads the stamp from both the current and incoming metadata and rejects updates whose timestamp is not strictly newer — logged as [tracking] skip stale update for branch <bid> for observability. The synthesized tracking branch metadata mirrors the remote's timestamp so subsequent comparisons share a reference frame.

Tradeoff: publishing the same HEAD twice at different moments produces different metadata blob hashes now (the timestamps differ). Gossip convergence degrades slightly — duplicate blobs for the same semantic state — but correctness is preserved and regressions are eliminated.

CLI Surface

The trible CLI exposes sync via the pile net subcommand:

trible pile net identity [--key PATH]
    Print this node's iroh identity (generates a key if needed).

trible pile net sync <PILE> [--peers ...] [--key PATH]
    Long-running bidirectional sync on the team's gossip mesh.
    The mesh is identified by the team root pubkey directly (no
    separate --topic flag): every team has exactly one mesh,
    derived from its identity. Auto-merges incoming tracking
    branches into same-named local ones every tick. Reads
    `TRIBLE_TEAM_ROOT` and `TRIBLE_TEAM_CAP` env vars for multi-
    user team operation; falls back to single-user team-of-one
    using the node's own pubkey when those aren't set.

trible pile net pull <PILE> <REMOTE> --branch NAME [--key PATH]
    One-shot pull of a named branch from a specific peer (REMOTE is
    the peer's iroh node id, 64-char hex). Pull-only mode — no gossip
    subscription, direct QUIC + DHT fetch, materialize a tracking
    branch, merge into local. Useful for "give me a copy of that
    project" workflows. Same env-var fallback as `sync`.

trible team {create, invite, request-join, approve, retract, list,
              list-pending, list-issued, show}
    Team capability lifecycle — see the Capability Auth chapter.

What's Deferred

A few structural improvements the design discussion has surfaced but that aren't implemented yet:

• Incremental commit-chain advance. Today the tracking branch only moves when the whole reachable closure of a HEAD is local. Under sustained gossip pressure on large histories, we could fall arbitrarily behind. A git-like incremental walker (parallel-fetch commit contents, advance the tracking branch commit-by-commit in topological order) would give steady progress at the cost of exposing intermediate states to readers.
• CachingStore<P> with on-miss fetch. A middleware that wraps a Peer and does DHT-backed on-miss fetching inside BlobStoreGet::get, with a policy callback for gating by size / schema / context. Would cover the "cache eviction + lazy fetch" workflows that current eager-only semantics can't.
• Schema-aware traversal in track. op_children today scans parent blob bytes for 32-byte chunks that look like hashes. That's cheap and peer-agnostic but pulls more than strictly necessary when a blob contains handle-sized non-hash data. A schema-aware walker that parses each blob as its declared schema and enumerates referenced handles could be precise, but adds significant traversal complexity.

All three are additive: the current model stays correct as a strict-closure / eager-only baseline that these improvements build on.

Capability Auth

The triblespace-net crate ships a chain-of-trust capability system on top of iroh's TLS-verified peer identities. Every connection on the /triblespace/pile-sync/4 ALPN must present a capability before any other op is served. This chapter explains the team model, the CLI lifecycle, and the two-tier scope gate the relay enforces.

For the design rationale (single team root vs multi-root web-of-trust, sign-the-bytes convention, embedded parent sig optimisation), see the companion design notes in triblespace-core/src/repo/capability.rs's module-level docs.

Model

A team has one immutable root keypair, generated once at team creation and used to sign exactly one capability — the founder's. After that the root keypair is archived; it never operates online. Like a CA: bootstrapping authority, not runtime authority.

All other capabilities chain off the founder's via delegation. Any holder of a capability can sign a sub-capability for someone else, as long as the sub-cap's scope is a subset of their own. Verification walks the chain back to the team root.

Each capability is two blobs stored in the pile:

• A cap blob — a TribleSet carrying cap_subject (the pubkey this cap authorises), cap_issuer (the pubkey that signed it), cap_scope_root (the entity id anchoring the scope facts inside the same blob), and metadata::expires_at.
• A sig blob — a TribleSet with sig_signs (handle of the cap blob) plus attestation::signed_by, attestation::signature_r, and attestation::signature_s, reusing the shared structural attestation attributes.

Signatures attest to the cap blob's canonical bytes (matching how Workspace::commit signs commit metadata), not to a hash of those bytes — keeping signatures hash-agnostic across any future change to the handle scheme.

Non-root caps embed their parent's signature inline as a sub-entity within the cap blob (cap_embedded_parent_sig). This halves cold-cache verification fetch counts: at chain depth N, the verifier needs N+1 blobs instead of 2N+1.

Team Lifecycle (CLI)

The trible team subcommands cover the full lifecycle. All four operations work directly against a pile file — they don't require the network thread.

trible team create --pile PATH [--key KEY_PATH]
    Mint a new team root keypair, sign the founder's capability with
    it, and write both into the pile. Prints the team root pubkey
    (publish this to peers), the team root SECRET (archive offline),
    and the founder's cap-sig handle (the founder's "credential" for
    OP_AUTH).

trible team invite --pile PATH --team-root HEX --cap HEX --key ISSUER
                   --invitee HEX --scope (read|write|admin)
                   [--branch HEX]...
    Issue a sub-capability to another peer. ISSUER must hold a cap
    that subsumes the requested scope. The invitee's pubkey appears
    on its own (use `trible pile net identity` on the invitee's
    machine to print it). Prints the invitee's cap-sig handle.

trible team request-join --admin HEX --scope (read|write|admin)
                         [--key PATH] [--pile PATH]
    Send an OP_REQUEST_CAP to an admin's running daemon asking to
    be issued a capability. The admin sees the request on their
    pending-requests cell (`team list-pending`); after `team approve`
    the freshly-signed cap arrives via the auth-handshake ALPN.

trible team approve --pile PATH --entry HEX --team-root HEX
                    --cap HEX [--key PATH]
    Approve a pending request, sign the cap, dispatch it back to
    the requester, and add a renewal-policy entry so the local
    daemon keeps the cap renewed.

trible team retract --pile PATH --entry HEX
    Stop auto-renewing one (subject, scope) entry. The peer's
    chain dies at its next natural expiry. Pure local decision —
    no broadcast, no transitive cascade. This is the eviction
    primitive: there is no team-root-signed revocation blob in
    the descriptive-caps model.

trible team list --pile PATH
    Audit summary: per-cap detail line (issuer → subject, scope,
    expiry — sorted soonest-expiry-first).

trible team list-pending --pile PATH
    Incoming join requests awaiting approval.

trible team list-issued --pile PATH
    Renewal-policy entries this node is keeping renewed.

trible team show --pile PATH --cap HEX [--verify TEAM_ROOT_HEX]
    Walk one chain end-to-end. Prints each level with subject,
    issuer, scope, expiry, sig blob handle, cap blob handle, and
    a signer-matches-issuer (`✓` / `✗ MISMATCH`) check. Bounded
    by MAX_DEPTH=32; chains beyond root render the embedded
    parent sig as `(embedded in level above)`. Use when `list`
    shows a cap is present but a connection still fails — `show`
    surfaces structural mismatches (signer ≠ issuer, missing
    parent sig fields) that the summary view hides.

    `--verify <TEAM_ROOT_HEX>` (or env `TRIBLE_TEAM_ROOT`)
    additionally runs `verify_chain` against the given team root
    and reports `✓ VERIFIED` or `✗ FAILED — <VerifyError>` —
    the same code path the relay's `OP_AUTH` uses, so the
    result is the local-side rehearsal of what a real connection
    attempt would produce. Add `--expected-subject HEX` to
    override the default subject check (the leaf cap's declared
    `cap_subject`) for subject-substitution-attack detection.

A typical bootstrap flow:

# Founder, on machine A:
$ trible team create --pile team.pile --key founder.key
team root pubkey: 1a8a6a9d8ca1da67facab373de21233b...
team root SECRET: <archive offline>
founder cap (sig): 4e6e02d51c3676ece1eea9094f8e9d76...

# Invitee, on machine B:
$ trible pile net identity --key invitee.key
node: e825b3a8d387b4dae1720b0edcbfaa9e...

# Founder, on machine A:
$ trible team invite --pile team.pile \
    --team-root 1a8a6a9d... \
    --cap       4e6e02d5... \
    --key       founder.key \
    --invitee   e825b3a8... \
    --scope     read
issued cap (sig): 7afe59e7f895b23f05452ff7919e12e4...

The invitee then runs the relay (or any pile-net peer) with TRIBLE_TEAM_ROOT and TRIBLE_TEAM_CAP set:

$ TRIBLE_TEAM_ROOT=1a8a6a9d... \
  TRIBLE_TEAM_CAP=7afe59e7... \
  trible pile net sync /path/to/their.pile --peers <founder-id>

Without those env vars the peer falls back to a single-user team-of-one (team_root = signing_key.verifying_key()), which means only their own caps will pass — useful for solo workflows but rejects every other peer's cap.

Wire Protocol

Protocol v4 (/triblespace/pile-sync/4) makes auth mandatory:

The first stream on every connection must be OP_AUTH. The server fetches the referenced sig blob, walks back to the team root through embedded parent sigs and cap_parent handles, and either accepts (AUTH_OK = 0x00) or rejects (AUTH_REJECTED = 0x01). Subsequent streams on the same connection inherit that verified capability for the lifetime of the connection — there's no per-stream re-auth.

Streams sent before OP_AUTH or after AUTH_REJECTED are silently closed. The server doesn't leak a "you sent the wrong thing" error back to the client.

Two-Tier Scope Gate

Capabilities encode their scope as tribles hung off cap_scope_root:

• One or more metadata::tag: PERM_* triples granting permissions (PERM_READ, PERM_WRITE, PERM_ADMIN).
• Zero or more scope_branch: <branch_id> triples restricting the permission to a specific branch. An empty branch-restriction set means "all branches".

The relay enforces scope at two levels:

Branch level (OP_LIST, OP_HEAD)

VerifiedCapability::grants_read_on(branch) filters which branches the peer can see. Out-of-scope branches are silently dropped from OP_LIST responses; OP_HEAD for an out-of-scope branch returns NIL_HASH (indistinguishable from "branch doesn't exist", as far as the wire is concerned).

Blob level (OP_GET_BLOB, OP_CHILDREN)

A peer with branch-X-only scope could otherwise circumvent the branch gate by guessing or probing raw blob hashes from branch Y. The blob-level gate closes that hole: a hash is in scope only if it's reachable (via 32-byte child chunks) from at least one branch head the cap grants read on. Out-of-scope blobs surface as None (length = u64::MAX) on OP_GET_BLOB; OP_CHILDREN filters its returned list to in-scope hashes only.

Unrestricted caps (granted_branches() == None — no scope_branch tribles) short-circuit to "every present blob is in scope".

Permission semantics mirror scope_subsumes: PERM_WRITE and PERM_ADMIN imply PERM_READ; PERM_ADMIN is required to delegate sub-capabilities. The reachability scan is recomputed per request today; per-stream caching is a future optimisation for chain-walk-heavy workloads.

Eviction

There is no team-root-signed revocation blob. The descriptive-caps model evicts peers via per-issuer non-renewal: every cap carries a short natural expiry (default 30 days), the issuer's running daemon refreshes the cap before that expiry as long as a renewal-policy entry says it should, and team retract deletes the entry. The peer's chain dies at the next natural expiry. The decision is local to the issuer — nothing propagates, nothing cascades, nothing has to be signed by the team root.

This trades the "instant network-wide revocation" property for several real wins:

• No revocation rescan on every snapshot refresh. Previously update_snapshot walked every blob looking for (rev, sig) pairs signed by the team root; that was a CPU hotspot on quiescent peers. The refresh path is now a near-no-op snapshot swap.
• No HashSet<VerifyingKey> shared state. The old model needed a process-wide revocation set, written from the snapshot scanner and read from every chain verification. Removing it dropped a cross-thread synchronisation point.
• No team-root keypair in normal operation. Issuing a revocation required the team root SECRET to sign. Now the root SECRET lives in cold storage; every day-to-day operation (invite, approve, retract) uses a regular admin cap.
• Monotonic gossip. The wire protocol no longer has to gossip revocation blobs as a special category that has to land before the affected cap is verified. Caps and renewals are first-class blobs; everything else is local issuer policy.

The trade-off: there's no way to immediately invalidate a compromised key network-wide. The mitigation is to keep natural expiries short (the 30-day default is a starting point, not a hard rule) and to ensure issuers stop renewing the moment they notice. For acutely sensitive teams the natural-expiry window can be tightened to hours.

Renewal happens via the same OP_DELIVER_CAP path that team approve uses: the issuer's daemon signs a fresh cap with a later expiry, dispatches it to the subject's daemon over the auth-handshake ALPN, and the subject records it in the team-cap cell. team list-issued shows the renewal-policy entries this node is keeping renewed; team retract --entry HEX marks one as non-renewing.

These three pieces of mutable policy—pending requests, renewal entries, and current team capabilities—are stored as ordinary queryable SimpleArchive values behind three local cells. Cells are recursive local retention roots, but they are neither branch authority nor wants and have no gossip surface. All teams share one team-cap cell value; replacing one intrinsic team entry leaves the other teams unchanged.

Cell replacement is atomic, but editing a whole archive is deliberately not a cross-process transaction. Two processes that read the same cell and then replace it can lose one another's otherwise-disjoint edits: the later replacement wins for the whole value. Until policy mutations are routed through the daemon as the single writer, stop pile net sync while running policy-mutating CLI commands such as team invite, team approve, and team retract, then restart it. Read-only commands may run concurrently.

An upgraded binary does not yet import policy written in the former local-policy-pin representation. Those legacy heads remain conservatively suppressed from gossip, so the upgrade cannot disclose them, but renewal, pending-request, and team-cap state must be migrated or re-established before the new cell-backed policy sees it. Removing that guard depends on landing and running the explicit legacy migration.

PeerConfig Surface

use triblespace::net::peer::{Peer, PeerConfig};

let pile = triblespace::core::repo::pile::Pile::open(path)?;
let peer = Peer::new(pile, signing_key.clone(), PeerConfig {
    peers: vec![bootstrap_endpoint_id],
    gossip: true,                           // false = pull/serve-only
    team_root: team_root_pubkey,            // 32 bytes — the team's CA AND
                                            // the gossip mesh id when gossip=true
    self_cap: my_own_cap_sig_handle,        // what we present on OP_AUTH
});

There's no Default impl: every peer construction site must specify a team root because auth is mandatory. The CLI's single-user team-of-one fallback sets team_root = signing_key.verifying_key() and self_cap = [0u8; 32] (which the remote rejects, signalling that multi-user operation needs the env vars).

For a hosted relay running for a team, the operator only needs:

• 32 bytes: the team root pubkey
• 32 bytes: the relay's own cap-sig handle (the team grants it a read-or-better cap and the operator pastes that handle into the config)

That's it. No per-user accounts, no shared secrets, no team configuration database. Caps live in the pile alongside everything else and gossip propagates them naturally.

Descriptive Structural Typing and the find! Idiom

This chapter documents the mental model and idioms we recommend when working with tribles. The model is intentionally descriptive: queries declare the shape of the data you want to see rather than prescribing a single concrete Rust type for every entity. This gives you the flexibility to keep the full graph around and to materialize only the view you need, when you need it.

Reading the chapter sequentially should equip you to:

1. talk about entities in terms of the fields they expose rather than the structs you wish they were,
2. design APIs that carry just enough information (a workspace, a checkout, an id) to ask for more data later, and
3. know when it is worth materializing a typed projection and when the descriptive view is already the best representation.

Key ideas at a glance

• Attributes are typed fields (unlike untyped RDF predicates).
• An entity in tribles is a structural record: a bag of typed fields.
• attributes! accepts explicit ids for shared columns and can derive deterministic ids from a name + encoding when you omit the hex literal; use the derived form for quick, local attributes and reserve explicit ids for published protocols.
• find! patterns are descriptive type checks / projections: they select entities that match a requested shape.
• entity! constructs ad‑hoc entities (like struct literals).
• Reified kinds/tags are attached via metadata::tag (GenId); projects often export canonical KIND_* constants you can pattern-match directly against.
• Inline encoding entities are tagged with metadata::KIND_INLINE_ENCODING; blob encoding entities with metadata::KIND_BLOB_ENCODING.
• Prefer passing the Workspace + the checkout result (TribleSet) and an entity id around — only materialize a concrete Rust view when required.
• Strongly prefer operating on the tuples returned by find!; wrapper structs should exist only as grudging adapters for APIs that demand them.

Why "descriptive" not "prescriptive"?

In a prescriptive system you define a named struct (type), commit to it, and force conversions at boundaries. Tribles instead let you describe the fields you need at call sites. That keeps code resilient to schema evolution and avoids unnecessary unfolding of the graph.

In linguistic terms: instead of insisting every entity be declared as CategoryX, you ask "show me entities that have fields A and B" and work with those. If an entity also has field C that's fine — it simply matches the descriptive pattern.

Type theory mapping (short)

• Structural typing: types are shapes of fields, not names.
• Width subtyping: records with more fields subsume records with fewer.
• Intersection types: requiring both patterns A and B is like A & B.
• Row polymorphism: patterns naturally allow additional (unspecified) fields to exist.

Core idioms and recommended patterns

1. Use Workspace as your core I/O handle

The Workspace is the primary object for interacting with a repository. It lets you open a branch, commit, push, checkout history, and — importantly — read blob handles (LongString) cheaply.

Pattern: open a workspace for the configured branch, checkout the HEAD ancestors to produce a TribleSet content snapshot for efficient read-only pattern matching, and use the same Workspace to lazily read blobs when you need them.

This avoids duplicating memory and allows cheap zero-copy access to LongString blobs.

Manager-owned repository and workspace DI

At runtime, prefer to give a long-lived manager (session, exporter, service) ownership of a Repository<Pile>. Downstream code can depend on that manager in one of two shapes:

1. Accept a &mut Repository<_> and open/pull the workspace you need inside the function. This works well for tasks that need to coordinate multiple checkouts or want to control the retry loop themselves, and the mutable borrow is typically short-lived: you only need it while creating or pushing workspaces.
2. Ask the manager to mint a &mut Workspace<_> for the duration of a task (e.g. an update, render, or event-handling callback) and pass that mutable reference down. The manager remains responsible for merging or dropping the workspace when the task completes.

Both approaches avoid constructing piles or repositories ad-hoc and keep lifecycle management centralized. Importantly, they let multiple tasks hold distinct mutable workspaces over the same repository while only requiring a single mutable borrow of the repository when you create or push those workspaces. Library functions should therefore accept a &mut Repository<_> or a &mut Workspace<_> (optionally paired with a TribleSet checkout for read-only helpers) rather than opening new repositories inside hot paths.

Example (pseudocode):

// manager owns a Repository for the process/session lifetime
let mut repo = manager.repo_mut();
let branch_id = manager.default_branch_id;

// option 1: task pulls its own workspace
let mut ws = repo.pull(branch_id)?;
let content = ws.checkout(ws.head())?;

// option 2: manager provides a workspace to a task callback
manager.with_workspace(branch_id, |ws| {
    let snapshot = ws.checkout(ws.head())?;
    render(snapshot);
    Ok(())
})?;

This pattern keeps startup/teardown centralized and eliminates the common hot-loop anti-pattern of repeatedly opening ephemeral repository instances.

2. Use find! as a descriptive type / projection

find! is not just a query language; it is the place where you declare the shape of the data you expect. Treat find! patterns as lightweight, inline type declarations. If an entity doesn't match — either because the pattern fails or because a typed variable's conversion fails — find! silently skips it. Use ? on a variable to receive conversion errors as Result values instead of filtering them out.

When your project defines canonical tag ids (GenId constants) prefer to match the tag directly in the pattern rather than binding a short-string and filtering afterwards. Pattern clauses can be composed: you can match on tags and required attributes, and even join related entities in a single find! invocation.

Example: find plan snapshot ids (match tag directly)

// Match entities that have the canonical plan snapshot tag attached.
for (e,) in find!((e: Id), triblespace::pattern!(&content, [{ ?e @ metadata::tag: (KIND_PLAN_SNAPSHOT) }])) {
    // `e` is a plan snapshot entity id; follow-up finds can read other fields
}

Worked example: composing a structural pattern

// Grab all active plans with a title and owner.
for (plan_id, title, owner) in find!(
    (plan_id: Id, title: ShortString, owner: Id),
    triblespace::pattern!(&content, [
        { ?plan_id @ metadata::tag: (KIND_PLAN) },
        { ?plan_id plan::status: (plan::STATUS_ACTIVE) },
        { ?plan_id plan::title: ?title },
        { ?plan_id plan::owner: ?owner },
    ])
) {
    // `title` is already typed as ShortString.
    // `owner` can drive a follow-up find! to pull account info as needed.
}

find! returns tuples of the values you requested in the head of the query. Nothing more, nothing less. The example above reads as "give me the Id bound to plan_id, the short string bound to title, and another Id bound to owner for every entity matching these clauses." Because the matching is descriptive, adding a new attribute such as plan::color does not invalidate the call site — you only see the data you asked for.

3. Lazy, ad‑hoc conversions only where needed

If a function needs a few fields for an operation, ask for them with find! inside the function. If later you perform an operation that needs different fields, you can perform another small find! there. Don't materialize large subgraphs unless a single operation needs them.

The recommended function signature is minimal and focused on the tribles primitives. Conversions into bespoke structs are almost always a smell; they obscure which fields are actually used and quickly devolve into an unofficial schema. Treat any adapter as an opt-in shim that exists purely at integration boundaries where consumers refuse to speak tribles primitives.

fn handle_plan_update(ws: &mut Workspace<Pile>, plan_id: Id) -> io::Result<()> {
    // ad-hoc find! calls to read the fields we need
    let checkout = ws.checkout()?;

    if let Some((title,)) =
        find!((title: ShortString), triblespace::pattern!(&checkout, [{ ?plan_id plan::title: ?title }]))
            .next()
    {
        // The returned tuple is already typed. Convert to an owned String only if
        // external APIs demand ownership.
        process_title(title.from_inline::<&str>());
    }

    Ok(())
}

If you cannot avoid exposing a typed facade (for example because an external API insists on receiving a struct), keep the struct tiny, document that it is a legacy shim, and derive it straight from a find! tuple:

struct PlanSummary<'a> {
    id: Id,
    title: &'a str,
}

fn load_plan_summary<'a>(ws: &'a mut Workspace<Pile>, plan_id: Id) -> io::Result<Option<PlanSummary<'a>>> {
    let content = ws.checkout()?;
    Ok(find!(
        (title: ShortString),
        triblespace::pattern!(&content, [{ ?plan_id plan::title: ?title }])
    )
    .next()
    .map(|(title,)| PlanSummary {
        id: plan_id,
        title: title.from_inline::<&str>(),
    }))
}

The struct above is merely a view with borrowed references; it is not a blessed schema. Resist the temptation to evolve it into a "real" model type — extend the find! pattern first and only mirror those changes here when an external interface forces your hand.

4. Read LongString as &str (zero-copy)

Blob encoding types in tribles are intentionally zerocopy. Prefer the typed View API which returns a borrowed &str without copying when possible.

let view = ws
    .get::<View<str>, LongString>(handle)
    .map_err(|e| ...)?; // `handle` is a Inline<Handle<LongString>>
let s: &str = view.as_ref(); // zero-copy view tied to the workspace lifetime
// If you need an owned String: let owned = view.to_string();

Note: a View borrows data that is managed by the Workspace; avoid returning &str that outlives the workspace or the View.

When you do need ownership, convert at the edge of the system. Internal helpers should continue to pass views or typed handles around so that the call site that triggers a blob fetch is easy to spot. Cloning the in-memory blob after it has been pulled is cheap; the expensive part is fetching it from storage (potentially a remote) in the first place.

5. Structural sharing and normalization patterns

When persisting graphs that contain many repeated or immutable pieces (e.g. steps in a plan), prefer structural sharing:

• Store canonical step entities (LongString blobs for their text).
• Create a lightweight "link" entity per plan that references the step ids and metadata like order and status.

On update, create new step entities only for truly new step text and add a new snapshot entity that references the steps. This keeps history immutable and easy to reason about.

6. Push/merge retry loop for writers

When pushing writes, use the standard push/merge loop to handle concurrent writers. Two options are available:

• Manual conflict handling with try_push (single attempt; returns a conflicting workspace on CAS failure):

ws.commit(content, "plan-update");
let mut current_ws = ws;
while let Some(mut incoming) = repo.try_push(&mut current_ws)? {
    incoming.merge(&mut current_ws)?;
    current_ws = incoming;
}

• Automatic retries with push (convenience wrapper that merges and retries until success or error):

ws.commit(content, "plan-update");
// `push` will handle merge+retry internally; it returns Ok(()) on success
// or an error if the operation ultimately failed.
repo.push(&mut ws)?;

Practical anti‑patterns

• Do not unfold the graph or convert it into nested Rust structs. It wastes CPU and memory and loses the benefits of tribles’ flexible reifications.
• Avoid holding repo locks across async/await points. Acquire workspaces, do the minimal synchronous I/O you need, then release locks before awaiting.
• Don’t assume presence of a field; be explicit about optional vs required semantics using Option / Result in typed adapters.
• Don't create ephemeral Repository instances every time you need to read or write data. Instead, own a long-lived Repository in a manager and expose workspace-opening helpers.
• Don't explicitly convert Values via from_inline/to_inline; use typed find! patterns find!((field: <field_type>), ...) and ws.get::<View<...>, _>(handle) for blob reads.
• Don't create helper functions for queries, use find! patterns directly in the function that needs them. This keeps the shape of the data explicit and close to where it is used and avoids unnecessary unfolding of the graph.
• Don't convert the structures returned by find! into other Rust structs. Work with the returned tuples directly.
• find! should be thought of like a fundamental language primitive, like if/match/for. It is not a "database query" that returns rows to be converted into structs, it is a way to describe the shape of the data you want to see. ORM-like abstractions that try to map find! results into structs are an anti-pattern.
• Avoid reading blobs eagerly; prefer lazy reads via ws.get::<View<...>, _>(handle). Allocate owned data only when necessary.

Glossary

• Workspace: the repo handle that opens branches, reads blobs, commits and pushes.
• TribleSet: the in-memory content snapshot returned by Workspace::checkout.
• find!: the macro you use to discover entities matching a pattern (a descriptive type declaration).
• entity!: construct a self-contained entity fragment (exports, facts, attribute-description metafacts, and their shared blobs). Merge fragments via +=, or call .into_facts() only when you explicitly want to discard every other channel.
• LongString: zero-copy blob encoding for potentially-large text.

Closing notes

This chapter captures the pragmatic type story we use in tribles: describe the fields you need at the place you need them, keep the full graph, and materialize small views lazily.

Reviewers' checklist (quick)

• Prefer find!/pattern! projections for the fields needed by the function.
• Avoid converting graph into rust structs.
• Use ws.get::<View<...>, _>(handle) for zero-copy blob reads; allocate only when an owned value is required.
• Match canonical tag ids via metadata::tag (KIND_* constants).
• Manager-owned repo: long-lived Repository instances should be owned by a session/exporter/manager; library code should accept a Workspace or TribleSet rather than opening piles itself.
• Use push/merge retry loops for writers; avoid holding repo locks across async/await points.

The sections below contain copy‑pasteable recipes for common operations.

Idioms & code recipes

This section contains pragmatic, copy‑pasteable snippets and patterns you can reuse. The examples intentionally use the tribles macros (attributes!, find!, pattern!, entity!) directly — that is the intended style.

Reviewer checklist

When reviewing code that touches tribles, look for these items:

• Does the code use find! to select only the fields it needs, rather than unfolding the entire graph?
• Are blob reads kept lazy (only read LongString when necessary)?
• Are push flows using the push/merge retry loop to avoid losing concurrent updates?
• Is the code avoiding holding the repo's Mutex across awaits and long blocking operations?

Further reading and references

• See the tribles macros: attributes!, find!, pattern!, entity! in the tribles code for exact usage.
• Type theory: "row polymorphism", "structural typing", "width subtyping" if you want the formal background.

Importing Other Data Formats

Import pipelines let you bring external datasets into a tribles repository without hand-writing encodings or entity identifiers every time. This chapter introduces the import namespace, explains how the JSON importers map foreign fields onto attributes, and outlines how you can extend the same patterns to new formats.

Import Namespace Overview

The triblespace_core::import module collects conversion helpers that translate structured documents into raw tribles. Today the namespace ships with two deterministic JSON importers and an N-Triples (RDF) importer:

• JsonObjectImporter hashes sorted and deduplicated NIL || attribute || value rows using the same protocol as entity!, so identical fact sets reproduce the same entities. It accepts a top-level JSON object (or a top-level array of objects). Construct it with a blob sink (e.g., a Workspace’s store or a MemoryBlobStore) and an optional 32-byte namespace when independently imported corpora must not share identities. Each import_* call returns a Fragment that exports the root entity id(s) and contains the emitted facts.
• JsonTreeImporter preserves the full JSON structure and ordering by emitting explicit node and entry entities (a JSON AST). It derives content-addressed identifiers from the JSON values themselves so identical subtrees deduplicate across overlapping imports. Unlike the object importer it can represent arbitrary JSON roots, including primitives. Each import_* call returns a rooted Fragment for the imported JSON value.
• ntriples::ingest_ntriples (and the file-backed ingest_ntriples_file wrapper) reads the line-oriented N-Triples serialization of an RDF graph and emits one trible per statement. URIs become stable entity ids via the import::rdf_uri attribute; predicate URIs become attribute ids via Attribute::<S>::from(entity!{ metadata::iri:, metadata::value_encoding: }) — the IRI is the canonical identifier; literal values map into the appropriate native InlineEncoding based on their XSD datatype.

JsonObjectImporter uses a fixed mapping for JSON primitives:

• strings → Handle<LongString>
• numbers → F64
• booleans → Boolean

Arrays are treated as multi-valued fields; every element becomes its own trible under the same attribute identifier. Nested objects recurse automatically, linking parent to child entities through GenId attributes derived from the containing field name. After one or more imports, call metadata() to retrieve metadata as a Fragment exporting the derived attribute ids. The fragment contains attribute descriptors plus multi-value hints (a metadata::tag edge pointing to metadata::KIND_MULTI). Use clear() when you need a completely fresh run (drop the per-field attribute caches and multi-value tracking).

Mapping JSON Fields to Attributes

Attributes are derived through the entity-core mechanism — Attribute::<S>::from(entity!{ metadata::name: <field handle>, metadata::value_encoding: <S as MetaDescribe>::id() }) — which hashes the sorted and deduplicated canonical NIL || attribute || value rows to produce a stable attribute id from the JSON field name and its fixed InlineEncoding. The importer caches the resulting Attribute<S> per field so the hash only has to be computed once per run. Arrays are treated as multi-valued fields: every item is encoded and stored under the same attribute identifier, producing one trible per element.

After an import completes the importer regenerates metadata from its cached attribute map. The import_* call returns a Fragment exporting the root entity id(s) for the imported document and containing the emitted facts; call metadata() to retrieve a separate Fragment exporting the derived attribute ids and containing attribute descriptors plus multi-value hints (via metadata::tag pointing to metadata::KIND_MULTI). Merge those descriptors into your repository alongside the imported facts when you want queries to discover the original JSON field names or project datasets by encoding without repeating the derivation logic. Field names are stored as metadata::name handles to LongString blobs so arbitrarily long keys survive roundtrips; metadata::name is a general-purpose entity naming attribute, but importers use it for field names here. Importers intentionally avoid emitting attribute usage annotations; those are reserved for code-defined attributes so each codebase can attach its own contextual names and descriptions.

You can import multiple documents by merging fragments:

let mut all = Fragment::empty();
all += importer.import_str(doc1)?;
all += importer.import_str(doc2)?;
// all.exports() yields the root ids; all.facts() yields the merged tribles.

When exporting back to JSON, pass a blob reader (e.g., from a Workspace or MemoryBlobStore) to export_to_json so longstrings can be inlined. If a blob is missing or unreadable the exporter returns an error with the handle hash instead of silently emitting a placeholder, keeping roundtrips lossless when blobs are present. The exporter uses the same fixed mapping in reverse: ShortString → JSON string, Handle<LongString> → JSON string (via blob lookup), Boolean → JSON bool, F64 → JSON number, GenId → inlined object (unless already visited). Attributes that use other encodings are ignored so JSON roundtrips stay predictable even when the dataset mixes in format-specific extensions.

Nested objects recurse automatically. The parent receives a GenId attribute that points at the child entity, allowing the importer to represent the entire object graph as a connected set of tribles. Because those GenId attributes are also derived from the parent field names they remain stable even when you import related documents in separate batches.

Lossless JSON Import

JsonTreeImporter trades the compact attribute/value encoding for a lossless JSON AST representation. Each JSON value becomes a node tagged with a kind (json_tree::kind_*). Objects and arrays emit explicit entry entities that store field names and indices (json_tree::field_* and json_tree::array_*), preserving ordering and allowing repeated keys. Numbers are stored as raw decimal strings via Handle<LongString> so precision is not lost. Array and field indices are stored as U256BE to keep ordering exact even for large collections.

Because node identifiers are derived from the content of each value, identical subtrees converge automatically when you import overlapping backups. This makes lossless imports a good archival layer: you can keep full-fidelity raw JSON and still layer semantic projections on top.

Each import_* call returns a rooted, self-contained Fragment containing the JSON AST facts, every referenced string/number/field-name blob, and the fixed json_tree::* schema in its metafacts. The importer also mirrors content blobs into the backing store supplied at construction. Merge returned fragments when you ingest multiple documents; their descriptions and attachments converge under the same set union. metadata() remains available when a caller wants to inspect the schema directly, but persisting an import does not require a separate metadata step.

Importing N-Triples (RDF)

The import::ntriples module reads the N-Triples serialization of an RDF graph and emits one trible per statement. The importer is a pure function of its input: it returns self-contained fragments whose shared blob stores carry every byte referenced by their facts or metafacts.

use std::io::Cursor;
use triblespace::core::import::ntriples::ingest_ntriples;

let data = br#"
<http://example.org/frank> <http://example.org/firstname> "Frank" .
<http://example.org/frank> <http://example.org/birthyear> "1920"^^<http://www.w3.org/2001/XMLSchema#integer> .
"#;
let import = ingest_ntriples(Cursor::new(&data[..]))?;
assert_eq!(import.triples, 2);

// `facts` is the RDF graph and already carries its predicate vocabulary.
let mut facts = import.facts;
// URI↔id annotations are optional queryable content.
facts += import.uri_map;
Ok::<(), triblespace::core::import::ntriples::IngestError>(())

URI → entity id. Every subject and URI-valued object gets a stable triblespace Id derived from its URI via the import::rdf_uri attribute: the URI is stored as a LongString blob, wrapped in an entity! fragment exporting a single rdf_uri edge, and the fragment's content-derived root id becomes the entity id. The same URI always produces the same id across processes, so repeated imports over the same data reach the same TribleSet — even across machines. The rdf_uri inverse-mapping edges are returned separately in NtImport::uri_map: merge that fragment into the graph when pattern!([{ ?e @ rdf_uri: ?uri }]) should recover source URIs, attach it as metadata when recovery should not affect content queries, or drop it when URI recovery is unnecessary.

Orphan blank nodes. A blank node that is referenced as an object but has no outgoing facts cannot use the normal intrinsic-entity derivation: every such factless node would otherwise collapse to the same empty entity. Instead, the importer retains a separate, domain-separated skolem protocol over the immutable source-document content hash and the literal blank-node label. Importing the same byte-identical document repeatedly therefore reproduces the same ids and converges under set union. Different labels remain distinct, as do labels in documents with different serialized content. This is deliberately content addressing of the N-Triples document, not RDF graph canonicalization: changing comments or whitespace creates a new document scope.

Predicate → attribute id. Predicate URIs become attribute ids through the entity-core derivation exposed as Attribute::<S>::iri(predicate). Because attribute ids are hashed together with the chosen InlineEncoding, the same predicate used for two different literal types produces two different attribute ids — which is what you want: :birthyear "1920"^^xsd:integer and :birthyear "1920" (untyped string) shouldn't collide. (JSON field names use the same shape but with metadata::name instead of metadata::iri, so the resulting ids are also distinct from same-spelled IRIs.)

Literal → native value. XSD datatypes map into the appropriate triblespace inline encodings:

Unrecognized datatypes fall back to Handle<LongString> so no data is lost — the lexical form ships through verbatim. Numeric parse failures fall back to the string path too.

Roundtrips and querying. Because both ids and attribute ids are derived, you can query the imported graph without inventing a separate schema:

use triblespace::core::attribute::Attribute;
use triblespace::prelude::inlineencodings::I256BE;

let birthyear = Attribute::<I256BE>::iri("http://example.org/birthyear");
for (entity, year) in find!(
    (entity: Id, year: i128),
    pattern!(&facts, [{ ?entity @ birthyear: ?year }])
) {
    println!("{entity} born in {year}");
}

N-Triples only. The current importer handles the line-oriented N-Triples format: one statement per line, URIs in angle brackets, literals in double quotes with optional ^^<datatype>, and acyclic blank-node graphs. Turtle-style prefixes and quad/N-Quads are not supported; cyclic blank-node graphs are rejected rather than assigned arbitrary identities.

Managing Entity Identifiers

The importer buffers the encoded facts for each object as complete 64-byte NIL || attribute || value rows, sorts and deduplicates them, hashes their contiguous bytes with BLAKE3, and takes the final 16 digest bytes as the entity identifier. It passes those same defining rows through the shared intrinsic entity builder, ensuring identical fact sets produce identical IDs even across separate runs. You can supply an optional 32-byte namespace via the constructor; it prefixes the canonical row stream and deliberately prevents identities from unifying across namespaces. The returned Fragment exports the resulting plain Id root and contains exactly the object's defining rows plus any recursively imported child-object facts.

This hashing step also changes how repeated structures behave. When a JSON document contains identical nested objects—common in fixtures such as citm_catalog or Twitter exports—the deterministic importer emits the same identifier for each recurrence. Only the first copy reaches the underlying TribleSet; later occurrences are recognised as duplicates and skipped during the merge. Even if the hash itself is fast, that deduplication step reduces workload on datasets with significant repetition.

Extending the Importers

To support a new external format, implement a module in the import namespace that follows the same pattern: decode the source data, derive attributes with Attribute::<S>::iri(...) for URI-identified predicates or Attribute::<S>::named(...) for display-name origins such as JSON fields, encode values using the appropriate InlineEncoding, and carry the dynamic attribute fragments in the result's metafacts. If the format supplies stable identifiers, mix them into the hashing step or salt so downstream systems can keep imports idempotent.

PATCH

The Persistent Adaptive Trie with Cuckoo-compression and Hash-maintenance (PATCH) is TribleSpace’s workhorse for set operations. It combines three core ideas:

1. Persistence. Updates clone only the modified path, so existing readers keep a consistent view while writers continue mutating. The structure behaves like an immutable value with copy-on-write updates.
2. Adaptive width. Every node is conceptually 256-ary, yet the physical footprint scales with the number of occupied children.
3. Hash maintenance. Each subtree carries a 128-bit fingerprint that allows set operations to skip identical branches early.

Together these properties let PATCH evaluate unions, intersections, and differences quickly while staying cache friendly and safe to clone.

Node layout

Traditional Adaptive Radix Trees (ART) use specialised node types (Node4, Node16, Node48, …) to balance space usage against branching factor. PATCH instead stores every branch in the same representation:

• The Branch header tracks the first depth where the node diverges (end_depth) and caches a pointer to a representative child leaf (childleaf). These fields give PATCH its path compression — a branch can cover several key bytes, and we only expand into child tables once the children disagree below end_depth.
• Children live in a byte-oriented cuckoo hash table backed by a single slice of Option<Head>. Each bucket holds two slots and the table grows in powers of two up to 256 entries.
• A heap Leaf owns its key and value. An archive-backed LocalLeaf is instead a tagged pointer directly into immutable archive bytes. It has no allocation or reference count of its own; the enclosing PATCH keeps the archive alive.

Insertions reuse the generic modify_child helper, which drives the cuckoo loop and performs copy-on-write if a branch is shared. When the existing allocation is too small we allocate a larger table with the same layout, migrate the children, and update the owning pointer in place. Because every branch uses the same structure we avoid the tag soup and pointer chasing that ARTs rely on while still adapting to sparse and dense fan-out.

Resizing strategy

PATCH relies on two hash functions: an identity map and a pseudo-random permutation sampled once at startup. Both hashes feed a simple compressor that masks off the unused high bits for the current table size. Doubling the table therefore only exposes one more significant bit, so each child either stays in its bucket or moves to the partner bucket index + old_bucket_count.

The byte_table_resize_benchmark demonstrates how densely the table can fill before resizing. The benchmark inserts all byte values repeatedly and records the occupancy that forced each power-of-two table size to grow:

ByteTable resize fill - random: 0.863, sequential: 0.972
Per-size fill (random)
  size   2: 1.000  # path compression keeps two-entry nodes fully occupied
  size   4: 0.973
  size   8: 0.899
  size  16: 0.830
  size  32: 0.749
  size  64: 0.735
  size 128: 0.719
  size 256: 1.000  # identity hash maps all 256 children without resizing
Per-size fill (sequential)
  size   2: 1.000  # path compression keeps two-entry nodes fully occupied
  size   4: 1.000
  size   8: 0.993
  size  16: 1.000
  size  32: 0.928
  size  64: 0.925
  size 128: 0.927
  size 256: 1.000  # identity hash maps all 256 children without resizing

Random inserts average roughly 86 % table fill while sequential inserts stay near 97 % before the next doubling. Small nodes stay compact because the path-compressed header only materialises a table when needed, while the largest table reaches full occupancy without growing past 256 entries. These predictable fill factors keep memory usage steady without ART’s specialised node types.

Archive-backed leaf lifetimes

A LocalLeaf is safe only while the allocation containing its bytes remains alive. Each PATCH therefore carries an exact persistent owner cover: a binary Patricia trie keyed by the data address of each retained Arc<dyn ArchiveOwner>. Retaining the owner also prevents its address from being reused. The cover is deduplicated by address and structurally shared across snapshots. Its governing invariant is

owners(LocalLeaves(root)) ⊆ cover

Structural operations preserve that invariant as follows:

• archive insertion retains the owner before publishing its LocalLeaf;
• cloning clones the root and cover together;
• union joins both covers before either root is moved or detached;
• intersection retains both input covers, because it may reuse a leaf from either side;
• difference retains the left cover, because it can only reuse left-hand leaves; and
• consuming iterators carry the cover beside their detached traversal queue until every queued key has been copied out or dropped.

The cover is a lifetime receipt rather than a reachability index. Operations may conservatively retain an owner whose leaves disappeared from the result; direct clearing and removal paths that empty a PATCH clear that provenance. Aggregate reconciliation may nevertheless install or retain a conservative cover on an already-empty PATCH, so emptiness alone does not promise immediate release. A TribleSet shares one such cover across all six PATCH indexes, joining any divergent covers once at aggregate set-operation boundaries.

Hash maintenance

On first use in a process, PATCH samples a private random key. Each leaf fingerprint is the 128-bit output of SipHash-2-4 under that key, and each branch stores the XOR of its children’s fingerprints. On insert or delete, the old contribution is XORed out and the new one XORed in, so aggregate maintenance is constant-time. Set operations compare aggregates first: equal fingerprints short-circuit under the practical assumption that they denote equal key sets, while unequal ones force a structural walk. For any fixed pair of unequal sets, the false-positive probability is approximately 2^-128 under the keyed-hash assumption.

The raw subtree fingerprints are process-local implementation values, not serialized identities. They must remain opaque to untrusted chosen-input callers. Although XOR is linear, the usual linear-dependency construction requires observing the fingerprints of chosen keys; the private key makes that attack inapplicable without such an exposure oracle. PATCH's raw root aggregate therefore stays crate-private.

TribleSet::fingerprint preserves the useful O(1) public cache-key API without opening that oracle. It applies a domain-separated SipHash-2-4 PRF to the root aggregate under a second process-random key initialized beside the leaf key. TribleSetFingerprint::as_u128, Debug, and Hash expose only this nonlinear blinding. Equal sets retain equal tokens within one process, while the XOR of public singleton tokens reveals nothing useful about the aggregate of their union. The token remains a 128-bit cache hint, not a durable content identifier or proof of equality.

Archive-backed leaves do not cache their fingerprint, so PATCH avoids hashing them when an exact, cheaper decision is available. Pairs of leaf nodes involving a LocalLeaf compare key bytes directly. A LocalLeaf paired with a subtree of cardinality other than one rejects fingerprint equality from the cached count; a unary branch remains eligible for the ordinary fingerprint path. These are performance shortcuts only, not collision remediation. Pairs without a LocalLeaf retain the normal cached-fingerprint path.

Consumers can reorder or segment keys through the KeySchema and KeySegmentation traits. Prefix queries reuse the schema’s tree ordering to walk just the matching segments. Because every update is implemented with copy-on-write semantics, cloning a tree is cheap and retains structural sharing: multiple workspaces can branch, mutate independently, and merge results without duplicating entire datasets.

Blobs

Blobs are immutable sequences of bytes used whenever data no longer fits into the fixed 256‑bit value slot of a trible. Instead of treating these payloads as untyped binary blobs, Tribles keeps track of their structure via BlobEncoding. Much like InlineEncoding drives how values are serialized into a trible, a BlobEncoding defines how to encode and decode rich data into a byte sequence.

When to reach for blobs

Values and tribles capture compact facts – identifiers, timestamps, counters – in a fixed width. Whenever information grows beyond that footprint, blobs carry the payload while tribles continue to reference it. Common use cases include documents, media assets, serialized entity archives, or even domain specific binary formats. Because blobs are content addressed, the same payload stored twice automatically deduplicates to the same handle. In the in-memory implementation this falls straight out of the code: MemoryBlobStore::insert keeps a BTreeMap keyed by the handle and simply reuses the existing entry when the same digest shows up again.

Handles, schemas, and stores

Blobs live in a BlobStore. The store provides persistent storage and a content hash, determined by the selected HashProtocol, that acts as a stable handle. Handles can be embedded into tribles just like any other value so they benefit from the existing querying machinery. A handle couples the blob's hash with its BlobEncoding so consumers always know how to deserialize the referenced bytes.

Converting Rust types to blobs is infallible in practice, therefore the ToBlob and TryFromBlob traits are the most common helpers. The TryToBlob and FromBlob variants have been dropped to keep the API surface small without losing ergonomics.

End‑to‑end example

The following example demonstrates creating blobs, archiving a TribleSet and signing its contents:

#![allow(unused)]
fn main() {
use triblespace::prelude::*;
use triblespace::examples::literature;
use triblespace::core::{attestation, repo};
use inlineencodings::{Handle, Blake3};
use blobencodings::{SimpleArchive, LongString};
use rand::rngs::OsRng;
use ed25519_dalek::{Signature, Signer, SigningKey};

// Build a BlobStore and fill it with some data.
let mut memory_store: MemoryBlobStore = MemoryBlobStore::new();

let book_author_id = fucid();
let quote_a: Inline<Handle<LongString>> = memory_store
    .put("Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic.")
    .unwrap();
let quote_b = memory_store
    .put("I must not fear. Fear is the mind-killer. Fear is the little-death that brings total obliteration. I will face my fear. I will permit it to pass over me and through me. And when it has gone past I will turn the inner eye to see its path. Where the fear has gone there will be nothing. Only I will remain.")
    .unwrap();

let set = entity!{
   literature::title: "Dune",
   literature::author: &book_author_id,
   literature::quote: quote_a,
   literature::quote: quote_b
};

// Serialize the TribleSet and store it as another blob. The resulting
// handle points to the archived bytes and keeps track of its schema.
let archived_set_handle: Inline<Handle<SimpleArchive>> = memory_store.put(&set).unwrap();

let mut csprng = OsRng;
let commit_author_key: SigningKey = SigningKey::generate(&mut csprng);
let signature: Signature = commit_author_key.sign(
    &memory_store
        .reader()
        .unwrap()
        .get::<Blob<SimpleArchive>, SimpleArchive>(archived_set_handle)
        .unwrap()
        .bytes,
);

// Store the handle in another TribleSet so the archived content can be
// referenced alongside metadata and cryptographic proofs.
let _meta_set = entity!{
   repo::content: archived_set_handle,
   repo::short_message: "Initial commit",
   attestation::signed_by: commit_author_key.verifying_key(),
   attestation::signature_r: signature,
   attestation::signature_s: signature,
};
}

Blobs complement tribles and values by handling large payloads while keeping the core data structures compact. Embedding handles into entities ties together structured metadata and heavyweight data without breaking immutability or introducing duplication. This division of labor lets tribles focus on querying relationships while BlobStores take care of storage concerns such as hashing, deduplication, and retrieval.

Pile Format

The on-disk pile keeps blobs, native collection records, pins, local cells, and wants in one append-only file. The write-ahead log is the database: all indices are reconstructed from the bytes already stored on disk. This design avoids background compaction, manifest management, or auxiliary metadata while still providing a durable content-addressed store for local repositories. The pile file is memory mapped for fast, zero-copy reads and can be safely shared between threads because existing bytes are never mutated—once data is validated it remains stable.

While large databases often avoid mmap due to pitfalls with partial writes and page cache thrashing [1], the pile's narrow usage pattern keeps these failure modes manageable. Appends happen sequentially and validation walks new bytes before readers observe them, so the memory map never exposes half-written records.

Record model: generic envelope and uniform 256-byte framing

Every record the pile writes today begins with the same fixed 256-byte envelope header, followed (for blobs) by the payload, padded so the whole record is a 256-byte multiple:

The envelope marker was minted with trible genid on 2026-08-11. Record kinds reuse the existing current V3 blob/branch/cell/want markers and V4 collection markers; no semantic IDs were reminted. A collection descriptor itself remains an ordinary blob, not a fourth collection-record kind. Want records likewise retain their historical weak-pin/weak-unpin kind IDs; those are physical format names, not the public storage model.

The span includes the header. Zero is invalid; decoders perform checked span * 256 arithmetic and require that the complete record fit in the observed pile prefix. A header-only record therefore has span 1. A blob has span 1 + ceil(payload_length / 256), and the decoder requires the generic span and blob-specific byte length to agree exactly. A u32 block count keeps the prefix compact while permitting a single record of almost 1 TiB.

The common framing is load-bearing:

• Position independence. Blob data starts at the constant record_start + 256; there is no offset-derived padding. A record means the same thing at any offset, so records survive relocation and cat a.pile >> b.pile is a valid merge of two piles.
• Alignment for free. Because every newly written record is a 256-byte multiple, a pile composed entirely of current 256-byte-framed records stays aligned under the atomic lock-free append. Every blob payload in such a pile lands on a 256-byte boundary, satisfying GPU storage-buffer binding requirements (CUDA / Metal min_storage_buffer_offset_alignment) for zero-copy aliasing.
• Cache-friendly headers. Each header begins on a cache-line boundary and admits safe typed views with the zerocopy crate.

Reserved kind-body bytes are zeroed and are not part of the content hash; per-record metadata belongs in tribles, not in the header, so identical bytes never fork into distinct blobs.

Unknown kinds inside this envelope decode as opaque records. Normal pile replay semantically skips them and continues with subsequent known records; PileRecords still exposes their exact offset, length, kind, and raw bytes. This is a forgetful projection: any future kind introduced under this envelope must remain independent of the meaning of known records. In particular, it may not change the validity or effect of a known record, constrain an old writer's otherwise-valid append, or make an existing record depend on a companion record of the new kind. Such an extension—or any other extension whose absence cannot conservatively mean “no effect”—requires a new generic envelope marker instead.

Concatenation is associative ordered composition, not universally commutative: branches, cells, and wants are right-biased last-writer-wins logs. Opaque filtering is sound because it leaves the relative order of every known record unchanged; only collection records additionally collapse to order-independent set union.

The reader still accepts original V1 records (64-byte-aligned blob, branch, and tombstone layouts), unenveloped V3 records, and unenveloped V4 collection records byte-for-byte. An unknown unenveloped marker still reports ReadError::UnsupportedRecord { offset, marker }, because its boundary is unknowable. Older binaries predating the generic envelope reject its marker; upgrade them rather than trying to repair the pile.

The envelope deliberately has no checksum or complemented length. It detects torn/truncated appends through its bounds and kind-specific checks, and it solves version-skew framing; it is not intended to diagnose arbitrary header bit rot. For example, a corrupted kind can look like an opaque kind, while a corrupted but still in-bounds span can cover later bytes. Blob payload integrity remains protected by its content hash.

Design Rationale

This format emphasizes simplicity over sophisticated on-disk structures. Appending new records rather than rewriting existing data keeps corruption windows small and avoids complicated page management. Storing everything in a single file makes a pile easy to back up, replicate over simple transports, or merge by concatenation, while still allowing it to be memory mapped for fast reads. Internally the pile tracks an applied_length watermark; offsets below this boundary are known-good and only the tail beyond it is rescanned when refreshing state.

Operational workflow

1. Open the file. Pile::open builds the struct around a File handle and memmap2 mapping. It does not read any records yet (and it does not create missing files — create the file explicitly for a fresh pile).
2. Load and validate. refresh acquires a shared lock, walks bytes beyond applied_length, and rebuilds the blob, collection-record, and pin indices in memory. It fails loud on a corrupt or torn record (ReadError::CorruptPile { valid_length }). It skips bounded unknown envelope kinds as opaque records and distinguishes an unknown legacy marker as ReadError::UnsupportedRecord { offset, marker }. It never mutates the file. Callers rarely need to invoke it directly: reader, records, pins, head, update, cell, and set_cell call refresh internally before they inspect or apply records, so external writers are visible without a standalone scan.
3. Amputate only when asked to. amputate is the explicit, opt-in repair path: it re-runs validation under an exclusive lock and truncates the file back to the last valid record, discarding a torn record left by a crash. It crosses complete opaque envelopes and may truncate a torn opaque tail at its known start. It refuses UnsupportedRecord without modifying the file because an unknown unenveloped record's boundary is unknowable. It is deliberately not part of the normal open sequence. The trible pile amputate <path> command wraps it for operators.
4. Append new records. put (through the BlobStorePut trait), CollectionStore::insert, local-cell replacement, and pin update helpers extend the file. Each append immediately feeds the bytes back through the record scanner so in-memory indices stay synchronised without waiting for a manual refresh. Blob records use a single write_vectored call; fixed-width collection and pin records use one append of their 256-byte envelope header. Records larger than ~1 GiB can't be appended in a single atomic writev because kernel write_vectored calls cap at INT_MAX bytes on macOS and MAX_RW_COUNT (~2 GiB) on Linux. In that case put takes an exclusive file lock and issues plain write_all calls — still append-only, still repairable by an explicit amputate if a crash leaves a partial tail, but serialised against other writers for the duration of the append.
5. Read through a snapshot. reader clones the memory map and PATCH indices into a PileReader, yielding iterators and metadata lookups that can execute without further locking.

This lifecycle keeps pile usage predictable: open → operate (operations refresh as they run) → hand out read-only readers. If a process wants to scan for new appends between operations (for example, a background monitor that is not issuing reader or pin calls), it can explicitly call refresh to pick up external writers without blocking them for long. If corruption is ever reported, surface it to the operator; truncating is a decision, not a default.

Immutability Assumptions

A pile is treated as an immutable append-only log. Once a record sits below a process's applied offset, its bytes are assumed permanent. The implementation does not guard against mutations; modifying existing bytes is undefined behavior. Only the tail beyond the applied offset might hide a partial append after a crash, so validation and repair only operate on that region. Each record's validation state is cached for the lifetime of the process under this assumption, avoiding repeated hash verification for frequently accessed blobs.

Hash verification only happens when blobs are read. Opening even a very large pile is therefore fast while still catching corruption before data is used.

Every newly written record begins with the generic marker, kind ID, and span described above. The sections below illustrate each kind-specific body.

Usage

A pile typically lives as a .pile file on disk. Repositories open it through Pile::open and load it with refresh (directly or via the first operation that refreshes internally). Multiple threads may share the same handle thanks to internal synchronisation, making a pile a convenient durable store for local development. Blob appends use a single O_APPEND write. Each handle remembers the last offset it processed and, after appending, scans any gap left by concurrent writes before advancing this applied_length. Writers may race and duplicate blobs, but content addressing keeps the data consistent. Each handle tracks hashes of pending appends separately so repeated writes are deduplicated until a refresh. Pin updates only record the referenced hash and do not verify that the corresponding blob exists in the pile, so a pile may act as a head-only store when blob data resides elsewhere.

use std::error::Error;
use std::path::PathBuf;

use anybytes::Bytes;
use triblespace::prelude::*;
use triblespace::core::repo::pile::ReadError;
use triblespace::core::repo::BlobStoreMeta;

fn add_blob(bytes: &[u8]) -> Result<(), Box<dyn Error>> {
    let path = PathBuf::from("data.pile");
    let mut pile = Pile::open(&path)?;
    // Load and validate the existing records. This FAILS LOUD on a corrupt
    // or torn record and never mutates the file. Unknown envelope kinds are
    // skipped as opaque; unknown legacy markers remain unsupported.
    match pile.refresh() {
        Ok(()) => {}
        Err(err @ ReadError::UnsupportedRecord { .. }) => return Err(err.into()),
        Err(err @ ReadError::CorruptPile { .. }) => return Err(err.into()),
        Err(other) => return Err(other.into()),
    }

    // Insert a blob and obtain a handle pointing at the on-disk bytes.
    let handle = pile.put(Bytes::from_source(bytes.to_vec()))?;

    // Readers operate on a snapshot cloned from the pile's mmap.
    let reader = pile.reader()?;
    if let Some(meta) = reader.metadata(handle)? {
        println!("stored {} bytes at {}", meta.length, meta.timestamp);
    }
    drop(reader);
    pile.close()?;
    Ok(())
}

This pattern illustrates the typical flow: open, load with refresh, rely on the built-in refreshes performed by reader and pin helpers, mutate via put, then hand the PileReader snapshot to read-only consumers. Updating pin heads requires a brief critical section—flush → refresh → lock → refresh → append → unlock—so a caller observes a consistent head even when multiple processes contend for the same file descriptor. refresh acquires a shared lock so it cannot race with an explicit amputate, which takes an exclusive lock before truncating a corrupted tail.

Filesystems lacking atomic write/vwrite appends—such as some network or FUSE-based implementations—cannot safely host multiple writers for records below the ~1 GiB atomic-write threshold and are not supported in that mode. (Records above the threshold use the exclusive-lock fallback and don't rely on filesystem atomicity.) Using an atomicity-lacking filesystem for small records risks pile corruption.

Bounded refresh snapshots

Replay snapshots the observed file length once per refresh and decodes exactly that bounded prefix. Shared-lock atomic writers may append after the snapshot; those records are intentionally picked up by the next refresh. Post-write readback still observes the live length while looking for the caller's own record. This avoids a metadata syscall per record without weakening exact torn-tail offsets or amputation's exclusive retry.

PileReader receives one persistent PATCH snapshot when it is created. Later refreshes can extend the pile's copy without changing existing readers, and blobs_diff can compare two snapshots through PATCH's structurally shared set difference instead of enumerating either complete index.

Tools that need the raw log rather than the collapsed state—reflogs, consolidation, forensics—should use PileRecords, an iterator over every record in a pile file in log order. It shares its decoder with the replay path described above, so it understands every record format ever written; do not hand-roll a parser against the layouts documented in this chapter. An unknown envelope kind is yielded as PileRecordContent::Opaque with its declared boundary; callers can preserve its exact bytes through the iterator's raw file view. An unknown unenveloped marker is reported as UnsupportedRecord, while a malformed or truncated record is reported as CorruptPile.

Semantic Pile and Yard reads may continue across opaque records, but destructive retention is different: Pile::rewrite_retained_into, Yard collection, compaction, and reclaim refuse before mutation when any opaque record is present. An older reader cannot know whether the unknown kind owns a known blob, so silently omitting it—or collecting its dependencies—would be unsafe.

Blob Records

Each blob record carries:

• Record kind – identifies blob semantics inside the generic envelope.
• Timestamp – milliseconds since the Unix epoch when the append occurred.
• Payload length – the unpadded byte length of the blob.
• Hash – the digest produced by the pile's hash protocol (BLAKE3 by default) and used as the blob handle.
• Reserved – zeroed padding to the fixed 256-byte header length; not part of the content hash.

The payload follows at record_start + 256 and is post-padded to the next 256-byte boundary. The Pile Blob Metadata chapter explains how to query these fields through the PileReader API.

Native Collection Records

CollectionStore is a grow-only set of canonical collection-calculus records: signed COMMIT assertions and unsigned MERGE and DERIVE equations. The pile stores these three kinds directly as fixed one-block enveloped records. Their semantic kind IDs retain the V4 markers. They are not blob records, have no following payload, and carry no insertion timestamp. They are also distinct from mutable branch pins and local cells described below: collection records have no head, tombstone, or last-writer-wins update. Their logical key is the record's intrinsic entity ID.

The collection itself is identified by a canonical SimpleArchive descriptor containing (scope, representation, recipe). Its 32-byte blob handle is the sole CollectionId. Records carry this handle directly; there is no definition record or registry. Consequently a transferred claim names the exact descriptor bytes needed to interpret it, using the ordinary blob store.

The magic markers below identify the compact pile representation. They are wire-format markers, not the metadata::tag IDs found in the equivalent canonical SimpleArchive entities.

Every reserved byte must be zero; a nonzero reserved byte makes replay fail as corrupt rather than silently assigning meaning to a format extension. Merge inputs are stored in lexicographic digest order (low <= high), so swapping the two operands cannot create a second representation of the same commutative equation.

The intrinsic record ID is deliberately absent from these headers. On replay, the decoder reconstructs the exact canonical one-root entity from the stored fields and its collection-record kind tag, then derives the root ID from that fact set. For a commit this reconstruction includes the public key and both signature components. Consequently the compact pile header and the canonical SimpleArchive form identify the same semantic record without trusting a separately stored key.

Pile replay keeps the records in intrinsic-ID order. Re-inserting an identical record is an idempotent success; a different record reconstructing to the same ID is reported as a collision. Concatenating piles therefore gives set-union semantics for collection records: append order and duplicate copies do not change the discovered collection calculus. This order-independent behavior is specific to collection records and does not turn the last-writer-wins pin log into a set.

Legacy unenveloped V4 collection records

Before the generic envelope, the same three V4 kind IDs occupied bytes 0..16, followed immediately by the semantic fields. Those exact 256-byte records remain readable and reconstruct the same current collection records. They are never rewritten in place; newly inserted records use the envelope.

Legacy V3 collection records

V3 encoded a collection by a separate definition record with a 16-byte intrinsic entity ID. Its V1 commit signature transcript and equations therefore do not identify the current descriptor-handle semantics. The reader recognizes all four old markers so it can validate record boundaries and preserve their bytes during conservative rewrites, but treats them as inert physical evidence: they never enter CollectionStore, assert membership, or retain blobs.

Pin Records (branch head / tombstone)

Pin-head records map a pin (branch) identifier to the hash of a blob; a tombstone retracts the mapping. Appends are intentionally lightweight: the pile does not check whether the referenced blob exists locally, allowing deployments that store heads on disk while serving blob contents from a remote store.

Local Cell Records

Local cells are named last-writer-wins operational values. Their V3 markers are 24264FA9EE46A1ACC0E024AE69774B09 (replace) and 4FE372AE868D22A44DED7A60D579B651 (clear), minted with trible genid on 2026-08-10. A clear is material even in a pile that has not observed an older value, so concatenating that pile after an older one still suppresses the old cell.

Cells are deliberately not branches: they have no compare-and-swap guard, history, enumeration API, collection authority, or gossip surface. They are also not wants. A current cell value is instead a recursive local operational retention root, allowing queryable policy stored in ordinary SimpleArchive blobs to survive collection without asserting that it belongs to any published collection.

Want Records

A want assertion (and its retraction counterpart, using the same layout with a different marker) is keyed by blob handle — per-blob and anonymous, with no pin ID. Assertions and retractions resolve last-writer-wins per handle. The resulting WantStore state is independent from mutable branches and local policy cells: a pile may use wants for fetch-on-demand and bounded cache retention without using branches at all. Because wants are durable records, reopening a pile reconstructs the current wanted set. The implementation keeps the original weak-pin/weak-unpin marker IDs solely so existing piles continue to decode byte-for-byte.

Legacy unenveloped records

Unenveloped V3 blob, branch, local-cell, and want records place their kind ID directly in 0..16. Their semantic bodies begin at byte 16 rather than byte 36: a V3 blob stores timestamp at 16..24, byte length at 24..32, and hash at 32..64; branch and cell IDs occupy 16..32; branch/cell values occupy 32..64; and want handles occupy 16..48. All have a 256-byte header and remain readable byte-for-byte. The legacy V3 and V4 collection layouts are listed above.

Piles written before V3 contain 64-byte-aligned V1 records: a 64-byte blob header (marker, timestamp, length, hash) followed by a payload padded to a 64-byte boundary, and 64-byte branch / tombstone records. The reader recognises the V1 markers and reads these records byte-identical; they are never rewritten. V1 had no want records.

Recovery

refresh scans an existing file to ensure every record fits. It does not verify blob hashes. A malformed or truncated known or enveloped record reports the number of bytes that were valid so far using ReadError::CorruptPile. A complete unknown envelope kind is structurally accepted and semantically skipped; an unknown unenveloped marker reports its bytes and offset using ReadError::UnsupportedRecord, since the reader cannot infer that record's length. Both errors leave the file untouched, and the reader never guesses a legacy record length.

If the file shrinks between scans into data that has already been applied, the process aborts immediately. Previously returned Bytes handles would dangle and continuing could cause undefined behavior, so truncation into validated data is treated as unrecoverable.

refresh holds a shared file lock while scanning. This prevents a concurrent amputate call from truncating the file out from under the reader.

The amputate helper is the explicit, destructive repair path: it re-runs the same validation under an exclusive lock and truncates the file to the valid length if corruption is encountered, discarding incomplete data left by an interrupted write. It crosses complete opaque envelopes, truncates a torn one at its start, and propagates UnsupportedRecord for unknown unenveloped markers without truncating. Run it deliberately (e.g. via trible pile amputate <path>)—never as a routine part of opening. Hash verification happens lazily only when individual blobs are loaded so that opening a large pile remains fast.

For more details on interacting with a pile see the Pile struct documentation.

Pile Blob Metadata

Every blob stored in a pile begins with a compact header. Besides the payload hash (covered in Pile Format), the header records when the blob was appended and how long the payload is. The Pile implementation surfaces this information so tooling can answer questions such as "when did this blob arrive?" without walking the raw bytes on disk.

Header fields at a glance

The current 256-byte generic envelope written ahead of every blob contains:

The reader also accepts legacy V1/V3 blob headers and projects their timestamp, length, and hash through the same API.

BlobMetadata re-exposes the timestamp and length fields so callers can read when a blob was appended and how large the payload is.

BlobMetadata

BlobMetadata is a lightweight struct shared by all repository implementations. It mirrors the timestamp/length pair in the header and leaves validation to the reader:

• timestamp: the write time stored in the blob header as a u64. A convenient way to turn this into a SystemTime is shown below. Pile::put records this value using SystemTime::now(), so it reflects wall-clock time and can move forward or backward if the system clock is adjusted.
• length: the size of the blob payload in bytes. Padding that aligns current entries to 256-byte boundaries is excluded from this value, so it matches the slice returned by PileReader::get.

Looking up blob metadata

PileReader::metadata accepts the same Inline<Handle<_, _>> that other blob store APIs use. The reader consults its in-memory index and, on the first request for a handle, lazily hashes the payload to confirm the bytes match the handle. Subsequent metadata lookups for the same handle reuse that cached validation result. When the payload passes validation the method returns Some(BlobMetadata); otherwise it yields None.

Readers operate on the snapshot that was current when they were created. Call Pile::refresh and request a new reader to observe blobs appended afterwards. PileReader::metadata never fails for valid snapshots—its error type is Infallible.

use std::time::{Duration, SystemTime, UNIX_EPOCH};

use anybytes::Bytes;
use triblespace::core::blob::encodings::UnknownBlob;
use triblespace::core::blob::Blob;
use triblespace::core::repo::pile::Pile;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let mut pile = Pile::open("/tmp/example.pile")?;

    let blob = Blob::<UnknownBlob>::new(Bytes::from_source(b"hello world".to_vec()));
    let handle = pile.put(blob)?;

    let reader = pile.reader()?;
    if let Some(meta) = reader.metadata(handle).unwrap() {
        let appended_at = UNIX_EPOCH + Duration::from_millis(meta.timestamp);
        println!(
            "Blob length: {} bytes, appended at {:?}",
            meta.length, appended_at
        );
    }

    drop(reader);
    pile.close()?;
    Ok(())
}

Failure cases

metadata returns None in a few situations:

• the handle does not correspond to any blob stored in the pile;
• the reader snapshot predates the blob (refresh the pile and create a new reader to see later writes);
• validation previously failed because the on-disk bytes did not match the recorded hash, for example after the pile file was corrupted before this process opened it.

When None is returned, callers can treat it the same way they would handle a missing blob from get: the data is considered absent from the snapshot they are reading. Because validation is cached, later calls will continue to report None for the same handle until a future refresh revalidates the blob.

For additional background on the binary layout and how the header interacts with padding, see the Pile Format chapter.

Glossary

This chapter collects the core terms that appear throughout the book. Skim it when you encounter unfamiliar terminology or need a refresher on how concepts relate to one another in TribleSpace.

Attribute

A property that describes some aspect of an entity. Attributes occupy the middle position in a trible and carry the InlineEncoding (or blob-handle encoding) that interprets and validates the value. Modules mint them with the attributes! macro, so they behave like detached struct fields: each attribute remains independently typed even when many are combined to describe the same entity, preserving its individual semantics. Provide an explicit 128-bit id in the macro when you need a canonical column shared across crates or languages; omit the literal to derive a deterministic id from the attribute name and encoding (the macro wraps the name + encoding id in an entity!{} fragment and takes the root for you), which is handy for short-lived or internal attributes.

Blob

An immutable chunk of binary data addressed by the hash of its contents. Blobs store payloads that do not fit in the fixed 32-byte value slot—long strings, media assets, archived TribleSets, commit metadata, and other large artifacts. Each blob is tagged with a BlobEncoding so applications can decode it back into native types.

Blob Store

An abstraction that persists blobs. Implementations back local piles, in-memory workspaces, or remote object stores while presenting a common BlobStore interface that handles hashing, deduplication, and retrieval.

Capability

A signed authorisation to act with a specific scope on a triblespace network. Each capability is two SimpleArchive blobs: a cap blob carrying cap_subject (the pubkey it authorises), cap_issuer, cap_scope_root, and metadata::expires_at; and a sig blob whose sig_signs points at the cap blob's handle and carries the issuer's signed_by + signature_r/s. Caps chain off the team root (or off another cap with admin scope) and verify by walking back to the configured team_root. Holders present the sig blob's handle on connection (OP_AUTH); the relay enforces the verified scope on every subsequent op. See the Capability Auth chapter.

Checkout

The result of Workspace::checkout. A Checkout pairs a TribleSet with the CommitSet that produced it. It derefs to TribleSet for querying and its AddAssign implementation merges both facts and commit sets, making it the natural accumulator for incremental query loops.

Commit

A signed snapshot of repository state. Commits archive a TribleSet describing the workspace contents and store metadata such as parent handles, timestamps, authors, signatures, and optional messages. The metadata itself lives in a SimpleArchive blob whose hash becomes the commit handle.

CommitSet

A set of commit handles. CommitSet implements CommitSelector by returning itself, which is useful for incremental deltas (e.g., checkout(full.commits()..)). Supports union, intersection, and difference operations.

Commit Selector

A query primitive that walks a repository’s commit graph to identify commits of interest. Selectors power history traversals such as parents, nth_ancestors, ranges like a..b, and helpers such as history_of(entity).

Constraint

The trait that every query operator implements. Its methods—variables, estimate, propose, confirm, satisfied, and influence—let the Atreides solver navigate the search space without a separate planner. propose and confirm take a frontier: a whole batch of parent bindings, of which a single binding is the width-1 case. Constraints are stateless: every method receives the bindings it needs as a parameter, so the engine can backtrack, batch, and split without telling anyone. Estimates guide variable ordering and never change results; confirm may only kill candidates, never add or revive them. Custom data sources and application predicates participate in queries by implementing this trait.

Entity

The first position in a trible. Entities identify the subject making a statement and group the attributes asserted about it. They are represented by stable identifiers so multiple facts about the same subject cohere.

In practice you pick an identifier policy:

• Extrinsic ids (for example ufoid, fucid, genid) track a conceptual subject across edits and versions. Use these when you intend to accumulate additional facts over time.
• Intrinsic ids (content-derived hashes) are recomputed from the entity's asserted fields. The entity! macro uses this policy when you omit the explicit id @ prefix (or when you write _ @), so identical records unify naturally.

Ownership policies and schemas determine who may mint new facts for a given identifier.

Fragment

A self-contained bundle of exported IDs, content facts, descriptive metafacts, and one content-addressed blob store shared by both fact sets. entity! and import pipelines return fragments; entity! carries descriptions for the attributes that actually emitted facts. Fragments compose via += without mixing descriptions into ordinary queries. Use Fragment::root() to extract derived IDs, Fragment::empty() to start accumulation, and spread (*) to pass child fragments into parent entities, giving Merkle trees for free.

PATCH

The Persistent Adaptive Trie with Cuckoo-compression and Hash-maintenance. A single PATCH stores one ordering of a trible set in a 256-ary trie whose nodes use byte-oriented cuckoo hash tables and copy-on-write semantics. A TribleSet maintains six PATCH instances — one per permutation of entity, attribute, and value. Shared leaves keep permutations deduplicated, rolling hashes let set operations skip unchanged branches, and queries only visit the segments relevant to their bindings, further described in the deep-dive chapter.

Pile

An append-only collection of blobs and branch records stored in a single file. Piles act as durable backing storage for repositories, providing a write-ahead-log style format that can be memory mapped, repaired after crashes, and safely shared between threads.

Repository

The durable record that ties blob storage, branch metadata, and namespaces together. A repository coordinates synchronization, replication, and history traversal across commits while enforcing signatures and branch ownership.

Encoding

The byte-layout contract for a typed value. Encodings assign language-agnostic meaning to the raw bytes — they are not the concrete Rust types — so any implementation that understands the encoding can interpret the payloads consistently. Inline encodings map the fixed 32-byte payload of a trible to native types; blob encodings describe arbitrarily long payloads so tribles referencing those blobs stay portable. The corresponding traits are InlineEncoding and BlobEncoding.

Scope

The set of permissions a Capability grants. Output as tribles hung off the cap's cap_scope_root entity: one or more metadata::tag: PERM_* triples (PERM_READ, PERM_WRITE, PERM_ADMIN) optionally combined with scope_branch: <branch_id> triples that restrict the permission to specific branches. An empty branch-restriction set means "every branch within the permission set." Sub-capabilities issued via delegation must have a scope that is a subset of the parent's; the verifier enforces this via scope_subsumes during chain walk.

Team Root

The single immutable keypair that anchors a triblespace network's capability chain. Generated once at team creation, used to sign exactly one capability (the founder's), and then archived offline — the team root never operates online. Like a CA: bootstrapping authority, not runtime authority. The relay hard-codes the team root pubkey via PeerConfig.team_root and rejects any cap chain that doesn't terminate at it.

Trible

A three-part tuple of entity, attribute, and value stored in a fixed 64-byte layout. Tribles capture atomic facts, and query engines compose them into joins and higher-order results.

TribleSpace

The overall storage model that organises tribles across blobs, PATCHes, and repositories. It emphasises immutable, content-addressed data, monotonic set semantics, and familiar repository workflows.

Inline

The third position in a trible. Values store a fixed 32-byte payload interpreted through the attribute’s schema. They often embed identifiers for related entities or handles referencing larger blobs.

Workspace

A mutable working area for preparing commits. Workspaces track staged trible sets and maintain a private blob store so large payloads can be uploaded before publishing. Once a commit is finalised it becomes immutable like the rest of TribleSpace.

Formal Verification Roadmap

This roadmap captures the initial strategy for driving the triblespace crates toward comprehensive formal verification. It unifies model checking, symbolic execution, fuzzing, and deterministic simulation so we can reason about both the low-level data structures and high-level repository workflows with stronger correctness guarantees.

Verification Stack Overview

• Model checking with Kani explores bounded but exhaustive state spaces for invariants that must never be violated.
• Symbolic execution with Miri exposes undefined behaviour (UB) and aliasing issues across regular unit tests without requiring new harnesses.
• Coverage-guided fuzzing stresses APIs with randomized input sequences to uncover emergent behaviours that formal proofs might miss.
• Deterministic simulations replay realistic repository workflows so we can audit higher-level semantics and regression-test subtle interplays between subsystems.

Each technique complements the others; together they provide layered assurance that keeps regressions from reaching downstream users.

Goals

• Protect the fundamental algebraic properties of TribleSet, PATCH, and the repository commit graph.
• Exercise serialization, deserialization, and zero-copy data views under adversarial inputs.
• Detect behavioural regressions in query heuristics, constraint solving, and workspace merging before they reach downstream users.
• Integrate the tooling into CI so proofs and regression checks run automatically for every change.
• Preserve a contributor-friendly workflow where verification steps are discoverable, well documented, and quick to reproduce locally.

Current Foundation

• proofs/ already contains Kani harnesses for query, value, and variable-set behaviour. They provide examples of bounded nondeterministic data generation (kani::any, Inline::new) and assume/guarantee reasoning that new harnesses can reuse.
• ./scripts/preflight.sh is the aggregation point for formatting and tests; adding verification steps here keeps contributor workflows consistent.

Invariant Catalogue

The roadmap anchors future work around the following invariants. Each row tracks the subsystem we care about, the guarantees we want to encode, and a rough sketch of how to exercise them in Kani, Miri, or fuzzing harnesses.

Expansion Plan

Phase 1 – Harden the Existing Kani Coverage

1. Catalogue crate-level invariants and map them to concrete Kani harnesses. Start with:
   • TribleSet operations preserving canonical ordering and deduplication.
   • Join heuristics in atreides ensuring variable bindings never alias conflicting values.
   • Repository merge logic maintaining append-only pile semantics.
2. Extract shared helpers for generating bounded arbitrary data (e.g. Vec::bounded_any) so harnesses remain expressive without exploding the search space.
3. Adopt a per-module harness layout (proofs/<module>_harness.rs) registered from proofs/mod.rs to make maintenance predictable.
4. Configure scripts/verify.sh to run targeted cargo kani --harness <name> invocations in parallel, then wire it into CI with caching to keep runtimes manageable.

Phase 2 – Symbolic Execution with Miri

1. Enable cargo miri test for the default test suite to surface undefined behaviour (UB) and aliasing bugs that regular tests may miss.
2. Gate flaky or unsupported tests with cfg(miri) guards so the suite stays deterministic under the interpreter.
3. Document the workflow in scripts/preflight.sh and optionally expose a dedicated scripts/miri.sh for local runs when developers need deeper debugging.

Contributor Workflow

1. Run ./scripts/preflight.sh before every commit; it aggregates formatting, testing, and (eventually) targeted verification checks.
2. Use cargo kani --harness <NAME> locally when iterating on a new proof. Start from the harness templates in proofs/ so generators and assumptions stay consistent.
3. Execute cargo miri test after modifying unsafe code, pointer logic, or concurrency primitives; it catches UB bugs that normal tests cannot surface.
4. Kick off fuzz targets with cargo fuzz run <TARGET> when touching boundary code (deserializers, planners, repository sync). Store new corpus inputs in version control if they expose bugs or tricky behaviours.
5. Record findings, gaps, and future work in INVENTORY.md so the roadmap evolves alongside the implementation effort.

Phase 3 – Fuzzing and Property Testing

1. Introduce a cargo fuzz workspace targeting:
   • PATCH encoders/decoders with binary corpus seeds generated from integration tests.
   • Join-order heuristics to explore combinations of constraint graphs and filter predicates.
   • Repository sync workflows by fuzzing sequences of commits, pulls, and merges.
2. Reuse structured generators from proptest where deterministic shrinking is valuable, and bridge them into fuzz harnesses when possible to keep the state space constrained.
3. Automate nightly or on-demand fuzz campaigns via CI artifacts, storing any found counterexamples alongside minimised reproducers.

Phase 4 – Deterministic Simulation Testing

1. Model repository replication scenarios with deterministic event queues to explore conflict resolution, garbage collection, and concurrent writers.
2. Encode the simulations as regular unit tests backed by recorded execution traces so they can double as documentation for expected behaviour.
3. Capture simulation scenarios discovered during fuzzing to prevent regressions.

Milestones & Reporting

• Track coverage for each invariant in a shared dashboard (CI summary or INVENTORY.md) so contributors can quickly spot gaps.
• Celebrate major wins—like a new harness landing or a bug found via verification—in the CHANGELOG to reinforce the value of the effort.
• Review and refresh this roadmap at least once per release cycle to keep the guidance aligned with the architecture.

Tooling Integration

• Track verification status in CI badges and documentation so contributors know which guarantees currently hold.
• Extend INVENTORY.md with follow-up work items whenever new invariants or subsystems are identified.
• Keep verification-specific configuration (Kani property files, fuzz corpora, deterministic seeds) under version control to make runs reproducible.

Next Steps

1. Break the invariant catalogue into GitHub issues that reference the planned harness files (proofs/tribleset_harness.rs, proofs/patch_harness.rs, etc.).
2. Prototype the PATCH harness that drives Branch::modify_child through insertion/growth cycles so we can assert the displacement planner and table_grow never drop entries; wire the run into scripts/verify.sh.
3. Evaluate CI capacity to determine how frequently Kani proofs, cargo miri, and fuzzers can run without blocking contributors, documenting the cadence directly in INVENTORY.md.

This roadmap should evolve alongside the codebase—update it whenever new verification opportunities or obstacles appear.