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.