Wie Diff funktioniert: Unified-Diff-Format, der Myers-Algorithmus und Patches flüssig lesen

git diff, Code-Review, Patch-Dateien, Merge-Konflikte — das Arbeitsleben eines Entwicklers wird von Diffs gerahmt. Die meisten von uns lesen sie täglich, ohne je zu fragen, wie sie entstehen, und das funktioniert gut, bis zu dem Tag, an dem es das nicht mehr tut: ein Diff, der behauptet, Sie hätten eine Funktion neu geschrieben, die Sie nur verschoben haben, ein Merge-Konflikt, der keinen Sinn ergibt, oder ein 10.000-Zeilen-Patch für eine Wortänderung. Diese Anleitung erklärt, was tatsächlich vor sich geht: der Algorithmus, der die Differenz findet, das Unified-Format, das sie kodiert, und warum Diffs manchmal „falsch“ aussehen, obwohl sie technisch korrekt sind.

Das Problem, das Diff wirklich löst

Bei zwei Dateien klingt „der Unterschied“ offensichtlich, bis man versucht, ihn zu definieren. Ändern Sie eine Zeile in der Mitte — einfach. Aber verschieben Sie einen Absatz von oben nach unten, und plötzlich gibt es viele gültige Beschreibungen: hier 40 Zeilen löschen, dort 40 Zeilen einfügen — oder die 3 Zeilen darüber löschen, sie darüber neu einfügen — und so weiter, exponentiell viele. Ein Diff-Werkzeug muss eine wählen, und das vernünftige Kriterium ist: das kleinstmögliche Bearbeitungsskript — die wenigsten Zeileneinfügungen und -löschungen, die Datei A in Datei B verwandeln.

Mathematisch umformuliert ist das das Problem der längsten gemeinsamen Teilfolge (LCS). Finden Sie die längste Zeilenfolge, die in beiden Dateien in derselben Reihenfolge vorkommt (nicht zwingend zusammenhängend), ist alles Übrige der Diff: Zeilen in A, aber nicht in der LCS, sind Löschungen; Zeilen in B, aber nicht in der LCS, sind Einfügungen. Minimale Änderungen = maximale gemeinsame Zeilen.

Myers: Der Algorithmus hinter Git Diff

LCS naiv zu berechnen ist quadratisch in Zeit und Speicher — für einen Absatz in Ordnung, für eine 50.000-Zeilen-Datei schmerzhaft. Der Algorithmus, den Git nutzt, 1986 von Eugene Myers veröffentlicht, findet das minimale Bearbeitungsskript in O((N+M)·D) Zeit, wobei D die Größe des Unterschieds selbst ist. Die praktisch entscheidende Konsequenz: Die Diff-Kosten skalieren mit dem Ausmaß der Unterschiede, nicht nur mit der Größe der Dateien. Zwei fast identische riesige Dateien diffen schnell; zwei völlig verschiedene kleine ebenso; der schlimmste Fall sind große Dateien mit großen Änderungen.

Myers’ Einsicht ist elegant: Bauen Sie ein Raster, dessen X-Achse Datei A und dessen Y-Achse Datei B ist, und die minimale Differenz zu finden wird zum Finden eines kürzesten Pfads von Ecke zu Ecke — nach rechts (Löschung), nach unten (Einfügung) oder diagonal (passende Zeile, kostenlos). Gits Implementierung ergänzt Heuristiken — etwa Hunk-Verschiebung, damit Änderungen an Leerzeilen und Funktionsgrenzen ausgerichtet werden —, weshalb sich die Ausgabe meist natürlich liest.

Unified Diff lesen: Das Format entschlüsselt

Das Unified-Diff-Format (was git diff und diff -u ausgeben) packt das Bearbeitungsskript in kompakten, menschenlesbaren Text. Die Anatomie eines Hunks:

--- a/src/config.js
+++ b/src/config.js
@@ -10,7 +10,7 @@ function loadConfig() {
   const env = getEnv();
-  const timeout = 3000;
+  const timeout = 5000;
   return { env, timeout };
 }

• --- a/... / +++ b/... — die „Vorher“- und „Nachher“-Dateien (die Präfixe a/ und b/ sind eine Git-Konvention).
• @@ -10,7 +10,7 @@ — der Hunk-Kopf: Dieser Hunk beginnt bei Zeile 10 in der alten Datei (über 7 Zeilen) und Zeile 10 in der neuen (ebenfalls 7 Zeilen). Unterscheiden sich die Anzahlen, z. B. -10,7 +10,9, hat der Hunk netto zwei Zeilen hinzugefügt. Der Text nach dem zweiten @@ ist ein Kontexthinweis, meist die umgebende Funktion.
• (Leerzeichen) — Kontextzeile, in beiden Dateien vorhanden.
• - — Zeile entfernt; + — Zeile hinzugefügt. Eine geänderte Zeile erscheint immer als -/+-Paar: Es gibt keine „Änderungs“-Operation, nur Löschen + Einfügen.

Standardmäßig erhalten Sie 3 Zeilen Kontext über und unter jeder Änderung; git diff -U10 erweitert ihn, und Werkzeuge wie unser Diff Checker rendern dieselbe Information nebeneinander mit Hervorhebung, was für lange Prosa- oder Config-Vergleiche oft leichter ist als das rohe Patch-Format.

Warum Diffs manchmal falsch aussehen

Den Algorithmus zu verstehen erklärt die klassischen Ärgernisse:

• „Ich habe nur eine Funktion verschoben, aber der Diff zeigt eine Neuschreibung.“ Zeilenbasierter Diff kennt kein Verschieben — ein Verschieben ist buchstäblich Löschen plus Einfügen. Manche Werkzeuge erkennen verschobene Blöcke heuristisch (Git hat git diff --color-moved), aber das zugrunde liegende Bearbeitungsskript kann „verschoben“ nicht ausdrücken.
• Diff-Rauschen durch Neuformatierung. Formatiert ein Tool die Datei neu ein, ist jede berührte Zeile eine Änderung — das minimale Bearbeitungsskript meldet getreulich, dass diese 2.000 Zeilen tatsächlich verschieden sind. Whitespace-unempfindliche Modi (git diff -w) existieren genau dafür.
• Ein besserer Diff existierte, wurde aber nicht gefunden. Die Kürzester-Pfad-Suche ist an exakt übereinstimmenden Zeilen verankert. Haben Sie jede Zeile leicht geändert (in jeder eine Versionsnummer hochgezählt), kollabiert die LCS, und der Diff verfällt zu „alles löschen, alles einfügen“ — korrekt, aber nutzlos.
• JSON und andere strukturierte Daten. Zeilenbasierter Diff von formatiertem JSON ist ordentlich, aber ordnen Sie einen Schlüssel um, und das Rauschen übertönt die echte Änderung. Strukturbewusste Werkzeuge vergleichen geparste Werte statt Text: unser JSON Diff zeigt, welche Schlüssel und Werte sich tatsächlich geändert haben, unabhängig von Schlüsselreihenfolge oder Formatierung — das richtige Werkzeug bei strukturierten Daten.

Praktische Tipps

• Kleine, fokussierte Commits sind nicht nur Hygiene — sie sind Diff-Ergonomie. Reviewer (und Sie selbst später) lesen Bearbeitungsskripte; je kleiner D, desto klarer die Geschichte.
• Rename-Erkennung (git status zeigt renamed:) ist eine Ähnlichkeitsheuristik, die nach dem Diffen angewendet wird, keine Magie: Git diffed die Löschung gegen alle Einfügungen und paart die ähnlichste.
• Für Prosa und Doku ist ein Diff auf Wortebene (oder --word-diff in Git) meist lesbarer als auf Zeilenebene.
• Die inverse Operation ist patch / git apply: ein Unified Diff plus ein sauberer Kontext-Match genügt, um die Änderung erneut anzuwenden — weshalb es die Kontextzeilen überhaupt gibt. Sie sind der Anker, der Patches kleine Abweichungen in der Zieldatei überleben lässt.

Kurzreferenz

• Diff = minimales Einfüge-/Löschskript = Komplement der längsten gemeinsamen Teilfolge.
• Myers’ Algorithmus: Kosten skalieren mit der Größe des Unterschieds, kürzester Pfad auf einem Bearbeitungsraster; das führt git diff aus.
• @@ -a,b +c,d @@ = alter Start,Anzahl / neuer Start,Anzahl; - löschen, + einfügen, Leerzeichen Kontext; eine „geänderte“ Zeile ist ein -/+-Paar.
• Verschiebungen existieren im Diff nicht — sie sind Löschen + Einfügen; Neuformatierung ist von Neuschreiben nicht zu unterscheiden.
• Strukturierte Daten verdienen einen strukturellen Diff: geparstes JSON vergleichen, nicht Textzeilen.