FA-88986 / Digital logic simulation / Open access
Critical path follows the first fanin · case 01
The reported critical path passes through a fanin that does not determine the arrival time.
ROOT CAUSE
Path tracing always steps to the first listed fanin.
VERIFIED REPAIR
Step back to the fanin with the latest arrival time, breaking ties by smallest name.
Unsuccessful approach: Choosing the fanin with the largest own delay ignores the arrival accumulated before it.
Case contract
Input [pis, gates, outs, period, setup]: pis maps input -> arrival time; gates are [name, delay, fanins] in topological order. arrival(g) = delay + max fanin arrival. required(g) = min over fanout gates m of (required(m) - delay(m)), plus period - setup if g is an output. Slack = required - arrival over gates. Return [worst slack, critical path, sorted [gate, slack]] where the path ends at the output with least slack (ties by name) and walks back through the fanin with the latest arrival (ties by smallest name) to a primary input.
Why this case matters
Static timing engines back-propagate required times through fanout trees; min/max confusion and delay attribution errors change the reported critical path.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + max(arr[f] for f in fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(fi[0])
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [4, ['a', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Failed |
| diamond tighter period | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Passed |
| long branch through internal output | [1, ['b', 'v', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Failed |
| internal output with fanout | [1, ['b', 'v', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Failed |
| reconvergent unequal branches | [1, ['a', 'p', 'q', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Failed |
| reconvergent with late input | [0, ['a', 'p', 'q', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Failed |
SHA-256 / fc87ce039b6214c6118287651bc9d977f4af018e8ff3a11ece624e873000037a
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + max(arr[f] for f in fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(max(sorted(fi), key=lambda f: g[f][0] if f in g else 0))
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [4, ['a', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Failed |
| diamond tighter period | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Passed |
| long branch through internal output | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Passed |
| internal output with fanout | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Passed |
| reconvergent unequal branches | [1, ['a', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Failed |
| reconvergent with late input | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Passed |
SHA-256 / 25dfa6fba842a13a4fa53e7f953f480015b7f1542182971c321d1a24a2f29948
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + max(arr[f] for f in fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(max(sorted(fi), key=lambda f: arr[f]))
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Passed |
| diamond tighter period | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Passed |
| long branch through internal output | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Passed |
| internal output with fanout | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Passed |
| reconvergent unequal branches | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Passed |
| reconvergent with late input | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Passed |
SHA-256 / 99262df653e2096dc5e016f3a3b7068766347671f64abc0d0faf8a0eb5135479
Verification & scope
A deterministic bounded teaching model of one simulator rule set; the contract is stipulated and is not a claim of conformance to any HDL standard or commercial simulator. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:13.312981+00:00.
Case digest / 197172b4e8449e40d6fe6803430063fce2108e4ff0b3e974d83a51ea4dab43ae