Uma série de artigos é dedicada à descrição da abordagem ideal para a implementação de ferramentas de análise de código estático, projetadas para especialistas. O objetivo do trabalho são abordagens, modelos e técnicas para obter o máximo desempenho da ferramenta, minimizando a complexidade do desenvolvimento e suporte / alteração da ferramenta. Este artigo descreve uma maneira de acelerar o analisador e reduzir o consumo de memória. O artigo está estruturado para que o leitor leia o manual escrito por Terrence Parr.Usando o ANTLR ao máximo
O ANTLR funciona melhor entre cerca de 1 kb e 10 kb; arquivos maiores não serão analisados por esta biblioteca com velocidade máxima. Também o trabalho de depuração em arquivos grandes se torna quase impossível. A principal razão pela qual você precisa manter os dados de entrada do analisador dentro dos limites especificados é que os algoritmos de previsão de ramificação do ANTLR usam ativamente a pilha; portanto, por qualquer meio, você precisa se livrar de loops na gramática quando uma regra se chama através de muitas outras regras, incluindo certas condições de ativação para essa conexão, considere um exemplo:var f = fun a(b) { b = 10; return b; }
Este código pode ser descrito com a seguinte gramática:start: stmt* EOF;
stmt: varDecl | funDecl | expr ';' | 'return' expr ';';
varDecl: 'var' id '=' expr;
expr: id ('=' expr)? | number;
funDecl: 'fun' id '(' id* ')' '{' stmt* '}'
É fácil ver que stmt é chamado dentro da regra funDecl, que forma um loop que em aplicativos reais pode fazer com que um arquivo de 100 kb exija 4 GB de heap de RAM para obter o desempenho máximo ou até a capacidade de trabalhar, que é uma situação absolutamente inaceitável .Uma maneira de superar essa desvantagem é adicionar modificações especiais no processo de criação de tokens, ou seja, convolução de {} blocos em um token, com o processamento desses tokens posteriormente em um novo analisador, para a entrada da qual os tokens recolhidos serão transmitidos.Para fazer isso, no ANTLR, você pode substituir o método org.antlr.v4.runtime.Lexer # nextToken do lexer, onde é possível implementar a funcionalidade de convolução: override def nextToken(): Token = super.nextToken() match {
case x: RScanToken if x.getType == foldOpen => buildFoldToken(x)
case x: Token => x
}
def buildFoldToken(start: RScanToken): RScanToken = {
val (token, list) = createFoldBlockBody(
mutable.MutableList[RScanToken]()
++ List(start.asInstanceOf[RScanToken])
)
val result = new RScanToken(path, _tokenFactorySourcePair, foldBlock, Lexer.DEFAULT_TOKEN_CHANNEL, start.getStartIndex, token.getStopIndex)
result.setLine(start.getLine)
result.setCharPositionInLine(start.getCharPositionInLine)
result.setFoldedTokens(list)
result
}
private def createFoldBlockBody(list: mutable.MutableList[RScanToken]): (RScanToken, mutable.MutableList[RScanToken]) = {
var current: RScanToken = null
while (current == null || current.getType != Token.EOF && current.getType != foldClose) {
current = nextToken().asInstanceOf[RScanToken]
list += current
}
if (current.getType == Token.EOF)
throw new IllegalStateException()
(current, list)
}
A gramática deve ser complementada por:startJavaScript
: HashBangLine? jsFileBody? EOF
;
startFoldBlock
: block EOF
;
block
: LBRACE stmtList? RBRACE
| FoldBlock
// ,
// startFoldBlock
;
Com essa abordagem, o conteúdo da convolução não será processado mais uma vez, pois o algoritmo recursivo absorverá os tokens e os salvará.A velocidade de processamento cresce de 2 a 10 vezes, a diferença se torna especialmente visível nos arquivos js minificados.O impacto na operação ANTLR da otimização proposta usando vários arquivos javascript como exemplo:Sem otimização, o trabalho é realizado em um encadeamento, com otimização, se possível, o processamento é paralelo.O lançamento foi realizado em uma máquina com 64 GB de RAM, CPU Intel® Core (i) i7-9700K a 3.60GHz, OpenJDK Runtime Environment AdoptOpenJDK (build 11.0.4 + 11).Chaves de inicialização da JVM: -Xmx4G -XX: + UseG1GC -XX: MaxHeapFreeRatio = 30 -XX: MinHeapFreeRatio = 10Para o arquivo tsserver.js, a chave é -Xmx32G, enquanto o consumo de memória atingiu 22 GB! Enquanto arquivos minificados de até 200 kb com otimização são analisados com um limite de heap de 128 mb no modo paralelo, sem a necessidade de o coletor de lixo colocar uma carga no processador, no máximo 2%!Criação de perfil
O ANTLR suporta a criação de perfil do analisador / lexer em tempo de execução.Para habilitá-lo, é necessário chamar o método: org.antlr.v4.runtime.Parser # setProfile antes de executar qualquer regra. Então você pode obter todas as informações, por exemplo, desta maneira: private def printProfileInfo(parser: AbstractRScanParser, tokenStream: TokenStream): Unit = {
val parseInfo = parser.getParseInfo
val atn = parser.getATN
for (di <- parseInfo.getDecisionInfo if di.ambiguities.size() > 0) {
val ds = atn.decisionToState.get(di.decision)
val ruleName = parser.ruleName(ds.ruleIndex)
log.debug("Ambiguity in rule '" + ruleName + "' -> {}", di)
log.debug("=========================")
log.debug(tokenStream.getText)
log.debug("=========================")
}
}
Uma vantagem óbvia com esse método é a redução na quantidade de dados que você precisa analisar, pois as convoluções podem ser substituídas por {} e sempre funcionam em convolução local, o que acelera bastante o processo de otimização da gramática.Conclusão
Este artigo propõe um método para otimizar o trabalho de gramáticas formais implementadas usando a biblioteca ANTLR, embora a própria abordagem possa ser aplicada a outras bibliotecas. Um recurso de otimização é a redução no número de transições a serem encaminhadas para validar o fluxo do token de entrada. Também permite analisar arquivos grandes (mais de 1 mb) com um custo de memória de 512 mb para processamento de thread único, enquanto a falta de otimização exigirá 50 vezes mais memória para um trabalho rápido usando a mesma gramática.Código fonte disponível no github. Este projeto é feito para demonstrar o trabalho de otimização. O projeto é simplificado o máximo possível, é recomendável iniciar o estudo na classe GrammarTester, uma configuração de inicialização foi feita para ele, você só precisa registrar o caminho para a pasta com os dados de entrada. Preste atenção à chave rscan.tester.cache.dir, os arquivos temporários serão gravados nesta pasta, a análise de arquivo bem-sucedida é corrigida nessa pasta e não permitirá que o analisador analise-a uma segunda vez - conveniente para corrigir erros. No momento, a gramática foi testada em 17 mil arquivos de node_modules criados para o aplicativo principal de reação. Somente node_modules aninhados foram ignorados.No próximo artigo, consideraremos as opções para organizar os dados e o modelo R (Reflexão) para a representação ideal dos dados de origem como objetos de análise com consumo mínimo de memória, a capacidade de implementar algoritmos de pesquisa para elementos com complexidade O (1) e poder salvar em disco no formato serializado todos os objetos, bem como peças de teste de unidade da ferramenta.