Volt
bab4431884
The module had no cell in any gate, and read two ways: its docstring promised
ValueError for 'no duplicate present' while its self-test said it does not
promise detection at all. Measured at 95e4962: every array of length n+1 over
1..n for n=1..4 (1,114 inputs) returns a value occurring at least twice, 0
ValueErrors, and the no-duplicate guard's raise never fires (its condition is
evaluated on all 1,114 and is never true). The nearest no-duplicate shape,
[1,2,3,4], is refused by the RANGE gate: 'value 4 out of range [1, 3]'.
- find_duplicate.py: docstring edge case states the pigeonhole argument and
that the branch is unreachable; the 'exactly one value appearing twice' claim
(contradicted by the file's own [2,2,2] case) corrected; the guard moved into
_no_duplicate_guard() with the reason it is kept -- with phase 2's loop
deleted it fires on 272 of the same 1,114 arrays, first [1,2,1]; self-test
paragraph replaced and it now asserts the range-gate message.
- test_find_duplicate.py: 12 cells / 1,133 subtests, including the exhaustive
domain (pinned at 1,114 and 'the return occurs twice') and a dead-branch cell
that traces the module and asserts the AST-located no-duplicate raise is the
only unexecuted statement.
- Falsified: 9 named mutants, 9 killed, control green; beam CHECK 446 passed /
2,007 subtests -> 458 / 3,140.
217 lines
8.2 KiB
Python
217 lines
8.2 KiB
Python
"""Cells for `find_duplicate` (Q95, volt, 2026-10-28).
|
|
|
|
The module had no cell in any gate, and the record that opened Q95 measured a
|
|
`raise ValueError("no duplicate present in nums")` that no validated input can
|
|
reach. These cells do two things a green gate could not do before: they grade
|
|
the behaviour over the whole validated domain (n = 1..4, every array), and they
|
|
grade the *shape* of the code -- the no-duplicate guard is declared as the
|
|
module's only unexecuted line, so deleting it, or growing new dead code beside
|
|
it, moves a cell.
|
|
|
|
Run from the lane directory: python3 -m pytest -q test_find_duplicate.py
|
|
"""
|
|
import ast
|
|
import itertools
|
|
import sys
|
|
import unittest
|
|
from pathlib import Path
|
|
|
|
import find_duplicate as fd
|
|
|
|
MODULE_PATH = Path(fd.__file__)
|
|
|
|
|
|
def _module_source():
|
|
return MODULE_PATH.read_text(encoding="utf-8")
|
|
|
|
|
|
def _traced_call(func, *args):
|
|
"""Call func(*args), returning (result_or_exception, executed_line_set)."""
|
|
executed = set()
|
|
|
|
def local(frame, event, arg):
|
|
if event == "line" and frame.f_code.co_filename == str(MODULE_PATH):
|
|
executed.add(frame.f_lineno)
|
|
return local
|
|
|
|
previous = sys.gettrace()
|
|
sys.settrace(local)
|
|
try:
|
|
try:
|
|
result = func(*args)
|
|
except Exception as exc: # noqa: BLE001 - the caller grades the class
|
|
result = exc
|
|
finally:
|
|
sys.settrace(previous)
|
|
return result, executed
|
|
|
|
|
|
def _valid_arrays(n):
|
|
return itertools.product(range(1, n + 1), repeat=n + 1)
|
|
|
|
|
|
NO_DUPLICATE_INPUTS = ([], [1], [0, 1], [1, 3], [1, 2, 3, 4], [True, 1],
|
|
[1.0, 1], ["1", 1])
|
|
NO_DUPLICATE_PERMUTATIONS = ([1, 2, 3, 4], [2, 1], [1, 2, 3])
|
|
|
|
|
|
class KnownDuplicates(unittest.TestCase):
|
|
def test_each_documented_case_returns_its_duplicate(self):
|
|
cases = [
|
|
([1, 3, 4, 2, 2], 2),
|
|
([3, 1, 3, 4, 2], 3),
|
|
([1, 1], 1),
|
|
([2, 2, 2], 2),
|
|
([1, 2, 3, 4, 5, 5], 5),
|
|
([2, 4, 3, 2, 1], 2),
|
|
# Phase 1's meeting point is inside the cycle and its value (3)
|
|
# occurs once; only phase 2's entrance (2) is the duplicate. A
|
|
# suite whose cases all have meeting == entrance cannot see phase 2
|
|
# go missing -- this case can.
|
|
([1, 2, 3, 4, 2], 2),
|
|
]
|
|
for nums, expected in cases:
|
|
with self.subTest(nums=nums):
|
|
self.assertEqual(fd.find_duplicate(list(nums)), expected)
|
|
|
|
def test_input_is_not_mutated(self):
|
|
nums = [3, 1, 3, 4, 2]
|
|
snapshot = list(nums)
|
|
fd.find_duplicate(nums)
|
|
self.assertEqual(nums, snapshot)
|
|
|
|
def test_repeated_calls_are_deterministic(self):
|
|
nums = [4, 3, 4, 2, 1]
|
|
reads = {fd.find_duplicate(list(nums)) for _ in range(5)}
|
|
self.assertEqual(reads, {4})
|
|
|
|
|
|
class ValidatedDomain(unittest.TestCase):
|
|
def test_domain_size_is_the_pigeonhole_domain(self):
|
|
# n**(n+1) for n = 1..4 -> 1 + 8 + 81 + 1024
|
|
self.assertEqual(sum(n ** (n + 1) for n in range(1, 5)), 1114)
|
|
|
|
def test_every_validated_array_returns_a_value_occurring_twice(self):
|
|
total = 0
|
|
for n in range(1, 5):
|
|
for array in _valid_arrays(n):
|
|
total += 1
|
|
nums = list(array)
|
|
with self.subTest(nums=nums):
|
|
got = fd.find_duplicate(nums)
|
|
self.assertGreaterEqual(nums.count(got), 2)
|
|
|
|
def test_no_validated_array_raises_anything(self):
|
|
total = raises = 0
|
|
for n in range(1, 5):
|
|
for array in _valid_arrays(n):
|
|
total += 1
|
|
try:
|
|
fd.find_duplicate(list(array))
|
|
except Exception as exc: # noqa: BLE001 - any raise is the finding
|
|
raises += 1
|
|
self.fail("validated input raised %r: %r" % (array, exc))
|
|
self.assertEqual((total, raises), (1114, 0))
|
|
|
|
|
|
class RefusedInputs(unittest.TestCase):
|
|
def test_short_arrays_are_refused_by_the_length_gate(self):
|
|
for bad in ([], [1]):
|
|
with self.subTest(bad=bad):
|
|
with self.assertRaises(ValueError) as ctx:
|
|
fd.find_duplicate(list(bad))
|
|
self.assertIn("at least 2 elements", str(ctx.exception))
|
|
|
|
def test_out_of_range_values_are_refused_by_the_range_gate(self):
|
|
for bad in ([0, 1], [1, 3], [1, 2, 3, 4], [-1, 1]):
|
|
with self.subTest(bad=bad):
|
|
with self.assertRaises(ValueError) as ctx:
|
|
fd.find_duplicate(list(bad))
|
|
self.assertIn("out of range", str(ctx.exception))
|
|
|
|
def test_bools_floats_and_strings_are_not_ints_for_this_contract(self):
|
|
for bad in ([True, 1], [1.0, 1], ["1", 1]):
|
|
with self.subTest(bad=bad):
|
|
with self.assertRaises(ValueError) as ctx:
|
|
fd.find_duplicate(list(bad))
|
|
self.assertIn("out of range", str(ctx.exception))
|
|
|
|
def test_no_duplicate_shape_is_refused_by_the_range_gate_not_by_floyd(self):
|
|
# Q95's reading: a no-duplicate array of length n+1 over 1..n cannot
|
|
# exist, so the nearest no-duplicate shape is one short and dies on the
|
|
# range gate -- never on the "no duplicate present" branch.
|
|
for permutation in NO_DUPLICATE_PERMUTATIONS:
|
|
with self.subTest(permutation=permutation):
|
|
with self.assertRaises(ValueError) as ctx:
|
|
fd.find_duplicate(list(permutation))
|
|
message = str(ctx.exception)
|
|
self.assertIn("out of range", message)
|
|
self.assertNotIn("no duplicate present", message)
|
|
|
|
|
|
class DeadBranchIsDeclared(unittest.TestCase):
|
|
"""The no-duplicate guard is the module's only unexecuted line."""
|
|
|
|
def _guard_raise_lineno(self):
|
|
tree = ast.parse(_module_source())
|
|
for node in ast.walk(tree):
|
|
if isinstance(node, ast.Raise) and isinstance(node.exc, ast.Call):
|
|
for arg in node.exc.args:
|
|
if isinstance(arg, ast.Constant) and isinstance(arg.value, str):
|
|
if "no duplicate present" in arg.value:
|
|
return node.lineno
|
|
self.fail("the no-duplicate raise is gone from find_duplicate.py")
|
|
|
|
def _statement_lines(self):
|
|
tree = ast.parse(_module_source())
|
|
|
|
def is_docstring(node):
|
|
return (
|
|
isinstance(node, ast.Expr)
|
|
and isinstance(node.value, ast.Constant)
|
|
and isinstance(node.value.value, str)
|
|
)
|
|
|
|
lines = set()
|
|
for node in tree.body:
|
|
if isinstance(node, (ast.FunctionDef, ast.AsyncFunctionDef)):
|
|
if node.name == "_self_test":
|
|
continue # its own asserts are not this module's behaviour
|
|
# `def` itself emits no line event, and a docstring is an
|
|
# Expr the interpreter never steps into.
|
|
for inner in ast.walk(node):
|
|
if isinstance(inner, ast.stmt) and not is_docstring(inner):
|
|
lines.add(inner.lineno)
|
|
lines.discard(node.lineno)
|
|
return lines
|
|
|
|
def test_only_the_no_duplicate_raise_is_unexecuted(self):
|
|
executed = set()
|
|
for n in range(1, 5):
|
|
for array in _valid_arrays(n):
|
|
_, seen = _traced_call(fd.find_duplicate, list(array))
|
|
executed |= seen
|
|
for bad in NO_DUPLICATE_INPUTS + NO_DUPLICATE_PERMUTATIONS:
|
|
_, seen = _traced_call(fd.find_duplicate, list(bad))
|
|
executed |= seen
|
|
|
|
declared_dead = self._guard_raise_lineno()
|
|
unexecuted = self._statement_lines() - executed
|
|
self.assertEqual(
|
|
unexecuted, {declared_dead},
|
|
"unexecuted lines (declared dead line %d): %s"
|
|
% (declared_dead, sorted(unexecuted)),
|
|
)
|
|
|
|
def test_the_guard_cannot_fire_on_validated_input(self):
|
|
# Independent of line numbers: no validated call may produce the
|
|
# "no duplicate present" message.
|
|
for n in range(1, 5):
|
|
for array in _valid_arrays(n):
|
|
result, _ = _traced_call(fd.find_duplicate, list(array))
|
|
self.assertNotIsInstance(result, ValueError, array)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
unittest.main()
|