Можно бесконечно наслаждаться тремя вещами: как горит огонь, как течёт река, и как Клод правит баги в древнем юниксе.
В утилите /bin/fgrep из Unix V7 изначально имеется ошибка. То есть fgrep мог молча не найти то, что следовало найти. Вот как модель Opus 5 нашла и исправила эту ошибку. Задокументируем рассуждения ИИ для истории.
ОЧЕРЕДЬ ДЛЯ FAILURE-ССЫЛОК БЫЛА ЛИНЕЙНОЙ ПО СУТИ, НО БЕЗ ПРОВЕРКИ ГРАНИЦ.
cfail() обходит бор шириной, а в V7 для этого использовалась кольцевая очередь queue[400], расположенная прямо в стеке cfail. Арифметика её циклического перехода имела ДВЕ ВЕТВИ, однако проверка выхода за границы присутствовала только в одной из них. Непроверенной оставалась именно та ветвь, по которой идёт ЦЕПОЧКА: если имеется одно длинное ключевое слово, бор не содержит разветвлений, при каждой постановке в очередь front == rear, управление ни разу не попадает в проверяемую ветвь, и rear просто уходит за пределы массива. На сборке этого исходного кода с AddressSanitizer оказалось достаточно ключевого слова длиной около 450 символов.
Но кольцевая очередь вообще была не нужна. КАЖДОЕ СОСТОЯНИЕ ПОПАДАЕТ В ОЧЕРЕДЬ РОВНО ОДИН РАЗ: состояние является nst ровно одного узла, nst каждый раз получает новое значение ++smax, а корень ничьим nst не является. Следовательно, в очередь никогда не помещается более MAXSIZ-1 элементов, и ЛИНЕЙНАЯ очередь длиной MAXSIZ не может ни зациклиться, ни переполниться. Поэтому вся кольцевая арифметика удалена, вместе с обеими проверками overflo() в cfail; теперь единственным ограничением программы остаётся MAXSIZ.
Не поддавайтесь искушению вовсе отказаться от очереди и просто обходить массив w[] по порядку индексов. cgotofn() выделяет состояния в порядке чтения ключевых слов, а распространение флага out в цикле qloop требует именно обхода в ширину, а не просто порядка «родитель раньше потомка».
ДА И САМА ФУНКЦИЯ FAILURE БЫЛА НЕПРАВИЛЬНОЙ — ИМЕННО ЭТО ПРИВОДИЛО К НЕВЕРНЫМ РЕЗУЛЬТАТАМ.
fail(q) для состояния q, являющегося c-потомком состояния s, должно указывать на первое состояние в ЦЕПОЧКЕ FAILURE состояния s, имеющее переход по символу c. В V7 брали s->fail, проходили по его цепочке альтернативных переходов, а затем СРАЗУ ПЕРЕХОДИЛИ К КОРНЮ. Второго перехода по fail никогда не выполнялось, потому что в боре использовалась обычная функция goto, а не полностью достроенный детерминированный автомат, где одного перехода действительно было бы достаточно. Поэтому все ссылки, требовавшие двух и более переходов по fail, оказывались слишком «высокими», а поскольку признак out распространяется именно вдоль fail, ключевое слово, заканчивавшееся в таком состоянии, никогда не обнаруживалось.
Минимальный пример — ключевые слова bd, debdb, ebb и строка debd. Для состояния deb значение fail(deb) равно eb. У состояния eb нет перехода по d, и V7 сразу возвращается к корню, устанавливая fail(debd) = d. Но пропущенный шаг должен был быть fail(eb) = b; у состояния b переход по d есть, он приводит к состоянию bd, которое соответствует ключевому слову. V7 же не выводил ничего.
После исправления fgrep работает правильно. Исходники доступны здесь: fgrep.c функция cfail()
comments