In diesen wunderbaren Januartagen sind wir natürlich alle besorgt über das Problem der Minimierung des Quellcodes bei gleichzeitiger Beibehaltung der Invariante. Ich meine, egal?!? Vergebens ... Hier ist der Compiler abgestürzt, und das Programm ist gigantisch - es ist für die Entwickler irgendwie unpraktisch, so etwas zu senden. Und dann beginnt der Spaß: Was passiert, wenn Sie es wegwerfen? Oh, es fällt nicht - okay, wir gehen, aber was ist, wenn es fällt? - stürzt immer noch ab, und dies und das ... Oh, ich habe den Compiler auf den alten Quellen gestartet.
Gleichzeitig ist die Automatisierung der Suche nach Fehlern eine Frage des Lebens: Git Bisect, Llvm-Bugpoint, Creduce, ... In diesem Artikel beschreibe ich einen weiteren Weg, um das Problem der Vereinfachung des Testfalls zu lösen, der in Bezug auf die Programmiersprache mehr oder weniger universell ist, und zeige einige Anwendungsbeispiele.
Universal, sag mal ... Vielleicht wurde es natürlich schon zehnmal umgesetzt, aber würde das einen erfahrenen Radfahrer aufhalten? Und in den Händen eines Mikroskops scheinen alle Probleme Nägel zu sein. In der Rolle eines Mikroskops - PMD .
Im Allgemeinen gibt es eine solche Sprache zum Schreiben von Modellen, die durch Differentialgleichungen beschrieben werden - Modelica. Es ist ziemlich weit fortgeschritten, es gibt eine sehr coole offene Implementierung und im Allgemeinen. Es gibt jedoch ein kleines Problem: Manchmal tritt im Compiler ein interner Compilerfehler auf. In einem früheren Artikel habe ich bereits gezeigt, wie man dem statischen PMD-Analysator zusätzlich zu den zehn vorhandenen Sprachmodulen die Modela-Unterstützung hinzufügt (einige meiner Fehler sind übrigens während des Überprüfungsprozesses aufgetreten). Nun entschied ich mich - was nützt es, zu verschwinden - und schickte ein Proof-of-Concept-Tool namens Source Code Minimizer, das die vorhandenen Sprachmodule PMD wiederverwendete. Leider haben sie mich - wenn auch nicht weit entfernt - in das benachbarte Depot geschickt: Der Menter sagte, er entscheide sich immer noch nicht, dies bis zum Ende des Jahrhunderts zu unterstützen, und es geht in der allgemeinen Codebasis verloren, sodass ich bald eine Einladung zur Mitarbeit in meinem Posteingang fand ist frisch erstellt pmd / pmd-scm .
Was ist die Erklärung des Problems? Es ist erforderlich, die Größe des Quellcodes zu reduzieren, wobei ein Teil seiner Eigenschaften erhalten bleibt. Genauer gesagt, ich möchte
- Der resultierende Code war vorhersehbar
- Es muss nicht so minimal wie möglich sein . Die Vervollständigung von Dateien ist zulässig, sollte jedoch nicht zu Qual werden
- automatische Verschleierung wird nicht berücksichtigt
- Das minimierte Programm kann in mehrere Dateien mit Quellcode unterteilt werden
- In Java muss sich beispielsweise jede
public Klasse in einer separaten Datei mit dem richtigen Namen usw. befinden. - Ich möchte, dass jede Datei am Ende sichtbar bleibt
- Bei Transformationen muss die angegebene Invariante erhalten bleiben
Internes Gerät
In diesem Abschnitt werde ich die Implementierung grob beschreiben. Zunächst stelle ich noch einmal fest, dass diese Idee, gelinde gesagt, nicht neu ist. Und wenn ich Git-Bisect nur als Beispiel für den "automatischen Debugging-Mechanismus" zitiert habe, bin ich über längere Zeit auf Creduce oder ähnliches gestoßen (obwohl ich es nicht verwendet habe). Aber ich musste llvm-bugpoint verwenden - es ist beeindruckend: Sie sitzen, debuggen Ihren LLVM-Pass und es - eine solche Infektion - stürzt auf einigen Dateisystemen ab. Sie können diese Datei also in LLVM-Bitcode kompilieren, opt für die .bc-Datei mit Ihrem Plugin ausführen und sicherstellen, dass sie abstürzt. Und dann habe ich grob gesagt nur opt durch llvm-bugpoint und in einer Minute ein umfangreiches „Skelett“ einer der Funktionen erhalten, das aus einer Wolke von Basisblöcken und Übergängen zwischen ihnen besteht. Alles außer Zweigen wurde erfolgreich weggeworfen. Übrigens, wie in meiner Aussage zum Problem, kam es nach einem Dutzend Minuten manueller Vereinfachung darauf an, dass ich einen der Verzweigungstypen falsch verarbeitete und alles andere nur Kulisse war. Im Allgemeinen ist die Idee nicht neu.
Und jetzt zur Umsetzung. Da es ein mehr oder weniger universelles Tool sein sollte, wollte ich eine Art Framework erstellen, in das wir für verschiedene Sprachen optimierte Implementierungen einbinden können. Als Ergebnis stachen zwei recht orthogonale Konzepte heraus:
- invariant unterstützt
- Minimierungsstrategie
Invariante
Eine der Optionen für die Eigenschaft, die Sie möglicherweise speichern möchten, habe ich bereits beschrieben: „Der Compiler hat einen Ausdruck auf die Konsole gedruckt“ (z. B. „Interner Compilerfehler“). Ideen können auch aus einer Vielzahl von Fuzzern gewonnen werden: AFL , Killerbeez und andere:
- Der Prozess endete mit einem Return-Code (insbesondere "Crash on Signal" unter Linux).
- Der Vorgang dauerte mehr als T Millisekunden. Hier kann leider Instabilität aufgrund der schwebenden Last des Systems auftreten. Um die Genauigkeit zu erhöhen, können Sie die CPU-Zeit verwenden. Im Idealfall sind jedoch Leistungsindikatoren hilfreich
- Der Compiler kann eine Ausgabedatei (nicht) generieren
- ...
Ich habe bereits einige davon implementiert (Rückkehrcode, gedruckte Zeile), einige nicht, einige sind möglicherweise spezifisch für einzelne Sprachen. Im Allgemeinen handelt es sich hierbei um einen ziemlich autonomen Teil der Aufgabe, der oft völlig unabhängig von einer bestimmten Sprache ist.
Minimierungsstrategie
Auf den ersten Blick ist hier alles rein sprachabhängig. Irgendwo müssen Sie Variablen zusammen mit Anwendungsfällen wegwerfen - um die gleiche Anzahl von Gleichungen und Unbekannten beizubehalten. Umso wichtiger ist es, diesen Teil des Codes zu abstrahieren. Es kann jedoch für jeden etwas Grundlegendes gelten: Beispielsweise dreht sich die XPath-Rules-Engine mit einer leichten Bewegung der Hand ... dreht sich ... ... oh, bei XPath Version 1.0 dreht sie sich nicht. Sorry, ein kleines technisches Problem - in ein universelles Tool zum Trimmen von Syntaxbäumen für den winter . Im Allgemeinen ist die Minimierungsstrategie-API recht einfach: Im Großen und Ganzen hat die Funktion eine Sprungfunktion (sie enthält eine Liste der Wurzelknoten der Syntaxbäume), die über die Operationsschnittstelle die Frage stellen kann, ob diese Verzweigungen entfernt werden sollen. Wenn die Invariante verletzt wird, gibt die Funktion die Kontrolle zurück, andernfalls dreht sie den Stapel, indem sie eine spezielle Ausnahme auslöst, und die resultierende Version wird als nächste Annäherung verwendet. Ein Prozess gilt als abgeschlossen, wenn die Schrittfunktion die Steuerung nicht über eine Ausnahme zurückgegeben hat. Sie können sagen, dass dies schrecklich unwirksam ist - vielleicht so, ZATO NÜTZLICH !! 111 , aber worum geht es, wenn der externe Compiler-Prozess regelmäßig hunderte Male in einem Zyklus gestartet werden soll.
Dies wirft die Frage auf: Wie erhält man die Quelle vom verdünnten AST zurück? Natürlich können Sie versuchen, für jede Sprache, die eine Textdatei generiert, einen speziellen Code zu schreiben. Aber wie Sie wissen, sollte ein Programmierer faul sein. Es wird also nicht funktionieren - es ist eindeutig nicht aus der Serie "Bestehende Implementierungen aufgreifen und loslegen". Glücklicherweise gibt es in den Knoten des Baums Informationen über die Anfangs- und Endzeilen und -spalten für diesen Knoten. Das heißt, wenn das Sprachmodul diese Informationen korrekt anzeigt, können Sie den Quelltext entnehmen und sorgfältig Teile daraus ausschneiden (daher nebenbei bemerkt und einige Schwierigkeiten mit der Verschleierung: Es reicht nicht aus, etwas wegzuwerfen, aber Sie müssen es ersetzen (z. B. Bezeichner). Übrigens haben wir in der PMD-Codebasis sogar eine Klasse zum Bearbeiten einer Datei gefunden, bei der sich nicht schneidende Textausschnitte verwendet werden (und zwar auch zum Hinzufügen, was für diese bestimmte Aufgabe jedoch nicht so interessant ist).
Theorie: Zusammenfassung
Im Moment habe ich zwei Strategien umgesetzt. Eine davon ist das XPath-Trimmen, was in gewisser Weise ein entarteter Fall ist, da es das Ergebnis zwangsweise schreibt, auch wenn es keine syntaktisch korrekte Quelle mehr ist. Die zweite ist bereits „ehrlich“ iterativ und interaktiv (in dem Sinne, dass sie wirklich mit dem Compiler interagiert und die Invariante überprüft): Sie versucht nur, Zweige nacheinander in eine Schleife zu werfen. Hier ist ein bisschen mehr dazu:
- Im Prinzip macht die Überprüfung der Invariante für die Quelle, die nicht analysiert wird, für eine "ehrliche" Strategie wenig Sinn: Selbst wenn der Compiler dies überlebt, muss der Minimizer die Quelle neu starten. Daher ist es sinnvoll, die "defekten" Dateien im Voraus zu löschen: Das Parsen in Ihrem Prozess ist schneller als das Ausführen des gesamten Compilers
- im allgemeinen Fall wäre es wahrscheinlich zweckmäßig, hier Coroutinen zu verwenden (naja, oder den Kontrollfluss umzukehren), aber da dies weit von dem rechnerisch schwierigsten Teil der Arbeit entfernt ist, gehe ich bei jedem Schritt in der Schrittfunktion einfach um den Baum herum und zähle die Entfernung Oberteile. Ich erinnere mich nur an die Theke. Also dachte ich zuerst, das Oberteil sei größer, das Oberteil weniger - welchen Unterschied macht es, heuristisch jedenfalls! Es stellte sich heraus, dass der Fehler pro Einheit die Konvergenzrate zeitweise ändern kann. Im Wesentlichen ist dies logisch: Es ist oft eine effektive Strategie, ganze Funktionen aus der Klasse in die richtige Reihenfolge zu bringen. Aber ein bisschen zu überspringen und jedes Mal in die Funktion zu gehen , was in den meisten Fällen nichts mit dem Problem zu tun hat, sieht nach einer so lala Idee aus.
- Übrigens über Coroutinen und die Bereitstellung des Kontrollflusses: Es würde einige Probleme geben, da sich der AST nach dem Neustart des geänderten Textes möglicherweise nicht auf sehr offensichtliche Weise ändert (dh nicht nur die angegebenen Zweige werden zurückgeworfen, sondern die Knoten, die leer werden, verschwinden irgendwo, irgendwo Im Allgemeinen wird das Parsen in die andere Richtung gehen. Ganz zu schweigen davon, dass die Knoten des neuen AST in Bezug auf die alten nicht identisch sein werden, und logische Übereinstimmung durch
equals - sieht ebenfalls nach einer schwierigen Aufgabe aus - Im Prinzip können Sie die Funktionen von PMD in unterschiedlichem Maße nutzen: Sie können berechnete Typen, Abhängigkeiten für die Verwendung von Definitionen usw. verwenden. und etwas sehr Kluges tun (aber Sie müssen eine universelle API in Betracht ziehen). Andererseits ist es für die beschriebene Strategie ausreichend, einen Analysebaum zu erhalten. Und hier könnten Sie sogar Kaitai Struct einbinden und versuchen, afl-tmin zu drücken, um Binärdateien zu minimieren :)
Übe
Erstellen wir zunächst einen Minimierer:
git clone https://github.com/pmd/pmd-scm.git cd pmd-scm ./mvnw clean verify unzip pmd-scm-dist/target/pmd-scm-bin-1.0.0-SNAPSHOT.zip
Jetzt brauchst du eine Quelle. Nehmen wir zum Beispiel GreedyStrategy.java .
Finden Sie mit Rule Designer heraus, wie ein typischer AST für Java aussieht, und führen Sie ihn aus
$ ./bin/run.sh scm --language java \ --input-file ../pmd-scm/src/main/java/net/sourceforge/pmd/scm/strategies/GreedyStrategy.java \ --output-file GreedyStrategy-min.java \ --strategy xpath \ --xpath-expression '//BlockStatement[count(../BlockStatement) > 1]' Original file(s): 6155 bytes, 1099 nodes. After initial white-space cleanup: size 4548 bytes (73%), 1099 nodes (100%) After pass #1: size 1984 bytes (32%), 1099 nodes (100%) After final white-space cleanup: size 1984 bytes (32%), 325 nodes (29%) After blank line clean up: size 1767 bytes (28%), 325 nodes (29%)
package net.sourceforge.pmd.scm.strategies; import java.util.Collections; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; import net.sourceforge.pmd.lang.ast.Node; public class GreedyStrategy extends AbstractMinimizationStrategy { public static class Configuration extends AbstractConfiguration { @Override public MinimizationStrategy createStrategy() { return new GreedyStrategy(this); } } public static final MinimizationStrategyConfigurationFactory FACTORY = new AbstractFactory("greedy") { @Override public MinimizationStrategyConfiguration createConfiguration() { return new Configuration(); } }; private GreedyStrategy(Configuration configuration) { super(configuration); } private final Map<Node, HashSet<Node>> directlyDependingNodes = new HashMap<>(); private final Map<Node, Set<Node>> transitivelyDependingNodes = new HashMap<>(); private void fetchDirectDependentsFromSubtree(Node node) {
Das heißt, wir haben alle Funktionen geleert, die direkt mehr als eine Anweisung enthalten . Löschen von Kommentaren, Leerzeilen usw. Ich habe es nicht spezifiziert - schließlich ist dies (bisher?) In erster Linie ein Tool zum Debuggen von Compilern , anstatt schöne Schnittstellenbeschreibungen zu erstellen.
Schauen wir uns jetzt etwas interessanteres an: Versuchen Sie, zwei Dateien mit dem Feedback des Compilers gleichzeitig zu minimieren:
orig / TestResource.java:
class TestResource { int func() { System.err.println("Hello World!"); return 123; } void unused() {
orig / Main.java:
class Main { public static void main(String[] args) { String str = new TestResource().func(); return 123; } }
Wie Sie sehen können, kompilieren sie nicht:
$ javac orig/TestResource.java orig/Main.java orig/Main.java:3: error: incompatible types: int cannot be converted to String String str = new TestResource().func(); ^ orig/Main.java:5: error: incompatible types: unexpected return value return 123; ^ 2 errors
Stellen wir uns vor, dass mit dem ersten Fehler etwas nicht stimmt, und versuchen Sie, ein minimales Beispiel zu erstellen, das produziert
error: incompatible types: int cannot be converted to String
Führen Sie dazu aus
$ bin/run.sh scm --language java \ --input-file orig/TestResource.java orig/Main.java \ --output-file TestResource.java Main.java \ --invariant message \ --printed-message "error: incompatible types: int cannot be converted to String"\ --command-line "javac TestResource.java Main.java" \ --strategy greedy Original file(s): 290 bytes, 77 nodes. After initial white-space cleanup: size 258 bytes (88%), 77 nodes (100%) After pass #1: size 255 bytes (87%), 64 nodes (83%) After pass #2: size 244 bytes (84%), 57 nodes (74%) After pass #3: size 205 bytes (70%), 51 nodes (66%) After pass #4: size 192 bytes (66%), 46 nodes (59%) After pass #5: size 181 bytes (62%), 39 nodes (50%) After pass #6: size 179 bytes (61%), 39 nodes (50%) After final white-space cleanup: size 149 bytes (51%), 39 nodes (50%) After blank line clean up: size 147 bytes (50%), 39 nodes (50%)
Als Ergebnis bekommen wir
TestResource.java:
class TestResource { int func() { } }
Main.java:
class Main { public static void main() { String str = new TestResource().func(); } }
$ javac TestResource.java Main.java TestResource.java:3: error: missing return statement } ^ Main.java:3: error: incompatible types: int cannot be converted to String String str = new TestResource().func(); ^ 2 errors
Alles wie bestellt!
Zusammenfassung
Bisher befindet sich das Projekt noch in einem relativ frühen Stadium, aber es gibt bereits etwas zu demonstrieren. In Zukunft gibt es Ideen, eine API für sprachunabhängige Indikatoren für Abhängigkeiten zwischen AST-Knoten zu entwickeln, um sprachspezifische Strategien bereitzustellen. Es wäre auch schön, eine universelle Strategie zu entwickeln, die das Groovy / Kotlin / -Skript ausführt - schließlich haben es Menschen, die Java verwenden, vielleicht noch nie gesehen, aber sie kennen sich zum Beispiel mit Modelika und Modelika bestens aus haben ihre fortgeschrittenen Möglichkeiten im Kopf, die Quelle zu quetschen.