Für's Code-Review mit andernorts arbeitenden Kollegen eignet sich
das Skript hd, das Dateiunterschiede farbig im Web-Browser anzeigt.
Jeder kennt diff, die praktische Unix-Utility, die die Differenzen
zwischen Dateien anzeigt. Und sdiff, das den GNU diffutils
([2]) beiliegt, stellt sogar zwei Dateien direkt nebeneinander
und kennzeichnet die Unterschiede, sodass man genau sehen kann, wo
sich zum Beispiel im C-Source-Code eines Programms etwas geändert hat.
Abbildung 1 zeigt eine typische C-Datei vor und nach einigen Änderungen. Direkt nebeneinandergestellt lassen sich die Unterschiede nur schwer erkennen. Schön ausgerichtet und farblich unterlegt wie in Abbildung 2 hingegen wird schnell klar, welche Zeilen gleich blieben, welche eingefügt, gelöscht oder verändert wurden.
| |
| Abbildung 1: Orginal- und modifizierte Datei |
 |
| Abbildung 2: Graphisches Diff |
Das heute und in der nächsten Ausgabe besprochene
CGI-Skript hd (für HTML-Diff) tut genau dies -- in
einem Webbrowser.
Führt man eine Änderung durch, sendet man für's Code-Review (Stichwort: ``Ekschtriem Brogramming'') einfach die URL per AIM oder Email herum und holt sich eine zweite Meinung darüber ein, ob der ``schnelle Fix'', den man gerade anbrachte, tatsächlich das gewünschte tut oder aber unerwünschte Seiteneffekte auslöst.
Außerdem unterstützt
hd auch das für die Versionskontrolle großer
Projekte weit genutzte CVS. Es vergleicht nicht nur ordinäre Dateien,
sondern auch verschiedene Revisionen derselben Datei in CVS oder
die lokale Arbeitskopie mit der eingecheckten Version.
Ausgehend von einem uralten Skript namens hdiff,
das bei Netscape in irgendeiner
verstaubten Schublade lag und an dem neulich jemand herumschraubte,
dachte ich mir: Es muesste doch mit schlauen Modulen wie
Algorithm::Diff möglich sein, das Ganze in neuem Perl zu schreiben!
Gesagt, getan. Heute besprechen wir den Algorithmus, der
Änderungen so schön sichtbar macht und nächstes Mal kommt
das zugehörige CGI-Skript dran.
diffWas versteht eigentlich ein intelligentes Wesen unter dem ``Unterschied
zwischen zwei Dateien''? Die Entwickler von diff haben darüber lange
und scharf nachgedacht und kamen nach [3] mit folgender Lösung daher:
Ähneln sich beide Dateien stark, liegt es nahe, zuerst
die Gemeinsamkeiten festzustellen und dann eine Strategie zu entwickeln,
die eine Datei in die andere überzuführen, indem man bestimmte Zeilen
löscht, einfügt oder ändert.
Oder, konkreter gesprochen, worin besteht der Unterschied zwischen diesen beiden Reihen:
1: a b c d e f g Y h i
2: a b c X e f g h Z i
Es sticht ins Auge, dass X, Y und Z nicht ins Bild passen. Das Gehirn
erkennt die Sequenzen abc und efg und rattert los: ``Wenn ich
Reihe 1 hernehme und in ihr
d durch X ersetze, Y lösche und Z einfüge,
erhalte ich Reihe 2. Demnach ist der Unterschied zwischen Reihe 1 und
Reihe 2 einfach die Folge dieser Operationen''.
Seite an Seite dargestellt, zeigt sich die Überführung anschaulicher:
1: a b c d e f g Y h i
2: a b c X e f g h Z i
Dies ist genau das Format, indem wir uns die farblich unterlegte
Ausgabe von hd wünschen,
wenn es die alte und die neue Version einer Programmdatei anzeigt
(Abbildung 3).
Zum Glück gibt es schon einen Algorithmus, der die Gemeinsamkeiten
zweier Reihen als sogenannte LCS (longest common subsequence) erkennt.
Mark-Jason Dominus hat ihn im Modul Algorithm::Diff implementiert
und bietet eine Funktion traverse_sequences() an, deren Aufruf außer zwei
Arrayreferenzen auf die beiden Reihen
auch noch eine Referenz auf einen Hash entgegennimmt, der Funktionen
festlegt, die traverse_sequences() während des Durchlaufs anspringt:
traverse_sequences(
\@a1, \@a2,
{ MATCH => \&m_cback,
DISCARD_A => \&a_cback,
DISCARD_B => \&b_cback,
} );
Die LCS der oben dargestellten Reihen ist abcefghi. Dies ist beileibe
nicht immer so einfach, wie im Beispiel oben, da der erste Eindruck
der Gemeinsamkeiten manchmal schwer täuscht, aber das braucht uns
nicht zu kümmern, da der Algorithmus zuverlässig die Arbeit übernimmt.
Man stelle sich nun zwei Zeiger vor, die die beiden Reihen von links nach rechts Element für Element durchwandern. Hierbei gelten folgende Regeln:
traverse_sequence() den MATCH-Callback
auf und schiebt beide Zeiger um eins weiter nach rechts.
Steht ein Zeiger auf einem Element, das nicht zur LCS gehört (wie zum Beispiel
Element X in Reihe 2), ruft traverse_sequence() den
DISCARD_A- oder DISCARD_B-Callback auf, je nachdem ob es sich um den Zeiger
in Reihe 1 oder Reihe 2 handelt. Anschließend wandert der entsprechende
Zeiger um Eins weiter nach rechts.
 |
| Abbildung 3: Der Diff-Algorithmus in Aktion |
In beiden Fällen erhalten die Callback-Funktionen die Indexpositionen der beiden Zeiger mitgeteilt. Für das Beispiel oben ergibt sich folgende Callback-Sequenz:
MATCH: 0 0
MATCH: 1 1
MATCH: 2 2
DISCARD_A: 3 3
DISCARD_B: 4 3
MATCH: 4 4
MATCH: 5 5
MATCH: 6 6
DISCARD_A: 7 7
MATCH: 8 7
DISCARD_B: 9 8
MATCH: 9 9
Abbildung 2 zeigt, wie die Funktion die kritische Stelle um die Indexposition 3 abarbeitet. Wären die Buchstaben im Beispiel die Zeilen einer Datei, wollten wir sie nach Abbildung 4 darstellen.
 |
| Abbildung 4: Graphisches Diff |
Mit folgendem Regelsatz lässt sich die Ausgabe oben leicht in in die grafische Darstellung umwandeln:
MATCH blieb die Zeile unverändert. Linke und rechte
Spalte der Ausgabe geben die jeweilige Zeile der Ursprungs- und Zieldatei an.
Ein einzelnes DISCARD_A indiziert, dass eine Zeile in der Ursprungsdatei
gelöscht wurde. Die graphische Diff-Ausgabe zeigt links die Originalzeile
und rechts eine Leerzeile.
Ein einzelnes DISCARD_B signalisiert, dass eine Zeile zur Ursprungsdatei
hinzugefügt wurde. Die graphische Diff-Ausgabe zeigt links eine Leerzeile
und rechts die neue Zeile.
Folgt ein DISCARD_B direkt auf ein DISCARD_A (oder umgekehrt),
handelt es sich nicht um zwei separate Aktionen, die Zeilen löschen
oder hinzufügen, sondern um eine einzige Änderungsaktion.
Die grafische Ausgabe zeigt links die alte und rechts die neue Zeile.
Listing SDiff.pm zeigt ein Modul
mit der Implementierung der zentralen Routine
sdiff(). hd wird nächtes
Mal mit use SDiff einfach das heute vorgestellte Modul hereinziehen
und dessen Funktionalität nutzen.
Wie jedes ordentlich programmierte Modul führt SDiff.pm eine
mittels our deklarierte Versions-Variable $VERSION, die
auf 0.01 steht.
Da SDiff.pm mittels des @ISA-Arrays in Zeile
8 von den Standard-Modulen Exporter und AutoLoader erbt und
im Array @EXPORT_OK die Routine sdiff aufführt, kann das Skript
nächstes Mal mittels
use SDiff qw( sdiff );
die Funktion sdiff() in ihren Namensraum importieren und
einfach sdiff() aufrufen ohne explizit SDiff::sdiff() zu spezifizieren.
sdiff in SDiff.pm
nimmt als Parameter unter anderem
zwei Referenzen auf Arrays entgegen, deren Elemente die Zeilen der
beiden zu vergleichenden Dateien enthalten.
Es gibt die
als $a1 und $a2 gespeicherten Referenzen an
traverse_sequences() weiter
und definiert zusätzlich noch
die Callbacks für die Ereignisse MATCH, DISCARD_A und DISCARD_B.
01 ###########################################
02 # SDiff.pm
03 # Mike Schilli, 2002 (m@perlmeister.com)
04 ###########################################
05
06 require Exporter;
07 our $VERSION = "0.02";
08 our @ISA = qw(Exporter AutoLoader);
09 our @EXPORT_OK = qw( sdiff );
10
11 use Algorithm::Diff qw(traverse_sequences);
12
13 ###########################################
14 sub sdiff {
15 ###########################################
16 my($a1, $a2, $setr, $context,
17 $ignore_blanks) = @_;
18
19 my (@res, $prev);
20
21 $prev = "";
22 @res = ();
23
24 traverse_sequences( $a1, $a2, {
25
26 MATCH => sub {
27 my($i,$j) = @_;
28 push @res,
29 [$a1->[$i], $a2->[$j], "u"];
30 $prev = "MATCH";
31 },
32
33 DISCARD_A => sub {
34 my($i,$j) = @_;
35 if($prev eq "DISCARD_B") {
36 $res[$#res]->[0] = $a1->[$i];
37 $res[$#res]->[2] = "c";
38 } else {
39 push @res, [$a1->[$i], "", "d"];
40 mark_window($setr, $#res,
41 $context) if $setr;
42 }
43 $prev = "DISCARD_A";
44 },
45
46 DISCARD_B => sub {
47 my($i,$j) = @_;
48 if($prev eq "DISCARD_A") {
49 $res[$#res]->[1] = $a2->[$j];
50 $res[$#res]->[2] = "c";
51 } else {
52 push @res, ["", $a2->[$j], "i"];
53 mark_window($setr, $#res,
54 $context) if $setr;
55 }
56 $prev = "DISCARD_B";
57 },
58 },
59 $ignore_blanks ? sub {
60 ($_ = $_[0]) =~ s/\s+//g;
61 return $_; }
62 : undef );
63
64 # Limit set to extent of array
65 if($setr) {
66 $$setr = $$setr->intersect("0-$#res");
67 }
68
69 return \@res;
70 }
71
72 ###########################################
73 sub mark_window {
74 ###########################################
75 my($setr, $idx, $window) = @_;
76
77 my $from = $idx - $window;
78 $from = 0 if $from < 0;
79 my $to = $idx + $window;
80 $$setr = $$setr->union("$from-$to");
81 }
82
83 1;
Im Array @res legt sie das Ergebnis der Berechnung ab -- jedes Element
dort
ist eine Referenz auf ein Array mit drei Elementen: die linke und die
rechte Spalte für die graphische Diff-Anzeige, sowie ein drittes Element,
das mit 'i', 'd', 'u' oder 'c' anzeigt, ob eine neue Zeile eingefügt
(insert), eine alte gelöscht (delete), die aktuelle Zeile
unverändert (unmodified) blieb oder sich änderte (changed).
Weil der Algorithmus statt einer 'c'-Aktion eine delete und eine
insert-Aktion liefert, muss sich sdiff() and die letzte Aktion
erinnern, um nötigenfalls eine DISCARD_A-DISCARD_B-Folge in eine
'c'-Aktion überzuführen.
Deshalb
speichert der der Skalar $prev stets das Ereignis
("MATCH", "DISCARD_A" oder "DISCARD_B") ab.
Der MATCH-Callback, der ab Zeile 25 definiert ist,
nimmt zunächst die beiden übergebenen Indizes als
$i und $j entgegen. Da bei einem MATCH Quell-
und Zielzeile offensichtlich unverändert sind, erzeugt
Zeile 28 einfach einen anonymen Array aus beiden samt
angehängtem Aktionsindikator 'u' und stellt diesen ans Ende des
Ergebnisarrays @res. Zeile 29 merkt sich in $prev, was
abgelaufen ist, falls die nächste Aktion nachsehen will,
was passiert ist.
Der DISCARD_A-Callback ab Zeile 32 prüft zunächst in Zeile
34, ob die letzte Aktion nicht etwa ein DISCARD_B-Callback war.
Falls dem so ist, liegt keine Löschungsaktion vor, sondern eine
Änderung der gegenwärtigen Zeile. Mit
res[$#res] greift es sich das Ergebnis der vorangegangenen
Aktion und stopft in die erste Spalte (die die letzte Aktion
irrtümlich leer ließ, da sie eine Einfügeaktion vermutete) den
Wert der gegenwärtigen ersten Spalte: Es fasst also beide
DISCARD-Aktionen zu einer einzigen Change-Aktion zusammen.
Zeile 36 setzt auch noch den passenden 'c'-Merker.
Falls die letzte Aktion kein DISCARD_B-Callback war,
liegt offensichtlich eine ganz normale Zeilenlöschung vor. Zeile
38 legt in der ersten Spalte den Zeilenwert der ersten Datei ab,
lässt die zweite Spalte leer und setzt den Aktionsmerker auf
'd' (delete). Zeile 42 merkt sich das Ergebnis in
$prev, auf das vielleicht der nächste Callback wieder
zugreift. Die in Zeile 39 aufgerufene Funktion mark_window()
besprechen wir weiter unten.
Die ab Zeile 45 definierte Funktionsreferenz zum
DISCARD_B-Ereignis läuft genau spiegelbildlich ab: War das
vorhergehende Ereignis eine DISCARD_A-Aktion, liegt eine
Change-Aktion vor und der letzte Eintrag in @res wird korrigiert,
andernfalls klatscht sie einen neuen Eintrag ans Ende von @res.
Haben sich in einem 1000-Zeilen-Listing
nur die Zeilen 525-527 und 702 verändert,
wäre es vielleicht übertrieben, ein Diff mit dem gesamten Listing
darzustellen. Vielmehr soll die Funktion sdiff() zusätzlich zu den
eigentlichen Änderungen Kontextfenster angeben, in denen sie sich abspielten.
Als Kontextfenster definieren wir einen Zeilenbereich,
der außer den geänderten Zeilen auch noch die fünf
vorhergehenden und die fünf nachfolgenden unveränderten Zeilen enthält.
Im Beispiel wären dies 520-524,525-527,528-532,697-701,702,703-707
oder zusammengefasst 520-532,697-707 als ``interessante'' Zeilen.
Für diese sogenannte Run-List nutzt sdiff() das praktische Modul
Set::IntSpan vom CPAN, mit dem man einfach ganzzahlige Bereiche angeben und
manipulieren kann. Einem mit
$set = Set::IntSpan->new();
definierten Set kann man mittels
# Bereich 5-13 einfügen
$set->union("5-13");
# 31 einfügen
$set->union("31");
neue Bereiche/Einzelwerte zufügen und andererseits mittels
# Schnittmenge bilden
$set->intersect("1-100");
Schnittmengen bilden (Mengenlehre!), also die definierten Bereiche begrenzen.
sdiff() nimmt hierzu in der Argumentliste zwei vorher nicht erwähnte
Parameter entgegen: $setr, eine Referenz auf eine Referenz auf ein
Objekt vom Typ Set::IntSpan und $context, die Anzahl der den
geänderten Bereich umgebenden Kontext in einer Richtung, also 5.
Die Doppel-Referenz ist deshalb notwendig, da Set::IntSpan-Objekte
sich nicht wie üblich mittels
einer Objektreferenz manipulieren lassen -- vielmehr geben
die Methoden als Ergebnis Referenzen auf neue Objekte zurück.
Da sdiff aber die
hereingereichte Objektreferenz im Auftrag des Hauptprogramms
modifizieren muss, brauchen wir einen ``Pointer'' darauf.
Innerhalb von sdiff() greifen wir deshalb mittels $$setr
auf die eigentlich Objektreferenz zu.
Wann immer sdiff() auf eine veränderte
Zeile stößt, fügt sie mittels der Funktion
mark_window() einen Bereich von Zeilennummer-5 bis
Zeilennummer+5 in die Run-List setr ein.
mark_window() nimmt hierzu die Doppelreferenz auf das Set::IntSpan-Objekt,
den Index der Zeile und die einfache Länge des Kontextfensters (5)
entgegen und manipuliert das Set -- wobei es achtgibt, dass die
Indizes nicht unter 0 fallen.
Auf das Ende des Arrays kann es nicht achten, da dessen Länge zum
aktuellen Zeitpunkt noch gar nicht feststeht.
So kann es am Ende von sdiff() durchaus sein, dass die Run-List
die Länge des eigentlichen Diff-Arrays um bis zu 5 Elemente
überschreitet und deswegen bildet Zeile 61 eine Schnittmenge
mit einem Bereich, der exakt dem Ausmaß des Diff-Arrays entspricht.
Zeile 64 schließlich gibt eine Referenz auf das Ergebnisarray an das aufgeregt wartende Hauptprogramm zurück, das dann die einfach die grafische Aufbereitung übernimmt. Und das kommt beim nächsten Mal dran! Bis denne!
Algorithm::Diff von Mark-Jason Dominus
 |
Michael Schilliarbeitet als Software-Engineer bei Yahoo! in Sunnyvale, Kalifornien. Er hat "Goto Perl 5" (deutsch) und "Perl Power" (englisch) für Addison-Wesley geschrieben und ist unter mschilli@perlmeister.com zu erreichen. Seine Homepage: http://perlmeister.com. |