bisecting pytest

pysect.py

# An unpolished script to do pytest-bisection
# By this I don't mean bisecting a repository on commits using pytest,
# but rather bisecting the powerset of tests using pytest.
# In other words:
#   This script takes a list of tests where the last one fails
#   You already ran the test in isolation, but then the test passes
#   Therefore some *other* test causes your test to fail
#   This script finds the necessary preconditions that causes your test to fail

# I said "unpolished". You need to edit pytest_start and pytest_arg to match
# what you want to run with. The script does understand parametrized tests, but
# it doesn't do test classes. The algorithm isn't optimal (on so many levels).
# The output is clumsy.

import math
import xml.etree.ElementTree as ET
from pprint import pprint
from enum import Enum
from dataclasses import dataclass
import random
import sys
import procrunner
from collections import namedtuple
from types import SimpleNamespace


class Relevance(Enum):
    INNOCENT = 1
    INVOLVED = 2
    FAILED = 3
    UNKNOWN = 4


@dataclass(frozen=True)
class Test:
    """Class for keeping track of pytest tests."""

    classname: str
    name: str

    @property
    def pytest_name(self):
        return self.classname.replace(".", "/") + ".py::" + self.name


@dataclass
class Knowledge:
    """A summary of all known things."""

    testruns: set
    tests: dict

    def __init__(self, tests: dict):
        self.tests = tests
        self.testruns = set()

    @property
    def unknowns(self):
        return sum(1 for v in self.tests.values() if v == Relevance.UNKNOWN)

    @property
    def chainlength(self):
        return sum(1 for v in self.tests.values() if v != Relevance.INNOCENT)

    def __str__(self):
        return (
            f"Current test chain length is {self.chainlength} with {self.unknowns} unknowns\n"
            + "\n".join(f"  {t}: {r}" for t, r in self.tests.items())
            + "\n"
        )


def parse_file(filename) -> dict:
    with open(filename) as fh:
        tree = ET.parse(fh)
    tests = {}
    for suite in tree.iter("testsuite"):
        # pprint(suite.attrib)
        for test_record in suite.iter("testcase"):
            test = Test(
                classname=test_record.attrib["classname"],
                name=test_record.attrib["name"],
            )
            success = not bool(list(test_record.iter("failure")))
            if success:
                involvement = Relevance.UNKNOWN
            else:
                involvement = Relevance.FAILED
            tests[test] = involvement
    return tests


def form_new_hypothesis(knowledge: dict) -> list:
    # Step 1: Skip all innocent tests
    hypothesis = [(t, i) for t, i in knowledge.tests.items() if i != Relevance.INNOCENT]
    # Step 2: Remove at least one unknown test
    while True:
        k = random.randrange(len(hypothesis))
        if hypothesis[k][1] == Relevance.UNKNOWN:
            del hypothesis[k]
            break
    # Step 3: Randomly remove n further tests with n=floor(unk/2)
    n = math.floor(sum(1 for h in hypothesis if h[1] == Relevance.UNKNOWN) / 2)
    for _ in range(n):
        while True:
            k = random.randrange(len(hypothesis))
            if hypothesis[k][1] == Relevance.UNKNOWN:
                del hypothesis[k]
                break
    # Step 4: Presto
    new_hypothesis = tuple(h[0] for h in hypothesis)
    if new_hypothesis in knowledge.testruns:
        print("Tried this before :(")
    return new_hypothesis


def update_knowledge(knowledge: dict, update: dict) -> dict:
    # Step 1: Does the update include any unexpected test failures?
    for t, r in update.items():
        if r == Relevance.FAILED and not knowledge.tests[t] == Relevance.FAILED:
            exit(f"Unexpected test failure of {t}")

    # Does the update include all expected test failures?
    failed_run = all(
        t in update and update[t] == Relevance.FAILED
        for t, r in knowledge.tests.items()
        if r == Relevance.FAILED
    )
    if failed_run:
        # Excellent. We can rule out all uninvolved tests
        revised_knowledge = Knowledge(
            tests={
                t: update[t] if t in update else Relevance.INNOCENT
                for t in knowledge.tests
            }
        )
        # TODO: could recycle some result knowledge in 'testruns'
        return revised_knowledge

    # The update did not reproduce all test failures :|

    # Keep a record and check if we exhausted the search space
    knowledge.testruns.add(tuple(update))
    if len(knowledge.testruns) == 2 ** (knowledge.unknowns - 1):
        # All remaining tests are bad!
        for k in knowledge.tests:
            if knowledge.tests[k] == Relevance.UNKNOWN:
                knowledge.tests[k] = Relevance.INVOLVED

    return knowledge


pytest_args = ["--regression"]
pytest_start = ["tests/util/test_options.py"]
pytest_log = """
doc/examples/test_boilerplate.py::test_boilerplate 
tests/test_cpp_components.py::test_cpp_program[tests-algorithms-spot_prediction-tst_reeke_model] 
tests/test_plot_reflections.py::test_run 
tests/test_scitbx.py::test_complex_double_none_comparison 
tests/algorithms/background/test_gmodel.py::test_robust 
tests/algorithms/background/test_modeller.py::TestExact::test_constant3d_modeller 
tests/algorithms/background/test_modeller.py::TestExact::test_linear3d_modeller 
tests/algorithms/background/test_modeller.py::TestPoisson::test_constant3d_modeller 
tests/algorithms/background/test_modeller.py::TestPoisson::test_linear3d_modeller 
tests/algorithms/background/test_outlier_rejector.py::test_truncated 
tests/algorithms/background/test_outlier_rejector.py::test_normal 
tests/algorithms/clustering/test_plots.py::test_plot_uc_histograms 
tests/algorithms/clustering/test_unit_cell.py::test_unit_cell 
tests/algorithms/image/test_centroid.py::Test_Centroid::test_centroid_points2d 
tests/algorithms/image/test_centroid.py::Test_Centroid::test_centroid_image2d 
tests/algorithms/image/test_centroid.py::Test_Centroid::test_centroid_masked_image2d 
tests/algorithms/image/test_centroid.py::Test_Centroid::test_centroid_bias 
tests/algorithms/image/connected_components/test_connected_components.py::Test2d::test_coords_are_valid 
tests/algorithms/image/connected_components/test_connected_components.py::Test2d::test_labels_are_valid 
tests/algorithms/image/connected_components/test_connected_components.py::Test3d::test_values_are_valid 
tests/algorithms/image/fill_holes/test_simple_fill.py::test 
tests/algorithms/image/filter/test_distance.py::test_chebyshev 
tests/algorithms/image/filter/test_index_of_dispersion.py::test 
tests/algorithms/image/filter/test_mean_and_variance.py::test_masked_mean_filter 
tests/algorithms/image/filter/test_mean_and_variance.py::test_masked_mean_and_variance_filter 
tests/algorithms/image/filter/test_median.py::test_masked_filter 
tests/algorithms/image/threshold/test_local.py::Test::test_niblack 
tests/algorithms/image/threshold/test_local.py::Test::test_index_of_dispersion 
tests/algorithms/image/threshold/test_local.py::Test::test_gain 
tests/algorithms/image/threshold/test_local.py::Test::test_dispersion_w_gain 
tests/algorithms/image/threshold/test_local.py::Test::test_dispersion_threshold 
tests/algorithms/image/threshold/test_local.py::Test::test_dispersion_algorithm_symmetry[DispersionThreshold] 
tests/algorithms/image/threshold/test_local.py::Test::test_dispersion_debug_algorithm_symmetry[DispersionThresholdDebug] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[P 1] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[C 1 2 1] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[C 2 2 2] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[I 2 2 2] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[I 4 2 2] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[R 3 2 :H] 
tests/algorithms/indexing/test_assign_indices.py::test_assign_indices[I 4 3 2] 
tests/algorithms/indexing/test_compare_orientation_matrices.py::test_compare_orientation_matrices 
tests/algorithms/indexing/test_index.py::test_index_insulin_multi_sequence[fft3d] 
tests/algorithms/indexing/test_index.py::test_index_insulin_multi_sequence[real_space_grid_search] 
tests/algorithms/indexing/test_index.py::test_index_insulin_force_stills[fft1d] 
tests/algorithms/indexing/test_index.py::test_index_ED_still_low_res_spot_match[stills-True] 
tests/algorithms/indexing/test_index.py::test_index_known_orientation 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 1-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 1 2 1-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[C 1 2 1-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 2 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[C 2 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[F 2 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[I 2 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 4 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[I 4 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 6 2 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[R 3 2 :H-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[P 4 3 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[I 4 3 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell[F 4 3 2-linear-None] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[P 1] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[C 1 2 1] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[C 2 2 2] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[I 2 2 2] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[I 4 2 2] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[R 3 2 :H] 
tests/algorithms/indexing/test_max_cell.py::test_max_cell_low_res_with_high_res_noise[I 4 3 2] 
tests/algorithms/indexing/test_model_evaluation.py::test_ModelRank 
tests/algorithms/indexing/test_model_evaluation.py::test_filter_doubled_cell 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[P 1 2 1] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[P 2 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[F 2 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[P 4 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[P 6 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[P 4 3 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_detect[F 4 3 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[P 1 2 1] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[P 2 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[F 2 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[P 4 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[P 6 2 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[P 4 3 2] 
tests/algorithms/indexing/test_non_primitive_basis.py::test_correct[F 4 3 2] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[P 1] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[C 1 2 1] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[C 2 2 2] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[I 2 2 2] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[I 4 2 2] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[R 3 2 :H] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler[I 4 3 2] 
tests/algorithms/indexing/test_symmetry.py::test_SymmetryHandler_no_match 
tests/algorithms/indexing/test_symmetry.py::test_symmetry_handler_c2_i2[crystal_symmetry1] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry1] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry3] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry5] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry7] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry9] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry11] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry13] 
tests/algorithms/indexing/test_symmetry.py::test_find_matching_symmetry[crystal_symmetry15] 
tests/algorithms/indexing/basis_vector_search/test_combinations.py::test_combinations[P3] 
tests/algorithms/indexing/basis_vector_search/test_combinations.py::test_combinations[R3:h] 
tests/algorithms/indexing/basis_vector_search/test_combinations.py::test_filter_known_symmetry_no_matches 
"""
pytest_start = [l.strip() for l in pytest_log.split("\n")]
pytest_start = [l for l in pytest_start if l]
pytest_start = [l for l in pytest_start if len(l.split("::")) == 2]


def run_pytest(arguments):
    print("Running pytest...")
    result = procrunner.run(["pytest", "--junit-xml", "pytest.xml"] + arguments)
    print(f"Pytest result: {result.returncode}")
    return parse_file("pytest.xml")


knowledge = Knowledge(tests=run_pytest(pytest_args + pytest_start))
print(knowledge)

if not knowledge.unknowns:
    exit("Nothing for me to do")

if not any(t == Relevance.FAILED for t in knowledge.tests.values()):
    exit("No test failed")

while True:
    if not knowledge.unknowns:
        print("Shortest path found:")
        for t in knowledge.tests:
            if knowledge.tests[t] in (Relevance.INVOLVED, Relevance.FAILED):
                print("  " + t.pytest_name)
        exit()

    hypothesis = form_new_hypothesis(knowledge)
    update = run_pytest(pytest_args + [h.pytest_name for h in hypothesis])
    knowledge = update_knowledge(knowledge, update)
    print(knowledge)