@aweftjs/codec

The wire format: values, deltas and commits to bytes, and back.

One value has one spelling. The decoder refuses any input an encoder would not have written, so two implementations that both pass the fixture suite write byte-identical output for the same commit. Byte equality is what conformance means here, and every rule in the package serves it.

That is a rule about spelling, not about trust. See "What this does not do" before you rely on it for anything else.

The format is written down in spec/format.md, and this package is its normative implementation. Nothing here knows about observables, transports or storage.

Quickstart

import { createId, decodeCommit, encodeCommit, type Commit } from '@aweftjs/codec';

const doc = createId();

const commit: Commit = {
	deltas: [
		{ type: 'add', id: doc, ref: { kind: 'object', key: 'title' }, value: 'plan' },
		{ type: 'add', id: doc, ref: { kind: 'object', key: 'done' }, value: false },
	],
};

const bytes = encodeCommit(commit);
const back = decodeCommit(bytes);
// encodeCommit(back) is byte for byte the same as bytes. Always, for any input decodeCommit
// accepted.

encodeCommit sorts the deltas, so the same commit handed over in any order gives the same bytes. decodeCommit refuses deltas that arrive out of that order rather than sorting them: accepting both spellings would mean two byte strings decode to one commit, and re-encoding could no longer reproduce its input.

A delta names a slot, not a path

The target is id plus ref. There is no path anywhere in the format, so a delta means the same thing whatever else moved in the same commit.

{ kind: 'object', key: 'title' }        // a string slot
{ kind: 'array',  key: position }       // a position key, ordered as bytes
{ kind: 'map',    key: someId }         // keyed by identity

ref.kind says which observable kind the delta is talking about, so a receiver that has never seen the target can still read the delta. value is present for add and replace and absent for remove.

Values are flat

type Value = null | boolean | number | string | Uint8Array | Reference;

There is no nested structure in a slot. A structure inlined into a slot would be state that no delta addresses, and every change to state is a delta. A slot that holds another observable holds a Reference to it:

{ edge: 'attach', kind: 'object', id: childId }   // where the child lives
{ edge: 'alias',  kind: 'object', id: childId }   // a second name for it, moves nothing

An observable has exactly one attach edge. Every other reference to it is an alias, which is what makes one walk up the attach edges the whole answer to where something sits.

Ids and positions

Ids are 12 random bytes, and idToText gives the 16 base64url characters that are safe in a URL, a log line or a JSON key. createId takes no seed and no injectable generator on purpose: code that needs deterministic ids takes them as input.

A position is a non-empty byte string that does not end in a zero byte. Those two rules are what guarantee a key always exists between any two distinct keys, so an array never runs out of room to grow. comparePositions is the plain unsigned byte comparison, and a prefix sorts before what extends it.

import { assertPosition, comparePositions, isValidPosition } from '@aweftjs/codec';

isValidPosition(Uint8Array.of(0x80));        // true
isValidPosition(Uint8Array.of(0x80, 0x00));  // false, ends in a zero byte

assertId and assertPosition hand the value back, so they can wrap it on the way into a structure rather than sitting on a line of their own.

Id, Position and Tag are three distinct types, not three spellings of Uint8Array. They are the same bytes at runtime and on the wire; the difference exists only while the compiler is looking, so a signature that wants an id refuses a position (design 104). Bytes from anywhere else become an id or a position by going through assertId or assertPosition, which is the check they needed anyway.

const id: Id = assertId(bytes);          // checked, and now typed as an id
const key: Position = assertPosition(k); // same, for an array slot key

This package judges positions and never mints one. Choosing a key between two others is left open by the format on purpose, and @aweftjs/core is what makes the choice: ordinary array work does it for you, so list.splice(1, 0, x) on ['a', 'c'] turns positions 80 81 into 80 8080 81. positionsOf reads the keys back, and insertAt is the other direction, for a receiver honouring a position it was told rather than inventing one and diverging. Writing your own is a real job, not a one-liner, so reach for core rather than starting from comparePositions.

Refusals name a reason

Every throw is a CodecError carrying a reason, and the reason is part of the format's contract rather than a message for a human. Two implementations that reject the same input for different stated reasons have not agreed on the format.

import { decodeCommit, type CodecError } from '@aweftjs/codec';

try {
	decodeCommit(damaged);
} catch (error) {
	(error as CodecError).reason;  // 'deltas-out-of-order', 'truncated', 'duplicate-slot', ...
}

The reasons are pinned by spec/fixtures/invalid/: one file per case, naming the bytes, the stage the refusal is due at, and the reason to refuse for. The filenames say which is which, so that directory is the list to read and to branch on. A reason not exercised there is not part of the contract.

The value layer

encodeValue and decodeValue sit below commits, on the small type set the format allows: null, booleans, integers, float64, byte strings, text strings and arrays. No maps and no tags, so there is no dialect to negotiate.

Integers are exact and written as integers in [MIN_INT, MAX_INT], which is +/- 2^53, and anything outside that is a float. The bound is exact representability rather than JavaScript's safe-integer range, because a double holds 2^53 exactly. A whole number written as a float is refused, and so is an integer padded into a wider form than it needs.

Most callers want encodeCommit and never touch this layer. It is public because an implementation in another language checks its own value encoding against this one.

What this does not do

It does not detect tampering. Damage a byte and one of two things happens: the bytes stop being a commit and decoding throws, or they are still a legal commit and decode cleanly into a different one. Both are correct. Flip a bit inside an id and you get a different id, which is as valid as the one you started with, and nothing in the format can know you did not mean it. Flipping every bit of three small commits in turn, 562 of 968 flips decoded without complaint. How many depends on the shape of the commit, and it is never small. If your bytes cross a channel that can change them, put a checksum or a signature in your own framing. This package will not notice.

Commit.tag is not that check, whatever the word integrity suggests. It is a digest over the prior values of the slots a commit addresses, computed by the sender against its own state before the commit, and it answers one question: did this commit land on the state the sender thought it would? A receiver that computes a different tag treats the two replicas as diverged and resynchronizes. It says nothing about the bytes in between, and the algorithm that fills it is still open, so nothing here computes or checks one yet.

It does not frame anything. A decoded commit is internally complete, but no public API reports how many bytes it consumed, so a log of commits needs its own framing to say where each one ends. The simplest workable one is a length prefix per frame:

const frame = (bytes: Uint8Array): Uint8Array => {
	const out = new Uint8Array(4 + bytes.length);
	new DataView(out.buffer).setUint32(0, bytes.length);
	out.set(bytes, 4);
	return out;
};
// Reading back: take the length, slice the frame, hand exactly that slice to decodeCommit.

decodeCommit takes one commit with nothing before or after it, so the framing decides where a commit ends, and anything that must survive a hostile channel adds its own checksum or signature at this layer. recipes/codec/main.ts is a complete log doing this.

Boundaries

Deliberately not here: any document model, any transport, any persistence.

The reasoning behind the choices lives in docs/design/, and the format they implement in spec/format.md.

The design notes

A design NNN above is the note of that number in docs/design/, which says what was decided, why, what it costs, and what would reverse it.

API

Every export of @aweftjs/codec, its signature as the compiler resolves it, and its block comment.

@aweftjs/codec

CodecError

interface CodecError extends Error { readonly reason: string; readonly fix: string; }

An error carrying a stable machine-readable reason and the remedy for it.

The reason is part of the format's contract: spec/fixtures/invalid/ names one per case, so a conforming implementation must reject the same input for the same stated cause, not merely reject it somehow.

Commit

interface Commit { readonly deltas: readonly Delta[]; readonly tag?: Tag; }

The unit that crosses every boundary.

A commit applies whole or not at all, and it carries at least one delta. Its deltas are a set, written in the canonical order of section 6.9, and a receiver replaying them one at a time would pass through states the sender never had.

tag is 4 to 32 bytes and is not a checksum of these bytes. It is a digest over the prior values of the slots this commit addresses, computed by the sender against its own state before the commit, and it answers whether the commit landed on the state the sender expected. A receiver computing a different tag treats the replicas as diverged and resynchronizes. The algorithm that fills it is still open, so nothing here computes one.

Delta

interface Delta { readonly type: DeltaType; readonly id: Id; readonly ref: Ref; readonly value?: Value; }

One change to one slot.

The target is id plus ref and never a path, so a delta means the same thing whatever else moved in the same commit. value is absent exactly when the type is remove: absent as in the key is omitted, not present holding undefined, and a decoded delta reads the same way.

DeltaType

type DeltaType = 'add' | 'replace' | 'remove';

What a delta does to the slot it names.

The same three words JSON Patch uses, deliberately: the format is specified for other languages to implement, and an implementer reading replace already knows the semantics. add needs the slot free, replace and remove need it taken. That rule binds whoever applies the commit to a document: an applier refuses a commit that gets it wrong rather than reconciling it. The encoder cannot check it, because it holds no state across commits; the only slot rule enforced here is that one commit never targets a slot twice.

EdgeKind

type EdgeKind = 'attach' | 'alias';

What a reference to an observable means.

attach is where the observable lives, and it has exactly one. alias names it from somewhere else and moves nothing.

ID_BYTES

ID_BYTES: 12

96 bits. Twelve bytes encode to exactly sixteen base64url characters with no padding.

ID_TEXT_LENGTH

ID_TEXT_LENGTH: 16

How many characters the text form of an id is. Sixteen base64url characters, no padding.

Id

type Id = Uint8Array & { readonly [idBrand]: true; };

Bytes that have been checked to be an id.

The same twelve bytes a Uint8Array holds, and the same bytes on the wire. The brand is a property that exists only while the compiler is looking, so a position or an integrity tag cannot stand in for an id in a signature that asks for one (design 104).

createId and assertId are the only things that produce one. Bytes from anywhere else reach an id by going through assertId, which is the width check they needed anyway.

Example

const id: Id = assertId(bytes);

MAX_INT

MAX_INT: number

Integers are exact in this range and are written as integers. Outside it, as float64.

The bound is exact representability, which is what section 6.2 states, and not the safe integer range: a double holds 2^53 exactly and 2^53 + 1 not at all. Reaching for MAX_SAFE_INTEGER here stops one short on the positive side and leaves the range lopsided, so a whole number another implementation wrote as an integer, reading the same prose, comes back refused.

MAX_TAG_BYTES

MAX_TAG_BYTES: 32

No block comment on this export.

MIN_INT

MIN_INT: number

No block comment on this export.

MIN_TAG_BYTES

MIN_TAG_BYTES: 4

The narrowest and widest a commit tag may be. Section 3.3; the algorithm is open.

ObservableKind

type ObservableKind = 'object' | 'array' | 'map';

Which of the three kinds an observable is. It is fixed when the observable is made.

Position

type Position = Uint8Array & { readonly [positionBrand]: true; };

Bytes that have been checked to be a position key.

The same bytes a Uint8Array holds, and the same bytes on the wire. The brand is a property that exists only while the compiler is looking, so an id or an integrity tag cannot stand in for a position in a signature that asks for one (design 104).

assertPosition is the only thing that produces one, because this package judges positions and never mints one.

Example

const ref = { kind: 'array', key: assertPosition(bytes) };

Ref

type Ref = { readonly kind: 'object'; readonly key: string; } | { readonly kind: 'array'; readonly key: Position; } | { readonly kind: 'map'; readonly key: Id; };

Which slot within an observable. The kind is carried, so a receiver that has never seen the observable can still tell what it is being told about.

Reference

interface Reference { readonly edge: EdgeKind; readonly kind: ObservableKind; readonly id: Id; }

A value that is another observable is named, never inlined.

The edge says what this reference means. An observable has exactly one attach edge, which is where it lives; every other reference to it is an alias. Aliases keep state a graph without giving an observable a second home, which is what makes a single walk up the attach edges the whole answer to where something sits.

Tag

type Tag = Uint8Array & { readonly [tagBrand]: true; };

Bytes that have been checked to be a commit's integrity tag.

The same bytes a Uint8Array holds, and the same bytes on the wire. The brand is a property that exists only while the compiler is looking, so an id or a position cannot stand in for a tag in a signature that asks for one (design 104).

The algorithm that fills a tag is open, so this package computes none and has nothing that mints one. Whatever computes a digest states that its result is a Tag.

Example

const commit: Commit = { deltas, tag };

Value

type Value = null | boolean | number | string | Uint8Array | Reference;

Everything a slot can hold: a primitive, or the name of another observable.

There is no structure here on purpose. A structure inlined into a slot would be state that changes with no delta addressing it, and every change to state is a delta.

WireValue

type WireValue = null | boolean | number | string | Uint8Array | readonly WireValue[];

Everything the encoding can carry, at the level below deltas and commits.

The type set is small on purpose, and there are no maps and no tagged values. A commit is built out of these and nothing else, which is what keeps one spelling per value.

assertId

assertId: (id: Uint8Array<ArrayBufferLike>) => Id

Check that this is an id, and hand it back.

Params

• id: the bytes to check

Returns the same bytes as an Id, so it can wrap a value on its way into a structure. This is where raw bytes become an id: the check and the type say the same thing here, and every signature downstream can then ask for an id and get one.

Throws when it is not exactly ID_BYTES long. An id of the wrong width is refused at the edge rather than stored and found later, because by then nothing can say what it was.

Example

const delta = { type: 'add', id: assertId(bytes), ref, value };

assertPosition

assertPosition: (p: Uint8Array<ArrayBufferLike>) => Position

Check that this is a well formed position, and hand it back.

Params

• p: the position key

Returns the same bytes as a Position, so it can wrap a value on its way into a ref. This is where raw bytes become a position: the check and the type say the same thing here.

Throws when it is empty or ends in a zero byte. Both are refused here rather than at the far end, because a key that breaks either rule leaves an array with a place it can never grow into and nothing downstream can tell why.

Example

const ref = { kind: 'array', key: assertPosition(position) };

assertValue

assertValue: (value: Value) => void

Refuse a slot value the format cannot carry.

Params

• value: what a delta puts in a slot, a reference included

Returns nothing. It throws or it does not.

Throws a CodecError. invalid-number for a non-finite number, lone-surrogate for an unpaired surrogate, invalid-value for anything else with no encoding. A reference passes: its id and its slot key are checked where they are read, and what it points at is not this function's business. Callers holding a value before it reaches the encoder use this, so a document can never hold something its own bytes cannot say. A value that gets in without passing here makes the document unserveable to every byte client, and the failure lands on whoever tries to encode it rather than on whoever wrote it.

Example

assertValue(delta.value);

bytesFromHex

bytesFromHex: (hex: string) => Uint8Array<ArrayBufferLike>

The bytes behind a hex string.

Params

• hex: an even number of hex characters

Returns the bytes it spells.

Throws when the length is odd or a character is not hex, rather than guessing at what was meant.

Example

const position = bytesFromHex(slot);

bytesToHex

bytesToHex: (b: Uint8Array<ArrayBufferLike>) => string

A byte string as lower case hex.

Params

• b: the bytes

Returns two characters per byte. Hex is used where bytes have to be a string that still sorts the way the bytes do, which is what lets an array slot be keyed by its position.

Example

slots.set(bytesToHex(position), cell);

codecError

codecError: (reason: string, detail: string, fix: string) => CodecError

Build a refusal that names the rule it is refusing for, and what to do about it.

Params

• reason: the stable machine-readable cause, as spec/fixtures/invalid/ states it

• detail: what was actually seen, for a human reading the message

• fix: one sentence saying what to do instead, in the imperative

Returns an Error whose message is reason: detail. fix, whose reason is the reason alone, and whose fix is the remedy alone. Callers branch on reason and never on the message. The fix is required. An error that says only what went wrong leaves its reader to infer the remedy, and the reader is often an agent with no other documentation in front of it. npm run errors refuses a refusal whose fix is empty.

Example

throw codecError('invalid-id', `${id.length} bytes is not an id`, 'Mint ids with createId.');

compareBytes

compareBytes: (a: Uint8Array<ArrayBufferLike>, b: Uint8Array<ArrayBufferLike>) => number

Order two byte strings.

Returns -1, 0 or 1. Bytes are unsigned, and a string that is a prefix of another sorts before it.

Example

compareBytes(Uint8Array.of(1), Uint8Array.of(1, 0)) === -1

compareDeltas

compareDeltas: (a: Delta, b: Delta) => number

Order two deltas the way section 6.9 orders them, without writing any bytes.

Returns -1, 0 or 1. Zero means they address the same slot, which a commit may not do.

Throws a CodecError with reason invalid-id when either delta's id is not ID_BYTES long. The rule is stated over the encoded form: the id, then the ref. This reads that order off the values instead, which is the same order for a reason worth stating rather than trusting. Ids are all one width, so their heads are equal and only the bytes decide. A ref's kind encodes to one byte that grows with the kind. A string or byte string is written as a length and then its contents, and every head grows with the length it holds, so a shorter key sorts first whatever it contains. UTF-8 orders by code point, so text compares by code point.

Example

[...deltas].sort(compareDeltas)

comparePositions

comparePositions: (a: Position, b: Position) => number

Order two position keys.

Returns negative, zero or positive, ordering the keys as their bytes order, which is the one array order every implementation agrees on.

Example

positions.sort(comparePositions);

createId

createId: () => Id

Mint an id.

Returns ID_BYTES of cryptographically secure randomness. There is no seed, no injectable generator, and no fallback. A generator that can be replaced at runtime exists so tests can be deterministic, and its effect is that tests observe randomness production never sees, so no test can catch a weak source. Code that needs deterministic ids takes them as input instead.

decodeCommit

decodeCommit: (bytes: Uint8Array<ArrayBufferLike>) => Commit

Decode a commit, rejecting anything the encoder would not have produced.

Params

• bytes: one commit, with nothing before or after it

Returns the commit, its deltas in canonical order.

Throws a CodecError naming the rule broken. Deltas out of canonical order are rejected rather than sorted, because accepting them would mean two byte strings decode to one commit and re-encoding could not reproduce the input.

decodeValue

decodeValue: (bytes: Uint8Array<ArrayBufferLike>) => WireValue

Decode one value, rejecting anything the encoder would not have written.

Params

• bytes: exactly one value, with nothing before or after it

Returns the value. Re-encoding it reproduces the bytes it was read from, for every input this accepts.

Throws a CodecError naming the rule broken. An integer padded into a wider form, a whole number written as a float, an indefinite length and a trailing byte are all refused, not because they are ambiguous but because accepting them would give one value two spellings.

Example

decodeValue(encodeValue('hi')) === 'hi';

encodeCommit

encodeCommit: (commit: Commit) => Uint8Array<ArrayBufferLike>

Encode a commit.

Params

• commit: its deltas in any order, and an optional integrity tag

Returns the canonical bytes. Deltas are sorted here, so the same commit given in any order produces the same bytes.

Throws a CodecError naming the rule broken, for an empty commit, a duplicated slot, a malformed id, position or value, or a remove carrying a value.

encodeValue

encodeValue: (v: WireValue) => Uint8Array<ArrayBufferLike>

Encode one value, below the level of deltas and commits.

Params

• v: anything WireValue allows

Returns the canonical bytes. There is one encoding per value, so two encoders that agree on the format produce the same bytes for the same value.

Throws a CodecError for a value the format cannot carry, including undefined, a plain object, a Map, a bigint and a lone surrogate in a string.

Example

encodeValue([1, 'two', null]);

equalBytes

equalBytes: (a: Uint8Array<ArrayBufferLike>, b: Uint8Array<ArrayBufferLike>) => boolean

Do two byte strings hold the same bytes?

Returns true when they are the same length and every byte matches. Identity is not the question: two arrays holding the same bytes are one value to this format.

Example

if (equalBytes(idOfDelta, idOfNode)) apply(delta);

idFromText

idFromText: (text: string) => Id

The id behind its text form.

Params

• text: sixteen base64url characters, as idToText writes them

Returns the 12 bytes, as an id.

Throws when the length or the alphabet is wrong. Round tripping through text is lossless, so anything that does not round trip was never one of these ids.

Example

const id = idFromText(slotKey);

idToText

idToText: (id: Id) => string

The textual form of an id: sixteen base64url characters.

Params

• id: an id. Raw bytes reach one through assertId

Returns the text form, safe in a URL, a log line, or a JSON object key.

Throws a CodecError with reason invalid-id when the bytes are not ID_BYTES long.

isReference

isReference: (v: Value) => v is Reference

Is this value a reference to an observable rather than a primitive?

Params

• v: any value the format can carry

Returns true only for the three field shape a reference has. Narrowing on "an object that is not bytes and not an array" would answer true for a plain object too, and the caller then fails a step later complaining about the kind rather than about the structure it was actually handed.

Example

if (isReference(delta.value)) follow(delta.value.id);

isValidPosition

isValidPosition: (p: Uint8Array<ArrayBufferLike>) => boolean

Is this a well formed position key?

Params

• p: the bytes to judge

Returns true when the key is non-empty and does not end in a zero byte. Both rules exist so that a key can always be produced between any two distinct keys: with a trailing zero allowed, nothing fits between K and K followed by a zero, and an array would run out of room to grow.

Example

isValidPosition(Uint8Array.of(0x80, 0x00));  // false

slotKeyOf

slotKeyOf: (ref: Ref) => string

The name a slot has in a path, and the key a document files it under.

Params

• ref: the slot a delta names

Returns an object key as itself, an array position in hex, a map identity in text form.

Throws a CodecError with reason invalid-id when a map slot's key is not an id. This is one mapping with one implementation, because a second copy is a second chance to disagree about what a document's own keys are.

Example

slotKeyOf({ kind: 'object', key: 'title' });   // 'title'

Refusals

Every error this package raises carries a reason to switch on and a fix that says what to do. These are its reasons, from errors.txt.

Recipes

The programs in the stack's gate that use this package, each a job someone would have.

• recipes/codec: the package's own recipe