source_resolution_models.py (12602B)
1 """Independent regression models/cases retained from retired batch workflows. 2 3 Probe templates are test data, not a preparation CLI. Model unit tests do not 4 validate an edited compiler. No historical Git objects or reference workspaces 5 are required to import these helpers. 6 """ 7 from dataclasses import dataclass, replace 8 9 10 import hashlib 11 12 13 import json 14 15 16 from pathlib import Path 17 18 19 import random 20 21 22 from base_workloads import encode as n 23 24 25 from http_headers import LEAF, TRUE, pair, tree_list, result, expect 26 27 28 from source_grammar_models import node, diagnostic 29 30 31 from source_order import field 32 33 34 from tooling_batch_models import chars, position 35 36 37 ROOT=Path(__file__).resolve().parent.parent 38 39 40 DRIVER='''!import prelude as B 41 !import source_resolve as R 42 !import source_order as O 43 !import source_ast as A 44 !export models 45 !export free 46 !export graphs 47 !export demand 48 !export wrong 49 models rows = B.map (row : B.pair (R.resolveGateAst (B.fst row) (B.snd row)) (O.sourceFreeNames (B.snd row))) rows 50 free rows = B.map O.sourceFreeNames rows 51 graphs rows = B.map (row : B.pair (O.orderGateProgram (B.fst row) (B.snd row)) (O.sourceAnalyzeDefinitions (B.fst (B.snd row)) (B.fst row))) rows 52 wrong _ = t 53 spin x = spin x 54 name text = A.sourceAstNode 2 text 7 8 55 errorCode reply = B.lazyResult (diagnostic _ : B.fst diagnostic) (_ _ : 99) reply 56 demand x = [ 57 (R.sourceFindBinder (B.pair "a" (spin x)) "a") 58 (R.sourceFindExternal (B.pair (B.pair "a" 23) (spin x)) "a") 59 (R.sourceFindExternal [(B.pair "other" (spin x)) (B.pair "a" 24)] "a") 60 (O.sourceFreeNames (A.sourceAstNode 1 (spin x) (spin x) (spin x))) 61 (R.sourceResolveElements (B.pair t (spin x)) (_ _ _ : B.err 77 9) (spin x) (spin x)) 62 (R.sourceResolveName (name "a") ["a"] (spin x)) 63 (O.sourceAnalyzeNames [(name "a")] [(B.pair (name "a") (spin x))] (spin x)) 64 (errorCode (O.sourceAnalyzeNames (B.pair (name "missing") (spin x)) [] [])) 65 (errorCode (O.orderGateProgram (spin x) (B.pair 66 [(B.pair (name "a") (spin x)) (B.pair (name "a") (spin x))] (spin x))))] 67 ''' 68 69 70 def sha(raw):return hashlib.sha256(raw).hexdigest() 71 72 73 @dataclass(frozen=True) 74 class Ast: 75 kind: int 76 payload: object=LEAF 77 at: int=1 78 79 @property 80 def start(self):return position(1,self.at+1,self.at) 81 @property 82 def end(self):return position(1,self.at+2,self.at+1) 83 def tree(self): 84 k,p=self.kind,self.payload 85 if k in (2,7):p=chars(p) 86 elif k==6:p=n(p) 87 elif k==3:p=pair(*(x.tree() for x in p)) 88 elif k==4:p=pair(chars(p[0]),p[1].tree()) 89 elif k==5:p=p.tree() 90 elif k==8:p=tree_list(x.tree() for x in p) 91 elif k in (9,15):p=pair(Ast(2,p[0],self.at).tree(),pair(p[1].tree(),p[2].tree())) 92 elif k==10:p=pair(n(p[0]),pair(p[1].tree(),p[2].tree())) 93 elif k==11:p=pair(p[0].tree(),tree_list(pair(LEAF if name is None else b'\1'+Ast(2,name,body.at).tree(),body.tree()) for name,body in p[1])) 94 elif k==12:p=tree_list(pair(tree_list(pattern.tree() for pattern in patterns),body.tree()) for patterns,body in p) 95 elif k==13: 96 tag,value=p 97 if tag==2:value=value.tree() 98 elif tag==3:value=pair(*(x.tree() for x in value)) 99 elif tag==4:value=chars(value) 100 elif tag==6:value=pair(chars(value[0]),value[1].tree()) 101 elif tag==7:value=value.tree() 102 p=pair(n(tag),value) 103 elif k==14:p=pair(p[0].tree(),p[1].tree()) 104 return node(k,p,self.start,self.end) 105 106 107 def do_lower(a): 108 operator,statements=a.payload 109 if not statements:return operator 110 _,body=statements[-1] 111 for binder,value in reversed(statements[:-1]): 112 body=Ast(3,(Ast(3,(operator,value),operator.at),Ast(4,(binder or '_',body),value.at)),operator.at) 113 return body 114 115 116 def captures(pattern): 117 tag,p=pattern.payload 118 if tag==4:return [p] 119 if tag==6:return [p[0]]+captures(p[1]) 120 if tag==2:return captures(p) 121 if tag==3:return captures(p[0])+captures(p[1]) 122 return [] 123 124 125 def pins(pattern): 126 tag,p=pattern.payload 127 if tag==7:return [p] 128 if tag==6:return pins(p[1]) 129 if tag==2:return pins(p) 130 if tag==3:return pins(p[0])+pins(p[1]) 131 return [] 132 133 134 def free(a,bound=()): 135 k,p=a.kind,a.payload 136 if k==2:return [] if p in bound else [a] 137 if k==3:return free(p[0],bound)+free(p[1],bound) 138 if k==4:return free(p[1],(p[0],)+bound) 139 if k==5:return free(p,bound) 140 if k==8:return [v for child in p for v in free(child,bound)] 141 if k in (9,15): 142 nested=(p[0],)+bound 143 return free(p[1],nested if k==15 else bound)+free(p[2],nested) 144 if k==10:return free(p[1],bound)+free(p[2],bound) 145 if k==11:return free(do_lower(a),bound) 146 if k==12: 147 names=[] 148 for patterns,body in p: 149 names += [v for pattern in patterns for pin in pins(pattern) for v in free(pin,bound)] 150 scope=tuple(reversed([name for pattern in patterns for name in captures(pattern)]))+bound 151 names += free(body,scope) 152 return names 153 if k==14:return free(p[0],bound)+free(p[1],bound) 154 return [] 155 156 157 class Missing(Exception): 158 def __init__(self,tree):self.tree=tree 159 160 161 def resolved(a,environment,bound=()): 162 """Ordinary surface syntax -> scoped core. No candidate/oracle parser call.""" 163 k,p=a.kind,a.payload 164 def core(kind,payload=LEAF):return node(kind,payload,a.start,a.end) 165 if k in (1,6,7):return core(k,LEAF if k==1 else n(p) if k==6 else chars(p)) 166 if k==2: 167 if p in bound:return core(2,n(bound.index(p))) 168 for name,tree in environment: 169 if name==p:return core(5,tree) 170 raise Missing(result(False,diagnostic(20,chars(p),LEAF,a.start),a.tree())) 171 if k==3: 172 left=resolved(p[0],environment,bound);right=resolved(p[1],environment,bound) 173 return core(3,pair(left,right)) 174 if k==4:return core(4,resolved(p[1],environment,(p[0],)+bound)) 175 if k==5: 176 child=resolved(p,environment,bound) 177 return node_from_span(child,a) 178 if k==8:return core(8,tree_list(resolved(child,environment,bound) for child in p)) 179 if k==9: 180 value=resolved(p[1],environment,bound) 181 body=resolved(p[2],environment,(p[0],)+bound) 182 return core(3,pair(core(4,body),value)) 183 if k==10: 184 left=resolved(p[1],environment,bound);right=resolved(p[2],environment,bound) 185 return core(3,pair(left,right) if p[0]==15 else pair(right,left)) 186 raise Missing(result(False,diagnostic(21,LEAF,n(k),a.start),a.tree())) 187 188 189 def node_from_span(tree,a):return node_from_parts(field(tree,0),field(tree,1,0),a.start,a.end) 190 191 192 def node_from_parts(kind,payload,start,end):return pair(kind,pair(payload,pair(start,end))) 193 194 195 def resolve_result(a,environment): 196 try:return result(True,resolved(a,environment)) 197 except Missing as error:return error.tree 198 199 200 def environment_tree(environment):return tree_list(pair(chars(name),tree) for name,tree in environment) 201 202 203 def ast_cases(): 204 rng=random.Random(3809);serial=0 205 def make(depth): 206 nonlocal serial 207 serial+=1;at=serial 208 k=rng.choice([1,2,3,4,5,6,7,8,9,10] if depth else [1,2,6,7]) 209 if k==1:p=LEAF 210 elif k==2:p=rng.choice(['a','b','outside','missing']) 211 elif k==6:p=rng.randrange(32) 212 elif k==7:p=rng.choice(['a','λ','']) 213 elif k==3:p=(make(depth-1),make(depth-1)) 214 elif k==4:p=(rng.choice(['a','b']),make(depth-1)) 215 elif k==5:p=make(depth-1) 216 elif k==8:p=[make(depth-1) for _ in range(rng.randrange(4))] 217 elif k==9:p=(rng.choice(['a','b']),make(depth-1),make(depth-1)) 218 else:p=(rng.choice([15,16]),make(depth-1),make(depth-1)) 219 return Ast(k,p,at) 220 a,b=Ast(2,'a',2),Ast(2,'b',3) 221 nodes=[a,Ast(4,('a',Ast(4,('a',a)))),Ast(4,('a',Ast(4,('b',a)))), 222 Ast(9,('a',a,Ast(4,('b',a)))),Ast(3,(a,b)),Ast(10,(16,a,b)),Ast(5,a),Ast(99)] 223 nodes += [make(4) for _ in range(112)] 224 environments=[[],[('a',n(23)),('a',n(99)),('b',n(24)),('outside',a.tree())]] 225 return [(a,env) for a in nodes for env in environments] 226 227 228 def scope_cases(): 229 a,b=Ast(2,'a',2),Ast(2,'b',3) 230 capture=Ast(13,(4,'a'));pin=Ast(13,(7,a)) 231 nested=Ast(13,(6,('whole',Ast(13,(3,(capture,Ast(13,(2,Ast(13,(4,'b')))))))))) 232 groups=[Ast(12,[([p],Ast(8,[a,b,Ast(2,'whole'),a]))]) for p in [capture,pin,nested]] 233 rows=groups+[Ast(14,(a,g)) for g in groups] 234 rows += [Ast(4,('a',g)) for g in rows[:]] 235 rows += [Ast(15,('a',Ast(4,('b',Ast(3,(a,b)))),a)),Ast(9,('a',a,a)),Ast(15,('a',a,a))] 236 rows += [Ast(11,(a,statements)) for statements in [[],[(None,b)],[('a',a),(None,a)],[(None,b),(None,Ast(2,'_'))], [('b',a),('a',b),(None,Ast(8,[a,b]))]]] 237 return rows 238 239 240 def pattern_result(pattern,binders,environment): 241 def lower(pattern): 242 tag,p=pattern.payload 243 if tag==2:p=lower(p) 244 elif tag==3:p=pair(lower(p[0]),lower(p[1])) 245 elif tag==4:p=chars(p) 246 elif tag==6:p=pair(chars(p[0]),lower(p[1])) 247 elif tag==7:p=resolved(p,environment,tuple(binders)) 248 return pair(n(tag),pair(p,pattern.start)) 249 try:return result(True,lower(pattern)) 250 except Missing as error:return error.tree 251 252 253 def pattern_cases(): 254 a,b,missing=[Ast(13,(7,Ast(2,name,at)),at) for name,at in [('a',2),('b',3),('missing',4)]] 255 capture=Ast(13,(4,'a'));literal=Ast(13,(5,Ast(2,'opaque').tree())) 256 patterns=[Ast(13,(0,LEAF)),Ast(13,(1,LEAF)),capture,literal,a,b,missing, 257 Ast(13,(2,a)),Ast(13,(3,(a,b))),Ast(13,(6,('a',a))), 258 Ast(13,(3,(missing,a))),Ast(13,(3,(a,missing)))] 259 return [(pattern,binders,env) for pattern in patterns 260 for binders in [[],['a'],['b','a','b']] 261 for env in [[],[('a',Ast(2,'opaque').tree()),('a',n(99)),('b',n(24))]]] 262 263 264 def program_tree(definitions,final): 265 return pair(tree_list(pair(token.tree(),body.tree()) for token,body in definitions),LEAF if final is None else b'\1'+final.tree()) 266 267 268 def graph_model(definitions,environment,final): 269 local=[token.payload for token,_ in definitions];external={name for name,_ in environment} 270 graph=[];analysis=None;duplicate=None;seen=set() 271 for token,body in definitions: 272 if token.payload in seen and duplicate is None: 273 duplicate=result(False,diagnostic(30,chars(token.payload),chars(token.payload),token.start),pair(token.tree(),body.tree())) 274 seen.add(token.payload) 275 dependencies=[] 276 for mention in free(body): 277 name=mention.payload 278 if name in local:dependencies.append(name) 279 elif name not in external and analysis is None: 280 analysis=result(False,diagnostic(20,chars(name),LEAF,mention.start),mention.tree()) 281 graph.append((token.payload,dependencies)) 282 analyzed=analysis if analysis is not None else result(True,tree_list(pair(chars(name),tree_list(chars(dep) for dep in deps)) for name,deps in graph)) 283 if duplicate is not None:return duplicate,analyzed 284 if analysis is not None:return analysis,analyzed 285 if final is not None: 286 for mention in free(final): 287 if mention.payload not in local and mention.payload not in external: 288 return result(False,diagnostic(20,chars(mention.payload),LEAF,mention.start),mention.tree()),analyzed 289 pending=dict(graph);ordered=[] 290 while pending: 291 ready=next((name for name,deps in pending.items() if all(dep in ordered for dep in deps)),None) 292 if ready is not None:ordered.append(ready);del pending[ready];continue 293 current=next(iter(pending));visited=set() 294 while current not in visited: 295 visited.add(current);current=next(dep for dep in pending[current] if dep in pending) 296 token=next(token for token,_ in definitions if token.payload==current) 297 diag=pair(n(31),pair(chars('acyclic'),pair(chars(current),pair(token.start,tree_list([chars(current)]))))) 298 return result(False,diag),analyzed 299 return result(True,tree_list(chars(name) for name in ordered)),analyzed 300 301 302 def graph_cases(): 303 rng=random.Random(512);rows=[] 304 for i in range(120): 305 names=['v'+str(j) for j in range(rng.randrange(9))];definitions=[] 306 for j,name in enumerate(names): 307 mentions=[Ast(2,rng.choice(names+['outside','missing']),10+j*10+k) for k in range(rng.randrange(5))] 308 definitions.append((Ast(2,name,1+j),Ast(8,mentions))) 309 if definitions and i%9==0:definitions.append((replace(definitions[0][0],at=99),Ast(2,'missing',98))) 310 environment=[('outside',n(23))]+([(names[0],n(99))] if names else []) 311 final=Ast(2,'missing',100) if i%7==0 else None 312 rows.append((definitions,environment,final)) 313 return rows