Skip to content

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.

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.tsx

The 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).

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.
  • onProgress fires after each edge is contracted with (contracted, total), where total is the edge count. Relayed from the worker; the dialog drives a determinate progress bar from it.
  • signal is an AbortSignal for cancellation. v1 cancellation is soft (see below).
  • Returns a Promise<TensorResult> on success. Rejects with a DOMException ("AbortError") on cancel, or a ComputeError on pre-compute validation failure / worker init failure / version mismatch / a structural error from Rust. Per-spider phase-parse failures do not reject — they surface on result.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.

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 workerPromise memoizes a single ES-module Worker, lazily created on the first computeTensor call and kept warm across calls. It is terminated on beforeunload.
  • The worker holds its own wasmPromise: on first message it dynamically imports public/wasm/zxw/zxw.js and calls its async default init, which fetches and instantiates the .wasm. The #[wasm_bindgen(start)] init_panic_hook runs automatically during instantiation.
  • If init fails (worker load error or version mismatch), the handler calls worker.terminate() and resets workerPromise = null before 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.

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.

  • If signal.aborted at call time, computeTensor rejects with AbortError immediately, 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 with AbortError. The dialog treats AbortError as “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 cancelled requestId. Cooperative cancellation (the Rust progress callback unwinding contraction) is a planned Phase 6 item.

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.

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.

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) in nodes.rs) — a standardized normalization (arity 2 unchanged; arity 0 → half). The scale is 1 at arity 2, √2 at arity 3, 1/√2 at 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⟩) and T[1, single-hot at output axis k] = 1 for each output k (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 as w-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, not e^{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.

compute_tensor(graph: &FrontendGraphSlice, on_progress: Option<&dyn Fn(usize, usize)>) -> Result<TensorResult, ComputeError> runs six phases:

  1. Empty short-circuit — no nodes → scalar 1.
  2. 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.)
  3. Initial groups — boundaries go into pending_boundaries; spider/box labels are parsed (parse failure → warning + phase 0); each tensor-vertex gets a Group { tensor, free_axes }. A rank-vs-degree guard surfaces DegreeOverflow.
  4. 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.
  5. Disconnected components — surviving groups combined via outer_product; dangling (degree-0) boundaries added as length-2 [1,0] tensors.
  6. Partition + flatten — free axes stably sorted by (role_rank, node_order, leg_index) where role rank is Input < Output < Neutral; apply permuted_axes; enumerate every multi-index in row-major order into data.

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.

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 of shape (or 1 for a scalar).
  • inputCount / outputCount — drive the matrix interpretation. With n = inputCount and m = outputCount, the rank-(n+m) tensor is displayed as a 2^m × 2^n matrix (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.

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.

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.