FA-43586 / Borrow checking / Open access
One concrete lifetime instantiation is mistaken for a universal proof · case 01
One concrete lifetime instantiation is mistaken for a universal proof.
ROOT CAUSE
The static analyzer mishandles concrete universal: one concrete lifetime instantiation is mistaken for a universal proof.
VERIFIED REPAIR
Apply the specified transfer or inference rule at this site: if d['universal_obligation'] and d['concrete_only']: errors.append('concrete-universal').
Unsuccessful approach: The partial repair uses if d['universal_obligation'] and d['concrete_only'] and not d['checked']: errors.append('concrete-universal'), which still violates the stipulated analysis contract.
Case contract
Check higher-ranked borrow instantiation using de Bruijn binder depths and universes. Bound occurrence index less than binder arity; substitutions shift free lifetimes when crossing binders; fresh universes strictly exceed caller universe; existential solutions cannot mention newer universes; universally quantified input must be checked for every listed placeholder; alpha renaming preserves equal occurrences; distinct bound parameters remain distinct; dropping a binder decrements outside indices; bound lifetimes cannot be selected as static; placeholder obligations cannot be discharged by one concrete lifetime. Input is a fully explicit descriptor of the stated toy IR. Return rule identifiers in declaration order; absent optional obligations use the provided neutral defaults. No rule is an assertion about a production language.
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(d):
errors=[]
if any(i<0 or i>=d['arity'] for i in d['indices']): errors.append('bound-index-range')
if d['after']!=[i+d['crossed'] for i in d['before']]: errors.append('capture-avoiding-shift')
if d['fresh']<=d['caller']: errors.append('fresh-universe')
if any(u>d['existential_universe'] for u in d['solution_universes']): errors.append('universe-leak')
if not set(d['placeholders'])<=set(d['checked']): errors.append('universal-coverage')
if any(d['renaming'][a]!=d['renaming'][b] for a,b in d['equal_pairs']): errors.append('alpha-equality')
if any(d['renaming'][a]==d['renaming'][b] for a,b in d['distinct_pairs']): errors.append('alpha-distinctness')
if d['outside_after']!=[i-1 for i in d['outside_before']]: errors.append('binder-pop')
if bool(set(d['static_choices'])&set(d['bound'])): errors.append('static-skolem')
if False: errors.append('concrete-universal')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'indices': [], 'arity': 0, 'crossed': 0, 'before': [], 'after': [], 'fresh': 1, 'caller': 0, 'solution_universes': [], 'existential_universe': 0, 'placeholders': [], 'checked': [], 'equal_pairs': [], 'renaming': {}, 'distinct_pairs': [], 'outside_before': [], 'outside_after': [], 'static_choices': [], 'bound': [], 'universal_obligation': False, 'concrete_only': False}
check('well formed empty obligations',solve(base),[])
check('bound-index-range regression 0', solve(dict(base, **({'indices':[N],'arity':N}))), ['bound-index-range'])
check('bound-index-range regression 1', solve(dict(base, **({'indices':[N+1],'arity':N+1}))), ['bound-index-range'])
check('capture-avoiding-shift regression 0', solve(dict(base, **({'before':[N],'after':[N],'crossed':1}))), ['capture-avoiding-shift'])
check('capture-avoiding-shift regression 1', solve(dict(base, **({'before':[N,N+1],'after':[N,N+1],'crossed':2}))), ['capture-avoiding-shift'])
check('fresh-universe regression 0', solve(dict(base, **({'fresh':N,'caller':N}))), ['fresh-universe'])
check('fresh-universe regression 1', solve(dict(base, **({'fresh':N+1,'caller':N+1}))), ['fresh-universe'])
check('universe-leak regression 0', solve(dict(base, **({'solution_universes':[N+1],'existential_universe':N}))), ['universe-leak'])
check('universe-leak regression 1', solve(dict(base, **({'solution_universes':[N+2],'existential_universe':N+1}))), ['universe-leak'])
check('universal-coverage regression 0', solve(dict(base, **({'placeholders':['a','b'],'checked':['a']}))), ['universal-coverage'])
check('universal-coverage regression 1', solve(dict(base, **({'placeholders':list(range(N+1)),'checked':[0]}))), ['universal-coverage'])
check('alpha-equality regression 0', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':0,'b':1}}))), ['alpha-equality'])
check('alpha-equality regression 1', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':N,'b':N+1}}))), ['alpha-equality'])
check('alpha-distinctness regression 0', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':0,'b':1,'c':1}}))), ['alpha-distinctness'])
check('alpha-distinctness regression 1', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':N,'b':N+1,'c':N+1}}))), ['alpha-distinctness'])
check('binder-pop regression 0', solve(dict(base, **({'outside_before':[N],'outside_after':[N]}))), ['binder-pop'])
check('binder-pop regression 1', solve(dict(base, **({'outside_before':[N+1],'outside_after':[N+1]}))), ['binder-pop'])
check('static-skolem regression 0', solve(dict(base, **({'static_choices':['a'],'bound':['a']}))), ['static-skolem'])
check('static-skolem regression 1', solve(dict(base, **({'static_choices':[N],'bound':[N]}))), ['static-skolem'])
check('concrete-universal regression 0', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':['a']}))), ['concrete-universal'])
check('concrete-universal regression 1', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':[N]}))), ['concrete-universal'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| bound-index-range regression 0 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| bound-index-range regression 1 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| capture-avoiding-shift regression 0 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| capture-avoiding-shift regression 1 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| fresh-universe regression 0 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| fresh-universe regression 1 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| universe-leak regression 0 | ['universe-leak'] | ['universe-leak'] | Passed |
| universe-leak regression 1 | ['universe-leak'] | ['universe-leak'] | Passed |
| universal-coverage regression 0 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| universal-coverage regression 1 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| alpha-equality regression 0 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-equality regression 1 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-distinctness regression 0 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| alpha-distinctness regression 1 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| binder-pop regression 0 | ['binder-pop'] | ['binder-pop'] | Passed |
| binder-pop regression 1 | ['binder-pop'] | ['binder-pop'] | Passed |
| static-skolem regression 0 | ['static-skolem'] | ['static-skolem'] | Passed |
| static-skolem regression 1 | ['static-skolem'] | ['static-skolem'] | Passed |
| concrete-universal regression 0 | [] | ['concrete-universal'] | Failed |
| concrete-universal regression 1 | [] | ['concrete-universal'] | Failed |
SHA-256 / 1e552428746dec1a59b6194f7bcc7bbee2ca91d2f02e9412539fbc4b5ad9a04c
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
errors=[]
if any(i<0 or i>=d['arity'] for i in d['indices']): errors.append('bound-index-range')
if d['after']!=[i+d['crossed'] for i in d['before']]: errors.append('capture-avoiding-shift')
if d['fresh']<=d['caller']: errors.append('fresh-universe')
if any(u>d['existential_universe'] for u in d['solution_universes']): errors.append('universe-leak')
if not set(d['placeholders'])<=set(d['checked']): errors.append('universal-coverage')
if any(d['renaming'][a]!=d['renaming'][b] for a,b in d['equal_pairs']): errors.append('alpha-equality')
if any(d['renaming'][a]==d['renaming'][b] for a,b in d['distinct_pairs']): errors.append('alpha-distinctness')
if d['outside_after']!=[i-1 for i in d['outside_before']]: errors.append('binder-pop')
if bool(set(d['static_choices'])&set(d['bound'])): errors.append('static-skolem')
if d['universal_obligation'] and d['concrete_only'] and not d['checked']: errors.append('concrete-universal')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'indices': [], 'arity': 0, 'crossed': 0, 'before': [], 'after': [], 'fresh': 1, 'caller': 0, 'solution_universes': [], 'existential_universe': 0, 'placeholders': [], 'checked': [], 'equal_pairs': [], 'renaming': {}, 'distinct_pairs': [], 'outside_before': [], 'outside_after': [], 'static_choices': [], 'bound': [], 'universal_obligation': False, 'concrete_only': False}
check('well formed empty obligations',solve(base),[])
check('bound-index-range regression 0', solve(dict(base, **({'indices':[N],'arity':N}))), ['bound-index-range'])
check('bound-index-range regression 1', solve(dict(base, **({'indices':[N+1],'arity':N+1}))), ['bound-index-range'])
check('capture-avoiding-shift regression 0', solve(dict(base, **({'before':[N],'after':[N],'crossed':1}))), ['capture-avoiding-shift'])
check('capture-avoiding-shift regression 1', solve(dict(base, **({'before':[N,N+1],'after':[N,N+1],'crossed':2}))), ['capture-avoiding-shift'])
check('fresh-universe regression 0', solve(dict(base, **({'fresh':N,'caller':N}))), ['fresh-universe'])
check('fresh-universe regression 1', solve(dict(base, **({'fresh':N+1,'caller':N+1}))), ['fresh-universe'])
check('universe-leak regression 0', solve(dict(base, **({'solution_universes':[N+1],'existential_universe':N}))), ['universe-leak'])
check('universe-leak regression 1', solve(dict(base, **({'solution_universes':[N+2],'existential_universe':N+1}))), ['universe-leak'])
check('universal-coverage regression 0', solve(dict(base, **({'placeholders':['a','b'],'checked':['a']}))), ['universal-coverage'])
check('universal-coverage regression 1', solve(dict(base, **({'placeholders':list(range(N+1)),'checked':[0]}))), ['universal-coverage'])
check('alpha-equality regression 0', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':0,'b':1}}))), ['alpha-equality'])
check('alpha-equality regression 1', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':N,'b':N+1}}))), ['alpha-equality'])
check('alpha-distinctness regression 0', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':0,'b':1,'c':1}}))), ['alpha-distinctness'])
check('alpha-distinctness regression 1', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':N,'b':N+1,'c':N+1}}))), ['alpha-distinctness'])
check('binder-pop regression 0', solve(dict(base, **({'outside_before':[N],'outside_after':[N]}))), ['binder-pop'])
check('binder-pop regression 1', solve(dict(base, **({'outside_before':[N+1],'outside_after':[N+1]}))), ['binder-pop'])
check('static-skolem regression 0', solve(dict(base, **({'static_choices':['a'],'bound':['a']}))), ['static-skolem'])
check('static-skolem regression 1', solve(dict(base, **({'static_choices':[N],'bound':[N]}))), ['static-skolem'])
check('concrete-universal regression 0', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':['a']}))), ['concrete-universal'])
check('concrete-universal regression 1', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':[N]}))), ['concrete-universal'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| bound-index-range regression 0 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| bound-index-range regression 1 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| capture-avoiding-shift regression 0 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| capture-avoiding-shift regression 1 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| fresh-universe regression 0 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| fresh-universe regression 1 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| universe-leak regression 0 | ['universe-leak'] | ['universe-leak'] | Passed |
| universe-leak regression 1 | ['universe-leak'] | ['universe-leak'] | Passed |
| universal-coverage regression 0 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| universal-coverage regression 1 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| alpha-equality regression 0 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-equality regression 1 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-distinctness regression 0 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| alpha-distinctness regression 1 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| binder-pop regression 0 | ['binder-pop'] | ['binder-pop'] | Passed |
| binder-pop regression 1 | ['binder-pop'] | ['binder-pop'] | Passed |
| static-skolem regression 0 | ['static-skolem'] | ['static-skolem'] | Passed |
| static-skolem regression 1 | ['static-skolem'] | ['static-skolem'] | Passed |
| concrete-universal regression 0 | [] | ['concrete-universal'] | Failed |
| concrete-universal regression 1 | [] | ['concrete-universal'] | Failed |
SHA-256 / 344556fce0c7b3c719883e6edac08afed118c328ce0e304b3fbf2fdf101b1b6b
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(d):
errors=[]
if any(i<0 or i>=d['arity'] for i in d['indices']): errors.append('bound-index-range')
if d['after']!=[i+d['crossed'] for i in d['before']]: errors.append('capture-avoiding-shift')
if d['fresh']<=d['caller']: errors.append('fresh-universe')
if any(u>d['existential_universe'] for u in d['solution_universes']): errors.append('universe-leak')
if not set(d['placeholders'])<=set(d['checked']): errors.append('universal-coverage')
if any(d['renaming'][a]!=d['renaming'][b] for a,b in d['equal_pairs']): errors.append('alpha-equality')
if any(d['renaming'][a]==d['renaming'][b] for a,b in d['distinct_pairs']): errors.append('alpha-distinctness')
if d['outside_after']!=[i-1 for i in d['outside_before']]: errors.append('binder-pop')
if bool(set(d['static_choices'])&set(d['bound'])): errors.append('static-skolem')
if d['universal_obligation'] and d['concrete_only']: errors.append('concrete-universal')
return errors
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
base={'indices': [], 'arity': 0, 'crossed': 0, 'before': [], 'after': [], 'fresh': 1, 'caller': 0, 'solution_universes': [], 'existential_universe': 0, 'placeholders': [], 'checked': [], 'equal_pairs': [], 'renaming': {}, 'distinct_pairs': [], 'outside_before': [], 'outside_after': [], 'static_choices': [], 'bound': [], 'universal_obligation': False, 'concrete_only': False}
check('well formed empty obligations',solve(base),[])
check('bound-index-range regression 0', solve(dict(base, **({'indices':[N],'arity':N}))), ['bound-index-range'])
check('bound-index-range regression 1', solve(dict(base, **({'indices':[N+1],'arity':N+1}))), ['bound-index-range'])
check('capture-avoiding-shift regression 0', solve(dict(base, **({'before':[N],'after':[N],'crossed':1}))), ['capture-avoiding-shift'])
check('capture-avoiding-shift regression 1', solve(dict(base, **({'before':[N,N+1],'after':[N,N+1],'crossed':2}))), ['capture-avoiding-shift'])
check('fresh-universe regression 0', solve(dict(base, **({'fresh':N,'caller':N}))), ['fresh-universe'])
check('fresh-universe regression 1', solve(dict(base, **({'fresh':N+1,'caller':N+1}))), ['fresh-universe'])
check('universe-leak regression 0', solve(dict(base, **({'solution_universes':[N+1],'existential_universe':N}))), ['universe-leak'])
check('universe-leak regression 1', solve(dict(base, **({'solution_universes':[N+2],'existential_universe':N+1}))), ['universe-leak'])
check('universal-coverage regression 0', solve(dict(base, **({'placeholders':['a','b'],'checked':['a']}))), ['universal-coverage'])
check('universal-coverage regression 1', solve(dict(base, **({'placeholders':list(range(N+1)),'checked':[0]}))), ['universal-coverage'])
check('alpha-equality regression 0', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':0,'b':1}}))), ['alpha-equality'])
check('alpha-equality regression 1', solve(dict(base, **({'equal_pairs':[('a','a'),('a','b')],'renaming':{'a':N,'b':N+1}}))), ['alpha-equality'])
check('alpha-distinctness regression 0', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':0,'b':1,'c':1}}))), ['alpha-distinctness'])
check('alpha-distinctness regression 1', solve(dict(base, **({'distinct_pairs':[('a','b'),('b','c')],'renaming':{'a':N,'b':N+1,'c':N+1}}))), ['alpha-distinctness'])
check('binder-pop regression 0', solve(dict(base, **({'outside_before':[N],'outside_after':[N]}))), ['binder-pop'])
check('binder-pop regression 1', solve(dict(base, **({'outside_before':[N+1],'outside_after':[N+1]}))), ['binder-pop'])
check('static-skolem regression 0', solve(dict(base, **({'static_choices':['a'],'bound':['a']}))), ['static-skolem'])
check('static-skolem regression 1', solve(dict(base, **({'static_choices':[N],'bound':[N]}))), ['static-skolem'])
check('concrete-universal regression 0', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':['a']}))), ['concrete-universal'])
check('concrete-universal regression 1', solve(dict(base, **({'universal_obligation':True,'concrete_only':True,'checked':[N]}))), ['concrete-universal'])
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 |
|---|---|---|---|
| well formed empty obligations | [] | [] | Passed |
| bound-index-range regression 0 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| bound-index-range regression 1 | ['bound-index-range'] | ['bound-index-range'] | Passed |
| capture-avoiding-shift regression 0 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| capture-avoiding-shift regression 1 | ['capture-avoiding-shift'] | ['capture-avoiding-shift'] | Passed |
| fresh-universe regression 0 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| fresh-universe regression 1 | ['fresh-universe'] | ['fresh-universe'] | Passed |
| universe-leak regression 0 | ['universe-leak'] | ['universe-leak'] | Passed |
| universe-leak regression 1 | ['universe-leak'] | ['universe-leak'] | Passed |
| universal-coverage regression 0 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| universal-coverage regression 1 | ['universal-coverage'] | ['universal-coverage'] | Passed |
| alpha-equality regression 0 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-equality regression 1 | ['alpha-equality'] | ['alpha-equality'] | Passed |
| alpha-distinctness regression 0 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| alpha-distinctness regression 1 | ['alpha-distinctness'] | ['alpha-distinctness'] | Passed |
| binder-pop regression 0 | ['binder-pop'] | ['binder-pop'] | Passed |
| binder-pop regression 1 | ['binder-pop'] | ['binder-pop'] | Passed |
| static-skolem regression 0 | ['static-skolem'] | ['static-skolem'] | Passed |
| static-skolem regression 1 | ['static-skolem'] | ['static-skolem'] | Passed |
| concrete-universal regression 0 | ['concrete-universal'] | ['concrete-universal'] | Passed |
| concrete-universal regression 1 | ['concrete-universal'] | ['concrete-universal'] | Passed |
SHA-256 / 519c50047cfe3ac5196b24b7d0b84c9abb91b48291abf42ad5706536b20c1914
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:44:03.545568+00:00.
Case digest / 944c31fe0b05eb5b587753be6ad3a87c031666e4be859216606c076578b6a1e9