This document describes the complete algorithm for laying out
function graphs in the Graphden editor. Internal data shape:
derive-fn-slot-views flattens (fn × slot) views into “arg row”
records that feed every walker; lookups are slot-id-keyed
(bindings, parent-bound-terminals, covered-slots,
child-covered-sources-for-fn). See src/graphden/layout/
(data.clj / graph.clj / builder_helpers.clj) for the
implementation — resources/packages/app/layout/impls.clj is only the
thin defbase boundary that calls into it.
The layout algorithm transforms a function graph into a 2D grid where:
Per-call-site model (load-bearing). The build stage emits one node
per call site, not one node per fn identity. A root fn keys by
fn-<id>; every nested fn keys by (caller-node-id, source-arg-id)
(add-fn-node, builder_helpers.clj), so two uses of the same fn from
two different bindings are two distinct nodes. Consequently the graph
handed to placement is a TREE — every node has exactly one parent, and
no node is shared between parents. This is why placement is a plain
depth-first tree walk (below) and why there is no shared-node path
analysis or column-offset alignment: those concepts have no referent
when nothing is shared.
Bounded unfolding. A reference to a function already on the current traversal path is drawn as a leaf with its incoming edge. Sibling uses of the same function still unfold separately. One layout unfolds at most 64 nested function calls; the next function also remains a leaf and can be opened as a new graph root. This bounds the rendering of cyclic or unusually deep imported graphs without changing their stored definitions or execution semantics.
Request → Load Data → Build Graph Elements → Place Nodes → Validate → Response
graphden.layout.graph performs Load Data + Build Graph Elements
(it labels these “Stages 1–2” internally); graphden.layout.core
performs Place Nodes + Validate + Response and parses the HTTP request.
Input: root-id (UUID), expansions (map of fn-id → level)
Process:
fn / slot / fn-slot / binding /
binding-list-item entities from storage.derive-fn-slot-views flattens each fn’s inheritance closure
into anchor rows (one per (fn, slot) pair) plus item rows for
list-bindings.fn-map: fn-id → fn entityarg-map: synth-arg-id → derived (fn, slot) viewargs-by-fn: fn-id → [view rows]slot-map: slot-id → slot entityfn-slots-by-fn: fn-id → [fn-slot junction rows]binding-by-fn-slot: [fn-id slot-id] → binding rowbindings-by-fn: fn-id → [binding rows]items-by-binding: binding-id → [list-item rows] sorted by positionTransform the database entities into graph nodes and edges based on expansions.
For each function, determine its “display level”:
Unified arg edges: EVERY unset arg — required, optional,
ref-propagated (deep), or a HOF lambda-param — is emitted as the same
placeholder node + edge shape by add-unset-arg-node, carrying
:optionalArg / :deepArg / :lambdaArg flags the client styles by
(lighter / sparser dashes / λ ghost). :lambdaArg follows the
executor’s call shape, not “any free under a HOF”: child-hof
resolves the boundary’s lambda-params through
renames/hof-lambda-params (authored :lambda-params, else the slot’s
structural [:fn {ARGS} RET], else alpha-equivalence — docs/CLOSURE_CAPTURE.md),
so a callee’s captured frees render as ordinary bindable placeholders;
only when that resolution refuses does the render fall back to the
older every-free-is-λ reading. The former compact badge strips
(:optionalArgs / :hofCapturedArgs) are retired; :deepFreeArgs
(the informational ⇣-strip on expanded inner nodes) remains.
A value node whose binding carries a resolver (an inline :vault-get
secret — its stored :value is the vault PATH) is flagged :secretRef true
(add-arg-value-node); the editor draws it as 🔒 <path> and routes its
click to the rotate form instead of the literal editor.
Sequence groups: the items of one list are not N
look-alike args. expand-sequence-anchor emits one entry per chain
item and then the append tail — the anchor’s own :unset entry,
:sequence-anchor? true (+ :seq-tail? true after items), rendered
as a free + placeholder after the last item. A list closed upstream
shows a locked tail instead of an actionable + (an empty chain keeps
its sentinel — the slot’s only presence on the card). The group-sequence-edges post-pass then
stamps every member edge (items + tail) with :seqGroup (source node +
slot), :seqIndex (chain order), :seqCount and :seqLabel (the bare
slot name), and the same :seqGroup / :seqIndex on the target nodes.
Items follow their owners’ reverse BFS inheritance order, matching the
executor, then their position within each owner’s list. Synthetic anchor
source links point at the defining slot and do not determine that order.
The editor draws one labelled trunk per group that fans out AFTER
the type chip — a plain arg splits at the bend before its chip, a list
element after it — and the per-item × moves onto the item’s branch.
Inheritance chain: [fn-id, parent-id, grandparent-id, ...]
When expanding to level N:
Node IDs encode the call site, so the same fn used from two places
produces two nodes (add-fn-node in builder_helpers.clj):
| Context | Node ID Format | Purpose |
|---|---|---|
Root node (or any node with no source-arg-id) |
fn-{original-fn-id} |
Canonical root id |
| Nested reference | fn-{caller-tag}-{source-arg-id} |
Scoped to the (caller, arg) that referenced it |
caller-tag is the caller’s node-id with its leading fn- stripped, so
prefixes don’t double at each nesting level.
Key insight: because the id folds in the referencing (caller,
source-arg-id) pair, a fn referenced from N different bindings becomes N
distinct nodes — matching Clojure call-site semantics. There is no
shared “canonical” node reused across references; sharing does not exist
in this model.
Bindings are arg values that flow through inheritance:
add-10 (binds a=10)
└── inherits from: add (has args: a, b)
When processing add-10:
- bindings = {add/a-arg-id → {value: 10, arg-name: "a"}}
- These bindings apply when showing add's arg "a"
Binding propagation rules:
favicon-route → metrics-handler.Defines-own-ref rule (critical for coll chains): When a structural node has an arg that DEFINES its own ref (the source arg has no ref), that arg’s ref-id takes precedence over any ancestor binding with a different ref-id.
Example: editor-routes → list-11 → list-10 → list-10-9
(where list-11.coll → list-10, list-10.coll → list-10-9)
When processing structural list-10:
- list-10.coll has ref-id = list-10-9 (defines own ref - source has no ref)
- Binding from list-11.coll has ref-id = list-10 (different from list-10-9)
- Because list-10 DEFINES its own coll ref, use list-10-9, NOT the binding's list-10
- This ensures the coll chain continues: list-10 → list-10-9 → list-10-8 → ...
Without this rule, the binding would incorrectly override the structural ref, breaking the coll chain and hiding all nested items.
When determining which bindings “belong inside” a structural ref-fn vs should be shown at the expansion root, the algorithm collects arg-ids from the ref-fn’s inheritance chain. If a binding’s source chain leads to one of these arg-ids, it’s considered “covered” by the structural ref — shown there, not at the root.
Problem: When the expansion root and the ref-fn share a common ancestor (e.g., both
inherit from conj-any), the shared ancestor’s args appear in BOTH chains. This causes
ALL bindings whose source chains pass through the shared ancestor to be incorrectly
filtered as “covered.”
Example: editor-routes → list-11 → conj-any (expansion chain)
list-10 → conj-any (ref-fn chain)
conj-any has args: coll (9bee1b2f), item (6a08596a)
Without exclusion:
6a08596a is in ref-fn-arg-ids (from list-10's chain including conj-any)
ALL editor-routes' items have source chains ending at 6a08596a
→ ALL items filtered as "covered" → items disappear from graph!
Solution: Shared ancestor exclusion. When collecting arg-ids from ref-fn chains, EXCLUDE fns that also appear in the expansion root’s full inheritance chain.
This rule applies in these places in the code:
| Location | What it collects | Effect of exclusion |
|---|---|---|
collect-expanded-args → ref-fn-arg-ids |
Args from displayed ref-fns | Items not filtered as “belonging inside ref” |
process-fn → displayed-ref-arg-ids |
Args from displayed child ref-fns | Item bindings not filtered inside structural nodes |
child-covered-sources-for-fn |
Slot-ids exposed by child ref’s closure | Slots not mistakenly “covered by coll child” when they live in the shared ancestor |
The deep ancestor-ref subtree that expansion previously re-walked per
binding is now resolved through the migration-target index in
process-expanded-fn-impl (ancestor-ref-fn-id-index plus the
migration-via-* branches in graph.clj): it answers “does this fid
appear inside an ancestor ref’s chain?” in O(1) instead of walking the
subtree for every binding.
{:nodes [{:data {:id "fn-xxx" :label "name" :type "fn" ...}} ...]
:edges [{:data {:id "e-xxx" :source "fn-a" :target "fn-b" :argName "handler"}} ...]}
A composed fn-def with no own bindings on a slot inherits its
parent’s value / :list-append items. The layout intentionally
does NOT emit those values as arg-nodes under the CHILD’s fn —
the child’s args-by-fn slice is empty for inherited-only slots.
Instead, the editor’s fn-overlay walks parent-ids at render
time and exposes the parent rows on the SAME card (the ancestor
expansion strip). Clicking an ancestor row navigates to that fn,
whose own layout DOES emit the bound values + sequence items.
What this means for layout-API consumers (UI tests, alternate front-ends):
/api/graph/layout?root=child returns just the fn
node + any own-binding placeholders. Inherited values are NOT
in the response.:expansions argument in the layout request.This split is the load-bearing assumption pinned by the
graphden.tools.browser-test/edit-inheritance-regression.test.js
e2e test — parent layout exposes items, child layout doesn’t.
A template’s holes often live deeper than the root card’s slot
surface: an extension of :service-get has service / path free,
but both belong to fns reached through the parent’s ref-bound url
(:_service-url-join → :service-endpoint), which the collapsed card
does not render; a Ring wrap’s base-handler is a free fn-typed slot
one ref down. After the walkers, builder-helpers/emit-root-deep-frees!
runs once for a composed / base-fn root: every entry of
compile.surface/public-free-entries — the executor’s public surface,
the same set the Run form lists: the surface walk plus the HOF closure
captures minus everything an enclosing scope supplies (lambda params,
env-bindings) — whose slot has no placeholder yet becomes an unset node
with an edge from the root, flagged :deepArg. Captures that are
OPTIONAL stay off the card (they are the HOF target’s knobs, listed in
the Run form and named — with their target — by the inspector’s
“Captured inside” section); a REQUIRED capture is a real hole and is
drawn. Optionality is the entry’s own :optional? (the executor’s
effective-required at the slot’s owner), so the card, the form and the
inspector cannot disagree. A listener’s card therefore shows its own
slots only (real-graph test). The node names the ROOT fn
(fnId) keyed by the inner slot, so the + binder writes a binding on
this fn — closure capture, what a fn-def :args {:service …} on the
same fn stores. Type-row roots skip the pass (their only slot is the
synthetic one hidden above).
Placement walks each node’s children in a fixed order. Under the
per-call-site model every child has exactly one parent — nothing is
shared — so ordering is a plain stable sort by child type, with
original insertion order preserved inside a type (order-children /
get-child-type in core.clj):
| Type | Rank | Detected from node :data |
|---|---|---|
:fn |
0 (first) | :type = "fn" |
:fixed |
1 | :type = "arg" |
:free |
2 (last) | placeholder (:isPlaceholder), missing data, or anything else |
So a node’s fn children come first (in their original order), then its fixed args, then its free args. There is no divergence/upper-path/lower-path ordering — those existed only to route edges into shared nodes, and there are no shared nodes here.
One exception: the members of a sequence group (:seqGroup on the node
data) sort as a single block — ranked and placed where the group’s
first-emitted member fell, ordered inside by :seqIndex — so a list of
mixed refs and literals keeps its chain order and the fanned-out
branches never cross.
layout-graph (core.clj) does a depth-first placement of the tree.
Because the element graph is a tree, no two nodes ever contend for the
same cell by construction; the row search below only has to dodge cells
already filled by earlier branches.
build-branch). Node i in the branch is assigned column start-col + i.place-subtree)Step 1 — Build the horizontal branch. From SELECTED, follow the first sorted child repeatedly, assigning consecutive columns:
branch = [SELECTED@col]
current = SELECTED
while current has children:
first = sorted_children[current][0]
branch.append(first@(col+1))
current = first
Step 2 — Find the row (column-aware compaction). Starting at min-row
(0 for the graph root, else parent-row + 1), scan downward for the first
row where every column used by the branch is free (find-row-for-branch
→ branch-fits-at-row?). Only the branch’s own columns are checked, so a
short branch can share a row with a deeper subtree whose nodes sit in
columns the branch doesn’t touch.
Step 3 — Place the branch at that row (place-branch), one node per
consecutive column.
Step 4 — Reserve the vertical edge. If the branch landed more than one
row below its parent, mark the intervening cells in the child’s column as
{:vertical-edge true} (reserve-vertical-edge) so no later branch can
cross that descending edge. Adjacent rows need no reservation.
Step 5 — Recurse into remaining children, RIGHT-TO-LEFT. Walk the branch
in reverse; for each branch node place its non-first children (each as a
full subtree via place-subtree), starting the row search at
branch-row + 1 and the column at node-col + 1.
Key invariant: a node’s ENTIRE subtree is placed before its next sibling is started.
Graph:
A
├── B
│ ├── D
│ └── E
└── C
└── F
Step 1: SELECTED = A, branch = [A, B, D] (first-children chain)
Step 3: place at row 0 → A(0,0) B(0,1) D(0,2)
Step 5: process children right-to-left:
- D has no more children
- B has child E → min_row = 1, branch = [E] at col 2 → E(1,2)
- A has child C → min_row = 1, branch = [C, F] uses cols 1-2
row 1: col 2 occupied by E → try row 2 → C(2,1) F(2,2)
Result:
col: 0 1 2
row 0: A B D
row 1: E
row 2: C F
C shares no row with E because col 2 is taken at row 1; it drops to row 2.
Graph:
A
├── B → C → D (horizontal branch at row 0, cols 1-3)
│ ├── E (child of C)
│ └── F (child of C, pushed to row 2)
└── G → H
Processing:
1. Place branch A, B, C, D at row 0.
2. Right-to-left:
- C's child E → row 1, (1,3)
- C's child F → col 3 busy at row 1 → row 2, (2,3);
reserve vertical edge at col 3, row 1 (C@row0 → F@row2)
- A's child G → branch [G, H] uses cols 1-2; row 1 free there → G(1,1) H(1,2)
Result:
col: 0 1 2 3
row 0: A B C D
row 1: G H E
row 2: F
G shares row 1 with E because their columns don’t overlap (G/H in 1-2, E at 3), and the reserved cell at (row 1, col 3) keeps any branch off the C→F edge.
place-elements (and the test entry compute-layout-matrix) attach the
grid positions and a validation record, returning the response shape:
{:nodes [...]
:edges [...]
:grid-pos {node-id {:row r :col c} ...}
:validation {:valid true/false :issues [...] :warnings [...]}}
validate-layout (core.clj) separates fatal structural problems
(any one makes :valid false, reported in :issues) from advisory
signals (reported in :warnings, :valid stays true):
:type |
Severity | Condition |
|---|---|---|
no_root |
fatal | Input nodes exist but no zero-in-edge root was found (empty graph or a pure cycle), so nothing could be placed. |
collision |
fatal | Two placed nodes share a (row, col) cell. |
orphan |
advisory | A root exists but some input node has no path from it, so the DFS never gave it a position. Dropping a node unreachable from the selected root is intended behaviour (a fn graph often has sibling nodes off the root’s subtree), so this is surfaced for observability without invalidating the layout. The message lists the unplaced node-ids. |
When layout changes (expansion, preview), the anchor node stays stationary while all other nodes move relative to it. This prevents disorienting jumps.
Anchor selection priority:
anchorNodeId — set by expansion click or preview hover/clearpreviewState mapCritical timing: anchorNodeId and old position must be captured BEFORE the async
fetchBackendLayout() call (editor-render.js grabs capturedAnchorNodeId), because
callers clear anchorNodeId synchronously after calling renderGraph() (which is
async). After fetch completes, the saved anchor position is used to compute the offset
applied to all new positions.
Preview anchor: Both applyHoverSpec (hover) and clearPreview (mouseleave) set
anchorNodeId before calling renderGraph. Without this, clearing a preview would
cause the graph to jump back to unanchored position, then the node re-enters focus,
re-triggering preview — creating an infinite animation loop.
When layout problems occur:
Identify the symptom: Which nodes are misplaced? What’s the expected vs actual position?
Update this document if algorithm needs changes
src/graphden/layout/ - The layout algorithm: Load Data + Build Elements in data.clj / graph.clj / builder_helpers.clj (derive-fn-slot-views, process-fn, collect-expanded-args, …); Place Nodes + Validate + request parsing in core.clj (order-children, layout-graph, validate-layout, parse-layout-request)resources/packages/app/layout/impls.clj - Thin defbase boundary (_load-graph-cached, _layout-build-apply, …) that calls into the algorithm abovetest/graphden/layout/ - Layout teststools/browser-test/ - Visual browser tests