check_anchor_refinement.py

"""Semantic model for paid anchor refinement and deferred left dispatch.
Python directory maps are bookkeeping, not a native timing implementation.
"""
from dataclasses import dataclass,replace
from itertools import product,permutations
import random,json
from check_frozen_row_composition import B,lookup,insert,view,close
from check_row_typed_composition import flag_change
from check_rectangle_deficit import Token,Fibre,extend,debit,count,frame_count,key
import check_pending_substitution as n

@dataclass(frozen=True)
class Row:
    seen:object=B
    entries:tuple=() # spelling, class offset, current anchor profile
@dataclass(frozen=True)
class Meta:
    anchors:int
    frozen:bool
    hist:tuple
    cells:tuple
    population:tuple
@dataclass(frozen=True)
class State:
    rows:object=B
    targets:object=B # ('anchor', index) or ('mask', mask)
    pairs:object=B
    keys:object=B
    unfinished:object=None
    excessive:object=None

def units(k):
    p=None
    for _ in range(k):p=Token(p)
    return p

def anchor_mask(meta,j):
    return sum(1<<(m-1) for m in range(1,len(meta.hist)) if meta.hist[m] is not None and m&(1<<j))

def freeze(meta,k):
    r=(1<<k)-1
    cells=tuple(Fibre(meta.hist[m],units(m.bit_count() if meta.hist[m] is not None else 0),None) for m in range(1,r+1))
    hist=[None]*(1<<r)
    for j in range(meta.anchors):
        q=anchor_mask(meta,j);hist[q]=Token(hist[q])
    return replace(meta,frozen=True,cells=cells,population=tuple(hist))

def bad(meta,K):
    if meta is None:return False,False
    u=any(f.deficit is not None for f in meta.cells) if meta.frozen else False
    q=sum(x is not None for x in meta.population) if meta.frozen else len({anchor_mask(meta,j) for j in range(meta.anchors)})
    return u,q>K

def step(st,v,w,k=2,d=2,s=1,K=2):
    z=key(w)
    if z is None or abs(n.cls(v)-n.cls(z))>s:return None
    row=lookup(st.rows,v) or Row();slot=lookup(row.seen,z)
    if slot is None:
        if len(row.entries)==d:return None
        idx=len(row.entries);entries=list(row.entries)+[(tuple(z),n.cls(z)-n.cls(v),0)]
        seen=insert(row.seen,z,idx+1)
    else:idx=slot-1;entries=list(row.entries);seen=row.seen
    profile=entries[idx][2]
    r=(1<<k)-1
    meta=lookup(st.keys,z) or Meta(0,False,(None,)*(r+1),(),())
    before=lookup(st.keys,z)
    pairroot=lookup(st.pairs,v) or B;dup=bool(lookup(pairroot,w))
    desc=lookup(st.targets,w)
    if desc is None:
        if meta.anchors<k:
            desc=('anchor',meta.anchors);meta=replace(meta,anchors=meta.anchors+1)
        else:
            if not meta.frozen:meta=freeze(meta,k)
            desc=('mask',0)
    if desc[0]=='anchor':
        if meta.frozen:
            if not dup:return None
        else:
            new=profile|(1<<desc[1])
            if new!=profile:
                hist=list(meta.hist)
                if profile:assert hist[profile] is not None;hist[profile]=hist[profile].tail
                hist[new]=Token(hist[new]);meta=replace(meta,hist=tuple(hist))
                entries[idx]=(entries[idx][0],entries[idx][1],new)
    else:
        if not profile:return None
        c=profile-1;bit=1<<c;mask=desc[1];new=mask|bit
        f=meta.cells[c];debt=f.deficit;tc=f.targets
        if not mask&bit:debt=extend(debt,f.predecessors);tc=Token(tc)
        if not dup:debt=debit(debt)
        cells=list(meta.cells);cells[c]=Fibre(f.predecessors,tc,debt)
        hist=list(meta.population)
        if mask!=new:
            if mask:assert hist[mask] is not None;hist[mask]=hist[mask].tail
            hist[new]=Token(hist[new])
        meta=replace(meta,cells=tuple(cells),population=tuple(hist));desc=('mask',new)
    return State(insert(st.rows,v,Row(seen,tuple(entries))),insert(st.targets,w,desc),
                 insert(st.pairs,v,insert(pairroot,w,True)),insert(st.keys,z,meta),
                 flag_change(st.unfinished,bad(before,K)[0],bad(meta,K)[0]),
                 flag_change(st.excessive,bad(before,K)[1],bad(meta,K)[1]))

def oracle(seq,k=2,d=2,s=1):
    groups={};seen=set();rows={}
    for v,w in seq:
        z=key(w)
        if z is None or abs(n.cls(v)-n.cls(z))>s:return None
        rows.setdefault(v,set()).add(z)
        if len(rows[v])>d:return None
        a,closed,edges=groups.setdefault(z,([],False,set()))
        ws={b for x,b in edges}
        if w not in ws:
            if len(a)<k:a.append(w)
            else:closed=True
        if closed and w in a and (v,w) not in edges:return None
        if closed and not any((v,t) in edges for t in a):return None
        edges.add((v,w));groups[z]=(a,closed,edges)
    return groups

def inspect(st,seq,K=2,k=2,d=2,s=1):
    groups=oracle(seq,k,d,s);assert groups is not None
    ok=True;badkeys=0;excesskeys=0
    for z,(anchors,frozen,edges) in groups.items():
        meta=lookup(st.keys,z);assert meta.anchors==len(anchors) and meta.frozen==frozen
        vs={v for v,w in edges};ws={w for v,w in edges}
        profile={v:sum(1<<j for j,w in enumerate(anchors) if (v,w) in edges) for v in vs}
        for v in vs:
            row=lookup(st.rows,v);idx=lookup(row.seen,z)-1
            assert ''.join(row.entries[idx][0])==z and row.entries[idx][2]==profile[v]
        h=[sum(m==a for a in profile.values()) for m in range(1<<k)]
        assert h[0]==0 and [count(x) for x in meta.hist]==h
        hist=[0]*(1<<((1<<k)-1))
        rectangles=True
        for w in ws:
            mask=sum(1<<(m-1) for m in range(1,1<<k) if any(b==w and profile[v]==m for v,b in edges))
            desc=lookup(st.targets,w)
            got=anchor_mask(meta,desc[1]) if desc[0]=='anchor' else desc[1]
            assert got==mask;hist[mask]+=1
        if frozen:
            assert [count(x) for x in meta.population]==hist
            for m in range(1,1<<k):
                es={(v,w) for v,w in edges if profile[v]==m};V={v for v in vs if profile[v]==m};T={w for v,w in es}
                f=meta.cells[m-1];debt=len(V)*len(T)-len(es)
                # Empty profiles have no actual targets even if m has set bits.
                if not V:
                    assert count(f.targets)==0 and f.deficit is None
                    continue
                assert count(f.predecessors)==len(V) and count(f.targets)==len(T) and frame_count(f.deficit)==debt
                rectangles &= not debt
        diversity=len({frozenset(v for v,b in edges if b==w) for w in ws})<=K
        if rectangles:assert diversity==(sum(bool(x) for x in hist)<=K)
        badkeys+=not rectangles
        excesskeys+=sum(bool(x) for x in hist)>K
        ok &= rectangles and diversity
    assert count(st.unfinished)==badkeys and count(st.excessive)==excesskeys
    assert ok==(st.unfinished is None and st.excessive is None)
    return ok

def add_left(roots,frozen,u,v,k=2,d=2,s=1):
    receipt=lookup(frozen.rows,v) or Row();out=[]
    for m,root in enumerate(roots,1):
        outer=n.walk(root,u);index=view(outer[1])[0] or {}
        serviced,j=n.service_for_name(index,v,d,s)
        jobs={}
        for word,offset,profile in receipt.entries:
            if profile==m:jobs.setdefault(j+offset,[]).append(word)
        for bucket,words in jobs.items():
            old=serviced.get(bucket,n.Bucket());assert not old.pending
            serviced[bucket]=n.Bucket(old.committed,tuple(words))
        out.append(close(outer,serviced))
    return tuple(out)

stats=dict(sequences=0,prefixes=0,retained_versions=0,queries=0)
def check(seq,K=2,k=2,d=2,s=1,query=True):
    stats['sequences']+=1;st=State();versions=[st]
    for i,(v,w) in enumerate(seq):
        st=step(st,v,w,k,d,s,K)
        if st is None:assert oracle(seq,k,d,s) is None;return None
        inspect(st,seq[:i+1],K,k,d,s);stats['prefixes']+=1;versions.append(st)
    for i,old in enumerate(versions):inspect(old,seq[:i],K,k,d,s);stats['retained_versions']+=1
    if inspect(st,seq,K,k,d,s) and query:
        roots=(B,)*((1<<k)-1);marks=set();leftversions=[(roots,marks)]
        for i,v in enumerate(sorted({v for v,w in seq})+['111']):
            u=str(i%2);roots=add_left(roots,st,u,v,k,d,s);marks=marks|{(u,v)};leftversions.append((roots,marks))
        for roots,marks in leftversions:
            for u,w in product(('0','1'),sorted({w for v,w in seq})+['0001']):
                desc=lookup(st.targets,w);z=key(w)
                mask=0 if desc is None else (anchor_mask(lookup(st.keys,z),desc[1]) if desc[0]=='anchor' else desc[1])
                got=any(mask&(1<<c) and n.index_contains(lookup(roots[c],u) or {},z) for c in range(len(roots)))
                want=any((u,v) in marks and b==w for v,b in seq)
                assert got==want;stats['queries']+=1
    return st

def main():
    rng=random.Random(138);pool=list(product(['0','1'],['10','010','0010','00010']))
    for bits in range(1<<len(pool)):
        seq=[e for i,e in enumerate(pool) if bits>>i&1]
        mix=seq[:];rng.shuffle(mix)
        if mix:mix.append(mix[0])
        for order in (seq,list(reversed(seq)),mix):check(order,K=1+bits%2)
    anchors=[('00','100'),('01','100'),('00','0100'),('10','0100')]
    rest=[('00','00100'),('01','00100'),('00','000100'),('10','000100')]
    for a in permutations(anchors):
        for b in permutations(rest):
            st=check(list(a+b));assert st is not None and inspect(st,list(a+b))
    for _ in range(300):check([rng.choice(pool) for _ in range(rng.randrange(1,20))])
    # Open keys need no closing record or boundary sweep.
    seq=[('0','10'),('1','010'),('0','010'),('1','10')]
    st=check(seq,K=1);assert inspect(st,seq,K=1)
    # A newly named row after anchor closure and a late new anchor edge reject.
    assert check([('0','10'),('1','010'),('0','0010'),('00','0010')]) is None
    assert check([('0','10'),('1','010'),('0','0010'),('1','10')]) is None
    # Exact anchor duplicates after closure are harmless.
    seq=[('0','10'),('1','010'),('0','0010'),('0','10')]
    assert inspect(check(seq),seq)
    # Interleaved normalized keys and per-key closure.
    for _ in range(100):
        seq=[('0','10'),('1','010'),('0','11'),('1','011')]
        rng.shuffle(seq);seq += [('0','0010'),('1','0011')]
        check(seq)
    # Profile classes and their actual names are determined by the relation.
    profile_assignments=0
    rows=['00','01','10','11'];z='00';ts=['0'*j+'1'+z for j in range(4)]
    for profiles in product((1,2,3),repeat=len(rows)):
        if not all(any(m&(1<<j) for m in profiles) for j in range(2)):continue
        pre=[(v,ts[j]) for v,m in zip(rows,profiles) for j in range(2) if m&(1<<j)]
        tail=[(v,ts[j+2]) for v,m in zip(rows,profiles) for j in range(2) if m&(1<<j)]
        rng.shuffle(pre);rng.shuffle(tail)
        st=check(pre+tail);assert st is not None and inspect(st,pre+tail)
        profile_assignments+=1
    growing=[]
    for L in (3,4,5):
        vs=[''.join(v) for v in product('01',repeat=L)];profiles=[1+i%3 for i in range(len(vs))]
        z='0'*L;ts=['0'*j+'1'+z for j in range(6)]
        pre=[(v,ts[j]) for v,m in zip(vs,profiles) for j in range(2) if m&(1<<j)]
        tail=[(v,ts[j]) for v,m in zip(vs,profiles) for j in range(2,6) if m&(1<<(j%2))]
        rng.shuffle(pre);rng.shuffle(tail)
        st=check(pre+tail,d=1,s=0);assert st is not None and inspect(st,pre+tail,d=1,s=0)
        growing.append(len(vs))
    st=State();excess=[]
    for v,w in anchors+rest:
        st=step(st,v,w);excess.append(count(st.excessive))
    assert max(excess)==1 and excess[-1]==0
    for anchor_budget in (1,3):
        for _ in range(64):
            check([rng.choice(pool) for _ in range(rng.randrange(1,12))],k=anchor_budget,K=2)
    print(json.dumps({**stats,'anchor_and_tail_permutations':576,'profile_assignments':profile_assignments,'growing_row_counts':growing,'transient_excess_keys':excess,'native_timing_evidence':False},indent=2))
if __name__=='__main__':main()