リグレッションはソフトウェア業界における大きな問題です。しかし、その主張の背後にある実際の数字を出すのは困難です。

2002年のNISTの研究[1]のような、バグ全般に関するいくつかの数字があります。

そしてその後

最終的に結論は次のように始まりました。

ソフトウェアに関連するコストの80％がメンテナンスに関するものであるという別の推定もあります[2]。

ただし、Wikipediaによると[3]

しかし、既存のソフトウェアを改善することは、リグレッションに注意する必要があるため、非常にコストがかかることがわかります。少なくとも、これにより上記の調査が互いに一致するようになります。

もちろん、ある種のソフトウェアは開発され、その後あまり改善されることなくしばらく使用され、最終的に破棄されます。この場合、当然のことながら、リグレッションは大きな問題ではない可能性があります。しかし、一方で、長年にわたって、または数十年でさえ、多くの人々によって継続的に開発および保守されている大きなソフトウェアがたくさんあります。そして、そのようなソフトウェアに依存している（時には非常に重要な）多くの人々がいるため、リグレッションは本当に大きな問題です。

そのようなソフトウェアの1つがLinuxカーネルです。そして、Linuxカーネルを見ると、リグレッションと戦うために多くの時間と労力が費やされていることがわかります。リリースサイクルは、2週間続くマージウィンドウから始まります。次に、最初のリリース候補（rc）バージョンがタグ付けされます。そして、それ以降、最終リリースまで、約1週間間隔でさらに7〜8個のrcバージョンが表示されます。

最初のrcリリースから最終リリースまでの時間は、rcバージョンをテストし、バグ、特にリグレッションに対処するために使用されることになっています。そして、この時間はリリースサイクル時間の80％以上です。しかし、もちろんリリース後も続くため、これは戦いの終わりではありません。

そして、これがIngo Molnar（有名なLinuxカーネル開発者）がgit bisectの使用について述べていることです。

したがって、開発者は常にリグレッションと戦っており、実際にはバグはできるだけ早く、つまり発見され次第修正する必要があることがよく知られています。そのため、この目的のために優れたツールを用意することは興味深いのです。

では、リグレッションに対処するために使用されるツールは何でしょうか？それらは、通常バグに対処するために使用されるツールとほぼ同じです。唯一の特定のツールは、テストスイートと「git bisect」のようなツールです。

テストスイートは非常に優れています。しかし、単独で使用すると、各コミット後にすべてのテストがチェックされるように使用されることになっています。これは、興味深い結果が得られないために多くのテストが実行され、組み合わせの爆発の影響を受けるため、効率が非常に低いことを意味します。

実際、問題は、大きなソフトウェアには多く異なる構成オプションがあり、各テストケースは各コミット後に各構成で合格する必要があるということです。したがって、各リリースにN個の構成、M個のコミット、T個のテストケースがある場合は、以下を実行する必要があります。

N、M、Tはすべてソフトウェアのサイズとともに成長しています。

したがって、すぐにすべてを完全にテストすることはできなくなります。

また、テストスイートにバグが入り込んだ場合は、テストをテストスイートに追加できます。しかし、新しく改善されたテストスイートを使用して、バグが入り込んだ場所を見つけたい場合は、バイセクションプロセスをエミュレートするか、おそらく、非常に無駄になる可能性のある、「悪い」コミットから後方に各コミットをぶっきらぼうにテストする必要があります。

使用する最初の"git bisect"サブコマンドは、検索を開始する"git bisect start"です。次に、コミットスペースを制限するために境界を設定する必要があります。これは通常、1つの「悪い」コミットと少なくとも1つの「良い」コミットを指定することで行われます。これらは、"git bisect start"への最初の呼び出しで次のように渡すことができます。

または、以下を使用して設定できます。

そして

ここで、BAD、GOOD、COMMITはすべてコミットに解決できる名前です。

次に、"git bisect"は選択したコミットをチェックアウトし、次のようにユーザーにテストを依頼します。

ここで使用する例は、実際にはおもちゃのような例であることに注意してください。ここでは、「2.6.26-something」のようなバージョンを持つ最初のコミットを探します。つまり、トップレベルのMakefileに「SUBLEVEL = 26」という行があるコミットです。これはおもちゃのような例です。なぜなら、「git bisect」を使用するよりも、「git blame」や「git log -S<string>」など、Gitを使用してこのコミットを見つけるより良い方法があるからです。

この時点で、基本的に検索を駆動する方法は2つあります。ユーザーが手動で駆動するか、スクリプトまたはコマンドによって自動的に駆動するかです。

ユーザーが駆動する場合、検索の各ステップで、ユーザーは現在のコミットをテストし、前述の「git bisect good」または「git bisect bad」コマンドを使用して、それが「良い」か「悪い」かを伝える必要があります。例えば

そして、そのようなステップをさらに数回繰り返すと、「git bisect」は最終的に最初の悪いコミットを見つけます

この時点で、コミットが何をするのかを確認したり、(まだチェックアウトされていない場合は)チェックアウトしたり、例えば、それを使って調整したりできます

そして、完了したら、「git bisect reset」を使用して、二分探索を開始する前にいたブランチに戻ることができます

二分探索プロセスを駆動するもう1つの方法は、「git bisect」に、各二分探索ステップでスクリプトまたはコマンドを起動して、現在のコミットが「良い」か「悪い」かを知るように指示することです。これを行うには、「git bisect run」コマンドを使用します。例えば

この例では、「grep ^SUBLEVEL = 25 Makefile」を「git bisect run」のパラメータとして渡しました。これは、各ステップで、渡したgrepコマンドが起動されることを意味します。そして、それがコード0で終了した場合 (つまり成功)、git bisectは現在の状態を「良い」とマークします。コード1 (または1から127までのコード、特殊コード125を除く) で終了した場合、現在の状態は「悪い」とマークされます。

128から255までの終了コードは、「git bisect run」にとって特別です。これらは、二分探索プロセスをすぐに停止させます。これは、例えば、渡されたコマンドの完了に時間がかかりすぎる場合に便利です。なぜなら、シグナルでそれを強制終了することができ、二分探索プロセスが停止するからです。

スクリプトで非常に異常な状況が検出された場合に「exit 255」とすることで、「git bisect run」に渡すスクリプトでも役立ちます。

現在の状態がテストできない場合もあります。例えば、当時それを妨げるバグがあったため、コンパイルされない場合などです。これは、特別な終了コード125が使用される理由です。これは、「git bisect run」に、現在のコミットをテストできないとマークし、別のコミットを選択してチェックアウトする必要があることを伝えます。

二分探索プロセスが手動で駆動される場合、「git bisect skip」を使用して同じことができます。(実際、特別な終了コード125は、「git bisect run」にバックグラウンドで「git bisect skip」を使用させます。)

または、より詳細に制御したい場合は、例えば「git bisect visualize」を使用して現在の状態を調べることができます。これにより、gitk (または DISPLAY 環境変数が設定されていない場合は「git log」) が起動され、より良い二分探索点を見つけるのに役立ちます。

いずれにせよ、テストできないコミットの文字列がある場合、探している回帰がこれらのテストできないコミットのいずれかによって導入されている可能性があります。この場合、どのコミットが回帰を導入したかを確信を持って伝えることはできません。

したがって、「git bisect skip」を使用した場合 (または実行スクリプトが特別なコード125で終了した場合)、次のような結果が得られる可能性があります

二分探索プロセスを他の人に示したい場合は、例えば、次を使用してログを取得できます

そして、次を使用してそれを再生できます

Gitのコミットは有向非巡回グラフ (DAG) を形成するため、各ステップでテストする最適な二分探索コミットを見つけるのはそれほど簡単ではありません。いずれにせよ、Linusは「本当に愚かな」アルゴリズムを見つけて実装し、その後Junio Hamanoによって改善され、非常にうまく機能しています。

したがって、スキップされたコミットがない場合に、最適な二分探索コミットを見つけるために「git bisect」で使用されるアルゴリズムは次のとおりです

1) 次のコミットのみを保持します

a) 「悪い」コミットの祖先である (「悪い」コミット自体を含む)、b) 「良い」コミットの祖先ではない (「良い」コミットを除く)。

これは、DAG内の興味のないコミットを取り除くことを意味します。

例えば、次のようなグラフで開始する場合

ここで、Bは「悪い」コミット、「G」は「良い」コミット、W、X、およびYはその他のコミットです。この最初のステップの後、次のグラフが得られます

したがって、WとBのコミットのみが保持されます。コミットXとYはそれぞれルールa)とb)によって削除され、コミットGもルールb)によって削除されるためです。

Gitユーザーにとって、これは次で与えられるコミットのみを保持することと同等であることに注意してください

また、保持されるコミットが「良い」コミットの子孫である必要はないことに注意してください。したがって、次の例では、コミットWとZが保持されます

2) グラフの「良い」端から開始して、各コミットに関連する祖先の数に1を加えたものを関連付けます

例えば、次のグラフでは、Hが「悪い」コミット、AとDは「良い」コミットの親です

これにより、次が得られます

3) 各コミットに関連付けます: min(X, N - X)

ここで、Xはステップ2)でコミットに関連付けられた値であり、Nはグラフ内のコミットの総数です。

上記の例では、N = 8なので、これにより次が得られます

4) 最適な二分探索点は、関連付けられた数が最も大きいコミットです

したがって、上記の例では、最適な二分探索点はコミットCです。

5) アルゴリズムを高速化するためにいくつかのショートカットが実装されていることに注意してください

最初からNがわかっているので、min(X, N - X) が N/2 より大きくなることはないことがわかります。したがって、ステップ2)と3)で、コミットにN/2を関連付ける場合、これが最適な二分探索点であることがわかります。したがって、この場合、他のコミットの処理を停止して、現在のコミットを返すことができます。

任意のコミットグラフに対して、「git rev-list --bisect-all」を使用して、各コミットに関連付けられた数を確認できます。

例えば、上記のグラフの場合、次のようなコマンド

次のような出力が生成されます

まず、「最適な二分探索点」を定義しましょう。コミットXの状態 (「良い」または「悪い」) を知ることが、コミットの状態が「良い」か「悪い」かをできるだけ多くの情報を提供する場合は、コミットXを最適な二分探索点または最適な二分探索コミットであると言います。

これは、次の関数が最大になるコミットが最適な二分探索コミットであることを意味します

ここで、information_if_good(X)はXが良い場合に得られる情報であり、information_if_bad(X)はXが悪い場合に得られる情報です。

ここで、「最初の悪いコミット」が1つしかないと仮定します。これは、そのすべての子孫が「悪い」であり、他のすべてのコミットが「良い」ことを意味します。また、すべてのコミットが、良いか悪いか、または最初の悪いコミットである確率が等しいと仮定します。したがって、c個のコミットの状態を知ることは、これらのc個のコミットがグラフ上のどこにあるか、およびcが何であれ、常に同じ量の情報を提供します。(したがって、これらのコミットが、例えばブランチ上にある、または良いコミットまたは悪いコミットの近くにあることが、より多くの情報を提供したり、より少ない情報を提供したりしないと仮定します)。

また、上記の二分探索アルゴリズムのステップ1)の後のようなクリーンアップされたグラフがあると仮定しましょう。これは、グラフから削除できるコミット数で得られる情報を測定できることを意味します。

そして、グラフ内のコミットXを取得しましょう。

Xが「良い」とわかった場合、その祖先はすべて「良い」ことがわかっているので、次のように言いたいと思います

そして、これはステップ1) b) で「良い」コミットの祖先を削除するため、当てはまります。

Xが「悪い」とわかった場合、その子孫はすべて「悪い」ことがわかっているので、次のように言いたいと思います

しかし、ステップ1) a) では悪いコミットの祖先のみを保持するため、これは間違っています。したがって、コミットが「悪い」とマークされている場合は、より多くの情報を取得します。なぜなら、新しい「悪い」コミットの祖先ではない、前の「悪い」コミットの祖先が最初の悪いコミットではないこともわかるからです。それらが良いか悪いかはわかりませんが、新しい「悪い」コミットの祖先ではないため、最初の悪いコミットではないことはわかっています。

したがって、コミットが「悪い」とマークされている場合は、新しい「悪い」コミットの祖先であるものを除いて、グラフ内のすべてのコミットを削除できることがわかります。これは、次を意味します

ここで、Nは(クリーンアップされた)グラフ内のコミットの数です。

したがって、最終的に、最適な二分探索コミットを見つけるには、次の関数を最大化する必要があることを意味します

そして、これは素晴らしいことです。なぜなら、ステップ2)でnumber_of_ancestors(X)を計算し、ステップ3)でf(X)を計算するからです。

例として次のグラフを見てみましょう

次の最適ではない関数を計算すると

次が得られます

しかし、git bisectで使用されるアルゴリズムでは、次が得られます

したがって、最適な二分探索点としてG、H、K、またはLを選択しました。これはFよりも優れています。なぜなら、例えばLが悪い場合、L、M、およびNが悪いだけでなく、G、H、I、およびJが最初の悪いコミットではないこともわかるからです (最初の悪いコミットが1つしかないと仮定し、Lの祖先でなければならないため)。

したがって、現在のアルゴリズムは、最初に仮定したことを考えると、可能な限り最良であるように思われます。

一部のコミットがスキップされている場合 ("git bisect skip"を使用)、二分探索アルゴリズムはステップ1)から3)まで同じです。しかし、その後、ほぼ次のステップを使用します

6) 関連付けられた値の降順でコミットをソートします

7) 最初のコミットがスキップされていない場合は、それを返してここで停止できます

8) それ以外の場合は、ソートされたリスト内のすべてのスキップされたコミットをフィルタリングします

9) 疑似乱数ジェネレータ (PRNG) を使用して、0から1までの乱数を生成します

10) この乱数にその平方根を掛けて、0に偏らせます

11) 結果に、フィルタリングされたリスト内のコミットの数を掛けて、このリストへのインデックスを取得します

12) 計算されたインデックスのコミットを返します

ステップ7)（スキップアルゴリズム）の後、2番目のコミットがスキップされたかどうかを確認し、スキップされていない場合はそれを返すことができます。実際、これは「git bisect skip」がGitバージョン1.5.4（2008年2月1日リリース）で開発されてから、Gitバージョン1.6.4（2009年7月29日リリース）まで使用していたアルゴリズムでした。

しかし、Ingo MolnarとH. Peter Anvin（もう一人の有名なLinuxカーネル開発者）は、最良の二分点候補がすべてテスト不可能なコミット領域に集中する場合があると不満を述べました。この場合、ユーザーは多くのテスト不可能なコミットをテストする必要があり、非常に非効率的でした。

実際、テスト不可能なコミットは、ある時点で破損が導入され、その破損が他の多くのコミットが導入された後にのみ修正されたため、テスト不可能なことが多いのです。

この破損は、もちろん、ほとんどの場合、コミットグラフ内で特定しようとしている破損とは関係ありません。しかし、興味深い「悪い挙動」が存在するかどうかを知ることができません。

そのため、テスト不可能なコミットの近くにあるコミットは、それ自体がテスト不可能である可能性が高いという事実があります。また、（二分探索アルゴリズムにより）最適な二分コミットも一緒に見つかることが多いです。

そのため、最初の二分コミットがスキップされたときに、次に最適なスキップされていない二分コミットを単純に選択するのは良くありません。

グラフ上のほとんどのコミットは、テストすると非常に多くの情報が得られることがわかりました。そして、平均して多くの情報を提供しないコミットは、goodコミットとbadコミットの近くにあるものです。

そのため、goodコミットとbadコミットから離れたコミットを優先するように偏ったPRNG（擬似乱数生成器）を使用するのが良い選択肢のように思えました。

このアルゴリズムの明らかな改善点の1つは、PRNGを使用する前に、最良の二分コミットの値に近い関連値を持ち、別のブランチにあるコミットを探すことです。そのようなコミットが存在する場合、テスト不可能である可能性は低いので、ほぼランダムに選択されたコミットよりも多くの情報を提供する可能性が高いからです。

上記の「二分探索アルゴリズム」では説明されていない、二分探索アルゴリズムには別の調整があります。

前の例では、「good」コミットは「bad」コミットの祖先であると想定しました。しかし、これは「git bisect」の要件ではありません。

もちろん、「bad」コミットは「good」コミットの祖先にはなれません。goodコミットの祖先は「good」であると想定されているためです。そして、すべての「good」コミットはbadコミットに関連している必要があります。「bad」コミットのブランチとリンクがないブランチには存在できません。しかし、goodコミットがbadコミットに関連していても、その祖先でも子孫でもない可能性があります。

たとえば、「main」ブランチと、次のように「D」というコミットでmainブランチからフォークされた「dev」ブランチが存在する可能性があります。

コミット「D」は、ブランチ「main」と「dev」のマージの最適な共通祖先であるため、これらのブランチの「マージベース」と呼ばれます。

ここで、コミットJがbadで、コミットGがgoodであり、これまで説明したように二分探索アルゴリズムを適用するとします。

二分探索アルゴリズムのステップ1) b)で説明したように、goodコミットのすべての祖先はgoodであると想定されるため削除します。

そのため、残るのは

しかし、最初のbadコミットが「B」で、「main」ブランチでコミット「F」によって修正された場合はどうなるでしょうか？

このような二分探索の結果は、実際にはBであるにもかかわらず、Hが最初のbadコミットであると判明することになります。それは間違っています！

そして、実際には、あるブランチで作業している人が、別のブランチで作業している人がバグを修正したことに気づいていないということが起こりえます！Fが複数のバグを修正したり、リリース準備ができていなかった大規模な開発作業を元に戻したりする場合もあります。

実際、開発チームは開発ブランチとメンテナンスブランチの両方を維持することが多く、「git bisect」がメンテナンスブランチにない開発ブランチでのリグレッションを二分探索したいときにうまく機能すれば、非常に簡単になります。次のコマンドを使って二分探索を開始できるはずです。

この追加の優れた機能を有効にするために、二分探索が開始され、一部のgoodコミットがbadコミットの祖先ではない場合、最初にbadコミットとgoodコミット間のマージベースを計算し、これらのマージベースを最初にチェックアウトしてテストするコミットとして選択します。

あるマージベースがbadであることが判明した場合、二分探索プロセスは次のようなメッセージで停止します。

ここで、BBBBBBはbadマージベースのsha1ハッシュであり、[GGGGGG,...]はgoodコミットのsha1のコンマ区切りのリストです。

一部のマージベースがスキップされた場合、二分探索プロセスは続行されますが、スキップされたマージベースごとに次のメッセージが出力されます。

ここで、BBBBBBはbadコミットのsha1ハッシュ、MMMMMMはスキップされたマージベースのsha1ハッシュ、[GGGGGG,...]はgoodコミットのsha1のコンマ区切りのリストです。

したがって、badマージベースがない場合、二分探索プロセスはこのステップの後、通常どおり続行されます。

テストスイートとgit bisectの両方を使用している場合、各コミット後にすべてのテストが合格することを確認することはそれほど重要ではなくなります。ただし、もちろん、他のバグの二分探索をより困難にする可能性があるため、あまり多くのものを壊さないようにするためにいくつかのチェックを行うのはおそらく良い考えです。

いくつかのポイント（たとえば、rcおよびベータリリース）で、すべてのN個の構成に対してすべてのTテストケースが合格することを確認することに注力できます。また、一部のテストが合格しない場合は、「git bisect」（または「git bisect run」の方が望ましい）を使用できます。したがって、おおよそ次のことを実行する必要があります。

ここで、cはテストのラウンド数（したがって小さな定数）、bはコミットあたりのバグの比率（うまくいけば小さな定数も）です。

したがって、各コミット後にすべてをテストする場合のO(N * T * M)に対してO(N * T)であるため、明らかにずっと優れています。

これは、テストスイートはいくつかのバグがコミットされるのを防ぐのに適しており、いくつかのバグがあることを知らせるのにも非常に適していることを意味します。しかし、いくつかのバグがどこに導入されたかを知らせるのにはあまり適していません。それを効率的に知らせるには、git bisectが必要です。

テストスイートのもう1つの良い点は、テストスイートがある場合、悪い動作をテストする方法をすでに知っているということです。したがって、リグレッションが発生した場合は、この知識を使用して「git bisect」用の新しいテストケースを作成できます。これにより、バグの二分探索と修正が容易になります。そして、作成したテストケースをテストスイートに追加できます。

したがって、テストケースの作成方法と二分探索の方法を知っていれば、好循環に陥ります。

テストの増加 ⇒ テストの作成が容易になる ⇒ 二分探索が容易になる ⇒ テストの増加

したがって、テストスイートと「git bisect」は、一緒に使用すると非常に強力で効率的な補完的なツールです。

次のようなものを使用して、破損したビルドを非常に簡単に自動的に二分探索できます。

例：

一方、これを頻繁に行う場合は、入力の手間を省くためにスクリプトを用意する価値があります。

これは、Junio Hamanoが使用した実際のスクリプト[4]からわずかに変更されたスクリプトの例です。

このスクリプトは、パフォーマンスリグレッションを導入したコミットを見つけるために「git bisect run」に渡すことができます。

破損を引き起こすことを認識している変更を含むコミットがないようにすることは、明らかに良い考えです。他のコミットが後で破損を修正した場合でも同様です。

また、どのVCSを使用する場合でも、各コミットに1つの小さな論理的な変更のみを含めることをお勧めします。

コミットの変更が小さければ小さいほど、「git bisect」は効果的になります。また、小さな変更は、コミッターのみがレビューした場合でもレビューが容易であるため、そもそも「git bisect」はあまり必要なくなるでしょう。

もう1つの良い考えは、良いコミットメッセージを用意することです。それらは、いくつかの変更がなぜ行われたのかを理解するのに非常に役立ちます。

これらの一般的なベストプラクティスは、二分探索を頻繁に行う場合に非常に役立ちます。

まず、マージ自体は、マージでソースコードの競合を解決する必要がない場合でも、いくつかのリグレッションを引き起こす可能性があります。これは、あるブランチで意味的な変更が行われているときに、他のブランチがそれを認識していない可能性があるためです。

たとえば、あるブランチが関数の意味を変更する一方で、別のブランチが同じ関数への呼び出しを追加する可能性があります。

多くのファイルを修正して競合を解決する必要がある場合、これはさらに悪化します。そのため、このようなマージは「悪魔のマージ」と呼ばれます。それらは、リグレッションを非常に追跡しにくくする可能性があります。このようなマージである場合、最初のbadコミットを知ることは誤解を招く可能性さえあります。バグが、あるブランチの意味的な変更から来ているのに、人々はバグが悪い競合解決から来ていると考える可能性があるためです。

いずれにせよ、「git rebase」を使用して履歴を線形化できます。これは、そもそもマージを回避するために使用できます。または、非線形の履歴の代わりに線形の履歴で二分探索を行うために使用できます。これは、あるブランチで意味的な変更があった場合に、より多くの情報を提供するはずです。

マージは、より小さなブランチを使用したり、長いバージョン関連のブランチのみを使用するのではなく、多くのトピックブランチを使用したりすることで、より簡単にすることもできます。

また、Linuxカーネルのlinux-nextのような特別な統合ブランチで、テストをより頻繁に行うことができます。

リグレッションを処理するための特別なワークフローは、大きな成果をもたらす可能性があります。

以下は、Andreas Ericssonが使用するワークフローの例です。

そして、以下はAndreasがこのワークフローについて述べたことです[5]。

明らかに、このワークフローはテストスイートと「git bisect」の間の好循環を利用しています。実際、リグレッションに対処するための標準的な手順になっています。

他のメッセージでアンドレアスは、彼らも上記で説明した「ベストプラクティス」、つまり、小さな論理コミット、トピックブランチ、邪悪なマージの禁止などを使用していると述べています。これらのプラクティスはすべて、二分探索をより簡単かつ有用にすることで、コミットグラフの二分探索性を向上させます。

したがって、優れたワークフローは、上記の点を中心に設計されるべきです。つまり、二分探索をより簡単、より有用、かつ標準的なものにすることです。

「git bisect」の優れた点の1つは、それが開発者ツールだけではないということです。QA担当者や、ソースコードにアクセスできる場合、またはすべてのビルドにアクセスできる場合はエンドユーザーでも効果的に使用できます。

かつてLinuxカーネルのメーリングリストで、エンドユーザーに常に二分探索を依頼することが適切かどうかについて議論があり、それが適切であるという観点を支持する非常に良い点が提示されました。

たとえば、David Millerは[6]で次のように述べています。

これは、QA担当者やエンドユーザーがそれを行うことができる方が「安価」であることが多いことを意味します。

興味深いのは、バグを報告するエンドユーザー（またはバグを再現したQA担当者）は、バグが発生する環境にアクセスできるということです。そのため、多くの場合、リグレッションをより簡単に再現できます。また、二分探索を実行できる場合は、バグが発生する環境からより多くの情報が抽出されるため、バグを理解し、修正するのが容易になります。

オープンソースプロジェクトの場合、これはエンドユーザーからより有用な貢献を得て、QAと開発活動に彼らを導入する良い方法になります。

カーネル開発のような場合によっては、二分探索を完全に自動化するために複雑なスクリプトを開発する価値がある場合があります。

以下は、Ingo Molnarがそれについて述べていることです[7]

テストスイートとgit bisectは、一緒に使用すると非常に強力であることがわかりました。他のシステムと組み合わせることができれば、さらに強力になります。

たとえば、一部のテストスイートは、夜間にいくつかの珍しい（またはランダムな）構成で自動的に実行できます。テストスイートによってリグレッションが見つかった場合は、「git bisect」を自動的に起動し、「git bisect」によって最初に見つかった不良コミットの作成者、およびおそらく他の人々にも結果をメールで送信できます。また、バグ追跡システムに新しいエントリを自動的に作成することもできます。

以前に、「git bisect skip」がコミットグラフの中でテストできない領域を避けるためにPRNGを使用するようになったことを説明しました。問題は、最初に見つかった不良コミットがテストできない領域にある場合があることです。

議論を簡単にするために、テストできない領域が単純なコミットの文字列であり、それが1つのコミット（二分探索を中断するコミットであるため、BBCと呼びましょう）によって導入された破損によって作成され、後で別のコミット（二分探索を修正するコミットであるため、BFCと呼びましょう）によって修正されたと仮定します。

例：

ここで、Yは正常であり、BFCは不良であり、BBCおよびX1からX6まではテストできないことがわかっています。

この場合、手動で二分探索している場合は、BBCの直前で始まる特別なブランチを作成できます。このブランチの最初のコミットは、BFCをスカッシュしたBBCである必要があります。また、ブランチ内の他のコミットは、BBCとBFCの間にあるコミットをブランチの最初のコミットにリベースし、その後に続くBFC以降のコミットもリベースする必要があります。

例：

ここで、'で引用されたコミットはリベースされています。

インタラクティブなリベースを使用すると、Gitでこのようなブランチを簡単に作成できます。

たとえば、次を使用します。

次に、BFCをBBCの後ろに移動してスカッシュします。

その後、新しいブランチで通常どおりに二分探索を開始でき、最終的に最初の不良コミットを見つけることができます。

例：

「git bisect run」を使用している場合は、上記と同じ手動での修正を使用し、特別なブランチで別の「git bisect run」を開始できます。または、「git bisect」のマニュアルページで説明されているように、「git bisect run」に渡されるスクリプトは、コンパイルしてソフトウェアをテストする前にパッチを適用できます[8]。パッチは、現在のテストできないコミットをテスト可能なコミットに変える必要があります。したがって、テストの結果は「正常」または「不良」になり、「git bisect」は最初の不良コミットを見つけることができるようになります。また、スクリプトは、テストが完了したら、スクリプトを終了する前にパッチを削除することを忘れないでください。

（パッチの代わりに「git cherry-pick BFC」を使用して修正を適用できることに注意してください。この場合、テスト後、スクリプトから戻る前に、チェリーピックを元に戻すために「git reset --hard HEAD^」を使用する必要があります。）

ただし、上記のテストできない領域を回避する方法は、少しぎこちないものです。特別なブランチを使用することは、これらのブランチが通常のブランチのように開発者間で共有できるため優れていますが、多くのブランチを取得してしまうというリスクがあります。また、通常の「git bisect」のワークフローが中断されます。したがって、「git bisect run」を完全に自動的に使用する場合は、特別なブランチで二分探索を再開するためにスクリプトに特別なコードを追加する必要があります。

いずれにせよ、上記の特別なブランチの例では、Z'とZのコミットが同じソースコードの状態（gitの用語では同じ「ツリー」）を指しているはずであることに気付くことができます。これは、Z'がZと同じ変更をわずかに異なる順序で適用した結果であるためです。

したがって、二分探索時にZをZ'で「置換」するだけで済む場合は、スクリプトに何も追加する必要はありません。プロジェクトで特別なブランチと置換を共有しているすべての人にとって、それはただ機能するはずです。

上記の例では、次のようになります。

これが、「git replace」コマンドが作成された理由です。技術的には、「refs/replace/」階層に置換「refs」を格納します。これらの「refs」は、（「refs/heads/」に格納されている）ブランチや（「refs/tags/」に格納されている）タグのようなものであり、つまり、開発者間でブランチやタグのように自動的に共有できることを意味します。

「git replace」は非常に強力なメカニズムです。たとえば、コミットメッセージや作成者を変更するなど、既にリリースされた履歴内のコミットを修正するために使用できます。また、git「grafts」の代わりに、リポジトリを別の古いリポジトリにリンクするためにも使用できます。

実際、Gitコミュニティに「売り込んだ」のはこの最後の機能であり、そのため、GitのGitリポジトリの「マスター」ブランチにあり、2009年10月または11月にGit 1.6.5でリリースされる予定です。

「git replace」の1つの問題は、現在、すべての置換refsを「refs/replace/」に格納していることですが、二分探索にのみ役立つ置換refsが「refs/replace/bisect/」にある方がおそらく良いでしょう。このようにすると、置換refsは二分探索にのみ使用でき、「refs/replace/」に直接ある他のrefsはほぼ常に使用できます。

「git bisect」のもう1つの可能な改善点は、散発的なバグを追跡する際の信頼性を高めるために、実行されるテストにいくつかの冗長性をオプションで追加することです。

これは、散発的なバグと呼ばれる一部のバグが、コンパイラーの出力に大きく依存するため、すべてのカーネルビルドに表示されるわけではないため、一部のカーネル開発者によって要求されています。

たとえば、3回のテストごとに、「git bisect」は、既に「正常」または「不良」であることが判明しているコミットをテストするようにユーザーに要求することができます（子孫または祖先のいずれかがそれぞれ「正常」または「不良」であることが判明しているため）。コミットが以前に誤って分類された場合、二分探索は早期に中断でき、うまくいけば、あまり多くの間違いが犯される前に中断できます。その後、ユーザーは何が起こったのかを確認し、修正された二分探索ログを使用して二分探索を再開する必要があります。

GithubでEaldwulf Wuffingaによって作成されたBBChopというプロジェクトがあり、ベイズ検索理論を使用してそのようなことを行っています[9]

ただし、BBChopはVCSとは独立しており、GitユーザーがGitに統合されたものを持っている方が簡単でしょう。