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