Разделение пополам - это метод, используемый при разработке программного обеспечения для определения наборов изменений, которые приводят к определенному изменению поведения. В основном он используется для поиска патча, в котором была обнаружена ошибка . Другая область применения - поиск патча, который косвенно исправляет ошибку.
Обзор
В 1997 году Брайан Несс и Вьет Нго из Cray Research описали процесс поиска набора изменений, который вводил конкретную регрессию, как «изоляцию изменения источника» . Регрессионное тестирование было выполнено на компиляторах Cray в редакциях, содержащих один или несколько наборов изменений. Версии с известными регрессиями нельзя было проверить, пока разработчики не решат проблему. Изоляция изменения источника сузила причину до одного набора изменений, который затем можно было исключить из редакций, разблокировав их в отношении этой проблемы, в то время как автор изменения работал над исправлением. Несс и Нго описали методы линейного поиска и двоичного поиска для выполнения этой изоляции. [1]
Деление кода пополам имеет целью свести к минимуму усилия по поиску определенного набора изменений. Он использует алгоритм «разделяй и властвуй», который зависит от наличия доступа к истории кода, которая обычно сохраняется с помощью контроля версий в репозитории кода .
Метод деления пополам
Алгоритм деления кода пополам
История кода имеет структуру ориентированного ациклического графа, который можно топологически отсортировать . Это позволяет использовать алгоритм поиска «разделяй и властвуй», который:
- разбивает пространство поиска кандидатских ревизий
- тесты на рассматриваемое поведение
- уменьшает пространство поиска в зависимости от результата теста
- повторно итерация описанных выше действий до диапазона с максимально одним bisectable кандидатов патча остается
Алгоритмическая сложность
Бисекции находятся в LSPACE , имеющие алгоритмическую сложность из с участием обозначает количество ревизий в пространстве поиска и аналогичен бинарному поиску .
Желаемые свойства репозитория
Для разделения кода пополам желательно, чтобы каждая ревизия в пространстве поиска могла быть построена и протестирована независимо.
Монотонность
Чтобы алгоритм деления пополам идентифицировал один набор изменений, который вызвал изменение тестируемого поведения, поведение должно монотонно меняться во всем пространстве поиска. Для логической функции, такой как проверка «годен / не пройден», это означает, что она изменяется только один раз для всех наборов изменений между началом и концом области поиска.
Если в пространстве поиска есть несколько наборов изменений, где тестируемое поведение изменяется между ложным и истинным, то алгоритм деления пополам найдет один из них, но он не обязательно будет основной причиной изменения поведения между началом и концом. пространства поиска. Основной причиной может быть другой набор изменений или комбинация двух или более наборов изменений в пространстве поиска. Чтобы помочь справиться с этой проблемой, автоматизированные инструменты позволяют игнорировать определенные изменения во время поиска пополам.
Поддержка автоматизации
Хотя метод деления пополам можно выполнить вручную, одним из его основных преимуществ является то, что его можно легко автоматизировать. [1] Таким образом, он может вписаться в существующие процессы автоматизации тестирования : сбои в исчерпывающих автоматических регрессионных тестах могут запускать автоматическое деление пополам для локализации сбоев. Ness и Ngo сосредоточили внимание на его потенциале в среде Cray в стиле непрерывной доставки, в которой автоматически изолированный плохой набор изменений можно было автоматически исключать из сборок. [2]
Системы контроля версий Fossil , Git и Mercurial имеют встроенную функциональность для разделения кода пополам. [3] [4] [5] Пользователь может начать сеанс деления пополам с указанным диапазоном ревизий, из которых система управления версиями предлагает ревизию для тестирования, пользователь сообщает системе, была ли ревизия протестирована как «хорошая» или «плохая». ", и процесс повторяется до тех пор, пока не будет определена конкретная" плохая "ревизия. Другие системы контроля версий, такие как Bazaar или Subversion , поддерживают деление пополам через плагины [6] или внешние скрипты. [7]
Phoronix Test Suite может автоматически делать деление пополам, чтобы найти регресс производительности.
Смотрите также
- Дельта-отладка (обобщение поиска минимальной причины ошибки)
- Аннотация § Контроль источника (определение ревизий, которые редактировали строку в файле)
Рекомендации
- ^ а б Несс, Брайан; Нго, Вьетнам (1997). Сдерживание регрессии за счет изоляции изменения источника . Конференция по компьютерному программному обеспечению и приложениям. IEEE. DOI : 10.1109 / CMPSAC.1997.625082 .
- ^ Целлер, Андреас (1999). Вчера моя программа заработала. Сегодня это не так. Почему? . Европейская конференция по программной инженерии. Тулуза, Франция. DOI : 10.1145 / 318774.318946 .
- ^ «Ископаемое: Справка: пополам» . www.fossil-scm.org . Проверено 3 сентября 2020 .
- ^ "git-bisect (1)" . git-scm.com . Проверено 5 августа 2017 .
- ^ "hg" . Selenic.com . Проверено 9 января 2017 .
- ^ «bisect - Найдите ревизию, в которой есть ошибка, с помощью двоичного поиска - документация Bazaar 2.8.0dev1» . Doc.bazaar.canonical.com . Проверено 9 января 2017 .
- ^ "свн-биссект" . Metacpan.org . Проверено 9 января 2017 .