import argparse
import cmath
import json
from pathlib import Path
import random
import subprocess
import tempfile
import unittest
ROOT = Path(__file__).resolve().parent.parent
HEADER = "qleisli.phase-dag 1 phase256-dag-v1\n"
IDENTITY = (0, 0, 0)
BINARY = ROOT / "lean-kernel/.lake/build/bin/qleisli-kernel"
def oracle(word):
values = []
for original in [0, 1]:
bit, phase = original, 0
for gate in word:
if gate == "x":
bit ^= 1
elif bit:
phase = (phase + int(gate[1:])) % 256
values.append((bit, phase))
assert values[0][0] != values[1][0]
return values[0][0], values[0][1], values[1][1]
def complex_oracle(word, result):
for original in [0, 1]:
state = [complex(original == 0), complex(original == 1)]
for gate in word:
if gate == "x":
state.reverse()
else:
state[1] *= cmath.exp(2j * cmath.pi * int(gate[1:]) / 256)
expected = [0j, 0j]
expected[original ^ result[0]] = cmath.exp(2j * cmath.pi * result[original + 1] / 256)
assert all(abs(a - b) < 2e-11 for a, b in zip(state, expected))
def definition(body, claim=IDENTITY, shape="Bit"):
return f"{shape} {' '.join(map(str, claim))} {body}"
def artifact(nodes, entry=None):
if entry is None:
entry = len(nodes) - 1
return f"{HEADER}entry {entry}\nnodes {len(nodes)}\n" + "\n".join(nodes) + "\n"
def request(claim=IDENTITY, shape="Bit"):
return f"{HEADER}{shape}\nexpect {' '.join(map(str, claim))}\n"
def no_duplicates(pairs):
result = {}
for key, value in pairs:
if key in result:
raise ValueError(f"duplicate result key {key}")
result[key] = value
return result
class HierarchyTests(unittest.TestCase):
decisions = 0
def setUp(self):
self.temp = tempfile.TemporaryDirectory(prefix="qleisli-hierarchy-")
self.addCleanup(self.temp.cleanup)
self.program = Path(self.temp.name) / "program.qhd"
self.required = Path(self.temp.name) / "required.qhr"
def invoke(self, program, required, accepted, code=None, stage="verification"):
self.program.write_bytes(program.encode() if isinstance(program, str) else program)
self.required.write_bytes(required.encode() if isinstance(required, str) else required)
result = subprocess.run([str(BINARY), "--phase-dag", str(self.program), str(self.required)],
capture_output=True, timeout=5, check=False)
type(self).decisions += 1
self.assertEqual(result.stderr, b"")
self.assertEqual(result.returncode, 0 if accepted else 1)
data = json.loads(result.stdout, object_pairs_hook=no_duplicates)
self.assertEqual(set(data), {"format", "version", "profile", "accepted", "code", "stage", "node", "stats"})
self.assertEqual(data["format"], "qleisli.kernel-result")
self.assertEqual(data["version"], 1)
self.assertEqual(data["profile"], "phase256-dag-v1")
self.assertIs(data["accepted"], accepted)
self.assertEqual(data["stage"], stage)
self.assertEqual(data["code"], code or ("accepted" if accepted else "contract"))
if accepted:
self.assertIsNone(data["node"])
self.assertEqual(set(data["stats"]), {"nodes", "references", "work_units", "depth", "expanded_gates", "dense_dimension"})
self.assertEqual(data["stats"]["dense_dimension"], 0)
else:
self.assertIsNone(data["stats"])
if stage == "verification":
self.assertIs(type(data["node"]), int)
else:
self.assertIsNone(data["node"])
return data
def test_immutable_first_artifacts(self):
root = ROOT / "tests/fixtures/lean_hierarchy"
import hashlib
baseline = json.loads((root / "baseline.json").read_text())
for name, digest in baseline["sources"].items():
self.assertEqual(hashlib.sha256((root / name).read_bytes()).hexdigest(), digest)
data = self.invoke((root / "shared.qhd").read_bytes(), (root / "identity.qhr").read_bytes(), True)
self.assertEqual(data["stats"], dict(nodes=3, references=2, work_units=47,
depth=3, expanded_gates=4096**2, dense_dimension=0))
def test_small_shared_dags_against_expanded_and_complex_oracles(self):
rng = random.Random(0xCD3)
for case in range(100):
with self.subTest(case=case):
nodes, expanded = [], []
for index in range(6):
tag = rng.choice(["leaf"] if index == 0 else ["leaf", "call", "repeat", "sequence"])
if tag == "leaf":
word = [rng.choice(["x", "p0", "p1", "p16", "p32", "p255"]) for _ in range(rng.randrange(5))]
body = f"leaf {len(word)}" + (" " + " ".join(word) if word else "")
elif tag == "call":
child = rng.randrange(index)
word = expanded[child]
body = f"call {child} 1 0 1 0"
elif tag == "repeat":
count, child = rng.randrange(5), rng.randrange(index)
word = expanded[child] * count
body = f"repeat {count} {child}"
else:
left, right = rng.randrange(index), rng.randrange(index)
word = expanded[left] + expanded[right]
body = f"sequence 2 {left} {right}"
self.assertLessEqual(len(word), 4096)
meaning = oracle(word)
complex_oracle(word, meaning)
nodes.append(definition(body, meaning))
expanded.append(word)
root_word = sum(expanded, [])
meaning = oracle(root_word)
complex_oracle(root_word, meaning)
nodes.append(definition("sequence 6 0 1 2 3 4 5", meaning))
result = self.invoke(artifact(nodes), request(meaning), True)
self.assertEqual(result["stats"]["expanded_gates"], len(root_word))
self.assertEqual(result["stats"]["nodes"], 7)
wrong = (meaning[0], (meaning[1] + 1) % 256, meaning[2])
self.invoke(artifact(nodes), request(wrong), False)
changed = nodes[:]
parts = changed[0].split(" ")
parts[2] = str((int(parts[2]) + 1) % 256)
changed[0] = " ".join(parts)
rejected = self.invoke(artifact(changed), request(meaning), False)
self.assertEqual(rejected["node"], 0)
def test_global_phase_and_all_dyadic_angles(self):
for tick in range(256):
word = ["x", f"p{tick}", "x", f"p{tick}"]
meaning = (0, tick, tick)
complex_oracle(word, meaning)
self.invoke(artifact([definition("leaf 4 " + " ".join(word), meaning),
definition("call 0 1 0 1 0", meaning)]), request(meaning), True)
self.invoke(artifact([definition("leaf 4 x p16 x p16", (0, 16, 16))]), request(), False)
def test_body_count_dependency_and_request_mutations(self):
original = [definition("leaf 1 p16", (0, 0, 16)), definition("repeat 2 0", (0, 0, 32))]
self.invoke(artifact(original), request((0, 0, 32)), True)
self.invoke(artifact([original[0], definition("repeat 3 0", (0, 0, 32))]), request((0, 0, 32)), False)
self.invoke(artifact([definition("leaf 1 p17", (0, 0, 16)), original[1]]), request((0, 0, 32)), False)
chain = [original[0], original[1], definition("call 1 1 0 1 0", (0, 0, 32)),
definition("sequence 2 1 2", (0, 0, 64))]
self.invoke(artifact(chain), request((0, 0, 64)), True)
chain[2] = definition("call 0 1 0 1 0", (0, 0, 32))
self.invoke(artifact(chain), request((0, 0, 64)), False)
self.invoke(artifact(original), request((0, 0, 32), "Bits1"), False, "invalid_ir")
def test_closed_power_against_direct_boundary_execution(self):
for word in [["p1"], ["x", "p17"], ["p255", "x", "p16"]]:
leaf = definition(f"leaf {len(word)} " + " ".join(word), oracle(word))
for count in [0, 1, 2, 255, 256, 4095, 4096]:
meaning = oracle(word * count)
nodes = [leaf, definition(f"repeat {count} 0", meaning)]
result = self.invoke(artifact(nodes), request(meaning), True)
self.assertEqual(result["stats"]["expanded_gates"], len(word) * count)
self.assertEqual(result["stats"]["work_units"], 23 + 3 * len(word))
self.invoke(artifact([definition("leaf 0"), definition("repeat 4097 0")]),
request(), False, "limit", "artifact")
def test_zero_repeat_checks_body_and_retains_reachability(self):
self.invoke(artifact([definition("leaf 1 x", (1, 0, 0)), definition("repeat 0 0")]), request(), True)
for nodes in [
[definition("sequence 0"), definition("repeat 0 0")],
[definition("leaf 1 x", (1, 0, 0), "Unit"), definition("repeat 0 0", shape="Unit")],
[definition("repeat 0 0")],
[definition("repeat 0 99")],
]:
shape = "Unit" if nodes[0].startswith("Unit") else "Bit"
self.invoke(artifact(nodes), request(shape=shape), False, "invalid_ir")
self.invoke(artifact([definition("leaf 1 x"), definition("repeat 0 0")]), request(), False)
def test_exact_shape_and_zero_width_owner_ports(self):
for shape in ["Unit", "Bits0", "Bit", "Bits1"]:
nodes = [definition("leaf 0", shape=shape), definition("call 0 1 0 1 0", shape=shape)]
self.invoke(artifact(nodes), request(shape=shape), True)
for call in ["call 0 0 0", "call 0 2 0 0 1 0", "call 0 1 1 1 0", "call 0 1 0 0"]:
self.invoke(artifact([nodes[0], definition(call, shape=shape)]), request(shape=shape), False, "invalid_ir")
for first, second in [("Unit", "Bits0"), ("Bit", "Bits1")]:
nodes = [definition("leaf 0", shape=first), definition("call 0 1 0 1 0", shape=second)]
self.invoke(artifact(nodes), request(shape=second), False, "invalid_ir")
def test_dag_cycles_forward_references_and_unreachable_entries(self):
for nodes in [
[definition("call 0 1 0 1 0")],
[definition("call 1 1 0 1 0"), definition("call 0 1 0 1 0")],
[definition("call 1 1 0 1 0"), definition("leaf 0")],
[definition("leaf 0"), definition("leaf 0")],
]:
self.invoke(artifact(nodes), request(), False, "invalid_ir")
self.invoke(artifact([definition("leaf 0")], entry=1), request(), False, "invalid_ir")
def test_large_shared_work_and_depth_boundary(self):
nodes = [definition("leaf 1 p1", (0, 0, 1))]
for index in range(1, 64):
nodes.append(definition(f"repeat 4096 {index - 1}"))
result = self.invoke(artifact(nodes), request(), True)
self.assertEqual(result["stats"]["nodes"], 64)
self.assertEqual(result["stats"]["references"], 63)
self.assertEqual(result["stats"]["depth"], 64)
self.assertEqual(result["stats"]["expanded_gates"], 4096**63)
self.assertLess(result["stats"]["work_units"], 1400)
nodes.append(definition("repeat 4096 63"))
self.invoke(artifact(nodes), request(), False, "limit")
def test_node_reference_and_primitive_boundaries(self):
nodes = [definition("leaf 0") for _ in range(255)]
nodes.append(definition("sequence 255 " + " ".join(map(str, range(255)))))
self.assertEqual(self.invoke(artifact(nodes), request(), True)["stats"]["nodes"], 256)
self.invoke(artifact(nodes + [definition("call 255 1 0 1 0")]), request(), False, "limit", "artifact")
self.invoke(artifact([definition("leaf 4096 " + " ".join(["x"] * 4096))]), request(), True)
self.invoke(artifact([definition("leaf 4097 " + " ".join(["x"] * 4097))]), request(), False, "limit", "artifact")
nodes = [definition("leaf 0"), definition("sequence 4096 " + " ".join(["0"] * 4096))]
self.invoke(artifact(nodes), request(), True)
nodes.append(definition("call 1 1 0 1 0"))
self.invoke(artifact(nodes), request(), False, "limit")
def test_strict_transport_and_no_schema_shortcuts(self):
original = artifact([definition("leaf 1 p16", (0, 0, 16))])
required = request((0, 0, 16))
for bad in [original.replace("phase256-dag-v1", "qpe-dyadic8-v1"),
original.replace("dag 1", "dag 2"), original.replace("leaf 1 p16", "qft 1"),
original.replace("p16", "p016"), original.replace("p16", "p-1"),
original.replace("p16", "p1.6"), original.replace("Bit", "Bits8"),
original.replace("nodes 1", "nodes 01"), original.replace("nodes 1", "nodes 2"),
original.replace(" ", " "), original.replace("\n", "\r\n"),
original + "\n", original[:-1], original + "\0", original + "\u2028",
b"\xff"]:
self.invoke(bad, required, False, "syntax", "artifact")
self.invoke(original.replace("p16", "p256"), required, False, "limit", "artifact")
self.invoke(original, required.replace("expect", "claim"), False, "syntax", "requirement")
self.invoke(" " * 65537, required, False, "limit", "artifact")
self.invoke(original, " " * 65537, False, "limit", "requirement")
if __name__ == "__main__":
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("binary", nargs="?", type=Path, default=BINARY)
args = parser.parse_args()
BINARY = args.binary.resolve()
result = unittest.TextTestRunner(verbosity=2).run(unittest.defaultTestLoader.loadTestsFromTestCase(HierarchyTests))
print(f"Native DAG decisions: {HierarchyTests.decisions}")
raise SystemExit(not result.wasSuccessful())