30.10.2025 08:14
vityaman 0 259 Источник

Привет, Хабр! Меня зовут Виктор Смирнов. В Yandex Infrastructure я c недавнего времени занимаюсь фронтендом YQL: транслятором и инструментами разработки.

В этом посте я расскажу про новый модуль автодополнения запросов на YQL, а также продемонстрирую, как он преобразил консольный клиент YDB CLI.

Предыстория

В августе 2024 года я был студентом на направлении «программная инженерия» факультета ПИиКТ (бывшая кафедра ВТ) университета ИТМО. Выбирая тему выпускной квалификационной работы, я отправил письмо по адресу students@ydb.tech со страницы «YDB для студентов» и получил предложение от руководителя разработки клиентских библиотек YDB Алексея Мясникова @asmyasnikov) сделать автодополнение YQL в YDB CLI. Тема для меня очень релевантная, так как я как раз специализируюсь на инструментах разработки.

У YDB, как и у любой уважающей себя СУБД, есть свой консольный клиент — YDB CLI. С его помощью можно выполнять запросы в интерактивном режиме. В то время в приложении практически отсутствовало автодополнение YQL.

Тогда как раз Павел Орлов завершил добавление ANTLR4 в транслятор YQL, что открыло новые возможности для разработки будущего движка автодополнения. Кстати, об этом Павел рассказал в отдельной статье на Хабр.

Перед тем как углубляться в тему автодополнения, я хочу немного рассказать о предметной области.

Введение в YDB и YQL

YDB — это распределённая реляционная СУБД с поддержкой транзакций, разработанная на языке С++. В данной СУБД слои вычислений и хранения разделены, что позволяет независимо их масштабировать. Помимо построчного хранения данных, YDB также поддерживает колоночный формат. Также СУБД поддерживает очереди сообщений и запросы сразу с несколькими источниками данных.

YQL является языком и инфраструктурой для выполнения запросов к системам хранения и обработки данных. Больше о YQL можно узнать из статьи Ивана Блинкова на Хабр и доклада Виталия Стояна на YouTube. Пользователь обычно выражает YQL-запросы при помощи SQL-синтаксиса.

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

$preview = ($str) -> {
    $max_len = 64U;
    $len = IF($max_len > Length($str), Length($str), $max_len);
    RETURN Substring($str, 0U, $len);
};

$directory = 'story/ydb';
$source = directory || '/autocomplete';

SELECT $preview(chapter) AS preview
FROM $source FLATTEN BY (chapter)
WHERE String::Contains(chapter, 'YDB');

Архитектура модуля автодополнения

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

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

Также очень желательно ранжирование списка слов по вероятности использования в заданном контексте. В простейшем случае подойдёт статистика использований.

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

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

Окружение, в котором осуществляется автодополнение, может накладывать некоторые ограничения на используемые технологии. Например, как YDB CLI, так и сервер YDB реализованы на C++, так что, где бы ни запускать код автодополнения — локально или на сервере, всё равно наиболее удобно использовать нативный язык.

Схематично архитектура модуля представлена на рисунке.

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

Локальный анализ

На этапе локального анализа решаются следующие задачи:

  1. Восстановление на некорректном запросе. Например, если пользователь не закрыл строковый литерал.

  2. Лексический анализ запроса. Реализован при помощи сгенерированного ANTLR лексера.

  3. Определение текущей лексемы. Для этого нужно определить границы слов. Например, если перед курсором символ имени, то автодополнять нужно текущее слово, а если перед ним оператор — следующее слово.

  4. Определение типов следующих лексем. На этом этапе мы получим ключевые слова и типы ожидаемых имён. Решение данной задачи уже есть — это библиотека antlr4-c3.

Библиотека antlr4-c3

Библиотека antlr4-c3 позволяет по ATN (представлению ANTLR-грамматики) и тексту получить множество лексем, ожидаемых парсером в заданной позиции курсора. Алгоритм antlr4-c3 описан в посте автора библиотеки — Mike Lischke. Для лучшего понимания алгоритма можно сперва познакомиться с ANTLR, прочитав статьи LL(*): The Foundation of the ANTLR Parser Generator и Adaptive LL(*) Parsing: The Power of Dynamic Analysis.

Для получения кандидатов на автодополнение алгоритм antlr4-c3 обходит граф ATN заданной грамматики, начиная с нулевого индекса списка лексем, увеличивая индекс при посещении переходов, соответствующим лексемам, пока не достигает курсора.

Пусть позиция курсора была достигнута в состоянии S графа ATN, тогда запускается процедура поиска следующих за состоянием S лексем. Данная процедура запускается рекурсивно при проходе через стрелки графа, соответствующие продукциям, предикатам, epsilon-стрелкам, а на стрелках, «поглощающих» лексемы, фиксируются кандидаты.

Благодаря тому, что antlr4-c3 в процессе обхода ATN поддерживает состояние стека вызовов, по достижении курсора можно вернуть его пользователю для дальнейшего анализа. Например, можно сконфигурировать модуль так, чтобы он возвращал эти стеки вызовов синтаксического анализатора, содержащие заданные клиентом правила вывода. Это используется для определения типа идентификатора, например имени таблицы или функции, когда одного типа лексемы недостаточно.

Глобальный анализ

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

  1. Мутация запроса. Из-за того, что в SQL ключевые слова могут использоваться в качестве имён, могут получаться не совсем желаемые деревья разбора, например вход SELECT x.| FROM table можно проинтерпретировать как SELECT x.FROM table. Тут применяется грязный хак — вставка после курсора некоторого символа: SELECT x._ FROM table.

  2. Построение дерева разбора запроса. Реализовано при помощи сгенерированного ANTLR парсера.

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

  4. Вывод схемы таблицы с учётом подзапросов, JOIN-ов и проекций, а также другие анализы.

Хранилище имён

После обоих анализов мы знаем не только требуемые типы имён, но и, например, пути до таблиц с колонками. Теперь можно сформировать запрос к хранилищу имён, а оно в свою очередь должно:

  1. Фильтровать кандидатов по содержимому текущей лексемы. Простым решением является хранение имён в отсортированных массивах и получение отрезка совпадающих по префиксу имён при помощи бинарного поиска.

  2. Сортировать кандидатов по релевантности. Простое решение — использование частоты употребления слов.

  3. Кешировать результаты. Наивно возвращать результаты из локального хранилища, асинхронно пополняя его свежими данными по запросу.

Результаты

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

Отдельные благодарности Виталию Стояну за дельные замечания и координацию разработки, а также Николаю Перфилову и Алексею Мясникову за поддержку внедрения решения в YDB CLI.

Заключение

Таким был подход к реализации автодополнения языка на основе технологии ANTLR на примере YQL. Если вы используете YQL и заинтересованы в развитии автодополнения в используемых вами средах разработки, дайте нам знать — пишите и голосуйте за актуальные комментарии к данному посту. При особом желании можете добавить новую функциональность в движок автодополнения самостоятельно — весь код доступен в репозитории на GitHub. Так же буду рад вашим вопросам на тему автодополнения кода, давайте обсуждать.

Комментарии (0)