FA-88891 / Digital logic simulation / Open access
Gate level taken from the shallowest fanin · case 01
Reconvergent logic reports a smaller depth than its longest path.
ROOT CAUSE
The level of a gate is computed from the minimum input level instead of the maximum.
VERIFIED REPAIR
Set the level to one plus the maximum level of all inputs.
Unsuccessful approach: Using only the first pin still misses a deeper net arriving on a later pin.
Case contract
Input [pis, gates]: pis maps primary input net -> 0/1; gates are [out, op, ins] in any order with ops and/or/xor/nand/not/tie0/tie1. Reject with 'undriven <net>' (first gate in list order, first pin) if a gate reads a net driven by nobody, or 'multiply driven <net>' if a net has two drivers (a gate driving a primary input counts). Otherwise evaluate in dependency waves; return 'loop' if no gate becomes ready. Level: primary inputs 0, gate = 1 + max input level, tie cells 0. Return {'depth': max level, 'values': sorted [net, value]}.
Why this case matters
Levelized compiled-code simulators must order gates by dependency and diagnose structural netlist errors before evaluating.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates = args
seen = set(pis)
for out, op, ins in gates:
if out in seen:
return 'multiply driven ' + out
seen.add(out)
for out, op, ins in gates:
for i in ins:
if i not in seen:
return 'undriven ' + i
level = {p: 0 for p in pis}
val = dict(pis)
pending = list(gates)
while pending:
ready = [g for g in pending if all(i in level for i in g[2])]
if not ready:
return 'loop'
for out, op, ins in ready:
level[out] = 1 + min([level[i] for i in ins], default=-1)
bits = [val[i] for i in ins]
if op == 'and': v = int(all(bits))
elif op == 'or': v = int(any(bits))
elif op == 'xor': v = sum(bits) % 2
elif op == 'nand': v = 1 - int(all(bits))
elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
else: v = 1 - bits[0]
val[out] = v
pending = [g for g in pending if g not in ready]
return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 |
|---|---|---|---|
| reconvergent netlist listed out of order | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | Failed |
| tie cell chain depth | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | Passed |
| undriven input on a later pin | undriven nosuch1 | undriven nosuch1 | Passed |
| real combinational loop | loop | loop | Passed |
| two gates drive one net | multiply driven m | multiply driven m | Passed |
| gate drives a primary input | multiply driven a | multiply driven a | Passed |
| three-input nand | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | Passed |
| unbalanced depth | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | Failed |
SHA-256 / 61514e4b1db53407e32185dea4f99c1dbcdfd347658347a3a391cc7c06880259
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates = args
seen = set(pis)
for out, op, ins in gates:
if out in seen:
return 'multiply driven ' + out
seen.add(out)
for out, op, ins in gates:
for i in ins:
if i not in seen:
return 'undriven ' + i
level = {p: 0 for p in pis}
val = dict(pis)
pending = list(gates)
while pending:
ready = [g for g in pending if all(i in level for i in g[2])]
if not ready:
return 'loop'
for out, op, ins in ready:
level[out] = 1 + max([level[i] for i in ins[:1]], default=-1)
bits = [val[i] for i in ins]
if op == 'and': v = int(all(bits))
elif op == 'or': v = int(any(bits))
elif op == 'xor': v = sum(bits) % 2
elif op == 'nand': v = 1 - int(all(bits))
elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
else: v = 1 - bits[0]
val[out] = v
pending = [g for g in pending if g not in ready]
return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 |
|---|---|---|---|
| reconvergent netlist listed out of order | {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | Passed |
| tie cell chain depth | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | Passed |
| undriven input on a later pin | undriven nosuch1 | undriven nosuch1 | Passed |
| real combinational loop | loop | loop | Passed |
| two gates drive one net | multiply driven m | multiply driven m | Passed |
| gate drives a primary input | multiply driven a | multiply driven a | Passed |
| three-input nand | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | Passed |
| unbalanced depth | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | Failed |
SHA-256 / f678ace356b131161680af6fda0e9d1de29a39c6a7db673fec12181548763d22
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates = args
seen = set(pis)
for out, op, ins in gates:
if out in seen:
return 'multiply driven ' + out
seen.add(out)
for out, op, ins in gates:
for i in ins:
if i not in seen:
return 'undriven ' + i
level = {p: 0 for p in pis}
val = dict(pis)
pending = list(gates)
while pending:
ready = [g for g in pending if all(i in level for i in g[2])]
if not ready:
return 'loop'
for out, op, ins in ready:
level[out] = 1 + max([level[i] for i in ins], default=-1)
bits = [val[i] for i in ins]
if op == 'and': v = int(all(bits))
elif op == 'or': v = int(any(bits))
elif op == 'xor': v = sum(bits) % 2
elif op == 'nand': v = 1 - int(all(bits))
elif op in ('tie0', 'tie1'): v = int(op == 'tie1')
else: v = 1 - bits[0]
val[out] = v
pending = [g for g in pending if g not in ready]
return {'depth': max(level.values()), 'values': [[k, val[k]] for k in sorted(val)]}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch1']]]], 'undriven nosuch1'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 1], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch2']]]], 'undriven nosuch2'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 1], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 1}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 1], ['g1', 0], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 1}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 1], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 1}, [['g1', 'and', ['a', 'nosuch3']]]], 'undriven nosuch3'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 1}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 1}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 1}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 1}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 1], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})], [('reconvergent netlist listed out of order', [{'a': 0, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 0], ['b', 1], ['c', 0], ['g1', 1], ['g2', 1], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 0, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 0], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 0, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch4']]]], 'undriven nosuch4'), ('real combinational loop', [{'a': 0, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 0, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 0, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 0}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 0], ['y', 1]]}), ('unbalanced depth', [{'a': 0, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 0], ['b', 1], ['c', 0], ['d1', 1], ['d2', 0], ['d3', 0], ['d4', 0]]})], [('reconvergent netlist listed out of order', [{'a': 1, 'b': 1, 'c': 0}, [['g3', 'or', ['g1', 'g2', 'c']], ['g1', 'nand', ['a', 'b', 'c']], ['g2', 'not', ['a']], ['g4', 'and', ['g3', 'b']]]], {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]}), ('tie cell chain depth', [{'a': 1, 'b': 1, 'c': 0}, [['t', 'tie1', []], ['u', 'not', ['t']], ['w', 'not', ['u']]]], {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]}), ('undriven input on a later pin', [{'a': 1, 'b': 1, 'c': 0}, [['g1', 'and', ['a', 'nosuch5']]]], 'undriven nosuch5'), ('real combinational loop', [{'a': 1, 'b': 1, 'c': 0}, [['p', 'and', ['a', 'q']], ['q', 'or', ['p', 'b']]]], 'loop'), ('two gates drive one net', [{'a': 1, 'b': 1, 'c': 0}, [['m', 'and', ['a', 'b']], ['m', 'or', ['a', 'c']], ['o', 'not', ['m']]]], 'multiply driven m'), ('gate drives a primary input', [{'a': 1, 'b': 1, 'c': 0}, [['a', 'not', ['b']]]], 'multiply driven a'), ('three-input nand', [{'a': 1, 'b': 1, 'c': 0, 'e': 1}, [['y', 'nand', ['a', 'b', 'c']]]], {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]}), ('unbalanced depth', [{'a': 1, 'b': 1, 'c': 0}, [['d1', 'not', ['a']], ['d2', 'not', ['d1']], ['d3', 'and', ['b', 'd2']], ['d4', 'or', ['c', 'c', 'c', 'c', 'c', 'd3']]]], {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]})]]
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 |
|---|---|---|---|
| reconvergent netlist listed out of order | {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | {'depth': 3, 'values': [['a', 1], ['b', 1], ['c', 0], ['g1', 1], ['g2', 0], ['g3', 1], ['g4', 1]]} | Passed |
| tie cell chain depth | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['t', 1], ['u', 0], ['w', 1]]} | Passed |
| undriven input on a later pin | undriven nosuch1 | undriven nosuch1 | Passed |
| real combinational loop | loop | loop | Passed |
| two gates drive one net | multiply driven m | multiply driven m | Passed |
| gate drives a primary input | multiply driven a | multiply driven a | Passed |
| three-input nand | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | {'depth': 1, 'values': [['a', 1], ['b', 1], ['c', 0], ['e', 1], ['y', 1]]} | Passed |
| unbalanced depth | {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | {'depth': 4, 'values': [['a', 1], ['b', 1], ['c', 0], ['d1', 0], ['d2', 1], ['d3', 1], ['d4', 1]]} | Passed |
SHA-256 / e39ddfbadf83893fcd94868e04b16a716246a1c8c5c9fe4d30f2af6d14cad07a
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:12.335831+00:00.
Case digest / b4397e980c9fae17af11d83ceb7c7df4b1d5de5d09ceab2e632e8468295eb591