En ces merveilleux jours de janvier, nous sommes tous, bien sûr, préoccupés par la question de minimiser le code source tout en préservant l'invariant. Je veux dire, je m'en fous?!? En vain ... Ici le compilateur est tombé, et le programme est gigantesque - il est en quelque sorte gênant pour les développeurs d'envoyer une telle chose. Et puis le plaisir commence: que faire si vous le jetez? Oh, ça ne tombe pas - d'accord, on le laisse, mais si c'est le cas? - plante toujours, et ceci, et ceci, et cela ... Oh, j'ai démarré le compilateur sur les anciennes sources.
Dans le même temps, l'automatisation de la recherche de bugs est une question de vie: git bisect, llvm-bugpoint, creduce, ... Dans cet article je décrirai encore une autre façon de résoudre le problème de la simplification du cas de test, plus ou moins universel par rapport au langage de programmation, et en montrerai quelques uns exemples d'utilisation.
Universel, disons ... Peut-être, bien sûr, il a déjà été mis en œuvre dix fois, mais cela arrêterait-il un cycliste aguerri. Et quand entre les mains d'un microscope, tous les problèmes semblent être des clous. Dans le rôle d'un microscope - PMD .
En général, il existe un tel langage pour écrire des modèles décrits par des équations différentielles - Modelica. Il est assez avancé, il y a une implémentation ouverte très cool et en général. Mais il y a un petit problème: parfois une erreur de compilation interne se produit dans le compilateur. Dans un article précédent, j'ai déjà montré comment ajouter la prise en charge de Modela à l'analyseur statique PMD (en passant, certaines de mes erreurs sont apparues lors du processus de révision) en plus des dix modules de langage existants. Alors maintenant, j'ai décidé - à quoi bon disparaître - et j'ai envoyé un outil de preuve de concept Source Code Minimizer, réutilisant les modules de langage PMD existants. Malheureusement, j'ai été envoyé, mais pas très loin, dans un référentiel voisin: le mentor a déclaré qu'il ne décidait toujours pas de prendre en charge cela jusqu'à la fin du siècle, et qu'il est perdu dans la base de code commune, j'ai donc rapidement trouvé une invitation à collaborer dans ma boîte de réception est fraîchement créé pmd / pmd-scm .
D'abord, quelle est l'énoncé du problème? Il est nécessaire de réduire la taille du code source, en préservant une partie de ses propriétés. Plus précisément, je veux
- le code résultant était prévisible
- il ne doit pas être aussi minimal que possible , la «fin de fichier» est autorisée, mais elle ne devrait pas se transformer en tourment
- l'obfuscation automatique n'est pas envisagée
- le programme minimisé peut être divisé en plusieurs fichiers avec le code source
- par exemple, en Java, chaque classe
public doit être dans un fichier séparé avec le nom correct, etc. - Je veux que chaque fichier reste visible à la fin
- dans le processus de transformations, l'invariant indiqué doit être conservé
Dispositif interne
Dans cette section, je vais décrire grossièrement l'implémentation. Pour commencer, je constate à nouveau que cette idée, pour le dire en douceur, n'est pas nouvelle. Et si j'ai cité git bisect simplement comme exemple du «mécanisme de débogage automatique», je suis tombé sur creduce ou quelque chose de similaire pendant un certain temps (bien que je ne l'ait pas utilisé). Mais j'ai dû utiliser llvm-bugpoint - c'est impressionnant: vous vous asseyez, déboguez votre LLVM Pass, et il - une telle infection - se bloque sur certains systèmes de fichiers. Donc, vous pouvez compiler ce fichier en code bit LLVM, exécuter opt sur le fichier .bc avec votre plugin et vous assurer qu'il se bloque. Et puis, grosso modo, je viens de remplacer opt par llvm-bugpoint , et après une minute, j'ai eu un «squelette» lourd d'une des fonctions, consistant en un nuage de blocs de base et de transitions entre eux; tout sauf les branches a été jeté avec succès. Soit dit en passant, comme dans mon énoncé du problème, après une douzaine de minutes de simplification manuelle, tout se résume au fait que j'ai mal traité l'un des types de branche, et tout le reste n'était que décor. En général, l'idée n'est pas nouvelle.
Et maintenant pour la mise en œuvre. Puisqu'il était censé être un outil plus ou moins universel, je voulais créer une sorte de framework dans lequel nous pourrions entasser des implémentations optimisées pour différents langages. En conséquence, deux concepts plutôt orthogonaux se sont démarqués:
- pris en charge invariant
- stratégie de minimisation
Invariant
J'ai déjà décrit l'une des options de la propriété que vous souhaitiez enregistrer: «le compilateur a imprimé une phrase sur la console» («Erreur interne du compilateur», par exemple). En outre, les idées peuvent être glanées à partir d'une variété de fuzzers: AFL , Killerbeez et autres:
- le processus s'est terminé avec du code retour (en particulier, «crash on signal» sous Linux)
- le processus a pris plus de T millisecondes. Ici, hélas, une instabilité peut se produire en raison de la charge flottante du système. Pour une plus grande précision, vous pouvez utiliser le temps CPU, bien que, idéalement, les compteurs de performances soient utiles.
- le compilateur peut (pas) générer un fichier de sortie
- ...
J'ai déjà implémenté certains d'entre eux (code retour, ligne imprimée), d'autres non, certains peuvent être spécifiques à des langues individuelles. En général, il s'agit d'une partie de la tâche assez autonome, souvent complètement indépendante d'une langue spécifique.
Stratégie de minimisation
À première vue, tout ici est purement dépendant de la langue. Quelque part, vous devez jeter les variables avec les cas d'utilisation, quelque part - pour conserver le même nombre d'équations et d'inconnues. Il est d'autant plus important d'abstraire cette partie du code. Mais quelque chose de basique peut être rendu commun pour tout le monde: par exemple, d'un simple mouvement du poignet, le moteur de règles XPath tourne ... tourne ... ... oh, pour XPath version 1.0, ce n'est pas le cas. Désolé, un petit problème technique - dans un outil universel pour couper les arbres de syntaxe pour l'hiver . En général, l'API de stratégie de minimisation est assez simple: en gros, la fonction a une fonction d'étape (on lui donne une liste des nœuds racine des arbres de syntaxe), qui peut demander "mais essayez de jeter ces branches" via l'interface d'opération. Si l'invariant est violé, la fonction retourne le contrôle; sinon, elle fait tourner la pile en lançant une exception spéciale, et la version résultante est considérée comme la prochaine approximation. Un processus est considéré comme terminé si la fonction d'étape a renvoyé le contrôle sans passer par une exception. Vous pouvez dire que cela est terriblement inefficace - peut-être que oui, ZATO CONVENIENT !! 111 , mais de quoi s'agit-il, s'il est censé démarrer régulièrement le processus de compilation externe des centaines de fois dans un cycle.
Cela soulève la question: comment récupérer la source de l'AST aminci? Bien sûr, vous pouvez essayer d'écrire un code spécial pour chaque langue qui génère un fichier texte. Mais, comme vous le savez, un programmeur doit être paresseux. Donc ça ne marchera pas - ce n'est déjà clairement pas de la série "ramassé les implémentations existantes et c'est parti." Heureusement, dans les nœuds de l'arborescence, il y a des informations sur les lignes et colonnes de début et de fin pour ce nœud - cela signifie que si le module de langue indique correctement ces informations, vous pouvez prendre le texte source et en découper soigneusement des morceaux (d'où, d'ailleurs, et quelques difficultés d'obscurcissement: il ne suffit pas de jeter quelque chose, mais vous devez le remplacer: des identifiants, par exemple). Soit dit en passant, dans la base de code PMD, nous avons même trouvé une classe pour éditer un fichier en utilisant des opérations de coupe de texte sans intersection (ainsi que l'ajout, mais ce n'est pas si intéressant pour cette tâche particulière).
Théorie: Résumé
Pour le moment, j'ai mis en œuvre deux stratégies. L'un d'eux est le découpage XPath, qui est, dans un sens, un cas dégénéré, car il écrit de force le résultat, même s'il ne s'agit plus d'une source syntaxiquement correcte. Le second est déjà «honnête» itératif et interactif (dans le sens où il interagit vraiment avec le compilateur et vérifie l'invariant): il essaie juste de lancer les branches une par une en boucle. En voici un peu plus:
- en principe, la vérification de l'invariant pour la source, qui n'est pas analysée, n'a guère de sens pour une stratégie "honnête": même si le compilateur survit à cela, le minimiseur devra redémarrer la source. Par conséquent, il est logique de jeter les fichiers «cassés» à l'avance: l'analyse dans votre processus est plus rapide que l'exécution de tout le compilateur
- dans le cas général, il serait probablement pratique d'utiliser des coroutines ici (enfin, ou de retourner le flux de contrôle à l'envers), mais comme c'est loin d'être la partie la plus difficile du calcul, à chaque étape de la fonction d'étape, je me contente de marcher autour de l'arbre, en comptant la distance hauts. Je me souviens seulement du comptoir. Donc, au début, je pensais que le sommet est plus grand, le sommet est moins - quelle différence cela fait-il, heuristique quand même! Il s'est avéré que l'erreur par unité peut parfois modifier le taux de «convergence». En substance, c'est logique: jeter des fonctions entières de la classe dans l'ordre sera souvent une stratégie efficace. Mais pour sauter un peu, et chaque fois pour aller à l'intérieur de la fonction, dans la plupart des cas n'ayant rien à voir avec le problème, cela ressemble à une idée comme ça.
- par ailleurs sur les coroutines et le déploiement du flux de contrôle: il y aurait des problèmes avec cela, car après le redémarrage du texte modifié, l'AST peut ne pas changer de manière très évidente (c'est-à-dire non seulement ces branches seront rejetées, mais quelque part les nœuds vides disparaîtront, quelque part généralement l'analyse va dans l'autre sens). Sans oublier que les nœuds de la nouvelle AST ne seront pas identiques par référence aux anciens, et la correspondance logique par
equals - ressemble également à une tâche difficile - en principe, vous pouvez utiliser les capacités de PMD à des degrés divers: vous pouvez utiliser des types calculés, des dépendances de définition-utilisation, etc. et faites quelque chose de très intelligent (mais vous devez envisager une API universelle). En revanche, pour la stratégie décrite, il suffit d'obtenir un arbre d'analyse. Et ici, vous pouvez même accrocher du Kaitai Struct et essayer de pousser afl-tmin pour minimiser les fichiers binaires :)
Pratique
Pour commencer, construisons un minimiseur:
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
Maintenant, vous avez besoin d'une source. Prenons GreedyStrategy.java par exemple.
À l'aide de Rule Designer, découvrez à quoi ressemble un AST typique pour Java et exécutez
$ ./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) {
Autrement dit, nous avons vidé toutes les fonctions contenant directement plus d'une instruction . Cependant, la suppression des commentaires, des lignes vides, etc. Je ne l'ai pas précisé - après tout, est-ce (jusqu'à présent?) Principalement un outil de débogage des compilateurs , plutôt que de créer de belles descriptions d'interface.
Regardons quelque chose de plus intéressant maintenant: essayez de minimiser deux fichiers avec les commentaires du compilateur en même temps:
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; } }
Comme vous pouvez le voir, ils ne compilent pas:
$ 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
Imaginons que quelque chose ne va pas avec la première erreur, et essayons de faire un exemple minimal qui produit
error: incompatible types: int cannot be converted to String
Pour ce faire, exécutez
$ 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%)
En conséquence, nous obtenons
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
Tout comme commandé!
Résumé
Jusqu'à présent, le projet est à un stade assez précoce, mais il y a déjà quelque chose à démontrer. À l'avenir, il y a des idées pour créer une API pour les dépendances d'indication de langue entre les nœuds AST, afin de permettre de fournir des stratégies spécifiques au langage. Il serait également intéressant de créer une stratégie universelle qui exécute le script Groovy / Kotlin / autre chose - après tout, les gens qui utilisent Java ne l'ont peut-être jamais vu, mais ils connaissent parfaitement bien, par exemple, Modelika, et ont dans leur tête leurs moyens avancés pour presser la source.