We need a WebAssembly object linker that:
The implementation is complete and every verification path passes. Files written to ~/wasm_reloc_linker.py and ~/solution.md. Here is the solution document:
wasm-relocation-cycle-dedup: a deterministic, diagnostic-first Wasm object linkerWe need a WebAssembly object linker that:
A naive linker fails in four distinct, order-dependent ways. Each is a separate root cause and must be fixed independently.
The common implementation iterates modules and inserts the first definition it sees into a symbol table. Reordering the inputs changes which definition wins. Likewise, weak symbols are often resolved by "first weak definition encountered", which is not a stable rule.
Root cause: the symbol table is a side effect of iteration order. The fix is to make resolution a pure function of the set of definitions, with an explicit, total ordering used only to break genuine ties.
A loop that raises on the first duplicate strong symbol hides the remaining collisions and makes the error depend on module order.
Root cause: conflict detection and failure are interleaved. The fix is to partition the whole input first, collect all competing definitions per name, and only then decide to fail. The witness for a name is the full set of strong definitions, sorted canonically.
Aliases are frequently treated as ordinary symbols. That breaks for transitive aliases (a -> b -> c) and alias cycles (a -> b -> a), which must be detected and must not recurse forever.
Root cause: alias resolution is not separated from symbol resolution and has no cycle guard. The fix is a dedicated _resolve_alias_chain that walks an explicit pos map and returns a canonical rotation of a cycle when one is found, so the same cycle is discovered identically no matter where the walk started.
If relocations are applied while symbol lookup is still changing, addends get folded onto unstable addresses. If the first unresolved relocation raises, the remaining references are never reported.
Root cause: relocation is fused with resolution. The fix is a strict phase order — resolve the complete symbol table, then apply relocations — and collect every unresolved reference into a single witness list.
A DFS that raises on the first back edge reports whichever cycle the DFS happened to enter first, which depends on node and neighbor ordering. A graph may contain several cycles of different lengths, and the user needs the minimal one.
Root cause: the reported cycle is an artifact of DFS entry order. The fix is an explicit shortest-cycle search with a canonical tie-break: for each candidate start, explore only nodes >= start (so start is the cycle minimum and every cycle is generated exactly once in canonical rotation), run a BFS to find the shortest return path, and keep the (length, path) minimum.
Every ordered structure (module layout, symbol iteration, weak-winner choice, relocation output, topological order, witness lists) must be produced from a canonical key, and never from caller-provided ordering. The implementation below sorts modules by name, symbols by (module, offset, size), relocations by (module, section, offset, kind, symbol, addend), and Kahn's algorithm uses a sorted ready-set.
link()1. canonicalize object order (sort by module name)
2. detect duplicate module names
3. assign module bases deterministically
4. merge alias tables; find contradictory aliases and alias cycles
5. resolve global symbols (strong wins, else canonical weak winner);
collect ALL strong/strong conflicts
6. apply relocations against the frozen symbol table; collect ALL unresolved refs
7. build the init-dependency graph; find the minimal cycle
8. raise one LinkError carrying every diagnostic category, or return LinkResult
The single LinkError exposes .diagnostics (all categories) while .kind and .witness point at the highest-priority category, so callers can either consume the minimal actionable witness or the complete picture.
wasm_reloc_linker.py)"""Deterministic WebAssembly object linker (reference implementation).
The module models the parts of the wasm object-link pipeline that are easy to
get wrong:
* cross-module symbol resolution, including transitive aliases;
* weak/strong binding resolution with a deterministic winner;
* relocation application with addends;
* initializer dependency cycle detection;
* order-independent, deterministic diagnostics.
Everything is deliberately expressed with plain Python dataclasses so that the
linker can be exercised without a full ``.o`` binary parser. A thin adapter
(steps 1-3 below) can feed it from the wasm "linking" / "reloc.*" custom
sections:
1. read ``linking`` section -> symbols / segment info / init funcs
2. read ``reloc.CODE`` / ``reloc.DATA`` -> relocations (type, offset, index,
addend)
3. build ``ObjectFile`` objects and call :func:`link`
"""
from __future__ import annotations
from collections import deque
from dataclasses import dataclass, field
from enum import Enum
from typing import Dict, Iterable, List, Mapping, Optional, Sequence, Tuple
# ---------------------------------------------------------------------------
# Input model
# ---------------------------------------------------------------------------
class Binding(str, Enum):
"""Linkage of a symbol definition."""
STRONG = "strong" # normal external definition
WEAK = "weak" # overridable definition
LOCAL = "local" # module-private, never participates in global lookup
@dataclass(frozen=True)
class SymbolDef:
"""A (possibly weak) symbol definition contributed by one object."""
name: str
module: str
binding: Binding = Binding.STRONG
offset: int = 0
size: int = 0
@dataclass(frozen=True)
class Relocation:
"""A relocation record with an addend.
``symbol`` is the symbol name referenced by the record. ``section`` and
``offset`` identify where the relocated value is stored. ``kind`` is a
relocation type tag; ``ABS`` (a plain address) is used by the examples but
any tag is carried through the result unchanged.
"""
module: str
section: str
offset: int
symbol: str
addend: int = 0
kind: str = "ABS"
@dataclass
class ObjectFile:
"""A relocatable wasm object."""
name: str
size: int = 0
symbols: List[SymbolDef] = field(default_factory=list)
# alias name -> canonical name (may be another alias)
aliases: Mapping[str, str] = field(default_factory=dict)
relocations: List[Relocation] = field(default_factory=list)
# global init function names, in declaration order
init: List[str] = field(default_factory=list)
# init function -> functions that must run before it
init_deps: Mapping[str, Sequence[str]] = field(default_factory=dict)
# ---------------------------------------------------------------------------
# Output model
# ---------------------------------------------------------------------------
@dataclass(frozen=True)
class ResolvedRelocation:
module: str
section: str
offset: int
kind: str
symbol: str
addend: int
value: int
def canonical_key(self) -> Tuple[str, str, int, str]:
return (self.module, self.section, self.offset, self.kind)
@dataclass
class LinkResult:
module_bases: Dict[str, int]
resolved_symbols: Dict[str, int]
relocations: List[ResolvedRelocation]
initializers: List[str]
warnings: List[str] = field(default_factory=list)
class LinkError(Exception):
"""Aggregated, deterministic link failure.
``kind`` is ``"conflict"``, ``"alias"``, ``"unresolved"`` or ``"cycle"``.
``witness`` is a *minimal* list of actionable records: for a conflict it is
the competing strong definitions, for an unresolved relocation it is the
relocation itself, for a cycle it is the canonical cycle path.
"""
def __init__(
self,
kind: str,
message: str,
witness: List[object],
diagnostics: Optional[Dict[str, List[object]]] = None,
):
super().__init__(message)
self.kind = kind
self.witness = witness
# Every independent category found in the same pass, keyed by kind.
# When only one category exists this is ``{kind: witness}`` so callers
# that only inspect ``.witness`` keep working.
self.diagnostics: Dict[str, List[object]] = (
diagnostics if diagnostics is not None else {kind: witness}
)
# ---------------------------------------------------------------------------
# Helpers
# ---------------------------------------------------------------------------
def _canonical_modules(objects: Iterable[ObjectFile]) -> List[ObjectFile]:
"""Return objects in a canonical order independent of caller ordering."""
return sorted(objects, key=lambda o: o.name)
def _assign_bases(objs: Sequence[ObjectFile]) -> Dict[str, int]:
bases: Dict[str, int] = {}
cursor = 0
for obj in objs:
bases[obj.name] = cursor
cursor += obj.size
return bases
def _build_alias_map(
objs: Sequence[ObjectFile],
) -> Tuple[Dict[str, str], List[Tuple[str, List[Tuple[str, str]]]]]:
"""Merge per-object alias tables and detect contradictory aliases.
Returns ``(alias_map, conflicts)`` where each conflict is
``(alias_name, [(module, target), ...])`` sorted canonically. Aliases are
global: a reference to ``a`` resolves through the merged table.
"""
first: Dict[str, str] = {}
owners: Dict[str, List[Tuple[str, str]]] = {}
for obj in objs:
for alias, target in sorted(obj.aliases.items()):
owners.setdefault(alias, []).append((obj.name, target))
first.setdefault(alias, target)
conflicts: List[Tuple[str, List[Tuple[str, str]]]] = []
for alias in sorted(owners):
pairs = sorted(set(owners[alias]))
if len({t for _, t in pairs}) > 1:
conflicts.append((alias, pairs))
return first, conflicts
def _resolve_alias_chain(
name: str, alias_map: Mapping[str, str]
) -> Tuple[Optional[str], Optional[List[str]]]:
"""Follow ``name`` through aliases.
Returns ``(canonical_name, None)`` on success or ``(None, cycle)`` when the
alias chain loops. The returned cycle is rotated to start at its smallest
member so witnesses are canonical.
"""
seen: List[str] = []
pos: Dict[str, int] = {}
cur = name
while cur in alias_map:
if cur in pos:
cycle = seen[pos[cur]:]
return None, _canonical_cycle(cycle)
pos[cur] = len(seen)
seen.append(cur)
cur = alias_map[cur]
return cur, None
def _canonical_cycle(cycle: Sequence[str]) -> List[str]:
"""Rotate ``cycle`` so it starts at its lexicographically smallest node."""
if not cycle:
return []
i = min(range(len(cycle)), key=lambda k: cycle[k])
return list(cycle[i:]) + list(cycle[:i])
# ---------------------------------------------------------------------------
# Symbol resolution
# ---------------------------------------------------------------------------
def _resolve_symbols(
objs: Sequence[ObjectFile],
bases: Mapping[str, int],
alias_map: Mapping[str, str],
) -> Tuple[Dict[str, int], List[Tuple[str, List[SymbolDef]]]]:
"""Resolve global symbols, returning addresses and strong conflicts.
A name may resolve to at most one strong definition. When more than one
exists the *entire* competing set is returned as a conflict witness. Weak
definitions lose to a strong one; without a strong one the winner is chosen
by ``(module, offset)`` which is stable under input reordering.
"""
defs: Dict[str, List[SymbolDef]] = {}
for obj in objs:
for sym in obj.symbols:
if sym.binding == Binding.LOCAL:
continue
defs.setdefault(sym.name, []).append(sym)
resolved: Dict[str, int] = {}
conflicts: List[Tuple[str, List[SymbolDef]]] = []
for name in sorted(defs):
group = sorted(defs[name], key=lambda s: (s.module, s.offset, s.size))
strong = [s for s in group if s.binding == Binding.STRONG]
weak = [s for s in group if s.binding == Binding.WEAK]
if len(strong) > 1:
conflicts.append((name, strong))
continue
winner = strong[0] if strong else weak[0]
resolved[name] = bases[winner.module] + winner.offset
return resolved, conflicts
def _local_symbols(objs: Sequence[ObjectFile], bases: Mapping[str, int]) -> Dict[Tuple[str, str], int]:
"""Map ``(module, name) -> address`` for module-private symbols."""
table: Dict[Tuple[str, str], int] = {}
for obj in objs:
for sym in obj.symbols:
if sym.binding == Binding.LOCAL:
table[(obj.name, sym.name)] = bases[obj.name] + sym.offset
return table
# ---------------------------------------------------------------------------
# Relocations
# ---------------------------------------------------------------------------
def _apply_relocations(
objs: Sequence[ObjectFile],
bases: Mapping[str, int],
resolved: Mapping[str, int],
alias_map: Mapping[str, str],
) -> Tuple[List[ResolvedRelocation], List[Tuple[Relocation, str]]]:
"""Apply every relocation and collect *all* unresolved references."""
local = _local_symbols(objs, bases)
out: List[ResolvedRelocation] = []
unresolved: List[Tuple[Relocation, str]] = []
for obj in objs:
relocs = sorted(
obj.relocations,
key=lambda r: (r.module, r.section, r.offset, r.kind, r.symbol, r.addend),
)
for rel in relocs:
# 1. module-local symbols win inside their own object.
if (obj.name, rel.symbol) in local:
value = local[(obj.name, rel.symbol)] + rel.addend
else:
target, cycle = _resolve_alias_chain(rel.symbol, alias_map)
if cycle is not None:
unresolved.append((rel, "alias cycle: " + " -> ".join(cycle)))
continue
assert target is not None
if target in resolved:
value = resolved[target] + rel.addend
else:
unresolved.append((rel, f"undefined symbol {target!r}"))
continue
out.append(
ResolvedRelocation(
module=rel.module,
section=rel.section,
offset=rel.offset,
kind=rel.kind,
symbol=rel.symbol,
addend=rel.addend,
value=value,
)
)
out.sort(key=lambda r: r.canonical_key())
return out, unresolved
# ---------------------------------------------------------------------------
# Initializer cycle detection
# ---------------------------------------------------------------------------
def _build_init_graph(objs: Sequence[ObjectFile]) -> Dict[str, List[str]]:
graph: Dict[str, List[str]] = {}
for obj in objs:
for fn in obj.init:
graph.setdefault(fn, [])
for fn, deps in obj.init_deps.items():
graph.setdefault(fn, [])
for dep in deps:
graph[fn].append(dep)
# deterministic, duplicate-free adjacency
return {n: sorted(set(nbrs)) for n, nbrs in graph.items()}
def minimal_cycle(graph: Mapping[str, Sequence[str]]) -> Optional[List[str]]:
"""Return the shortest directed cycle, tie-broken lexicographically.
For every candidate start node, only nodes ``>= start`` are traversed, which
guarantees ``start`` is the cycle minimum, so each cycle is discovered once
in canonical rotation. BFS then yields the shortest cycle through that
start. The global best is ``(length, path)`` minimal.
Complexity: O(V * (V + E)) time, O(V) extra space.
"""
adj = {n: sorted(set(graph.get(n, ()))) for n in sorted(graph)}
best: Optional[Tuple[int, Tuple[str, ...]]] = None
for start in sorted(adj):
dist = {start: 0}
parent: Dict[str, Optional[str]] = {start: None}
q: deque[str] = deque([start])
found: Optional[List[str]] = None
while q and found is None:
u = q.popleft()
for v in adj.get(u, ()):
if v < start:
# would introduce a smaller node -> not the canonical min
continue
if v == start:
path: List[str] = []
cur: Optional[str] = u
while cur is not None:
path.append(cur)
cur = parent[cur]
path.reverse()
found = path
break
if v not in dist:
dist[v] = dist[u] + 1
parent[v] = u
q.append(v)
if found is not None:
cand = (len(found), tuple(found))
if best is None or cand < best:
best = cand
return list(best[1]) if best else None
def _topological_order(graph: Mapping[str, Sequence[str]]) -> Optional[List[str]]:
"""Kahn topological order of prerequisites first, deterministic by name.
``graph[fn]`` is the set of functions ``fn`` depends on, so each dependency
must appear in the output before ``fn``. Ties are broken by name to keep
the result stable under input reordering.
"""
indeg = {n: len(set(graph.get(n, ()))) for n in graph}
dependents: Dict[str, List[str]] = {n: [] for n in graph}
for n in graph:
for d in set(graph.get(n, ())):
dependents.setdefault(d, []).append(n)
ready = sorted(n for n, d in indeg.items() if d == 0)
order: List[str] = []
while ready:
n = ready.pop(0)
order.append(n)
for d in sorted(dependents.get(n, ())):
indeg[d] -= 1
if indeg[d] == 0:
# insert keeping the ready list sorted (deterministic)
lo, hi = 0, len(ready)
while lo < hi:
mid = (lo + hi) // 2
if ready[mid] < d:
lo = mid + 1
else:
hi = mid
ready.insert(lo, d)
if len(order) != len(graph):
return None
return order
# ---------------------------------------------------------------------------
# Public entry point
# ---------------------------------------------------------------------------
def link(objects: Iterable[ObjectFile]) -> LinkResult:
"""Link a set of objects deterministically, or raise :class:`LinkError`.
Every independent diagnostic category is collected in a single pass before
anything is raised, so a failure never hides the other problems and the
chosen witness is never an artifact of traversal order.
"""
objs = _canonical_modules(objects)
# --- name-shape diagnostics -------------------------------------------
counts: Dict[str, int] = {}
for obj in objs:
counts[obj.name] = counts.get(obj.name, 0) + 1
dup_modules = sorted(m for m, c in counts.items() if c > 1)
if dup_modules:
rec = [("duplicate-module", m) for m in dup_modules]
raise LinkError(
"conflict",
f"duplicate module names: {dup_modules}",
rec,
{"conflict": rec},
)
bases = _assign_bases(objs)
alias_map, alias_conflicts = _build_alias_map(objs)
# --- alias diagnostics -------------------------------------------------
alias_cycles: List[Tuple[str, List[str]]] = []
for alias in sorted(set(alias_map) | {t for t in alias_map.values()}):
_target, cycle = _resolve_alias_chain(alias, alias_map)
if cycle is not None:
alias_cycles.append((alias, cycle))
seen_cycles = set()
unique_alias_cycles: List[Tuple[str, List[str]]] = []
for alias, cyc in alias_cycles:
key = tuple(cyc)
if key not in seen_cycles:
seen_cycles.add(key)
unique_alias_cycles.append((alias, cyc))
unique_alias_cycles.sort(key=lambda x: (tuple(x[1]), x[0]))
alias_witness: List[object] = []
alias_witness.extend(
(a, [f"{m}:{t}" for m, t in pairs]) for a, pairs in sorted(alias_conflicts)
)
alias_witness.extend(cyc for _alias, cyc in unique_alias_cycles)
# --- symbol / relocation / init diagnostics ---------------------------
resolved, conflicts = _resolve_symbols(objs, bases, alias_map)
relocations, unresolved = _apply_relocations(objs, bases, resolved, alias_map)
graph = _build_init_graph(objs)
cycle = minimal_cycle(graph)
diags: Dict[str, List[object]] = {}
if alias_witness:
diags["alias"] = alias_witness
if conflicts:
diags["conflict"] = [
(name, sorted(f"{s.module}@{s.offset}" for s in strong))
for name, strong in sorted(conflicts)
]
if unresolved:
diags["unresolved"] = [
(r.module, r.section, r.offset, r.symbol, r.addend, reason)
for r, reason in sorted(
unresolved,
key=lambda x: (x[0].module, x[0].section, x[0].offset, x[0].kind),
)
]
if cycle is not None:
diags["cycle"] = [cycle]
if diags:
# Stable priority: alias corruption invalidates name lookup, so it is
# reported first; all categories remain available via .diagnostics.
priority = ["alias", "conflict", "unresolved", "cycle"]
kind = next(k for k in priority if k in diags)
summary = ", ".join(f"{k}={len(v)}" for k, v in diags.items())
raise LinkError(
kind,
f"link failed ({summary})",
diags[kind],
diags,
)
order = _topological_order(graph) or []
return LinkResult(
module_bases=bases,
resolved_symbols=dict(sorted(resolved.items())),
relocations=relocations,
initializers=order,
warnings=[],
)
# ---------------------------------------------------------------------------
# Self-tests
# ---------------------------------------------------------------------------
def _self_test() -> None:
S, W, L = Binding.STRONG, Binding.WEAK, Binding.LOCAL
def obj(name, size, syms, aliases=None, relocs=None, init=None, deps=None):
return ObjectFile(
name=name,
size=size,
symbols=[SymbolDef(*s) for s in syms],
aliases=aliases or {},
relocations=[Relocation(*r) for r in (relocs or [])],
init=init or [],
init_deps=deps or {},
)
# 1. basic resolution + addend, order independent
a = obj("a", 16, [("foo", "a", S, 4)])
b = obj("b", 16, [], relocs=[("b", ".text", 0, "foo", 8)])
r1 = link([a, b])
r2 = link([b, a])
assert r1.resolved_symbols == {"foo": 4}
assert r1.relocations[0].value == 12
assert r1 == r2
# 2. strong beats weak regardless of input order
s = obj("s", 8, [("g", "s", S, 0)])
w = obj("w", 8, [("g", "w", W, 0)])
for order in ([s, w], [w, s]):
assert link(order).resolved_symbols["g"] == 0 # module s < w
# 3. two strong defs -> conflict with both witnesses
c1 = obj("c1", 8, [("g", "c1", S, 0)])
c2 = obj("c2", 8, [("g", "c2", S, 0)])
try:
link([c1, c2])
raise AssertionError("expected conflict")
except LinkError as e:
assert e.kind == "conflict"
assert sorted(e.witness[0][1]) == ["c1@0", "c2@0"]
# 4. aliases, transitive, resolve in relocations
al = obj("al", 8, [("real", "al", S, 0)], aliases={"x": "y", "y": "real"})
uses = obj("u", 8, [], relocs=[("u", ".text", 0, "x", 0)])
assert link([uses, al]).relocations[0].value == 0
# 5. alias cycle is reported as an alias error
ac = obj("ac", 8, [], aliases={"p": "q", "q": "p"})
try:
link([ac])
raise AssertionError("expected alias cycle")
except LinkError as e:
assert e.kind == "alias"
assert e.witness[0] == ["p", "q"]
# 6. unresolved relocation witness
ur = obj("ur", 8, [], relocs=[("ur", ".text", 0, "nope", 4)])
try:
link([ur])
raise AssertionError("expected unresolved")
except LinkError as e:
assert e.kind == "unresolved"
assert e.witness[0][3] == "nope"
# 7a. shortest cycle wins over a longer one
m = obj("m", 8, [], init=["A", "B", "C"], deps={"A": ["B"], "B": ["C"], "C": ["A"]})
try:
link([m])
raise AssertionError("expected cycle")
except LinkError as e:
assert e.kind == "cycle"
assert e.witness[0] == ["A", "B", "C"]
# 7b. self-loop is the minimal cycle
ms = obj("ms", 8, [], init=["A", "B", "D"], deps={"A": ["B"], "B": ["A"], "D": ["D"]})
try:
link([ms])
raise AssertionError("expected cycle")
except LinkError as e:
assert e.witness[0] == ["D"]
# 7c. equal-length cycles tie-break lexicographically
mt = obj(
"mt",
8,
[],
init=["A", "B", "C", "D"],
deps={"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"]},
)
try:
link([mt])
raise AssertionError("expected cycle")
except LinkError as e:
assert e.witness[0] == ["A", "B"], e.witness[0]
# 8. acyclic Kahn order deterministic
m2 = obj("m2", 8, [], init=["A", "B"], deps={"B": ["A"]})
res = link([m2])
assert res.initializers == ["A", "B"]
# 9. all conflicts aggregated, not first-only
multi = [
obj("m1", 8, [("g", "m1", S, 0), ("h", "m1", S, 0)]),
obj("m2", 8, [("g", "m2", S, 0), ("h", "m2", S, 0)]),
]
try:
link(multi)
raise AssertionError("expected conflict")
except LinkError as e:
assert [w[0] for w in e.witness] == ["g", "h"]
print("all self-tests passed")
if __name__ == "__main__":
_self_test()
The model is intentionally decoupled from the binary parser. To use it on real .o files, adapt the wasm linking / reloc.* custom sections:
linking section into SymbolDefs (flags give Binding, the WEAK flag maps to Binding.WEAK, undefined symbols carry no address);reloc.CODE / reloc.DATA records: (type, offset, symbol_index, addend) -> Relocation(module, section, offset, symbol, addend, kind);ELEM / init-func metadata into ObjectFile.init and ObjectFile.init_deps;link(objects).The module is self-testing. Run:
python3 wasm_reloc_linker.py
Expected output:
all self-tests passed
The self-tests cover: basic resolution + addend, strong/weak precedence under both input orders, strong/strong conflict witness with both modules, transitive alias resolution, alias-cycle detection, unresolved-relocation witness, shortest self-loop cycle, equal-length lexicographic tie-break, and deterministic acyclic Kahn ordering.
python3 - <<'PY'
import itertools, random
from wasm_reloc_linker import *
def O(n,sz,syms,aliases=None,relocs=None):
return ObjectFile(n,sz,[SymbolDef(*s) for s in syms],aliases or {},
[Relocation(*r) for r in (relocs or [])])
mods=[
O("alpha",16,[("main","alpha",Binding.STRONG,0),("helper","alpha",Binding.WEAK,4)],
aliases={"h":"helper"}, relocs=[("alpha",".text",8,"helper",2)]),
O("beta",16,[("helper","beta",Binding.STRONG,8),("tbl","beta",Binding.STRONG,12)],
relocs=[("beta",".data",0,"main",1)]),
O("gamma",8,[("tbl","gamma",Binding.WEAK,0)],relocs=[("gamma",".text",0,"h",8)]),
]
ref = link(mods)
for perm in itertools.permutations(mods):
assert link(perm) == ref
for _ in range(300):
m=[ObjectFile(o.name,o.size,list(reversed(o.symbols)),o.aliases,
list(reversed(o.relocations)),list(reversed(o.init)),o.init_deps) for o in mods]
random.shuffle(m)
assert link(m) == ref
print("determinism fuzz OK")
PY
Expected: determinism fuzz OK.
python3 - <<'PY'
from wasm_reloc_linker import *
S=Binding.STRONG
def O(n,syms,aliases=None,relocs=None,init=None,deps=None):
return ObjectFile(n,8,[SymbolDef(*s) for s in syms],aliases or {},
[Relocation(*r) for r in (relocs or [])],init or [],deps or {})
objs=[
O("a",[("g","a",S,0)],aliases={"z":"z2","z2":"z"},
relocs=[("a",".t",0,"missing",0)],init=["A","B"],deps={"A":["B"],"B":["A"]}),
O("b",[("g","b",S,0)]),
]
try:
link(objs)
except LinkError as e:
assert set(e.diagnostics) == {"alias","conflict","unresolved","cycle"}
print("aggregated:", e)
print("aggregation OK")
PY
Expected:
aggregated: link failed (alias=1, conflict=1, unresolved=1, cycle=1)
aggregation OK
link() returns equal LinkResult values for every permutation of the input objects and for reversed symbol/relocation lists inside each object, because layout, resolution, relocation output, initializer order and all witnesses are derived from sorted canonical keys.
| Failure mode | Root cause | Fix |
|---|---|---|
| Wrong symbol wins after reorder | resolution coupled to iteration | resolve from the whole definition set; explicit tie-break |
| Only first conflict reported | detection fused with failure | partition all names, collect all strong/strong sets, raise once |
| Alias loops / chain misses | no dedicated alias pass | _resolve_alias_chain + canonical cycle rotation |
| Addends on unstable addresses | relocation fused with resolution | freeze symbol table, then apply relocations |
| Traversal-dependent cycle | DFS back-edge | shortest-cycle BFS with >= start restriction and lexicographic tie-break |
| Non-deterministic output | caller ordering leaked | canonical sort keys everywhere |
Verified: python3 wasm_reloc_linker.py → all self-tests passed; determinism fuzz → determinism fuzz OK; aggregated diagnostics → aggregation OK; embedded code byte-matches ~/wasm_reloc_linker.py.
# Evidence - Problem class: wasm-relocation-cycle-dedup - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-04T04:11:37.288Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement a WebAssembly object linker that resolves symbol aliases and weak/strong definitions across modules, applies relocations including addends, and detects cyclic initializer dependencies. It must preserve deterministic output under arbitrary input ordering and report minimal actionable conflict or cycle witnesses rather than failing at the first traversal-dependent error.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "wasm-relocation-cycle-dedup", "provider": "openrouter", "solved_at": "2026-10-04T04:11:37.289Z", "version": "3.11"}