The history format

This specification fixes how semantic history is stored: the encoding of each fact, the hash chain, content-hashed blobs and module sources, the encoding of checkpoints and holes, durability, and the data version. Two implementations that agree on this file read each other's histories.

It realizes the language contract and never redefines it. history.md owns which facts a history records and when, call and task ids, pauses, checkpoints and where they may be taken, replay and its verdicts, forks, holes, integrity claims and program identity. concurrency.md owns what first and stop decide. Where this file and an owner disagree, the owner wins.

Within the runtime track, abi.md owns the value encoding every fact uses; execution.md owns how a run writes, pauses, resumes and forks a history; diagnostics.md owns how a storage failure is reported.

A history

A history is one run's sequence of facts and the blobs they refer to, and nothing else. It is not an instruction log, an application trace, or a host's record of bindings, retries or halts.

• Facts are stored in order, one per line, each line the canonical JSON of one fact (abi.md), ending in a newline.
• Blobs are stored in a content-addressed store beside the facts, each under the hash of its exact bytes.

Fact n is the fact's 1-based position. Positions name facts in replay verdicts and viewers ("diverged at fact 12"); they are locators, not identities. Calls and tasks are identified by their ids, which come from the program's own structure (history.md).

How facts and blobs are laid out in files, databases or object stores is the host's choice. A run is identified by its run id and the identities its Start records, never by a path.

Serves foundations: History carries non-derivable meaning; Semantic execution history.

Hashes

Every hash is SHA-256, written sha256: followed by 64 lowercase hex digits. A value's hash is the hash of its canonical text. A blob's hash is the hash of its exact bytes.

Value slots

Every place a fact holds a program value is a value slot, which takes one of three forms:

{"value": v}          the value inline, in canonical form
{"blob": "sha256:…"}  the value stored once in the blob store, by its hash
{"hole": "sha256:…"}  the value withheld; only its hash remains

Whether a value is inline or a blob is the writer's choice and carries no meaning; a writer typically moves large values to blobs so each is stored once. A blob holding a value holds its canonical text, so the blob's hash is the value's hash.

Facts

Every fact is an object with these members, plus those of its kind:

{ "n":    position,
  "prev": hash of the previous fact's digest form, or null for Start,
  "fact": "Start" | "Call" | "Reply" | "Choice" | "Stop" | "Checkpoint" | "End" }

The members of each kind:

• Start. data is the data version. run is the run id the host assigned. program is the program identity (history.md), and std the std version the program uses, which is its language version. modules lists every module the program contains, sorted by path, each as {"path", "commit", "source"}: the import path, the resolved commit for a remote module (null for a local or submitted one), and the hash of its source blob. entry is {"module", "name"}. input maps each entry parameter's name to a value slot. parent is {"run", "checkpoint"} for a fork, naming the parent run and the hash of the checkpoint fact it started from, or {"run", "call"} for a nested run, naming the outer run and the call that started it.
• Call. call is the call id. tool is the declaration's identity as {"repository", "version", "file", "name"}, and fingerprint its fingerprint (abi.md). args maps each parameter's name to a value slot. type is the hash of the blob holding the schema of the type a generic Tool's caller expects.
• Reply. outcome is {"Ok": slot}, {"Failed": slot}, {"BadReply": text}, {"NotRun": text} or {"Unknown": text}. The text is the reason the host or runtime gave; history does not classify it.
• Choice. task is the task whose task.first made the choice, and first the id of the task it picked; library functions such as task.race record the first they make.
• Stop. task is the stopped task. found is {"Finished": slot} when it had already returned, with its value, or "Running". closed the ids of its calls closed with no reply, in call-id order. The Stop is written first; replies already buffered for the task follow it as Reply facts (history.md).
• Checkpoint. Described below.
• End. outcome is {"Completed": slot} or {"Faulted": {"message": text, "at": {"module", "line", "column"}}}.

A paused run's history ends at its open calls; a pause writes no fact of its own. A run the host halts has no End; the halt is the host's record (execution.md).

Digest form

A fact's digest form is the fact with every value slot replaced by {"hash": h}, where h is the value's hash. A fact's hash is the hash of the canonical text of its digest form.

Hashing the digest form rather than the stored line means the chain commits to every value while letting the writer move a value inline or to a blob, and letting a host turn a value into a hole, without changing any hash.

Serves foundations: Honest withholding.

The hash chain

Every fact after Start carries in prev the hash of the fact before it. Chaining is not optional. Editing, deleting, reordering or splicing a fact breaks the chain from that point on.

The head is the hash of the last fact. Tampering is detectable against a head held somewhere the history's holder does not control, and that is all the chain claims. It does not authenticate the writer: a runtime that omits or invents facts writes a well-chained false history. A party holding the history and its only head can rewrite both. A recorded reply shows what was admitted, not that the reply was true (history.md).

While a run is writing, its newest fact is the least protected, because nothing after it vouches for it yet.

Serves foundations: Every record has a boundary; Bounded trust and disclosure.

Module sources

Every module source the program uses is stored as a blob holding the source file's exact UTF-8 bytes, std modules included, and named in Start. Replay, resume and fork read the program from these blobs. They never fetch a repository, consult a pin cache, or read the filesystem the run started on.

A source blob whose hash does not match its Start entry, or a program re-formed from the sources whose identity does not match program, is corruption.

Serves foundations: Deterministic reconstruction; Stable meaning.

Checkpoints

A Checkpoint fact records a top-level function and its arguments, which the language defines as the run's whole state at that point (history.md).

{ "n": 9, "prev": "sha256:…", "fact": "Checkpoint",
  "checkpoint": 1,
  "function": {"module": "support.flow", "name": "work"},
  "args": {"ticket": slot, "notes": slot, "round": slot, "pending": slot},
  "tasks": { "root/3#1": parked task, … } }

• checkpoint numbers checkpoints from 1 in the run. Call ids after it restart under that number.

• types lists a generic function's type arguments, one per type parameter in declaration order; a function with none has no types. A type is written:

  {"module": path, "name": name, "args": [type, …]}   a declared type, built-in ones included
  {"tuple": [type, …]}                                 a tuple
  {"function": {"params": [type, …], "result": type, "effect": "pure" | "through" | "tool"}}

  module is the path of the module that declares the type, as Start lists it, and args its type arguments. name is its name: the type declarations of one name in one module, which only types declared in blocks can share, are counted from 1, a top-level one first and the rest in source order, and the nth, for n from 2, is written name#n. effect is a function type's !pure, pass-through or !tool.

• args maps each parameter's name to a value slot, at the parameter's type with the type arguments in place. Values are in the canonical encoding, with two additions only checkpoints have:

  • a value of an opaque type is encoded like any other value of its shape, since the program made it;
  • a task in a Task<T> position is the id of the call it is parked on, a string, and is described in tasks.

• tasks describes each parked task by its call id:

  { "wrap":  null, or {"constructor": "Arrived", "at": "reply" or position,
                        "with": {other payload values}},
    "call":  {"tool", "fingerprint", "args", "type"},   as in its Call fact
    "reply": an outcome, when the reply was recorded before the checkpoint }

  wrap says how the task's result is built from the reply: the constructor, where the reply goes in its payload, and the payload's other values.

A checkpoint carries everything resume needs, including each parked call's request and any reply already recorded, so every fact between Start and the latest checkpoint may be moved out of the live history into an archive. Start always stays. The archive keeps its chain, and the checkpoint's prev still commits it. Archiving is not a hole: resume and replay from the checkpoint need nothing archived, and replay from Start reads the archive.

Rebuilding a checkpoint's arguments is not decoding (abi.md): every type is rebuilt, and a checkpoint that does not fit its function's parameter types, or whose type arguments name no type of the program, are not one per type parameter, or do not meet a type parameter's requirements (types.md), is corruption, or, for a fork onto a new program version, a refused fork (execution.md).

Serves foundations: Crash-resumable execution.

Holes

A host may replace a stored value with a hole, for example to remove personal data. It rewrites the value slot to {"hole": h} with the value's hash, and deletes the blob if no other slot uses it. The fact's hash does not change.

A reader reports what is missing in three classes and keeps them apart:

Holes and missing blobs make a replay that needs the value Incomplete (history.md). A hash is not a value: it cannot stand in for an argument or a reply, however well it commits to one. Corruption is neither: it is a storage failure, reported as one, never as divergence, because divergence is a statement about the run.

A hole carries only its hash. No reason, category or label is stored with it, and the format has no place for one. A host that withheld a value says why in its own records.

Serves foundations: Honest withholding.

Writing and durability

A fact is accepted when it and every blob it names are durable at the level the runtime states. The order history.md requires, each fact before its consequence, is met in terms of acceptance.

• A runtime states exactly what accepted means for it, such as written to the operating system, which survives process death, or synchronized to storage, which also survives power loss. It claims no more than it states, and an in-memory history claims no crash safety.
• Blob durability rides fact durability. A Call whose arguments sit in an unsynchronized blob is not accepted, however its line was written.
• A write or synchronization failure is reported before the consequence it was meant to protect is exposed.
• One writer appends to a history at a time.

A torn last line, an incomplete final fact left by an interrupted write, is truncation. A writer reopening the history removes it before appending, and a reader reports it as truncation, not tampering. Any other invalid line is corruption.

A history is append-only. A written fact is never edited, reordered or re-encoded in place; the only changes after writing are turning values into holes and archiving facts before a checkpoint, and neither changes a hash.

Serves foundations: Recorded before its consequence; Honest uncertainty.

Reading

A reader checks, before it serves anything to replay or resume:

1. the data version in Start, refusing one it does not know;
2. the hash chain, from Start or from the checkpoint it starts at;
3. every source blob against Start, and the program identity against the re-formed program;
4. every blob it serves, against its hash.

During replay the history only answers lookups. It never repairs, reorders or fills in a fact to make it match, and it has no dispatcher to fall back on.

The data version

The history format shares the data version with the value encoding and the Tool protocol (abi.md). Start records it as "major.minor".

• A reader decodes a version it knows or refuses the whole history. There is no partial acceptance and no field-by-field guessing; a fact with a member its version does not define is refused.
• Minors only add, so a reader of one minor reads every earlier minor of the same major. A change of meaning takes a new major.
• Stored bytes are never rewritten into a newer version.

No data version is stable before the first public release (runtime architecture).

Serves foundations: Stable meaning.