Makepp Erweiterung

Makepp Erweiterungsprojekte

Makepp http://makepp.sf.net ist ein erheblich verbesserter GNU make Klon, der dessen große Schwächen ausbügelt. Da Makepp in Perl ab der Version 5.6 geschrieben ist, und da hier am Herz operiert wird, ist Voraussetzung an die Bewerber eine gute, für die ersten 3 Projekte eher sehr gute, Beherrschung von Perl. Die umfangreichen Regressionstests von Makepp, sowie eine testweise Anwendung auf zwei unterschiedliche Großprojekte bei Amadeus, sollen die Korrektheit der Lösung gewähren.

Sehr nützlich ist ein Verständnis der Zusammenhänge beim Übersetzen und Binden. Kenntnis einer make Variante, gerne auch der vergleichbaren Ansätze in ant, jam oder cook, ist von großem Vorteil. Auch Prolog Kenntnis kann als Erfahrung mit einer deklarativen Programmierweise dienen.

Das 2. und 3. Projekt ergänzen einander. Man könnte sie zu einem sehr ambitionierten Projekt bündeln, oder auch zu zweit, mit Abstimmung zwischen den Lösungen, angehen.

Voraussetzung für eine Zusammenarbeit ist, daß die Ergebnisse unter der Perl-üblichen GPL ≥ 2 und Artistic Doppellizensierung zur Verfügung stehen, und in die öffentliche makepp Versionsverwaltung einfließen dürfen.

1. Parser Reimplentierung mit while und foreach

Wenn Makepp im Kern auch auf deklarativer Programmierung basiert, so gibt es doch auch imperative Elemente, wie Variablenzuweisungen oder Anweisungen wie if. Bislang gibt es in Makepp eine umfangreiche if Erweiterung gegenüber GNU make, beispielsweise:

ifdef ABC
  and ifdef DEF
or ifdef GHI
  and ifdef JKL
    ...
else ifdef MNO
or ifdef PQR
    ...
else
    ...
endif

Realisiert werden soll folgende rein syntaktische Erweiterung, wobei die Variable schleifenlokal gesetzt wird:

foreach X = 1 2 3
    ...
endforeach

Hierbei werden die Zeilen dazwischen 3x gelesen, und X hat nacheinander erst den Wert 1, dann 2, dann 3, danach wieder den, den es vorher hatte. Hätte es += geheißen, und wäre X vorher a gewesen, dann wäre es ``a 1'', dann ``a 2'', dann ``a 3'' und danach wieder a. Makepp hat eine $[X] Notation, die hier besonders interessant ist, da sie schon beim Lesen der Zeile ersetzt wird, und nicht erst beim Auswerten einer Regel. Sie wird dann beim 3 maligen Lesen 3x anders ersetzt werden.

Zum Beispiel haben wir folgende Zeilen:

foreach X := 1 2 3
    prog$[X]: LDFLAGS = $(LDFLAGS$[X])
endforeach
A = abc 
foreach A += def 'ghi jkl' mno
    &echo $[A]
endforeach
&echo $[A]

Makepp soll dies lesen, als hätte da gestanden:

    prog1: LDFLAGS = $(LDFLAGS1)
    prog2: LDFLAGS = $(LDFLAGS2)
    prog3: LDFLAGS = $(LDFLAGS3)
A = abc 
    &echo abc def
    &echo abc 'ghi jkl'
    &echo abc mno
&echo abc

Analog soll es eine while Schleife geben, welche genau alle if Varianten spiegelt (wobei whilesys nur der Vollständigkeit halber Sinn macht, da sich das System nicht ändert). Wir suchen alle .x Dateien im von mehreren Verzeichnissen ersten, welches überhapt solche enthält -- die Schleife endet wenn DIRS leer wird, oder RESULT etwas enthält (also nicht gleich garnichts ist), wildcard also fündig wurde:

DIRS := dir1 dir2 dir3
whiledef DIRS
and whileeq $(RESULT)
    RESULT := $(wildcard $(firstword $(DIRS))/*.x)
    DIRS := $(wordlist 2, -1, $(DIRS))
endwhile

Die Schachtelung muß in jeder Kombination sauber abgearbeitet werden. So wird die Zeile A immer wieder gesehen, und das ifdef getestet solange die while Bedingung wahr ist. Jedesmal wenn dabei das ifdef wahr ist wird die Zeile B gesehen und die foreach Schleife durchlaufen. Die Zeile C wird also in Abhängikeit der Bedingung zwischen 0 und n · m (Anzahl while Iterationen mal Anzahl foreach Iterationen) gesehen:

whiledef ...
  A
  ifdef ...
    B
    foreach ...
      C
    endforeach
  endwhile
endif

Zur Diagnose braucht man noch eine geschachtelte Zeilennummerierung: 11.3.2 ist die 11. Zeile in der 3. Iteration der äußeren Schleife und der 2. der inneren Schleife. Diese erweiterte Nummer soll der Parser zu jeder Zeile speichern, so wie er jetzt bereits die einfache Nummer speichert.

Makepp hat eine recht vertrackte Eingabeschleife in den Modulen Makefile.pm und, für mehrzeilige Anweisungen, wie define oder sub, noch in Makesubs.pm. Der Haken an der Sache sind die if* Anweisungen die darüber entscheiden, welche Zeilen gesehen werden, und welche nicht. Auch in nicht gesehenen Zeilen müssen geschachtelte if*, define usw. Anweisungen korrekt übersprungen werden, zukünftig dann auch while* und foreach. Dies geschieht momentan nicht 100% konsistent, da je nach Konstellation an verschiedenen Stellen das Gleiche gemacht wird.

Dass Neue in eine schon überfrachtete Leseschleife anzubauen, würde sie noch unwartbarer machen. Gewünscht ist daher, den Parser neu zu konzipieren, so daß er aus einem Guß die alten und neuen Anforderung abdeckt, und sich dadurch immer konsistent verhält. An allen anderen Stellen parst Makepp mit Perl's elegantem /\G.../gc Mechanismus. Das sollte auch beim Lesen nachgezogen werden.

Wichtig ist, alles durch möglichst leichtgewichtige reguläre Ausdrücke zu lösen, so daß die Schleife eher schneller, aber auf keinen Fall langsamer arbeitet. Dies kann außerhalb von Makepp mit dem Befehl makeppbuiltin preprocess nachgewiesen werden, der die Makepp Leseschleife mit if*, und zukünftig auch foreach und while*, Anweisungen als Präprozessor zur Verfügung stellt. Zur Absicherung müssen aussagekräftige Testfälle in die Regressionstests eingebaut werden.

Die Parserreimplementierung ist eine gute Gelegenheit, einen anderen Mißstand abzuschaffen: Momentan führt ein Doppelpunkt, der nicht Teil von ':=' ist, dazu, die Zeile als Regel zu betrachten. Das führt dazu, daß solche Zeilen scheinbar verschluckt werden, da sie in der jeweils zweiten Interpretation gelesen werden:

perl { print qq!Hier: steht doch keine Regel, oder?\n! }
perl { print qq!Hier: steht doch keine Regel, oder?\n! }
&echo Hier: steht doch keine Regel, oder?
&echo Hier: steht doch keine Regel, oder?

Hier soll überlegt werden, ob es Fälle gibt, wo die Rückwärtskompatibilität dies verlangt. Diese Überlegung soll im makepp-Forum publik gemacht werden. Gibt es keinen Hinderungsgrund, soll das Schlüsselwort am Anfang der Zeile vorrangig erkannt werden.

2. Parallele CommandParser und Scanner

Makepp guckt sich Befehle an und erkennt an den Parametern implizite Abhängigkeiten. So bedeutet die Bindeoption -lxyz, daß eine Datei libxyz.so oder .a gebraucht wird. Ein Argument xyz.cpp heißt nicht nur, daß diese Datei gebraucht wird (und z.B. ggf. erst per Präprozessor aus embedded SQL erzeugt werden muß). Vielmehr wird diese Datei dann vom Scanner auf #include Anweisungen durchsucht, die wiederum evtl. eine Dateierzeugung anstoßen, und anschließend rekursiv selber gescannt werden.

Eine Analyse mit perl -d:DProf gibt immer wieder folgenden gekürzten Aufrufbaum:

Scanner::include
   Scanner::find
      FileInfo::exists_or_can_be_built_or_remove
         ...
   Scanner::get_tagname
   CommandParser::add_dependency
      ActionParser::add_dependency
         ActionParser::add_any_dependency_
            Rule::add_meta_dependency
               Rule::add_any_dependency_
                  main::build
                     ...
                  MakeEvent::wait_for

Wie man am Ende sieht, wir die Erzeugung jeweils abgewartet. Währenddessen können auch alle Aufträge die bereits eingereiht wurden, abgearbeitet werden, aber es kommen keine neuen hinzu, bis diese Stelle verlassen wird. Das Ergebnis ist, daß die Warteschlange austrocknen kann, und nur ein Teil der vorgegebenen Parallelisierung ausgeschöpft wird.

Die Lösung wäre hier, statt nach wait_for weiterzumachen, mit when_done die Folgeverarbeitung einzureihen, und währenddessen andere CommandParser oder Scanner ihre Aufträge abarbeiten zu lassen. Was trivial klingt, bedeutet womöglich ein massives Umkrempeln der aktiven Hauptschleife in eine ereignisgetriebene. Abläufe, die sich über mehrere Klassen und geschachtelte Methodenaufrufe erstrecken, müßten im Objektstatus eingefroren und beizeiten wieder aufgetaut werden. Scanner sollten prior so früh wie möglich wieder geweckt werden, da sie ja eine Datei offen halten und die Anzahl gleichzeitig geöffneter Dateien vom System beschränkt ist.

Evtl. gibt es auch eine weniger invasive Lösung, bei der sich aber auch die Schnittstellen aller betroffenen Methoden ändern würden. In dem Szenario wird auf alles was nicht an der Stelle gebraucht wird erst zum spätest möglichen Zeitpunkt reagiert. Dafür würden die build_handles soweit nach oben gereicht, bis sie gebraucht werden. Dies könnte zu weniger Stellen mit Einfrierungsbedarf führen. Könnte ein Ansatz wie Coro oder Coro::Cont das alles noch einfacher machen?

Auch muß geschaut werden, was parallel passieren darf, z.B. die Befriedigung mehrerer -lxyz Optionen, da diese unabhängig voneinander sind. Der CommandParser darf aber insgesamt erst zurückkehren, wenn alles erledigt ist. Beim Scanner gibt es zwei Modi. Der einfache nimmt an, daß alle #include Anweisungen benötigt werden, kann diese mithin parallel bearbeiten. Der schlaue berücksichtigt auch #define und #ifdef, muß also sequentiell arbeiten, soll aber, während er wartet, andere CommandParser oder Scanner zum Zuge kommen lassen.

3. Effizientere Auftrags- und Ereignisabarbeitung

Die Möglichkeiten hier etwas zu verbessern sind noch nicht gründich erforscht! Als Ergebnis könnte die frustrierende Feststellung, daß so keine signifikante makepp Verbesserung erzielbar ist, hearuskommen.

Die Abarbeitung der eigentlichen Befehle in makepp ist etwas schwerfällig. Im Falle von Parallelisierung gibt erst mal eine Endebehandlung die gesammelten Ausgaben aus (damit die nicht von mehreren Befehlen durcheinander kommen) und reicht den Rückgabewert weiter. Eine Nachbehandlung speichert den Rückgabewert im Statusfeld des zugehörigen Objekts.

Eine nächste Nachbehandlung bündelt die Erledigung sämtlicher Schritte einer Regel, und meldet alle Ausgaben als erledigt, so daß andere Regeln wiederum anlaufen können.

Die vielen Schritte werden dadurch verschlimmert, daß im $SIG{CHLD} keine eigentliche Verarbeitung stattfindet, sondern nur das Eintreffen des Signals hochgezählt wird. Dies ist wohl insbesondere bei Perl 5.6 und möglicherweise ab 5.8.1 mit $ENV{PERL_SIGNALS} eq 'unsafe' notwendig, da das Innere der Signalbehandlung nicht sicher ist.

Stattdessen wird an geeigneten Stellen gepollt, ob Prozesse beendet sind, und diese werden dann nachbearbeitet. Pollen ist leider eine verschwenderische Vorgehensweise, zumal das System uns Bescheid gibt! Aus dieser Einleitung ergeben sich zwei Ansätze, die Abläufe zu straffen.

Ein erster Teil der Aufgabe lautet, durch Internetrecherche und experimentell einen Mechanismus zu identifizieren, sei es Signalbehandlung, private Semaphore, select oder noch etwas anderes, um effizienter auf Ereignisse reagieren zu können. Dieser Mechanismus muß sehr portabel ab Perl 5.6 sein. Oder er muß, auf den Plattformen, wo er anwendbar ist, alternativ auswählbar sein. Multithreading ist vermutlich keine Lösung, da in Perl einerseits die API noch nicht lange gefestigt ist, und das behäbige Modell wohl eher auf unabhängige Perls innerhalb eines Apache-Prozesses zielt, denn auf Java-artige Parallelisierung einer Aufgabe.

Um diesen Kern herum sollen die Ereignisabläufe gestrafft werden. Ich denke, es wird drei Auftragsklassen geben:

  1. Interne Aufträge die knappe Ressourcen belegen (Scanner)

  2. Sonstige interne Aufträge

  3. Externe Aufträge (Kindprozesse unter Unix)

Diese Reihenfolge gibt die Priorisierung beim Anstarten vor. Bei einer Option -jJ werden, wenn einer der ersten beiden ablaufbereit ist, erst J-1 externe Aufträge und dann einer von diesen. Liegt keiner an, können J externe Aufträge starten. Auch in diesem Thema könnte die Eignung von Coro oder Coro::Cont untersucht, und ggf. umgestellt werden.

4. Automatische Konfigurierung

Es gibt viele Fragen beim Portieren von Programmen, insbesondere in C/C++. Wie man echo portabel einen Zeilenumbruch am Ende abgewöhnt, ist dank des eingebauten Befehls in makepp keine Frage. Knifflig ist, ob die Funktion xyz oder alternativ wenigstens xyz1 überhaupt verfügbar ist, wenn ja in welcher Datei sie deklariert wird, welchen Typ die Parameter und der Rückgabewert haben, und inwieweit der mit einem anderen Typ kompatibel ist (signed/unsigned, Wertebereich/Anzahl Bytes...). Diese Fragen entscheiden zunehmend auch bei Amadeus über die Eignung von makepp bei selbstgeschriebenen Basisbibliotheken.

Es gibt viele Ansätze diese Fragen zu beantworten. Meist erzeugen sie ein größter gemeinsamer Nenner Shell Skript, das wiederum ein ggN Makefile erzeugt. Beides ist sehr umständlich um alle möglichen Fehler diverser Ausprägungen der Bourne Shell und make aus den 70ern zu umgehen. Die Ergebnisse sind so verknotet, daß makepp, trotz weitgehender Kompatibilität, seine liebe Not damit hat. Aber selbst wo es funktioniert, ist es witzlos, da die ganzen überlegenen Eigenschaften von makepp nicht zum Zuge kommen.

Ziel dieses Projekts ist es, ein Makeppfile Gerüst zu schaffen, in dem diese Tests ablaufen. Dann können die Tests parallelisiert werden, und man kann den eigentlichen Aufbau von der Konfiguration abhängen lassen, so daß bei Bedarf automatisch nachkongfiguriert wird. Das Gerüst würde aus einer allgemeinen Makeppfile bestehen, die alle Varianten von Tests (z.B kleines C Programm erzeugen, kompilieren und im Erfolgsfall starten) als Pattern-Regeln bereitstellt. Daneben werden vermutlich mehrere thematisch spezialisierte (z.B. Dateifunktionen) Makefiles die Regeln mit Leben füllen.

Damit diese riesige Wissensbasis nicht überall vorhanden sein muß, wäre es denkbar, sie einerseits in ein Ergänzungsarchiv, das man optional installiert, auszulagern, und andererseits daraus genau die Tests zu extrahieren, die man mit seinem Projekt ausliefern möchte.

Ein anderer Aspekt sind die Erkenntnisse, die makepp in .makepp Verzeichnissen speichert. Jede Datei die dort als einst generiert hinterlegt ist, und die jetzt nicht mehr generierbar ist, wird moniert. Man sollte also die Wahl haben, die Tests permanent aktiv zu haben, was Aktualität gewährleistet, aber als Bremse wirkt, oder aber die Ergebnisse in einem .makeppconf Verzeichnis zu speichern, und die Regeln auszublenden.

Um dieses Gerüst mit Regeln zu füttern, sollen die bestehenenden Konfiguratoren dahingehend untersucht werden, wie man deren Wissensbasis und Regelfundus möglichst automatisiert übernehmen kann. Die gängigen Konfiguratoren sind hierbei der Platzhirsch GNU autotools, dessen libtool evtl. übernommen werden könnte. Im Perl Umfeld ist dies natürlich Metaconfig mit ExtUtils::MakeMaker und Test::Harness. Desweiteren gibt es z.B. die mir nicht geläufigen Debian Dist oder AT&T Iffe.

Daniel Pfeiffer
Last modified: 2007-07-22