Биссекция (программная инженерия) - Bisection (software engineering)

Пополам это метод, используемый в разработка программного обеспечения идентифицировать изменить наборы которые приводят к определенному изменению поведения. В основном он используется для поиска патча, который представил ошибка. Другая область применения - поиск патча, который косвенно исправляет ошибку.

Обзор

Процесс поиска набор изменений который ввел конкретный регресс был описан как "изоляция изменения источника" в 1997 году Брайаном Нессом и Вьет Нго из Cray Research. Регрессионное тестирование был исполнен на Cray's компиляторы в редакциях, содержащих одну или несколько ревизий. Версии с известными регрессиями нельзя было проверить, пока разработчики не решат проблему. Изоляция изменения источника сузила причину до одного набора изменений, который затем можно было исключить из редакций, разблокировав их в отношении этой проблемы, в то время как автор изменения работал над исправлением. Несс и Нго в общих чертах линейный поиск и бинарный поиск методы выполнения этой изоляции.^[1]

Деление кода пополам имеет целью свести к минимуму усилия по поиску определенного набора изменений. разделяй и властвуй алгоритм это зависит от наличия доступа к истории кода, которая обычно сохраняетсяконтроль версий в репозиторий кода.

Метод бисекции

Алгоритм деления кода пополам

История кода имеет структуру ориентированный ациклический граф который может быть топологически отсортированный. Это позволяет использовать алгоритм поиска «разделяй и властвуй», который:

разбивает пространство поиска кандидатских изменений
тесты на рассматриваемое поведение
уменьшает пространство поиска в зависимости от результата теста
повторяет описанные выше шаги до тех пор, пока не будет получен диапазон не более чем с одним делимым пополам кандидат на патч останки

Алгоритмическая сложность

Биссекция находится в LSPACE имея алгоритмическая сложность из ${ Displaystyle О ( журнал N)}$ с ${ displaystyle N}$ обозначает количество ревизий в области поиска и похож на бинарный поиск.

Желаемые свойства репозитория

Для разделения кода пополам желательно, чтобы каждая ревизия в пространстве поиска могла быть построена и протестирована независимо.

Монотонность

Чтобы алгоритм деления пополам идентифицировал один набор изменений, который вызвал изменение тестируемого поведения, поведение должно измениться. монотонно через пространство поиска. Для логической функции, такой как проверка «годен / не годен», это означает, что она изменяется только один раз во всех наборах изменений между началом и концом области поиска.

Если в пространстве поиска есть несколько наборов изменений, где тестируемое поведение меняется с ложного на истинное, то алгоритм деления пополам найдет один из них, но это не обязательно будет основная причина изменения поведения между началом и концом области поиска. Основной причиной может быть другой набор изменений или комбинация двух или более наборов изменений в пространстве поиска. Чтобы помочь справиться с этой проблемой, автоматизированные инструменты позволяют игнорировать определенные изменения во время поиска пополам.

Поддержка автоматизации

Хотя метод деления пополам можно выполнить вручную, одним из его основных преимуществ является то, что его можно легко автоматизировать.^[1] Таким образом, он может вписаться в существующие автоматизация тестирования процессы: сбои в исчерпывающих автоматических регрессионных тестах могут вызвать автоматическое деление пополам для локализации ошибок. Несс и Нго сосредоточились на своем потенциале в Cray's непрерывная доставка -стилевое окружение, в котором автоматически изолированный плохой набор изменений может быть автоматически исключен из сборок.^[2]

Системы контроля версий Ископаемое, Git и Mercurial имеют встроенную функциональность для разделения кода пополам.^[3]^[4]^[5] Пользователь может начать сеанс деления пополам с заданным диапазоном ревизий, из которого система контроля версий предлагает ревизию для тестирования, пользователь сообщает системе, проверена ли ревизия как «хорошая» или «плохая», и процесс повторяется до тех пор, пока не появится конкретный выявлена "плохая" доработка. Другие системы контроля версий, такие как Базар или же Subversion, поддержка деления пополам через плагины^[6] или внешние скрипты.^[7]

Тестовый набор Фороникс может автоматически делать деление пополам, чтобы найти снижение производительности.

Смотрите также

Дельта-отладка (обобщение поиска минимальной причины ошибки)
Аннотация § Контроль версий (определение ревизий, которые редактировали строку в файле)