Nestes dias maravilhosos de janeiro, todos nós, é claro, estamos preocupados com a questão de minimizar o código-fonte e preservar o invariante. Quero dizer, não liga?!? Em vão ... Aqui o compilador caiu, e o programa é gigantesco - é de alguma forma inconveniente para os desenvolvedores enviarem uma coisa dessas. E então a diversão começa: e se você jogá-la fora? Ah, não cai - ok, vamos embora, mas e se for? - ainda trava, e isso, isso e aquilo ... Ah, eu iniciei o compilador nas fontes antigas.
Ao mesmo tempo, automatizar a pesquisa de bugs é uma questão de vida: git bisect, llvm-bugpoint, creduce, ... Neste artigo, descreverei mais uma maneira de resolver o problema de simplificar o caso de teste, mais ou menos universal em relação à linguagem de programação, e mostrar algumas exemplos de uso.
Universal, digamos ... Talvez, é claro, já tenha sido implementado dez vezes, mas impediria um ciclista experiente. E quando nas mãos de um microscópio, todos os problemas parecem unhas. No papel de um microscópio - PMD .
Em geral, existe uma linguagem para escrever modelos descritos por equações diferenciais - Modelica. É bastante avançado, existe uma implementação aberta muito legal e em geral. Mas há um pequeno problema: às vezes, um erro interno do compilador ocorre no compilador. Em um artigo anterior, eu já mostrei como adicionar suporte ao Modela ao analisador estático PMD (a propósito, alguns dos meus erros surgiram durante o processo de revisão), além dos dez módulos de idioma existentes. Então agora eu decidi - o que é bom desaparecer - e enviei uma ferramenta de prova de conceito Source Code Minimizer, reutilizando os módulos de linguagem existentes PMD. Infelizmente, fui enviado, embora não muito longe, para um repositório vizinho: o mentor disse que ainda não decide dar suporte a isso até o final do século, e ele está perdido na base de código comum, então logo encontrei um convite para colaborador na minha caixa de entrada. é recém-criado pmd / pmd-scm .
Primeiro, qual é a afirmação do problema? É necessário reduzir o tamanho do código fonte, preservando algumas de suas propriedades. Mais especificamente, eu quero
- o código resultante era previsível
- não precisa ser o mínimo possível , a "conclusão de arquivos" é permitida, mas não deve se transformar em tormento
- ofuscação automática não é considerada
- programa minimizado pode ser dividido em vários arquivos com código fonte
- por exemplo, em Java, cada classe
public deve estar em um arquivo separado com o nome correto, etc. - Quero que cada arquivo permaneça visível no final
- no processo de transformações, a invariante indicada deve ser preservada
Dispositivo interno
Nesta seção, descreverei mais ou menos a implementação. Para começar, repito que essa ideia, para dizer o mínimo, não é nova. E se eu citei o git bisect simplesmente como um exemplo do "mecanismo de depuração automática", me deparei com creduce ou algo semelhante por algum tempo (embora eu não o tenha usado). Mas eu tive que usar o llvm-bugpoint - é impressionante: sente-se, depure seu LLVM Pass e ele - tal infecção - trava em alguns sistemas de arquivos. Portanto, você pode compilar esse arquivo no código de bit LLVM, executar opt no arquivo .bc com seu plug-in e verificar se ele trava. E então, grosso modo, acabei de substituir opt por llvm-bugpoint , e em um minuto obtive um "esqueleto" robusto de uma das funções, consistindo em uma nuvem de blocos de base e transições entre elas; tudo, menos galhos, foi jogado fora com sucesso. A propósito, como na minha declaração do problema, depois de uma dúzia de minutos de simplificação manual, tudo se resumiu ao fato de eu ter processado incorretamente um dos tipos de ramificação, e todo o resto era apenas um cenário. Em geral, a ideia não é nova.
E agora para a implementação. Como era para ser uma ferramenta mais ou menos universal, eu queria criar algum tipo de estrutura na qual pudéssemos criar implementações otimizadas para diferentes idiomas. Como resultado, dois conceitos bastante ortogonais se destacaram:
- invariável suportado
- estratégia de minimização
Invariante
Uma das opções para a propriedade que você deseja salvar, eu já descrevi: “o compilador imprimiu uma frase no console” (“Erro interno do compilador”, por exemplo). Além disso, as idéias podem ser recolhidas a partir de uma variedade de difusores: AFL , Killerbeez e outros:
- o processo terminou com algum código de retorno (em particular, "falha no sinal" no Linux)
- o processo levou mais de T milissegundos. Aqui, infelizmente, a instabilidade pode ocorrer devido à carga flutuante do sistema. Para maior precisão, você pode usar o tempo da CPU, embora, idealmente, os contadores de desempenho sejam úteis.
- o compilador pode (não) gerar algum arquivo de saída
- ...
Eu já implementei alguns deles (código de retorno, linha impressa), outros não, alguns podem ser específicos para idiomas individuais. Em geral, essa é uma parte da tarefa bastante autônoma, geralmente completamente independente de um idioma específico.
Estratégia de minimização
À primeira vista, tudo aqui é puramente dependente da linguagem. Em algum lugar, você precisa descartar variáveis junto com casos de uso, em algum lugar - para manter o mesmo número de equações e incógnitas. O mais importante é abstrair esta parte do código. Mas algo básico pode ser comum a todos: por exemplo, com um movimento do pulso, o mecanismo de regras do XPath gira ... gira ... ... oh, para o XPath versão 1.0, isso não acontece. Desculpe, um pequeno problema técnico - em uma ferramenta universal para aparar árvores de sintaxe para o inverno . Em geral, a API da estratégia de minimização é bastante simples: em geral, a função possui uma função step (é fornecida uma lista dos nós raiz das árvores de sintaxe), que pode perguntar "mas tente eliminar esses desvios" por meio da interface de operação. Se a invariante for violada, a função retornará o controle; caso contrário, ela girará a pilha lançando uma exceção especial e a versão resultante será tomada como a próxima aproximação. Um processo é considerado completo se a função de etapa retornou o controle não por meio de uma exceção. Você pode dizer que isso é terrivelmente ineficaz - talvez sim, ZATO CONVENIENT !! 111 , mas sobre o que se trata, se é suposto iniciar regularmente o processo do compilador externo centenas de vezes em um ciclo.
Isso levanta a questão: como recuperar a fonte do AST reduzido? Obviamente, você pode tentar escrever um código especial para cada idioma que gera um arquivo de texto. Mas, como você sabe, um programador deve ser preguiçoso. Portanto, não vai funcionar - já não é claramente da série "pegou as implementações existentes e foi embora". Felizmente, nos nós da árvore, há informações sobre as linhas e colunas inicial e final desse nó - ou seja, se o módulo de idioma indicar corretamente essas informações, você pode pegar o texto de origem e cortar cuidadosamente partes dele (daí, a propósito, e alguma dificuldade com a ofuscação: não basta jogar algo fora, mas você precisa substituí-lo: identificadores, por exemplo). A propósito, na base de código do PMD, encontramos até uma classe para editar um arquivo usando operações de corte de texto sem interseção (além de adicionar, mas isso não é tão interessante para esta tarefa em particular).
Teoria: Resumo
No momento, eu implementei duas estratégias. Um deles é o corte XPath, que é, de certo modo, um caso degenerado, porque grava o resultado à força, mesmo que não seja mais uma fonte sintaticamente correta. O segundo já é iterativo e interativo "honesto" (no sentido de que realmente interage com o compilador e verifica o invariante): ele apenas tenta lançar ramificações uma a uma em um loop. Aqui está um pouco mais sobre isso:
- em princípio, verificar o invariante para a fonte, que não é analisado, faz pouco sentido para uma estratégia "honesta": mesmo que o compilador sobreviva a isso, o minimizador terá que reiniciar a fonte. Portanto, faz sentido jogar fora os arquivos “quebrados” com antecedência: a análise do seu processo é mais rápida do que executar o compilador inteiro
- no caso geral, provavelmente seria conveniente usar corotinas aqui (bem, ou inverter o fluxo de controle), mas como essa é a parte mais difícil do trabalho computacionalmente, em cada etapa da função etapa, apenas ando pela árvore, contando a distância tops. Só me lembro do balcão. Então, no começo eu pensei que o topo é maior, o topo é menor - que diferença faz, heurística de qualquer maneira! Descobriu-se que o erro por unidade pode alterar a taxa de "convergência" às vezes. Em essência, isso é lógico: jogar funções inteiras da classe em ordem geralmente será uma estratégia eficaz. Mas, para pular um pouco, e cada vez que entrar na função, na maioria dos casos, não tem nada a ver com o problema, parece uma idéia.
- a propósito das corotinas e da implantação do fluxo de controle: haveria alguns problemas com isso, pois após a reinicialização do texto alterado, o AST pode não ser alterado de maneira muito óbvia (ou seja, não apenas os ramos indicados serão retrocedidos, mas os nós que ficarem vazios desaparecerão em algum lugar, em algum lugar geralmente a análise irá para o outro lado). Sem mencionar que os nós do novo AST não serão idênticos por referência aos antigos e a correspondência lógica por
equals - também parece uma tarefa difícil - em princípio, você pode usar os recursos do PMD em vários graus: você pode usar tipos calculados, dependências de uso de definições etc. e faça algo muito inteligente (mas você precisa considerar uma API universal). Por outro lado, para a estratégia descrita, é suficiente obter uma árvore de análise. E aqui você pode até conectar um pouco do Kaitai Struct e tentar pressionar o afl-tmin para minimizar os arquivos binários :)
Prática
Para começar, vamos criar um 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
Agora você precisa de alguma fonte. Vamos considerar o GreedyStrategy.java, por exemplo.
Usando o Rule Designer, descubra como é um AST típico para Java e execute
$ ./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) {
Ou seja, esvaziamos todas as funções que contêm diretamente mais de uma instrução . No entanto, excluir comentários, linhas em branco etc. Eu não o especifiquei - afinal, isso (até agora?) É principalmente uma ferramenta para depurar compiladores , em vez de criar belas descrições de interface.
Vejamos algo mais interessante agora: tente minimizar dois arquivos com feedback do compilador ao mesmo tempo:
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 você pode ver, eles não compilam:
$ 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
Vamos imaginar que algo está errado com o primeiro erro e tentar fazer um exemplo mínimo que produza
error: incompatible types: int cannot be converted to String
Para fazer isso, execute
$ 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, obtemos
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
Tudo como ordenado!
Sumário
Até agora, o projeto está em um estágio bastante inicial, mas já há algo a demonstrar. No futuro, existem idéias para tornar uma API independente de idioma, indicando dependências entre nós AST, para possibilitar o fornecimento de estratégias específicas de idioma. Também seria bom criar uma estratégia universal que execute o script Groovy / Kotlin / de outra maneira - afinal, as pessoas que usam Java podem nunca ter visto, mas sabem perfeitamente bem, por exemplo, Modelika e têm em mente suas maneiras avançadas de espremer a fonte.