Shrinking

Случайный 1000-элементный массив, ломающий утверждение, говорит вам что что-то не так, но чтение его почти ничего не говорит о почему. Shrinking превращает этот массив в нечто вроде [0, 1] — минимальный вход, который раннер смог найти и который всё ещё ломает property — поиском, а не осмотром.

Integrated shrinking

С версии 2.0 shrinking встроен в генерацию, а не является отдельным шагом. Каждый вызов ArbitraryInterface::generate(Random) возвращает Shrinkable: сгенерированное значение плюс ленивое дерево меньших кандидатов, прикреплённое прямо в момент генерации. Нет отдельного метода shrink(mixed $value), которому пришлось бы реверс-инжинирить меньшее значение из голого скаляра — дерево уже существует, построенное тем же кодом, что произвёл значение.

Именно это заставляет корректно shrink'аться трансформированные генераторы. Gen::map() и Gen::flatMap() не нуждаются в собственной shrink-логике: они несут Shrinkable исходного значения и заново применяют трансформацию к каждому кандидату по мере shrink'а источника. Генератор Gen::map($int, fn($n) => "user-$n") shrink'ается, shrink'ая нижележащий int и переформатируя строку — никогда не угадывая, как уменьшить произвольную строку.

Shrink-цикл

При падении раннер выполняет жадный спуск: пробует первого child-кандидата в дереве текущего узла; если он всё ещё падает — переходит к нему и повторяет с его детей; если ни один из детей узла не падает, этот узел и есть ответ. Это эвристика, не исчерпывающий поиск — результат best-effort минимален, а не доказуемо минимален. (Одно исключение: для монотонных предикатов shrink-лестница целочисленных генераторов — точный бинарный поиск, там результат действительно минимален.)

Property falsified after 246 successful run(s); seed=7382910
  Original: maxAttempts=17, baseSeconds=91, cap=847, attempts=23
  Shrunk:   maxAttempts=1, baseSeconds=848, cap=847, attempts=1 (12 shrink step(s), 41 trial(s))

trial(s) считает каждого испробованного кандидата, принятого и отклонённого; shrink step(s) считает только принятые спуски. Спуск можно ограничить через #[Property(maxShrinks: 25)] или полностью отключить через maxShrinks: 0, получив исходный контрпример без изменений — см. Ограничение shrink-работы.

Инвариант терминации

Shrink-дерево полезно, только если гарантирован конец обхода. Две правила, обязательные для каждого встроенного генератора (и требуемые от любого своего ArbitraryInterface), дают эту гарантию:

1. Каждая ветка конечна. Ни один генератор не отдаёт бесконечный поток всё уменьшающихся кандидатов.
2. Ни один кандидат не равен родителю. Каждый builder строго уменьшает некоторую конкретную меру на каждом шаге — расстояние до целевого значения, длину строки, размер списка, индекс в упорядоченном домене. Интерцептор добавляет защитную проверку сверху: кандидат, чьё значение равно текущему (возможно, если функция map() не инъективна), пропускается, даже если дерево технически его предложило.

Вместе это означает, что спуск всегда достигает неподвижной точки за конечное число шагов, независимо от глубины или ширины дерева.

Построение своего дерева

Shrinkable даёт три конструктора: leaf($value) для значения без меньших кандидатов, of($value, $closure) для значения с лениво вычисляемым списком кандидатов, и map($fn) для трансформации всего существующего дерева. Построение дерева с нуля — включая точную дисциплину, которую требует инвариант терминации — разобрано на примере в Свой arbitrary.