🍅 🍴 🏇🏻 Complementando o SQL. Parte 1. A complexidade da análise. Histórias sobre como finalizar o arquivo ANTLR 📀 📫 👩🏼‍🏫

Publico o artigo original sobre Habr, cuja tradução está publicada no blog da Codingsight .

O que acontecerá neste artigo?

Trabalho na empresa há mais de cinco anos, que desenvolve a linha IDE para trabalhar com bancos de dados. Ao iniciar o trabalho neste artigo, eu não conseguia imaginar quantas histórias interessantes eu conseguia lembrar, porque, quando terminei, recebi mais de 30 páginas de texto. Depois de um pouco de reflexão, agrupei as histórias por tópico e dividi o artigo em várias.

À medida que publicar, adicionarei links para as seguintes partes:

Parte 1. A complexidade da análise. Histórias sobre como finalizar o ANTLR com um arquivo
Parte 2. Otimização do trabalho com seqüências de caracteres e abrir arquivos
Parte 3. Vida útil das extensões do Visual Studio. Trabalhe com IO. Uso incomum do SQL
Parte 4. Trabalhando com exceções, o impacto dos dados no processo de desenvolvimento. Usando o ML.NET

Muitas coisas interessantes aconteceram durante o trabalho: encontramos vários bugs no .NET, otimizamos algumas funções várias vezes e outras apenas por cento, fizemos algo muito legal na primeira vez e algo que não conseguimos, mesmo depois de algumas tentativas. Minha equipe está desenvolvendo e dando suporte aos recursos da linguagem IDE, sendo a principal a conclusão de código. Daí o nome da série de artigos. Em cada uma das partes, contarei várias histórias: algumas sobre sucessos, outras sobre fracassos.

Nesta parte, vou me concentrar nos problemas de análise de SQL, na luta contra esses problemas e nos erros cometidos nessa luta.

Para quem está interessado em apenas parte disso e apenas para facilitar a navegação, o conteúdo do artigo:

Conteúdo

Quem sou eu?

Eu vim para este trabalho em junho, com muito pouca experiência. Eu, como muitos, vim para programação porque queria fazer brinquedos. Vários, mesmo com bastante sucesso. Eu até escrevi sobre o desenvolvimento de um aqui. Recentemente, a propósito, ele a ressuscitou em outro servidor. Ainda havia uma dúzia de jogos feitos ou abandonados em diferentes estágios de prontidão. Além dos jogos, antes de começar este trabalho, consegui concluir vários projetos como freelancer. O maior deles foi o aplicativo de mídia social, que era um portal de futebol com tabelas de torneios, dados de jogadores e a capacidade de notificar os usuários da pontuação ou dos objetivos marcados via SMS. Isso foi feito há quase 10 anos. Naquela época, nem todo mundo usava smartphones, e quem costumava ir mais frequentemente sem a Internet ou com o EDGE de três maldições no qual abrir um site de texto nem sempre era possível. Então a ideia me pareceu boa.

De alguma forma, além de jogos, eu também fui atraído por criar ajustes diferentes para mim ou para outros desenvolvedores. Às vezes, ele estava perto do que eu tinha que fazer no trabalho um pouco mais tarde. Por exemplo, um dos projetos que eu fiz ao estudar a API do Win32 foi um programa que destacava o código XML no Rich Edit Control. Além disso, foi possível fazer o upload de códigos retroiluminados para códigos BMP, HTML ou BB que estavam na moda em diferentes fóruns.

Outro projeto que ficou muito próximo do que aconteceu no trabalho foi um programa que analisa o código C / C ++ e cria um diagrama de blocos a partir dele. O fluxograma estava em estrita conformidade com os requisitos de um professor da universidade. Foi feito desajeitadamente, na testa, com zero conhecimento da teoria da análise sintática, e trabalhou exclusivamente no meu caráter de baixa qualidade. Alguns anos depois, enquanto limpava o computador do lixo antigo, deparei-me com ele e não consegui removê-lo, então o publiquei no github por uma questão de história.

Essas experiências, juntamente com freelancers, proporcionaram uma experiência bastante boa e possibilitaram um emprego. Com o tempo, depois de algumas dúzias de análises de sangue e lágrimas, começo a beneficiar a empresa e o produto. Voltando, é bem engraçado entender que, como resultado de vários acidentes, comecei a fazer exatamente o que me atraía.

Quais são as dificuldades?

Esse bloco é necessário para imergir o leitor no contexto do que estamos realmente fazendo.

Desenvolvimento de desktop

Talvez isso não seja nem complexidade, porque já é um campo muito maduro no qual não há muito desconhecido, as bibliotecas são estáveis, as melhores práticas são conhecidas. Esse recurso do nosso projeto está aqui, porque eu, como muitos outros programadores, propenso à novidade, e a novidade agora está na web. Houve dias em que, na chuva, subi no parapeito da janela, coberto com um cobertor, uma caneca de cacau, e pensei em redis, reagir, carga pesada e sistemas distribuídos que estão sendo desenvolvidos em algum lugar sem mim agora. O outro lado desse problema é que não é fácil descrever a complexidade do projeto para desenvolvedores familiares que bebem cerveja, e quando você trabalha em aplicativos que operam de acordo com leis fundamentalmente diferentes, fica ainda mais difícil.

Analisando SQL e Dialetos

Também escrevi pequenos analisadores para diferentes idiomas antes deste trabalho. Durante algum tempo eu ministrei cursos de .NET. Para alguns grupos, como uma tarefa adicional, como parte do tópico "string", eles sugeriram a criação de seu próprio analisador JSON simples. Somente o SQL e suas variantes estão longe de XML ou JSON projetados para serem igualmente compreensíveis para analisadores e pessoas. Além disso, o SQL é sintaticamente mais complexo que o C / C ++, com suas muitas funções acumuladas ao longo de uma longa história. O SQL é estruturado de maneira diferente, eles tentaram fazer com que parecesse uma linguagem natural, com bastante sucesso, a propósito. O idioma possui vários milhares de palavras-chave (dependendo do dialeto). Freqüentemente, para distinguir uma expressão de outra, você precisa espiar duas ou mais palavras (tokens) para a frente. Essa abordagem é chamada de lookahead. Existe uma classificação de analisadores de acordo comquão longe eles podem olhar à frente: LA (1), LA (2) ou LA (*), o que significa que o analisador pode olhar o mais longe possível para determinar a ramificação correta. Às vezes, o final opcional de uma cláusula dentro de uma instrução SQL coincide com o início de outra, que também é opcional: tais situações tornam os analisadores muito mais complicados. O T-SQL derrama água no fogo, no qual o ponto-e-vírgula é opcional e o final possível, mas não obrigatório, de algumas instruções SQL pode entrar em conflito com o início de outras.tais situações complicam bastante os analisadores. O T-SQL derrama água no fogo, no qual o ponto-e-vírgula é opcional e o final possível, mas não obrigatório, de algumas instruções SQL pode entrar em conflito com o início de outras.tais situações complicam bastante os analisadores. O T-SQL derrama água no fogo, no qual o ponto-e-vírgula é opcional e o final possível, mas não obrigatório, de algumas instruções SQL pode entrar em conflito com o início de outras.

Ainda não acredita? Existe um mecanismo para descrever linguagens formais através de gramáticas . Gramática é um código em um idioma que descreve outro. A partir de uma gramática, você geralmente pode gerar um analisador usando uma ferramenta. As ferramentas e idiomas de descrição gramatical mais famosos são o YACC e o ANTLR . Os analisadores gerados pelo YACC são usados diretamente nos mecanismos MySQL , MariaDB , PostgreSQL. Você pode tentar levá-los diretamente do código-fonte aberto e desenvolver a conclusão do código e outras funções com base na análise SQL com base neles. Além disso, essa implementação receberia atualizações gratuitas em termos de desenvolvimento, e o analisador se comportaria como idêntico ao mecanismo de banco de dados. Então, por que usamos o ANTLR? Ele suporta qualitativamente C # /. NET, existem boas ferramentas para trabalhar com ele, sua sintaxe é muito mais fácil de ler e escrever. A sintaxe do ANTLR acabou sendo tão conveniente que a Microsoft a usou recentemente na documentação oficial do C #.

Voltemos à minha prova da complexidade do SQL, em comparação com outras linguagens, em termos de análise. Para fazer isso, quero comparar os tamanhos da gramática para diferentes idiomas disponíveis publicamente. No dbForge, usamos nossas próprias gramáticas, elas são mais completas do que as disponíveis publicamente, mas, infelizmente, estão muito entupidas com inserções de código C # para oferecer suporte a funções diferentes, mais sobre isso na seção "Analisando sem árvores" na seção "Erros".

Abaixo estão os tamanhos de gramática para diferentes idiomas:

JS - 475 linhas analisador + 273 lexer = 748 linhas
Java - 615 linhas analisador + 211 lexer = 826 linhas
C # - 1159 linhas analisador + 433 lexer = 1592 linhas
C ++ - 1933 linhas

MySQL- analisador de 2515 linhas + 1189 lexer = 3704 linhas
T-SQL - analisador de 4035 linhas + 896 lexer = 4931 linhas
PL SQL - analisador de linhas 6719 + 2366 lexer = 9085 linhas

No final de alguns lexers, há uma enumeração dos caracteres unicode disponíveis no idioma, isso é inútil em avaliação da complexidade do idioma. Peguei o número de linhas antes de iniciar essas transferências.

Pode haver perguntas sobre a complexidade de analisar um idioma com base no número de linhas em sua gramática. As perguntas também podem ser sobre a abundância de gramáticas abertas em comparação com a sintaxe real dos idiomas. Apesar disso, ainda considero útil fornecer esses números, pois o spread é muito grande.

Isso não é tudo, porque não precisamos apenas analisar vários arquivos no SQL. Estamos fazendo um IDE, o que significa que devemos trabalhar em scripts incompletos ou inválidos. Mesmo se você escrever seus scripts sem erros, talvez você os escreva de forma inconsistente, é improvável que o script seja válido durante todo o processo de seu desenvolvimento. Por exemplo, primeiro escrevo "SELECT FROM", após o que terei o prazer de ver a lista de tabelas disponíveis. Quando seleciono uma tabela, reorganizo o carro para SELECT, pressione a barra de espaço e aguarde a lista de colunas dessa tabela específica. Este é um exemplo muito simples, mas mostra que o analisador que fornece a conclusão do código no IDE não pode falhar, com a exceção de encontrar um script inválido. Tivemos que criar muitos truques para garantir que a dica de ferramenta funcionasse corretamente em muitos desses cenários,mas os usuários ainda enviam cenários diferentes para trabalhar com scripts inacabados, o que significa que precisamos criar novos truques.

Guerras dedicadas

Ao analisar o código, às vezes há situações em que a próxima palavra não deixa claro qual das duas alternativas escolher. Às vezes, basta espiar um número estritamente definido de palavras com antecedência e você pode definitivamente escolher uma alternativa. O mecanismo para resolver esse tipo de imprecisão é chamado de lookahead da ANTLR. O método analisador, neste caso, é construído como uma cadeia incorporada de ifs, cada um dos quais parece mais uma palavra. Abaixo está um exemplo de gramática que gera incerteza desse tipo.

rule1:
    'a' rule2 | rule3
    ;

rule2:
    'b' 'c' 'd'
    ;

rule3:
    'b' 'c' 'e'
    ;

No meio da regra1, depois de passar o token 'a', o analisador terá que olhar 2 token adiante para escolher qual regra seguir. Mais uma vez, essa verificação será feita dentro da regra. Essa gramática pode ser reescrita para que essa aparência não exista; infelizmente, a estrutura geralmente sofre com essas otimizações e o ganho de desempenho é relativamente baixo.

Existem mecanismos mais complexos para resolver incertezas mais complexas. Um deles é o mecanismo de predicado de sintaxe (synpred) no ANTLR3.

Ele vem em socorro nesses casos em que, por exemplo, a conclusão opcional de uma cláusula cruza com o início da outra opcional a seguir. O predicado, em termos de ANTLR3, é o método gerado, que faz uma passagem virtual pelo texto de acordo com uma das alternativas e, se for bem-sucedido, retorna verdadeiro, essa conclusão do predicado é chamada de bem-sucedida. O passe virtual também é chamado de passe de retorno. Se o predicado funcionou com sucesso, é feito um passo real. Isso se torna um problema quando outro predicado começa dentro de um predicado e, em seguida, uma seção pode ser percorrida cem e mil vezes.

Considere um exemplo simplificado. Existem 3 pontos de incerteza (A, B, C).

O analisador entra em A, lembra a posição no texto, inicia uma passagem virtual do 1º nível.
B, , 2- .
C, , 3- .
3- , 2 .
2 , 1 B .
, A, B .

Assim, todas as verificações dentro de C serão realizadas 4 vezes, B - 3 vezes, A - 2 vezes. Mas e se a alternativa adequada for o segundo ou o terceiro da lista? Então, em algum estágio de um dos predicados, ele falhará, a posição no texto será revertida e outro predicado começará a ser executado.

Analisando repetidamente a causa do congelamento do aplicativo, nos deparamos com casos em que a “cauda” sinprada foi executada milhares de vezes. Os Synpreds são especialmente problemáticos em regras recursivas. Infelizmente, por sua natureza, o SQL é recursivo, que é pelo menos a capacidade de usar uma subconsulta em quase todos os lugares. Às vezes, com a ajuda de vários truques e truques, acaba resultando na regra, de modo que o predicado se foi.

Obviamente, o synpred tem um efeito negativo no desempenho. Em algum momento, foi necessário colocar sua população sob controle estrito. O único problema é que, ao escrever o código gramatical, a aparência do synpred pode não ser óbvia. Além disso, às vezes uma mudança em uma regra leva ao aparecimento de um predicado em outra. Isso não pode ser controlado manualmente. Para controlar o número de predicados, escrevemos um regular simples, chamado por uma Tarefa MsBuild especial. Se o número de predicados for diferente do número especificado em um arquivo separado, a Tarefa interrompeu o assembly e relatou um erro. Vendo esse erro, o desenvolvedor teve que reescrever o código de regra várias vezes, tentando se livrar de predicados desnecessários, possivelmente envolvendo outros desenvolvedores no problema. Se um predicado é inevitável,o desenvolvedor atualiza o número de predicados no arquivo correspondente. Uma alteração nesse arquivo chama atenção extra para a revisão.

Em casos raros, até escrevemos nossos próprios predicados em C # para contornar os que o ANTLR gera. Felizmente, esse mecanismo também existe.

Cool bike solutions

Herança gramatical

Após o anúncio de quaisquer alterações em cada um dos DBMS que apoiamos, nosso trabalho para apoiá-los começa. Quase sempre, o ponto de partida para isso é apoiar construções sintáticas na gramática. Para cada dialeto SQL, escrevemos nossa própria gramática, isso gera alguma repetição do código, mas, no final das contas, é mais fácil do que procurar um comum entre eles. Apenas alguns anos atrás, o MySQL e o MariaDB eram muito semelhantes, escrever gramáticas separadas era impraticável. Como essas poucas construções que estavam no MariaDB, mas não estavam no MySQL, suportamos a gramática do MySQL. Este foi um momento desagradável: para o usuário do MySQL, poderíamos sugerir construções que não seriam válidas. Nos últimos anos, o MariaDB e o MySQL se tornaram muito divergentes em termos de sintaxe e mais. Ficou aparenteque é errado oferecer suporte a dois idiomas diferentes na mesma gramática.

Uma solução possível pode ser uma cópia completa da gramática, após a qual cada uma é suportada separadamente. Como resultado de uma longa discussão, tomamos uma decisão ousada. Estou muito feliz por não termos copiado o código, todas as células em mim resistiram a essa decisão. Decidiu-se escrever seu próprio ANTLR, o pré-processador de gramática, que implementa o mecanismo de herança gramatical. Há algum tempo, deparei-me com uma gramática ANTLR3 no repositório oficial de gramáticas ANTLR4. Eu acho que essa frase precisa ser lida várias vezes para perceber a profundidade da loucura.

Discutindo a idéia de herança, rapidamente percebemos que gostaríamos de ter um mecanismo para o polimorfismo. A capacidade da gramática do herdeiro não apenas redefinir a regra, mas também chamar a base. Além disso, quero controlar a posição da chamada da regra básica: começo, meio ou fim. Decidimos que todas as regras podem ser redefinidas, para isso você não precisa especificar nada adicional. Para redefinir uma regra, basta declarar uma regra com o mesmo nome na gramática sucessora. Depois disso, a regra da gramática pai estará disponível com um nome diferente.

O ANTLR torna uma ferramenta agradável para o desenvolvimento ajustando - há uma extensão para o VS, há o ANTLRWorks. Apresentando o mecanismo de herança, eu não gostaria de perder esta oportunidade. Mas como então indicar a gramática básica? Você pode criar algum tipo de convenção para nomear arquivos, mas isso não é de todo óbvio. Outra opção seria indicar essas informações adicionais em um arquivo separado, mas mesmo agora, ao digitar essas linhas, senti o cheiro dessa solução. A saída foi uma indicação da gramática básica na gramática do herdeiro no formato de um comentário da ANTLR. Todas as ferramentas simplesmente ignoram esse texto e podemos facilmente extrair o código que nos interessa.

Os requisitos foram formados, é hora de implementá-los. Escrevemos a Tarefa MsBuild, que foi incorporada ao sistema geral de compilação como uma ação de pré-compilação. Task executou o trabalho do pré-processador de gramática ANTLR, gerando a gramática resultante da base e herdada. A gramática resultante já foi processada pela própria ANTLR. Se uma regra com o mesmo nome da pai for encontrada na gramática sucessora, a regra básica será renomeada: o nome da gramática pai será adicionado ao seu nome após o sublinhado. Por esse nome, ele poderia ser contatado no herdeiro.

O mecanismo do pré-processador em si não demorou muito tempo, mas, juntamente com a geração do analisador, resultou em lentidão de todas as remontagens do projeto em 10 a 20 segundos. Em algum momento, isso deixou de nos agradar. Decidimos pensar em como isso pode ser otimizado. A solução foi adicionar o hash da soma de todas as gramáticas das quais depende, na forma de um comentário, ao cabeçalho do arquivo do analisador CS. Antes de fazer qualquer coisa, o pré-processador comparava esses hashes com os arquivos do disco e, se eles não diferiam, o arquivo do analisador era considerado relevante. No estágio inicial de desenvolvimento, tivemos que analisar mais de uma vez os analisadores e gramáticas inválidas coletadas pela versão desatualizada do pré-processador. Como resultado, a soma de hash da montagem com o pré-processador apareceu no comentário do cabeçalho.

Outra ANTLR de pós-processamento

Em muitas linguagens de programação, se a palavra for a chave, ela não poderá mais ser usada como o nome do objeto. No SQL, dependendo do dialeto, de 800 a 3000 palavras-chave. A maioria deles está intimamente relacionada à área de assunto; além disso, nem todos foram introduzidos imediatamente; portanto, a proibição de usá-los como nomes de objetos seria recebida com uma onda de indignação. O SQL introduz o conceito de palavras-chave reservadas e não reservadas. Você não pode nomear um objeto da mesma maneira que uma palavra-chave reservada (SELECT, FROM etc) sem citá-lo, pois não é uma palavra-chave reservada (CONVERSATION, AVAILABILITY etc) - você pode. Esse comportamento complica o desenvolvimento do analisador. No momento da análise lexical, o contexto é desconhecido, mas o analisador requer números diferentes para o identificador e a palavra-chave. Para resolver esse problema, adicionamos mais um pós-processamento ao analisador ANTLR.O pós-processamento substitui todas as verificações explícitas por um identificador, com uma chamada para um método especial. Este método implementa uma verificação mais complicada. Se um identificador for inserido e outro for esperado, tudo estará bem, mas se uma palavra-chave não reservada for fornecida à entrada, ela deverá ser verificada adicionalmente. Uma verificação adicional é que o método é examinado no contexto atual na procura por ramificações, onde essa palavra-chave não reservada pode ser usada precisamente como uma palavra-chave e, se não houver ramificações, pode ser usada como um identificador.mas se uma palavra-chave não reservada for inserida, ela precisará ser verificada adicionalmente. Uma verificação adicional é que o método é examinado no contexto atual na procura por ramificações, onde essa palavra-chave não reservada pode ser usada precisamente como uma palavra-chave e, se não houver ramificações, pode ser usada como um identificador.mas se uma palavra-chave não reservada for inserida, ela precisará ser verificada adicionalmente. Uma verificação adicional é que o método é examinado no contexto atual na procura por ramificações, onde essa palavra-chave não reservada pode ser usada precisamente como uma palavra-chave e, se não houver ramificações, pode ser usada como um identificador.

A rigor, esse problema só pode ser resolvido por meio do ANTLR, mas essa solução não será ótima. Uma solução clássica para esse problema é criar uma regra que lista todas as palavras-chave não reservadas e um token de identificador. Além disso, sempre que for permitido usar um identificador, não será mais usado o token de identificador do identificador, mas essa é uma regra especial. Essa solução não apenas faz com que você lembre-se de adicionar a palavra-chave quando a digita, não apenas onde é usada, mas também nesta regra especial, mas também funciona muito mais devagar.

Erros

Análise sem árvores

O resultado do analisador, como regra, é uma árvore de sintaxe. Uma árvore de sintaxe ( abstrata ou concreta ) é uma estrutura de dados que reflete o texto do programa através do prisma da gramática formal. Se você deseja implementar um editor de código com preenchimento automático para o idioma criado recentemente, tendo estudado o problema, provavelmente implementará aproximadamente o seguinte algoritmo:

Analise o texto no editor. Obtenha a árvore de sintaxe.
Encontre o nó sob o carro. Combine com a gramática. Descubra quais palavras-chave e tipos de objetos estarão disponíveis no momento.

Nesse caso, a gramática é convenientemente representada como um gráfico ou uma máquina de estados finitos.

Infelizmente, no início do desenvolvimento, o IDE ANTLR existia em sua terceira versão. A quarta versão foi reescrita do zero e é fundamentalmente diferente da terceira; ao passar o código, o analisador gerará automaticamente uma árvore de análise sem uma única linha adicional. Na terceira versão, havia um mecanismo pelo qual se podia dizer à ANTLR como construir uma árvore, mas não era muito agradável usá-la. Além disso, muitos exemplos e artigos sobre este tópico sugeriram o uso do mecanismo de ações para executar código no momento em que o analisador passa a regra. Esse mecanismo é incrivelmente conveniente e permite que você obtenha resultados rapidamente. Infelizmente, essa solução levou a grandes problemas de arquitetura com o desenvolvimento do produto e a um aumento na complexidade do suporte a novas funcionalidades. O fato é que, em um arquivo, em um arquivo gramatical,as ações começaram a se acumular associadas a um grande número de funcionalidades diferentes, o que seria bom para se espalhar para diferentes montagens. No futuro, fomos capazes de distribuir os manipuladores de ação para diferentes montagens implementando uma versão bastante complicada do padrão de notificador de assinante, mas as chamadas em si, com a transmissão das informações necessárias, ainda bagunçam nossa gramática, complicam o suporte de novas funcionalidades e impõem restrições sérias e desagradáveis à arquitetura.complicam o suporte de novas funcionalidades e impõem restrições sérias e desagradáveis à arquitetura.complicam o suporte de novas funcionalidades e impõem restrições sérias e desagradáveis à arquitetura.

Mas nem tudo é tão óbvio quanto parece. O fato é que o ANTLR3 é muito mais rápido que o ANTLR4. De acordo com nossas medidas, as diferenças são de cerca de 6 vezes. Além disso, a árvore de sintaxe para scripts grandes pode ocupar muito espaço na RAM e, desde que tenhamos que sobreviver no espaço de endereço de 32 bits dos estúdios Visual e SqlServer Management, isso pode ser crítico.

Conclusão

Os subtotais podem ser os seguintes:

ANTLR uma ferramenta poderosa para construir analisadores
Sua vantagem sobre os outros são ferramentas, sintaxe conveniente, um grande número de idiomas suportados
O ANTLR4 foi reescrito do zero e implica trabalhar com o analisador diferente da terceira versão
Sempre existe uma maneira de obter um pouco mais das bibliotecas do ThirdParty do que elas oferecem
Linguagem específica do SQL, criar analisadores para ela não é uma tarefa fácil
A análise de código para tarefas relacionadas à criação de um IDE tem suas próprias peculiaridades: você precisa considerar trabalhar em scripts não criptografados ou inválidos

Vejo você na próxima parte!

Complementando o SQL. Parte 1. A complexidade da análise. Histórias sobre como finalizar o arquivo ANTLR