This document describes the integrity constraints enforced by the
graphden storage layer. The slot/fn-slot/binding model handles most
shape correctness through schema-level uniqueness (UNIQUE on the
junction tables); the only protocol-level constraint that needs
explicit code is dependency-cycle detection.
parent-ids
(many-to-many junction).(name, type-fn-id) pair, immutable post-create.(fn, slot) customization (value, ref, rename,
type override, terminal seal, list flags).(defprotocol GraphConstraints
(validate-no-dependency-cycle! [this owner-fn-id ref-fn-id]))
Storage implementations enforce this by walking the
fn → binding.ref-fn-id → binding-list-item.ref-fn-id graph.
Rule: The dependency graph (any ref-fn-id, in either bindings
or list-items) cannot form a cycle.
Rationale: Cycles cause infinite recursion at compile / execute time.
Example:
fn add-numbers
binding {slot s-other, ref-fn-id multiply-numbers}
fn multiply-numbers
binding {slot s-other, ref-fn-id add-numbers} ✗ dependency-cycle
Self-reference at the per-binding layer: validate-no-dependency-
cycle-impl carves out owner-fn-id == ref-fn-id — the bare self-ref
write doesn’t throw at this check. HOWEVER the higher-level
topological-sort (executor/composition/deps.clj) runs over the
whole fn-def set at sync time and rejects any cycle, including bare
self-refs. End result: graph-level recursion is structurally
impossible today — neither self-ref nor mutual-ref nor any
parent+ref combination passes both checks. See
docs/ARCHITECTURE.md § Part 3 — Recursion and Cycles for the
empirical demonstration, and RECURSION.md for the
:fix-based recursion path (shipped) that adds recursion without a
graph cycle.
Identity edges are not dependencies. A ref bound into a
:fn-ref-typed slot (ids/identity-edge?) names its target without
evaluating it — the compiled closure bakes the target’s id, nothing
is called through the edge. So the cycle walk skips it at every layer
(the per-binding constraint above, the sync-time topological-sort
via slot-res/fn-ref-arg?, and compile-eager’s ref-DAG), and two
services that each name the other (:service-endpoint :service …,
SERVICES.md § Endpoints)
are legal. The edge is still a real inbound reference for Used-by,
GC and cross-org rejection.
The write-time guard (crud.validation/cycle-check-rej) applies the
same rule to the edge being written: a ref-fn-id into a :fn-ref
slot (or under a binding-level type-override to :fn-ref) runs no
walk at all. On a binding or list-item update the guard keys the walk
off the stored row’s owner fields (a PUT {ref-fn-id} alone carries
neither fn-id nor binding-id), so re-pointing a ref is checked like
creating one.
How the walk runs. generic-constraints/dependency-closure loads
the ref’s execution graph through sp/resolve-execution-graph — the
same recursive-CTE resolver the executor compiles from, O(1) round trips
whatever the closure’s size — and walks it in memory over exactly the
edges forward-deps-of follows, skipping identity edges; constraint-
vector type NAMES ([:union :a :b], keywords the resolver does not
chase) are resolved in one batched query per round. There is no visit
cap on this path: binding a fn with a large closure (the editor’s own
router) is a normal write. (The per-fn walker it replaced — four queries
per visited fn, capped at 1000 visits → chain-too-deep — is gone.)
Error: :constraint-violation/dependency-cycle
These hold by virtue of UNIQUE constraints in the schema, not the
protocol:
| Entity | Unique key | Note |
|---|---|---|
fn |
(org-id, anonymous-hash) NULLS NOT DISTINCT |
anonymous fn dedup, per org — a tenant’s inline shape is its own row (records.ids/anonymous-fn-id mixes the org into the id); the platform’s package anons stay unique by hash |
fn-slot |
(fn-id, slot-id) |
a slot is exposed at most once per fn |
binding |
(fn-id, slot-id) |
one binding per (fn, slot) |
ns |
(org-id, parent-id, name) NULLS NOT DISTINCT |
per org, like branch: two orgs may both hold packages/team; a root namespace (NULL parent) is unique too |
branch |
(org-id, name) NULLS NOT DISTINCT |
per org |
A UNIQUE key declared after an entity’s table exists is landed on a
migrated DB by ensure-unique-indexes! on every migration pass
(CREATE UNIQUE INDEX IF NOT EXISTS); existing rows that violate the
new key leave a boot-time warning naming the index, never a broken boot —
clean the duplicates and the next pass lands it. A retired key is dropped
by name via *retired-indexes* in storage/postgres/migration.clj (an entry
is added at retirement and removed once every deployment is past it).
Two former base-table UNIQUE keys were retired because their
invariant is a property of the per-branch RESOLVED VIEW, not of the
identity table (soft-deleted identity rows persist by design and would
occupy the key forever; cross-branch divergence must not be blocked):
| Entity | Retired key | Now enforced by |
|---|---|---|
fn |
(namespace-id, name) |
check-fn-name-collisions! in VersionedStorage — live-view check on the writing branch AND on every branch forked off it, one batched read per write batch, advisory-lock-serialized (uniq/xact-lock!). Error: :constraint-violation/fn-name-collision |
binding-list-item |
(binding-id, position) |
check-list-item-position-collision! in VersionedStorage — the writing branch’s own view only (see below). Error: :constraint-violation/position-collision |
The same resolved-view rule covers resource-override.path
(check-resource-override-path-collisions!,
:constraint-violation/resource-override-path-collision).
Every check also runs where rows reach a view other than by a direct write:
:descendant-branch-id). The advisory-lock keys for these two leave
the branch out, so a write on main and one on a feature branch are
serialized against each other.List positions take the other side of that trade-off. Refusing main’s
append because some feature branch already has an item at that position
would leave main’s author no way out — they may not see that branch, and
the editor computes the position for them. So an ancestor’s append is
never refused on a descendant’s account; the descendant transiently shows
two items at one position (ordered by id, so the compiled list is stable),
and merging it back is refused with position-collision until its
author moves one of them — the author who can fix it is the one asked to.
slot.name and slot.type-fn-id are NOT individually unique — two
slots with the same name and type are distinct identities (sharing
is opt-in via fn-slot pointing at the same slot-id).
| Storage | Location |
|---|---|
| all backends | generic-constraints/dependency-closure loads the execution graph through resolve-execution-graph (the PostgreSQL recursive-CTE resolver), then walks its indexed rows in memory. constraints/validate-no-dependency-cycle-impl uses that closure to reject a cycle. |
The GraphConstraints extension is wired generically through
graphden.storage.protocol.generic-constraints.
src/graphden/storage/protocol/contract_tests.clj exercises the
protocol against any storage that registers GraphConstraints.
The suite covers the per-binding contract (allow nil ref, allow self-ref,
allow a distinct independent fn) plus concurrent CRUD. The sync-time
topological-sort rejection of graph cycles is a separate layer.
bb test # runs unit tests
Inheritance regression e2e tests live in
tools/browser-test/edit-inheritance-regression.test.js: