pattern_lowering.py (19744B)
1 #!/usr/bin/env python3 2 """Unpublished pattern-lowering candidate: authenticated rebuild, controls and costs. 3 4 Reuses complete unchanged reference modules, rebuilds every affected consumer up 5 through source_unit, and leaves accepted compilers/fixtures untouched. The Haskell 6 control driver is compiled through Nix. No recovery frontend or equality jet. 7 """ 8 import argparse 9 import hashlib 10 import json 11 from pathlib import Path 12 import re 13 import statistics 14 import subprocess 15 import time 16 17 from bundle_dag import Intern, merge_bundles, read 18 from stable_bundle import assembled 19 from executable_object import KINDS, verify_payload 20 from fixture_sources import snapshot_bytes, verify 21 from native_header import native_header 22 from native_library_migration import digest 23 from repair_support_fixture import checked_receipt 24 from shipped_compiler import verify as verify_compiler 25 26 ROOT = Path(__file__).resolve().parent.parent 27 COMMON = '''false = t 28 true = t t 29 triage leaf stem fork = t (t leaf stem) fork 30 lAnd = triage (_ : false) (_ x : x) (_ _ x : x) 31 y = ((mut wait fun : wait mut (x : fun (wait mut x))) 32 (x : x x) 33 (a0 a1 a2 : t (t a0) (t t a2) a1)) 34 select leafK stemK forkK value = ((chosen : chosen t) 35 (triage leafK (child : _ : stemK child) 36 (left right : _ : forkK left right) value)) 37 ''' 38 EQ_BODY = '''triage 39 (triage true (_ : false) (_ _ : false)) 40 (a : triage false (self a) (_ _ : false)) 41 (a b : triage false (_ : false) (c d : lAnd (self a c) (self b d)))''' 42 PROGRAMS = { 43 'copy-triage': 'worker self xs = triage t (_ : t) (head tail : t (t head) (self tail)) xs', 44 'copy-delayed': 'worker self xs = select (_ : t) (_ : t) (head tail : t (t head) (self tail)) xs', 45 'copy-case': 'worker self xs = case xs of\n [] = []\n [head | tail] = t (t head) (self tail)\n _ = []', 46 'copy-equations': 'worker self [] = []\nworker self [head | tail] = t (t head) (self tail)\nworker self _ = []', 47 'copy-case-cons-first': 'worker self xs = case xs of\n [head | tail] = t (t head) (self tail)\n _ = []', 48 'copy-equations-cons-first': 'worker self [head | tail] = t (t head) (self tail)\nworker self _ = []', 49 'copy-equations-cons-first-three': 'worker self [head | tail] = t (t head) (self tail)\nworker self [] = []\nworker self _ = []', 50 'pick-triage': 'pick value = triage t (_ : t t) (_ _ : t t t) value', 51 'pick-delayed': 'pick value = select (_ : t) (_ : t t) (_ _ : t t t) value', 52 'pick-case': 'pick value = case value of\n t = t\n (t _) = t t\n _ = t t t', 53 'pick-equations': 'pick t = t\npick (t _) = t t\npick _ = t t t', 54 'eq-triage': 'worker = (self : ' + EQ_BODY + ')', 55 'eq-triage-explicit': 'worker self left right = (' + EQ_BODY + ') left right', 56 'eq-delayed': '''worker self left right = select 57 (_ : select (_ : t t) (_ : t) (_ _ : t) right) 58 (a : select (_ : t) (b : self a b) (_ _ : t) right) 59 (a b : select (_ : t) (_ : t) (c d : lAnd (self a c) (self b d)) right) 60 left''', 61 'eq-equations': 'worker self t t = t t\nworker self (t a) (t b) = self a b\nworker self (t a b) (t c d) = lAnd (self a c) (self b d)\nworker self _ _ = t', 62 'eq-nested-case': '''worker self left right = case left of 63 t = case right of 64 t = t t 65 _ = t 66 (t a) = case right of 67 (t b) = self a b 68 _ = t 69 (t a b) = case right of 70 (t c d) = lAnd (self a c) (self b d) 71 _ = t 72 _ = t''', 73 } 74 75 76 def authored_cases(): 77 """Reuse the existing independent corpus, not its generation-preparation CLI.""" 78 text = (ROOT / 'test/source_equations.py').read_text() 79 namespace = {'json': json} 80 exec(compile(text[text.index('def quoted'):text.index('manager =')], 81 'source_equations.py:authored-corpus', 'exec'), namespace) 82 return namespace['cases'] 83 84 85 def audit(workspace, store, producer, reused): 86 """Verify receipts, all exported objects and exact local/external pin sets.""" 87 def obj(domain, pin): 88 assert re.fullmatch('[0-9a-f]{64}', pin) 89 payload = (store / 'objects' / pin[:3] / pin).read_bytes() 90 assert digest(domain, payload) == pin 91 return payload 92 modules = {} 93 for source in sorted(workspace.glob('*.tri')): 94 fields = (store / 'cache/source-build' / source.stem).read_text().strip().split('\t') 95 assert len(fields) == 4 and fields[0] == 'arboricx.source-build-cache.v1' 96 _, key, manifest, receipt = fields 97 rows = checked_receipt(obj('arboricx.build-receipt.v1', receipt), source.read_bytes(), manifest, producer) 98 exports = {} 99 for line in obj('arboricx.module-manifest.v1', manifest).decode().splitlines()[1:]: 100 tag, name, kind, pin, abi = line.split('\t') 101 assert tag == 'export' and kind in KINDS and abi == 'arboricx.abi.tree.v1' 102 assert name not in exports 103 verify_payload(kind, obj(kind, pin)) 104 exports[name] = pin 105 dependencies = [row for row in rows if row[0] == 'local'] 106 assert [row[1] for row in dependencies] == native_header(source.read_text())[0] 107 modules[source.stem] = dict(manifest=manifest, receipt=receipt, exports=exports, 108 dependencies=dependencies, pins=[row for row in rows if row[0] == 'pin'], 109 source_sha256=sha(source.read_bytes())) 110 for alias, module in modules.items(): 111 expected = set() 112 for _, dep, manifest, receipt in module['dependencies']: 113 assert (manifest, receipt) == (modules[dep]['manifest'], modules[dep]['receipt']) 114 expected.update(('pin', dep, manifest, name, pin) for name, pin in modules[dep]['exports'].items()) 115 if alias in reused: 116 ref = reused[alias]['manifest'] 117 assert module['manifest'] == ref 118 expected.update(('pin', ref, ref, name, pin) for name, pin in module['exports'].items()) 119 assert {tuple(row) for row in module['pins']} == expected, ('stale dependency pins', alias) 120 return modules 121 122 123 def sha(raw): 124 return hashlib.sha256(raw).hexdigest() 125 126 127 def main(): 128 parser = argparse.ArgumentParser(description=__doc__) 129 parser.add_argument('tricu', type=Path) 130 parser.add_argument('--directory', type=Path, required=True) 131 parser.add_argument('--reference-unit', type=Path, required=True, 132 help='explicit retained source_unit bundle (unqualified exports)') 133 parser.add_argument('--resume', action='store_true', help='diagnostic checkpoint reuse, not fresh-generation acceptance') 134 parser.add_argument('--skip-costs', action='store_true') 135 parser.add_argument('--prepare-worker', action='store_true', 136 help='also rebuild affected map-builder consumers for an explicit transition worker') 137 args = parser.parse_args() 138 root, host = args.directory.resolve(), args.tricu.resolve() 139 root.mkdir(parents=True, exist_ok=args.resume) 140 workspace, store = root / 'workspace', root / 'store' 141 workspace.mkdir(exist_ok=args.resume) 142 # Do not inherit a parent checkout map when the probe lives under it. 143 (workspace / "tricu.workspace").write_text("tricu.workspace.v1\n") 144 metadata = verify_compiler() 145 rows = {row[2]: row for row in verify(ROOT / 'test/fixtures')} 146 report = dict(complete=False, resumed=args.resume, compiler_sha256=metadata['sha256'], 147 runtime_sha256=sha(host.read_bytes()), sources={}, reused={}, commands=[], samples=[], costs=[]) 148 started = time.monotonic() 149 if (root / 'report.json').exists(): 150 previous = (root / 'report.json').read_bytes() 151 assert json.loads(previous)['compiler_sha256'] == metadata['sha256'] 152 (root / ('previous-' + sha(previous) + '.json')).write_bytes(previous) 153 def save(): 154 report['seconds'] = time.monotonic() - started 155 (root / 'report.json').write_text(json.dumps(report, indent=2) + '\n') 156 def command(argv, seconds=30): 157 remaining = 1200 - (time.monotonic() - started) 158 if remaining <= 0: 159 raise TimeoutError('20-minute candidate budget exhausted') 160 begin = time.monotonic() 161 reply = subprocess.run(list(map(str, argv)), cwd=ROOT, capture_output=True, text=True, 162 timeout=min(seconds, remaining)) 163 report['commands'].append(dict(argv=list(map(str, argv)), returncode=reply.returncode, 164 seconds=time.monotonic()-begin, stdout=reply.stdout, stderr=reply.stderr)) 165 save() 166 if reply.returncode: 167 raise RuntimeError(reply.stderr[-3000:] + reply.stdout[-3000:]) 168 return reply 169 def run(options, seconds=30, memory=8192): 170 return command([host, 'arboricx', *options, '+RTS', '-N1', '-T', f'-M{memory}m', '-RTS'], seconds) 171 def imported(path): 172 reply = run(['import', '--file', path, '--store', store], 60) 173 return re.search(r'Created module alias .* -> ([0-9a-f]{64})', reply.stdout)[1] 174 entries = {} 175 for line in (ROOT / 'bootstrap/compiler-source-map.v1').read_text().splitlines()[1:]: 176 fields = line.split('\t') 177 entries[fields[1]] = (fields[3], [] if fields[4] == '-' else fields[4].split(',')) 178 needed = [] 179 def visit(alias): 180 if alias not in needed: 181 for dep in entries[alias][1]: 182 visit(dep) 183 needed.append(alias) 184 visit('source_map' if args.prepare_worker else 'source_unit') 185 affected = {'source_pattern'} 186 for alias in needed: 187 if any(dep in affected for dep in entries[alias][1]): 188 affected.add(alias) 189 active = affected | {dep for alias in affected for dep in entries[alias][1]} 190 report['affected'] = sorted(affected) 191 # Check the transitive unchanged closure, even behind a retained facade. 192 for alias in needed: 193 data = (ROOT / entries[alias][0]).read_bytes() 194 report['sources'][alias] = sha(data) 195 if alias not in affected: 196 assert snapshot_bytes(ROOT / 'test/fixtures', rows[alias][4]) == data, ('stale reuse', alias) 197 reference = root / 'reference-unit.arboricx' 198 reference.write_bytes(args.reference_unit.read_bytes()) 199 imported(reference) # authenticate the explicitly selected reference bundle 200 report['reference_unit_sha256'] = sha(reference.read_bytes()) 201 tool = imported(ROOT / metadata['bundle']) 202 payload = (store / 'objects' / tool[:3] / tool).read_bytes() 203 assert digest('arboricx.module-manifest.v1', payload) == tool 204 producer = next(row.split('\t')[3] for row in payload.decode().splitlines()[1:] if row.split('\t')[1] == 'sourceBuildGraph') 205 for alias in needed: 206 if alias not in active: 207 continue 208 path = workspace / (alias + '.tri') 209 if alias in affected: 210 path.write_bytes((ROOT / entries[alias][0]).read_bytes()) 211 else: 212 cohort, _, _, _, source_pin = rows[alias] 213 fixture = ROOT / 'test/fixtures' / (cohort + '.arboricx') 214 names = [(name, name[len(alias)+1:]) for name in read(fixture)[3] if name.startswith(alias+'.')] 215 assert names 216 bundle = root / (alias + '-retained.arboricx') 217 merge_bundles(bundle, [(fixture, names)], prune_unreachable=True) 218 pin = imported(bundle) 219 path.write_text('!export * from ' + pin + '\n') 220 report['reused'][alias] = dict(source_pin=source_pin, manifest=pin, bundle_sha256=sha(bundle.read_bytes())) 221 assert {p.stem for p in workspace.glob('*.tri')} == active 222 subject = root / 'source_unit.arboricx' 223 run(['compile', '--file', workspace / 'source_unit.tri', '--toolchain', tool, 224 '--tool-store', store, '--store', store, '--output', subject, '--compile-timeout', '600'], 630) 225 if args.prepare_worker: 226 full_worker = root / 'source_map.arboricx' 227 run(['compile', '--file', workspace / 'source_map.tri', '--toolchain', tool, 228 '--tool-store', store, '--store', store, '--output', full_worker, 229 '--compile-timeout', '600'], 630) 230 worker = root / 'worker.arboricx' 231 merge_bundles(worker, [(full_worker, [('sourceMapBuildStable', 'sourceMapBuildStable')])], 232 prune_unreachable=True) 233 imported(worker) 234 report['worker_sha256'] = sha(worker.read_bytes()) 235 report['modules'] = audit(workspace, store, producer, report['reused']) 236 assert imported(subject) == report['modules']['source_unit']['manifest'], 'tested/published unit mismatch' 237 report['candidate_sha256'] = sha(subject.read_bytes()) 238 sources = root / 'program-sources' 239 sources.mkdir(exist_ok=args.resume) 240 for name, body in PROGRAMS.items(): 241 if name.startswith('pick-'): 242 body += '\nworker self xs = triage t (_ : t) (head tail : t (pick head) (self tail)) xs' 243 source = COMMON + body + '\nmain input = y worker input' + (' input' if name.startswith('eq-') else '') + '\n' 244 (sources / (name+'.tri')).write_text(source) 245 (root / 'equations.json').write_text(json.dumps(authored_cases()) + '\n') 246 # GHC is invoked THROUGH Nix, never direct cabal or an ambient compiler. 247 expression = ('let f = builtins.getFlake ("git+file://" + toString ./.); ' 248 'p = f.inputs.nixpkgs.legacyPackages.${builtins.currentSystem}; ' 249 'in p.haskellPackages.ghcWithPackages (h: [h.cryptonite h.memory h.base16-bytestring h.vector h.aeson])') 250 command(['nix', 'shell', '--impure', '--expr', expression, '--command', 'ghc', '-O2', '-rtsopts', 251 '-XOverloadedStrings', '-XLambdaCase', '-XMultiWayIf', '-XScopedTypeVariables', '-isrc', 252 '-outputdir', root / 'test-objects', ROOT / 'test/PatternLowering.hs', '-o', root / 'controls'], 180) 253 report['controls'] = command([root / 'controls', root, '+RTS', '-M4096m', '-RTS'], 180).stdout 254 local = root / ('local-control-' + str(time.time_ns())) 255 command(['python3', ROOT / 'test/local_control.py', host, '--unit', subject, '--directory', local], 180) 256 report['local_control'] = json.loads((local / 'report.json').read_text()) 257 if not args.skip_costs: 258 cost_probes(root, run, imported, report, save) 259 report['complete'] = True 260 save() 261 print('PASS: unpublished candidate; all affected consumers rebuilt and audited.') 262 for row in report['costs'] + report.get('construction_costs', []): 263 print(json.dumps(row)) 264 265 266 def cost_probes(root, run, imported, report, save): 267 names = ['copy-triage', 'copy-equations', 'copy-case', 'copy-equations-cons-first-three', 268 'pick-triage', 'pick-case', 'pick-equations', 'eq-triage-explicit', 'eq-equations', 'eq-nested-case'] 269 pins = {name: {role: imported(root / folder / (name+'.arboricx')) 270 for role, folder in [('reference', 'reference-programs'), ('candidate', 'programs')]} 271 for name in names} 272 values = [[b'\0', b'\1\0', b'\2\0\0'][i % 3] for i in range(2048)] 273 list_file = root / 'list.tree' 274 list_file.write_bytes(b''.join(b'\2'+v for v in values)+b'\0') 275 intern = Intern() 276 index = intern.node((0,)) 277 for _ in range(12): 278 index = intern.node((2, index, index)) 279 # Preserve a single export by selecting main before replacing its node table. 280 single = root / 'input-template.arboricx' 281 merge_bundles(single, [(root / 'reference-programs/eq-triage.arboricx', [('main', 'main')])], prune_unreachable=True) 282 template = read(single) 283 import struct 284 manifest = bytearray(template[0]) 285 for offsets in template[4].values(): 286 for offset in offsets: 287 struct.pack_into('>I', manifest, offset, index) 288 dag = root / 'dag.arboricx' 289 dag.write_bytes(assembled(manifest, intern.encoded())) 290 argument = imported(dag) 291 for name in names: 292 if name.startswith('eq-'): 293 arguments, expected = ['--arg-export', argument+':main'], '10' 294 else: 295 xs = [b'\1'+v for v in values] if name.startswith('copy-') else values 296 arguments = ['--arg-tree-file', list_file] 297 expected = ''.join(str(v) for v in b''.join(b'\2'+v for v in xs)+b'\0') 298 for repetition in range(4): 299 for role in (['reference', 'candidate'] if repetition % 2 == 0 else ['candidate', 'reference']): 300 reply = run(['run', '--module', pins[name][role], '--name', 'main', '--store', root/'store', 301 *arguments, '--format', 'ternary', '--profile', '--profile-full-result'], 20, 512) 302 assert reply.stdout == expected, (name, role, 'independent complete-output oracle') 303 samples = {v['profile']: v for line in reply.stderr.splitlines() if line.startswith('{') for v in [json.loads(line)]} 304 before, after = samples['force-begin-1'], samples['force-end-1'] 305 report['samples'].append(dict(name=name, role=role, warmup=repetition == 0, 306 wall_ns=after['wall_ns']-before['wall_ns'], allocated_bytes=after['allocated_bytes']-before['allocated_bytes'])) 307 medians = {role: {key: statistics.median(row[key] for row in report['samples'] 308 if row['name'] == name and row['role'] == role and not row['warmup']) 309 for key in ['wall_ns', 'allocated_bytes']} for role in ['reference', 'candidate']} 310 report['costs'].append(dict(name=name, scope='full-result-forcing-v1', medians=medians)) 311 save() 312 # Also screen compiler construction costs, not only the resulting programs. 313 # Full forcing observes all returned definition trees. Semantic/code-generation 314 # oracles for these exact sources have already run in the Haskell driver. 315 from stable_bundle import byte_tree 316 reference = root / 'reference-unit.arboricx' 317 compilers = {'reference': imported(reference), 'candidate': imported(root / 'source_unit.arboricx')} 318 environment = root / 'empty-environment.tree' 319 environment.write_bytes(b'\0') 320 report['construction_samples'], report['construction_costs'] = [], [] 321 for name in ['copy-equations', 'pick-equations', 'eq-equations']: 322 source = root / (name + '.source.tree') 323 source.write_bytes(byte_tree((root / 'program-sources' / (name+'.tri')).read_bytes())) 324 for repetition in range(4): 325 for role in (['reference', 'candidate'] if repetition % 2 == 0 else ['candidate', 'reference']): 326 reply = run(['run', '--module', compilers[role], '--name', 'compileStableModuleDefinitions', 327 '--store', root/'store', '--arg-tree-file', environment, '--arg-tree-file', source, 328 '--profile', '--profile-full-result', '--result', '--format', 'number'], 30, 1024) 329 # Deliberately cheap presentation AFTER complete forcing: the 330 # definition list is not a number. A compiler error is not success. 331 assert reply.stdout == 'ok: <not-number: Invalid Tree Calculus number>' 332 samples = {v['profile']: v for line in reply.stderr.splitlines() if line.startswith('{') for v in [json.loads(line)]} 333 before, after = samples['force-begin-1'], samples['force-end-1'] 334 report['construction_samples'].append(dict(name=name, role=role, warmup=repetition == 0, 335 wall_ns=after['wall_ns']-before['wall_ns'], allocated_bytes=after['allocated_bytes']-before['allocated_bytes'])) 336 medians = {role: {key: statistics.median(row[key] for row in report['construction_samples'] 337 if row['name'] == name and row['role'] == role and not row['warmup']) 338 for key in ['wall_ns', 'allocated_bytes']} for role in ['reference', 'candidate']} 339 report['construction_costs'].append(dict(name=name, scope='compile-full-definitions-v1', medians=medians)) 340 save() 341 342 343 if __name__ == '__main__': 344 main()