Score a Test Suite with Mutation Testing

In Catch the Broken Versions, someone wrote three broken versions of page_count by hand, and your check had to return False for each one. A mutation-testing tool such as mutmut makes the broken versions for you. It changes one small piece of your code, such as >= to >, and runs your tests again. Each changed version is a mutant. If any test fails, the tests kill the mutant. If they all pass, it survives, and you may be missing a test. The mutation score is the percentage of mutants killed.

The grader cannot run mutmut, so here you write a small mutation scorer yourself.

Change code through its syntax tree

Python's ast module parses source code into a tree of nodes, one per piece of syntax, such as a comparison or an addition. This tree is the AST, short for abstract syntax tree. You can change a node and compile the tree back into a function:

import ast
from typing import Any

tree = ast.parse("def is_adult(age: int) -> bool:\n    return age >= 18\n")
for node in ast.walk(tree):
    if isinstance(node, ast.Compare):
        node.ops = [ast.Gt()]  # >= becomes >

namespace: dict[str, Any] = {}
exec(compile(tree, "<mutant>", "exec"), namespace)
print(namespace["is_adult"](18))  # False

ast.walk visits every node in the tree. A test that expects is_adult(18) == True kills this mutant. Each node also records where it starts. lineno is its line, counting from 1, and col_offset is its column, counting from 0.

What to write

def targets(tree: ast.Module, operator: str) -> list[Target]
def mutate(node: Target, operator: str) -> None
def kills(mutant: ast.Module, entrypoint: str, cases: Sequence[Case]) -> bool
def score_suite(*, source, entrypoint, cases, operators) -> Score

An operator names one kind of change. targets returns every node in the module that the operator can change, including nodes inside function bodies. Sort them by (lineno, col_offset, end_lineno, end_col_offset), using 0 for a missing end position. ast.walk has its own visiting order, so always sort.

mutate(node, operator) makes that change to one node, in place.

• A chained comparison such as 0 < x < 10 has two comparison operators, so it is not a target.
• -3 is a unary minus applied to the constant 3. Mutating the constant gives -4.
• return None is a target, because its value is the constant None. A bare return is not a target.
• An operator name that is not in the table has no targets.

Run each mutant

kills(mutant, entrypoint, cases) compiles the tree, runs it with exec in a new namespace dictionary, and looks up entrypoint there. If any of those steps raises an Exception, return True.

Then call entrypoint(**case["kwargs"]) for each case, in order. Return True at the first call that raises an Exception or returns a value other than case["expected"]. Return False if every case passes. With no cases, a mutant survives unless its setup raises. Catch Exception only, so SystemExit and other BaseException subclasses still propagate.

All the cases for one mutant share its namespace, and each mutant gets a new one. Pass the case arguments as they are, without copying them.

Build the score

In score_suite, parse source with ast.parse. Invalid source raises there, before any mutant exists. Then, for each operator in the order given, make one mutant per target. Start each mutant from its own copy.deepcopy of the original tree. Change only the selected node, and call ast.fix_missing_locations on the copy before you pass it to kills.

Count every mutant. A repeated operator makes its mutants again, and a mutant that behaves like the original still counts. Don't run the original first. The tests assume it passes its cases.

Return {"total": int, "killed": int, "score_percent": int, "survivors": list[str]}.

• score_percent is killed * 100 // total, rounded down. If total is 0, it is 100.
• Label each survivor f"{operator}@{lineno}:{col}", from the target's position before you mutated it. Columns are UTF-8 byte offsets, as the AST reports them.
• Sort survivors by the tuple (lineno, col, operator), then format them. Sorting the strings would put line 10 before line 9. Keep duplicates.

Read the example

The first test uses comparison, constant and return_none on this function:

def grade(score: int) -> str:
    if score >= 90:
        return "A"
    if score >= 80:
        return "B"
    return "F"

That makes seven mutants, from two comparisons, two integer constants and three returns. Cases for scores 95 and 50 kill two of them, the return_none mutants of "A" and "F". The score is 2 * 100 // 7 == 28. The cases never reach return "B", and they never test a boundary. Add cases at 90, 89, 80 and 79, and all seven mutants die.

Line coverage tells you which lines ran. Mutation testing tells you whether your tests fail when those lines change. A survivor can also be an equivalent mutant, one that behaves exactly like the original, such as return None turned into a bare return. No test can kill it, so read each survivor before you write a test for it.