Как я сделал PR на 14К строк в проект YDB будучи студентом

В этой статье я хотел бы рассказать о задаче, решение которой легло в основу моей дипломной работы. В ноябре 2023 года я был студентом Физтеха — учился на базовой кафедре Яндекса, программа обучения которой реализуется совместно с ШАД. Задача заключалась в переводе парсера языка запросов YQL (диалект SQL для YDB и YTsaurus) с ANTLR3 на ANTLR4. Мой наставник в ШАД и руководитель команды разработки клиентских библиотек YDB в Яндексе к. т. н. Алексей Мясников @asmyasnikov отметил её как особо сложную. Но меня это не отпугнуло: из всех тем, предложенных в ШАД, эта показалась самой интересной и близкой мне.

С чего всё началось

Стоит рассказать небольшую предысторию. Эта задача по сути — технический долг и блокер для ряда других задач. Грамматика ANTLR позволяет сгенерировать парсеры на различных языках программирования (ЯП). Актуальные кодогенераторы парсеров на популярных ЯП предоставляются для 4-й версии ANTLR. Например, чтобы поддержать YDB в проекте sqlc (имплементация подхода db‑first), требуется парсер диалекта YQL на Golang. Для реализации автодополнения и подсветки синтаксиса YQL во встроенном интерфейсе YDB требуется парсер YQL на TypeScript. Аналогичная функциональность в YDB CLI требует парсера YQL на С++.

Решение задачи перевода грамматики YQL с ANTLR3 на 4 постоянно откладывалось по разным причинам.

Во‑первых, неочевидно, что её можно решить как‑то быстро и изящно, не затрагивая большую часть кодовой базы YQL, соответственно, сложно прогнозировать сроки.

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

Забегая вперёд, скажу, что задача действительно оказалась непростой: пришлось основательно разобраться в том, как устроен парсинг запроса в YQL, хорошо изучить сборку проекта, покопаться во внутренностях ANTLR3 и ANTLR4, чтобы в итоге встроить использование ANTLR4 как переключаемую функциональность и незаметно осуществить миграцию.

В рамках этой статьи я не буду погружаться в сложные специфические детали, поэтому план такой: сначала обсудим то, как ANTLR позволяет просто и быстро реализовывать парсеры различных языков, на примере SQL, затем опишем основные особенности парсинга YQL и, наконец, поверхностно рассмотрим, каким образом получилось встроить в эту схему ANTLR4.

Парсер SQL from Scratch

В этой части рассмотрим, как можно написать простой парсер SQL‑запросов с помощью ANTLR4. Основная цель — дать некоторое базовое представление о том, что такое парсинг запроса и как его довольно просто реализовать с помощью ANTLR4. Это поможет лучше понять дальнейший текст, в частности, то, как парсинг выглядит в YQL.

Можно сказать, что парсинг, или синтаксический анализ, — это процесс проверки принадлежности последовательности лексем языку некоторой формальной грамматики. Его результат — синтаксическое дерево разбора последовательности в случае, если она принадлежит языку. Здесь есть несколько новых терминов, так что обо всём по порядку.

Лексема (или токен) — единица языка. В каком‑то смысле это буква алфавита, на котором мы определяем язык. Вообще обычно синтаксическому анализу предшествует лексический анализ — преобразование входного текста в последовательность токенов. Например, в случае языка SQL имеет смысл выделить ключевые слова (SELECT, FROM и т. д.) в отдельные сущности, чтобы наш парсер работал с их последовательностью. Рассмотрим пример объявления токенов в ANTLR:

CREATE: 'CREATE';
LPAR: '(';
RPAR: ‘)‘
ID: ('a'..'z' | 'A'..'Z' | '_') ('a'..'z' | 'A'..'Z' | '_' | '0'..'9')*;
NUM: [0-9]+ ('.' [0-9]+)?;
…

Здесь ID — токен для идентификатора таблицы и имён колонок. Он описывается с помощью регулярного выражения — последовательности символов, которая может начинаться с любой буквы или нижнего подчёркивания, а среди остальных символов могут встречаться ещё и цифры. Аналогично NUM задаёт float‑число, которое может быть записано с точкой или без. То есть токен не всегда однозначно соответствует какому‑то фиксированному слову, корректнее думать о токене как некотором классе слов, соответствующих заданному описанию.

Формальная грамматика — набор правил, описывающих синтаксис языка. Неформально каждое правило описывает некоторое выражение, которое может содержаться в тексте на этом языке. Здесь проще всего сразу рассмотреть игрушечный пример грамматики для ANTLR4:

sql_query:
    create_stmt
    | drop_stmt
    | select_stmt 
    | insert_stmt
;
create_stmt: CREATE TABLE ID LPAR table_schema RPAR;
drop_stmt: DROP TABLE ID;
select_stmt: SELECT (expr_list | STAR) (FROM ID)? (WHERE expr)?;

expr_list: expr (COMMA expr)*;
expr:
    NUM
    | ID
    | MINUS expr
    | LPAR expr RPAR
    | expr (MINUS|PLUS) expr
    | expr (STAR|SLASH) expr
    ;

Первое правило описывает глобальную структуру запроса — в данном случае это одно из выражений CREATE, DROP, SELECT, INSERT. Второе правило описывает структуру выражения CREATE: оно начинается с последовательности токенов CREATE и TABLE, а заканчивается описанием схемы таблицы table_schema, заключенной в скобки (токены LPAR и RPAR). В ANTLR токены задаются в верхнем регистре, а правила — в нижнем. Их еще называют нетерминалами грамматики: можно сказать, что они описывают некоторые синтаксические выражения языка.

Синтаксическое дерево разбора (англ. abstract syntax tree AST) — дерево, построенное по входному тексту. Его корень — первый нетерминал грамматики, каждая внутренняя вершина соответствует какому‑то нетерминалу, её дети — правой части правила для этого нетерминала, а листья — токенам (причём значения токенов в порядке обхода дерева слева направо составляют входное слово). Дерево разбора есть только для синтаксически корректных входных текстов, то есть тех, которые принадлежат языку, описываемому грамматикой. Например, AST для запроса SELECT col1 + col2 FROM table:

Синтаксическое дерево представляет особый интерес, ведь именно с его помощью интерпретируется запрос. Обходя дерево и производя нужные действия в зависимости от вида вершины, можно на выходе получить граф, описывающий запрошенное вычисление, оптимизировать его, а затем исполнить его для получения результат запроса. Например, на схеме в вершине expr_list можно передавать выше функцию, принимающую на вход строку таблицы и возвращающую результат нужного выражения над ней. Тогда в вершине select_stmt можно вызвать эту функцию на строках нужной таблицы, полученной из токена ID.

Таким образом, написав необходимую грамматику для ANTLR4, мы сразу получаем возможность её парсить: запуск команды antlr GrammarExample.g4 -o output-folder -Dlanguage=Cpp генерирует код, который запускает парсинг и построение AST. Вообще ANTLR4 предлагает некоторый интерфейс для обхода полученного дерева.

class  ToySqlBaseListener : public ToySqlListener {
public:

  virtual void enterSql_query(ToySqlParser::Sql_queryContext * /*ctx*/) override { }
  virtual void exitSql_query(ToySqlParser::Sql_queryContext * /*ctx*/) override { }

  virtual void enterCreate_stmt(ToySqlParser::Create_stmtContext * /*ctx*/) override { }
  virtual void exitCreate_stmt(ToySqlParser::Create_stmtContext * /*ctx*/) override { }

  virtual void enterDrop_stmt(ToySqlParser::Drop_stmtContext * /*ctx*/) override { }
  virtual void exitDrop_stmt(ToySqlParser::Drop_stmtContext * /*ctx*/) override { }

  virtual void enterSelect_stmt(ToySqlParser::Select_stmtContext * /*ctx*/) override { }
  virtual void exitSelect_stmt(ToySqlParser::Select_stmtContext * /*ctx*/) override { }
…

Однако для моей задачи это не особо актуально, тем более этого интерфейса не было в ANTLR3. Здесь важно понять, что AST позволяет каким‑то образом осуществить интерпретацию запроса. Каким — не важно, в идеале подмена ANTLR3 на ANTLR4 должна поменять лишь то, что происходит на стадии до получения синтаксического дерева. Так мы плавно подходим к следующей части — устройству парсинга в YDB.

Парсинг запросов в YDB

В предыдущей части мы обсудили, что основная цель парсинга — получить абстрактное синтаксическое дерево входного запроса. В YDB для этого использовался ANTLR3, но с некоторыми особенностями. Синтаксический разбор происходит в два этапа: сначала по грамматике генерируется protobuf, описывающий схему AST. Например, для правила sql_query : ( sql_stmt_list | ( PRAGMA ANSI DIGITS ansi_sql_stmt_list ) ); получится схема:

message TRule_sql_query {
    message TAlt1 {
        TRule_sql_stmt_list Rule_sql_stmt_list1 = 1;string Descr = 2;
   }
   message TAlt2 {
        message TBlock1 {
             TToken Token1 = 1;
             TToken Token2 = 2;
             TToken Token3 = 3;
             TRule_ansi_sql_stmt_list Rule_ansi_sql_stmt_list4 = 4;
             string Descr = 5;
        }
        TBlock1 Block1 = 1;
        string Descr = 2;
    }
    oneof Alt {
        TAlt1 Alt_sql_query1 = 1;
        TAlt2 Alt_sql_query2 = 2;
    }
}

То есть это описание возможной структуры, которая содержится в вершине для нетерминала sql_query. Далее уже запускается генерация кода на C++, который производит синтаксический анализ запросов, результат которого возвращается в виде protobuf‑сообщения, соответствующего сгенерированной схеме.

На самом деле такой процесс парсинга в каком‑то смысле выбивается из привычного паттерна использования ANTLR: сам инструмент позиционируется именно как парсер‑генератор, то есть штука, которая создаёт код, а не описание типов. Более того, ANTLR3 и ANTLR4 вообще не поддерживают работу с proto‑форматом, и попытки прогуглить это ни к чему не привели. Может показаться, что в YDB используется изменённая версия ANTLR3, но это не совсем так. Спойлер: сам бинарный файл приложения ANTLR3 не изменён, но изменены некоторые метаданные, используемые при исполнении.

И вот наконец в работе над задачей возникла проблема, которая не гуглилась и для которой у меня не было даже примерного направления, куда копать. Даже большинство прочитанных глав в двух основных книгах по ANTLR3 и ANTLR4 не помогли.

Правильным направлением в данном случае оказалась попытка выяснить, как вообще ANTLR генерирует код для разных ЯП. Ответ на этот вопрос потребовал некоторых раскопок во внутренностях обеих версий ANTLR — далее постараюсь сжато и идейно описать механику того, как это происходит.

Но сначала придётся описать алгоритм, который используется в ANTLR для парсинга. Разработчик ANTLR назвал этот алгоритм LL(*). На самом деле это некоторое логичное продолжение идеи более известного LL(k) с динамически подбираемым параметром k, так что рассмотрим для простоты именно его.

В сущности, это довольно интуитивный алгоритм: процесс разбора заключается в последовательном раскрытии правил грамматики, включающих текущий префикс входной последовательности. Решение о раскрытии правила принимается на основе не более чем k следующих символов входа. Причём в случае, когда по k следующим символам нельзя однозначно понять, какое правило раскрывать, грамматика считается неподходящей и её стоит изменить.

Рассмотрим пример для следующего правила из грамматики YQL:

single_source
    : table_ref
    | LPAREN select_stmt RPAREN
    | LPAREN values_stmt RPAREN
;

Представим, что мы прочитали какой‑то префикс входной последовательности токенов и теперь раскрываем это правило. Очевидно, нам было бы недостаточно знания лишь о текущем символе, ведь текущим символом может быть скобка LPAREN. Но, допустим, мы знаем, что select_stmt и values_stmt можно различить по первому токену. Тогда можно написать следующий псевдокод разбора этого правила (и идейно это буквально код, генерируемый ANTLR):

void Parser::single_source() {
    if (lookahead(1) == first(Rules::table_ref)) {
        table_ref();
    } else if (lookahead(1) == Token::LPAREN) {
        matchToken(Token::LPAREN);
        if (lookahead(2) == first(Rules::select_stmt)) {
            select_stmt();
        } else if (lookahead(2) == first(Rules::values_stmt)) {
            values_stmt();
        } else {
            raise Exception;
        }
        matchToken(Token::RPAREN);
    } else {
        raise Exception;
    }
}

Отметим, что, во‑первых, по коду легко восстановить само правило, которое он разбирает, а во‑вторых, чтобы написать по правилу такой код, нужно просто знать, на сколько символов вперёд смотреть, а сама структура кода следует из альтернатив в правой части правила. На самом деле ANTLR3 и 4 где‑то у себя под капотом высчитывают всё, что нужно для воссоздания логики парсинга правила, а код, реализующий логику, описывается в специальных StringTemplate. Таким образом, генерируемый инструментом код настраивается через смену файла.stg с шаблонами.

В YDB для генерации protobuf в своё время был написан специальный файл.stg, в котором в определённых шаблонах вместо кода для правила была описана именно protobuf‑схема. При подкладывании этого файла по определённому пути относительно папки, из которой запускается бинарь ANTLR, он подменит оригинальный.stg, и получится нужная генерация. Для генерации кода самого парсера, который возвращает AST в соответствии с protobuf‑схемой, был также изменён оригинальный Cpp.stg, используемый для генерации кода на C++.

Таким образом, задача свелась к тому, чтобы задать файл.stg для ANTLR4, который бы генерировал ровно такую же protobuf‑схему, а также модифицировать Cpp.stg в соответствии с этой схемой. Основная сложность состояла в том, что шаблоны в ANTLR4 совсем не такие, как в ANTLR3, и изначально было вообще не очевидно, что получится сделать ту же схему. Но в итоге за счёт тщательного изучения иерархии шаблонов и нескольких правок в грамматике удалось добиться идентичной генерации.

Писать об этом подробнее смысла не вижу, так как информация крайне специфичная и вряд ли будет полезной. Однако хочется сказать, что изначально показавшееся странным решение генерировать protobuf‑схему в итоге позволило практически безболезненно осуществить миграцию. По сути, это победа. Осталось только внедрить, не сломав текущую функциональность, но это уже дело техники: настроить сборку и пройти тесты.

Аккуратная миграция

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

Самая очевидная проблема возникает из‑за разных интерфейсов, которые предоставляют сгенерированные разными версиями инструментов парсеры. Бороться с этим можно следующим образом: для всех классов, которые пользуются сгенерированным кодом, написать специализацию, которая будет вызываться для кода, произведённого ANTLR4. Рассмотрим на следующем примере:

template <typename TLexer, bool IsAntlr4 = IsDerivedFromLexer<TLexer>::value>
class TLexerTokensCollector;
// antlr3 version
template <typename TLexer>


class TLexerTokensCollector<TLexer, false> {
...
    TLexerTokensCollector(...) ... {}
...

}
// antlr4 version
template <typename TLexer>
class TLexerTokensCollector<TLexer, true> {
...
    TLexerTokensCollector(...) ... {}


... }

В данном случае выберется нужная версия TLexerTokensCollector в зависимости от её шаблонного параметра TLexer. Причём IsDerivedFromLexer определяется так:

template<typename T>

struct IsDerivedFromLexer
{
    static constexpr bool value = std::is_base_of<antlr4::Lexer, T>::value;
};

Ещё один интересный случай возник по ходу внедрения в тесты. Проблема оказалась в правиле для токена:

fragment ID_QUOTED_CORE: '``' | '\`' | ~'`';
ID_QUOTED: BACKTICK ID_QUOTED_CORE* BACKTICK;

ID_QUOTED — это идентификатор, заключённый в бэктики. Проблема возникла в запросе:

--!antlr4_parser
select
    1 as `Schema has `RealCost``
    -- foo`bar

В данном случае стадия лексического анализа ANTLR4 выделила выражение Schema has `RealCost`` -- foo в отдельный токен. На самом деле, если разобраться, то всё корректно:

Schema has -> (~'`')*
` -> '\`'
RealCost -> (~'`')*
`` -> '``'
n    -- foo -> (~'`')*

Стоит учитывать, что матчинг регулярных выражений в ANTLR по умолчанию «жадный» (то есть движок пытается сматчить последовательности символов как можно большей длины), поэтому он пошёл до последнего бэктика. Возникает вопрос к ANTLR3: почему в нём ID_QUOTED получает значение Schema has `RealCost`?

Как бы там ни было, корректное исправление правила в данном случае такое:

fragment ID_QUOTED_CORE: '\'. | '``' | ~('`' | '\');

В сущности это логично: в бэктиках может быть либо экранированный символ, либо двойные бэктики, либо что-то ещё.

Остальные изменения не столь содержательны, и их легко решить по выводу ошибки сборки. Здесь сложно дать какой-то универсальный совет. Для отладки сборки, конечно же, помогут общие навыки настройки проектов на C++, а также работы с CMake илиYaMake.

Заключение

Таким образом, задача действительно оказалась довольно сложной: потребовалось поковыряться в устройстве ANTLR и YDB, но тем не менее проблему удалось довольно изящно решить и аккуратно внедрить фичу, не ломая логику огромного проекта. Так что вышел довольно выгодный для всех сторон обмен: мне — интересный опыт и диплом, моему ментору из ШАД — решение долгого и безнадёжной задачи и первый действительно большой коммит в YDB от внешнего опенсорс‑контрибьютора. Правда из 14к строк большинство пришлось не на код и логику, а на новые файлы отредактированной грамматики, тестов,.stg‑шаблонов и скриптов сборки. Коммит получился большой скорее по глобальности своих изменений.

Полезные ссылки

• Книги про ANTLR3 и 4:

  • The Definitive ANTLR Reference

  • The Definitive ANTLR 4 Reference

• StringTemplalte Engine (кодогенерация с.stg)