FA-73926 / Feature flag rollout bucketing / Open access
Prerequisite flag chain: Shared prerequisites are mistaken for cycles · case 01
Two flags that both depend on the same base flag report a prerequisite cycle.
ROOT CAUSE
Cycle detection records every visited flag in one list shared across sibling branches instead of the current path.
VERIFIED REPAIR
Detect cycles only against the flags on the current evaluation path.
Unsuccessful approach: Checking the path without its root lets a cycle through the root run one hop further and blame the wrong flag.
Case contract
flags maps key -> {on, off, serve, prereqs:[[key, required variation]]}. Missing flags yield [None, MISSING, key]; revisiting a flag on the current path yields [None, CYCLE, key] (checked before on/off). An off flag serves [off, OFF, None]. Prerequisites are evaluated in order; MISSING/CYCLE results propagate unchanged; the first prerequisite that is OFF or serves a different variation stops evaluation with [off, PREREQUISITE_FAILED, that prerequisite key]. A prerequisite that itself failed counts as serving its off variation. Otherwise [serve, ON, None].
Why this case matters
Prerequisite chains gate dependent features and must fail closed with an actionable reason.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(flags, name):
visited = []
def ev(key, stack):
f = flags.get(key)
if f is None:
return [None, 'MISSING', key]
if key in visited:
return [None, 'CYCLE', key]
visited.append(key)
if not f['on']:
return [f['off'], 'OFF', None]
for pre, want in f.get('prereqs', []):
got = ev(pre, stack + [key])
if got[1] in ('MISSING', 'CYCLE'):
return got
if got[0] != want or got[1] == 'OFF':
return [f['off'], 'PREREQUISITE_FAILED', pre]
return [f['serve'], 'ON', None]
return ev(name, [])
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 1',
[{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
'd'],
[None, 'MISSING', 'd'])],
[('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 33',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x'], ['a', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['a', 'on'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'off']]},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'x']]}},
'b'],
[None, 'CYCLE', 'b'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 11',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
['on', 'ON', None]),
('prerequisite graph sample 27',
[{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'x'], ['e', 'x'], ['d', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['b', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'e': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['z', 'on']]}},
'd'],
[None, 'CYCLE', 'd'])],
[('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 16',
[{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
'c'],
['x', 'ON', None]),
('prerequisite graph sample 17',
[{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'd'],
[None, 'MISSING', 'd'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 21',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
[None, 'MISSING', 'e']),
('prerequisite graph sample 22',
[{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
['off', 'OFF', None])]]
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 |
|---|---|---|---|
| off prerequisite whose off value equals the requirement fails | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| failure names the unmet prerequisite | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle through an off member reports CYCLE | [None, 'CYCLE', 'a'] | [None, 'CYCLE', 'a'] | Passed |
| missing prerequisite propagates MISSING | [None, 'MISSING', 'zz'] | [None, 'MISSING', 'zz'] | Passed |
| first unmet prerequisite stops evaluation | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle revisits the root | [None, 'CYCLE', 'a'] | [None, 'CYCLE', 'a'] | Passed |
| diamond dependency is not a cycle | [None, 'CYCLE', 'd'] | ['on', 'ON', None] | Failed |
| prerequisite graph sample 1 | [None, 'MISSING', 'd'] | [None, 'MISSING', 'd'] | Passed |
SHA-256 / 382dca4fdca7054faf77412e58c0b163a440903e60d32fb6300e50d7012e096b
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(flags, name):
def ev(key, stack):
f = flags.get(key)
if f is None:
return [None, 'MISSING', key]
if key in stack[1:]:
return [None, 'CYCLE', key]
if not f['on']:
return [f['off'], 'OFF', None]
for pre, want in f.get('prereqs', []):
got = ev(pre, stack + [key])
if got[1] in ('MISSING', 'CYCLE'):
return got
if got[0] != want or got[1] == 'OFF':
return [f['off'], 'PREREQUISITE_FAILED', pre]
return [f['serve'], 'ON', None]
return ev(name, [])
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 1',
[{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
'd'],
[None, 'MISSING', 'd'])],
[('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 33',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x'], ['a', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['a', 'on'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'off']]},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'x']]}},
'b'],
[None, 'CYCLE', 'b'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 11',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
['on', 'ON', None]),
('prerequisite graph sample 27',
[{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'x'], ['e', 'x'], ['d', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['b', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'e': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['z', 'on']]}},
'd'],
[None, 'CYCLE', 'd'])],
[('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 16',
[{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
'c'],
['x', 'ON', None]),
('prerequisite graph sample 17',
[{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'd'],
[None, 'MISSING', 'd'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 21',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
[None, 'MISSING', 'e']),
('prerequisite graph sample 22',
[{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
['off', 'OFF', None])]]
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 |
|---|---|---|---|
| off prerequisite whose off value equals the requirement fails | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| failure names the unmet prerequisite | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle through an off member reports CYCLE | [None, 'CYCLE', 'b'] | [None, 'CYCLE', 'a'] | Failed |
| missing prerequisite propagates MISSING | [None, 'MISSING', 'zz'] | [None, 'MISSING', 'zz'] | Passed |
| first unmet prerequisite stops evaluation | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle revisits the root | [None, 'CYCLE', 'b'] | [None, 'CYCLE', 'a'] | Failed |
| diamond dependency is not a cycle | ['on', 'ON', None] | ['on', 'ON', None] | Passed |
| prerequisite graph sample 1 | [None, 'MISSING', 'd'] | [None, 'MISSING', 'd'] | Passed |
SHA-256 / 958f3a5474eefdaf86a14bd317bb2f8a769d85e723725f385139c03b12259e2a
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(flags, name):
def ev(key, stack):
f = flags.get(key)
if f is None:
return [None, 'MISSING', key]
if key in stack:
return [None, 'CYCLE', key]
if not f['on']:
return [f['off'], 'OFF', None]
for pre, want in f.get('prereqs', []):
got = ev(pre, stack + [key])
if got[1] in ('MISSING', 'CYCLE'):
return got
if got[0] != want or got[1] == 'OFF':
return [f['off'], 'PREREQUISITE_FAILED', pre]
return [f['serve'], 'ON', None]
return ev(name, [])
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('off prerequisite whose off value equals the requirement fails',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'off']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 1',
[{'a': {'on': False, 'off': 'x', 'serve': 'on', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['e', 'on'], ['e', 'off']]},
'c': {'on': False, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['e', 'x'], ['b', 'off']]}},
'd'],
[None, 'MISSING', 'd'])],
[('failure names the unmet prerequisite',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 33',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x'], ['a', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['a', 'on'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['a', 'off']]},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'x']]}},
'b'],
[None, 'CYCLE', 'b'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 11',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on']]},
'b': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['z', 'x'], ['b', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['b', 'x'], ['z', 'x'], ['e', 'on']]},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
['on', 'ON', None]),
('prerequisite graph sample 27',
[{'a': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': [['z', 'x'], ['e', 'x'], ['d', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['b', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'e': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['b', 'on'], ['z', 'on']]}},
'd'],
[None, 'CYCLE', 'd'])],
[('missing prerequisite propagates MISSING',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['zz', 'on']]}}, 'a'],
[None, 'MISSING', 'zz']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 16',
[{'a': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'on'], ['d', 'off']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': []},
'd': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['z', 'off'], ['z', 'on']]},
'e': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['d', 'on']]}},
'c'],
['x', 'ON', None]),
('prerequisite graph sample 17',
[{'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'd'],
[None, 'MISSING', 'd'])],
[('cycle through an off member reports CYCLE',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('first unmet prerequisite stops evaluation',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []},
'c': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('later missing prerequisite is never reached',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['zz', 'on']]},
'b': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['off', 'PREREQUISITE_FAILED', 'b']),
('nested failure serving required off variation passes',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'x']]},
'b': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': [['c', 'on']]},
'c': {'on': False, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('cycle revisits the root',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
[None, 'CYCLE', 'a']),
('diamond dependency is not a cycle',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['d', 'on']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'a'],
['on', 'ON', None]),
('prerequisite graph sample 21',
[{'a': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['b', 'on'], ['b', 'on'], ['d', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'off'], ['a', 'on'], ['d', 'x']]},
'c': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'x']]},
'd': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': []}},
'e'],
[None, 'MISSING', 'e']),
('prerequisite graph sample 22',
[{'a': {'on': False, 'off': 'off', 'serve': 'x', 'prereqs': [['d', 'x'], ['e', 'on'], ['c', 'on']]},
'b': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['c', 'off'], ['a', 'x']]},
'c': {'on': True, 'off': 'x', 'serve': 'x', 'prereqs': [['c', 'on']]},
'd': {'on': True, 'off': 'x', 'serve': 'on', 'prereqs': []},
'e': {'on': True, 'off': 'off', 'serve': 'on', 'prereqs': [['a', 'on']]}},
'a'],
['off', 'OFF', None])]]
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 |
|---|---|---|---|
| off prerequisite whose off value equals the requirement fails | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| failure names the unmet prerequisite | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle through an off member reports CYCLE | [None, 'CYCLE', 'a'] | [None, 'CYCLE', 'a'] | Passed |
| missing prerequisite propagates MISSING | [None, 'MISSING', 'zz'] | [None, 'MISSING', 'zz'] | Passed |
| first unmet prerequisite stops evaluation | ['off', 'PREREQUISITE_FAILED', 'b'] | ['off', 'PREREQUISITE_FAILED', 'b'] | Passed |
| cycle revisits the root | [None, 'CYCLE', 'a'] | [None, 'CYCLE', 'a'] | Passed |
| diamond dependency is not a cycle | ['on', 'ON', None] | ['on', 'ON', None] | Passed |
| prerequisite graph sample 1 | [None, 'MISSING', 'd'] | [None, 'MISSING', 'd'] | Passed |
SHA-256 / e29614c6ebffd711bdd03fd3cae9420cb9f1ea2d2d26147b4405a2b89fc18d44
Verification & scope
A deterministic toy flag-evaluation model with a stipulated contract; it does not reproduce any vendor SDK byte for byte. 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:48:51.983314+00:00.
Case digest / 6600c67f626e7f6f4a066bb889c8530ff36a9f1f97749f722296b3aee20c29ed