Text-Diff-Algorithmen: Wie Git, Patches und Diff-Tools funktionieren

Jedes Code-Review-Tool, jede git diff-Ausgabe, jede Patch-Datei, die Sie je gelesen haben, geht auf eine kleine Zahl von Algorithmen zurück, die zwischen 1976 und 2009 erfunden wurden. Zu wissen, welchen Ihr Tool verwendet — und welche Annahme er trifft — entscheidet darüber, ob Sie ein Diff in 30 Sekunden lesen oder zehn Minuten verwirrt darauf starren und sich fragen, ob der Refactor das Verhalten tatsächlich erhalten hat.

Was ein Diff tatsächlich ist

Ein Diff ist ein Edit-Skript: eine minimale Folge von Einfügungen und Löschungen, die Datei A in Datei B umwandelt. Für zwei Dateien der Gesamtlänge N mit D Unterschieden gibt es viele mögliche Skripte. Ein Diff-Algorithmus wählt eines nach einem Optimierungskriterium — meist das kleinste D, aber nicht immer.

Daraus folgen zwei Schlussfolgerungen. Erstens kann dieselbe Dateiänderung mit verschiedenen Tools legitim unterschiedlich aussehende Diffs erzeugen; sie sind alle in dem Sinne korrekt, dass ihre Anwendung Datei B rekonstruiert. Zweitens ist “lesbares Diff” eine schwächere Bedingung als “kleinstes Diff”, und die beiden widersprechen sich oft. Sie können zwei Dateien selbst mit unserem Text-Diff-Tool vergleichen und die Unified-Ausgabe nebeneinander sehen.

Myers-Diff — der Standard überall

Eugene Myers' Arbeit von 1986 An O(ND) Difference Algorithm and Its Variations definierte den Algorithmus, den GNU diff, Git, Mercurial, SVN und die meisten Editoren bis heute standardmäßig verwenden. Sie fasst das Diff-Problem als Suche nach dem kürzesten Pfad durch einen Edit-Graphen auf: Jeder diagonale Schritt ist eine passende Zeile, jeder horizontale Schritt löscht eine Zeile aus A, jeder vertikale Schritt fügt eine Zeile aus B ein. Der kürzeste Pfad entspricht dem Skript mit minimaler Bearbeitung.

Die Zeitkomplexität ist O(N × D), wobei N die Gesamtdateilänge und D die Anzahl der Unterschiede ist. Für typische Quelldateien mit kleinen Änderungen ist der Algorithmus im Wesentlichen linear; für Dateien, die von Grund auf neu geschrieben wurden, verschlechtert er sich, weshalb Git die Analyse mit den Standardwerten diff.algorithm und diff.renameLimit begrenzt.

Myers' Schwäche ist, dass er die Diff-Größe ohne jedes Strukturgefühl minimiert. Nach dem Verschieben eines Codeblocks paart Myers oft die schließende Klammer einer Funktion mit der schließenden Klammer einer anderen, weil das weniger geänderte Zeilen insgesamt ergibt. Das Ergebnis ist technisch minimal und menschlich verwirrend.

Patience-Diff — auf Lesbarkeit ausgelegt

Bram Cohen (der Autor von BitTorrent) führte 2007 das Patience-Diff ein, speziell um Myers' Refactor-Lesbarkeitsproblem zu beheben. Der Algorithmus:

1. Finde alle Zeilen, die in beiden Dateien genau einmal vorkommen. Das sind eindeutige Ankerzeilen.
2. Berechne die längste gemeinsame Teilsequenz der eindeutigen Anker (mit dem Patience-Sort-Algorithmus — daher der Name).
3. Vergleiche rekursiv jeden Bereich zwischen aufeinanderfolgenden Ankern mit demselben Verfahren und falle auf Myers zurück, wenn keine eindeutigen Anker mehr übrig sind.

Das Ergebnis richtet das Diff an den Zeilen aus, die ein Mensch als “dasselbe” erkennen würde — Funktionssignaturen, eindeutige Kommentare, Klassendeklarationen. Patience ist im schlimmsten Fall langsamer als Myers, erzeugt aber für typische Codeänderungen weit lesbarere Ausgaben. Aktivieren Sie es in Git mit git diff --patience oder global mit git config diff.algorithm patience.

Histogram-Diff — Patience, verfeinert

Das Histogram-Diff wurde von JGit (der Java-Git- Implementierung) eingeführt und später in den Upstream-Git portiert. Es verbessert Patience, indem es klüger bei der Wahl der Ankerzeilen ist: Statt Eindeutigkeit zu verlangen, wählt es die seltenen Zeilen mit der niedrigsten Häufigkeitszahl in beiden Dateien. Häufige Zeilen (schließende Klammern, Leerzeilen) werden zurückgestuft; seltene Zeilen (Funktionsnamen, markante Zeichenketten) werden zu Ankern.

Histogram ist heute der empfohlene Standard für die meisten Repositorys. Es erzeugt für typische Fälle eine Ausgabe ähnlich Patience und merklich bessere für Dateien mit vielen wiederholten Zeilen (etwa Datendateien, Fixtures und Konfiguration mit viel Einrückung). Aktivieren Sie es global mit git config --global diff.algorithm histogram.

Einen Unified-Diff-Hunk lesen

Das Unified-Diff (-u) ist das De-facto- Austauschformat. Ein Hunk sieht so aus:

@@ -42,7 +42,9 @@ class UserController {
   const user = await User.findById(id);
   if (!user) {
-    return res.status(404).end();
+    logger.warn({ id }, "user not found");
+    return res.status(404).json({ error: "not found" });
   }
   return res.json(user);
 }

Die @@-Zeile ist der Hunk-Header. Sie sagt: Die alte Datei beginnt bei Zeile 42 und umfasst 7 Zeilen; die neue Datei beginnt bei Zeile 42 und umfasst 9 Zeilen. Der nachfolgende Text nach dem zweiten @@ ist eine Abschnittsüberschrift — bei Code ist das meist die umschließende Funktion oder Klasse, von Git anhand einer sprachspezifischen Heuristik gewählt.

Zeilen ohne Präfix sind unveränderter Kontext. Zeilen, die mit - beginnen, existieren nur in der alten Datei; Zeilen, die mit + beginnen, nur in der neuen. Der Standardkontext beträgt drei Zeilen auf jeder Seite; -U10 erweitert ihn, nützlich, wenn die Wirkung der Änderung von einer Anweisung knapp außerhalb des Sichtfelds abhängt.

Leerzeichen und Zeilenenden

Die größte Einzelquelle verwirrender Diffs sind Leerzeichen. Häufige Übeltäter:

• Abschließende Leerzeichen. Ein Editor, der abschließende Leerzeichen beim Speichern entfernt, markiert jede berührte Zeile. Konfigurieren Sie core.whitespace und git diff --ignore-space-at-eol, um das Diff auf echte Änderungen zu fokussieren.
• Gemischte Einrückung. Der Wechsel von Tabs zu Leerzeichen (oder umgekehrt) ist ein Gesamtdatei-Diff, selbst wenn sich keine Logik geändert hat. Verwenden Sie git diff -w, um beim Review solcher Änderungen alle Leerzeichenunterschiede zu ignorieren.
• Zeilenenden. CRLF- vs. LF-Unterschiede lassen jede Zeile verändert aussehen. Richten Sie .gitattributes mit * text=auto ein, um beim Commit zu normalisieren.
• Abschließender Zeilenumbruch. Dateien ohne abschließenden Zeilenumbruch zeigen \ No newline at end of file im Diff. Manche Tools fügen den Zeilenumbruch beim Speichern stillschweigend hinzu und erzeugen einzeilige Diffs, die wie Rauschen aussehen.

Binärdateien

Diff-Algorithmen arbeiten auf Zeilen. Dateien ohne natürliche Zeilenumbrüche — Bilder, ausführbare Dateien, PDFs — erzeugen nutzlose Ausgaben, wenn sie textuell verglichen werden. Git erkennt Binärinhalte durch die Suche nach Nullbytes in den ersten 8 KB; wird etwas gefunden, reduziert sich das Diff auf Binary files a/x and b/x differ.

Für Binärinhalte, die vergleichbar sein sollten(DOCX, XLSX, Designdateien), kann .gitattributes einen benutzerdefinierten textconv-Filter registrieren, der die Datei vor dem Diff in eine textuelle Darstellung umwandelt. diff=word, diff=exif und ähnliche eingebaute Filter werden mit Git ausgeliefert.

Drei-Wege-Merge und warum Konflikte entstehen

Wenn Sie Branch B in Branch A mergen, betrachtet Git drei Versionen: den gemeinsamen Vorfahren C, die A-Version und die B-Version. Der Merge verläuft Zeile für Zeile:

• Zeile von C zu A unverändert, aber in B geändert → nimm B.
• Zeile in A geändert, aber in B unverändert → nimm A.
• Zeile in beiden identisch geändert → nimm eine; kein Konflikt.
• Zeile in A und B unterschiedlich geändert → Konflikt.

Konflikte werden in der Arbeitsdatei mit den Markern <<<<<<<, ======= und >>>>>>> markiert, die beide Versionen zeigen. Die Vorfahrenversion lässt sich mit merge.conflictStyle diff3 ebenfalls einbeziehen, was die Auflösung erheblich erleichtert, weil Sie sehen, wovon jede Seite ausgegangen ist.

Einen Algorithmus in der Praxis wählen

Für die tägliche Arbeit ist Histogram der beste Standard und der, den die meisten Teams global konfigurieren sollten. Patience liefert sehr ähnliche Ergebnisse und bleibt nützlich für sehr große Dateien, bei denen Histograms Speicherverbrauch spürbar wird. Myers ist die richtige Wahl für Maschine-zu-Maschine-Pipelines, die Diffs programmatisch verarbeiten, weil seine Ausgabe das kanonische Minimum ist.

Code-Review-Tools (GitHub, GitLab, Gerrit) verwenden alle aus Legacy-Gründen standardmäßig Myers; ihre Oberflächen bieten die Algorithmuswahl nicht immer an. Wenn ein Review-Diff verschoben aussieht, laden Sie den Patch herunter und rendern Sie ihn lokal neu mit git diff --histogram — das Ergebnis ist oft viel leichter zu lesen.

Das ehrliche Fazit

Stellen Sie Ihren globalen Git-Algorithmus auf Histogram um und denken Sie für die meisten Repositorys nie wieder daran. Wenn ein Diff Sie nach einem Refactor verwirrt, rendern Sie es mit einem anderen Algorithmus neu, bevor Sie annehmen, die Änderung sei falsch. Normalisieren Sie Leerzeichen und Zeilenenden auf Repository-Ebene, damit Reviewer ihre Zeit mit Logik verbringen, nicht mit Formatierung. Und denken Sie daran: Das Diff ist eine Darstellung, nicht die Wahrheit — die Wahrheit sind die beiden Dateien, und ein Diff ist nur eine von vielen gültigen Arten, den Weg dazwischen zu beschreiben.