Reihenfolge selbst ermitteln

1 files changed, 239 insertions, 92 deletions

diff --git a/dateibeziehungen.pas b/dateibeziehungen.pas
index 14c1128..7900913 100644
--- a/dateibeziehungen.pas
+++ b/dateibeziehungen.pas
@@ -25,19 +25,28 @@ type
     procedure mrProper;
     function add(neu: tAbhaengigkeit): longint;
     function last: tAbhaengigkeit;
+    procedure sort;
   end;
 
   tAbhaengigkeit = class(tObject)
-    quellenRE:  tRegExpr;
+  private
+    _erben,_eltern: tAbhaengigkeiten;
+  public
+    quellenRE:      tRegExpr;
     zieleFkt,
-    befehle:    tStringlist;
+    befehle:        tStringlist;
     quellen,
-    ziele:      tDateienMitDaten;
-    erben:      tAbhaengigkeiten;
-    prioritaet: longint;
+    ziele:          tDateienMitDaten;
     constructor create; overload;
     constructor create(original: tAbhaengigkeit); overload;
     destructor destroy; override;
+    function hatQuelleVonAlsZiel(abh: tAbhaengigkeit): boolean;
+    function hatErbenMitQuelle(name: string): boolean;
+    function erbeMitGleichenZielen(zl: tDateienMitDaten): tAbhaengigkeit;
+    procedure neuerErbe(erb: tAbhaengigkeit);
+    procedure entferneErben(i: longint); overload;
+    procedure entferneErben(erb: tAbhaengigkeit); overload;
+    procedure entferneElterReferenz(elt: tAbhaengigkeit);
   end;
 
   tMach = class
@@ -76,7 +85,7 @@ procedure findeMehrZiele(var ziele: tDateienMitDaten; zieleFkt: tStringList; que
 implementation
 
 uses
-  lowlevelunit, mystringlistunit, math;
+  lowlevelunit, mystringlistunit;
 
 // tAbhaengigkeiten ************************************************************
 
@@ -109,7 +118,12 @@ begin
 end;
 
 function tAbhaengigkeiten.add(neu: tAbhaengigkeit): longint;
+var
+  i: longint;
 begin
+  for i:=0 to count-1 do
+    if items[i]=neu then
+      fehler('Fehler: Ich soll etwas zur Liste hinzufügen, was schon drin ist!');
   result:=inherited add(neu);
 end;
 
@@ -118,6 +132,69 @@ begin
   result:=tAbhaengigkeit(inherited last);
 end;
 
+procedure tAbhaengigkeiten.sort;
+var
+  i,j,k,pLen:  longint;
+  perm:        array of longint;
+  tmp:         tAbhaengigkeit;
+  bedingungen: array of tPoint;
+  nehmbare:    array of byte; // 0 = ja, 1 = nein, 2 = nie wieder (schon genommen)
+  fortschritt: boolean;
+begin
+  // Permutation initialisieren
+  setlength(perm,count);
+  for i:=0 to length(perm)-1 do
+    perm[i]:=count; // sollte ohnehin überschrieben werden, aber "count" sorgt unten für einen Fehler!
+
+  setlength(bedingungen,0); // aka "y hängt (direkt) von x ab"
+  for i:=0 to count-1 do
+    for j:=0 to count-1 do
+      if (i<>j) and (items[i].hatQuelleVonAlsZiel(items[j])) then begin
+        setlength(bedingungen,length(bedingungen)+1);
+        bedingungen[length(bedingungen)-1].x:=i;
+        bedingungen[length(bedingungen)-1].y:=j;
+      end;
+
+  setlength(nehmbare,count);
+  for i:=0 to length(nehmbare)-1 do
+    nehmbare[i]:=0;
+
+  pLen:=0;
+  while pLen<count do begin
+    fortschritt:=false;
+    for i:=0 to length(nehmbare)-1 do
+      if nehmbare[i]=1 then                // noch nicht genommenes zurücksetzen
+        nehmbare[i]:=0;
+    for i:=0 to length(bedingungen)-1 do
+      if nehmbare[bedingungen[i].x]<2 then // wenn die Quelle noch nicht dran war,
+        nehmbare[bedingungen[i].y]:=1;     // darf das Ziel auch nicht genommen werden
+    for i:=0 to length(nehmbare)-1 do
+      if nehmbare[i]=0 then begin          // nehmbar?
+        nehmbare[i]:=2;                    // als "genommen" markieren
+        perm[pLen]:=i;
+        inc(pLen);
+        fortschritt:=true;
+      end;
+    if not fortschritt then
+      fehler('Ich kann keine Regel mehr finden, deren Quellen nicht mehr erzeugt werden müssen - gibt es vllt. eine zyklische Abhängigkeit?');
+  end;
+
+  // berechnete Permutation anwenden
+  for i:=0 to length(perm)-1 do
+    if perm[i]>=0 then begin
+      tmp:=items[i];
+      j:=i;
+      while perm[j]<>i do begin
+        k:=perm[j];
+        perm[j]:=-1;
+        items[j]:=items[k];
+        j:=k;
+      end;
+      items[j]:=tmp;
+      perm[j]:=-1;
+    end;
+end;
+
 // tAbhaengigkeit **************************************************************
 
 constructor tAbhaengigkeit.create;
@@ -129,8 +206,8 @@ begin
   setlength(quellen,0);
   setlength(ziele,0);
   befehle:=tStringlist.create;
-  erben:=tAbhaengigkeiten.create;
-  prioritaet:=42;
+  _erben:=tAbhaengigkeiten.create;
+  _eltern:=tAbhaengigkeiten.create;
 end;
 
 constructor tAbhaengigkeit.create(original: tAbhaengigkeit);
@@ -150,9 +227,9 @@ begin
     ziele[i]:=original.ziele[i];
   befehle:=tStringlist.create;
   befehle.text:=original.befehle.text;
-  erben:=tAbhaengigkeiten.create;
-  erben.kopiereVon(original.erben);
-  prioritaet:=original.prioritaet;
+  _erben:=tAbhaengigkeiten.create;
+  _eltern:=tAbhaengigkeiten.create;
+  original.neuerErbe(self);
 end;
 
 destructor tAbhaengigkeit.destroy;
@@ -162,10 +239,86 @@ begin
   setLength(ziele,0);
   zieleFkt.free;
   befehle.free;
-  erben.free;
+  while _erben.count>0 do
+    entferneErben(0);
+  while _eltern.count>0 do
+    _eltern[0].entferneErben(self);
+  _erben.free;
+  _eltern.free;
   inherited destroy;
 end;
 
+function tAbhaengigkeit.hatQuelleVonAlsZiel(abh: tAbhaengigkeit): boolean;
+var
+  i,j: longint;
+begin
+  result:=true;
+  for i:=0 to length(ziele)-1 do
+    for j:=0 to length(abh.quellen)-1 do
+      if abh.quellen[j].name = ziele[i].name then
+        exit;
+  result:=false;
+end;
+
+function tAbhaengigkeit.hatErbenMitQuelle(name: string): boolean;
+var
+  i,j: longint;
+begin
+  result:=true;
+  for i:=0 to _erben.count-1 do
+    for j:=0 to length(_erben[i].quellen)-1 do
+      if _erben[i].quellen[j].name=name then exit;
+  result:=false;
+end;
+
+function tAbhaengigkeit.erbeMitGleichenZielen(zl: tDateienMitDaten): tAbhaengigkeit;
+var
+  i: longint;
+begin
+  result:=nil;
+  for i:=0 to _erben.count-1 do
+    if gleicheDateinamen(_erben[i].ziele,zl) then begin
+      result:=_erben[i];
+      exit;
+    end;
+end;
+
+procedure tAbhaengigkeit.neuerErbe(erb: tAbhaengigkeit);
+begin
+  _erben.add(erb);
+  erb._eltern.add(self);
+end;
+
+procedure tAbhaengigkeit.entferneErben(i: longint);
+begin
+  _erben[i].entferneElterReferenz(self);
+  _erben.delete(i);
+end;
+
+procedure tAbhaengigkeit.entferneErben(erb: tAbhaengigkeit);
+var
+  i: longint;
+begin
+  for i:=0 to _erben.count-1 do
+    if _erben[i]=erb then begin
+      entferneErben(i);
+      exit;
+    end;
+  fehler('Fehler: Kann Erben nicht finden zum Entfernen!');
+end;
+
+procedure tAbhaengigkeit.entferneElterReferenz(elt: tAbhaengigkeit);
+var
+  i: longint;
+begin
+  for i:=0 to _eltern.count-1 do
+    if _eltern[i]=elt then begin
+      _eltern.delete(i);
+      exit;
+    end;
+  fehler('Fehler: Kann Elter nicht finden zum Entfernen der Referenz!');
+end;
+
 // tMach ***********************************************************************
 
 constructor tMach.create;
@@ -216,7 +369,7 @@ var
   na:            tAbhaengigkeit;
   ignoriere:     array of tRegExpr;
   rek:           boolean;
-  num,posi:      longint;
+  posi:          longint;
   wasWar,wasIst: tZeilenTyp;
 
 procedure aufraeumen;
@@ -234,9 +387,7 @@ begin
   result:=false;
 
   na:=tAbhaengigkeit.create;
-  na.prioritaet:=0;
   setlength(ignoriere,0);
-  num:=0;
   wasWar:=ztSuche;
   f:=tMyStringList.create;
   f.loadFromFile(machDatei);
@@ -261,9 +412,7 @@ begin
 
     if (wasWar=ztBefehl) and (wasIst<>ztBefehl) then begin
       _oriAbh.add(na);
-      inc(num);
       na:=tAbhaengigkeit.create;
-      na.prioritaet:=num;
     end;
 
     if s='%%DATEIENDE%%' then break;
@@ -361,7 +510,7 @@ begin
           setlength(_dats,length(_dats)+1); // dann werden sie einfach eingefügt
           _dats[length(_dats)-1]:=tDateiMitDatum.create;
           _dats[length(_dats)-1].name:=gutschlecht[gut][i];
-          _dats[length(_dats)-1].aktuell:=aVeraltet;
+          _dats[length(_dats)-1].aktuell:=aNichtVorhanden;
           continue;
         end;
         writeln('In der Summendatei gibt es eine Datei mit gültiger Prüfsumme, die ich nicht finden kann: '''+gutschlecht[gut][i]+'''!');
@@ -378,31 +527,25 @@ end;
 
 procedure tMach.erzeugeRegeln;
 var
-  i,j,k,l:       longint;
-  neues,schonDa: boolean;
-  s:             string;
-  tmpZiele:      tDateienMitDaten;
+  i,j,k,l:  longint;
+  neues:    boolean;
+  s:        string;
+  tmpZiele: tDateienMitDaten;
+  erb:      tAbhaengigkeit;
 begin
-
   repeat
     neues:=false;
 
     for i:=0 to _oriAbh.count-1 do
       for j:=0 to length(_dats)-1 do
         if _oriAbh[i].quellenRE.exec(_dats[j].name) then begin
-          schonDa:=false;
-          for k:=0 to _oriAbh[i].erben.count-1 do
-            for l:=0 to length(_oriAbh[i].erben[k].quellen)-1 do
-              schonDa:=schonDa or (_oriAbh[i].erben[k].quellen[l]=_dats[j]);
-
           // Falls diese Quelle schon in eine Regel einfließt, brauchen
           // wir nichts mehr zu machen, da es für jede Quelle höchstens
           // eine Regel gibt.
-          if schonDa then continue;
+          if _oriAbh[i].hatErbenMitQuelle(_dats[j].name) then continue;
 
           // Andernfalls müssen wir schauen, ob es zu dem Ziel / den Zielen
           // der Quelle schon eine Regel gibt.
-          schonDa:=false;
           setlength(tmpZiele,0);
           findeMehrZiele(tmpZiele,_oriAbh[i].zieleFkt,_dats[j].name,machDatei,_dats);
 
@@ -416,32 +559,31 @@ begin
             fehler('... ich beende.');
           end;
 
-          for k:=0 to _oriAbh[i].erben.count-1 do
-            if gleicheDateinamen(_oriAbh[i].erben[k].ziele,tmpZiele) then begin
-              // es gibt schon eine Regel für die Ziele der Quelle
-              schonDa:=true;
-              // dann wird dieser Regel nur die Quelle hinzugefügt
-              setlength(_oriAbh[i].erben[k].quellen,length(_oriAbh[i].erben[k].quellen)+1);
-              _oriAbh[i].erben[k].quellen[length(_oriAbh[i].erben[k].quellen)-1]:=_dats[j];
-              // und womöglich die befehle generiert
-              for l:=0 to _oriAbh[i].befehle.count-1 do begin
-                s:=_oriAbh[i].befehle[l];
-                if quellersetzung(s,_dats[j].name,machDatei) then begin
-                  if l=0 then _oriAbh[i].erben[k].befehle.clear;
-                  _oriAbh[i].erben[k].befehle.add(s);
-                end;
+          erb:=_oriAbh[i].erbeMitGleichenZielen(tmpZiele);
+          if assigned(erb) then begin
+            // es gibt schon eine Regel für die Ziele der Quelle,
+            // dann wird dieser Regel nur die Quelle hinzugefügt
+            setlength(erb.quellen,length(erb.quellen)+1);
+            erb.quellen[length(erb.quellen)-1]:=_dats[j];
+            // und womöglich die befehle generiert
+            for l:=0 to _oriAbh[i].befehle.count-1 do begin
+              s:=_oriAbh[i].befehle[l];
+              if quellersetzung(s,_dats[j].name,machDatei) then begin
+                if l=0 then erb.befehle.clear;
+                erb.befehle.add(s);
               end;
-              neues:=true;
-              break; // mehr Ziele sollte es ohnehin nicht geben
             end;
-          if schonDa then continue;
+            neues:=true;
+            continue;
+          end;
 
           // Ziel(e) ist/sind neu
           _mglAbh.add(tAbhaengigkeit.create);
-          _oriAbh[i].erben.add(_mglAbh.last);
+          _oriAbh[i].neuerErbe(_mglAbh.last);
           setlength(_mglAbh.last.quellen,1);
           _mglAbh.last.quellen[0]:=_dats[j];
-          _mglAbh.last.zieleFkt:=_oriAbh[i].zieleFkt;
+          _mglAbh.last.zieleFkt:=tStringlist.create;
+          _mglAbh.last.zieleFkt.text:=_oriAbh[i].zieleFkt.text;
           setlength(_mglAbh.last.ziele,length(tmpZiele));
           for k:=0 to length(tmpZiele)-1 do
             _mglAbh.last.ziele[k]:=tmpZiele[k];
@@ -451,7 +593,6 @@ begin
             if quellersetzung(s,_dats[j].name,machDatei) then
               _mglAbh.last.befehle.add(s);
           end;
-          _mglAbh.last.prioritaet:=_oriAbh[i].prioritaet;
         end;
 
   until not neues;
@@ -461,44 +602,57 @@ procedure tMach.findeWasZuTunIst;
 var
   i,j,k:   longint;
   ziA,quA: tAktualitaet;
+  neues:   boolean;
 begin
   // schauen, welche Regeln angewandt werden müssen
+  repeat
+    neues:=false;
+    for i:=_mglAbh.count-1 downto 0 do begin
+      for j:=0 to length(_mglAbh[i].quellen)-1 do
+        findeMehrZiele(_mglAbh[i].ziele,_mglAbh[i].zieleFkt,_mglAbh[i].quellen[j].name,machDatei,_dats);
+      if length(_mglAbh[i].ziele)=0 then begin // immer noch keine ziele
+        gibAus('Warnung: Keine Ziele für diese Abhängigkeit!',3);
+        gibAus('quellen:',3);
+        for k:=0 to length(_mglAbh[i].quellen)-1 do
+          gibAus(' '''+_mglAbh[i].quellen[k].name+'''',3);
+        gibAus('zieleFkt:',3);
+        for k:=0 to _mglAbh[i].zieleFkt.count-1 do
+          gibAus(' '''+_mglAbh[i].zieleFkt[k]+'''',3);
+        gibAus(' - wird ignoriert.',3);
+        _mglAbh[i].free;
+        _mglAbh.delete(i);
+        continue;
+      end;
 
-  for i:=0 to _mglAbh.count-1 do begin
-    for j:=0 to length(_mglAbh[i].quellen)-1 do
-      findeMehrZiele(_mglAbh[i].ziele,_mglAbh[i].zieleFkt,_mglAbh[i].quellen[j].name,machDatei,_dats);
-    if length(_mglAbh[i].ziele)=0 then begin // immer noch keine ziele
-      gibAus('Warnung: Keine ziele für diese Abhängigkeit!',3);
-      gibAus('quellen:',3);
-      for k:=0 to length(_mglAbh[i].quellen)-1 do
-        gibAus(' '''+_mglAbh[i].quellen[k].name+'''',3);
-      gibAus('zieleFkt:',3);
-      for k:=0 to _mglAbh[i].zieleFkt.count-1 do
-        gibAus(' '''+_mglAbh[i].zieleFkt[k]+'''',3);
-      gibAus(' - wird ignoriert.',3);
-      continue;
-    end;
-
-    quA:=aAktuell;
-    for j:=0 to length(_mglAbh[i].quellen)-1 do
-      if _mglAbh[i].quellen[j].aktuell<>aAktuell then
-        quA:=aWirdErneuert;
-    ziA:=aWirdErneuert;
-    for j:=0 to length(_mglAbh[i].ziele)-1 do
-      ziA:=min(ziA,_mglAbh[i].ziele[j].aktuell);
-
-    if ziA<quA then begin
-      _ztAbh.add(tAbhaengigkeit.create(_mglAbh[i]));
-      _mglAbh[i].erben.add(_ztAbh.last);
+      quA:=aAktuell;
+      for j:=0 to length(_mglAbh[i].quellen)-1 do
+        if _mglAbh[i].quellen[j].aktuell<>aAktuell then
+          quA:=aWirdErneuert;
+      ziA:=aWirdErneuert;
       for j:=0 to length(_mglAbh[i].ziele)-1 do
-        _mglAbh[i].ziele[j].aktuell:=aWirdErneuert;
+        if _mglAbh[i].ziele[j].aktuell=aVeraltet then
+          ziA:=min(ziA,aAktuell)
+        else
+          ziA:=min(ziA,_mglAbh[i].ziele[j].aktuell);
+
+      if ziA<quA then begin
+        neues:=true;
+        _ztAbh.add(tAbhaengigkeit.create(_mglAbh[i]));
+        for j:=0 to length(_mglAbh[i].ziele)-1 do
+          _mglAbh[i].ziele[j].aktuell:=aWirdErneuert;
+        _mglAbh[i].free;
+        _mglAbh.delete(i);
+      end;
     end;
-  end;
+  until not neues;
+
+  // anzuwendende Regeln sortieren
+  _ztAbh.sort;
 end;
 
 procedure tMach.tueWasZuTunIst(allesNeu, unsicher: boolean; ausgabeDatei: string);
 var
-  prior,i,j:                 longint;
+  i,j:                       longint;
   ausg:                      textfile;
   befehle,geaenderteDateien,
     sumDateien:              tStringlist;
@@ -507,9 +661,6 @@ var
   befehl:                    string;
 begin
   befehle:=tStringlist.create;
-  prior:=0;
-  for i:=0 to _ztAbh.count-1 do
-    prior:=max(prior,_ztAbh[i].prioritaet);
   geaenderteDateien:=tStringlist.create;
   sumDateien:=dateienMitGueltigerSumme(pruefsummenDatei);
   for i:=0 to length(_dats)-1 do begin
@@ -537,13 +688,9 @@ begin
     for j:=0 to length(_ztAbh[i].quellen)-1 do
       geaenderteDateien.add(_ztAbh[i].quellen[j].name);
   end;
-  while prior>=0 do begin
-    for i:=0 to _ztAbh.count-1 do
-      if _ztAbh[i].prioritaet=prior then
-        for j:=0 to _ztAbh[i].befehle.count-1 do
-          befehle.add(_ztAbh[i].befehle[j]);
-    dec(prior);
-  end;
+  for i:=0 to _ztAbh.count-1 do
+    for j:=0 to _ztAbh[i].befehle.count-1 do
+      befehle.add(_ztAbh[i].befehle[j]);
   if not unsicher then begin
     lokTest:=tRegExpr.create;
     if extractfilepath(ausgabeDatei)=extractfilepath(pruefsummenDatei) then
@@ -566,14 +713,14 @@ begin
       end;
   end;
   if geaenderteDateien.count>0 then begin
-    befehle.add('echo -ne "Sha512summen erneuern ..."');
+    befehle.add('echo -n "Sha512summen erneuern ..."');
     befehl:='sed "';
     for i:=0 to geaenderteDateien.count-1 do
       befehl:=befehl+'/\s'+escape(geaenderteDateien[i],'./','\')+'\$/d; ';
     befehl:=befehl+'" -i "'+pruefsummenDatei+'"';
     befehle.add(befehl);
     for i:=0 to geaenderteDateien.count-1 do
-      befehle.add('/usr/bin/sha512sum "'+geaenderteDateien[i]+'" >> '+pruefsummenDatei);
+      befehle.add('sha512sum "'+geaenderteDateien[i]+'" >> '+pruefsummenDatei);
     befehle.add('echo " fertig"');
   end;
 
@@ -767,7 +914,7 @@ begin
       dats[i]:=tDateiMitDatum.create;
       if pos('*',ziel)=0 then dats[i].name:=ziel
       else dats[i].name:='.uralt.'; // unpassende *-Muster erzeugen formal keine echte Datei
-      dats[i].aktuell:=aVeraltet;   // nicht existente dateien sind formal uralt
+      dats[i].aktuell:=aNichtVorhanden;
       setlength(ziele,length(ziele)+1);
       ziele[length(ziele)-1]:=dats[i];
     end;