"""Self-running tests. No pytest, no dependencies: python3 test_vm.py Every counted number on the commentary page is pinned here: 4,095 = 4,095, 4,095 -> 1, 203 of 400, 8,000 differential checks. Nothing here is timed, so the whole file is deterministic. The generator and the two buggy compilers are imported from `demo.py` rather than copied, because a test asserting "203 of 400" has to sweep the *same* 400 programs the page prints. The values themselves are checked against Python's own `eval`, which is an independent oracle. """ import ast import dis import sys from fractions import Fraction from demo import (ENV, compile_onepass_fold, compile_swapped, disasm, evaluate_counted, gen_source, tw_dict, vm_run_counted) from vm import (LOAD, PUSH, SUB, Bin, Num, closure_compile, compile_expr, count_nodes, evaluate, fold_constants, parse, tokenize, vm_run) def run_all(source, env=ENV): """Every back end's answer to one source string.""" tree = parse(source) return (evaluate(tree, env), vm_run(*compile_expr(tree), env), vm_run(*compile_expr(tree, fold=True), env), closure_compile(tree)(env), tw_dict(tree, env)) # --- the front end, inherited from tiny-interpreter and not the subject def test_tokenizer(): assert tokenize("2-x") == [("num", 2), ("-", "-"), ("name", "x"), ("eof", None)] assert tokenize(" 100 / 10 ") == [("num", 100), ("/", "/"), ("num", 10), ("eof", None)] assert tokenize("") == [("eof", None)] try: tokenize("2 $ 3") except SyntaxError as exc: assert "stray" in str(exc) else: raise AssertionError("stray character should not tokenize") def test_parser_shape(): assert repr(parse("2-3-4")) == "((2 - 3) - 4)" assert repr(parse("1+2*3")) == "(1 + (2 * 3))" assert repr(parse("(1+2)*3")) == "((1 + 2) * 3)" assert repr(parse("-x+1")) == "((-x) + 1)" # --- the identity the headline rests on def test_one_instruction_per_node(): for source in ("7", "x", "2-3-4", "-x", "2-x*(3+1)", "(2+3)*(4-1)"): tree = parse(source) code, _, _ = compile_expr(tree) assert len(code) == count_nodes(tree), source def test_identity_over_2000_programs(): worst = 0 for seed in range(2000): tree = parse(gen_source(10, seed=seed, ops="+-*")) code, _, _ = compile_expr(tree) worst = max(worst, abs(len(code) - count_nodes(tree))) assert worst == 0 def test_headline_program(): tree = parse(gen_source(2048)) code, consts, names = compile_expr(tree) assert count_nodes(tree) == 4095 == len(code) assert 2 * 2048 - 1 == 4095 value, steps, depth = vm_run_counted(code, consts, names, ENV) box = [0] walked = evaluate_counted(tree, ENV, box) assert steps == len(code) == box[0] == 4095 assert depth == 1 # one value left: the answer assert value == walked == 140 assert set(names) == {"x", "y", "z"} and len(consts) == 9 # --- four back ends, one tree def test_back_ends_agree_with_python(): cases = {"2-3-4": -5, "1+2*3": 7, "(1+2)*3": 9, "8-(0-3)": 11, "x-y-z": -9, "-x+1": -2, "2-x*(3+1)": -10, "100/10/2": 5.0} for source, want in cases.items(): assert eval(source, {}, ENV) == want, source assert run_all(source) == (want,) * 5, source def test_8000_differential_checks(): disagreements = 0 for seed in range(2000): tree = parse(gen_source(10, seed=seed, ops="+-*")) want = evaluate(tree, ENV) for got in (vm_run(*compile_expr(tree), ENV), vm_run(*compile_expr(tree, fold=True), ENV), closure_compile(tree)(ENV), tw_dict(tree, ENV)): disagreements += got != want assert disagreements == 0 def test_compile_once_run_many(): """One compiled program, three environments -- the reason variables are in the language at all.""" code, consts, names = compile_expr(parse("x*y-z")) for env in ({"x": 3, "y": 5, "z": 7}, {"x": 0, "y": 9, "z": 1}, {"x": -2, "y": -2, "z": -4}): assert vm_run(code, consts, names, env) == env["x"] * env["y"] - env["z"] # --- the constant pool def test_constant_pool_interns_by_type(): code, consts, _ = compile_expr(parse("2+2+2")) assert len(code) == 5 and consts == [2] # one PUSH target, reused tree = Bin("+", Num(1), Num(Fraction(1))) _, consts, _ = compile_expr(tree) assert consts == [1, Fraction(1)] and len(consts) == 2 # --- folding is the only thing that changes the count def test_folding_collapses_a_constant_program(): tree = parse(gen_source(2048, const_only=True)) plain, _, _ = compile_expr(tree) code, consts, names = compile_expr(tree, fold=True) assert len(plain) == 4095 and count_nodes(tree) == 4095 assert len(code) == 1 and count_nodes(fold_constants(tree)) == 1 assert disasm(code, consts, names) == " 0 PUSH -533" assert vm_run(code, consts, names, ENV) == evaluate(tree, ENV) == -533 assert 4095 - 1 == 4094 def test_folding_never_grows_the_program_or_moves_a_value(): for seed in range(200): tree = parse(gen_source(12, seed=seed, ops="+-*")) plain, _, _ = compile_expr(tree) folded, consts, names = compile_expr(tree, fold=True) assert len(folded) <= len(plain) assert len(folded) == count_nodes(fold_constants(tree)) assert vm_run(folded, consts, names, ENV) == evaluate(tree, ENV) def test_folding_leaves_division_by_zero_alone(): """Folding `1/0` would move a run-time error to compile time, and this toy has no way to report one.""" tree = parse("1/0") assert len(compile_expr(tree, fold=True)[0]) == 3 assert len(compile_expr(parse("1/0+2"), fold=True)[0]) == 5 # --- THE LINE: emit(left) before emit(right) def test_swapping_the_operands_keeps_the_shape_and_breaks_the_answer(): for source, correct, swapped in (("2-3-4", -5, 3), ("8-(0-3)", 11, -5), ("x-y-z", -9, 5)): tree = parse(source) good, bad = compile_expr(tree), compile_swapped(tree) assert vm_run(*good, ENV) == correct assert vm_run(*bad, ENV) == swapped assert len(good[0]) == len(bad[0]) assert sorted(op for op, _ in good[0]) == sorted(op for op, _ in bad[0]) tree = parse(gen_source(2048)) assert vm_run(*compile_expr(tree), ENV) == 140 assert vm_run(*compile_swapped(tree), ENV) == 216 assert len(compile_expr(tree)[0]) == len(compile_swapped(tree)[0]) == 4095 def test_one_pass_folder_is_silently_wrong_on_half_the_sweep(): wrong_two = wrong_one = crashed = 0 for seed in range(400): tree = parse(gen_source(12, seed=seed, ops="+-*")) want = evaluate(tree, ENV) if vm_run(*compile_expr(tree, fold=True), ENV) != want: wrong_two += 1 try: if vm_run(*compile_onepass_fold(tree), ENV) != want: wrong_one += 1 except Exception: crashed += 1 assert (wrong_two, wrong_one, crashed) == (0, 203, 0) def test_the_three_instruction_witness(): tree = parse("2-x") two = compile_expr(tree, fold=True) one = compile_onepass_fold(tree) assert [op for op, _ in two[0]] == [PUSH, LOAD, SUB] assert [op for op, _ in one[0]] == [LOAD, PUSH, SUB] assert len(two[0]) == len(one[0]) == 3 assert vm_run(*two, ENV) == evaluate(tree, ENV) == -1 assert vm_run(*one, ENV) == 1 # --- the boundary rows, as counts rather than timings def test_operand_type_never_changes_the_instruction_count(): from demo import convert_tree base = parse(gen_source(2048)) for convert in (lambda v: v, lambda v: v + 10 ** 100, Fraction): code, _, _ = compile_expr(convert_tree(base, convert)) assert len(code) == 4095 def test_the_smallest_program_is_three_instructions(): tree = parse(gen_source(2)) code, _, _ = compile_expr(tree) assert len(code) == count_nodes(tree) == 3 def test_cpython_compiles_the_same_expression_to_4097(): import re source = re.sub(r"\d+", lambda m: "xyz"[int(m.group()) % 3], gen_source(2048)) tree = parse(source) codeobj = compile(source, "", "eval") assert len(compile_expr(tree)[0]) == 4095 assert len(list(dis.get_instructions(codeobj))) == 4097 assert evaluate(tree, ENV) == eval(codeobj, {"__builtins__": {}}, dict(ENV)) == 178 def main(): tests = [v for k, v in sorted(globals().items()) if k.startswith("test_")] for test in tests: test() source = ast.parse(open(__file__).read()) asserts = sum(isinstance(n, ast.Assert) for n in ast.walk(source)) print(f"ok: {len(tests)} tests, {asserts} assertions") return 0 if __name__ == "__main__": sys.exit(main())