# Engineering design

## Boundary

`graphledger` is pure MoonBit. CLI JS FFI performs filesystem enumeration,
file reads/writes, exclusive immutable snapshot publication and process exit
status. It performs no graph analysis. There are no third-party dependencies.

## Identity and canonical form

Node IDs and edge IDs are case-sensitive strings. Edge IDs should be assigned
by a source exporter when multigraph relationships need stable identity.
Default IDs encode the endpoint/type tuple as JSON, avoiding delimiter
collisions. Canonical snapshots sort records by ID and recursively sort JSON
object keys, normalize Double representations, and preserve array order.
Source fields participate in identity of content: moving a source location can
therefore produce a metadata diff even when connectivity does not change.

The pair of rolling checksums is a convenience label, not a security hash.
Immutable publication compares complete canonical content if the label exists.
An untrusted writer can still modify snapshot files outside the tool. Readers
validate graph schema and references, not a signed chain of custody.

## Algorithms

- Degrees and weak components: adjacency maps and iterative BFS, O(V+E).
- Acyclicity: Kahn elimination, O(V+E).
- Strong components: iterative Kosaraju, O(V+E) after O(V log V + E log E)
  canonical sorting. No recursive graph traversal.
- Cycle proof: explicit DFS frames and gray-state back edges reconstruct one
  closed directed path. A cycle tail is not claimed to be a cycle member.
- Impact: sorted adjacency + BFS, one shortest witness path per reachable
  node. Time includes sorting and output path materialization. On a long chain,
  full paths require quadratic output space; this API is intended for bounded
  engineering graphs rather than unbounded graph analytics.
- Diff: ID maps and semantic canonical record comparison; linear lookups after
  sorting, plus property serialization cost.

No all-pairs transitive closure is stored in production. The exhaustive test
oracle independently uses transitive closure to validate SCCs and cycle proofs.

## Persistence and failure behavior

`commit` writes and fsyncs a unique temporary file, then publishes it using an
exclusive hard link. A concurrent publisher of identical content is accepted;
a different body under the same fingerprint fails. Temp files are cleaned up
in normal error handling. A process crash may leave a `.tmp-*` orphan. This is
an immutable object directory, not a transactional database or a branch catalog.
Directory fsync/power-loss durability is not promised across all filesystems.

Ordinary report output uses direct writes. It refuses paths aliasing an input,
but it is not a transactional multi-output export. JSONL currently buffers all
records before validation, allowing forward references.

## Verification

The repository includes unit tests, exhaustive 3-node graph enumeration,
2000-node deep-chain checks and Node CLI integration tests. The verifier checks
formatting, compiler diagnostics, tests and JS build. The CLI is validated on
Windows/Node; native or browser hosts would need their own I/O adapters.

## Future work

Versioned snapshot envelopes/migrations, content-addressed cryptographic hashes,
CommonMark parser coverage, typed property querying, multi-seed impact delta,
retained indexes and bounded-output traversal are follow-up work, not current
capabilities. Never silently weaken a rule on parse failure.