FA-41026 / Heap invariants / Open access
Heap meld sums disjoint sizes but does not double-count alias wrappers · case 01
The bounded meld ownership certificate reports an incorrect destination size.
ROOT CAUSE
Heap meld sums disjoint sizes but does not double-count alias wrappers.
VERIFIED REPAIR
Derive destination size using d["dest_size"] if rs==rd else d["dest_size"]+d["source_size"] under the stated bounded certificate contract.
Unsuccessful approach: The local patch uses d["dest_size"] and still violates the stated relation.
Case contract
A destructive heap meld uses owner union representatives. Parent mapping owner->owner is acyclic and includes every referenced owner. Merge source representative into destination representative; source wrapper becomes empty but live handles from either representative remain resolvable through the union. Report representatives before meld, parent mapping after meld, source size, destination size, accepted handle owners, and whether self-component meld is a no-op.
Why this case matters
This isolates an internal heap representation or priority-structure invariant using deterministic finite records.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
parents=d['parents']; dest=d['dest']; src=d['src']
def find(x):
while parents[x]!=x: x=parents[x]
return x
rd=find(dest); rs=find(src); out=dict(parents)
if rs!=rd: out[rs]=rd
return {'representatives': [rd,rs],
'union': out,
'source_size': d["source_size"] if rs==rd else 0,
'destination_size': d["dest_size"]+d["source_size"],
'accepted': [x for x in d["handles"] if find(x) in (rd,rs)],
'noop': rd==rs}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 3, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 3, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 4, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 4, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 6, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 6, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 7, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 7, 'accepted': ['a', 'b'], 'noop': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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 |
|---|---|---|---|
| regression certificate 1 | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | Passed |
| regression certificate 2 | {'accepted': ['a'], 'destination_size': 8, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | {'accepted': ['a'], 'destination_size': 4, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | Failed |
| regression certificate 3 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | Passed |
| regression certificate 4 | {'accepted': ['a', 'b'], 'destination_size': 10, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | Failed |
| regression certificate 5 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | Passed |
| regression certificate 6 | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Passed |
| variant-dependent certificate | {'accepted': ['a', 'b'], 'destination_size': 3, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 3, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Passed |
SHA-256 / 4e6f8fd7a8440a37720662309b380a19d3f344b8bc6448b1ce5d49d0d03336d2
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
parents=d['parents']; dest=d['dest']; src=d['src']
def find(x):
while parents[x]!=x: x=parents[x]
return x
rd=find(dest); rs=find(src); out=dict(parents)
if rs!=rd: out[rs]=rd
return {'representatives': [rd,rs],
'union': out,
'source_size': d["source_size"] if rs==rd else 0,
'destination_size': d["dest_size"],
'accepted': [x for x in d["handles"] if find(x) in (rd,rs)],
'noop': rd==rs}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 3, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 3, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 4, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 4, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 6, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 6, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 7, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 7, 'accepted': ['a', 'b'], 'noop': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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 |
|---|---|---|---|
| regression certificate 1 | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | Failed |
| regression certificate 2 | {'accepted': ['a'], 'destination_size': 4, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | {'accepted': ['a'], 'destination_size': 4, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | Passed |
| regression certificate 3 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 3, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | Failed |
| regression certificate 4 | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | Passed |
| regression certificate 5 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 1, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | Failed |
| regression certificate 6 | {'accepted': ['a', 'b'], 'destination_size': 0, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Failed |
| variant-dependent certificate | {'accepted': ['a', 'b'], 'destination_size': 0, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 3, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Failed |
SHA-256 / 5a4f567a484d2d88d999c4d2d8d0deabc84ded48718b51d7e63d61eb018fbff6
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
parents=d['parents']; dest=d['dest']; src=d['src']
def find(x):
while parents[x]!=x: x=parents[x]
return x
rd=find(dest); rs=find(src); out=dict(parents)
if rs!=rd: out[rs]=rd
return {'representatives': [rd,rs],
'union': out,
'source_size': d["source_size"] if rs==rd else 0,
'destination_size': d["dest_size"] if rs==rd else d["dest_size"]+d["source_size"],
'accepted': [x for x in d["handles"] if find(x) in (rd,rs)],
'noop': rd==rs}
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 3, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 3, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 4, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 4, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 6, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 6, 'accepted': ['a', 'b'], 'noop': False})], [({'parents': {'a': 'a', 'b': 'b'}, 'dest': 'a', 'src': 'b', 'dest_size': 2, 'source_size': 3, 'handles': ['a', 'b']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a'}, 'dest': 'a', 'src': 'a', 'dest_size': 4, 'source_size': 4, 'handles': ['a']}, {'representatives': ['a', 'a'], 'union': {'a': 'a'}, 'source_size': 4, 'destination_size': 4, 'accepted': ['a'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'd'}, 'dest': 'c', 'src': 'd', 'dest_size': 3, 'source_size': 2, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'd'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'a', 'c': 'c'}, 'dest': 'a', 'src': 'b', 'dest_size': 5, 'source_size': 5, 'handles': ['a', 'b', 'c']}, {'representatives': ['a', 'a'], 'union': {'a': 'a', 'b': 'a', 'c': 'c'}, 'source_size': 5, 'destination_size': 5, 'accepted': ['a', 'b'], 'noop': True}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'b', 'd': 'c'}, 'dest': 'a', 'src': 'd', 'dest_size': 1, 'source_size': 4, 'handles': ['a', 'b', 'c', 'd']}, {'representatives': ['a', 'b'], 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}, 'source_size': 0, 'destination_size': 5, 'accepted': ['a', 'b', 'c', 'd'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 2, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 2, 'accepted': ['a', 'b'], 'noop': False}), ({'parents': {'a': 'a', 'b': 'b', 'c': 'c'}, 'dest': 'b', 'src': 'a', 'dest_size': 0, 'source_size': 7, 'handles': ['a', 'b', 'c']}, {'representatives': ['b', 'a'], 'union': {'a': 'b', 'b': 'b', 'c': 'c'}, 'source_size': 0, 'destination_size': 7, 'accepted': ['a', 'b'], 'noop': False})]][N-1]
check('regression certificate 1', solve(cases[0][0]), cases[0][1])
check('regression certificate 2', solve(cases[1][0]), cases[1][1])
check('regression certificate 3', solve(cases[2][0]), cases[2][1])
check('regression certificate 4', solve(cases[3][0]), cases[3][1])
check('regression certificate 5', solve(cases[4][0]), cases[4][1])
check('regression certificate 6', solve(cases[5][0]), cases[5][1])
check('variant-dependent certificate', solve(cases[6][0]), cases[6][1])
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 |
|---|---|---|---|
| regression certificate 1 | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a'}} | Passed |
| regression certificate 2 | {'accepted': ['a'], 'destination_size': 4, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | {'accepted': ['a'], 'destination_size': 4, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 4, 'union': {'a': 'a'}} | Passed |
| regression certificate 3 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'd'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'a'}} | Passed |
| regression certificate 4 | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 5, 'noop': True, 'representatives': ['a', 'a'], 'source_size': 5, 'union': {'a': 'a', 'b': 'a', 'c': 'c'}} | Passed |
| regression certificate 5 | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | {'accepted': ['a', 'b', 'c', 'd'], 'destination_size': 5, 'noop': False, 'representatives': ['a', 'b'], 'source_size': 0, 'union': {'a': 'a', 'b': 'a', 'c': 'b', 'd': 'c'}} | Passed |
| regression certificate 6 | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 2, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Passed |
| variant-dependent certificate | {'accepted': ['a', 'b'], 'destination_size': 3, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | {'accepted': ['a', 'b'], 'destination_size': 3, 'noop': False, 'representatives': ['b', 'a'], 'source_size': 0, 'union': {'a': 'b', 'b': 'b', 'c': 'c'}} | Passed |
SHA-256 / 00ff04466186ba174f9669ab46bd4c97fbee4e7ec5ace64be6326bf0f08fb4af
Verification & scope
A stipulated offline diagnostic model; it does not implement a production allocator, concurrency protocol, or complete heap library. 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:43:36.845731+00:00.
Case digest / 3d571a5a6230f15223c31fd9f3b1668c9e2d7b09f320f9c40207851bd3f735b9