The version graph

A ROM’s history is rarely a clean linear sequence of releases: chains fork, side-branches diverge, regional variants pick up patches in a different order. Most analysis questions become tractable only when fantasm knows the topology — “show me what changed between A and B” needs to know how A and B are connected; “propagate this annotation forward” needs a path to walk.

fantasm models this with a directed acyclic graph of versions. Each version is a node; parents lists declare edges from older to newer. The graph lives in fantasm.toml as a sequence of [[versions.entry]] blocks — see fantasm.toml reference for the schema. This page describes what the graph is for.

Why a DAG, not a chain

A linear chain only handles the simple case. Real firmware:

  • Forks — a regional variant or experimental branch leaves the main line and never rejoins. 3.34B-japan descends from 3.34B but doesn’t show up in later mainline versions.

  • Merges — fixes from a side-branch make it back into a later mainline release. 3.40 might inherit from both 3.35K (the main line) and 3.34B-japan (the regional branch).

  • Roots — sometimes the lineage is genuinely unknown (“we found this ROM on a 5.25-inch disk, ancestry TBD”). Roots are a perfectly valid graph state.

A DAG admits all of these without contortion. fantasm rejects cycles at config-load time (VersionGraphCycleError), so the “D” — directed and acyclic — is enforced.

Path-finding and walked direction

VersionGraph.find_path(source, target) returns a list of edges forming the shortest path between two versions in the undirected projection of the DAG. Each edge carries:

  • parent_id — the older end of the underlying directed edge;

  • child_id — the newer end;

  • walked_forward — True when the path traverses the edge in the parent → child direction, False when going against the arrow.

That distinction matters because the per-edge analyses fantasm builds on top (most importantly compose_chained_map) are direction-aware. A confidence map built parent → child can be inverted on the fly when the path traverses backward, so you can ask “annotations from 3.62 applied to 3.34” and fantasm walks 3.62 → 3.60 → 3.40 → 3.35K → 3.35D → 3.34B → 3.34, inverting each forward-built map as needed.

If no path exists between source and target — disconnected components, say, or a still-unplaced root — the path lookup raises NoPathError with both ids attached.

Reloc blocks across edges

NFS-style firmware copies blocks of code from ROM into RAM at runtime, then jumps there. The ROM-resident source addresses shift as the rest of the ROM grows and shrinks across releases, but the runtime dest addresses (and the block lengths) stay stable — they’re properties of the project’s memory map, not of any one version.

fantasm uses that stability to match reloc blocks across an edge. VersionGraph.reloc_pairs_for_edge(edge) walks the parent’s and child’s reloc_blocks lists and pairs them off by (dest, length), returning (src_parent, src_child, dest, length) tuples the address-mapping primitives consume.

When a version’s reloc_blocks dest and length differ across versions (rare but possible — a project might widen or move a workspace page in a release), the block is silently dropped from the edge’s pair list: it can’t contribute to opcode matching anyway. The matched pairs sort by parent source address for determinism.

The lone version’s reloc destinations are also auto-merged into its effective regions: a block at dest=0x0400, length=0x100 makes 0x0400-0x04FF part of that version’s workspace as far as audit, lint, and comment_check are concerned. You don’t have to repeat the range under [memory] regions; just declare the reloc block once.

Composing maps along a path

The high-value primitive is compose_chained_map, exposed both as fantasm.api.version_graph.compose_chained_map and through the fantasm backfill and fantasm annotations diff CLI commands.

For each edge on the path it builds a per-hop confidence map — {parent_addr: (child_addr, block_length)} — by running an opcode-level Longest Common Subsequence between the two ROMs (with the relocated blocks matched separately at their runtime destinations). It then composes the maps end-to-end with min-confidence: the composed block_length is the smallest value seen along the path, because the chain is only as strong as its weakest link.

Practical consequences:

  • Annotations propagate cleanly through unchanged stretches. A 16-instruction routine that’s untouched across five releases will compose to a confidence-16 map across all five hops — a label or comment placed at the parent end maps cleanly to the corresponding child address.

  • Refactored stretches drop in confidence. A routine where release N rearranged six instructions still maps, but its composed block_length drops to whatever the smallest matching run was on the refactored hop. --threshold on backfill lets callers reject low-confidence propagations.

  • Disconnected addresses simply don’t appear. If an address doesn’t compose through every hop on the path, it’s absent from the result — backfill reports those as skipped: no-mapping.

Common shapes

A linear chain

The simplest case. Each version has one parent, the previous release.

[[versions.entry]]
id = "3.34"
reloc_blocks = [...]

[[versions.entry]]
id = "3.34B"
parents = ["3.34"]
reloc_blocks = [...]

[[versions.entry]]
id = "3.35D"
parents = ["3.34B"]
reloc_blocks = [...]

A linear chain handles “I want every comment from 3.34 propagated to 3.35D” perfectly: the path is two hops, both walked forward.

A fork with a branch

Side-branch picks up where the mainline diverged.

[[versions.entry]]
id = "3.34B"
parents = ["3.34"]

[[versions.entry]]
id = "3.34B-japan"
parents = ["3.34B"]
notes = "Japanese keyboard handling diverged at 3.34B"

[[versions.entry]]
id = "3.35D"
parents = ["3.34B"]

3.34B-japan and 3.35D are siblings; a path between them goes 3.34B-japan → 3.34B (backward) → 3.35D (forward). The backward walk inverts the canonical map automatically.

A merged version

Multiple parents.

[[versions.entry]]
id = "3.40"
parents = ["3.35K", "3.34B-japan"]

A merge reflects “this release pulled in fixes from both lines”. Path-finding picks the shortest route through one of the parent edges; the other parent only matters if you specifically ask for the disconnected-from-3.35K side.

A separate root

Versions whose ancestry isn’t yet placed.

[[versions.entry]]
id = "mystery-anfs"
notes = "Found on a 5.25\" disk; ancestry TBD pending opcode analysis"
reloc_blocks = []

The graph happily holds disconnected components. find_path to or from one will fail with NoPathError until the lineage is added — which is the right behaviour: better an explicit error than a silently-empty result.

Discovering the structure

Two CLI commands are the everyday windows into the graph:

  • fantasm addresses map A B shows the opcode-level address mapping between any two versions, computed via compose_chained_map. Useful for “I have an address in 3.34; where does it land in 3.65?”.

  • fantasm backfill A B proposes annotation propagations from A to B by walking the path between them and reading the source driver script. The companion fantasm annotations diff reports source-side annotations whose mapped target is missing, differs, or can’t be reached.

Both commands take --threshold to drop low-confidence propagations and --cpu / --rom-base to override the project defaults from fantasm.toml.

Programmatic surface

For Python callers, fantasm.api.version_graph exposes:

See API reference for the full reference.