En estos maravillosos días de enero, a todos nosotros, por supuesto, nos preocupa la cuestión de minimizar el código fuente y preservar el invariante. Quiero decir, ¿no te importa? En vano ... Aquí el compilador cayó, y el programa es gigantesco, de alguna manera es un inconveniente para los desarrolladores enviar tal cosa. Y luego comienza la diversión: ¿qué pasa si la tiras? Oh, no se cae, está bien, nos vamos, pero ¿y si es así? - Todavía se bloquea, y esto, y esto, y eso ... Oh, comencé el compilador en las fuentes antiguas.
Al mismo tiempo, automatizar la búsqueda de errores es una cuestión de vida: git bisect, llvm-bugpoint, creduce, ... En este artículo describiré otra forma de resolver el problema de simplificar el caso de prueba, más o menos universal con respecto al lenguaje de programación, y mostrar algunos ejemplos de uso
Universal, digamos ... Tal vez, por supuesto, ya se ha implementado diez veces, pero esto detendría a un ciclista experimentado. Y cuando está en manos de un microscopio, todos los problemas parecen ser las uñas. En el papel de un microscopio - PMD .
En general, existe un lenguaje para escribir modelos descritos por ecuaciones diferenciales: Modelica. Está bastante avanzado, hay una implementación abierta muy buena y en general. Pero hay un pequeño problema: a veces se produce un error interno del compilador en el compilador. En un artículo anterior, ya mostré cómo agregar soporte de Modela al analizador estático PMD (por cierto, algunos de mis errores surgieron durante el proceso de revisión) además de los diez módulos de idioma existentes. Así que ahora decidí, de qué sirve desaparecer, y envié una herramienta de prueba de concepto Source Code Minimizer, reutilizando los módulos de lenguaje existentes PMD. Desafortunadamente, me enviaron, aunque no muy lejos, a un repositorio vecino: el medidor dijo que todavía no decide apoyar esto hasta el final del siglo, y se pierde en la base de código común, por lo que pronto encontré una invitación para colaborar en mi bandeja de entrada Recién creado pmd / pmd-scm .
Primero, ¿cuál es la declaración del problema? Se requiere reducir el tamaño del código fuente, preservando parte de su propiedad. Más específicamente, quiero
- el código resultante era previsible
- no tiene que ser lo más mínimo posible , la "finalización del archivo" está permitida, pero no debe convertirse en tormento
- la ofuscación automática no se considera
- programa minimizado se puede dividir en varios archivos con código fuente
- por ejemplo, en Java, cada clase
public debe estar en un archivo separado con el nombre correcto, etc. - Quiero que cada archivo permanezca visible al final
- en el proceso de transformaciones, la invariante indicada debe ser preservada
Dispositivo interno
En esta sección, describiré aproximadamente la implementación. Para empezar, observo nuevamente que esta idea, por decirlo suavemente, no es nueva. Y si cité git bisect simplemente como un ejemplo del "mecanismo de depuración automática", me encontré con un producto o algo similar durante bastante tiempo (aunque no lo usé ). Pero tuve que usar llvm-bugpoint , es impresionante: te sientas, depuras tu LLVM Pass y, como una infección, se bloquea en algunos sistemas de archivos. Por lo tanto, puede compilar este archivo en código de bits LLVM, ejecutar opt en el archivo .bc con su complemento y asegurarse de que se bloquea. Y luego, más o menos, simplemente reemplacé opt con llvm-bugpoint , y en un minuto obtuve un fuerte "esqueleto" de una de las funciones, que consiste en una nube de bloques de base y transiciones entre ellas; todo menos las ramas fue descartado con éxito. Por cierto, como en mi declaración del problema, después de una docena de minutos de simplificación manual, todo se redujo al hecho de que procesé incorrectamente uno de los tipos de rama, y todo lo demás era solo un escenario. En general, la idea no es nueva.
Y ahora para la implementación. Como se suponía que era una herramienta más o menos universal, quería crear algún tipo de marco en el que pudiéramos incluir implementaciones optimizadas para diferentes idiomas. Como resultado, se destacaron dos conceptos bastante ortogonales:
- invariante apoyado
- estrategia de minimización
Invariante
Ya he descrito una de las opciones para la propiedad que quizás desee guardar: "el compilador imprimió una frase en la consola" ("Error interno del compilador", por ejemplo). Además, las ideas se pueden obtener de una variedad de fuzzers: AFL , Killerbeez y otros:
- el proceso finalizó con algún código de retorno (en particular, "bloqueo de señal" en Linux)
- El proceso tomó más de T milisegundos. Aquí, por desgracia, la inestabilidad puede ocurrir debido a la carga flotante del sistema. Para mayor precisión, puede usar el tiempo de CPU, aunque, idealmente, los contadores de rendimiento son útiles
- el compilador puede (no) generar algún archivo de salida
- ...
Ya he implementado algunos de ellos (código de retorno, línea impresa), algunos no, algunos pueden ser específicos de idiomas individuales. En general, esta es una parte bastante autónoma de la tarea, a menudo completamente independiente de un lenguaje específico.
Estrategia de minimización
A primera vista, todo aquí depende únicamente del idioma. En algún lugar necesita tirar variables junto con casos de uso, en algún lugar, para mantener el mismo número de ecuaciones e incógnitas. Lo más importante es abstraer esta parte del código. Pero algo básico puede hacerse común para todos: por ejemplo, con un ligero movimiento de la mano, el motor de las reglas XPath gira ... gira ... ... oh, para XPath versión 1.0 no gira. Lo sentimos, un pequeño problema técnico: una herramienta universal para cortar árboles de sintaxis para el invierno . En general, la API de estrategia de minimización es bastante simple: en general, la función tiene una función de paso (se le da una lista de los nodos raíz de los árboles de sintaxis), que puede preguntar "pero intente eliminar estas ramas" a través de la interfaz de operación. Si se viola el invariante, la función devuelve el control; de lo contrario, hace girar la pila lanzando una excepción especial, y la versión resultante se toma como la próxima aproximación. Un proceso se considera completo si la función de paso devolvió el control no a través de una excepción. Puedes decir que esto es terriblemente ineficaz, tal vez así, ¡CONVENIENTE DE ZATO! 111 , pero de qué se trata, si se supone que debe iniciar regularmente el proceso del compilador externo cientos de veces en un ciclo.
Esto plantea la pregunta: ¿cómo recuperar la fuente del AST reducido? Por supuesto, puede intentar escribir un código especial para cada idioma que genere un archivo de texto. Pero, como sabes, un programador debería ser flojo. Por lo tanto, no funcionará, ya que claramente no es de la serie "recogió implementaciones existentes y listo". Afortunadamente, en los nodos del árbol hay información sobre las filas y columnas iniciales y finales de este nodo; eso significa que, si el módulo de idioma indica esta información correctamente, puede tomar el texto fuente y cortarlo cuidadosamente (por lo tanto, por cierto, y algunas dificultades con la ofuscación: no es suficiente tirar algo, pero debes reemplazarlo: identificadores, por ejemplo). Por cierto, en la base de código PMD, incluso encontramos una clase para editar un archivo usando operaciones de corte de texto que no se cruzan (además de agregar, pero esto no es tan interesante para esta tarea en particular).
Teoría: resumen
Por el momento he implementado dos estrategias. Uno de ellos es el recorte XPath, que es, en cierto sentido, un caso degenerado, porque escribe el resultado por la fuerza, incluso si ya no es una fuente sintácticamente correcta. El segundo ya es iterativo e interactivo "honesto" (en el sentido de que realmente interactúa con el compilador y comprueba el invariante): solo intenta lanzar ramas una por una en un bucle. Aquí hay un poco más al respecto:
- en principio, verificar la fuente invariante, que no se analiza, tiene poco sentido para una estrategia "honesta": incluso si el compilador sobrevive a esto, el minimizador tendrá que reiniciar la fuente. Por lo tanto, tiene sentido desechar los archivos "rotos" de antemano: analizar el proceso es mucho más rápido que ejecutar todo el compilador
- en el caso general, probablemente sería conveniente usar corutinas aquí (bueno, o girar el flujo de control al revés), pero como esto está lejos de ser la parte más difícil del trabajo para la computación, en cada paso de la función de paso simplemente doy la vuelta al árbol, contando la distancia tops. Solo recuerdo el mostrador. Entonces, al principio pensé que la parte superior es más grande, la parte superior es menor: ¡qué diferencia hay, heurística de todos modos! Resultó que el error por unidad puede cambiar la tasa de "convergencia" a veces. En esencia, esto es lógico: lanzar funciones completas de la clase en orden a menudo será una estrategia efectiva. Pero para saltear un poco, y cada vez que ingrese a la función, en la mayoría de los casos sin tener nada que ver con el problema, parece una idea regular.
- por cierto, sobre las corutinas y el despliegue del flujo de control: habría algunos problemas con esto, ya que después de reiniciar el texto modificado, el AST puede no cambiar de una manera muy obvia (es decir, no solo estas ramas se devolverán, sino que en algún lugar los nodos vacíos desaparecerán, en algún lugar el análisis general irá en la otra dirección). Sin mencionar que los nodos del nuevo AST no serán idénticos en referencia a los antiguos, y la coincidencia lógica por
equals también parece una tarea difícil. - en principio, puede usar las capacidades de PMD en diversos grados: puede usar tipos calculados, dependencias de uso de definición, etc. y hacer algo muy inteligente (pero debes considerar una API universal). Por otro lado, para la estrategia descrita, es suficiente obtener un árbol de análisis. Y aquí incluso podría conectar algo de Kaitai Struct e intentar presionar afl-tmin para minimizar los archivos binarios :)
Practica
Para comenzar, construyamos un minimizador:
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
Ahora necesitas alguna fuente. Tomemos GreedyStrategy.java por ejemplo.
Con Rule Designer, descubra cómo es un AST típico para Java y ejecute
$ ./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) {
Es decir, vaciamos todas las funciones que contienen directamente más de una declaración . Sin embargo, eliminar comentarios, líneas en blanco, etc. No lo he especificado. Después de todo, ¿es esta (¿hasta ahora?) Principalmente una herramienta para depurar compiladores , en lugar de crear hermosas descripciones de interfaz.
Veamos algo más interesante ahora: intente minimizar dos archivos con comentarios del compilador al mismo tiempo:
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; } }
Como puede ver, no compilan:
$ 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
Imaginemos que algo está mal con el primer error, e intentemos hacer un ejemplo mínimo que produzca
error: incompatible types: int cannot be converted to String
Para hacer esto, ejecuta
$ 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%)
Como resultado, obtenemos
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
Todo según lo ordenado!
Resumen
Hasta ahora, el proyecto se encuentra en una etapa bastante temprana, pero ya hay algo que demostrar. En el futuro, hay ideas para hacer una API para dependencias de lenguaje agnóstico que indiquen dependencias entre los nodos AST, para que sea posible proporcionar estrategias específicas del idioma. También sería bueno hacer una estrategia universal que ejecute el script Groovy / Kotlin / script algo más: después de todo, las personas que usan Java pueden nunca haberlo visto, pero saben perfectamente, por ejemplo, Modelika, y tienen en su cabeza sus formas avanzadas de exprimir la fuente.