🐵 🔀 👫 Complementando SQL. Parte 1. La complejidad del análisis. Historias sobre la finalización del archivo ANTLR 👂🏻 🚻 🎎

Publico el artículo original sobre Habr, cuya traducción se publica en el blog Codingsight .

¿Qué pasará en este artículo?

He trabajado en la empresa durante más de cinco años, que ha estado desarrollando la línea IDE para trabajar con bases de datos. Al comenzar a trabajar en este artículo, no podía imaginar cuántas historias interesantes podía recordar, porque cuando terminé recibí más de 30 páginas de texto. Después de pensar un poco, agrupé las historias por tema y dividí el artículo en varias.

A medida que publique, agregaré enlaces a las siguientes partes:

Parte 1. La complejidad del análisis. Historias sobre la finalización de ANTLR con un archivo
Parte 2. Optimización de trabajar con cadenas y abrir archivos
Parte 3. Vida de las extensiones para Visual Studio. Trabaja con IO. Uso inusual de SQL
Parte 4. Trabajando con excepciones, el impacto de los datos en el proceso de desarrollo. Usando ML.NET

Sucedieron muchas cosas interesantes durante el trabajo: encontramos varios errores en .NET, optimizamos algunas funciones muchas veces, y algunas solo por porcentaje, hicieron algo muy bueno la primera vez, y algo que no logramos incluso después de unos pocos intentos Mi equipo está desarrollando y respaldando las características del lenguaje IDE, la principal es la finalización del código. De ahí el nombre de la serie de artículos. En cada una de sus partes contaré varias historias: algunas sobre éxitos, otras sobre fracasos.

En esta parte, me centraré en los problemas de analizar SQL, la lucha contra estos problemas y los errores cometidos en esta lucha.

Para aquellos que estén interesados solo en una parte de esto y solo para una fácil navegación, el contenido del artículo:

Contenido

¿Quién soy?

Llegué a este trabajo en junio con muy poca experiencia. Yo, como muchos, vine a la programación porque quería hacer juguetes. Varios incluso con bastante éxito. Incluso escribí sobre el desarrollo de uno aquí. Recientemente, por cierto, la resucitó en otro servidor. Todavía había una docena de juegos hechos o abandonados en diferentes etapas de preparación. Además de los juegos, antes de obtener este trabajo, logré completar varios proyectos en forma independiente. El más grande de ellos fue la aplicación para redes sociales, que era un portal de fútbol con mesas de torneos, datos sobre jugadores y la capacidad de notificar a los usuarios el puntaje final o los goles marcados por SMS. Esto se hizo hace casi 10 años. En ese momento, no todos usaban teléfonos inteligentes, y quienes solían ir más a menudo sin Internet o con el EDGE de tres maldiciones para abrir un sitio de texto no siempre era posible. Entonces la idea me pareció buena.

De alguna manera resultó que, además de los juegos, también me sentí atraído por crear diferentes ajustes para mí u otros desarrolladores. A veces, él estaba cerca de lo que tenía que hacer en el trabajo un poco más tarde. Por ejemplo, uno de los proyectos que hice al estudiar la API de Win32 fue un programa que resalta el código XML en Rich Edit Control. Además, fue posible cargar código retroiluminado a BMP, HTML o códigos BB que estaban de moda en diferentes foros.

Otro proyecto que resultó estar muy cerca de lo que hice en el trabajo fue un programa que analiza el código C / C ++ y construye un diagrama de bloques a partir de él. El diagrama de flujo estaba en estricta conformidad con los requisitos de un maestro en la universidad. Fue hecho torpemente, en la frente, con cero conocimiento de la teoría del análisis sintáctico, y trabajó exclusivamente en mi personaje de mierda. Unos años más tarde, mientras limpiaba la computadora de basura vieja, me topé con ella y no pude eliminarla, así que la publiqué en github por el bien de la historia.

Estos experimentos, junto con el trabajo independiente, dieron una experiencia bastante buena e hicieron posible conseguir un trabajo. Con el tiempo, después de un par de docenas empapadas en sangre y lágrimas, incluso empiezo a beneficiar a la empresa y al producto. Volviendo atrás, es bastante divertido entender que, como resultado de varios accidentes, comencé a hacer exactamente lo que me atraía.

¿Cuáles son las dificultades?

Este bloque es necesario para sumergir al lector en el contexto de lo que realmente estamos haciendo.

Desarrollo de escritorio

Quizás esto ni siquiera es complejidad, porque ya es un campo muy maduro en el que no hay mucho desconocido, las bibliotecas son estables, se conocen las mejores prácticas. Esta característica de nuestro proyecto está aquí, porque yo, como muchos otros programadores, soy propenso a la novedad, y la novedad ya no existe en la web. Hubo días en que, bajo la lluvia, me subí al alféizar de la ventana, cubierto con una manta, con una taza de cacao, y pensé en los sistemas de redis, reacción, alta carga y distribuidos que se están desarrollando en algún lugar sin mí en este momento. El otro lado de este problema es que no es fácil describir la complejidad del proyecto a los desarrolladores familiares sobre la cerveza, y cuando trabajas en aplicaciones que operan de acuerdo con leyes fundamentalmente diferentes, se vuelve aún más difícil.

Analizando SQL y Dialectos

También he escrito pequeños analizadores para diferentes idiomas antes de este trabajo. Durante algún tiempo enseñé cursos .NET. Para algunos grupos, como una tarea adicional, como parte del tema "cadena", sugirieron escribir su propio analizador JSON simple. Solo SQL y sus variantes están lejos de XML o JSON diseñados para ser igualmente comprensibles para los analizadores y las personas. Además, SQL es sintácticamente más complejo que C / C ++, con sus numerosas funciones acumuladas a lo largo de una larga historia. SQL está estructurado de manera diferente, por cierto, intentaron que parezca un lenguaje natural, con bastante éxito. El idioma tiene varios miles de palabras clave (según el dialecto). A menudo, para distinguir una expresión de otra, debe mirar dos o más palabras (tokens) hacia adelante. Este enfoque se llama anticipación. Existe una clasificación de analizadores sintácticos segúnqué tan lejos pueden mirar hacia adelante: LA (1), LA (2) o LA (*), lo que significa que el analizador puede mirar lo más adelante posible para determinar la rama correcta. A veces, el final opcional de una cláusula dentro de una instrucción SQL coincide con el comienzo de otra, que también es opcional: tales situaciones hacen que los analizadores sean mucho más complicados. T-SQL vierte agua en el fuego, en el que el punto y coma es opcional, y el final posible, pero no obligatorio, de algunas instrucciones SQL puede entrar en conflicto con el comienzo de otras.Tales situaciones complican enormemente los analizadores. T-SQL vierte agua en el fuego, en el que el punto y coma es opcional, y el final posible, pero no obligatorio, de algunas instrucciones SQL puede entrar en conflicto con el comienzo de otras.Tales situaciones complican enormemente los analizadores. T-SQL vierte agua en el fuego, en el que el punto y coma es opcional, y el final posible, pero no obligatorio, de algunas declaraciones SQL puede entrar en conflicto con el comienzo de otras.

¿Todavía no crees? Hay un mecanismo para describir lenguajes formales a través de gramáticas . La gramática es un código en un idioma que describe otro. A partir de una gramática, a menudo puede generar un analizador utilizando una herramienta. Las herramientas y lenguajes de descripción gramatical más famosos son YACC y ANTLR . Los analizadores generados por YACC se usan directamente en los motores MySQL , MariaDB , PostgreSQL. Puede intentar tomarlos directamente del código abierto y desarrollar la finalización del código y otras funciones basadas en el análisis SQL basado en ellos. Además, dicha implementación recibiría actualizaciones gratuitas en términos de desarrollo, y el analizador se comportaría con la garantía de ser idéntico al motor de la base de datos. Entonces, ¿por qué usamos ANTLR? Es cualitativamente compatible con C # /. NET, existen buenas herramientas para trabajar con él, su sintaxis es mucho más fácil de leer y escribir. La sintaxis ANTLR resultó ser tan conveniente que Microsoft la ha utilizado recientemente en la documentación oficial de C #.

Volvamos a mi prueba de la complejidad de SQL, en comparación con otros lenguajes, en términos de análisis. Para hacer esto, quiero comparar los tamaños de gramática para diferentes idiomas disponibles públicamente. En dbForge utilizamos nuestras propias gramáticas, son más completas que las disponibles públicamente, pero, desafortunadamente, están muy obstruidas con insertos de código C # para admitir diferentes funciones, más sobre esto en la sección "Análisis sin árboles" en la sección "Errores".

A continuación se muestran los tamaños de gramática para diferentes idiomas:

JS - analizador 475 líneas + 273 lexer = 748 líneas
Java - analizador 615 líneas + 211 lexer = 826 líneas
C # - 1159 líneas analizador + 433 lexer = 1592 líneas
C ++ - 1933 líneas

MySQL- 2.515 líneas analizador + 1189 lexer = 3704 líneas
T-SQL - 4035 líneas analizador + 896 lexer = 4931 líneas
PL SQL - 6719 líneas analizador + 2366 lexer = 9085 líneas

Al final de algunos lexers no es una enumeración de caracteres Unicode disponible en el idioma, esto es, en inútil evaluación de la complejidad del lenguaje. Tomé el número de líneas antes de comenzar tales transferencias.

Puede haber preguntas sobre la complejidad de analizar un lenguaje en función del número de líneas en su gramática. Las preguntas también pueden ser sobre la plenitud de las gramáticas abiertas en comparación con la sintaxis real de los idiomas. A pesar de esto, todavía considero útil dar estos números, ya que la extensión es demasiado grande.

Esto no es todo, porque no solo necesitamos analizar varios archivos en SQL. Estamos haciendo un IDE, lo que significa que debemos trabajar en scripts incompletos o inválidos. Incluso si escribe sus scripts sin errores, tal vez los escriba de manera inconsistente, es poco probable que el script sea válido durante todo el proceso de desarrollo. Por ejemplo, primero escribo "SELECCIONAR DESDE", después de lo cual me complacerá ver la lista de tablas disponibles. Cuando selecciono una tabla, reorganizaré el carro para SELECCIONAR, presionar la barra espaciadora y esperar la lista de columnas de esta tabla en particular. Este es un ejemplo muy simple, pero muestra que el analizador que proporciona la finalización del código en el IDE no puede bloquearse con la excepción de encontrar un script no válido. Tuvimos que idear muchos trucos para asegurarnos de que la información sobre herramientas funciona correctamente en muchos de estos escenarios,pero los usuarios aún envían diferentes escenarios para trabajar con scripts sin terminar, lo que significa que tenemos que idear nuevos trucos.

Guerras predicadas

Al analizar el código, a veces hay situaciones en las que la siguiente palabra no deja en claro cuál de las dos alternativas elegir. A veces es suficiente mirar por adelantado un número estrictamente definido de palabras y definitivamente puedes elegir una alternativa. El mecanismo para resolver este tipo de inexactitud se llama ANTLR anticipado. El método del analizador en este caso se construye como una cadena incrustada de ifs, cada uno de los cuales se ve una palabra más. A continuación se muestra un ejemplo de una gramática que genera incertidumbre de este tipo.

rule1:
    'a' rule2 | rule3
    ;

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

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

En el medio de la regla 1, después de haber pasado el token 'a', el analizador tendrá que mirar 2 tokens por delante para elegir qué regla seguir. Una vez más, esta verificación se realizará dentro de la regla. Esta gramática se puede reescribir para que esta búsqueda anticipada no exista, desafortunadamente la estructura a menudo sufre de tales optimizaciones, y la ganancia de rendimiento no es relativamente alta.

Existen mecanismos más complejos para resolver incertidumbres más complejas. Uno de ellos es el mecanismo de predicado de sintaxis (sincronizado) en ANTLR3.

Él viene al rescate en aquellos casos en que, por ejemplo, la finalización opcional de una cláusula se cruza con el comienzo de la siguiente opción opcional. El predicado, en términos ANTLR3, es el método generado, que hace un pasaje virtual a través del texto de acuerdo con una de las alternativas y, si tiene éxito, devuelve verdadero, esta finalización del predicado se llama exitosa. El pase virtual también se denomina pase de retroceso. Si el predicado funcionó con éxito, se realiza un pase real. Esto se convierte en un problema cuando otro predicado comienza dentro de un predicado, luego una sección puede atravesarse cien mil veces.

Considere un ejemplo simplificado. Hay 3 puntos de incertidumbre (A, B, C).

El analizador ingresa A, recuerda la posición en el texto, comienza un pasaje virtual del 1er nivel.
B, , 2- .
C, , 3- .
3- , 2 .
2 , 1 B .
, A, B .

Por lo tanto, todas las verificaciones dentro de C se realizarán 4 veces, B - 3 veces, A - 2 veces. Pero, ¿qué pasa si la alternativa adecuada es la segunda o la tercera en la lista? Luego, en alguna etapa de uno de los predicados, fallará, la posición en el texto retrocederá y otro predicado comenzará a ejecutarse.

Analizando repetidamente la causa del congelamiento de la aplicación, nos encontramos con casos en los que la "cola" sincronizada se ejecutó varios miles de veces. Los sincronizados son especialmente problemáticos en las reglas recursivas. Desafortunadamente, por su naturaleza, SQL es recursivo, que es al menos la capacidad de usar una subconsulta en casi todas partes. A veces, con la ayuda de varios trucos y trucos, resulta que resulta la regla para que el predicado desaparezca.

Obviamente, sincronizado tiene un efecto negativo en el rendimiento. En algún momento, era necesario poner a su población bajo estricto control. El único problema es que al escribir código gramatical, la apariencia de sincronizado puede no ser obvia. Además, a veces un cambio en una regla lleva a la aparición de un predicado en otra. Esto no se puede controlar manualmente. Para controlar el número de predicados, escribimos un simple regular, que fue llamado por una tarea especial de MsBuild. Si el número de predicados era diferente del número especificado en un archivo separado, Task interrumpió el ensamblado e informó un error. Al ver tal error, el desarrollador tuvo que volver a escribir el código de la regla varias veces, tratando de deshacerse de predicados innecesarios, posiblemente involucrando a otros desarrolladores en el problema. Si un predicado es inevitable,entonces el desarrollador actualiza el número de predicados en el archivo correspondiente. Un cambio en este archivo llama más la atención sobre la revisión.

En casos raros, incluso escribimos nuestros propios predicados en C # para evitar los que genera ANTLR. Afortunadamente, dicho mecanismo también existe.

Soluciones de bicicleta geniales

Herencia de gramática

Después del anuncio de cualquier cambio en cada uno de los DBMS que admitimos, nuestro trabajo para apoyarlos comienza. Casi siempre, el punto de partida para esto es admitir construcciones sintácticas en la gramática. Para cada dialecto SQL, escribimos nuestra propia gramática, esto genera cierta repetición del código, pero en última instancia es más fácil que buscar un común entre ellos. Hace solo un par de años, MySQL y MariaDB eran muy similares, escribir gramáticas separadas no era práctico. Debido a esas pocas construcciones que estaban en MariaDB, pero no en MySQL, admitimos en la gramática de MySQL. Este fue un momento desagradable: para el usuario de MySQL, podríamos sugerir construcciones que no serían válidas. En los últimos años, MariaDB y MySQL se han vuelto muy divergentes en términos de sintaxis y más. Se hizo evidenteque está mal admitir dos idiomas diferentes dentro de la misma gramática.

Una posible solución podría ser una copia completa de la gramática, después de lo cual cada una se admite por separado. Como resultado de una larga discusión, tomamos una decisión audaz. Estoy muy contento de que no hayamos copiado el código, cada celda en mí se resistió a esta decisión. Se decidió escribir su propio preprocesador de gramática ANTLR, que implementa el mecanismo de herencia gramatical. Hace algún tiempo, me encontré con una gramática ANTLR3 en el repositorio oficial de las gramáticas ANTLR4. Creo que esta oración necesita leerse varias veces para darse cuenta de la profundidad de la locura.

Al discutir la idea de la herencia, rápidamente nos dimos cuenta de que nos gustaría tener un mecanismo para el polimorfismo. La capacidad en la gramática del heredero no solo para redefinir la regla, sino también para llamar a la base. Además, quiero controlar la posición de la llamada de la regla básica: principio, medio o final. Decidimos que todas las reglas pueden redefinirse, para esto no necesita especificar nada adicional. Para redefinir una regla, es suficiente declarar una regla con el mismo nombre en la gramática sucesora. Después de eso, la regla de la gramática principal estará disponible con un nombre diferente.

ANTLR es una herramienta agradable para el desarrollo mediante el ajuste: hay una extensión para VS, hay ANTLRWorks. Al presentar el mecanismo de herencia, no me gustaría perder esta oportunidad. ¿Pero cómo indicar la gramática básica? Puede llegar a algún tipo de convención para nombrar archivos, pero esto no es del todo obvio. Otra opción podría ser indicar dicha información adicional en un archivo separado, pero incluso ahora, al escribir estas líneas, sentí el hedor de esta solución. El resultado fue una indicación de la gramática básica en la gramática del heredero en el formato de un comentario ANTLR. Todas las herramientas simplemente ignorarán este texto, y podemos extraer fácilmente el código que nos interesa.

Se han formado los requisitos, es hora de implementarlos. Escribimos la Tarea MsBuild, que se incorporó al sistema general de compilación como una acción previa a la compilación. La tarea realizó el trabajo del preprocesador de gramática ANTLR, generando la gramática resultante de la base y la heredada. La gramática resultante ya ha sido procesada por ANTLR. Si se encontró una regla con el mismo nombre que en el padre en la gramática sucesora, se cambió el nombre de la regla básica: el nombre de la gramática principal se agregó a su nombre después del guión bajo. Por este nombre se le podría contactar en el heredero.

El mecanismo del preprocesador en sí no tomó mucho tiempo, pero junto con la generación del analizador resultó que ralentizó cada reensamblaje del proyecto en 10-20 segundos. En algún momento, esto dejó de satisfacernos. Decidimos pensar en cómo se puede optimizar esto. La solución fue agregar el hash de la suma de todas las gramáticas de las que depende en forma de un comentario al encabezado del archivo del analizador CS. Antes de hacer nada, el preprocesador comparó estos hashes con los hash de los archivos en el disco, y si no difieren, el archivo del analizador se consideró relevante. En la etapa de desarrollo inicial, tuvimos que pisar el rastrillo de analizadores y gramáticas inválidos recopilados por la versión obsoleta del preprocesador más de una vez. Como resultado, la suma hash del ensamblaje con el preprocesador apareció en el comentario del encabezado.

Otro ANTLR de posprocesamiento

En muchos lenguajes de programación, si la palabra es la clave, ya no se puede usar como el nombre del objeto. En SQL, dependiendo del dialecto, de 800 a 3000 palabras clave. La mayoría de ellos están estrechamente relacionados con el área temática, además, no todos se introdujeron de inmediato, por lo que la prohibición de usarlos todos como nombres de objetos habría encontrado una oleada de indignación. SQL introduce el concepto de palabras clave reservadas y no reservadas. No puede nombrar un objeto de la misma manera que una palabra clave reservada (SELECCIONAR, DESDE, etc.) sin citarlo, ya que no es redundante (CONVERSACIÓN, DISPONIBILIDAD, etc.), puede hacerlo. Este comportamiento complica el desarrollo del analizador. En el momento del análisis léxico, el contexto es desconocido, pero el analizador requiere diferentes números para el identificador y la palabra clave. Para resolver este problema, agregamos un postprocesamiento más al analizador ANTLR.El posprocesamiento reemplaza todas las comprobaciones explícitas con un identificador, con una llamada a un método especial. Este método implementa un control más complicado. Si se ingresa un identificador y se espera un identificador adicional, entonces todo está bien, pero si se proporciona una palabra clave no reservada a la entrada, debe verificarse adicionalmente. Una comprobación adicional es que el método se examina en el contexto actual en la búsqueda de ramas, donde esta palabra clave no reservada se puede usar con precisión como palabra clave, y si no hay tales ramas, se puede usar como un identificador.pero si se ingresa una palabra clave no reservada, entonces debe verificarse adicionalmente. Una comprobación adicional es que el método se examina en el contexto actual en la búsqueda de ramas, donde esta palabra clave no reservada se puede usar exactamente como una palabra clave, y si no hay tales ramas, se puede usar como un identificador.pero si se ingresa una palabra clave no reservada, entonces debe verificarse adicionalmente. Una comprobación adicional es que el método se examina en el contexto actual en la búsqueda de ramas, donde esta palabra clave no reservada se puede usar con precisión como palabra clave, y si no hay tales ramas, se puede usar como un identificador.

Estrictamente hablando, este problema solo puede resolverse mediante ANTLR, pero dicha solución no será óptima. Una solución clásica a este problema es crear una regla que enumere todas las palabras clave no reservadas y un token de identificación. Además, siempre que esté permitido usar un identificador, ya no se usa el token identificador del identificador, pero esta es una regla especial. Dicha solución no solo le hace recordar agregar la palabra clave cuando la ingresa, no solo donde se usa, sino también en esta regla especial, también funciona mucho más lentamente.

Errores

Análisis sin árboles

El resultado del analizador, como regla, es un árbol de sintaxis. Un árbol de sintaxis ( abstracto u concreto ) es una estructura de datos que refleja el texto del programa a través del prisma de la gramática formal. Si desea implementar un editor de código con autocompletado para el idioma que se le ocurrió recientemente, después de estudiar el problema, es probable que implemente aproximadamente el siguiente algoritmo:

Analizar texto en el editor. Obtenga el árbol de sintaxis.
Encuentra el nudo debajo del carro. Combínalo con la gramática. Descubra qué palabras clave y tipos de objetos estarán disponibles en ese momento.

En este caso, la gramática se representa convenientemente como un gráfico o una máquina de estados finitos.

Desafortunadamente, al comienzo del desarrollo, el IDE ANTLR existía en su tercera versión. La cuarta versión ha sido reescrita desde cero y es fundamentalmente diferente de la tercera; al pasar el código, el analizador generará automáticamente un árbol de análisis sin una sola línea adicional. En la tercera versión, había un mecanismo por el cual se podía decirle a ANTLR cómo construir un árbol, pero no fue muy agradable usarlo. Además, muchos ejemplos y artículos sobre este tema sugirieron usar el mecanismo de acciones para ejecutar código en el momento en que el analizador pasa la regla. Este mecanismo es increíblemente conveniente y le permite obtener resultados rápidamente. Desafortunadamente, esta solución provocó problemas arquitectónicos importantes con el desarrollo del producto y un aumento en la complejidad de soportar nuevas funcionalidades. El hecho es que en un archivo, en un archivo de gramática,Las acciones comenzaron a acumularse asociadas con una gran cantidad de funcionalidades diferentes, lo que sería bueno distribuir a diferentes ensamblajes. En el futuro, pudimos distribuir los manejadores de acción para diferentes ensamblajes implementando una versión bastante complicada del patrón de notificación de suscriptor, pero las llamadas mismas, con la transmisión de la información necesaria, aún abarrotan nuestra gramática, complican el soporte de nuevas funcionalidades e imponen restricciones serias y desagradables en la arquitectura.complicar el soporte de nuevas funcionalidades e imponer restricciones serias y desagradables en la arquitectura.complicar el soporte de nuevas funcionalidades e imponer restricciones serias y desagradables en la arquitectura.

Pero no todo es tan obvio como parece. El hecho es que ANTLR3 es mucho más rápido que ANTLR4. Según nuestras mediciones, las diferencias son aproximadamente 6 veces. Además, el árbol de sintaxis para los scripts grandes podría ocupar mucho espacio en la RAM, y siempre que tengamos que sobrevivir en el espacio de direcciones de 32 bits de los estudios de Administración de Visual y SqlServer esto puede ser crítico.

Conclusión

Los subtotales pueden ser los siguientes:

ANTLR, una herramienta poderosa para construir analizadores
Su ventaja sobre otros es herramientas, sintaxis conveniente, una gran cantidad de idiomas compatibles
ANTLR4 fue reescrito desde cero e implica trabajar con el analizador diferente de la tercera versión
Siempre hay una manera de obtener un poco más de las bibliotecas de ThirdParty de lo que dan
Lenguaje específico de SQL, crear analizadores no es una tarea fácil
El código de análisis para tareas relacionadas con la creación de un IDE tiene sus propias peculiaridades: debe considerar trabajar en scripts no cifrados o no válidos

¡Nos vemos en la próxima parte!

Complementando SQL. Parte 1. La complejidad del análisis. Historias sobre la finalización del archivo ANTLR