lex-vcs

Agent-native version control for Lex: a typed operation log plus an attestation graph. Where Git versions files by snapshotting text, lex-vcs versions the content-addressed AST by recording typed deltas — and records the type-check verdict, the prompt that caused the change, and the evidence that the result is sound, all as first-class addressable objects.

This is the engine layer. The user-facing surfaces — the CLI (lex op, lex blame, lex attest, lex merge, …) and the HTTP API (lex serve → /v1/merge/*, /v1/stage/<id>/attestations) — compose on top of the types this crate exports.

Why an op log instead of file snapshots

A snapshot-of-pointers model (Git's "named pointer to a tree") can't answer the questions an agent harness asks:

• "Show me everything agent X did under intent Y in the last hour" without that being a pre-named branch.
• "Spawn 20 parallel exploration branches per task and discard 19" in O(1).
• "Did this exact verification already run?" without rerunning it.
• "Two agents made the same logical change — do they agree?" without a merge.

lex-vcs answers all of these because the unit of writing is an [Operation] — a typed delta keyed by (kind, payload, parents) — and branches are [Predicate]s over the log rather than snapshots.

What's shipped

The crate landed as the foundation slice of #129 and grew through a sequence of tier-2 issues. Each module is independently usable:

Core op log (#129)

• [Operation] / [OperationKind] — the typed delta enum: AddFunction, RemoveFunction, ModifyBody, RenameSymbol, ChangeEffectSig, AddImport / RemoveImport, AddType / RemoveType / ModifyType, Merge, and the #280 typed transforms (InlineLet, RenameLocal, ReplaceMatchArm). Carries declared effects and [budget(N)] costs inline so the write-time gate and lex op log --budget-drift don't need to rehydrate the AST.
• [OpId] — lowercase-hex SHA-256 of the canonical form of (kind, payload, parents). Two agents producing the same logical change against the same parent state get the same OpId, so the store dedups and surfaces "we agree" without a merge.
• [OpLog] — persistence + DAG queries. <root>/ops/<op_id>.json, atomic tempfile-+-rename writes, idempotent on existing ids. Includes packfile consolidation (#261): OpLog::repack rolls loose files into deterministic, content-addressed pack-<hash>.{pack,idx} files for stores past ~10k ops.
• [apply] — the narrow apply gate: validate parents against a known branch head, then persist. No type checking here (that's the next layer).

Write-time type-check gate (#130)

• [check_and_apply] wraps apply with a lex_types:: check_program pass over the candidate program. When this gate is the only path that advances a head, the store's invariant becomes "every accepted operation produces a program that type-checks" — the cascading-breakage failure mode (agent A commits a broken stage, agent B builds on it, CI catches it hours later) becomes impossible by construction. Effect violations surface here too, since check_program reports undeclared-effect calls as TypeErrors.

Intent linkage (#131)

• [Intent] / [IntentLog] — captures why a change happened: the prompt, the model that interpreted it, and the session that grouped it with siblings. [IntentId] is the SHA-256 of (prompt, session_id, model, parent_intent) — created_at is deliberately excluded so the same prompt dedups across runs. Stored in its own namespace (<root>/intents/<IntentId>.json) so prompts — which may carry sensitive data — stay out of the op log and per-intent ACLs remain tractable.

Attestations (#132)

• [Attestation] / [AttestationLog] — persistent evidence about a stage. Where Operation records what changed and Intent records why, an attestation records what we know about the result: TypeCheck, Examples, Spec, DiffBody, SandboxRun, Trace, plus the governance kinds (Override, Defer, Block / Unblock, ProducerBlock / ProducerUnblock, ProducerTrust / TrustWaived) and the repair-loop breadcrumbs (RepairHint, RepairAttempt), and the structured Review verdict (Approve / Reject / RequestChanges) that closes the Candidate->Promote gap (#836). [AttestationId] hashes (stage_id, op_id, intent_id, kind, result, produced_by) — cost, timestamp, and signature are excluded so the same logical verification dedups. Stored at <root>/attestations/<id>.json with a by-stage/ index for cheap per-stage listing. [is_stage_blocked] / [active_producer_block] drive CI gates.

Predicate branches (#133)

• [Predicate] — a saved query over the log (AncestorOf, Intent, And / Or / Not, …). Today's main is AncestorOf { op_id: <head> }; an exploration branch is just Intent { intent_id: <id> }. Discarding a branch is O(1): stop using the predicate; the ops it referenced stay reachable. Author and DescendantOf are deferred pending an author field and a forward-DAG index (see the module docs).

Merge (#134)

• [merge] — op-DAG three-way merge: find the LCA of two heads, diff the ops on each side, group by the SigId they touch, and classify each group as auto-merge or [ConflictKind]. This layer is whole-function: two divergent bodies for one sig are a ModifyModify conflict.
• [merge_bodies] — typed three-way merge inside a function (#838): a structural merge of three canonical CExpr bodies that composes disjoint subtree edits (different match arms, different let bindings) and conflicts on overlap. lex-store's merge path calls it for a ModifyModify, accepting the result only if the merged body also type-checks — so two agents editing different arms of one function no longer collide, the piece git structurally cannot do.
• [MergeSession] — a stateful state machine for programmatic conflict resolution: start collects conflicts, resolve/ resolve_checked accept batched [Resolution]s. resolve does structural validation only (known conflict, custom op acknowledges both sides). resolve_checked additionally type-checks each resolution against the composed program the moment it's submitted (#834): because the engine has no store access, it takes an injected [ResolutionChecker] — lex-store's MergeResolutionChecker overlays the projected post-merge delta on dst's head and runs the type checker (Store::typecheck_merge_projection), so a pick that leaves the merged head broken is rejected with ResolutionRejection::TypeError right away rather than at commit. commit finalizes once no conflicts remain; the store-backed commit paths then land the merge through Store::apply_merge_op_gated, which re-checks the real post-merge head before it moves (#833). The merge cost is paid once per session, not once per resolution batch — which matches the agent loop "submit 50 resolutions, see which broke type-checking, fix them, retry." Backs the CLI lex merge {start, status, resolve, commit} and the /v1/merge/* HTTP routes (the /v1/merge/<id>/resolve route uses resolve_checked).

Diffing (lex ast-diff / lex diff)

• [compute_diff] + [DiffReport] — AST-level structural diff between two sets of FnDecls (added / removed / renamed / modified, with body patches).
• [diff_to_ops] — lower a DiffReport (plus import deltas and old-head info) into the typed [Operation] sequence that reproduces it. This is how an edited source file becomes a committed run of ops.

Signing (#227)

• [Keypair] / [verify_stage_id] — Ed25519 signing of the StageId string (not the AST), so authorship survives canonical- AST format changes and stays cheap and cross-tool reproducible. Public keys → 64 hex chars, signatures → 128 hex chars, lowercase no-0x, matching the OpId / StageId convention.

Format migration (#244)

• [migrate] — when [OperationFormat] gains a variant, every OpId rotates (the canonical pre-image changes) and parent references must be remapped transitively. plan_migration returns a topologically-ordered [MigrationPlan]; apply_migration writes it in two phases (write-new, then delete-old) so a crash mid- migration leaves the store readable. Today only OperationFormat::V1 is in production — the machinery exists so the next format bump is a recipe, not a rewrite. Branch-head and attestation cascades are handled by the CLI (lex store migrate-ops) and a follow-up, respectively (see the module docs).

Identity and the canonical form

Every id in this crate (OpId, IntentId, AttestationId) is the lowercase-hex SHA-256 of a canonical JSON pre-image. The V1 canonical-form rules are the authoritative spec in [src/canonical.rs] and are load-bearing — violating any of them silently rewrites every id in every existing store:

1. Compact JSON (no pretty-printing).
2. Field order follows the struct/enum declaration.
3. BTreeSet for unordered string sets ([EffectSet]).
4. BTreeMap for unordered key-value collections (StageTransition::Merge { entries }).
5. parents sorted + deduped before hashing.
6. Empty parents arrays are emitted in the canonical form (this differs from the on-disk shape, which skips them).
7. Optional fields use skip_serializing_if = "Option::is_none", so adding a Some(...) where None was is a deliberate OpId rotation (the trick that lets intent_id / budget_cost be added without rotating pre-existing ids).
8. SHA-256 → 64 lowercase hex chars.

These are part of the project's stability contract — see docs/INVARIANTS.md and the authoritative spec in docs/design/canonicalization.md before writing code that depends on a hash being stable.

On-disk layout

<root>/ops/<op_id>.json                          # OperationRecord, loose
<root>/ops/pack-<hash>.{pack,idx}                # consolidated (repack)
<root>/intents/<IntentId>.json
<root>/attestations/<AttestationId>.json         # source of truth
<root>/attestations/by-stage/<StageId>/<id>      # index (rebuildable)

All writes are atomic (tempfile + rename) and idempotent on existing ids.

Hashing note

This crate uses SHA-256 (via sha2) for all identity, reusing what lex-store already uses for stage and signature identity. OpId is opaque, so swapping to Blake3 for performance later is a one-line crate change.

Tests

cargo test -p lex-vcs

The suite under tests/ covers the load-bearing invariants:

• opid_golden.rs / opid_property.rs — OpId stability: golden vectors plus property tests that the canonical form is order-independent for sets, maps, and parents.
• attestation_trace.rs / attestation_cascade.rs — attestation identity and the block/unblock cascade.
• budget_accounting.rs — [budget(N)] drift tracking across the op kinds that carry from_budget / to_budget.
• migrate.rs — the two-phase format migration and parent remap.
• repack_conformance.rs / merge_perf.rs — packfile determinism and merge performance.

Where this fits

lex-vcs depends only on lex-ast and lex-types (kept narrow on purpose — no lex-store, no lex-syntax in the non-dev path), so it can be the shared home for DiffReport and diff_to_ops without a circular dependency. lex-store builds the durable store on top of it; lex-cli and the HTTP API expose it to users.