Compute Layer
The compute layer evaluates the tensor a ZXW diagram represents: each vertex is a small
tensor, each edge contracts two tensors along one leg, and input/output boundary vertices
declare the open legs that survive to the result. The whole pipeline runs in the browser — a Rust
crate compiled to WebAssembly, driven from React through a Web Worker. There is no server.
This page covers the boundary end-to-end: the frontend entry point, the worker bridge, the WASM
exports, the Rust crate, and the result/error model. The authoritative plan and contract live in
doc/plans.md in the app repo; this page is the companion overview.
Pipeline at a glance
Section titled “Pipeline at a glance”Compute button / ⌘/Ctrl+Enter → useCompute.requestCompute() src/lib/hooks/useCompute.ts │ snapshot the store, projectToDocument(...), take .graph │ validateGraphForCompute(graph) │ → errors land per-vertex in the store's validationErrors │ → any error rejects early with a ComputeError ▼computeTensor(graph, { signal, onProgress }) src/lib/compute/index.ts │ postMessage({ type: "compute", requestId, graph }) ▼Web Worker src/lib/compute/worker.ts │ lazy-import public/wasm/zxw/zxw.js, version-check ▼Rust / WASM crates/zxw (compute_tensor) │ contract edge-by-edge over union-find groups ▼TensorResult { shape, data, warnings, inputCount, outputCount } │ (+ progress messages, + structured errors) ▼ComputeResultDialog src/components/graph-editor/ComputeResultDialog.tsxThe compute path is deliberately separate from the Zustand store: a one-off
projectToDocument(...) snapshot is taken at request time and only doc.graph (never doc.view)
is passed to computeTensor. No compute state lives in useGraphStore — orchestration (promise,
progress, abort, open flag) is held in the useCompute hook
(src/lib/hooks/useCompute.ts), consumed by GraphEditor; the engine (worker lifecycle, version
handshake) is module-level in index.ts. The one store write the compute path makes is
setValidationErrors — per-vertex results that light up offending vertices (see below).
Frontend entry point
Section titled “Frontend entry point”computeTensor(graph, callbacks?) in src/lib/compute/index.ts is the single entry point
components call.
type ComputeCallbacks = { onProgress?: (contracted: number, total: number) => void; signal?: AbortSignal;};
export async function computeTensor( graph: GraphSlice, callbacks?: ComputeCallbacks,): Promise<TensorResult>;- Input is a
GraphSlice—{ nodes, edges }, graph-theoretic only. Positions, rotations, selection, and document metadata never cross the boundary. onProgressfires after each edge is contracted with(contracted, total), wheretotalis the edge count. Relayed from the worker; the dialog drives a determinate progress bar from it.signalis anAbortSignalfor cancellation. v1 cancellation is soft (see below).- Returns a
Promise<TensorResult>on success. Rejects with aDOMException("AbortError") on cancel, or aComputeErroron pre-compute validation failure / worker init failure / version mismatch / a structural error from Rust. Per-spider phase-parse failures do not reject — they surface onresult.warnings.
The sole non-test caller is the useCompute hook, whose requestCompute is wired to the
toolbar’s Compute button and the ⌘/Ctrl+Enter shortcut. GraphEditor renders the result dialog.
Pre-compute validation (src/lib/graph/validate.ts)
Section titled “Pre-compute validation (src/lib/graph/validate.ts)”Before anything reaches the worker, requestCompute runs validateGraphForCompute(graph) — a
frontend port of the structural checks that used to live in the Rust ComputeError variants. It
catches, in one pass: duplicate node ids (duplicate-node-id), edges referencing missing vertices
(vertex-not-found), boundary degree > 1 (boundary-degree), H-box arity ≠ 2 (h-box-arity), and
W-node topology — exactly 1 input and ≥ 2 outputs (w-input-count / w-output-count). The error
messages match the old Rust strings so the dialog’s remediation hints stayed consistent.
The results are published to the store on every compute via
useGraphStore.setValidationErrors(errors): validationErrors is a record keyed by vertex id
(ephemeral — cleared/replaced on every compute, never persisted, never on the undo stack), and
the offending vertices light up in the editor. If any error was found, the promise rejects
immediately with a ComputeError(first.kind, first.message) — no worker round-trip.
DegreeOverflow alone stays backend-only: it depends on the contraction’s intermediate state and
isn’t pre-checkable.
Web Worker bridge
Section titled “Web Worker bridge”The frontend never imports the WASM glue directly. src/lib/compute/worker.ts owns the module,
and index.ts owns the worker lifecycle.
- A module-level
workerPromisememoizes a single ES-moduleWorker, lazily created on the firstcomputeTensorcall and kept warm across calls. It is terminated onbeforeunload. - The worker holds its own
wasmPromise: on first message it dynamically importspublic/wasm/zxw/zxw.jsand calls its async default init, which fetches and instantiates the.wasm. The#[wasm_bindgen(start)] init_panic_hookruns automatically during instantiation. - If init fails (worker load error or version mismatch), the handler calls
worker.terminate()and resetsworkerPromise = nullbefore re-throwing — this prevents a permanently-rejected memo that would fail every subsequent call.
Message protocol (src/lib/compute/types.ts)
Section titled “Message protocol (src/lib/compute/types.ts)”Every compute/cancel message carries a requestId so the protocol could multiplex (v1 only allows
one in-flight compute; the UI disables the button while pending).
Main → Worker (WorkerRequest):
| Message | Purpose |
|---|---|
{ type: "compute", requestId, graph } |
Run a contraction. |
{ type: "cancel", requestId } |
Soft-cancel a run (v1: no-op in the worker). |
{ type: "version-check" } |
One-shot handshake (no requestId). |
Worker → Main (WorkerResponse):
| Message | Purpose |
|---|---|
{ type: "progress", requestId, contracted, total } |
After each edge. |
{ type: "result", requestId, result } |
The TensorResult on success. |
{ type: "error", requestId, error, errorKind? } |
A structural failure. |
{ type: "version-ok", version } |
Handshake reply. |
Version handshake
Section titled “Version handshake”Immediately after spawning the worker, getWorker() posts { type: "version-check" } and awaits
version-ok. The worker calls wasm.compute_api_version() (the compile-time crate version) and
the wrapper compares it against EXPECTED_WASM_VERSION, imported from
public/wasm/zxw/package.json (regenerated by wasm-pack on every build). The check is strict
string equality. On mismatch it throws a ComputeError("version-mismatch", …), terminates the
worker, and resets the memo so the next call retries fresh.
This exists so a browser-cached stale .wasm after a deploy can’t silently desync the
serde_wasm_bindgen contract.
Cancellation (soft in v1)
Section titled “Cancellation (soft in v1)”- If
signal.abortedat call time,computeTensorrejects withAbortErrorimmediately, without touching the worker. - If
signal.abort()fires mid-run, the wrapper posts{ type: "cancel", requestId }, removes its listeners, and rejects the caller’s promise withAbortError. The dialog treatsAbortErroras “computation cancelled”. - The worker’s
"cancel"arm is a no-op: the Rust contraction runs to completion regardless; the main thread simply discards the result for the cancelledrequestId. Cooperative cancellation (the Rust progress callback unwinding contraction) is a planned Phase 6 item.
WASM exports (crates/zxw/src/wasm.rs)
Section titled “WASM exports (crates/zxw/src/wasm.rs)”Feature-gated to the wasm feature, only compiled for wasm-pack builds:
| Export | Signature | Purpose |
|---|---|---|
ping |
() -> String |
Returns "pong". Round-trip smoke test for scripts/ping-wasm.mts. |
init_panic_hook |
#[wasm_bindgen(start)] |
Auto-runs on instantiation; installs console_error_panic_hook so panics reach console.error with a backtrace. |
compute_api_version |
() -> String |
Returns env!("CARGO_PKG_VERSION"). Consumed by the version handshake. |
compute_tensor |
(input: JsValue, on_progress?: Fn) -> Result<JsValue, JsValue> |
The real entry point. Deserializes input into FrontendGraphSlice, runs compute_tensor, serializes the TensorResult back. |
compute_tensor deserializes the FrontendGraphSlice via serde_wasm_bindgen::from_value, wraps
the optional JS callback in a Box<dyn Fn(usize, usize)> (callback errors are silently swallowed
so a UI bug can’t derail a contraction), and serializes the result back via
serde_wasm_bindgen::to_value. Structural errors throw the Rust Display text as a JS Error.
The Rust crate (crates/zxw/)
Section titled “The Rust crate (crates/zxw/)”crate-type = ["cdylib", "rlib"] — cdylib for wasm-pack, rlib for cargo test. Default
features empty; the wasm feature pulls in wasm-bindgen, js-sys, serde-wasm-bindgen,
console_error_panic_hook. Core deps: serde, serde_json, num-complex, ndarray,
thiserror.
The repo root is a Cargo workspace (Cargo.toml): members = ["crates/zxw", "crates/cartographer"] with default-members = ["crates/zxw"], so a bare cargo test builds and
tests only the compute crate. crates/cartographer is a git submodule — a standalone Rust CLI
(treewidth / Cartesian-decomposition research), kept as a workspace member for planned later
integration; cargo llvm-cov --workspace covers both. The root Cargo.toml also carries a dummy
[package] table (wasm-pack fails on a package-less workspace root) and a size-tuned
[profile.release] (lto, opt-level = "z", codegen-units = 1, panic = "abort") for the wasm
artifact. rust-analyzer.toml (mirrored in .vscode/settings.json) enables the wasm feature so
rust-analyzer indexes crates/zxw/src/wasm.rs, which is cfg’d out under the default features.
Module map:
| Module | Responsibility |
|---|---|
graph.rs |
The serde data model / WASM contract: FrontendGraphSlice, FrontendGraphNodeRecord, FrontendVertexData, FrontendGraphEdgeRecord, VertexType. All #[serde(rename_all = "camelCase")] to match the TS types byte-for-byte. The Frontend prefix marks the WASM-boundary mirror of the TS types in src/lib/graph/types.ts — names differ across the boundary, the serialized shape is identical. It also mirrors the edge-kind enum (EdgeKind in edge-types.ts — default, dashed_blue, dashed_light) via serde; the kind rides the graph slice but every kind contracts identically today. |
phase.rs |
Phase expression parser, a port of src/lib/phase/parser.ts. Same grammar and delimiter stripping; see Labels & Phases for a known cosmetic divergence in error-message fragments. |
tensor.rs |
Dense complex tensor over ndarray::ArrayD<Complex<f64>>. contract, trace, outer_product, permuted_axes, apply_2x2_to_axis. Hand-rolled (no BLAS — Complex<f64> isn’t LinalgScalar). |
nodes.rs |
The per-vertex tensor builders + build_vertex_tensor dispatcher. Shape is always (2,)*arity. The dispatcher covers all eleven vertex types: black_dot builds a phaseless Z spider (z_spider(arity, 0)), input/output return None (boundaries declare open legs instead). |
contraction.rs |
The contraction algorithm, compute_tensor entry point, TensorResult, and the union-find / free-axis / boundary machinery. |
error.rs |
PhaseError (parser) and ComputeError (top-level contraction). Both derive thiserror. ComputeError retains only DegreeOverflow — the other structural checks moved to the frontend. |
wasm.rs |
The WASM exports above (feature-gated). |
utils.rs |
Test-only assert_eq_cplx! macro. |
Vertex tensors (nodes.rs)
Section titled “Vertex tensors (nodes.rs)”Every generator’s tensor has shape (2,)*arity. Locked conventions:
- Z spider
z_spider(arity, phase): all-0 index → 1, all-1 index →e^{i·phase}, else 0. - X spider: the Z spider with a Hadamard applied per leg, then scaled by
√2^(arity−2)(t * √2^(arity as i32 − 2)innodes.rs) — a standardized normalization (arity 2 unchanged; arity 0 → half). The scale is 1 at arity 2,√2at arity 3,1/√2at arity 1. - H box: fixed arity 2,
1/√2 · [[1,1],[1,-1]]— one of the two builders with a normalization factor (the other is the X spider). - W node
w_node(num_outputs): directional, unnormalized. Axis 0 = input, axes 1..N = outputs.T[0,0,…,0] = 1(input |0⟩ → all outputs |0⟩) andT[1, single-hot at output axis k] = 1for each outputk(input |1⟩ → single-hot over the outputs); else 0. The contraction layer assigns the W’s target edge to axis 0 and source edges to axes 1..N, and enforces exactly-1 input + ≥2 outputs (validated frontend-side asw-input-count/w-output-count). - And gate: unnormalized indicator (all-1s index → 1).
- Z box
z_box(arity, phase): two-corner —T[0..0]=1,T[1..1]=phase(raw phase value, note^{iφ}— the box/spider particularity). X box = Z box with Hadamard per leg. - Black dot
black_dot: a phaseless Z spider —z_spider(arity, 0)regardless of any phase the user typed (the label is decoration only). - Empty: scalar 1 when isolated (0 legs); the 2×2 identity when wired with 2 legs — a
multiplicative identity wire under contraction. Any other degree is a
DegreeOverflow.
build_vertex_tensor returns None for Input/Output — boundaries have no tensor; they declare
open legs instead.
Contraction algorithm (contraction.rs)
Section titled “Contraction algorithm (contraction.rs)”compute_tensor(graph: &FrontendGraphSlice, on_progress: Option<&dyn Fn(usize, usize)>) -> Result<TensorResult, ComputeError> runs six phases:
- Empty short-circuit — no nodes → scalar 1.
- Build lookups — node index and degree map. (Structural checks like duplicate ids, boundary
degree, H-box arity, and W topology are already done frontend-side by
validateGraphForCompute— see above — so the Rust side trusts the input shape.) - Initial groups — boundaries go into
pending_boundaries; spider/box labels are parsed (parse failure → warning + phase 0); each tensor-vertex gets aGroup { tensor, free_axes }. A rank-vs-degree guard surfacesDegreeOverflow. - Union-find edge walk — for each edge (progress fires after each): boundary↔boundary →
identity wire (boundaries act as 2×2 identity tensors; see below); self-loop →
trace; boundary↔tensor → tag the tensor’s free leg with the boundary’s role (no contraction); tensor↔tensor same group → trace; tensor↔tensor different groups →contract, union, merge free axes. - Disconnected components — surviving groups combined via
outer_product; dangling (degree-0) boundaries added as length-2[1,0]tensors. - Partition + flatten — free axes stably sorted by
(role_rank, node_order, leg_index)where role rank is Input < Output < Neutral; applypermuted_axes; enumerate every multi-index in row-major order intodata.
The tensor is dense — every multi-index is enumerated, including zeros (no sparsification in
v1). Complexity is fine for ≤ ~12 open legs / ~30 total legs; beyond that, planned Phase 6 work
(contraction ordering via cotengrust, sparse tensors) kicks in.
The TensorResult
Section titled “The TensorResult”Rust (contraction.rs) and the TS mirror (src/lib/compute/result-types.ts) match field-for-field
via serde_wasm_bindgen:
type TensorResult = { shape: number[]; // e.g. [2, 2] for a 2×2 matrix, [] for a scalar data: [number, number][]; // flat complex values (re, im), row-major warnings: string[]; // per-spider phase-parse failures (computation still succeeds) inputCount: number; // count of input boundary nodes outputCount: number; // count of output boundary nodes};shape— every leg dimension is 2 (binary ZXW generators).[]means a scalar.data— flat complex values in row-major order, each a(re, im)tuple (never a{re, im}object). Length = product ofshape(or 1 for a scalar).inputCount/outputCount— drive the matrix interpretation. Withn = inputCountandm = outputCount, the rank-(n+m)tensor is displayed as a2^m × 2^nmatrix (rows = outputs, columns = inputs). Both zero → scalar.
The frontend reshapes this in src/lib/compute/matrix-format.ts: matrixEntry(data, row, col, outputCount) = data[col * (1 << outputCount) + row], with big-endian bit labels for row/column
headers.
Error model
Section titled “Error model”Three failure tiers, kept strictly separate:
Pre-compute validation errors reject immediately (no worker round-trip). validateGraphForCompute
(src/lib/graph/validate.ts) runs in useCompute.requestCompute before the worker is touched. Its
kinds and stable messages:
| Kind | Meaning |
|---|---|
duplicate-node-id |
Two nodes share an id. |
vertex-not-found |
An edge references a vertex id absent from nodes. |
boundary-degree |
An input/output vertex has degree > 1. |
h-box-arity |
An H box must have arity 2. |
w-input-count |
A W node must have exactly 1 input leg. |
w-output-count |
A W node must have at least 2 output legs. |
These kinds are also part of ComputeErrorKind (result-types.ts), so the dialog renders the
same targeted hints whether the error came from validation or (for overlapping cases) from Rust.
Runtime structural errors from Rust. The Rust ComputeError enum now contains only
DegreeOverflow — a vertex with more edges than it has tensor legs (or a self-loop/multi-edge that
exhausts free legs mid-contraction). It isn’t pre-checkable because it depends on the contraction’s
intermediate state. The worker sends it as { type: "error", error, errorKind }; the wrapper
re-throws a JS ComputeError carrying kind: ComputeErrorKind. The full kind set the UI
switches on is "version-mismatch", "load-failed", "vertex-not-found", "h-box-arity",
"boundary-degree", "degree-overflow", "duplicate-node-id", "w-input-count",
"w-output-count", "unknown". classifyComputeError (errors.ts) is the fallback classifier
when errorKind is absent.
Per-spider phase warnings do not throw. Inside compute_tensor, a spider/box label that fails
to parse is downgraded to phase 0 and a human-readable string is pushed onto result.warnings; the
computation continues. Non-spider labels are decoration only and never warn.
Status and roadmap
Section titled “Status and roadmap”Phases 0–5 of the plan are landed: LaTeX label rendering, the label-as-phase convention + JS parser, the Cargo workspace + crate + WASM build, the Rust parser + tensor model + builders, the contraction algorithm, and the WASM bindings + worker + frontend. The compute layer is fully functional.
Phase 6 (optimisation) is planned, not done, and includes: ZXW rewrites (spider fusion, identity
removal, π-commutation, bialgebra, Hopf, Euler — the trigger to adopt petgraph); contraction
ordering via cotengrust; exact / symbolic phases (accepting \alpha, \beta, … — currently a
v1 error on both sides of the boundary); sparse tensors; and cooperative cancellation. All sit
behind the same compute_tensor boundary, so the frontend won’t change.
Treat doc/plans.md as the contract — if you change the compute boundary, update the plan too.