FA-88906 / Digital logic simulation / Open access
Second driver silently overwrites a net · case 01
Two gates driving the same net are accepted and the later one wins.
ROOT CAUSE
Driver uniqueness is never checked while collecting gate outputs.
VERIFIED REPAIR
Reject any gate output already driven by a primary input or an earlier gate.
Unsuccessful approach: Checking only collisions with primary inputs still accepts two gates on one net.
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 False:
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 | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['m', 1], ['o', 0]]} | multiply driven m | Failed |
| gate drives a primary input | {'depth': 1, 'values': [['a', 0], ['b', 1], ['c', 0]]} | multiply driven a | Failed |
| 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 / 0a34f1ac289d2ddbc8248f088c58b0fa66aca5c67c4d7d53055188a2f212a7b3
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 pis:
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 | {'depth': 2, 'values': [['a', 1], ['b', 1], ['c', 0], ['m', 1], ['o', 0]]} | multiply driven m | Failed |
| 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 / 2636e9154e311c8e3a7b5830c8771994347c245619d0ddbee852ea736167681b
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.340651+00:00.
Case digest / e85f5bec1649333fb15d707a29a3772278cb2e00b9a81134fbb8ad442c77107b