#!/usr/bin/env python3 """Driver for the checks of the computer-assisted parts of the paper (Appendix E). Python 3.8 or later, numpy, gcc. Usage: python3 run_all_checks.py [--quick | --full] [--only h1,h2,h3] [--workdir DIR] [--parts N] --quick (the default) runs the fast checks, about six minutes on one core and at most 0.6 GB of memory: h2 h2_check.py (the exact check of (H2)); its output must equal h2/h2_output.log. h1 check_certificate_file.py (each pattern has one certificate, at the threshold of its type, in the covered model, with tip radius 3/5); verify_all.py on the certificates of the pids 0, 100, 200, ..., 7900 (80 of the 7,962); closed_exact.py (a second, closed-form proof for the 4,735 patterns whose ring decouples); enumerate_patterns.py (the class of patterns, enumerated again, equals patterns.json). h3 compiles tailmem5, bellman and exact75 (each wrapper checks the sha256 digest of the C source it stores); runs exact75 in the five recorded cases (output equal to the logs exact75_*.log); runs tailmem5 in the five cases with a small quotient walk (lines E equal to the logs short_trails_*.log); compares the two enumerations; runs bellman in the five cases without sweeps (see jobs.yaml); recomputes Table tab:tail from the recorded logs by exact rational arithmetic. --full runs the quick checks and then: h1 verify_all.py on all 7,962 certificates, in N processes (--parts N, default 4): about 23 CPU-minutes. h3 the fifteen recorded runs of jobs.yaml, one at a time: tailmem5 (3.1 GB, about three minutes each; the output must equal the log), bellman (1.3 GB, about ten minutes each on four cores; the run must pass, and its bound must not exceed the entry of Table tab:tail), exact75 (seconds). --only restricts the checks to the listed hypotheses. --workdir DIR keeps the build directories and the outputs of all runs (DIR/out/NAME.out, standard output, and NAME.err, standard error) in DIR (default: a temporary directory, removed at the end). The script never modifies the files of anc/. Exit status 0 if every check passes.""" import argparse, json, math, os, re, shutil, subprocess, sys, tempfile, time from fractions import Fraction as Fr HERE = os.path.dirname(os.path.abspath(__file__)) H1, H2, H3 = (os.path.join(HERE, h) for h in ('h1', 'h2', 'h3')) PY = sys.executable RESULTS = [] OUT = None # directory for the outputs of the runs ENV = dict(os.environ, PYTHONDONTWRITEBYTECODE='1') # no __pycache__ in anc/ ENV.pop('PYTHONOPTIMIZE', None) # assertions must stay enabled ENV.pop('TIPRAD', None) # tip radius 3/5 (default of ring.py) # Table tab:tail of the paper: every entry rounded up in the sixth decimal TABLE = {('B', 'exact'): '0.582353', ('C', 'exact'): '0.823644', ('B', 1): '0.111332', ('B', 2): '0.118181', ('B', 3): '0.111332', ('C', 1): '0.078222', ('C', 2): '0.114607', ('C', 3): '0.107712', ('B', 'sum'): '0.923198', ('C', 'sum'): '1.124185', ('B', 'K'): '0.923198', ('C', 'K'): '0.899348'} def save(name, out, err): for ext, ls in (('.out', out), ('.err', err)): with open(os.path.join(OUT, name.replace(' ', '_') + ext), 'w') as f: f.write(''.join(l + '\n' for l in ls)) def record(name, ok, detail, t0): RESULTS.append((name, ok, detail, time.time() - t0)) print('%-34s %-5s %7.1fs %s' % (name, 'PASS' if ok else 'FAIL', time.time() - t0, detail), flush=True) def run(cmd, cwd=None): """run cmd; returns (exit code, stdout lines, stderr lines)""" r = subprocess.run(cmd, cwd=cwd, env=ENV, stdout=subprocess.PIPE, stderr=subprocess.PIPE, universal_newlines=True) return r.returncode, r.stdout.splitlines(), r.stderr.splitlines() def lines(path): with open(path) as f: return f.read().splitlines() def load_jobs(): """reads h3/jobs.yaml: top-level keys, each a list of mappings with plain or JSON-list values (no PyYAML needed)""" out, key, item = {}, None, None for raw in lines(os.path.join(H3, 'jobs.yaml')): if not raw.strip() or raw.lstrip().startswith('#'): continue if not raw.startswith(' '): key = raw.rstrip(':').strip(); out[key] = []; continue s = raw.strip() if s.startswith('- '): item = {}; out[key].append(item); s = s[2:] k, v = s.split(':', 1) v = v.strip() item[k.strip()] = json.loads(v) if v.startswith('[') else v return out def floats_after(prefix, ls): """{n: value} from the lines 'prefix n value' (exact rationals of the printed decimals)""" return {int(l.split()[1]): Fr(l.split()[2]) for l in ls if l.startswith(prefix + ' ')} # ---------------------------------------------------------------- (H2) def check_h2(): t0 = time.time() rc, out, err = run([PY, os.path.join(H2, 'h2_check.py')]) save('h2_check', out, err) ok = rc == 0 and out == lines(os.path.join(H2, 'h2_output.log')) record('h2 h2_check.py', ok, out[-1] if out else ' '.join(err[-1:]), t0) # ---------------------------------------------------------------- (H1) def check_h1(full, parts): t0 = time.time() rc, out, err = run([PY, os.path.join(H1, 'check_certificate_file.py')]) save('check_certificate_file', out, err) record('h1 check_certificate_file.py', rc == 0 and out[-1:] == ['CERTIFICATE FILE CHECK PASS'], out[-1] if out else ' '.join(err[-1:]), t0) t0 = time.time() rc, out, err = run([PY, os.path.join(H1, 'verify_all.py'), os.path.join(H1, 'certificates.jsonl'), '0', '100']) save('verify_all_0_100', out, err) ok = rc == 0 and len(out) == 1 and out[0].startswith('certificates 80 verified 80 failed []') record('h1 verify_all.py (80 of 7962)', ok, out[-1] if out else ' '.join(err[-1:]), t0) t0 = time.time() rc, out, err = run([PY, os.path.join(H1, 'closed_exact.py')]) save('closed_exact', out, err) expected = ('tip radius 3/5 | covered : decoupled patterns 4735 certified exactly at ' '(961/1000, 187/200): 4735 fails []') record('h1 closed_exact.py (4735 patterns)', rc == 0 and out[:1] == [expected], 'second proof for the decoupled patterns: ' + (out[0].split(': ', 1)[1] if out else ' '.join(err[-1:])), t0) t0 = time.time() rc, out, err = run([PY, os.path.join(H1, 'enumerate_patterns.py')]) save('enumerate_patterns', out, err) expected = ['consistent raw configurations 106101 effective patterns 7962 straight 2696 turn 5266', 'certified list: records 7962 distinct canonical keys 7962', 'in enumeration but not in list: 0 in list but not in enumeration: 0'] record('h1 enumerate_patterns.py', rc == 0 and out == expected, out[0] if out else ' '.join(err[-1:]), t0) if not full: return t0 = time.time() procs = [subprocess.Popen([PY, os.path.join(H1, 'verify_all.py'), os.path.join(H1, 'certificates.jsonl'), str(k), str(parts)], env=ENV, stdout=subprocess.PIPE, stderr=subprocess.PIPE, universal_newlines=True) for k in range(parts)] nver, nall, failed, ok = 0, 0, [], True for k, p in enumerate(procs): o, e = p.communicate() save('verify_all_%d_%d' % (k, parts), o.splitlines(), e.splitlines()) m = re.match(r'certificates (\d+) verified (\d+) failed \[(.*)\]', o.strip()) if p.returncode != 0 or not m: ok = False; continue nall += int(m.group(1)); nver += int(m.group(2)) failed += [x for x in m.group(3).split(',') if x.strip()] ok = ok and nall == 7962 and nver == 7962 and not failed record('h1 verify_all.py (all, %d parts)' % parts, ok, 'certificates %d verified %d failed %s' % (nall, nver, failed), t0) # ---------------------------------------------------------------- (H3) def wrapper(job, build): """runs the job (a mapping of jobs.yaml) through its wrapper anc/h3/, building in build/""" name = job['program'][:-3] rc, out, err = run([PY, os.path.join(H3, job['program']), '--workdir', os.path.join(build, name), '--'] + list(job['args'])) save(job['name'], out, err) return rc, out, err def tail_bound(ls): for l in ls: m = re.match(r'TAIL X=(\w) D0=(\d)\s+sum_\{n>20\} <= (\S+)\s+PASS', l) if m: return Fr(m.group(3)) return None def check_h3(full, build): jobs = load_jobs() t0 = time.time() ok, detail = True, [] for prog in ('tailmem5.py', 'bellman.py', 'exact75.py'): rc, out, err = run([PY, os.path.join(H3, prog), '--workdir', os.path.join(build, prog[:-3]), '--compile-only']) ok = ok and rc == 0 detail.append('%s %s' % (prog[:-3], 'ok' if rc == 0 else ' '.join(err[-2:]))) record('h3 compile (sha256 of sources)', ok, ', '.join(detail), t0) # exact75 in the recorded cases (seconds each) e75 = {} for j in jobs['recorded']: if j['program'] != 'exact75.py': continue t0 = time.time() rc, out, err = wrapper(j, build) ok = rc == 0 and out == lines(os.path.join(H3, j['log'])) e75[j['name'][-3:]] = out record('h3 ' + j['name'], ok, 'output %s %s' % ('equal to' if ok else 'DIFFERS from', j['log']), t0) # tailmem5 with a small quotient walk: the lines E for j in jobs['quick']: if j['program'] != 'tailmem5.py': continue t0 = time.time() rc, out, err = wrapper(j, build) rec = lines(os.path.join(H3, j['log'])) pick = lambda ls: [l for l in ls if l.startswith('E ') or l.startswith('# EXACT')] ok = rc == 0 and pick(out) == pick(rec) and len(pick(rec)) > 1 # cross-check with the independent enumeration exact75 (last column optimal_h) key = j['name'][-3:] dev = None if key in e75: E = floats_after('E', out) opt = {int(l.split()[0]): Fr(l.split()[-1]) for l in e75[key] if l and not l.startswith('#')} dev = max(abs(E[n] - opt[n]) / opt[n] for n in opt) if set(E) == set(opt) else None ok = ok and dev is not None and dev < Fr(1, 10 ** 11) record('h3 ' + j['name'], ok, 'lines E %s %s; vs exact75: max rel. dev. %s' % ( 'equal to' if pick(out) == pick(rec) else 'DIFFER from', j['log'], '%.1e' % float(dev) if dev is not None else 'n/a'), t0) # bellman without sweeps: free vector, prefixes, verification pass, bound for n = 22 for j in jobs['quick']: if j['program'] != 'bellman.py': continue t0 = time.time() rc, out, err = wrapper(j, build) rec = lines(os.path.join(H3, j['log'])) same = [l for l in out if l.startswith('# free vector') or l.startswith('# prefixes')] ok = rc == 0 and len(same) == 2 and all(l in rec for l in same) ok = ok and any('violated rows = 0' in l for l in out) and tail_bound(out) is not None dbg = [Fr(l.split(':')[1]) for l in out if l.startswith('# DEBUG bound for n = 22')] st = floats_after('D', lines(os.path.join(H3, j['log'].replace('bellman', 'short_trails')))) rel = abs(dbg[0] - st[22]) / st[22] if dbg and 22 in st else None ok = ok and rel is not None and rel < Fr(1, 10 ** 5) record('h3 ' + j['name'], ok, 'free vector and prefixes as in %s; n = 22: %s vs D 22 %s (rel. %s)' % ( j['log'], '%.9e' % float(dbg[0]) if dbg else '?', '%.9e' % float(st.get(22, 0)), '%.1e' % float(rel) if rel is not None else '?'), t0) # Table tab:tail from the recorded logs, exact rational sums of the printed (upward rounded) decimals t0 = time.time() ex = {(X, d): floats_after('E', lines(os.path.join(H3, 'short_trails_%s_%d.log' % (X, d)))) for X, d in (('B', 1), ('B', 2), ('C', 1), ('C', 2), ('C', 3))} tl, ok = {}, True for X, d in (('B', 1), ('B', 2), ('C', 1), ('C', 2), ('C', 3)): ls = lines(os.path.join(H3, 'bellman_%s_%d.log' % (X, d))) ok = ok and any(re.search(r'violated rows = 0,', l) for l in ls) and ls[-1].endswith('PASS') tl[(X, d)] = tail_bound(ls) tl[('B', 3)] = tl[('B', 1)] # reflection x_2 -> -x_2 up = lambda q: Fr(math.ceil(q * 10 ** 6), 10 ** 6) # round up in the sixth decimal val = {('B', 'exact'): up(2 * sum(ex[('B', 1)].values()) + sum(ex[('B', 2)].values())), ('C', 'exact'): up(sum(sum(ex[('C', d)].values()) for d in (1, 2, 3)))} for k, v in tl.items(): val[k] = up(v) val[('B', 'sum')] = val[('B', 'exact')] + val[('B', 1)] + val[('B', 2)] + val[('B', 3)] val[('C', 'sum')] = val[('C', 'exact')] + val[('C', 1)] + val[('C', 2)] + val[('C', 3)] val[('B', 'K')] = val[('B', 'sum')] val[('C', 'K')] = up(val[('C', 'sum')] / Fr(5, 4)) bad = [k for k in TABLE if val[k] != Fr(TABLE[k])] ok = ok and not bad and max(val[('B', 'K')], val[('C', 'K')]) < 1 # Empirical regression check (3) of Appendix C, independent of the certified bounds. ratios = [] for X, d in (('B', 1), ('B', 2), ('C', 1), ('C', 2), ('C', 3)): D = floats_after('D', lines(os.path.join(H3, 'short_trails_%s_%d.log' % (X, d)))) ratios.append(sum(D.values()) / Fr(TABLE[(X, d)])) ok = ok and min(D) == 22 and max(D) == 108 and ratios[-1] < 1 record('h3 Table tab:tail from logs', ok, 'K_B(1) <= %s, K_C(1) <= %s; lines D 22..108 / entry: %.4f to %.4f%s' % ( float(val[('B', 'K')]), float(val[('C', 'K')]), float(min(ratios)), float(max(ratios)), ('; differs: %s' % bad) if bad else ''), t0) if not full: return for j in jobs['recorded']: if j['program'] == 'exact75.py': continue # already run above t0 = time.time() rc, out, err = wrapper(j, build) rec = lines(os.path.join(H3, j['log'])) if j['program'] == 'tailmem5.py': ok = rc == 0 and err + out == rec detail = 'output %s %s' % ('equal to' if ok else 'DIFFERS from', j['log']) else: # the sweeps run in parallel threads, so the proposed U, and the bound, may differ slightly between runs b, X, d = tail_bound(out), j['args'][0], int(j['args'][1]) same = [l for l in out if l.startswith('# free vector') or l.startswith('# prefixes')] ok = (rc == 0 and b is not None and any('violated rows = 0' in l for l in out) and len(same) == 2 and all(l in rec for l in same) and b <= Fr(TABLE[(X, d)])) detail = 'bound %s (recorded %s, table %s)' % ('%.9e' % float(b) if b else 'none', '%.9e' % float(tail_bound(rec)), TABLE[(X, d)]) record('h3 ' + j['name'], ok, detail, t0) def main(argv): if not __debug__: sys.exit('run_all_checks.py: run without python -O (the checkers rely on assert statements)') parser = argparse.ArgumentParser(description='Run the ancillary AKLT manuscript checks.', allow_abbrev=False) mode = parser.add_mutually_exclusive_group() mode.add_argument('--quick', action='store_true', help='run the quick checks (default)') mode.add_argument('--full', action='store_true', help='run the full checks') parser.add_argument('--only', default='h1,h2,h3', metavar='HYPOTHESES', help='comma-separated list of h1, h2, h3') parser.add_argument('--workdir', metavar='DIR', help='keep build files and check outputs in DIR') parser.add_argument('--parts', type=int, default=4, metavar='N', help='number of processes for full H1 checks') args = parser.parse_args(argv) only = args.only.split(',') if any(name not in ('h1', 'h2', 'h3') for name in only): parser.error('--only requires a nonempty comma-separated list of h1, h2, h3') if args.parts < 1: parser.error('--parts must be a positive integer') RESULTS.clear() keep = args.workdir is not None work = os.path.abspath(args.workdir) if keep else tempfile.mkdtemp(prefix='anc-checks-') global OUT OUT = os.path.join(work, 'out') os.makedirs(OUT, exist_ok=True) print('anc checks (%s), python %s, build directory %s' % ('full' if args.full else 'quick', sys.version.split()[0], work)) t0 = time.time() try: if 'h2' in only: check_h2() if 'h1' in only: check_h1(args.full, args.parts) if 'h3' in only: check_h3(args.full, os.path.join(work, 'build')) finally: if not keep: shutil.rmtree(work, ignore_errors=True) if not RESULTS: print('NO CHECKS RAN', file=sys.stderr) return 1 nfail = sum(1 for r in RESULTS if not r[1]) print('%d checks, %d failed, %.0f s' % (len(RESULTS), nfail, time.time() - t0)) print('ALL CHECKS PASS' if nfail == 0 else 'SOME CHECKS FAILED') return 1 if nfail else 0 if __name__ == '__main__': sys.exit(main(sys.argv[1:]))