Дополняя SQL. Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником18.05.2020 11:17

Публикую на Хабр оригинал статьи, перевод которой размещен в блоге Codingsight.

Что будет в этой статье?

Более пяти лет работаю в компании, что занимается разработкой линейки IDE для работы с базами данных. Начиная работу над этой статьей я и не представлял как много интересных историй получится вспомнить, потому когда закончил получил более 30 страниц текста. Немного подумав, я сгруппировал истории по тематике, а статью разбил на несколько.

По мере публикации буду добавлять ссылки на следующие части:

Часть 1. Сложности парсинга. Истории о доработке ANTLR напильником
Часть 2. Оптимизация работы со строками и открытия файлов
Часть 3. Жизнь расширений для Visual Studio. Работа с IO. Необычное использование SQL
Часть 4. Работа с исключениями, влияние данных на процесс разработки. Использование ML.NET

За время работы произошло много интересного: мы нашли несколько багов в .NET, оптимизировали некоторые функции во много раз, а некоторые лишь на проценты, что-то делали очень круто и с первого раза, а что-то у нас не получалось даже после нескольких попыток. Моя команда занимается разработкой и поддержкой языковых функций IDE, главная из которых автодополнение кода. Отсюда и название цикла статей. В каждой их частей я буду рассказывать несколько историй: некоторые об успехах, некоторые о неудачах.

В этой части я сосредоточусь на проблемах парсинга SQL, борьбе с этими проблемами и ошибками допущенными в этой борьбе.

Для тех кому интересна лишь часть из этого и просто для удобной навигации содержание статьи:

Содержание

Кто я?

На эту работу я пришел джуном с совсем небольшим опытом. Я, как и многие, пришел в программирование потому что хотел делать игрушки. Несколько даже вполне успешно сделал. О разработке одной даже писал вот здесь. Недавно, кстати, воскресил ее на другом сервере. Была еще дюжина игр, сделанных или заброшенных на разных этапах готовности. Кроме игр, до получения этой работы, я успел выполнить несколько проектов на фрилансе. Самым крупным из них было приложение для социальных сетей представлявшее собой футбольный портал с турнирными таблицами, данными по игрокам и возможностью оповещать пользователей о финальном счете или забитых голах через SMS. Делалось это почти 10 лет назад. Тогда со смартфонами ходили далеко не все, а кто ходил все чаще без интернета или с трижды проклятым EDGE на котором-то и текстовый сайт открыть было не всегда возможно. Так что идея мне казалась годной.

Как-то так выходило, что помимо игр меня еще и тянуло создавать разный тулинг для себя или других разработчиков. Временами он оказывался близким к тому, что чуть позже мне пришлось делать на работе. Например, одним из проектов, что я делал изучая Win32 API была программа подсвечивающая XML код в Rich Edit Control. Кроме этого была возможность выгрузить код с подсветкой в BMP, HTML или модные тогда на разных форумах BB-коды.

Другим проектом, оказавшимся чертовски близким к тому, чем мне довелось заниматься на работе оказалась программа анализирующая код на С/С++ и строящая по нему блок-схему. Блок-схема строго соответствовала требованиям одного преподавателя в университете. Сделана она была топорно, в лоб, с нулевым знанием теории синтаксического анализа, а работала исключительно на моем дрянном характере. Несколько лет спустя, очищая компьютер от старого хлама, я наткнулся на нее и не смог удалить, потому выложил на github ради истории.

Эти эксперименты вкупе с фрилансом дали вполне годный опыт и дали возможность получить работу. Со временем, после пары дюжин пропитанных кровью и слезами ревью я даже начать приносить пользу компании и продукту. Оборачиваясь назад, довольно забавно понимать, что в результате нескольких случайностей я стал заниматься именно тем к чему и так тянуло.

Какие сложности?

Этот блок нужен для погружения читателя в контекст того, чем мы собственно занимаемся.

Десктопная разработка

Возможно это даже и не сложность, ведь это уже очень зрелая сфера в которой не так много неизвестного, библиотеки стабильны, best-practice известны. Эта особенность нашего проекта здесь, потому что я, как и многие другие программисты, падок на новизну, а новизна сейчас вся ушла в web. Были дни, когда во время дождя, я забирался на подоконник, укрывшись пледом, с кружкой какао, и думал о redis, react, highload и распределенных системах, что где-то там прямо сейчас разрабатываются без меня. Другая сторона этой проблемы в том, что и без того непросто описать знакомым разработчикам за пивом какую-то сложность проекта, а когда вы работаете над приложениями, что функционируют по фундаментально разным законам, это становится еще сложнее.

Парсинг SQL и диалектов

Мне и до этой работы доводилось писать небольшие парсеры для разных языков. Какое-то время я вел курсы по .NET. Некоторым группам, в качестве дополнительного задания, в рамках темы «строки», предлагал написать собственный простой парсер JSON. Только вот SQL и его разновидности это далеко ни XML и ни JSON разработанные, чтобы быть одинаково понятными парсерам и людям. Более того, SQL синтаксически сложнее даже чем С/С++, с его множеством накопленных за долгую историю функций. SQL устроен иначе, его пытались сделать похожим на естественный язык, довольно успешно, кстати. В языке несколько тысяч (в зависимости от диалекта) ключевых слов. Часто для того, чтобы отличить одно выражение от другого, нужно подсмотреть на два и более слов (tokens) вперед. Этот подход называется lookahead. Существует классификация парсеров по тому, как далеко они умеют подглядывать вперед: LA (1), LA (2), или LA (*), что означает, что парсер может заглянуть так далеко вперед как это только может потребоваться, чтобы определить правильную ветку. Иногда необязательный конец одной конструкции (clause) внутри одного SQL-statement совпадает с началом другой, тоже необязательной: такие ситуации существенно усложняют парсеры. Воду в огонь подливает T-SQL, в котором точка-с-запятой не является обязательной, а возможное, но не обязательное окончание некоторых SQL-statement может конфликтовать с началом других.

Все еще не верите? Существует механизм описания формальных языков через грамматики. Грамматикой называют код на одном языке, который описывает другой. Из грамматики часто можно сгенерировать парсер с помощью того или иного инструмента. Наиболее известными инструментами и языками описания грамматики являются YACC и ANTLR. Парсеры сгенерированные YACC используются прямо в движках MySQL, MariaDB, PostgreSQL. Можно было попробовать взять их прямо из открытых исходников и на их основе разрабатывать code completion и прочие функции завязанные на анализе SQL. Причем такая реализация получала бы бесплатные в плане разработки обновления, а парсер бы вел себя гарантировано идентично движку базы. Так почему же мы используем ANTLR? Он качественно поддерживает C#/.NET, для работы с ним есть неплохие инструменты, его синтаксис значительно легче читать и писать. Синтаксис ANTLR оказался так удобен, что microsoft, с недавнего времени использует его в официальной документации C#.

Вернемся к моему доказательству сложности SQL, в сравнении с другими языками, по части парсинга. Для этого хочу сравнить размеры грамматик для разных языков доступных публично. В dbForge мы используем свои грамматики, они полнее тех, что доступны публично, но, к сожалению, сильно засорены вставками C# кода для поддержки разных функций, об этом подробнее в параграфе «Синтаксический анализ без деревьев» раздела «Ошибки».

Ниже приведены размеры грамматик для разных языков:

JS — 475 строк парсер + 273 лексер = 748 строк
Java — 615 строк парсер + 211 лексер = 826 строк
C# — 1159 строк парсер + 433 лексер = 1592 строки
С++ — 1933 строки

MySQL — 2515 строк парсер + 1189 лексер = 3704 строки
T-SQL — 4035 строк парсер + 896 лексер = 4931 строка
PL SQL — 6719 строк парсер + 2366 лексер = 9085 строк

В конце некоторых лексеров идет перечисление символов юникод доступных в языке, это бесполезно в оценке сложности языка. Я брал количество строк до начала таких перечислений.

К оценке сложности парсинга языка на основании количества строк в его грамматике могут быть вопросы. Вопросы также могут быть к полноте открытых грамматик в сравнении с реальным синтаксисом языков. Несмотря на это все равно считаю полезным привести эти цифры, так как разброс уж слишком большой.

Это не все, ведь нам нужно не просто распарсить несколько файлов на SQL. Мы ведь делаем IDE, а значит должны работать на неполных или невалидных скриптах. Даже если вы пишете свои скрипты без ошибок, возможно вы их пишете непоследовательно, вряд ли скрипт валиден на протяжении всего процесса его разработки. Я, например, сначала пишу «SELECT FROM», после чего буду рад списку доступных таблиц. Когда выберу таблицу, я переставлю каретку на SELECT, нажму на пробел и буду ждать список колонок из этой конкретной таблицы. Это очень простой пример, но он показывает, что парсер обеспечивающий работу Code Completion в IDE не может падать с исключением встречая невалидный скрипт. Нам пришлось придумать немало трюков, чтобы обеспечить корректную работу подсказки на многих подобных сценариях, но пользователи все еще присылают разные сценарии работы с незаконченными скриптами, а значит нам приходится придумывать новые трюки.

Предикатные войны

При парсинге кода, иногда, случаются такие ситуации, когда по следующему слову непонятно какую из двух альтернатив выбрать. Иногда достаточно подсмотреть на строго определенное количество слов вперед и можно будет однозначно выбрать альтернативу. Механизм разрешения такого рода неточностей называется в ANTLR lookahead. Метод парсера в этом случае строится как вложенная цепочка if-ов, каждый из которых заглядывает на одно слово дальше. Ниже пример грамматики порождающий неопределенность этого вида.

rule1:
    'a' rule2 | rule3
    ;

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

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

В середине rule1, уже пройдя token «a», парсеру придется заглянуть на 2 token«а вперед, чтобы выбрать по какому правилу идти. Еще раз эта проверка будет сделана внутри правила. Эту грамматику можно переписать так, чтобы этого lookahead не было, к сожалению от таких оптимизаций часто страдает структура, а прирост производительности сравнительно не высок.

Для разрешения более сложных неопределенностей существуют более сложные механизмы. Один из них это механизм синтаксических предикатов (synpred) в ANTLR3.

На помощь он приходит в тех случаях, когда, например, не обязательное завершение одной clause пересекается с началом необязательной другой идущей следом. Предикатом, в терминах ANTLR3, называют сгенерированный метод, что совершает виртуальный проход по тексту в соответствии с одной из альтернатив и в случае успеха возвращает истину, такое завершение предиката называют успешным. Виртуальный проход еще называют проход в режиме backtracking. Если предикат отработал успешно, то совершается реальный проход. Проблемой это становится тогда, когда внутри одного предиката начинается другой, тогда один участок может быть пройден и сотню и тысячу раз.

Рассмотрим упрощенный пример. Есть 3 точки неопределенности (A, B, C).

Парсер входит в A, запоминает положение в тексте, начинает виртуальный проход 1-го уровня.
Парсер входит в B, запоминает положение в тексте, начинает виртуальный проход 2-го уровня.
Парсер входит в C, запоминает положение в тексте, начинает виртуальный проход 3-го уровня.
Парсер успешно завершает виртуальный проход 3-го уровня, возвращается на 2й и проходит С заново.
Парсер успешно завершает виртуальный проход 2 го уровня, возвращается на 1й и проходит B и С заново.
Парсер успешно завершает виртуальный проход, возвращается и совершает реальный проход по A, B и С.

Таким образом все проверки внутри C будут выполнены 4 раза, B — 3 раза, A — 2 раза. А что если подходящая альтернатива вторая или третья в списке? Тогда на каком-то из этапов какой-то из предикатов завершиться неудачей, положение в тексте откатится и начнет выполнение другой предикат.

Неоднократно разбирая причину зависания приложения мы натыкались на случаи, когда «хвост» synpred был выполнен несколько тысяч раз. Synpred«ы особенно проблематичны в рекурсивных правилах. К сожалению, по своей природе, SQL рекурсивен, чего стоит хотя бы возможность использовать подзапрос почти везде. Иногда с помощью разных трюков и ухищрений получается вывернуть правило так, чтобы предикат ушел.

Очевидно, что synpred имеет негативное влияние на производительность. На каком-то этапе пришлось поставить их популяцию под четкий контроль. Проблема только в том, что при написании кода грамматики появление synpred может быть неочевидным. Более того иногда изменение одного правила приводит к появлению предиката в другом. Это невозможно контролировать вручную. Для контроля численности предикатов мы написали нехитрую регулярку, что вызывалась специальным MsBuild Task«ом. Если число предикатов отличалось от числа указанного в отдельном файле, то Task обрывал сборку и сообщал об ошибке. Видя такую ошибку, разработчик должен был несколько раз переписать код правила, пытаясь избавится от лишних предикатов, возможно, привлечь к проблеме других разработчиков. Если появление предиката неизбежно, то разработчик обновляет количество предикатов в соответствующем файле. Изменение в этом файле привлекают дополнительное внимание на ревью.

В редких случаях, мы даже писали собственные предикаты на C#, чтобы обойти те, что генерирует ANTLR. К счастью, такой механизм тоже есть.

Крутые велосипеды решения

Наследование грамматик

После анонса любых изменений в каждой из поддерживаемых нами СУБД начинается наша работа по их поддержке. Почти всегда отправной точкой в этом будет поддержка синтаксических конструкций в грамматике. Для каждого диалекта SQL мы пишем собственную грамматику, это порождает некоторое повторение кода, но в конечном счете это проще, чем искать общее между ними. Еще пару лет назад MySQL и MariaDB были очень похожи, написание отдельных грамматик было нецелесообразно. Потому те немногие конструкции, что были в MariaDB, но не было в MySQL мы поддерживали в грамматике MySQL. В этом был неприятный момент: для пользователя MySQL мы могли подсказать конструкции, что были бы не валидными. В последние года MariaDB и MySQL стали сильно расходиться с точки зрения синтаксиса и не только. Стало очевидным, что неправильно поддерживать два разных языка в рамках одной грамматики.

Возможным решением могло бы стать полное копирование грамматики, после чего поддержка каждой как отдельно. В результате длительного обсуждение, мы пошли на смелое решение. Я очень рад, что мы не стали копировать код, каждая клеточка во мне сопротивлялась этому решению. Было решено написать свой препроцессор ANTLR грамматик, реализующий механизм наследования грамматик. Еще какое-то время назад, мне на глаза в официальном репозитории ANTLR4 грамматик попалась грамматика ANTLR3. Думаю это предложение нужно прочитать несколько раз, чтобы осознать глубину безумия.

Обсуждая идею наследование мы быстро поняли, что нам хотелось бы иметь и механизм для полиморфизма. Возможность в грамматике наследнике не только переопределять правило, но и вызывать базовое. Более того хочется контролировать положение вызова базового правила: начало, середина или конец. Мы приняли решение, что все правила можно переопределять, для этого не нужно указывать ничего дополнительно. Для того чтобы переопределить правило достаточно объявить в грамматике-наследнике правило с таким же именем. После этого правило из родительской грамматики будет доступно под другим именем.

Приятным в разработке инструментом ANTLR делает тулинг — есть расширение для VS, есть ANTLRWorks. Внедряя механизм наследования не хотелось бы терять эту возможность. Только как тогда указать базовую грамматику? Можно придумать какую-то конвенцию по именованию файлов, но это уж совсем не очевидно. Еще одним вариантом могло быть указание такой дополнительной информации в отдельном файле, но даже сейчас, набирая эти строки, я почувствовал вонь этого решения. Выходом стало указание базовой грамматики, в грамматике наследника в формате ANTLR-комментария. Все инструменты просто проигнорируют этот текст, а мы без проблем сможем вытянуть интересующий нас код.

Требования были сформированы, настало время их реализовывать. Мы написали MsBuild Task, который был встроен в общую систему сборки как pre-build-action. Task выполнял работу препроцессора ANTLR грамматики, генерируя результирующую грамматику из базовой и наследуемой. Результирующая грамматика уже обрабатывалась самим ANTLR. Если в грамматике-наследнике встречалось правило с тем же именем, что и в родительской, базовое правило переименовывалось: к его имени после нижнего подчеркивания добавлялось имя родительской грамматики. По такому имени к нему можно было обратиться в наследнике.

Сам механизм работы препроцессора не занимал много времени, но вместе с генерацией парсера получалось, что это на 10–20 секунд замедляло каждую пересборку проекта. В какой-то момент это перестало нас устраивать. Мы решили подумать как это можно оптимизировать. Выходом стало добавление в заголовок CS файла парсера хеш суммы всех грамматик от которых он зависит в виде комментария. Препроцессор перед тем как что-то делать сравнивал эти хеши с хешами файлов, лежащих на диске и если они не отличаются, то файл парсера считался актуальным. На этапе начальной разработки нам пришлось ни один раз наступить на грабли невалидных парсеров и грамматик собранных устаревшей версией препроцессора. В итоге в заглавном комментарии появилась и хеш-сумма сборки с препроцессором.

Еще один постпроцессинг ANTLR

Во многих языках программирования, если слово является ключевым, то использовать его в качестве имени объекта уже нельзя. В SQL, в зависимости от диалекта, от 800 до 3000 ключевых слов. Большинство из них тесно связаны с предметной областью, к тому же не все вводились сразу, поэтому запрет на использования их всех в качестве имен объектов встретил бы шквал негодования. В SQL вводится понятие резервированных и не резервированных ключевых слов. Нельзя назвать объект так же как резервированное ключевое слово (SELECT, FROM etc) не квотируя его, как не резервированное (CONVERSATION, AVAILABILITY etc) — можно. Такое поведение усложняет разработку парсера. На момент лексического анализа контекст неизвестен, но парсер требует разные номера для идентификатора и ключевого слова. Для решения этой проблемы мы добавили еще один постпроцессинг к ANTLR парсеру. Постпроцессинг заменяет все явные проверки на идентификатор, на вызов специального метода. В этом методе реализована более хитрая проверка. Если на вход подан идентификатор и дальше ожидается идентификатор, то все отлично, но если на вход подается нерезервированное ключевое слово, то его нужно дополнительно проверить. Дополнительная проверка заключается в том, что метод осматривается в текущем контексте в поиске веток, где это нерезервированное ключевое слово может использоваться именно как ключевое слово и если таких веток нет, значит здесь оно может быть применено как идентификатор.

Строго говоря, эту проблему можно решить исключительно средствами ANTLR, но такое решение не будет оптимальным. Классическим решением этой проблемы считается создание правила в котором перечисляются все нерезервированные ключевые слова и лексема идентификатор. Далее везде где допустимо использование идентификатора используется уже не лексема идентификатора, а это специальное правило. Такое решение мало того, что заставляет не забывать разработчика дописывать ключевое слово при его введении не только там, где оно используется, а еще и в этом специальном правиле, так еще и работает значительно медленнее.

Ошибки

Синтаксический анализ без деревьев

Результат работы парсера, как правило — синтаксическое дерево. Синтаксическое дерево (абстрактное или конкретное) представляет собой структуру данных отражающую текст программы через призму формальной грамматики. Если вы захотите реализовать редактор кода с автодополнением для языка, что недавно придумали, изучив вопрос, вы скорее реализуете примерно следующий алгоритм:

Распарсить текст в редакторе. Получить синтаксическое дерево.
Найти узел под кареткой. Сопоставить его с грамматикой. Узнать какие ключевые слова и типы объектов будут доступны в точке.

Грамматику в этом случае удобно представить в виде графа или конечного автомата.

К сожалению, на момент начала разработки IDE ANTLR существовал в своей третьей версии. Четвертая версия переписана с нуля и кардинально отличается от третьей, по прохождению кода парсером будет автоматически сгенерировано дерево разбора без единой дополнительной строчки. В третьей версии существовал механизм при помощи которого можно было подсказать ANTLR как построить дерево, но пользоваться им было не слишком приятно. Более того, многие примеры и статьи по этой теме предлагали использовать механизм actions для выполнения кода в момент прохождения парсером правила. Этот механизм невероятно удобен и позволяет очень быстро начать получать результаты. К сожалению, это решение привело к большим архитектурным проблемам с развитием продукта и увеличению сложности поддержки новой функциональности. Дело в том, что в одном файле, в файле грамматики, начали скапливаться actions связанные с большим количеством разной функциональности, которые хорошо было бы разнести по разным сборкам. В дальнейшем мы смогли разнести обработчики самих действий по разным сборкам, реализовав довольно хитрый вариант паттерна subscriber-notifier, но сами вызовы, с передачей необходимой информации, все еще загромождают нам грамматику, усложняют поддержку новой функциональности и накладывают серьезные и неприятные ограничения на архитектуру.

Но все не так очевидно, как может показаться. Дело в том, что ANTLR3 работает значительно быстрее ANTLR4. По нашим измерениям отличия примерно в 6 раз. Кроме того, синтаксическое дерево для больших скриптов могло бы занимать много места в оперативной памяти, а до тех пор пока нам приходится выживать в 32 битном адресном пространстве Visual и SqlServer Management студий это может быть критично.

Заключение

Промежуточные итоги могут быть следующими:

ANTLR мощный инструмент для построения парсеров
Его преимущество над другими это инструменты, удобный синтаксис, большое количество поддерживаемых языков
ANTLR4 был переписан с нуля и предполагает отличную от третьей версии работу с парсером
Всегда есть способ взять от ThirdParty библиотек немного больше чем они дают
SQL специфичный язык, построение парсеров для него — непростая задача
Парсинг кода для задач связанных с построением IDE имеет свои особенности: нужно учитывать работу на незакноченных или невалидных скриптах

До встречи в следующей части!