The Stable Map Spec

That is fine for a picture and fatal for a map. Recognising where something sits is most of what makes a map useful, and nobody can recognise a place that moves. The cost is invisible in a demo, where the diagram is seen once, and it dominates in daily use, where it is seen a hundred times.

This got worse as generation got better. When a diagram was drawn by hand once a quarter, it held still because nobody touched it. Deriving it from the source on every change fixed the accuracy problem and created a legibility problem in its place: the picture now changes faster than any reader can form a memory of it. The tools solved the first problem well and mostly have not noticed the second.

Nothing here requires a new algorithm. It requires a tool to say what it guarantees, in terms someone can rely on and someone else can check.

Graph drawing research has studied this since the early 1990s under the name preserving the mental map, from work by Misue, Eades, Lai and Sugiyama, and there is a substantial literature on dynamic graph drawing and layout stability since. Anyone building in this area should read it first. We did, and we are not claiming the insight.

Two things are genuinely unaddressed. That research generally assumes a graph mutated incrementally, whereas a map derived from a repository is re-derived wholesale from a source that people edit all day, which makes the identity question harder than the layout question. And none of it is expressed as something a product can commit to and a customer can verify. A body of technique exists; a contract does not.

The precedent for closing that gap is the C4 model, published as a free notation by its author while the tooling was sold separately. The notation spread because it was useful to people who never bought anything. This aims at the same shape.

Source is the artefact the map is derived from: a repository, a schema, a set of traces. Derivation is producing a graph from that source, and regeneration is doing it again later, after the source has changed.

Identity is the rule that decides whether a thing in this derivation is the same thing as one in the last. Region is the area a node is allotted, which contains that node and all of its descendants. Layout is an assignment of coordinates to nodes.

Must and should are used as RFC 2119 uses them. A tool that fails a must does not conform. A tool that fails a should conforms, and owes its users an explanation.

They are ordered by dependency rather than importance. Identity makes continuity expressible, containment makes movement bounded, and proportionality is what the other four add up to from the reader's side of the screen.

A place stays findable. A link to a location still lands there next month. A screenshot in a document is still true. “It is over on the left, under billing” survives being said out loud on a Tuesday and acted on the following week.

This falls out of P1 and P4 rather than being a rule of its own, and it is worth stating separately because it is the thing being bought. The properties are how a tool earns it and how you check that it did.

Each test takes a source, derives a layout, changes the source, and regenerates. Compare coordinates exactly. Approximate equality is a failure here, not a pass with rounding, because “nearly where it was” is precisely what an unstable layout already gives you.

1. P1Identity. Derive twice from an unchanged source. The set of identifiers must be identical. Then rename nothing and move one file, and check whether the tool's published identity rule predicted what happened.
2. P2Determinism. Derive twice from the same source and the same prior layout, in separate processes. Every coordinate must match exactly.
3. P3Containment. For every node, assert its position falls inside its parent's region. For every pair of siblings, assert their regions do not intersect. This one needs no regeneration at all.
4. P4Continuity. Add one leaf to a subtree. Every node outside that subtree whose region still contains its old position must have identical coordinates. Any node that moved must be explainable by the tool's published conditions.
5. P5Proportionality. Run the previous test at increasing sizes: one leaf, five, fifty, a doubled branch. Record the count of unrelated nodes that moved at each step. The result is a curve, and the tool should have told you in advance roughly where it bends.

A tool conforms when the four must tests pass, it publishes its identity rule, and it publishes the conditions under which a surviving node moves. Reporting the P5 curve is part of conforming even when the curve is unflattering.

Identity is derived from the path. A file that moves or is renamed is a new node with a new identifier, so it loses its position and so does everything under it. This satisfies P1 as written and fails what a reader actually wants, which is for a renamed thing to still be the same thing. Content-based identity would fix it and is not built.

Proportionality holds, and then stops. Running the P5 procedure against our own engine: adding one, two or five files to a neighbouring branch moved no unrelated node at all, with exact coordinate equality. Tripling a branch's size moved most of the map, some nodes across most of the world. There is a cliff rather than a slope, and where it sits depends on the shape of the change.

A large restructure can rotate an untouched subtree. When a region changes shape rather than only size, the internal arrangement of even an unchanged subtree can come back transposed: what sat side by side now sits stacked. Nothing in the five properties forbids this, which is arguably a gap in the specification rather than only in our implementation. We would rather publish that than quietly leave it out.

Which algorithm to use. Treemaps, force-directed layouts with pinning, hierarchical placement: any of them can satisfy all five. Naming one would turn a contract into a recipe and exclude better ideas.

What it should look like. Notation, shape, colour and level of abstraction are not addressed here. The C4 model answers that question and answers it well; this one is orthogonal to it and the two compose.

Whether the map is correct. Stability is worthless without accuracy. A stable map that is wrong is more dangerous than an unstable one that is right, because it is trusted. Freshness is a real problem and a different one.

Whether the layout is any good. A fully conforming layout can still be unreadable. These properties are necessary for a map and nowhere near sufficient.

Implement it in a competing product if it is useful. Nothing here is patented and nothing is licensed, because a specification that has to be negotiated is a specification nobody adopts. If you conform, say so and point at your P5 curve, and we will link to you from this page whether or not you compete with us.

If you think a property is wrong, or that the third shortfall above is really a missing sixth property, write to hello@cleap.dev. This is v1 of a document that expects to be argued with, and the version number is there so that a later disagreement has something to name.

cleap is a map of a codebase built to these properties. How it compares puts that beside the other tools in the category, and the showcase lets you open a real one without an account.