Regressionen sind ein großes Problem in der Softwareindustrie. Aber es ist schwierig, diese Behauptung mit konkreten Zahlen zu belegen.

Es gibt einige Zahlen zu Bugs im Allgemeinen, wie eine NIST-Studie aus dem Jahr 2002 [1], die besagte:

Und dann

Schließlich begann die Schlussfolgerung mit

Es gibt andere Schätzungen, die besagen, dass 80% der softwarebezogenen Kosten auf die Wartung entfallen [2].

Allerdings, laut Wikipedia [3]

Aber wir können vermuten, dass die Verbesserung bestehender Software sehr kostspielig ist, da man auf Regressionen achten muss. Zumindest würde dies die obigen Studien konsistent machen.

Natürlich wird einige Software entwickelt, dann eine Zeit lang ohne große Verbesserungen genutzt und schließlich verworfen. In diesem Fall sind Regressionen natürlich möglicherweise kein großes Problem. Aber andererseits gibt es viel große Software, die über Jahre oder sogar Jahrzehnte von vielen Leuten kontinuierlich entwickelt und gewartet wird. Und da oft viele Leute (manchmal kritisch) von solcher Software abhängen, sind Regressionen ein wirklich großes Problem.

Eine solche Software ist der Linux-Kernel. Und wenn wir uns den Linux-Kernel ansehen, können wir sehen, dass viel Zeit und Mühe aufgewendet wird, um Regressionen zu bekämpfen. Der Release-Zyklus beginnt mit einem 2 Wochen langen Merge-Fenster. Dann wird der erste Release Candidate (rc) Tag gesetzt. Und danach werden etwa 7 oder 8 weitere rc-Versionen erscheinen, mit etwa einer Woche dazwischen, bevor die endgültige Veröffentlichung erfolgt.

Die Zeit zwischen der ersten rc-Veröffentlichung und der endgültigen Veröffentlichung soll dazu dienen, rc-Versionen zu testen und Fehler und insbesondere Regressionen zu bekämpfen. Und diese Zeit macht mehr als 80% der Zeit des Release-Zyklus aus. Aber das ist noch nicht das Ende des Kampfes, denn er geht natürlich nach der Veröffentlichung weiter.

Und hier ist, was Ingo Molnar (ein bekannter Linux-Kernel-Entwickler) über seine Nutzung von git bisect sagt:

Daher werden Regressionen ständig von Entwicklern bekämpft, und es ist tatsächlich bekannt, dass Fehler so schnell wie möglich behoben werden sollten, sobald sie gefunden werden. Deshalb ist es interessant, gute Werkzeuge für diesen Zweck zu haben.

Welche Werkzeuge werden also zur Bekämpfung von Regressionen verwendet? Sie sind fast die gleichen wie die zur Bekämpfung von regulären Fehlern. Die einzigen spezifischen Werkzeuge sind Testsuiten und Werkzeuge wie "git bisect".

Testsuiten sind sehr gut. Aber wenn sie allein verwendet werden, sollen sie so eingesetzt werden, dass alle Tests nach jedem Commit überprüft werden. Das bedeutet, dass sie nicht sehr effizient sind, da viele Tests ohne interessantes Ergebnis ausgeführt werden und sie unter kombinatorischer Explosion leiden.

Tatsächlich ist das Problem, dass große Software oft viele verschiedene Konfigurationsoptionen hat und jeder Testfall für jede Konfiguration nach jedem Commit bestehen muss. Wenn Sie also für jede Version haben: N Konfigurationen, M Commits und T Testfälle, sollten Sie Folgendes durchführen:

wobei N, M und T alle mit der Größe Ihrer Software wachsen.

Sehr bald wird es also nicht mehr möglich sein, alles vollständig zu testen.

Und wenn einige Fehler Ihre Testsuite durchlaufen, können Sie einen Test zu Ihrer Testsuite hinzufügen. Aber wenn Sie Ihre neue verbesserte Testsuite verwenden möchten, um herauszufinden, wo der Fehler durchgeschlüpft ist, müssen Sie entweder einen Bisektionsprozess emulieren, oder Sie testen vielleicht plump jeden Commit rückwärts vom "schlechten" Commit, den Sie haben, was sehr verschwenderisch sein kann.

Der erste zu verwendende "git bisect"-Unterbefehl ist "git bisect start", um die Suche zu beginnen. Dann müssen Grenzen gesetzt werden, um den Commit-Raum einzuschränken. Dies geschieht normalerweise, indem ein "schlechter" und mindestens ein "guter" Commit angegeben werden. Diese können im ersten Aufruf von "git bisect start" wie folgt übergeben werden:

oder sie können mit folgenden Befehlen gesetzt werden:

und

wobei BAD, GOOD und COMMIT alles Namen sind, die zu einem Commit aufgelöst werden können.

Dann wird "git bisect" einen Commit seiner Wahl auschecken und den Benutzer bitten, ihn zu testen, wie hier gezeigt:

Beachten Sie, dass das Beispiel, das wir verwenden werden, wirklich ein Spielbeispiel ist. Wir suchen nach dem ersten Commit, der eine Version wie "2.6.26-something" hat, d.h. den Commit, der eine Zeile "SUBLEVEL = 26" in der obersten Makefile-Datei hat. Dies ist ein Spielbeispiel, da es mit Git bessere Möglichkeiten gibt, diesen Commit zu finden, als "git bisect" zu verwenden (z. B. "git blame" oder "git log -S<string>").

An diesem Punkt gibt es im Grunde 2 Möglichkeiten, die Suche zu steuern. Sie kann manuell vom Benutzer oder automatisch von einem Skript oder Befehl gesteuert werden.

Wenn der Benutzer sie steuert, muss der Benutzer bei jedem Schritt der Suche den aktuellen Commit testen und mit den oben beschriebenen Befehlen "git bisect good" oder "git bisect bad" angeben, ob er "gut" oder "schlecht" ist. Zum Beispiel:

Und nach ein paar weiteren Schritten wie diesem wird "git bisect" schließlich einen ersten schlechten Commit finden:

An diesem Punkt können wir sehen, was der Commit tut, ihn auschecken (falls er noch nicht ausgecheckt ist) oder damit herumspielen, zum Beispiel:

Und wenn wir fertig sind, können wir "git bisect reset" verwenden, um zu dem Branch zurückzukehren, in dem wir uns vor Beginn des Bisectings befanden.

Die andere Möglichkeit, den Bisektionsprozess zu steuern, besteht darin, "git bisect" anzuweisen, bei jedem Bisektionsschritt ein Skript oder einen Befehl auszuführen, um zu wissen, ob der aktuelle Commit "gut" oder "schlecht" ist. Dazu verwenden wir den Befehl "git bisect run". Zum Beispiel:

In diesem Beispiel haben wir "grep ^SUBLEVEL = 25 Makefile" als Parameter an "git bisect run" übergeben. Das bedeutet, dass bei jedem Schritt der übergebene grep-Befehl ausgeführt wird. Und wenn er mit dem Code 0 (was Erfolg bedeutet) beendet wird, markiert git bisect den aktuellen Zustand als "gut". Wenn er mit dem Code 1 (oder einem beliebigen Code zwischen 1 und 127, ausgenommen der spezielle Code 125) beendet wird, wird der aktuelle Zustand als "schlecht" markiert.

Exit-Codes zwischen 128 und 255 sind speziell für "git bisect run". Sie bewirken, dass der Bisektionsprozess sofort gestoppt wird. Dies ist zum Beispiel nützlich, wenn der übergebene Befehl zu lange dauert, da Sie ihn mit einem Signal beenden können und der Bisektionsprozess gestoppt wird.

Es kann auch in Skripten, die an "git bisect run" übergeben werden, nützlich sein, "exit 255" auszuführen, wenn eine sehr ungewöhnliche Situation erkannt wird.

Manchmal passiert es, dass der aktuelle Zustand nicht getestet werden kann, z. B. wenn er nicht kompiliert, weil es zu diesem Zeitpunkt einen Bug gab, der dies verhinderte. Dafür ist der spezielle Exit-Code 125 vorgesehen. Er teilt "git bisect run" mit, dass der aktuelle Commit als nicht testbar markiert werden soll und dass ein anderer ausgewählt und ausgecheckt werden soll.

Wenn der Bisektionsprozess manuell gesteuert wird, können Sie dafür "git bisect skip" verwenden. (Tatsächlich verwendet "git bisect run" den speziellen Exit-Code 125 im Hintergrund, um "git bisect skip" aufzurufen.)

Oder wenn Sie mehr Kontrolle wünschen, können Sie den aktuellen Zustand mit z. B. "git bisect visualize" inspizieren. Dies startet gitk (oder "git log", wenn die Umgebungsvariable DISPLAY nicht gesetzt ist), um Ihnen bei der Suche nach einem besseren Bisektionspunkt zu helfen.

In jedem Fall, wenn Sie eine Reihe von nicht testbaren Commits haben, kann es vorkommen, dass die gesuchte Regression von einem dieser nicht testbaren Commits eingeführt wurde. In diesem Fall ist es nicht möglich, sicher zu sagen, welcher Commit die Regression eingeführt hat.

Wenn Sie also "git bisect skip" verwendet haben (oder das Run-Skript mit dem speziellen Code 125 beendet wurde), erhalten Sie möglicherweise ein Ergebnis wie dieses:

Wenn Sie anderen Personen Ihren Bisektionsprozess zeigen möchten, können Sie ein Protokoll erhalten, z. B. mit:

Und es ist möglich, es wiederherzustellen mit:

Da die Git-Commits einen gerichteten azyklischen Graphen (DAG) bilden, ist das Finden des besten Bisektions-Commits für jeden Schritt nicht so einfach. Linus hat jedenfalls einen "wirklich dummen" Algorithmus gefunden und implementiert, der später von Junio Hamano verbessert wurde und recht gut funktioniert.

Der von "git bisect" verwendete Algorithmus, um den besten Bisektions-Commit ohne übersprungene Commits zu finden, ist wie folgt:

1) Nur die Commits beibehalten, die

a) Vorfahren des "schlechten" Commits sind (einschließlich des "schlechten" Commits selbst), b) keine Vorfahren eines "guten" Commits sind (ausschließlich der "guten" Commits).

Das bedeutet, dass wir die uninteressanten Commits im DAG loswerden.

Zum Beispiel, wenn wir mit einem Graphen wie diesem beginnen:

wobei B der "schlechte" Commit ist, "G" die "guten" Commits und W, X und Y andere Commits sind, erhalten wir nach diesem ersten Schritt den folgenden Graphen:

Es werden also nur die Commits W und B beibehalten. Da die Commits X und Y nach den Regeln a) bzw. b) entfernt werden und die Commits G ebenfalls nach Regel b) entfernt werden.

Hinweis für Git-Benutzer: Dies ist äquivalent zur Beibehaltung nur des von folgenden Befehl gelieferten Commits:

Beachten Sie auch, dass wir nicht verlangen, dass die beibehaltenen Commits Nachfahren eines "guten" Commits sind. In dem folgenden Beispiel werden also die Commits W und Z beibehalten:

2) Beginnend von den "guten" Enden des Graphen, ordnen Sie jedem Commit die Anzahl seiner Vorfahren plus eins zu.

Zum Beispiel mit dem folgenden Graphen, wobei H der "schlechte" Commit und A und D einige Eltern von "guten" Commits sind:

Dies ergibt:

3) Ordnen Sie jedem Commit zu: min(X, N - X)

wobei X der Wert ist, der dem Commit in Schritt 2) zugeordnet ist, und N die Gesamtzahl der Commits im Graphen ist.

Im obigen Beispiel haben wir N = 8, also ergibt dies:

4) Der beste Bisektionspunkt ist der Commit mit der höchsten zugeordneten Zahl.

Im obigen Beispiel ist der beste Bisektionspunkt also Commit C.

5) Beachten Sie, dass einige Abkürzungen implementiert sind, um den Algorithmus zu beschleunigen.

Da wir N von Anfang an kennen, wissen wir, dass min(X, N - X) nicht größer als N/2 sein kann. Daher können wir während der Schritte 2) und 3) die Verarbeitung anderer Commits stoppen und den aktuellen Commit zurückgeben, wenn wir N/2 einem Commit zuordnen. In diesem Fall können wir einfach aufhören, andere Commits zu verarbeiten, und den aktuellen Commit zurückgeben.

Für jeden Commit-Graphen können Sie die jedem Commit zugeordnete Zahl mit "git rev-list --bisect-all" sehen.

Zum Beispiel, für den obigen Graphen, ein Befehl wie:

würde etwas wie folgt ausgeben:

Definieren wir zunächst "bester Bisektionspunkt". Wir werden sagen, dass ein Commit X ein bester Bisektionspunkt oder ein bester Bisektions-Commit ist, wenn das Wissen über seinen Zustand ("gut" oder "schlecht") so viel Information wie möglich darüber liefert, ob der Zustand des Commits "gut" oder "schlecht" ist.

Das bedeutet, dass die besten Bisektions-Commits diejenigen sind, bei denen die folgende Funktion maximal ist:

wobei information_if_good(X) die Information ist, die wir erhalten, wenn X gut ist, und information_if_bad(X) die Information ist, die wir erhalten, wenn X schlecht ist.

Nehmen wir nun an, dass es nur einen einzigen "ersten schlechten Commit" gibt. Das bedeutet, dass alle seine Nachfahren "schlecht" sind und alle anderen Commits "gut" sind. Und wir nehmen an, dass alle Commits die gleiche Wahrscheinlichkeit haben, gut oder schlecht, oder der erste schlechte Commit zu sein, so dass das Wissen über den Zustand von c Commits immer die gleiche Information liefert, egal wo sich diese c Commits im Graphen befinden und egal was c ist. (Wir nehmen also an, dass diese Commits, z. B. auf einem Branch oder in der Nähe eines guten oder schlechten Commits, nicht mehr oder weniger Information liefern.)

Nehmen wir außerdem an, wir haben einen bereinigten Graphen, wie einen nach Schritt 1) im obigen Bisektionsalgorithmus. Das bedeutet, dass wir die Information, die wir erhalten, in Bezug auf die Anzahl der Commits messen können, die wir aus dem Graphen entfernen können.

Und nehmen wir einen Commit X im Graphen.

Wenn X als "gut" befunden wird, wissen wir, dass seine Vorfahren alle "gut" sind, also wollen wir sagen, dass

Und das ist richtig, denn in Schritt 1) b) entfernen wir die Vorfahren der "guten" Commits.

Wenn X als "schlecht" befunden wird, wissen wir, dass seine Nachfahren alle "schlecht" sind, also wollen wir sagen, dass

Aber das ist falsch, denn in Schritt 1) a) behalten wir nur die Vorfahren des schlechten Commits. Wir erhalten also mehr Information, wenn ein Commit als "schlecht" markiert wird, weil wir auch wissen, dass die Vorfahren des vorherigen "schlechten" Commits, die keine Vorfahren des neuen "schlechten" Commits sind, nicht der erste schlechte Commit sind. Wir wissen nicht, ob sie gut oder schlecht sind, aber wir wissen, dass sie nicht der erste schlechte Commit sind, weil sie keine Vorfahren des neuen "schlechten" Commits sind.

Wenn also ein Commit als "schlecht" markiert wird, wissen wir, dass wir alle Commits im Graphen entfernen können, mit Ausnahme derer, die Vorfahren des neuen "schlechten" Commits sind. Das bedeutet,

wobei N die Anzahl der Commits im (bereinigten) Graphen ist.

Am Ende bedeutet dies also, dass wir zur Suche nach den besten Bisektions-Commits die Funktion maximieren sollten:

Und das ist gut, denn in Schritt 2) berechnen wir number_of_ancestors(X) und in Schritt 3) berechnen wir f(X).

Nehmen wir den folgenden Graphen als Beispiel:

Wenn wir die folgende nicht optimale Funktion darauf berechnen:

erhalten wir:

aber mit dem von git bisect verwendeten Algorithmus erhalten wir:

Wir wählen also G, H, K oder L als besten Bisektionspunkt, was besser ist als F. Denn wenn z. B. L schlecht ist, wissen wir nicht nur, dass L, M und N schlecht sind, sondern auch, dass G, H, I und J nicht der erste schlechte Commit sind (da wir annehmen, dass es nur einen ersten schlechten Commit gibt und dieser ein Vorfahre von L sein muss).

Der aktuelle Algorithmus scheint also der bestmögliche zu sein, basierend auf unseren anfänglichen Annahmen.

Wenn einige Commits übersprungen wurden (mit "git bisect skip"), dann ist der Bisektionsalgorithmus für die Schritte 1) bis 3) derselbe. Aber dann verwenden wir ungefähr die folgenden Schritte:

6) Sortieren Sie die Commits nach abnehmendem zugeordnetem Wert.

7) Wenn der erste Commit nicht übersprungen wurde, können wir ihn zurückgeben und hier aufhören.

8) Filtern Sie andernfalls alle übersprungenen Commits aus der sortierten Liste.

9) Verwenden Sie einen Pseudo-Zufallszahlengenerator (PRNG), um eine Zufallszahl zwischen 0 und 1 zu generieren.

10) Multiplizieren Sie diese Zufallszahl mit ihrer Quadratwurzel, um sie zu Null hin zu verschieben.

11) Multiplizieren Sie das Ergebnis mit der Anzahl der Commits in der gefilterten Liste, um einen Index in dieser Liste zu erhalten.

12) Geben Sie den Commit am berechneten Index zurück.

Nach Schritt 7) (im Skip-Algorithmus) könnten wir prüfen, ob der zweite Commit übersprungen wurde, und ihn zurückgeben, wenn dies nicht der Fall ist. Und tatsächlich war dies der Algorithmus, den wir verwendeten, seit "git bisect skip" in Git Version 1.5.4 (veröffentlicht am 1. Februar 2008) entwickelt wurde, bis Git Version 1.6.4 (veröffentlicht am 29. Juli 2009).

Aber Ingo Molnar und H. Peter Anvin (ein weiterer bekannter Linux-Kernel-Entwickler) beklagten sich beide, dass manchmal die besten Bisektionspunkte alle in einem Bereich lagen, in dem alle Commits nicht testbar waren. Und in diesem Fall wurde der Benutzer aufgefordert, viele nicht testbare Commits zu testen, was sehr ineffizient sein konnte.

In der Tat sind nicht testbare Commits oft nicht testbar, weil zu einer bestimmten Zeit ein Fehler eingeführt wurde und dieser Fehler erst nach vielen anderen Commits behoben wurde.

Dieser Fehler steht natürlich meistens in keinem Zusammenhang mit dem Fehler, den wir im Commit-Graphen zu lokalisieren versuchen. Aber er hindert uns daran zu wissen, ob das interessante "schlechte Verhalten" vorhanden ist oder nicht.

Es ist also eine Tatsache, dass Commits in der Nähe eines nicht testbaren Commits mit hoher Wahrscheinlichkeit selbst nicht testbar sind. Und die besten Bisektionspunkte werden oft auch zusammen gefunden (aufgrund des Bisektionsalgorithmus).

Deshalb ist es eine schlechte Idee, einfach den nächsten besten unübersprungenen Bisektions-Commit zu wählen, wenn der erste übersprungen wurde.

Wir haben festgestellt, dass die meisten Commits im Graphen viel Information liefern können, wenn sie getestet werden. Und die Commits, die im Durchschnitt nicht viel Information liefern, sind diejenigen in der Nähe der guten und schlechten Commits.

Daher schien die Verwendung eines PRNG mit einer Neigung, Commits weg von den guten und schlechten Commits zu bevorzugen, eine gute Wahl zu sein.

Eine offensichtliche Verbesserung dieses Algorithmus wäre, nach einem Commit zu suchen, der einen zugeordneten Wert in der Nähe des besten Bisektions-Commits hat und sich auf einem anderen Branch befindet, bevor der PRNG verwendet wird. Denn wenn ein solcher Commit existiert, ist es unwahrscheinlich, dass er ebenfalls nicht testbar ist, und er wird wahrscheinlich mehr Informationen liefern als ein fast zufällig ausgewählter.

Es gibt eine weitere Anpassung im Bisektionsalgorithmus, die im "Bisektionsalgorithmus" oben nicht beschrieben wurde.

Wir haben in den vorherigen Beispielen angenommen, dass die "guten" Commits Vorfahren des "schlechten" Commits sind. Aber das ist keine Voraussetzung für "git bisect".

Natürlich kann der "schlechte" Commit kein Vorfahre eines "guten" Commits sein, da die Vorfahren der guten Commits als "gut" gelten. Und alle "guten" Commits müssen mit dem schlechten Commit verwandt sein. Sie können sich nicht auf einem Branch befinden, der keine Verbindung zum Branch des "schlechten" Commits hat. Aber es ist möglich, dass ein guter Commit mit einem schlechten Commit verwandt ist und dennoch weder ein Vorfahre noch ein Nachfahre davon ist.

Zum Beispiel kann es einen "main"-Branch und einen "dev"-Branch geben, der bei einem Commit namens "D" von dem main-Branch abgezweigt wurde, wie hier:

Der Commit "D" wird als "Merge Base" für die Branches "main" und "dev" bezeichnet, da er der beste gemeinsame Vorfahre für diese Branches für einen Merge ist.

Nehmen wir nun an, Commit J ist schlecht und Commit G ist gut, und wir wenden den Bisektionsalgorithmus wie zuvor beschrieben an.

Wie in Schritt 1) b) des Bisektionsalgorithmus beschrieben, entfernen wir alle Vorfahren der guten Commits, da diese ebenfalls als gut gelten.

Also würden wir nur noch folgendes übrig haben:

Aber was passiert, wenn der erste schlechte Commit "B" ist und er im "main"-Branch durch Commit "F" behoben wurde?

Das Ergebnis einer solchen Bisektion wäre, dass wir feststellen würden, dass H der erste schlechte Commit ist, obwohl es tatsächlich B ist. Das wäre also falsch!

Und ja, es kann in der Praxis vorkommen, dass Leute, die an einem Branch arbeiten, nicht wissen, dass Leute, die an einem anderen Branch arbeiten, einen Fehler behoben haben! Es könnte auch passieren, dass F mehr als einen Fehler behoben hat oder dass es sich um eine Rückgängigmachung einer großen Entwicklungsarbeit handelt, die noch nicht für die Veröffentlichung bereit war.

Tatsächlich pflegen Entwicklungsteams oft sowohl einen Entwicklungs- als auch einen Wartungs-Branch, und es wäre für sie recht einfach, wenn "git bisect" auch dann funktionieren würde, wenn sie eine Regression im Entwicklungs-Branch bisecten wollen, die nicht im Wartungs-Branch vorhanden ist. Sie sollten in der Lage sein, mit Folgendem mit der Bisektion zu beginnen:

Um diese zusätzliche nützliche Funktion zu ermöglichen, wenn eine Bisektion gestartet wird und wenn einige gute Commits keine Vorfahren des schlechten Commits sind, berechnen wir zuerst die Merge-Basen zwischen den schlechten und guten Commits und wählen diese Merge-Basen als die ersten zu prüfenden und zu testenden Commits aus.

Wenn sich herausstellt, dass eine Merge-Basis schlecht ist, wird der Bisektionsprozess mit einer Meldung wie dieser gestoppt:

wobei BBBBBB der SHA1-Hash der schlechten Merge-Basis ist und [GGGGGG,…] eine kommagetrennte Liste der SHA1-Hashes der guten Commits ist.

Wenn einige der Merge-Basen übersprungen werden, wird der Bisektionsprozess fortgesetzt, aber die folgende Meldung wird für jede übersprungene Merge-Basis ausgegeben:

wobei BBBBBB der SHA1-Hash des schlechten Commits ist, MMMMMM der SHA1-Hash der übersprungenen Merge-Basis und [GGGGGG,…] eine kommagetrennte Liste der SHA1-Hashes der guten Commits ist.

Wenn also keine schlechte Merge-Basis vorhanden ist, wird der Bisektionsprozess nach diesem Schritt wie gewohnt fortgesetzt.

Wenn Sie sowohl eine Testsuite haben als auch git bisect verwenden, wird es weniger wichtig, zu überprüfen, ob alle Tests nach jedem Commit bestanden werden. Obwohl es wahrscheinlich eine gute Idee ist, einige Überprüfungen durchzuführen, um zu vermeiden, dass zu viele Dinge kaputt gehen, da dies das Bisecting anderer Fehler erschweren könnte.

Sie können Ihre Anstrengungen darauf konzentrieren, an einigen Punkten (z. B. rc- und Beta-Releases) zu überprüfen, ob alle T Testfälle für alle N Konfigurationen erfolgreich sind. Und wenn einige Tests fehlschlagen, können Sie "git bisect" (oder besser "git bisect run") verwenden. Sie sollten also ungefähr Folgendes durchführen:

wobei c die Anzahl der Testrunden ist (also eine kleine Konstante) und b das Verhältnis von Fehlern pro Commit ist (hoffentlich auch eine kleine Konstante).

Es ist also natürlich viel besser, da es O(N * T) im Vergleich zu O(N * T * M) ist, wenn Sie nach jedem Commit alles testen würden.

Das bedeutet, dass Testsuiten gut darin sind, einige Fehler vom Commit abzuhalten, und sie sind auch ziemlich gut darin, Ihnen mitzuteilen, dass Sie einige Fehler haben. Aber sie sind nicht so gut darin, Ihnen zu sagen, wo einige Fehler eingeführt wurden. Um Ihnen das effizient mitzuteilen, ist git bisect erforderlich.

Das andere Nützliche an Testsuiten ist, dass Sie, wenn Sie eine haben, bereits wissen, wie Sie auf schlechtes Verhalten testen können. Sie können dieses Wissen also nutzen, um einen neuen Testfall für "git bisect" zu erstellen, wenn sich herausstellt, dass eine Regression vorliegt. So wird es einfacher sein, den Fehler zu bisecten und zu beheben. Und dann können Sie den gerade erstellten Testfall zu Ihrer Testsuite hinzufügen.

Wenn Sie also wissen, wie man Testfälle erstellt und wie man bisectet, werden Sie einem Kreislauf der Tugend unterliegen:

mehr Tests ⇒ einfacher, Tests zu erstellen ⇒ einfacher zu bisecten ⇒ mehr Tests

Testsuiten und "git bisect" sind also komplementäre Werkzeuge, die zusammen sehr mächtig und effizient sind.

Sie können defekte Builds sehr einfach automatisch bisecten, indem Sie etwas wie folgendes verwenden:

Zum Beispiel

Wenn Sie dies jedoch oft tun, kann es sich lohnen, Skripte zu haben, um zu viel Tippen zu vermeiden.

Hier ist ein Beispielskript, das leicht modifiziert aus einem realen Skript von Junio Hamano [4] stammt.

Dieses Skript kann an "git bisect run" übergeben werden, um den Commit zu finden, der eine Performance-Regression eingeführt hat:

Es ist offensichtlich eine gute Idee, keine Commits mit Änderungen zu haben, die wissentlich Dinge kaputt machen, auch wenn einige andere Commits den Bruch später beheben.

Es ist auch eine gute Idee, bei der Verwendung eines beliebigen VCS nur eine kleine logische Änderung pro Commit zu haben.

Je kleiner die Änderungen in Ihrem Commit sind, desto effektiver wird "git bisect" sein. Und Sie werden "git bisect" wahrscheinlich ohnehin weniger benötigen, da kleine Änderungen leichter zu überprüfen sind, auch wenn sie nur vom Committer überprüft werden.

Eine weitere gute Idee sind gute Commit-Nachrichten. Sie können sehr hilfreich sein, um zu verstehen, warum einige Änderungen vorgenommen wurden.

Diese allgemeinen Best Practices sind sehr hilfreich, wenn Sie häufig bisecten.

Erstens können Merges selbst Regressionen einführen, auch wenn der Merge keine Quellcode-Konfliktlösung erfordert. Das liegt daran, dass sich eine semantische Änderung in einem Branch ereignen kann, während der andere Branch davon nichts weiß.

Zum Beispiel kann ein Branch die Semantik einer Funktion ändern, während der andere Branch mehr Aufrufe derselben Funktion hinzufügt.

Dies wird durch viele zu korrigierende Dateien zur Konfliktlösung noch verschlimmert. Deshalb werden solche Merges als "böse Merges" bezeichnet. Sie können Regressionen sehr schwer nachvollziehbar machen. Es kann sogar irreführend sein, den ersten schlechten Commit zu kennen, wenn es sich um einen solchen Merge handelt, da die Leute denken könnten, der Fehler stamme von einer schlechten Konfliktlösung, obwohl er von einer semantischen Änderung in einem Branch stammt.

Jedenfalls kann "git rebase" verwendet werden, um die Historie zu linearisieren. Dies kann entweder verwendet werden, um das Mergen im Voraus zu vermeiden. Oder es kann verwendet werden, um auf einer linearen Historie statt auf der nichtlinearen zu bisecten, da dies im Falle einer semantischen Änderung in einem Branch mehr Informationen liefern sollte.

Merges können auch durch die Verwendung kleinerer Branches oder durch die Verwendung vieler Topic Branches anstelle von nur langen, versionsbezogenen Branches vereinfacht werden.

Und Tests können öfter in speziellen Integrations-Branches wie linux-next für den Linux-Kernel durchgeführt werden.

Ein spezieller Arbeitsablauf zur Verarbeitung von Regressionen kann großartige Ergebnisse liefern.

Hier ist ein Beispiel für einen Arbeitsablauf, der von Andreas Ericsson verwendet wird:

Und hier ist, was Andreas zu diesem Arbeitsablauf sagte [5]

Offensichtlich nutzt dieser Arbeitsablauf den positiven Kreislauf zwischen Test-Suiten und "git bisect". Tatsächlich macht er ihn zum Standardverfahren im Umgang mit Regressionen.

In anderen Nachrichten sagt Andreas, dass sie auch die oben beschriebenen "Best Practices" anwenden: kleine logische Commits, Topic-Branches, keine bösen Merges usw. Diese Praktiken verbessern alle die Bisect-Fähigkeit des Commit-Graphen, indem sie das Bisecten einfacher und nützlicher machen.

Ein guter Arbeitsablauf sollte also auf den oben genannten Punkten aufbauen. Das heißt, Bisecten einfacher, nützlicher und zum Standard zu machen.

Eine schöne Sache an "git bisect" ist, dass es nicht nur ein Entwicklerwerkzeug ist. Es kann effektiv von QA-Leuten oder sogar Endbenutzern verwendet werden (wenn sie Zugriff auf den Quellcode haben oder auf alle Builds zugreifen können).

Es gab einmal eine Diskussion in der Linux-Kernel-Mailingliste darüber, ob es in Ordnung sei, Endbenutzer immer zum Bisecten aufzufordern, und es wurden sehr gute Argumente angeführt, um diesen Standpunkt zu unterstützen.

Zum Beispiel schrieb David Miller [6]

Das bedeutet, dass es oft "billiger" ist, wenn QA-Leute oder Endbenutzer dies tun können.

Interessant ist auch, dass Endbenutzer, die Fehler melden (oder QA-Leute, die einen Fehler reproduziert haben), Zugriff auf die Umgebung haben, in der der Fehler auftritt. Daher können sie eine Regression oft leichter reproduzieren. Und wenn sie bisecten können, werden mehr Informationen aus der Umgebung extrahiert, in der der Fehler auftritt, was bedeutet, dass es einfacher wird, den Fehler zu verstehen und dann zu beheben.

Für Open-Source-Projekte kann es eine gute Möglichkeit sein, mehr nützliche Beiträge von Endbenutzern zu erhalten und sie in QA- und Entwicklungsaktivitäten einzuführen.

In einigen Fällen, wie z. B. bei der Kernelentwicklung, kann es sich lohnen, komplexe Skripte zu entwickeln, um das Bisecten vollständig zu automatisieren.

Hier ist, was Ingo Molnar dazu sagt [7]

Wir haben gesehen, dass Test-Suiten und Git Bisect sehr mächtig sind, wenn sie zusammen verwendet werden. Sie können noch mächtiger sein, wenn man sie mit anderen Systemen kombiniert.

Zum Beispiel könnten einige Test-Suiten nachts automatisch mit ungewöhnlichen (oder sogar zufälligen) Konfigurationen ausgeführt werden. Und wenn eine Regression von einer Test-Suite gefunden wird, kann "git bisect" automatisch gestartet werden, und sein Ergebnis kann an den Autor des ersten von "git bisect" gefundenen schlechten Commits und vielleicht an andere Personen gesendet werden. Und ein neuer Eintrag im Bug-Tracking-System könnte ebenfalls automatisch erstellt werden.

Wir haben bereits gesehen, dass "git bisect skip" nun einen PRNG verwendet, um zu versuchen, Bereiche im Commit-Graphen zu vermeiden, in denen Commits nicht testbar sind. Das Problem ist, dass der erste schlechte Commit manchmal in einem nicht testbaren Bereich liegt.

Um die Diskussion zu vereinfachen, nehmen wir an, dass der nicht testbare Bereich eine einfache Kette von Commits ist und dass er durch einen Fehler, der von einem Commit eingeführt wurde (nennen wir ihn BBC für Bisect Breaking Commit), und später durch einen anderen behoben wurde (nennen wir ihn BFC für Bisect Fixing Commit).

Zum Beispiel

wobei wir wissen, dass Y gut ist und BFC schlecht, und wobei BBC und X1 bis X6 nicht testbar sind.

In diesem Fall können Sie, wenn Sie manuell bisecten, einen speziellen Branch erstellen, der kurz vor dem BBC beginnt. Der erste Commit in diesem Branch sollte der BBC sein, mit dem BFC hineingequetscht. Und die anderen Commits im Branch sollten die Commits zwischen BBC und BFC sein, die auf den ersten Commit des Branches rebased wurden, und dann auch der Commit nach BFC, ebenfalls rebased.

Zum Beispiel

wobei Commits, die mit ' zitiert sind, rebased wurden.

Sie können einen solchen Branch mit Git einfach mit interaktivem Rebase erstellen.

Zum Beispiel mit

und dann BFC nach BBC verschieben und hineinquetschen.

Danach können Sie wie gewohnt im neuen Branch mit dem Bisecten beginnen und sollten schließlich den ersten schlechten Commit finden.

Zum Beispiel

Wenn Sie "git bisect run" verwenden, können Sie die gleiche manuelle Korrektur wie oben durchführen und dann einen weiteren "git bisect run" im speziellen Branch starten. Oder wie in der "git bisect"-Manpage angegeben, kann das an "git bisect run" übergebene Skript vor dem Kompilieren und Testen der Software einen Patch anwenden [8]. Der Patch sollte einen aktuellen nicht testbaren Commit in einen testbaren umwandeln. Das Testen führt dann zu "gut" oder "schlecht", und "git bisect" kann den ersten schlechten Commit finden. Und das Skript sollte nicht vergessen, den Patch nach dem Testen zu entfernen, bevor es aus dem Skript beendet wird.

(Beachten Sie, dass Sie anstelle eines Patches "git cherry-pick BFC" verwenden können, um die Korrektur anzuwenden, und in diesem Fall sollten Sie "git reset --hard HEAD^" verwenden, um den Cherry-Pick nach dem Testen und vor der Rückkehr aus dem Skript rückgängig zu machen.)

Die oben genannten Möglichkeiten, nicht testbare Bereiche zu umgehen, sind jedoch etwas umständlich. Die Verwendung spezieller Branches ist gut, da diese Branches von Entwicklern wie übliche Branches geteilt werden können, aber das Risiko besteht darin, dass die Leute viele solcher Branches bekommen. Und es stört den normalen "git bisect"-Arbeitsablauf. Wenn Sie also "git bisect run" vollständig automatisch nutzen möchten, müssen Sie Ihrem Skript speziellen Code hinzufügen, um das Bisecten in den speziellen Branches neu zu starten.

Jedenfalls kann man im obigen Beispiel für spezielle Branches feststellen, dass die Z' und Z Commits auf denselben Quellcode-Zustand (denselben "Tree" im Git-Jargon) verweisen sollten. Das liegt daran, dass Z' durch Anwendung derselben Änderungen wie Z, nur in etwas anderer Reihenfolge, entsteht.

Wenn wir also Z einfach durch Z' "ersetzen" könnten, wenn wir bisecten, dann müssten wir nichts zu einem Skript hinzufügen. Es würde einfach für jeden im Projekt, der die speziellen Branches und die Ersetzungen teilt, funktionieren.

Mit dem obigen Beispiel würde das ergeben

Deshalb wurde der Befehl "git replace" erstellt. Technisch gesehen speichert er Ersetzungs-"Refs" in der Hierarchie "refs/replace/". Diese "Refs" sind wie Branches (die in "refs/heads/" gespeichert sind) oder Tags (die in "refs/tags/" gespeichert sind), und das bedeutet, dass sie automatisch wie Branches oder Tags unter Entwicklern geteilt werden können.

"git replace" ist ein sehr mächtiger Mechanismus. Er kann verwendet werden, um Commits in bereits freigegebener Historie zu korrigieren, zum Beispiel um die Commit-Nachricht oder den Autor zu ändern. Und er kann auch anstelle von Git-Grafts verwendet werden, um ein Repository mit einem anderen alten Repository zu verknüpfen.

Tatsächlich ist es diese letzte Funktion, die es der Git-Community "verkauft" hat, so dass es sich jetzt im "master"-Branch des Git-Git-Repositorys befindet und im Oktober oder November 2009 in Git 1.6.5 veröffentlicht werden sollte.

Ein Problem mit "git replace" ist, dass es derzeit alle Ersetzungs-Refs in "refs/replace/" speichert, aber es wäre vielleicht besser, wenn die Ersetzungs-Refs, die nur für das Bisecten nützlich sind, in "refs/replace/bisect/" wären. Auf diese Weise könnten die Ersetzungs-Refs nur für das Bisecten verwendet werden, während andere Refs direkt in "refs/replace/" fast immer verwendet würden.

Eine weitere mögliche Verbesserung von "git bisect" wäre, optional einige Redundanz zu den durchgeführten Tests hinzuzufügen, damit es bei der Verfolgung sporadischer Fehler zuverlässiger ist.

Dies wurde von einigen Kernel-Entwicklern angefordert, da einige Fehler, die als sporadische Fehler bezeichnet werden, nicht in allen Kernel-Builds auftreten, da sie sehr stark von der Compiler-Ausgabe abhängen.

Die Idee ist, dass "git bisect" beispielsweise alle 3 Tests den Benutzer bitten könnte, einen Commit zu testen, der bereits als "gut" oder "schlecht" befunden wurde (weil einer seiner Nachfolger oder einer seiner Vorgänger als "gut" bzw. "schlecht" befunden wurde). Wenn sich herausstellt, dass ein Commit zuvor falsch klassifiziert wurde, kann das Bisecting frühzeitig abgebrochen werden, hoffentlich bevor zu viele Fehler gemacht wurden. Dann muss der Benutzer sehen, was passiert ist, und das Bisecting mit einem korrigierten Bisect-Protokoll neu starten.

Es gibt bereits ein Projekt namens BBChop, das von Ealdwulf Wuffinga auf Github erstellt wurde und etwas Ähnliches unter Verwendung von Bayesscher Suchtheorie tut [9]

Aber BBChop ist unabhängig von jedem VCS und es wäre für Git-Benutzer einfacher, etwas in Git integriert zu haben.