Unterschiede von quellcode-versionen erkenne?

[Sharky]

Hai ihr lieben,

ich arbeite zur Zeit an meinem kleinen, privaten Code-Verwaltungs-System.
Jetzt wollte ich gerne eine Funktionalität haben wie sie z.B in D2005 in der History-Funktion ist.
Ich habe also einen Referenzcode

Delphi-Quellcode:

begin
  if (blubb) then
  begin
    Mache_Etwas;
  end
end;

in der nächsten "Version" steht nun:

Delphi-Quellcode:

begin
  if (meow) then
  begin
    Mache_Etwas_Ganz_Anderese();
  end
end;

Diese Änderungen im Code möchte ich nun gerne optisch hervorheben.
Hat einer von euch eine Idee wie ich das am besten machen soll? (Info am Rande: Die einzelnen Code-Versionen werden in einer DB gespeichert).

[barf00s]

vllt hilft dir das hier ja ein wenig

http://www.ascotti.org/programming/lcs/lcs.htm

[Sharky]

Hai,

Zitat:

Zitat von barf00s

vllt hilft dir das hier ja ein wenig ...

nicht wirklich. ;-)

Ich kann mir jetzt zwar den Code ansehen.... aber das bringt mir nichts.
Wenn möglich möchte ich solche Fragen gerne innerhalb der DP klären. Dann haben nämlich auch andere etwas davon!

Verlinken kann jeder :roll:

[barf00s]

dann versteh ich dich nich -

[Bernhard Geyer]

Zitat:

Zitat von Sharky

Hai,

Zitat:

Zitat von barf00s

vllt hilft dir das hier ja ein wenig ...

nicht wirklich. ;-)

Und wieso nicht?
Solche Diff-Programme sind doch das übliche zum Quellcode-Vergleich. Habe sowas auch in meine eigene Versionsverwaltung eingebaut.

[Sharky]

Zitat:

Zitat von Bernhard Geyer

... Und wieso nicht? ...

Hai Bernhard,

wenn Du schon einen Text zitierst dann mane es doch auch so das der Zusammenhang erhalten bleibt.
Ich habe in meiner Antwort auf das Posting von barf00s doch genau gesagt warum mir der Link nicht richtig hilft.
Oder ist das zu schwer zu verstehen? (anstscheinend ist es so)
Ich sehe in dem Link keine mitelbare Antwort/Erklärung auf meine Frage.

[Sharky]

Zitat:

Zitat von barf00s

dann versteh ich dich nich -

Ja,
man merkt das Du nicht verstehst worum es diesem Forum geht :wall:

[barf00s]

warum sollte man denn in diesem forum den quelltext lang und breit diskutieren?
du hast nach etwas gefragt und ich hab dir eine mögliche lösung angeboten (dieses tool macht genau DAS was du brauchst - oder mit kleinen änderungen)

[dahead]

@thread-ersteller:

die wollen dir nur sagen, dass wenn du dir den source ankuckst, sicherlich die ein oder andere funktion für deine zwecke verwenden kannst.

aber das ist wohl nicht in deinem interesse?

[barf00s]

sharky wills ja anscheinend hier im forum _ausführlich_ breitgetreten haben, so das auch _andere_ sich des codes bedienen können ...

[dahead]

was ja nicht unbedingt verkehrt ist.

[alcaeus]

Hallo barf00s,

Zitat:

Zitat von barf00s

sharky wills ja anscheinend hier im forum _ausführlich_ breitgetreten haben, so das auch _andere_ sich des codes bedienen können ...

man koennte jetzt diese ganze Diskussion ueber Fertigloesungen breittreten, aber wenn Sharky keine fertige Loesung einfach so verwenden will, dann ist es seine Sache, und soll dich nicht weiter stoeren.
Also, halte dich bitte einfach zurueck.

@all: es geht in diesem Thread nicht darum, fertige Loesungen zu praesentieren, sondern das Prinzip dahinter zu verstehn. Glaubt mir, das aus einem fertigen Code rauszulesen ist nicht immer moeglich, geschweige denn sogar "leicht". Ich habs oft genug versucht ;)

Greetz
alcaeus

[ibp]

hai hai auch warme flossen?

ich kann dir dafür nur einen tipp geben angus johnsons textdiff (tdiff) die kannst du visuell und non visuell nutzen, incl. qc und algo-erklärung!

grüße aus der nachbarschaft!

[Bernhard Geyer]

Zitat:

Zitat von Sharky

Zitat:

Zitat von Bernhard Geyer

... Und wieso nicht? ...

Hai Bernhard,

wenn Du schon einen Text zitierst dann mane es doch auch so das der Zusammenhang erhalten bleibt.

Ok, etwas zu viel abgeschnitten.[/quote]

Zitat:

Zitat von Sharky

Ich habe in meiner Antwort auf das Posting von barf00s doch genau gesagt warum mir der Link nicht richtig hilft.
Oder ist das zu schwer zu verstehen? (anstscheinend ist es so)

Ja.

Wieso kannst du nicht eine bestehende Diff-Anwendung in deine Quellcode-Verwaltung einbauen? Du checkst die beiden Versionen aus und ruftst die Diff-Exe auf. Was stört dich daran bzw. was willst Du genau machen?

[Boombuler]

Hi,

ich denke das es nicht wirklich schwer ist wenn man folgende Probleme in den Griff bekommt:

1) Die Geschwindigkeit.

2) was macht man um sowas zu finden:

Delphi-Quellcode:

//Code 1:
Function Blub:boolean;
begin
  result := (GetTickCount > 100000);
end;

//Code 2:
Function Blub:boolean;
begin
  if (GetTickCount < 1000) then //Diese Zeile wird böse!
    result := (GetTickCount > 100000)
  else
    result := true;
end;

Deswegen solltest du dir überlegen ob du wenn du da durchgehst das Zeilenweise zu machen.
und wenn sich eine Zeile unterscheidet dann erst den Unterschied in der entsprechenden Zeile finden
und danach die Zeile finden die man mehr oder minder als die nächste Zeile verstehen kann!

Tipp von mir noch am Rande: Nimm vorher die Whitespaces raus. sonst wirst du zu viele Unterschiede finden, nur weil jemand meint etwas anders einrücken zu müssen usw!
Das macht das anzeigen ziehmlich unübersichtlich!

Greetz
Boombuler

PS: ich hoffe die grundüberlegungen helfen dir weiter!

[Flocke]

Das erste Problem ist das Diff, der theoretische Ansatz ist:

Code:

(die Endzeilen seinen jeweils exklusive)
Gegeben sind
1. z1von ... z1bis: der zu betrachtende Bereich aus Datei 1
2. z2von ... z2bis: der zu betrachtende Bereich aus Datei 2
Vorgehen:
3. Finde den längsten übereinstimmenden Block innerhalb des Bereichs:
     z1fund ... z1fund+zlaenge
     z2fund ... z2fund+zlaenge
4. Wenn zlaenge < Mindestlänge (z.B. 3)
   -> markiere den Bereich als nicht übereinstimmend
5. sonst
   -> Rufe die Funktion rekursiv auf mit den Blöcken davor und danach
    z1von ... z1fund und z2von ... z2fund
    z1fund+zlaenge ... z1bis und z2fund+zlaenge ... z2bis

Zur Beschleunigung der Geschwindigkeit arbeitet man dann mit Hashcodes, so dass man relativ schnell passende Zeilen findet und nicht alle immer wieder miteinander vergleichen muss.

Ich habe mir Anno '93 mal ein Diff-Programm selbst geschrieben (damals noch für DOS :angel2:), das auch große Dateien relativ schnell vergleichen konnte.

[Olli]

Vielleicht könnte man vorhandenes von WinMerge wiederverwenden. ZB als DLL?!

[Flocke]

Konnte nicht umhin mal was zu schreiben :mrgreen: (ist fast Wochenende und ich hatte etwas Zeit...)

Hier der relevante Code, funktioniert durch Auffinden des längsten übereinstimmenden Blocks und rekursives Fortfahren in den Teilen davor und danach (hat also eine gewisse Ähnlichkeit mit QuickSort):

Delphi-Quellcode:

procedure DiffRange(l1a, l1e, l2a, l2e: integer);
var
  l1s, l2s, maxm, bp1, bp2, bsz, scan, idx, pos, cnt: integer;
begin
  while true do
  begin
   l1s := l1e - l1a;
   l2s := l2e - l2a;
   if l1s > l2s then
     maxm := l2s
   else
     maxm := l1s;

   if maxm = 0 then
     break;

   bp1 := -1;
   bp2 := -1;
   bsz := 0;

   scan := l1a;
   while scan < l1e - bsz do
   begin
     idx := HashToRange(Info1.LineHash[scan], Info2.Count);
     repeat
      pos := Info2.HashLine[idx];
      if pos < l2a then
        break;

      if pos + bsz <= l2e then
      begin
        cnt := SameLines(scan, l1e, pos, l2e);

        if cnt = bsz then
         if DistanceLess(l1a, l1e, l2a, l2e, bp1, bp2, scan, pos) then
           dec(bsz);

        if cnt > bsz then
        begin
         bsz := cnt;
         bp1 := scan;
         bp2 := pos;
        end;
      end;

      idx := Info2.HashColl[idx];
     until idx < 0;

     if bsz > FHeuristic then break;
     if bsz + bsz >= maxm then break;

     inc(scan);
   end;

   if bsz = 0 then
     break;

   DiffRange(l1a, bp1, l2a, bp2);
   l1a := bp1 + bsz;
   l2a := bp2 + bsz;
  end;

  AddDiff(l1a, l1e, l2a, l2e);
end;

Das ist jetzt mal so in 2 Stunden heruntergehauen, hat bestimmt noch einiges an Optimierungspotential (und auch Kommentierungsbedarf :???:)

[Edit]

Neue Version hochgespielt: 0.2 (und ich hatte noch absolute Pfade von meinem Rechner als Vorgabe in den Edit-Felder :oops:)

[Sharky]

Hai Flocke,

ersteinmal herzlichen Dank für die Mühe :thumb:
Ich werde mir das am WE einmal in ruhe ansehen.

@Bernhard: Ich benutze in meinen Programmen einfach ungerne "externe Exen" ;-)
Ausserdem möchte ich halt gerne verstehen wie solch ein System funktioniert um es gegenbenenfalls an meine Bedürfnisse anpassen zu können.

[Flocke]

So, noch mal etwas verbessert. Ist jetzt selbst ohne Heuristik mehr als doppelt so schnell wie die alte Version mit :???:

[Sharky]

:thumb: Danke

[Daniel G]

:thumb: Nicht schlecht.

Aber wozu ist die Unit MemCheck da?

//Edit: Ok, vergisst die Frage. Habe sie mir inzwischen selbst beantwortet. Für andere Interessierte:
MemCheck home page

[Flocke]

Zitat:

Zitat von Daniel G

Aber wozu ist die Unit MemCheck da?

Ich war mir nicht völlig sicher, ob Delphi die dynamischen Arrays automatisch beim Verlassen der Prozedur wieder freigibt oder ob ich die manuell wieder freigeben muss, daher habe ich sicherheitshalber mit MemCheck mal auf Speicherlecks geprüft.

Wenn man es nicht hat, einfach in der Datei "pasdiff.dpr" die Unit MemCheck aus der uses-Liste nehmen und den Aufruf von MemChk nach begin rausschmeißen.

Übrigens: Nicht dass ihr meint, das Ding wäre langsam - das Programm macht insgesamt 100 Durchläufe um die Zeit besser stoppen zu können. Auf meinem Rechner braucht er für 1000 Zeilen ca. 1/100 Sekunde. Für zwei Dateien mit jeweils 100000 Zeilen braucht er mit Heuristik=50 etwa eine halbe Sekunde und ohne etwa 5 (auf einem P4 2,0 GhZ).

Hab's mal neu gepackt und MemCheck optional gemacht (siehe Anlage).

[Flocke]

Hab' noch ein bisschen nachoptimiert und ein paar andere Dinge geändert.

100000 x 100000 Zeilen brauchen jetzt ohne Heuristik bei mir keine Sekunde mehr :mrgreen:.
Code siehe Anlage oder hier abholen (da kann man auch direkt in den Quellcode sehen).