FA-43071 / Borrow checking / Open access
Outlives propagation removes required points instead of accumulating them · case 01
Outlives propagation removes required points instead of accumulating them.
ROOT CAUSE
The static analyzer mishandles constraint direction: outlives propagation removes required points instead of accumulating them.
VERIFIED REPAIR
Apply the specified transfer or inference rule at this site: points[a].update(points[b]).
Unsuccessful approach: The partial repair uses points[a].intersection_update(points[b]), which still violates the stipulated analysis contract.
Case contract
Solve finite outlives constraints a:b meaning a contains b. regions is universe, edges named constraints, equalities are bidirectional, demands maps region to points, universal maps region to required external points, forbidden maps region to points forbidden by storage scope. Compute least fixed point. Unknown edge endpoints produce error unknown; own seeds are retained; report sorted point sets and region names violating forbidden points. The static solution includes disconnected regions and propagates through cycles.
Why this case matters
A finite offline static-analysis model of ownership and borrowing; it does not execute the analyzed program.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, edges, equalities, demands, universal, forbidden):
names=set(regions)
if any(a not in names or b not in names for a,b in edges+equalities): return 'unknown'
links=list(edges)
for a,b in equalities: links.extend([(a,b),(b,a)])
points={r:set(demands.get(r,[])) for r in names}
for r in names: points[r].update(universal.get(r,[]))
changed=True
while changed:
changed=False
for a,b in links:
before=set(points[a])
points[b].update(points[a])
if points[a]!=before: changed=True
bad=sorted(r for r in names if points[r]&set(forbidden.get(r,[])))
return [dict((r,sorted(points[r])) for r in sorted(names)),bad]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('empty',solve([],[],[],{},{},{}),[{},[]])
check('disconnected',solve(['a'],[],[],{},{},{}),[{'a':[]},[]])
check('unknown edge',solve(['a'],[('a','z')],[],{},{},{}),'unknown')
check('unknown equality',solve(['a'],[],[('a','z')],{},{},{}),'unknown')
check('seed both',solve(['a'],[],[],{'a':[N,N+1]},{'a':[N+2]},{}),[{'a':[N,N+1,N+2]},[]])
check('equality',solve(['a','b'],[],[('a','b')],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N,N+1]},[]])
check('transitive reversed order',solve(['a','b','c'],[('a','b'),('b','c')],[],{'c':[N]},{},{}),[{'a':[N],'b':[N],'c':[N]},[]])
check('one-way',solve(['a','b'],[('a','b')],[],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N+1]},[]])
check('forbidden partial',solve(['a'],[],[],{'a':[N,N+1]},{},{'a':[N]}),[{'a':[N,N+1]},['a']])
check('empty not forbidden',solve(['a'],[],[],{},{},{'a':[N]}),[{'a':[]},[]])
check('cycle',solve(['a','b'],[('a','b'),('b','a')],[],{'a':[N]},{},{}),[{'a':[N],'b':[N]},[]])
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 |
|---|---|---|---|
| empty | [{}, []] | [{}, []] | Passed |
| disconnected | [{'a': []}, []] | [{'a': []}, []] | Passed |
| unknown edge | unknown | unknown | Passed |
| unknown equality | unknown | unknown | Passed |
| seed both | [{'a': [1, 2, 3]}, []] | [{'a': [1, 2, 3]}, []] | Passed |
| equality | [{'a': [1, 2], 'b': [1, 2]}, []] | [{'a': [1, 2], 'b': [1, 2]}, []] | Passed |
| transitive reversed order | [{'a': [], 'b': [], 'c': [1]}, []] | [{'a': [1], 'b': [1], 'c': [1]}, []] | Failed |
| one-way | [{'a': [1], 'b': [1, 2]}, []] | [{'a': [1, 2], 'b': [2]}, []] | Failed |
| forbidden partial | [{'a': [1, 2]}, ['a']] | [{'a': [1, 2]}, ['a']] | Passed |
| empty not forbidden | [{'a': []}, []] | [{'a': []}, []] | Passed |
| cycle | [{'a': [1], 'b': [1]}, []] | [{'a': [1], 'b': [1]}, []] | Passed |
SHA-256 / 8e7b486b4e55390d81fd0f45351c61ea7d90fefe32802ec463695e7796fc046f
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, edges, equalities, demands, universal, forbidden):
names=set(regions)
if any(a not in names or b not in names for a,b in edges+equalities): return 'unknown'
links=list(edges)
for a,b in equalities: links.extend([(a,b),(b,a)])
points={r:set(demands.get(r,[])) for r in names}
for r in names: points[r].update(universal.get(r,[]))
changed=True
while changed:
changed=False
for a,b in links:
before=set(points[a])
points[a].intersection_update(points[b])
if points[a]!=before: changed=True
bad=sorted(r for r in names if points[r]&set(forbidden.get(r,[])))
return [dict((r,sorted(points[r])) for r in sorted(names)),bad]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('empty',solve([],[],[],{},{},{}),[{},[]])
check('disconnected',solve(['a'],[],[],{},{},{}),[{'a':[]},[]])
check('unknown edge',solve(['a'],[('a','z')],[],{},{},{}),'unknown')
check('unknown equality',solve(['a'],[],[('a','z')],{},{},{}),'unknown')
check('seed both',solve(['a'],[],[],{'a':[N,N+1]},{'a':[N+2]},{}),[{'a':[N,N+1,N+2]},[]])
check('equality',solve(['a','b'],[],[('a','b')],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N,N+1]},[]])
check('transitive reversed order',solve(['a','b','c'],[('a','b'),('b','c')],[],{'c':[N]},{},{}),[{'a':[N],'b':[N],'c':[N]},[]])
check('one-way',solve(['a','b'],[('a','b')],[],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N+1]},[]])
check('forbidden partial',solve(['a'],[],[],{'a':[N,N+1]},{},{'a':[N]}),[{'a':[N,N+1]},['a']])
check('empty not forbidden',solve(['a'],[],[],{},{},{'a':[N]}),[{'a':[]},[]])
check('cycle',solve(['a','b'],[('a','b'),('b','a')],[],{'a':[N]},{},{}),[{'a':[N],'b':[N]},[]])
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 |
|---|---|---|---|
| empty | [{}, []] | [{}, []] | Passed |
| disconnected | [{'a': []}, []] | [{'a': []}, []] | Passed |
| unknown edge | unknown | unknown | Passed |
| unknown equality | unknown | unknown | Passed |
| seed both | [{'a': [1, 2, 3]}, []] | [{'a': [1, 2, 3]}, []] | Passed |
| equality | [{'a': [], 'b': []}, []] | [{'a': [1, 2], 'b': [1, 2]}, []] | Failed |
| transitive reversed order | [{'a': [], 'b': [], 'c': [1]}, []] | [{'a': [1], 'b': [1], 'c': [1]}, []] | Failed |
| one-way | [{'a': [], 'b': [2]}, []] | [{'a': [1, 2], 'b': [2]}, []] | Failed |
| forbidden partial | [{'a': [1, 2]}, ['a']] | [{'a': [1, 2]}, ['a']] | Passed |
| empty not forbidden | [{'a': []}, []] | [{'a': []}, []] | Passed |
| cycle | [{'a': [], 'b': []}, []] | [{'a': [1], 'b': [1]}, []] | Failed |
SHA-256 / 59e996e522e2e4d52d84484cba50292f2a4a986d20a6d3e1b470f34aac4a5048
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(regions, edges, equalities, demands, universal, forbidden):
names=set(regions)
if any(a not in names or b not in names for a,b in edges+equalities): return 'unknown'
links=list(edges)
for a,b in equalities: links.extend([(a,b),(b,a)])
points={r:set(demands.get(r,[])) for r in names}
for r in names: points[r].update(universal.get(r,[]))
changed=True
while changed:
changed=False
for a,b in links:
before=set(points[a])
points[a].update(points[b])
if points[a]!=before: changed=True
bad=sorted(r for r in names if points[r]&set(forbidden.get(r,[])))
return [dict((r,sorted(points[r])) for r in sorted(names)),bad]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('empty',solve([],[],[],{},{},{}),[{},[]])
check('disconnected',solve(['a'],[],[],{},{},{}),[{'a':[]},[]])
check('unknown edge',solve(['a'],[('a','z')],[],{},{},{}),'unknown')
check('unknown equality',solve(['a'],[],[('a','z')],{},{},{}),'unknown')
check('seed both',solve(['a'],[],[],{'a':[N,N+1]},{'a':[N+2]},{}),[{'a':[N,N+1,N+2]},[]])
check('equality',solve(['a','b'],[],[('a','b')],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N,N+1]},[]])
check('transitive reversed order',solve(['a','b','c'],[('a','b'),('b','c')],[],{'c':[N]},{},{}),[{'a':[N],'b':[N],'c':[N]},[]])
check('one-way',solve(['a','b'],[('a','b')],[],{'a':[N],'b':[N+1]},{},{}),[{'a':[N,N+1],'b':[N+1]},[]])
check('forbidden partial',solve(['a'],[],[],{'a':[N,N+1]},{},{'a':[N]}),[{'a':[N,N+1]},['a']])
check('empty not forbidden',solve(['a'],[],[],{},{},{'a':[N]}),[{'a':[]},[]])
check('cycle',solve(['a','b'],[('a','b'),('b','a')],[],{'a':[N]},{},{}),[{'a':[N],'b':[N]},[]])
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 |
|---|---|---|---|
| empty | [{}, []] | [{}, []] | Passed |
| disconnected | [{'a': []}, []] | [{'a': []}, []] | Passed |
| unknown edge | unknown | unknown | Passed |
| unknown equality | unknown | unknown | Passed |
| seed both | [{'a': [1, 2, 3]}, []] | [{'a': [1, 2, 3]}, []] | Passed |
| equality | [{'a': [1, 2], 'b': [1, 2]}, []] | [{'a': [1, 2], 'b': [1, 2]}, []] | Passed |
| transitive reversed order | [{'a': [1], 'b': [1], 'c': [1]}, []] | [{'a': [1], 'b': [1], 'c': [1]}, []] | Passed |
| one-way | [{'a': [1, 2], 'b': [2]}, []] | [{'a': [1, 2], 'b': [2]}, []] | Passed |
| forbidden partial | [{'a': [1, 2]}, ['a']] | [{'a': [1, 2]}, ['a']] | Passed |
| empty not forbidden | [{'a': []}, []] | [{'a': []}, []] | Passed |
| cycle | [{'a': [1], 'b': [1]}, []] | [{'a': [1], 'b': [1]}, []] | Passed |
SHA-256 / 1dbb57e6da8e9f3b108903ab31dd1b60550d3943df2a19ff59d724a4eb839507
Verification & scope
The explicitly stated toy language is the complete scope; this is not a production compiler or a claim about Rust semantics. 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:57.967779+00:00.
Case digest / 1d03d7b3abb2bc75b54ec35c91dc3da6dc4a949138d27d261d96a8139c346498