unit dateiBeziehungen;

{$mode objfpc}{$H+}

interface

uses
  classes, sysUtils, tools, regExpr, mystringlistunit, lowlevelunit;

type
  tZeilenTyp = (ztSuche,ztZiel,ztQuelle,ztBefehl);

  tGenerischeAbhaengigkeit = class;
  tExpliziteAbhaengigkeit = class;

  tGenerischeAbhaengigkeiten = class(tFPList)
  private
    function rItem(idx: longint): tGenerischeAbhaengigkeit; inline;
    procedure wItem(idx: longint; neu: tGenerischeAbhaengigkeit); inline;
  public
    property items[idx: longint]: tGenerischeAbhaengigkeit
      read rItem
      write wItem; default;
    procedure kopiereVon(original: tGenerischeAbhaengigkeiten);
    procedure mrProper;
    function add(neu: tGenerischeAbhaengigkeit): longint;
    function last: tGenerischeAbhaengigkeit;
  end;

  tExpliziteAbhaengigkeiten = class(tFPList)
  private
    function rItem(idx: longint): tExpliziteAbhaengigkeit; inline;
    procedure wItem(idx: longint; neu: tExpliziteAbhaengigkeit); inline;
  public
    property items[idx: longint]: tExpliziteAbhaengigkeit
      read rItem
      write wItem; default;
    procedure kopiereVon(original: tExpliziteAbhaengigkeiten);
    procedure mrProper;
    function add(neu: tExpliziteAbhaengigkeit): longint;
    function last: tExpliziteAbhaengigkeit;
    procedure sort;
  end;

  // Die goldene Regel bzgl. Abhängigkeiten ist,
  // dass jedes Ziel nur ein Mal erzeugt werden kann und muss (logisch)
  // und somit für zwei Regeln mit Zielmengen A und B
  // A \cut B \neq \emptyset => A \cut B \in {A,B}
  // gilt. Von diesen beiden Regeln ist dann höchstens eine anzuwenden.

  // Mit den Informationen jeder einzelnen Quelle muss die gesamte Regel
  // konstruiert werden können. Das beinhaltet:
  // - weitere Quellen (per regex matchbar)
  // - auszuführende Befehle (darf von "weiteren Quellen" abhängen)
  // - erzeugte Ziele (darf von "weiteren Quellen" abhängen)

  tGenerischeAbhaengigkeit = class(tObject)
  private
    _machDatei,_pruefSummenDatei: string;
    _quellens,_zieles:            array of tDateienMitDaten;
    _dats:                        tDateienMitDaten;
    function rQuellen(idx: longint): tDateienMitDaten;
    function rZiele(idx: longint): tDateienMitDaten;
    function quellErsetzung(var worin: string; worinIstRegex: tRegexTyp; quellen: tDateienMitDaten; momentanePosition: longint): boolean;
    function zieleHinzufuegen(ziele, quellen: tDateienMitDaten; zielFkt: string): boolean;
    function findeMehrZiele(ziele, quellen: tDateienMitDaten): boolean;
    function matchCount: longint;
  public
    quellenREs:                 array of string; // regexe der Quellen - nur deshalb kein tRegExpr, weil es ohnehin zuerst substituiert werden muss
    zieleFkt,befehleFkt:        tStringList;
    property quellen[idx: longint]: tDateienMitDaten
      read rQuellen;
    property ziele[idx: longint]: tDateienMitDaten
      read rZiele;
    constructor create(dats: tDateienMitDaten; machDatei,pruefSummenDatei: string);
    destructor destroy; override;
    function findeQuellen(dats: tDateienMitDaten): boolean;
    procedure generiereErben(var es: tExpliziteAbhaengigkeiten);
    function count: longint; inline;
  end;

  tExpliziteAbhaengigkeit = class(tObject)
    ziele,quellen: tDateienMitDaten;
    befehle:       tStringList;
    constructor create;
    destructor destroy; override;
    function hatQuelleVonAlsZiel(abh: tExpliziteAbhaengigkeit): boolean;
    function ersetzbarDurch(abh: tExpliziteAbhaengigkeit): boolean; inline;
    function pruefeObZuTun: boolean;
    function dump: string;
  end;

  tMach = class
  private
    _machDatei,_pruefSummenDatei: string;
    _ueberwachteDateien:          tMyStringList;
    _oriAbh:                      tGenerischeAbhaengigkeiten;
    _mglAbh:                      tExpliziteAbhaengigkeiten;
    _dats:                        tDateienMitDaten;
    _ign:                         array of tRegExpr;
    _warten:                      boolean;
    function liesMachDatei: boolean;
    function liesPruefsummenfile: boolean;
    function sammleDateien(wo: string; rekursiv: boolean): longint;
  public
    constructor create(machDatei, pruefSummenDatei: string; warten: boolean);
    destructor destroy; override;
    procedure erzeugeRegeln;
    procedure findeWasZuTunIst;
    procedure tueWasZuTunIst(sicher: integer; ausgabeDatei: string);
    function anzOriAbh: longint; inline;
    function anzMglAbh: longint; inline;
    function anzDats: longint; inline;
  end;

  tRedundanzenEntfernThread = class(tThread)
  private
    num,anz:  longint;
    mglAbh:   tExpliziteAbhaengigkeiten;
    ztd,itpf: pTLongintArray;      // die inversToepfe müssen nur auf _einen_ Topf je mglAbh zeigen, nicht auf alle.
    tpf:      pTLongintArrayArray;
    kA:       pRTLCriticalSection;
    fertig:   boolean;
  public
    constructor create(nummer,anzahl: longint; moeglicheAbhaengigkeiten: tExpliziteAbhaengigkeiten; zuTunDurch,inversToepfe: pTLongintArray; toepfe: pTLongintArrayArray; kritischerAbschnitt: pRTLCriticalSection);
    procedure execute; override;
  end;

  tBedingungFindeThread = class(tThread)
  private
    num,anz:  longint;
    tpf:      pTIntPointArrayArray;
    eas:      tExpliziteAbhaengigkeiten;
    fertig:   boolean;
  public
    bedingungen: tIntPointArray;
    constructor create(nummer,anzahl: longint; toepfe: pTIntPointArrayArray; expliziteAbhaengigkeiten: tExpliziteAbhaengigkeiten);
    destructor destroy; override;
    procedure execute; override;
  end;

procedure allgemeineErsetzungen(var worin: string; worinIstRegex: tRegexTyp; machDatei: string);

implementation

uses
  systemunit, math;

// tGenerischeAbhaengigkeiten ************************************************************

function tGenerischeAbhaengigkeiten.rItem(idx: longint): tGenerischeAbhaengigkeit;
begin
  result:=tGenerischeAbhaengigkeit(get(idx));
end;

procedure tGenerischeAbhaengigkeiten.wItem(idx: longint; neu: tGenerischeAbhaengigkeit);
begin
  put(idx,neu);
end;

procedure tGenerischeAbhaengigkeiten.kopiereVon(original: tGenerischeAbhaengigkeiten);
var
  i: longint;
begin
  clear;
  for i:=0 to original.count-1 do
    add(original[i]);
end;

procedure tGenerischeAbhaengigkeiten.mrProper;
var
  i: longint;
begin
  for i:=0 to count-1 do
    items[i].free;
  clear;
end;

function tGenerischeAbhaengigkeiten.add(neu: tGenerischeAbhaengigkeit): 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;

function tGenerischeAbhaengigkeiten.last: tGenerischeAbhaengigkeit;
begin
  result:=tGenerischeAbhaengigkeit(inherited last);
end;

// tExpliziteAbhaengigkeiten ************************************************************

function tExpliziteAbhaengigkeiten.rItem(idx: longint): tExpliziteAbhaengigkeit;
begin
  result:=tExpliziteAbhaengigkeit(get(idx));
end;

procedure tExpliziteAbhaengigkeiten.wItem(idx: longint; neu: tExpliziteAbhaengigkeit);
begin
  put(idx,neu);
end;

procedure tExpliziteAbhaengigkeiten.kopiereVon(original: tExpliziteAbhaengigkeiten);
var
  i: longint;
begin
  clear;
  for i:=0 to original.count-1 do
    add(original[i]);
end;

procedure tExpliziteAbhaengigkeiten.mrProper;
var
  i: longint;
begin
  for i:=0 to count-1 do
    items[i].free;
  clear;
end;

function tExpliziteAbhaengigkeiten.add(neu: tExpliziteAbhaengigkeit): 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;

function tExpliziteAbhaengigkeiten.last: tExpliziteAbhaengigkeit;
begin
  result:=tExpliziteAbhaengigkeit(inherited last);
end;

procedure tExpliziteAbhaengigkeiten.sort;
var
  i,j,k,pLen:            longint;
  perm:                  tLongintArray;
  tmp:                   tExpliziteAbhaengigkeit;
  bedingungen:           tIntPointArray;
  nehmbare:              array of byte; // 0 = ja, 1 = nein, 2 = nie wieder (schon genommen)
  fortschritt,fertig:    boolean;
  toepfe:                tIntPointArrayArray;
  bedingungFindeThreads: array of tBedingungFindeThread;
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(toepfe,max(1,round(sqrt(count))));
  for i:=0 to length(toepfe)-1 do
    setLength(toepfe[i],0);

  for i:=0 to count-1 do
    for j:=0 to items[i].ziele.count-1 do begin
      k:=pruefSumme(items[i].ziele[j].name,length(toepfe));
      setLength(toepfe[k],length(toepfe[k])+1);
      toepfe[k,length(toepfe[k])-1,'x']:=i;
      toepfe[k,length(toepfe[k])-1,'y']:=j;
      // hiermit finden wir schnell(er) zu einer Datei(summe) die Regel, die diese Datei erzeugt:
      // toepfe[summe] ist ein Array aller Regeln (Indizes), die Ziele dieser Summe erzeugen
    end;

  setLength(bedingungFindeThreads,numCpus);
  for i:=0 to length(bedingungFindeThreads)-1 do
    bedingungFindeThreads[i]:=tBedingungFindeThread.create(i,length(bedingungFindeThreads),@toepfe,self);
  repeat
    fertig:=true;
    for i:=0 to length(bedingungFindeThreads)-1 do
      fertig:=bedingungFindeThreads[i].fertig and fertig;
    if not fertig then
      sleep(10);
  until fertig;

  setLength(bedingungen,0); // aka "y hängt (direkt) von x ab"
  for i:=0 to length(bedingungFindeThreads)-1 do begin
    setLength(bedingungen,length(bedingungen)+length(bedingungFindeThreads[i].bedingungen));
    for j:=0 to length(bedingungFindeThreads[i].bedingungen)-1 do
      bedingungen[length(bedingungen)-1-j]:=bedingungFindeThreads[i].bedingungen[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;

// tGenerischeAbhaengigkeit **************************************************************

constructor tGenerischeAbhaengigkeit.create(dats: tDateienMitDaten; machDatei,pruefSummenDatei: string);
begin
  inherited create;
  _dats:=dats;
  setLength(quellenREs,0);
  zieleFkt:=tStringList.create;
  befehleFkt:=tStringList.create;
  setLength(_quellens,0);
  setLength(_zieles,0);
  _machDatei:=machDatei;
  _pruefSummenDatei:=pruefSummenDatei;
end;

destructor tGenerischeAbhaengigkeit.destroy;
var
  i: longint;
begin
  for i:=0 to length(_quellens)-1 do
    _quellens[i].free;
  setLength(_quellens,0);
  for i:=0 to length(quellenREs)-1 do
    setLength(quellenREs[i],0);
  setLength(quellenREs,0);
  for i:=0 to length(_zieles)-1 do
    _zieles[i].free;
  setLength(_zieles,0);
  zieleFkt.free;
  befehleFkt.free;
  for i:=0 to length(_quellens)-1 do
    _quellens[i].free;
  setLength(_quellens,0);
  inherited destroy;
end;

function tGenerischeAbhaengigkeit.rQuellen(idx: longint): tDateienMitDaten;
begin
  result:=_quellens[idx];
end;

function tGenerischeAbhaengigkeit.rZiele(idx: longint): tDateienMitDaten;
begin
  result:=_zieles[idx];
end;

function tGenerischeAbhaengigkeit.quellErsetzung(var worin: string; worinIstRegex: tRegexTyp; quellen: tDateienMitDaten; momentanePosition: longint): boolean;
var
  s,anfang,mitte,numStr: string;
  i,li,re,qNum:          longint;
  tmpRE:                 tRegExpr;
begin
  result:=true;
  for qNum:=-byte(momentanePosition>0) to momentanePosition-1 do begin
    if qNum<0 then
      numStr:=''
    else
      numStr:=intToStr(qNum);
    s:=quellen[qNum+byte(qNum<0)].name;
    ersetzeAlleVorkommen(worin,'%in'+numStr+'%',escapeStringToRegex(s,worinIstRegex)); // %in%
    s:=extractfilename(s);
    ersetzeAlleVorkommen(worin,'%ifile'+numStr+'%',escapeStringToRegex(s,worinIstRegex)); // %ifile%
    i:=0;
    while pos('.',s)>0 do begin
      while rightStr(s,1)<>'.' do
        delete(s,length(s),1);
      delete(s,length(s),1);
      inc(i);
      ersetzeAlleVorkommen(worin,'%basename'+numStr+','+intToStr(i)+'%',escapeStringToRegex(s,worinIstRegex)); // %basename%
    end;
    ersetzeAlleVorkommen(worin,'%basename'+numStr+'%',escapeStringToRegex(s,worinIstRegex)); // %basename%
  end;

  while pos('%dirname',worin)>0 do begin                  // %dirname%
    anfang:=erstesArgument(worin,'%dirname',false);
    mitte:=erstesArgument(worin,'%',false);
    s:='%dirname'+mitte+'%';
    if mitte='' then
      qNum:=0
    else
      try
        qNum:=strtoint(erstesArgument(mitte,',',true));
      except
        fehler('Syntaxfehler %dirname...%: '''+s+'%''');
      end;
    if mitte='' then
      li:=0
    else
      try
        li:=strtoint(erstesArgument(mitte,',',true));
      except
        fehler('Syntaxfehler %dirname...%: '''+s+'%''');
      end;
    if mitte='' then
      re:=-1
    else
      try
        re:=strtoint(erstesArgument(mitte,',',true));
      except
        fehler('Syntaxfehler %dirname...%: '''+s+'%''');
      end;

    if qNum>=momentanePosition then
      fehler('Quellersetzung sieht ''%dirname%'' für Quelle Nummer '+intToStr(qNum)+' an Position '+intToStr(momentanePosition)+'.');
    s:=extractFilePath(quellen[qNum].name);
    if rightStr(s,1)='/' then
      delete(s,length(s),1);
    i:=anzCs('/',s)+1;
    if li<0 then li:=li+i;
    if re<0 then re:=re+i;
    while li>0 do begin
      dec(li);
      dec(re);
      erstesArgument(s,'/',false);
    end;
    mitte:='';
    while re>=0 do begin
      dec(re);
      mitte:=mitte+'/'+erstesArgument(s,'/',false);
    end;
    delete(mitte,1,1);
    worin:=anfang+escapeStringToRegex(mitte,worinIstRegex)+worin;
  end;

  allgemeineErsetzungen(worin,worinIstRegex,_machDatei);  // %DIRNAME% %num'...'%

  result:=false;
  tmpRE:=tRegExpr.create;
  for qNum:=-byte(momentanePosition>0) to momentanePosition-1 do begin
    if qNum<0 then
      numStr:=''
    else
      numStr:=intToStr(qNum);
    s:=quellen[qNum+byte(qNum<0)].name;
    while pos('%nurmit'+numStr+'''',worin)>0 do begin     // %nurmit'...'%
      anfang:=erstesArgument(worin,'%nurmit'+numStr+'''',false);
      tmpRE.expression:=erstesArgument(worin,'''%',false);
      if not tmpRE.exec(s) then begin
        tmpRE.free;
        exit;
      end;
      worin:=anfang+worin;
    end;
    while pos('%nurohne'+numStr+'''',worin)>0 do begin    // %nurohne'...'%
      anfang:=erstesArgument(worin,'%nurohne'+numStr+'''',false);
      tmpRE.expression:=erstesArgument(worin,'''%',false);
      if tmpRE.exec(s) then begin
        tmpRE.free;
        exit;
      end;
      worin:=anfang+worin;
    end;
  end;
  result:=true;
  tmpRE.free;
end;

function tGenerischeAbhaengigkeit.zieleHinzufuegen(ziele, quellen: tDateienMitDaten; zielFkt: string): boolean;
var
  i,ebene,ende: longint;
  s,t,u:        string;
  sR:           tSearchRec;
begin
  result:=false;
  if pos('{',zielFkt)=0 then begin
    if not quellErsetzung(zielFkt,rtKein,quellen,quellen.count) then exit;
    if pos('*',zielFkt)=0 then begin
      zielFkt:=unEscapeCommas(zielFkt);
      ziele.add(_dats.finde(zielFkt,result));
    end
    else begin
      i:=findFirst(zielFkt,$3f,sR);
      while i=0 do begin
        result:=zieleHinzufuegen(ziele,quellen,extractFileDir(zielFkt)+'/'+sR.name) or result;
        i:=findNext(sR);
      end;
      findClose(sR);
    end;
  end
  else begin
    ende:=pos('{',zielFkt);
    ebene:=1;
    while (ebene>0) or (zielFkt[ende]<>'}') do begin
      inc(ende);
      case zielFkt[ende] of
        '{': inc(ebene);
        '}': dec(ebene);
      end{of case};
    end;
    s:=copy(zielFkt,1,pos('{',zielFkt)-1);
    t:=copy(zielFkt,pos('{',zielFkt)+1,ende-pos('{',zielFkt)-1);
    u:=copy(zielFkt,ende+1,length(zielFkt));
    if unEscapedPos('..',t)>0 then begin
      for i:=strtoint(copy(t,1,unEscapedPos('..',t)-1)) to strtoint(copy(t,unEscapedPos('..',t)+2,length(t))) do
        result:=zieleHinzufuegen(ziele,quellen,s+intToStr(i)+u) or result;
    end
    else begin
      t:=t+',';
      while unEscapedPos(',',t)>0 do begin
        result:=zieleHinzufuegen(ziele,quellen,s+copy(t,1,unEscapedPos(',',t)-1)+u) or result;
        delete(t,1,unEscapedPos(',',t));
      end;
    end;
  end;
end;

function tGenerischeAbhaengigkeit.findeMehrZiele(ziele, quellen: tDateienMitDaten): boolean;
var
  i: longint;
begin
  result:=false;
  for i:=0 to zieleFkt.count-1 do
    if zieleHinzufuegen(ziele,quellen,zieleFkt[i]) then
      result:=true;
end;

function tGenerischeAbhaengigkeit.matchCount: longint;
begin
  if length(_quellens)<>length(_zieles) then
    fehler('unterschiedlich viele Sätze an Quellen ('+intToStr(length(_quellens))+') und Zielen ('+intToStr(length(_zieles))+').');
  result:=length(_quellens);
end;

function tGenerischeAbhaengigkeit.findeQuellen(dats: tDateienMitDaten): boolean;
var
  i:       longint;
  idxs:    array of tLongintArray;
  tmpQs:   tDateienMitDaten; // hierin wird die momentan betrachte Kombination von Quellen gespeichert

procedure fuelleStelle(ii: longint);
var
  s:       string;
begin
  if ii>0 then begin             // vorherige Stelle "verbrauchen"
    tmpQs.add(dats[idxs[ii-1][length(idxs[ii-1])-1]]);
    setLength(idxs[ii-1],length(idxs[ii-1])-1);
  end;
  s:=quellenREs[ii];
  if (leftStr(s,1)='^') and (rightStr(s,1)='$') then begin // es handelt sich um einen regex
    if not quellErsetzung(s,rtFpc,tmpQs,ii) then           // regex-Substitution nicht erfolgreich -
      setLength(idxs[ii],0)                                // wird behandelt wie nie passender regex
    else
      dats.matchAll(s,idxs[ii],true);
  end
  else if (leftStr(s,1)='"') and (rightStr(s,1)='"') then begin // es handelt sich um einen regulären String
    delete(s,1,1);
    delete(s,length(s),1);
    if not quellErsetzung(s,rtKein,tmpQs,ii) then               // Substitution nicht erfolgreich -
      setLength(idxs[ii],0)                                     // wird behandelt wie nicht existente Datei
    else
      dats.matchAll(s,idxs[ii],false);
  end
  else
    fehler('Unbekannte Quell-Syntax: '''+s+''' - weder ''"/pfad/zur/Quelle"'' noch ''^/regex/der/auf/Quelle\.passt$''!');
  if length(idxs[ii])=0 then
    while tmpQs.count>=max(1,ii) do
      tmpQs.delete(tmpQs.count-1);
end;

begin
  result:=false;
  for i:=0 to length(_quellens)-1 do
    _quellens[i].free;
  setLength(_quellens,0);
  for i:=0 to length(_zieles)-1 do
    _zieles[i].free;
  setLength(_zieles,0);

  if length(quellenREs)=0 then exit;

  tmpQs:=tDateienMitDaten.create;
  setLength(idxs,length(quellenREs));
  for i:=0 to length(idxs)-1 do
    setLength(idxs[i],0);

  fuelleStelle(0);
  repeat
    while (tmpQs.count>0) and (length(idxs[tmpQs.count])=0) do
      tmpQs.delete(tmpQs.count-1);
    // jetzt gibt es genau so viele tmpQs bis eins vor der letzten idxs-Position
    // mit einem Wert <> 0

    if length(idxs[tmpQs.count])=0 then // das bedeutet einen Übertrag von der 0.
      break;                            // auf die -1. Stelle

    for i:=tmpQs.count+1 to length(idxs)-1 do begin // um die Stelle i zu füllen, benötigen wir
      fuelleStelle(i);                              // i-1 tmpQs, denn die i-te wird gewählt
      if i>tmpQs.count then // die neue Stelle wurde nicht befüllt
        break;
    end;

    if tmpQs.count<length(idxs)-1 then // eine Quellersetzung ist fehlgeschlagen -
      continue;                        // wir starten die Runde neu

    for i:=0 to length(idxs[length(idxs)-1])-1 do begin
      tmpQs.add(dats[idxs[length(idxs)-1][i]]);
      setLength(_quellens,length(_quellens)+1);
      _quellens[length(_quellens)-1]:=tDateienMitDaten.create;
      _quellens[length(_quellens)-1].append(tmpQs);
      tmpQs.delete(tmpQs.count-1);
    end;
    setLength(idxs[length(idxs)-1],0);
  until false;

  tmpQs.free;
  for i:=0 to length(idxs)-1 do
    setLength(idxs[i],0);
  setLength(idxs,0);

  setLength(_zieles,length(_quellens));
  for i:=0 to length(_zieles)-1 do begin
    _zieles[i]:=tDateienMitDaten.create;
    if findeMehrZiele(_zieles[i],_quellens[i]) then
      result:=true;
  end;
end;

procedure tGenerischeAbhaengigkeit.generiereErben(var es: tExpliziteAbhaengigkeiten);
var
  i,j,befCnt: longint;
  s:          string;
  neuSums:    tMyStringList;
begin
  neuSums:=tMyStringList.create;
  for i:=0 to matchCount-1 do begin
    befCnt:=0;
    es.add(tExpliziteAbhaengigkeit.create);
    for j:=0 to quellen[i].count-1 do
      es.last.quellen.add(quellen[i][j]);
    for j:=0 to ziele[i].count-1 do
      es.last.ziele.add(ziele[i][j]);

    neuSums.clear;
    for j:=0 to quellen[i].count-1 do
      neuSums.add(escapeStringToRegex(escape(quellen[i][j].name,'$','\'),rtShell,'"/'));
    for j:=0 to ziele[i].count-1 do
      neuSums.add(escapeStringToRegex(escape(ziele[i][j].name,'$','\'),rtShell,'"/'));
    neuSums.sort;
    neuSums.uniq('-');
    neuSums.appendTo(                              // Quell- und Zielsummen entfernen
      es.last.befehle,
      argMax div 20,
      'sed "/ ',
      '\$/d; / ',
      '\$/d" -i "'+escape(_pruefSummenDatei,'"\','\')+'"'
    );

    neuSums.clear;
    for j:=0 to quellen[i].count-1 do
      neuSums.add(quellen[i][j].name);
    neuSums.sort;
    neuSums.uniq('-');
    neuSums.appendTo(                              // Quellsummen erzeugen
      es.last.befehle,
      argMax div 20,
      'sha512sum "',
      '" "',
      '" >> "'+escape(_pruefSummenDatei,'"\','\')+'"'
    );

    for j:=0 to befehleFkt.count-1 do begin        // eigentliche Befehle ausführen
      s:=befehleFkt[j];
      if quellErsetzung(s,rtKein,quellen[i],quellen[i].count) then begin
        es.last.befehle.add(s);
        inc(befCnt);
      end;
    end;
    if befCnt=0 then
      fehler(
        'Keine Befehle auszuführen für explizite Abhängigkeit!'#10+
        'Befehle:'#10+
        befehleFkt.text+
        'Quellen:'#10+
        quellen[i].toString
      );

    neuSums.clear;
    for j:=0 to ziele[i].count-1 do
      neuSums.add(ziele[i][j].name);
    neuSums.sort;
    neuSums.uniq('-');
    neuSums.appendTo(                              // Zielsummen erzeugen
      es.last.befehle,
      argMax div 20,
      'sha512sum "',
      '" "',
      '" >> "'+escape(_pruefSummenDatei,'"\','\')+'"'
    );
  end;
  neuSums.free;
end;

function tGenerischeAbhaengigkeit.count: longint;
begin
  result:=length(_quellens);
end;

// tExpliziteAbhaengigkeit **************************************************************

constructor tExpliziteAbhaengigkeit.create;
begin
  inherited create;
  quellen:=tDateienMitDaten.create;
  ziele:=tDateienMitDaten.create;
  befehle:=tStringList.create;
end;

destructor tExpliziteAbhaengigkeit.destroy;
begin
  quellen.free;
  ziele.free;
  befehle.free;
  inherited destroy;
end;

function tExpliziteAbhaengigkeit.hatQuelleVonAlsZiel(abh: tExpliziteAbhaengigkeit): boolean;
begin
  result:=not abh.quellen.istDisjunktZu(ziele);
end;

function tExpliziteAbhaengigkeit.ersetzbarDurch(abh: tExpliziteAbhaengigkeit): boolean;
begin
  result:=abh.ziele.istNamenObermengeVon(ziele);
end;

function tExpliziteAbhaengigkeit.pruefeObZuTun: boolean;
var
  i:       longint;
  quA,ziA: tAktualitaet;
begin
  quA:=aAktuell;                         // bis auf weiteres gehen wir davon aus, dass die Quellen aktuell sind
  for i:=0 to quellen.count-1 do
    if quellen[i].aktuell<>aAktuell then // nicht aktuelle Quellen
      quA:=aWirdErneuert;                // werden sicherlich erneuert werden
  ziA:=aAktuell;                         // bis auf weiteres gehen wir davon aus, dass die Ziele aktuell sind
  for i:=0 to ziele.count-1 do
    ziA:=min(ziA,ziele[i].aktuell);

  result:=ziA<quA;
  if result then
    for i:=0 to ziele.count-1 do
      ziele[i].aktuell:=aWirdErneuert;
end;

function tExpliziteAbhaengigkeit.dump: string;
var
  i: longint;
begin
  result:='';
  for i:=0 to befehle.count-1 do
    result:=result+#10'B: '+befehle[i];
  for i:=0 to quellen.count-1 do
    result:=result+#10'Q: '+quellen[i].name;
  for i:=0 to ziele.count-1 do
    result:=result+#10'Z: '+ziele[i].name;
  delete(result,1,1);
end;

// tMach ***********************************************************************

constructor tMach.create(machDatei, pruefSummenDatei: string; warten: boolean);
begin
  inherited create;
  _oriAbh:=tGenerischeAbhaengigkeiten.create;
  _mglAbh:=tExpliziteAbhaengigkeiten.create;
  _dats:=tDateienMitDaten.create;
  _warten:=warten;
  _ueberwachteDateien:=tMyStringList.create;

  // machDatei teilweise prüfen und setzen
  if machDatei='' then begin
    machDatei:=pwd+'/';
    while (machDatei<>'/') and not fileExists(machDatei+'Machdatei') do begin
      delete(machDatei,length(machDatei),1);
      machDatei:=extractFilePath(machDatei);
    end;
    machDatei:=machDatei+'Machdatei';
  end;
  _machDatei:=machDatei;
  if not fileExists(_machDatei) then
    fehler('Datei '''+_machDatei+''' existiert nicht!');

  // pruefSummenDatei teilweise prüfen und setzen
  if pruefSummenDatei='' then
    pruefSummenDatei:=extractFilePath(_machDatei)+'.summen';
  _pruefSummenDatei:=pruefSummenDatei;

  // finale Prüfung / finales Einlesen
  if not liesMachDatei then
    fehler('Datei '''+_machDatei+''' ist fehlerhaft!');
  if not liesPruefsummenfile then
    fehler('Datei '''+_pruefSummenDatei+''' ist fehlerhaft!');
end;

destructor tMach.destroy;
var
  i: longint;
begin
  _oriAbh.mrProper;
  _oriAbh.free;
  _mglAbh.mrProper;
  _mglAbh.free;
  _dats.mrProper;
  _dats.free;
  _ueberwachteDateien.free;
  for i:=0 to length(_ign)-1 do
    _ign[i].free;
  setLength(_ign,0);
  inherited destroy;
end;

function tMach.liesMachDatei: boolean;
var
  f:             tMyStringList;
  s,t:           string;
  na:            tGenerischeAbhaengigkeit;
  rek:           boolean;
  posi:          longint;
  wasWar,wasIst: tZeilenTyp;

procedure aufraeumen;
begin
  f.free;
  na.free;
end;

begin
  result:=false;

  na:=tGenerischeAbhaengigkeit.create(_dats,_machDatei,_pruefSummenDatei);
  wasWar:=ztSuche;
  f:=tMyStringList.create;
  f.loadFromFile(_machDatei);
  f.add('%%DATEIENDE%%');
  if not f.unfoldMacros then begin
    f.free;
    gibAus('tMach.liesMachDatei: unfoldMacros fehlgeschlagen!',3);
    exit;
  end;
  s:='';
  while f.readln(s) do begin
    if rightStr(s,1)=';' then
      // ein Befehl(steil)
      wasIst:=ztBefehl
    else if rightStr(s,1)=':' then
      // ein Ziel
      wasIst:=ztZiel
    else if ((leftStr(s,1)='^') and (rightStr(s,1)='$')) or // ein Quell-Regex
      ((leftStr(s,1)='"') and (rightStr(s,1)='"')) then     // ein Quell-String
      wasIst:=ztQuelle
    else
      // eine zu überwachende Datei
      wasIst:=ztSuche;

    if wasIst in [ztBefehl] then
      delete(s,length(s),1);

    if (wasWar=ztBefehl) and (wasIst<>ztBefehl) then begin
      _oriAbh.add(na);
      na:=tGenerischeAbhaengigkeit.create(_dats,_machDatei,_pruefSummenDatei);
    end;

    if s='%%DATEIENDE%%' then break;

    case wasIst of
      ztSuche: begin
        allgemeineErsetzungen(s,rtKein,_machDatei);
        if startetMit('!',s) then begin
          setLength(_ign,length(_ign)+1);
          _ign[length(_ign)-1]:=tRegExpr.create;
          _ign[length(_ign)-1].expression:=s;
        end
        else begin
          rek:=startetMit('-r',s);
          while s<>'' do begin
            _ueberwachteDateien.add(char(ord('0')+byte(rek))+s);
            if sammleDateien(erstesArgument(s),rek)=0 then begin
              f.stepBack;
              f.readln(s);
              gibAus('Fehler: Ich habe etwas zu überwachendes nicht gefunden ('''+s+''').',3);
              aufraeumen;
              exit;
            end;
          end;
        end;
      end;
      ztBefehl: begin
        while unEscapedPos(';',s)>0 do begin
          posi:=unEscapedPos(';',s);
          s:=trim(leftStr(s,posi-1))+' && '+trim(rightStr(s,length(s)-posi));
        end;
        while pos(';;',s)>0 do
          delete(s,pos(';;',s),1);
        na.befehleFkt.add(s);
      end;
      ztZiel:
        while s<>'' do begin
          t:=erstesArgument(s);
          if rightStr(t,1)=':' then
            delete(t,length(t),1);
          na.zieleFkt.add(t);
        end;
      ztQuelle: begin
        setLength(na.quellenREs,length(na.quellenREs)+1);
        na.quellenREs[length(na.quellenREs)-1]:=s;
      end;
    end{of case};
    wasWar:=wasIst;
  end;

  if s<>'%%DATEIENDE%%' then
    gibAus('Interner Fehler! Die letzte Regel wird vsl. nicht beachtet!',3);

  aufraeumen;
  result:=true;
end;

function tMach.liesPruefsummenfile: boolean;
var
  f:            textFile;
  i:            longint;
  gutSchlecht:  tMyStringListBArray;
  gefunden,gut: boolean;
  dat:          tDateiMitDatum;
begin
  result:=false;
  if _pruefSummenDatei='' then begin
    gibAus('Fehler: Leerer Name als Summendatei angegeben!',3);
    exit;
  end;

  if not fileExists(_pruefSummenDatei) then begin
    assignFile(f,_pruefSummenDatei);
    rewrite(f);
    closeFile(f);
  end;
  if not fileExists(_pruefSummenDatei) then begin
    gibAus('Fehler: Ich bin nicht in der Lage, die bisher nicht existierende Datei '''+_pruefSummenDatei+''' anzulegen!',3);
    exit;
  end;

  gutSchlecht:=testeSummen(_pruefSummenDatei);

  for gut:=false to true do
    for i:=0 to gutSchlecht[gut].count-1 do begin
      dat:=_dats.finde(gutSchlecht[gut][i]);
      if gut then begin
        if dat.aktuell=aNichtVorhanden then begin
          gibAus('Fehler: In der Summendatei gibt es eine Datei mit gültiger Prüfsumme, die ich nicht finden kann: '''+dat.name+'''!',3);
          for gefunden:=false to true do
            gutSchlecht[gefunden].free;
          exit;
        end;
        dat.aktuell:=aAktuell;
      end
      else
        if dat.aktuell<>aNichtVorhanden then
          dat.aktuell:=aVeraltet;
    end;

  for gefunden:=false to true do
    gutSchlecht[gefunden].free;
  result:=true;
end;

function tMach.sammleDateien(wo: string; rekursiv: boolean): longint;
var
  sR:        tSearchRec;
  err,i:     longint;
  weglassen: boolean;
  rest:      string;
begin
  result:=0;
  rest:='';
  if pos('*',wo)>0 then begin // wir müssen globben
    rest:=wo;
    erstesArgument(rest,'*',false);
    erstesArgument(rest,'/',false);
    if rest<>'' then
      delete(wo,length(wo)-length(rest),length(rest)+1);
  end;
  if (rest='') and rekursiv then        // rekursive Suche angefordert
    rest:='*';
  err:=findFirst(wo,fareadOnly or faHidden or faSysFile or (byte(rest<>'')*faDirectory),sR);
  while err=0 do begin
    weglassen:=false;
    for i:=0 to length(_ign)-1 do
      weglassen:=weglassen or _ign[i].exec(extractFilePath(wo)+sR.name);
    if not weglassen then begin
      if sR.attr and faDirectory <> 0 then begin
        if (rest<>'') and
          (sR.name<>'.') and
          (sR.name<>'..') then
            result:=result+sammleDateien(extractFilePath(wo)+sR.name+'/'+rest,rekursiv);
      end
      else if (rest='') or (rest='*') then begin
        inc(result);
        _dats.add(tDateiMitDatum.create(extractFilePath(wo)+sR.name,aVeraltet));
      end;
    end;
    err:=findNext(sR);
  end;
  findClose(sR);
end;

procedure tMach.erzeugeRegeln;
var
  i:     longint;
  neues: boolean;
begin
  repeat
    neues:=false;

    for i:=0 to _oriAbh.count-1 do
      if _oriAbh[i].findeQuellen(_dats) then
        neues:=true; // neue Dateien sind entstanden

  until not neues;

  for i:=0 to _oriAbh.count-1 do
    _oriAbh[i].generiereErben(_mglAbh);
end;

procedure tMach.findeWasZuTunIst;
var
  i,j:                       longint;
  neues:                     boolean;
  zuTunDurch,inversToepfe:   tLongintArray;
  redundanzenEntfernThreads: array of tRedundanzenEntfernThread;
  kritischerAbschnitt:       tRTLCriticalSection;
  fertig:                    boolean;
  toepfe:                    tLongintArrayArray;
begin
  setLength(zuTunDurch,_mglAbh.count);
  for i:=0 to length(zuTunDurch)-1 do
    zuTunDurch[i]:=-1;

  j:=0;
  // schauen, welche Regeln angewandt werden müssen
  repeat
    neues:=false;
    for i:=0 to length(zuTunDurch)-1 do
      if zuTunDurch[i]=-1 then
        if _mglAbh[i].pruefeObZuTun then begin
          inc(j);
          zuTunDurch[i]:=i;
          neues:=true;
        end;
  until not neues;

  setLength(toepfe,max(1,round(sqrt(j)))); // wir verteilen die _mglAbh je nach ihren Zielen auf toepfe
  for i:=0 to length(toepfe)-1 do
    setLength(toepfe[i],0);
  setLength(inversToepfe,length(zuTunDurch));
  for i:=0 to length(inversToepfe)-1 do
    inversToepfe[i]:=-1;
  for i:=0 to length(zuTunDurch)-1 do
    if zuTunDurch[i]>=0 then
      for j:=0 to _mglAbh[i].ziele.count-1 do begin
        inversToepfe[i]:=pruefSumme(_mglAbh[i].ziele[j].name,length(toepfe)); // wir merken uns nur den Topf des letzten Zieles - (mindestens) in diesem Topf muss auch die Obermenge liegen
        setLength(toepfe[inversToepfe[i]],length(toepfe[inversToepfe[i]])+1);
        toepfe[inversToepfe[i]][length(toepfe[inversToepfe[i]])-1]:=i;
      end;

  for i:=0 to length(zuTunDurch)-1 do begin
    assert(_mglAbh[i].ziele.count>0,'Hier ist eine Abhängigkeit ohne Ziele!');
    _mglAbh[i].ziele.sItems[0]; // sortieren!
  end;

  // schauen, welche Regeln redundant sind
  initCriticalSection(kritischerAbschnitt);
  setLength(redundanzenEntfernThreads,numCpus);
  for i:=0 to length(redundanzenEntfernThreads)-1 do
    redundanzenEntfernThreads[i]:=tRedundanzenEntfernThread.create(i,length(redundanzenEntfernThreads),_mglAbh,@zuTunDurch,@inversToepfe,@toepfe,@kritischerAbschnitt);
  repeat
    fertig:=true;
    for i:=0 to length(redundanzenEntfernThreads)-1 do
      fertig:=redundanzenEntfernThreads[i].fertig and fertig;
    if not fertig then
      sleep(10);
  until fertig;
  for i:=0 to length(redundanzenEntfernThreads)-1 do
    redundanzenEntfernThreads[i].free;
  doneCriticalsection(kritischerAbschnitt);

  for i:=length(zuTunDurch)-1 downto 0 do
    if zuTunDurch[i]<>i then begin
      _mglAbh[i].free;
      _mglAbh.delete(i);
    end;
  setLength(zuTunDurch,0);

  // anzuwendende Regeln sortieren
  _mglAbh.sort;
end;

procedure tMach.tueWasZuTunIst(sicher: integer; ausgabeDatei: string);
var
  i,j:                       longint;
  ausg:                      textFile;
  befehle,alleDateien:       tMyStringList;
  lokTest:                   tRegExpr;
begin
  befehle:=tMyStringList.create;
  befehle.add('printf .');
  for i:=0 to _mglAbh.count-1 do
    for j:=0 to _mglAbh[i].befehle.count-1 do
      befehle.add(_mglAbh[i].befehle[j]);
  befehle.add('sed "/\s'+escapeStringToRegex(escape(_machDatei,'$','\'),rtShell,'"/')+'\$/d" -i "'+escape(_pruefSummenDatei,'"\','\')+'"');
  befehle.add('sha512sum "'+escape(_machDatei,'"\','\')+'" >> "'+escape(_pruefSummenDatei,'"\','\')+'"');
  befehle.add('sort -u "'+escape(_pruefSummenDatei,'"\','\')+'" | sponge "'+escape(_pruefSummenDatei,'"\','\')+'" || true'); // ignoriere diese Zeile, wenn "sponge" nicht existiert
  if (sicher=1) or // der Benutzer will es
    ((sicher=0) and (_dats.finde(_machDatei).aktuell<>aAktuell)) then begin // die Machdatei ist nicht aktuell
    lokTest:=tRegExpr.create;
    if ausgabeDatei<>'' then
      lokTest.expression:=unterVerzeichnisRegex(['0'+ausgabeDatei,_ueberwachteDateien])
    else
      lokTest.expression:=unterVerzeichnisRegex([_ueberwachteDateien]);
    alleDateien:=_dats.toMyStringList;
    alleDateien.grep('^\.uralt\.$',true);
    for i:=0 to befehle.count-1 do
      testeObBefehlLokal(befehle[i],extractFileDir(ausgabeDatei),alleDateien,lokTest);
    alleDateien.free;
    lokTest.free;
  end;

  if _mglAbh.count=0 then
    befehle.add('echo "Es gibt hier nichts zu tun!"');
  if ausgabeDatei='' then begin
    gibAus('befehle:',3);
    for i:=0 to befehle.count-1 do
      writeln(befehle[i]);
  end
  else begin
    assignFile(ausg,ausgabeDatei);
    rewrite(ausg);
    writeln(ausg,'set -e');
    for i:=0 to befehle.count-1 do begin
      write(ausg,'('+befehle[i]+') || (printf ''In\n"%s"\n'' "'+escape(befehle[i],'\"','\')+'"; ');
      if _warten then
        writeln(ausg,'read -p "ist ein Fehler aufgetreten! ... "; exit 1)')
      else
        writeln(ausg,'printf ''ist ein Fehler aufgetreten!\n''; exit 1)');
    end;
    closeFile(ausg);
  end;
  befehle.free;
end;

function tMach.anzOriAbh: longint;
begin
  result:=_oriAbh.count;
end;

function tMach.anzMglAbh: longint;
begin
  result:=_mglAbh.count;
end;

function tMach.anzDats: longint;
begin
  result:=_dats.count;
end;

// tRedundanzenEntfernThread ***************************************************

constructor tRedundanzenEntfernThread.create(nummer,anzahl: longint; moeglicheAbhaengigkeiten: tExpliziteAbhaengigkeiten; zuTunDurch,inversToepfe: pTLongintArray; toepfe: pTLongintArrayArray; kritischerAbschnitt: pRTLCriticalSection);
begin
  inherited create(true);
  num:=nummer;
  anz:=anzahl;
  mglAbh:=moeglicheAbhaengigkeiten;
  ztd:=zuTunDurch;
  tpf:=toepfe;
  itpf:=inversToepfe;
  kA:=kritischerAbschnitt;
  fertig:=false;
  suspended:=false;
end;

procedure tRedundanzenEntfernThread.execute;
var
  i,j: longint;
begin
  i:=num;
  while i<=length(ztd^)-1 do begin
    if ztd^[i]=i then begin
      assert(mglAbh[i].ziele.istSortiert,'tRedundanzenEntfernThread.execute: mglAbh['+intToStr(i)+'].ziele sind nicht sortiert - das kann ich im Thread aber nicht machen!');
      for j:=0 to length(tpf^[itpf^[i]])-1 do begin
        assert(mglAbh[tpf^[itpf^[i],j]].ziele.istSortiert,'tRedundanzenEntfernThread.execute: mglAbh['+intToStr(tpf^[itpf^[i],j])+'].ziele sind nicht sortiert - das kann ich im Thread aber nicht machen!');
        if (ztd^[tpf^[itpf^[i],j]]>=0) and (i<>tpf^[itpf^[i],j]) and mglAbh[i].ersetzbarDurch(mglAbh[tpf^[itpf^[i],j]]) then begin // ersetzbarDurch ist transitiv!
          enterCriticalsection(kA^);
          mglAbh[ztd^[tpf^[itpf^[i],j]]].quellen.append(mglAbh[i].quellen);
          ztd^[i]:=ztd^[tpf^[itpf^[i],j]];
          leaveCriticalsection(kA^);
          break;
        end;
      end;
    end;
    i:=i+anz;
  end;
  fertig:=true;
end;

// tBedingungFindeThread *******************************************************

constructor tBedingungFindeThread.create(nummer,anzahl: longint; toepfe: pTIntPointArrayArray; expliziteAbhaengigkeiten: tExpliziteAbhaengigkeiten);
begin
  inherited create(true);
  num:=nummer;
  anz:=anzahl;
  tpf:=toepfe;
  eas:=expliziteAbhaengigkeiten;
  fertig:=false;
  fillChar(bedingungen,sizeOf(bedingungen),0);
  setLength(bedingungen,0);
  suspended:=false;
end;

destructor tBedingungFindeThread.destroy;
begin
  inherited destroy;
end;

procedure tBedingungFindeThread.execute;
var
  i,j,k,topf: longint;
begin
  i:=num;
  while i<eas.count do begin
    for j:=0 to eas[i].quellen.count-1 do begin
      topf:=pruefSumme(eas[i].quellen[j].name,length(tpf^));
      for k:=0 to length(tpf^[topf])-1 do
        if (i<>tpf^[topf,k,'x']) and
          (eas[tpf^[topf,k,'x']].ziele[tpf^[topf,k,'y']].name = eas[i].quellen[j].name) then begin

          setLength(bedingungen,length(bedingungen)+1);
          bedingungen[length(bedingungen)-1,'x']:=tpf^[topf,k,'x'];
          bedingungen[length(bedingungen)-1,'y']:=i;
        end;
    end;
    i:=i+anz;
  end;
  fertig:=true;
end;

// allgemeine Funktionen

procedure allgemeineErsetzungen(var worin: string; worinIstRegex: tRegexTyp; machDatei: string);
var
  i:              longint;
  s,anfang,mitte: string;
begin
  s:=extractFilePath(machDatei);
  if rightStr(s,1)='/' then
    delete(s,length(s),1);
  ersetzeAlleVorkommen(worin,'%DIRNAME%',escapeStringToRegex(s,worinIstRegex));
  while pos('%num''',worin)>0 do begin
    anfang:=erstesArgument(worin,'%num''');
    mitte:=erstesArgument(worin,'''%',false);
    for i:=length(mitte) downto 1 do
      if mitte[i] in ['0'..'9'] then
        break
      else
        delete(mitte,i,1);
    for i:=length(mitte) downto 1 do
      if not (mitte[i] in ['0'..'9']) then begin
        delete(mitte,1,i);
        break;
      end;
    worin:=anfang+escapeStringToRegex(mitte,worinIstRegex)+worin;
  end;
end;

end.