TECHNOLOGY MATTERS
pensamentos desordenados sobre tecnologia, software, etc.

☰
ler esse site em: |

Analisando código com Sprache - Parte 1

😎 Este é o primeiro artigo de uma série de múltiplas partes sobre como analisar código com Sprache. Você pode ler a segunda parte aqui.

Você provavelmente sabe que às vezes (muitas vezes), o trabalho de um desenvolvedor é muito mais pesquisa ou análise do que programação! No passado, houve muitos casos em que eu estava em um projeto em que meu objetivo era migrar ou reescrever software antigo e, durante esses compromissos, acabei criando ferramentas para me ajudar. Muitas dessas ferramentas eram analisadores de código especializados que realizavam automaticamente a análise que eu exigia ou até mesmo geravam códigos mais novos que eu poderia utilizar.

Em todos esses casos, precisei analisar algum código estruturado e há uma maneira simples de fazer isso: usando Sprache, um framework de parsing para dotnet. Neste artigo, vamos ver como fazer isso.

Analisando código Java

Você pode escrever todos os tipos de analisadores com Sprache. Contanto que a linguagem seja formal, é fácil construir o código necessário, e você faz isso aproveitando todas as maravilhas da sintaxe C#. Vou propor um exemplo: um analisador para uma gramática parcial Java ☕.

Estou escolhendo Java porque é complexo o suficiente para nos permitir ver como o Sprache pode tornar sua vida mais fácil; tabém por que o Java está próximo do C#, então os leitores entenderão rapidamente a maior parte dele; e porque a gramática formal do Java é estruturada de tal forma que é possível extrapolar sua gramática sem muita pesquisa.

Obviamente, escrever um analisador completo demoraria muito; teremos que nos limitar a um analisador parcial. A maneira como fazemos isso é obter o código que queremos analisar e, em seguida, especificar a gramática exatamente para isso (eu chamo essa abordagem de best fit, importante princípio ágil). Então, escolhi uma vítima para este esforço: Google Authenticator é a fonte de um aplicativo Android que gera OTP’s. O aplicativo pode ser encontrado na Play Store.

😎 Eu já ysei este código-fonte como base para reproduzir o algoritmo de OTP, então estou familiarizado com ele.

Para ter um objetivo tangível, iremos gerar um gráfico de dependências entre classes do código; Isso deve ajudá-lo a saber como fazer mais do que apenas a análise, mas também como usar o código analisado para obter insights ou produzir outros artefatos.

Java BNF

O ponto de partida para nosso código é a gramática formal do Java. O eBNF - Notação ou Forma Backus-Naur Estendida - é uma descrição de uma gramática formal. Por exemplo, um bloco for em Java pode ser:

Exemplo:

for (int i = 0; i < 100; i++) { System.out.println(i); }

Gramática:

FORBLOCK = "for" "(" INITIALIZER ";" CONDITION ";" INCREMENT) BLOCK

INITIALIZER = ASSIGNMENT

ASSIGNMENT = TYPE VARIABLE "=" LITERAL 

CONDITION = BOOLEAN_EXPRESSION

INCREMENT = VARIABLE "++" | "++" VARIABLE

BLOCK = STATEMENT | "{" STATEMENT_LIST "}"

❗ Esta gramática está incompleta e não necessariamente correta; Este é um guia prático sobre como usar o Sprache, não sobre BNF e linguagens formais.

Portanto, começamos observando nosso código-alvo e criando uma pequena gramática. Para manter as coisas simples, iremos escrever analisadores para cada fonte em java/com/google/android/apps/authenticator/ e ignorar os arquivos não-java.

Por exemplo, dê uma olhada em AuthenticatorActivity.java, o primeiro arquivo no escopo. Você verá que as primeiras linhas são comentários e então temos uma instrução package, seguida por várias instruções import e, finalmente, uma definição de class. Excluindo os comentários (abordaremos isso mais tarde), a gramática seria:

JAVA_FILE = PACKAGE, IMPORT_LIST, CLASS_DECLARATIONS;

PACKAGE = "pacote", PACKAGE_NAME, ";";

PACKAGE_NAME = WORD, {"." PALAVRA };

WORD = CHARACTER, {CHARACTER};

CHARACTER = LETTER | DIGIT;

IMPORT_LIST = IMPORT, {IMPORT};

IMPORT = "importar", PACKAGE_NAME, ";";

CLASS_DECLARATION = "public", "class", WORD, "{" (*omitido*) "}";

Dê uma olhada nessa linguagem, compare-a com o arquivo, mas cheque-a contra seu conhecimento de Java (ou C#, apenas percebendo que essas duas linguagens são muito semelhantes). Por um lado, você provavelmente verá que a gramática acima pode ser usada para produzir o código-fonte; por outro, você perceberá rapidamente que ele não leva em consideração muitas construções que são legais em Java: por exemplo, uma fonte pode não ter imports quaisquer. Isso é o que quero dizer com * melhor ajuste * - estamos procurando uma maneira de analisar apenas o código no escopo.

Configurando o projeto

Assim que tivermos uma pequena gramática, podemos começar a codificar. Crie um novo projeto de biblioteca dotnet, adicione Sprache a ele via Nuget, crie um projeto de teste adicional com xUnit e baixe o código-fonte do Google Authenticator paraum diretório.

Definiremos estruturas de dados para armazenar cada elemento de nossa gramática e um teste para verificar se a análise funcionou conforme o esperado.

// BNF classes
public class JavaFile
{
    public Package Package { get; private set; }

    public List<Import> ImportList { get; private set; }

    public ClassDefinition ClassDefinition { get; private set; }
}

public class Package
{
    public PackageName PackageName { get; set; }
}

public class PackageName
{
	public PackageName() {}

	public PackageName(List<string> identifers) 
	{ 
		Identifiers = identifers;
	}

	public List<string> Identifiers { get; } = new List<string>();
}

public class Import
{
    public PackageName PackageName { get; set; }
}

public class ClassDefinition
{
    // OMMITED
}

Algumas coisas importantes a serem observadas na estrutura acima:

  • Eu não defini ImportList ou qualquer estrutura de lista - eu simplesmente usei o List genérico do C#.
  • Eu não defini uma construção de WORD ainda - irei armazená-las simplesmente como strings por enquanto, já que não estamos interessados ​​nela.

Agora, como se parece um parser? Precisamos de algo que possa obter os dados da fonte - texto, afinal - e produzir as estruturas acima:

interface IParser <T>
{
    T Parse (código de string);
}

Este é um analisador básico para uma determinada definição T - é apenas um único método que lê uma string e retorna a estrutura desejada. Começaremos declarando um dos analisadores básicos, o analisador Package. Revisitaremos essas estrutura com o tempo.

public class PackageNameParser : IParser<Package>
{
    public Package Parse(string code)
    {
        throw new NotImplementedException();
    }
}

Este será o nosso ponto de partida para o analisador.

Com essas classes definidas, podemos passar à configuração dos testes.

Os primeiros testes

😎 Sempre escreva os testes primeiro.

Usarei o xUnit, que provavelmente é o melhor framework de testes para C#. Você pode adaptar o código abaixo para o que quiser.

O primeiro caso de teste deve ser um “aquecimento”, então testamos o que acontece quando o código é nulo.

public class PackageNameParserTests
{
    [Fact]
    public void Parse_WhenCodeNull_Throws()
    {
        var sut = new PackageNameParser();

        Assert.Throws<ArgumentNullException>(() => sut.Parse(null));
    }
}

Execute o teste - ele falhará, como de costume, em conformidade com uma abordagem red-green-refactor. A próxima etapa é deixá-lo verde:

public class PackageNameParser : IParser<PackageName>
{
    public PackageName Parse(string code)
    {
        if (code == null) throw new ArgumentNullException(nameof(code));

        throw new NotImplementedException();
    }
}

Execute-o novamente e o teste será aprovado. O aquecimento está feito, nosso próximo passo é criar um caminho feliz. Queremos testar se podemos capturar corretamente o nome do pacote:

[Fact]
public void Parse_WhenValidPackage_ReturnsName()
{
    var packageExpresison = "package tinyJavaParser;";

    var sut = new PackageNameParser();
    
    var actual = sut.Parse(packageExpresison);

    Assert.Equal("tinyJavaParser", actual.Indentifiers[0]);
}

Execute-o e o teste falhará. Vamos implementar nosso primeiro analisador Sprache!

Analisadores Sprache

Se você der uma olhada no README do Sprache, saberá rapidamente como trabalhar com ele. Tudo começa com o objeto Parse estático, que pode ser chamado para analisar vários tipos de textos. Você constrói um analisador complexo combinando esses analisadores básicos usando LINQ.

Por exemplo, nosso nome de pacote é uma string feita de chars, então podemos usar Sprache.Parse.Letter para analisá-lo, mas primeiro devemos levar em conta a palavra-chave package e espaços que vem antes:

Parser<PackageName> parser =
    from packageKeyword in Sprache.Parse.String("package").Once()
    from space in Sprache.Parse.WhiteSpace.Many()
    from packageName in Sprache.Parse.Letter.Many().Text()
    from ending in Sprache.Parse.Char(';')
    select new PackageName { Indentifiers = new List<string> { packageName } };

Vejamos linha por linha. Em primeiro lugar, consideramos a palavra-chave do pacote, afirmando claramente que ela deve aparecer apenas uma vez:

from packageKeyword in Sprache.Parse.String("package").Once()

Então sabemos que haverá alguns espaços entre a palavra-chave e o identificador:

    from space1 in Sprache.Parse.WhiteSpace.Many()

Depois disso, extraímos o nome do pacote, que é uma sequência de letras:

    from packageName in Sprache.Parse.Letter.Many().Text()

E, finalmente, certificamo-nos de que a linha termina com um ;:

    from ending in Sprache.Parse.Char(';')

Depois de fazer tudo isso, podemos produzir a estrutura analisada, PackageName, usando os dados que coletamos antes:

    select new PackageName { Indentifiers = new() { packageName } };

Vamos usar esse conhecimento e implementar o método:

public PackageName Parse(string code)
{
    if (code == null) throw new ArgumentNullException(nameof(code));

    Parser<PackageName> parser =
        from packageKeyword in Sprache.Parse.String("package").Once()
        from space in Sprache.Parse.WhiteSpace.Many()
        from packageName in Sprache.Parse.Letter.Many().Text()
        from ending in Sprache.Parse.Char(';')
        select new PackageName(new() { packageName }) };

    return parser.Parse(code);
}

Execute os testes, você obterá 🟢. Agora, antes de passarmos para refatorar, quero melhorar o teste que acabamos de fazer e torná-lo mais genérico.

O teste considera apenas um nome de pacote com uma única palavra. Isso não é suficiente, e talvez você já tenha adivinhado que os identificadores compostos falharão. Adicionaremos alguns outros exemplos, e a melhor fonte para eles é - você adivinhou! - o código-fonte do Autenticador.

Você pode perceber que também não consideramos possíveis identificadores que tenham letras ou símbolos como sublinhado. Mas, para manter nosso objetivo, não precisamos de um analisador que leia todos os códigos Java válidos já escritos, em vez disso, apenas algo que analise o fonte com o qual estamos lidando. Isso pode não ser o caso em outros projetos onde você precise de um parser - por exemplo, talvez você não tenha acesso total ao código antes de executar o analisador e, nesse caso, você precisará dar um mergulho profundo no definição de linguagem. Da mesma forma, nosso analisador não está tentando validar o código que está consumindo - seja o que for que encontrarmos nesses arquivos, aceitamos que seja Java válido. Novamente, você pode querer adotar uma abordagem diferente, por exemplo, se este analisador for alimentado com código escrito apenas para ele, já que então você terá pessoas cometendo erros e precisará dizer a elas quais são.

Para encontrar os exemplos de pacotes, usei apenas o VSCode para abrir o diretório onde o código está, java/com/google/android/apps/authenticator/, e abri a ferrament de pesquisa:

Caixa de pesquisa em VSCode

E agora mudamos o teste de Fact para Theory usando alguns desses nomes:

Eu examinei a lista de pacotes e escolhi aqueles que achei representativos do domínio do nome. Vamos, depois, analisar tudo, mas é importante que antes disso já tenhamos alguns bons testes em funcionamento.

[Theory]
[InlineData("tinyJavaParser")]
[InlineData("com.google.android.apps.authenticator")]
[InlineData("com.google.android.apps.authenticator.enroll2sv.wizard")]
public void Parse_WhenValidPackage_ReturnsName(string packageName)
{
    var packageExpresison = $"package {packageName};";

    var sut = new PackageNameParser();

    var actual = sut.Parse(packageExpresison);

    Assert.Equal(packageName, string.Join('.', actual.Identifiers));
}

Tome seu tempo para entender as mudanças que fizemos no teste. Lembre-se de que a etapa refatorar se aplica também aos testes, portanto, embora possamos poder manter o teste como estava e apenas adicionar uma nova teoria, isso é mais limpo, ou seja, mais fácil de manter.

Agora executamos os testes e, claro, 🔴. É hora de corrigir o código.

Primeiro, tentamos corrigi-lo para * com.google.android.apps.authenticator *, contabilizando vários identificadores:

public PackageName Parse(string code)
{
    if (code == null) throw new ArgumentNullException(nameof(code));

    Parser<string> identifierParser = Sprache.Parse.Letter.Many().Text();

    Parser<PackageName> parser =
        from packageKeyword in Sprache.Parse.String("package").Once()
        from space in Sprache.Parse.WhiteSpace.Many()
        from packageHead in identifierParser
        from packageTail in (from delimiter in Sprache.Parse.Char('.').Once()
                                from identifier in identifierParser
                                select identifier).Many()
        from terminator in Sprache.Parse.Char(';')
        select new PackageName { Identifiers = (new[] { packageHead }).Concat(packageTail).ToList() };

    return parser.Parse(code);
}

Vamos mais uma vez dissecar o código.

Começamos criando um “sub parser”, por assim dizer, que lê um identificador. Deve ser muito simples, pois é o mesmo código que tínhamos antes - pegue o máximo de letras em sequência possível e converta em “texto”, ou seja, uma string.

Parser<string> identifierParser = Sprache.Parse.Letter.Many().Text();

Agora incrementamos as regras de análise antigas para contabilizar as repetições de identificadores. Fazemos isso obtendo pelo menos o primeiro identificador e, opcionalmente, muitos outros. packageTail também usa um sub-analisador que eu não declarei, então é embutido porque só faz sentido dentro deste analisador.

from packageHead in identifierParser
from packageTail in (from delimiter in Sprache.Parse.Char('.').Once()
                        from identifier in identifierParser
                        select identifier).Many()

Finalmente, precisamos criar uma lista a partir do identificador único packageHead e os múltiplos em packageTail, então eu trapacei um pouco:

select new PackageName { Identifiers = (new[] { packageHead }).Concat(packageTail).ToList() };

Eu crio um array apenas com o packageHead (new [] {packageHead}) e concateno-o wcom packageTail. Depois disso, eu apenas chamo ToList() para transformar o array resultante em uma lista.

Isso testará 🟢 verde para "com.google.android.apps.authenticator", mas ainda falhará para "com.google.android.apps.authenticator.enroll2sv.wizard ". Vamos dar uma olhada no erro:

Message: 
    Sprache.ParseException : Parsing failure: unexpected '2'; expected ; (Line 1, Column 53); recently consumed: tor.enroll

Sprache está nos dizendo que há um 2 que ele não esperava no stream e que acabou de consumir "tor.enroll". Se olharmos para a string de entrada, é fácil ver por que ela falha:

                         Apenas leia daqui
                                  ↓
com.google.android.apps.authenticator.enroll2sv.wizard
                                            ↑
                                      Falhou aqui

Portanto, como esperado, o número 2 não é permitido. Isso é apenas uma questão de expandir a definição de identifierParser para levar isso em consideração:

Parser<string> identifierParser = Sprache.Parse.LetterOrDigit.Many().Text();

Faça testes e aprecie seu 🟢!

Refatorar!

Agora é a hora de refatorar o código. Veremos como tornar nosso código mais simples de manter e usar.

Há duas coisas que devemos observar:

  • Em PackageNameParser.Parse, criamos duas instâncias de parser, identifierParser e parser. Eles são usados ​​apenas uma vez, logo no retorno. Várias chamadas para este método resultam na recriação dessas instâncias, mas podem ser reutilizadas. Isso também é evidenciado pelos documentos do Sprache.

  • Definimos uma interface IParser<T>, e Sprache tem um delegate Parser<out T>, que é muito próximo ao nosso. O Sprache pode definir analisadores usando seu delegate, e podemos combiná-los para produzir analisadores novos e mais complexos.

Com esse conhecimento, devemos refatorar nosso código para definir uma vez e usar os analisadores várias vezes; Devemos também abandonar nossa interface de análise e usar o delegado do Sprache. A maneira de fazer as coisas do Sprache é definir esses delegados como membros estáticos de uma classe, para que possamos criar:

public static class JavaGrammar
{
    public static readonly Parser<string> Identifier = Sprache.Parse.LetterOrDigit.Many().Text();

	public static readonly Parser<PackageName> PackageName =
		from packageKeyword in Sprache.Parse.String("package").Once()
		from space in Sprache.Parse.WhiteSpace.Many()
		from packageHead in Identifier
		from packageTail in (from delimiter in Sprache.Parse.Char('.').Once()
								from identifier in Identifier
								select identifier).Many()
		from terminator in Sprache.Parse.Char(';')
		select new PackageName(new[] { packageHead }.Concat(packageTail).ToList());
}

E mudar os testes para refletir isso:

public class PackageNameParserTests
{
    [Fact]
    public void Parse_WhenCodeNull_Throws()
    {
        Assert.Throws<ArgumentNullException>(() => JavaGrammar.PackageName.Parse(null));
    }

    [Theory]
    [InlineData("tinyJavaParser")]
    [InlineData("com.google.android.apps.authenticator")]
    [InlineData("com.google.android.apps.authenticator.enroll2sv.wizard")]
    public void Parse_WhenValidPackage_ReturnsName(string packageName)
    {
        var packageExpresison = $"package {packageName};";

        var actual = JavaGrammar.PackageName.Parse(packageExpresison);

        Assert.Equal(packageName, string.Join('.', actual.Identifiers));
    }
}

❗ Se você estiver recebendo um erro informando que o delegado não tem um método Parse, não se preocupe! Você apenas tem que adicionar uma diretiva using Sprache; no topo do arquivo.

Você pode remover a interface IParser que criamos para nos ajudar a definir como o código deve ser.

Análise

Ufs, demorou muito! “Nós vimos muito! Vamos revisar tudo isso por um momento, certo?

  • Você aprendeu que as sintaxes de linguagem são governadas por * gramáticas * e que podem ser expressas com uma notação conhecida como BNF ou EBNF.
  • Você criou um EBNF simplificado para Java, levando em consideração apenas o que estava no escopo. Você sabe que chamamos isso de * melhor ajuste *, e um princípio ágil semelhante ao YAGNI - construa apenas o que você vai usar.
  • Você criou vários casos de teste, a maioria derivados do próprio domínio do problema - a fonte do Autenticador do Google.
  • Você aprendeu como combinar analisadores Sprache para criar outro analisador mais complexo.

Isso lançou as bases para analisar as estruturas de programa mais complexas. No próximo artigo, terminaremos nossa gramática criando mais analisadores que podem lidar com todo o código-fonte. Também mostrarei como lidar com comentários e como “pular” código no qual você não está interessado. Seguindo esse artigo, como um bônus, terminaremos de construir nossa ferramenta e gerar o gráfico que mostrará aos usuários a relação entre as aulas.

Todo o código produzido até agora foi armazenado no Github. Você pode fazer um fork e usá-lo da maneira que quiser. Para obter a versão exata deste código, use esta tag.


#dotnet   #programação   #linguagem