git-bisect-lk2009

Регрессии: большая проблема

Регрессии — большая проблема в программной индустрии. Но сложно привести конкретные цифры, подтверждающие это утверждение.

Есть некоторые цифры о багах в целом, например, исследование NIST 2002 года [1], которое гласило:

И затем:

В конечном итоге вывод начинался с:

Существуют и другие оценки, утверждающие, что 80% затрат, связанных с программным обеспечением, составляют затраты на обслуживание [2].

Однако, согласно Википедии [3]:

Но мы можем предположить, что усовершенствование существующего программного обеспечения очень дорого, потому что нужно следить за регрессиями. По крайней мере, это сделало бы вышеупомянутые исследования согласованными друг с другом.

Конечно, какое-то программное обеспечение разрабатывается, затем используется некоторое время без существенного улучшения, и, наконец, выбрасывается. В этом случае регрессии могут не быть большой проблемой. С другой стороны, существует множество крупного программного обеспечения, которое постоянно развивается и поддерживается в течение многих лет или даже десятилетий множеством людей. И поскольку часто многие люди зависят (иногда критически) от такого программного обеспечения, регрессии представляют собой действительно большую проблему.

Одним из таких программных обеспечений является ядро Linux. И если мы посмотрим на ядро Linux, мы увидим, что много времени и усилий тратится на борьбу с регрессиями. Цикл выпуска начинается с 2-недельного периода слияния. Затем помечается первая версия кандидата выпуска (rc). После этого появляется ещё около 7 или 8 версий rc с примерно одной неделей между каждой из них, прежде чем выйдет окончательный релиз.

Время между первым релизом rc и окончательным релизом должно использоваться для тестирования версий rc и борьбы с ошибками, особенно с регрессиями. И это время составляет более 80% времени цикла выпуска. Но это ещё не конец борьбы, поскольку, конечно, она продолжается и после выпуска.

И вот что говорит Инго Молнар (известный разработчик ядра Linux) о своём использовании "git bisect":

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

Другие инструменты для борьбы с регрессиями

Итак, какие инструменты используются для борьбы с регрессиями? Они почти такие же, как и те, которые используются для борьбы с обычными ошибками. Единственными специфическими инструментами являются наборы тестов и инструменты, аналогичные "git bisect".

Наборы тестов очень хороши. Но когда они используются сами по себе, предполагается, что все тесты проверяются после каждого коммита. Это означает, что они не очень эффективны, потому что многие тесты выполняются без интересного результата, и они страдают от комбинаторного взрыва.

На самом деле проблема в том, что большое программное обеспечение часто имеет много различных параметров конфигурации, и каждый тестовый случай должен пройти для каждой конфигурации после каждого коммита. Итак, если у вас для каждого выпуска: N конфигураций, M коммитов и T тестовых случаев, вы должны выполнить:

N * M * T tests

где N, M и T — все увеличиваются с ростом размера вашего программного обеспечения.

Таким образом, очень скоро не будет возможности полностью протестировать всё.

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

Начало бисекции

Первая подкоманда «git bisect», которую нужно использовать, это «git bisect start», для начала поиска. Затем нужно установить границы, чтобы ограничить пространство коммитов. Обычно это делается путём указания одного «плохого» и как минимум одного «хорошего» коммита. Их можно передать в начальном вызове «git bisect start» так:

$ git bisect start [BAD [GOOD...]]

или их можно установить, используя:

$ git bisect bad [COMMIT]

и:

$ git bisect good [COMMIT...]

где BAD, GOOD и COMMIT — все имена, которые могут быть разрешены до коммита.

Затем «git bisect» переключится на выбранный коммит и попросит пользователя протестировать его, примерно так:

$ git bisect start v2.6.27 v2.6.25
Bisecting: 10928 revisions left to test after this (roughly 14 steps)
[2ec65f8b89ea003c27ff7723525a2ee335a2b393] x86: clean up using max_low_pfn on 32-bit

Обратите внимание, что пример, который мы будем использовать, является на самом деле учебным примером. Мы будем искать первый коммит, который имеет версию типа «2.6.26-что-то», то есть коммит, который содержит строку «SUBLEVEL = 26» в файле Makefile верхнего уровня. Это учебный пример, потому что есть лучшие способы найти этот коммит с помощью Git, чем использование «git bisect» (например, «git blame» или «git log -S<строка>»).

Ручное управление бисекцией

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

Если пользователь управляет им, то на каждом шаге поиска пользователь должен протестировать текущий коммит и указать, является ли он «хорошим» или «плохим», используя команды «git bisect good» или «git bisect bad» соответственно, которые были описаны выше. Например:

$ git bisect bad
Bisecting: 5480 revisions left to test after this (roughly 13 steps)
[66c0b394f08fd89236515c1c84485ea712a157be] KVM: kill file->f_count abuse in kvm

И после нескольких таких шагов «git bisect» в конечном итоге найдёт первый плохой коммит:

$ git bisect bad
2ddcca36c8bcfa251724fe342c8327451988be0d is the first bad commit
commit 2ddcca36c8bcfa251724fe342c8327451988be0d
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sat May 3 11:59:44 2008 -0700

    Linux 2.6.26-rc1

:100644 100644 5cf82581... 4492984e... M      Makefile

На этом этапе мы можем посмотреть, что делает коммит, переключиться на него (если он ещё не переключён) или подправить его, например:

$ git show HEAD
commit 2ddcca36c8bcfa251724fe342c8327451988be0d
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sat May 3 11:59:44 2008 -0700

    Linux 2.6.26-rc1

diff --git a/Makefile b/Makefile
index 5cf8258..4492984 100644
--- a/Makefile
+++ b/Makefile
@@ -1,7 +1,7 @@
 VERSION = 2
 PATCHLEVEL = 6
-SUBLEVEL = 25
-EXTRAVERSION =
+SUBLEVEL = 26
+EXTRAVERSION = -rc1
 NAME = Funky Weasel is Jiggy wit it

 # *DOCUMENTATION*

И после завершения мы можем использовать «git bisect reset», чтобы вернуться к ветке, в которой мы находились до начала бисекции:

$ git bisect reset
Checking out files: 100% (21549/21549), done.
Previous HEAD position was 2ddcca3... Linux 2.6.26-rc1
Switched to branch 'master'

Автоматическое управление бисекцией

Другой способ управления процессом бисекции — указать «git bisect», запустить скрипт или команду на каждом шаге бисекции, чтобы узнать, является ли текущий коммит «хорошим» или «плохим». Для этого используется команда «git bisect run». Например:

$ git bisect start v2.6.27 v2.6.25
Bisecting: 10928 revisions left to test after this (roughly 14 steps)
[2ec65f8b89ea003c27ff7723525a2ee335a2b393] x86: clean up using max_low_pfn on 32-bit
$
$ git bisect run grep '^SUBLEVEL = 25' Makefile
running grep ^SUBLEVEL = 25 Makefile
Bisecting: 5480 revisions left to test after this (roughly 13 steps)
[66c0b394f08fd89236515c1c84485ea712a157be] KVM: kill file->f_count abuse in kvm
running grep ^SUBLEVEL = 25 Makefile
SUBLEVEL = 25
Bisecting: 2740 revisions left to test after this (roughly 12 steps)
[671294719628f1671faefd4882764886f8ad08cb] V4L/DVB(7879): Adding cx18 Support for mxl5005s
...
...
running grep ^SUBLEVEL = 25 Makefile
Bisecting: 0 revisions left to test after this (roughly 0 steps)
[2ddcca36c8bcfa251724fe342c8327451988be0d] Linux 2.6.26-rc1
running grep ^SUBLEVEL = 25 Makefile
2ddcca36c8bcfa251724fe342c8327451988be0d is the first bad commit
commit 2ddcca36c8bcfa251724fe342c8327451988be0d
Author: Linus Torvalds <torvalds@linux-foundation.org>
Date:   Sat May 3 11:59:44 2008 -0700

    Linux 2.6.26-rc1

:100644 100644 5cf82581... 4492984e... M      Makefile
bisect run success

В этом примере мы передали «grep ^SUBLEVEL = 25 Makefile» в качестве параметра для «git bisect run». Это означает, что на каждом шаге будет запущена команда grep, которую мы передали. И если она завершится с кодом 0 (что означает успех), то git bisect пометит текущее состояние как «хорошее». Если она завершится с кодом 1 (или любым кодом между 1 и 127 включительно, за исключением специального кода 125), то текущее состояние будет помечено как «плохое».

Код выхода между 128 и 255 является специальным для «git bisect run». Он заставляет немедленно остановить процесс бисекции. Это полезно, например, если передаваемая команда занимает слишком много времени для завершения, потому что вы можете её убить с помощью сигнала, и это остановит процесс бисекции.

Это также может быть полезно в скриптах, переданных в «git bisect run», чтобы «exit 255», если обнаружено какое-либо очень необычное состояние.

Избегание нетестируемых коммитов

Иногда бывает, что текущее состояние не может быть протестировано, например, если оно не компилируется, потому что в то время была ошибка, мешающая этому. Для этого предназначен специальный код выхода 125. Он сообщает «git bisect run», что текущий коммит следует отметить как нетестируемый, и что следует выбрать и проверить другой.

Если процесс бисекции управляется вручную, вы можете использовать «git bisect skip», чтобы сделать то же самое. (На самом деле специальный код выхода 125 заставляет «git bisect run» использовать «git bisect skip» в фоновом режиме.)

Или, если вы хотите больше контроля, вы можете проверить текущее состояние, например, используя «git bisect visualize». Он запустит gitk (или «git log», если переменная среды DISPLAY не установлена), чтобы помочь вам найти лучшую точку бисекции.

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

Поэтому, если вы использовали «git bisect skip» (или скрипт выполнения завершился со специальным кодом 125), вы могли получить результат такого типа:

There are only 'skip'ped commits left to test.
The first bad commit could be any of:
15722f2fa328eaba97022898a305ffc8172db6b1
78e86cf3e850bd755bb71831f42e200626fbd1e0
e15b73ad3db9b48d7d1ade32f8cd23a751fe0ace
070eab2303024706f2924822bfec8b9847e4ac1b
We cannot bisect more!

Сохранение журнала и его воспроизведение

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

$ git bisect log > bisect_log.txt

И его можно воспроизвести, используя:

$ git bisect replay bisect_log.txt

Использование наборов тестов и git bisect вместе

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

Вы можете сосредоточить свои усилия на проверке в нескольких точках (например, rc и beta релизах), что все тестовые случаи T проходят для всех N конфигураций. И когда некоторые тесты не проходят, вы можете использовать «git bisect» (или лучше «git bisect run»). Таким образом, вы должны выполнить примерно:

c * N * T + b * M * log2(M) tests

где c — количество раундов тестирования (поэтому небольшая константа), а b — отношение ошибок к коммитам (надеюсь, тоже небольшая константа).

Таким образом, это намного лучше, так как это O(N * T) по сравнению с O(N * T * M), если вы будете тестировать все после каждого коммита.

Это означает, что наборы тестов хорошо предотвращают коммит некоторых ошибок, и они также довольно хорошо указывают на то, что у вас есть некоторые ошибки. Но они не так хорошо показывают, где были введены некоторые ошибки. Для того, чтобы эффективно сообщить об этом, необходим git bisect.

Другое приятное свойство наборов тестов заключается в том, что когда у вас есть набор тестов, вы уже знаете, как тестировать неправильное поведение. Поэтому вы можете использовать эти знания для создания нового тестового случая для «git bisect», когда, по всей видимости, произошла регрессия. Таким образом, бисекция ошибки и ее исправление будет проще. А затем вы можете добавить созданный вами тестовый случай в свой набор тестов.

Итак, если вы знаете, как создавать тестовые случаи и как бисектировать, вы будете подвержены положительной обратной связи:

больше тестов ⇒ проще создавать тесты ⇒ проще бисектировать ⇒ больше тестов

Таким образом, наборы тестов и «git bisect» — это взаимодополняющие инструменты, которые очень мощные и эффективные при совместном использовании.

Бисекция сбоев сборки

Вы можете очень легко автоматически бисектировать сломанные сборки, используя что-то вроде:

$ git bisect start BAD GOOD
$ git bisect run make

Передача sh -c "некоторые команды" в "git bisect run"

Например:

$ git bisect run sh -c "make || exit 125; ./my_app | grep 'good output'"

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

Поиск регрессий производительности

Вот пример скрипта, немного изменённого из реального скрипта, используемого Junio Hamano [4].

Этот скрипт можно передать в «git bisect run», чтобы найти коммит, который ввёл регрессию производительности:

#!/bin/sh

# Build errors are not what I am interested in.
make my_app || exit 255

# We are checking if it stops in a reasonable amount of time, so
# let it run in the background...

./my_app >log 2>&1 &

# ... and grab its process ID.
pid=$!

# ... and then wait for sufficiently long.
sleep $NORMAL_TIME

# ... and then see if the process is still there.
if kill -0 $pid
then
        # It is still running -- that is bad.
        kill $pid; sleep 1; kill $pid;
        exit 1
else
        # It has already finished (the $pid process was no more),
        # and we are happy.
        exit 0
fi

Следование общим рекомендациям по наилучшей практике

Очевидно, что неплохо не создавать коммиты с изменениями, которые сознательно ломают вещи, даже если некоторые другие коммиты позже исправят поломки.

Также неплохо, при использовании любого VCS, иметь только одно небольшое логическое изменение в каждом коммите.

Чем меньше изменения в вашем коммите, тем эффективнее будет «git bisect». И вам, вероятно, потребуется «git bisect» меньше в первую очередь, так как небольшие изменения легче проверить, даже если они проверяются только автором коммита.

Ещё одна хорошая идея — использовать хорошие сообщения коммитов. Они могут быть очень полезны для понимания того, почему были внесены некоторые изменения.

Эти общие рекомендации по наилучшей практике очень полезны, если вы часто бисектируете.

Избегание проблемных слияний

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

Например, одна ветка может изменить семантику функции, а другая ветка добавит больше вызовов этой функции.

Это усугубляется, если для разрешения конфликтов нужно исправлять множество файлов. Именно поэтому такие слияния называются «злыми слияниями». Они могут очень затруднить отслеживание регрессий. Это может даже вводить в заблуждение, зная первый плохой коммит, если он случайно оказывается таким слиянием, потому что люди могут подумать, что ошибка происходит из-за плохого разрешения конфликтов, когда она происходит из-за семантического изменения в одной ветке.

В любом случае, «git rebase» можно использовать для линеаризации истории. Это можно использовать как для избегания слияния в первую очередь, так и для бисекции линейной истории вместо нелинейной, поскольку это должно дать больше информации в случае семантического изменения в одной ветке.

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

А тестирование можно проводить чаще в специальных интеграционных ветках, таких как linux-next для ядра Linux.

Адаптация вашего рабочего процесса

Специальный рабочий процесс для обработки регрессий может дать отличные результаты.

Вот пример рабочего процесса, используемого Andreas Ericsson:

И вот что сказал Andreas об этом рабочем процессе [5]:

Очевидно, что этот рабочий процесс использует положительную обратную связь между наборами тестов и «git bisect». Фактически, он делает его стандартной процедурой для работы с регрессиями.

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

Таким образом, хороший рабочий процесс должен быть разработан вокруг вышеперечисленных пунктов. То есть, упростить бисекцию, сделать её более полезной и стандартной.

Включение людей QA и, если возможно, конечных пользователей

Одно хорошее свойство «git bisect» заключается в том, что это не только инструмент разработчика. Его эффективно могут использовать специалисты QA или даже конечные пользователи (если у них есть доступ к исходному коду или если они могут получить доступ ко всем сборкам).

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

Например, Дэвид Миллер написал [6]:

Это означает, что часто «дешевле», если это могут сделать специалисты QA или конечные пользователи.

Интересно также, что конечные пользователи, которые сообщают об ошибках (или специалисты QA, которые воспроизвели ошибку), имеют доступ к среде, где происходит ошибка. Поэтому они часто легче воспроизводят регрессию. И если они могут бисектировать, то будет получена больше информации об окружающей среде, где происходит ошибка, что означает, что будет легче понять и исправить ошибку.

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

Использование сложных скриптов

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

Вот что говорит об этом Инго Молнар [7]:

Сочетание наборов тестов, git bisect и других систем вместе

Мы видели, что наборы тестов и git bisect очень мощны при совместном использовании. Это может быть ещё мощнее, если вы сможете объединить их с другими системами.

Например, некоторые наборы тестов можно запускать автоматически ночью с некоторыми необычными (или даже случайными) конфигурациями. И если набор тестов обнаружит регрессию, то «git bisect» можно автоматически запустить, а его результат можно отправить по электронной почте автору первого плохого коммита, обнаруженного «git bisect», и, возможно, другим людям. Кроме того, можно автоматически создать новую запись в системе отслеживания ошибок.

"git replace"

Ранее мы видели, что "git bisect skip" теперь использует генератор псевдослучайных чисел (PRNG), чтобы пытаться избегать участков в графе коммитов, где коммиты не подлежат тестированию. Проблема в том, что иногда первый плохой коммит будет находиться в недоступной для тестирования области.

Для упрощения обсуждения предположим, что недоступная для тестирования область представляет собой простую цепочку коммитов, и что она была создана ошибкой, внесенной одним коммитом (назовем его BBC, от bisect breaking commit), и позже исправлена другим (назовем его BFC, от bisect fixing commit).

Например:

...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-...

где известно, что Y хороший, а BFC плохой, а BBC и X1 до X6 не подлежат тестированию.

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

Например:

      (BBC+BFC)-X1'-X2'-X3'-X4'-X5'-X6'-Z'
     /
...-Y-BBC-X1-X2-X3-X4-X5-X6-BFC-Z-...

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

Вы можете легко создать такую ветвь с помощью Git, используя интерактивную перебазирование.

Например, используя:

$ git rebase -i Y Z

а затем переместив BFC после BBC и сжав его.

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

Например:

$ git bisect start Z' Y

Если вы используете "git bisect run", вы можете использовать то же самое исправление вручную, как указано выше, а затем запустить другой "git bisect run" в специальной ветви. Или, как говорится в справке "git bisect", скрипт, переданный в "git bisect run", может применить патч перед компиляцией и тестированием программного обеспечения [8]. Патч должен преобразовать текущие нетестируемые коммиты в тестируемые. Таким образом, тестирование приведет к результатам "хорошо" или "плохо", и "git bisect" сможет найти первый плохой коммит. И скрипт не должен забыть удалить патч после завершения тестирования перед выходом из скрипта.

(Обратите внимание, что вместо патча можно использовать "git cherry-pick BFC" для применения исправления, и в этом случае следует использовать "git reset --hard HEAD^", чтобы отменить cherry-pick после тестирования и перед возвращением из скрипта.)

Однако приведенные выше способы обхода недоступных для тестирования областей немного громоздки. Использование специальных ветвей удобно, потому что эти ветви могут быть совместно использованы разработчиками, как и обычные ветви, но есть риск, что у людей накопится много таких ветвей. И это нарушает стандартный рабочий процесс "git bisect". Поэтому, если вы хотите использовать "git bisect run" полностью автоматически, вам необходимо добавить специальный код в ваш скрипт для перезапуска бисекции в специальных ветвях.

В любом случае, можно заметить в примере специальной ветви, что коммиты Z' и Z должны указывать на одно и то же состояние исходного кода (одну и ту же "дерево" в терминологии Git). Это происходит потому, что Z' получается из применения тех же изменений, что и Z, но в немного другом порядке.

Таким образом, если мы могли бы просто "заменить" Z на Z' во время бисекции, то нам не пришлось бы добавлять что-либо в скрипт. Он просто будет работать для всех в проекте, которые будут совместно использовать специальные ветви и замены.

Вот почему была создана команда "git replace". Технически она хранит замены "refs" в иерархии "refs/replace/". Эти "refs" похожи на ветви (которые хранятся в "refs/heads/") или теги (которые хранятся в "refs/tags"), а это означает, что они могут автоматически быть совместно использованы, как ветви или теги, среди разработчиков.

"git replace" - очень мощный механизм. Он может использоваться для исправления коммитов в уже выпущенной истории, например, для изменения сообщения коммита или автора. Он также может использоваться вместо git "grafts" для связывания репозитория с другим старым репозиторием.

Фактически, именно это последнее свойство убедило сообщество Git, поэтому оно теперь находится в ветке "master" репозитория Git и должно быть выпущено в Git 1.6.5 в октябре или ноябре 2009 года.

Одна проблема с "git replace" заключается в том, что в настоящее время все refs замен хранятся в "refs/replace/", но, возможно, было бы лучше, если бы refs замен, полезных только для бисекции, находились в "refs/replace/bisect/". Таким образом, refs замен могли бы использоваться только для бисекции, а другие refs непосредственно в "refs/replace/" использовались бы практически постоянно.

Бисекция спорадических ошибок

Другим возможным улучшением "git bisect" было бы добавление некоторой избыточности к выполняемым тестам, чтобы повысить надёжность при отслеживании спорадических ошибок.

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

Идея заключается в том, что каждые 3 теста, например, "git bisect" может попросить пользователя проверить коммит, который уже был признан "хорошим" или "плохим" (потому что один из его потомков или один из его предков был признан "хорошим" или "плохим" соответственно). Если окажется, что коммит был ранее неправильно классифицирован, то бисекция может быть прервана на ранней стадии, предположительно до того, как будут допущены слишком много ошибок. Тогда пользователю придётся разобраться в том, что произошло, и затем перезапустить бисекцию с использованием исправленного журнала бисекции.

Уже существует проект под названием BBChop, созданный Ealdwulf Wuffinga на GitHub, который делает нечто подобное, используя байесовскую теорию поиска [9]:

Но BBChop не зависит от какой-либо СКВ, и для пользователей Git было бы проще иметь что-то интегрированное в Git.