[Перевод] Как устроен языковой сервер21.02.2024 16:00

91b300d7ba35d1130732cb457dfa6c4b

В этом посте я хочу прокомментировать один любопытный комментарий из базы кода rust-analyzer. Вот этот комментарий.

Здесь описан интересный рекурсивный алгоритм, неоднократно встречающийся в разных аспектах программирования языковых серверов. Я видел реализации такого алгоритма на Kotlin и C#, а затем сам реализовал его на Rust.

Вот, казалось бы, рандомная подборка возможностей IDE:

  • Переход к определению
  • Завершение кода
  • Прогон теста на курсоре
  • Извлечение переменной


Что общего между ними? Все эти возможности относятся к актуальному положению курсора! В данном случае вводом служит не только состояние кода в конкретный момент времени, но и конкретное расположение исходников проекта, например src/main.rs:90:2.

При реализации каждой из вышеперечисленных возможностей языковой сервер первым делом должен «понять», что (в семантическом смысле) находится в базе кода по указанному смещению. Может быть, там оператор, например, +? Или имя, например, foo? Если это имя, то в каком контексте используется это имя — определяет ли оно сущность под названием foo или ссылается на ранее существовавший объект? Если это ссылка, то на какой объект она указывает? Каков её тип?

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

fn node_at_offset(node: SyntaxNode, offset: u32) -> SyntaxNode {
    assert!(node.text_range().contains(offset));
    node.children()
        .find(|it| it.text_range().contains(offset))
        .map(|it| node_at_offset(it, offset))
        .unwrap_or(node)
}


Но в самом синтаксическом дереве нет достаточной информации, которая позволяла бы управлять возможностями IDE. Требуется семантический анализ.

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

Традиционные компиляторы прикрепляют к семантическим элементам информацию о диапазоне (span) исходного кода, что может выглядеть так: 

struct Span {
    file: PathBuf,
    line: u32,
    column: u32,
}

struct LocalVariable {
    name: InternedString,
    mutability: Mutability,
    ty: Type,
    span: Span
}


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

Такой подход работает, но у него есть два недостатка.

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

Второй недостаток более философский. При использовании текстовых диапазонов стирается информация о синтаксических деревьях, на которых основаны эти диапазоны. Переменная LocalVariable не происходит из конкретного диапазона (span) текста, она создаётся на основе определённого узла в конкретном синтаксическом дереве. При реализации таких возможностей как «переход к определению», где требуется перейти от синтаксиса к семантике, удобно пользоваться аппроксимацией, она для этого достаточно хороша. Но при рефакторинге зачастую бывает удобно двигаться в противоположном направлении — от семантики к синтаксису. Чтобы изменить перечисление кортежей на перечисление записей, языковой сервер должен найти все включения данного перечисления в семантической модели, но после этого потребуется изменить семантическое дерево. А перейти от Span к SyntaxNode уже не так просто: разные синтаксические узлы могут относиться к одному и тому же диапазону!

Например, foo — это:

  • Токен имени
  • Ссылка
  • Тривиальный путь (foo: bar)
  • Выражение пути
PATH_EXPR@20..23
  PATH@20..23
    PATH_SEGMENT@20..23
      NAME_REF@20..23
        IDENT@20..23 "foo"


Итеративный рекурсивный анализ


Как же в таком случае языковому серверу удаётся отображать синтаксические узлы на соответствующие семантические элементы — и при этом такое отображение получается точным, и вычислять его можно лениво?

Во-первых, каждый семантический элемент получает метод source_syntax, возвращающий исходный синтаксический узел: 

impl LocalVariable {
    pub fn source_syntax(&self) -> SyntaxNode
}


Для разных типов этот метод реализуется по-разному. Иногда уместно сохранить ссылку на синтаксический узел: 

struct LocalVariable {
    source_syntax: SyntaxNodeId,
}

impl LocalVariable {
    pub fn source_syntax(&self) -> SyntaxNode {
        node_id_to_node(self.source_syntax)
    }
}


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

struct LocalVariable {
    parent: Function,
    ordinal: usize
}

impl LocalVariable {
    pub fn source_syntax(&self) -> SyntaxNode {
        let parent_function_syntax = self.parent.source_syntax()
        parent_function_syntax
            .descendants()
            .filter(|it| {
                it.kind == SyntaxNodeKind::LocalVariable
            })
            .nth(self.ordinal)
            .unwrap()
    }
}


Ещё один паттерн — получать эту информацию из сторонней таблицы: 

type SyntaxMapping = HashMap


В синтаксическом анализаторе rust используются все три подхода (в разных местах).
Так решается проблема перехода от семантического элемента к синтаксису, но исходная позиция у нас была прямо противоположная: от такого смещения как main.rs:80:20 мы переходим к SyntaxNode, а после этого нам требуется обнаружить семантический элемент. Фокус в том, чтобы использовать одно и то же решение в обоих направлениях:

Чтобы найти семантический элемент, занимающий определённую синтаксическую позицию, мы сделаем следующее:

1. Посмотрим родительский синтаксический узел.

2. Если родительского узла нет, то данный синтаксический узел соответствует целому файлу, а соответствующий семантический элемент — это модуль.

3. В противном случае рекурсивно подыскиваем семантику для родительского узла.

4. Среди всех потомков данного родительского узла (одного поколения) найдём такой, синтаксис исходного кода в котором соответствует именно тому узлу, с которого мы начали.

На псевдокоде: 

fn semantics_for_syntax(node: SyntaxNode) -> SemanticElement {
    match node.parent() {
        None => module_for_file(node.source_file),
        Some(parent) => {

            // Recursive call
            let parent_semantics = semantics_for_syntax(parent);

            for sibling in parent_semantics.children() {
                if sibling.source_syntax() == node {
                    return sibling
                }
            }
        }
    }
}


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

Рассмотрим следующий пример: 

struct RangeIter {
    lo: u32,
    hi: u32,
}

impl Iterator for RangeIter {
    type Item = u32;

    fn next(&mut RangeIter) -> Item {
                            //  ^ Cursor here

    }
}

impl RangeIter {
    ...
}


Начиная с синтаксического узла Item, языковой сервер будет рассматривать:

  • Возвращаемый тип функции next,
  • Саму эту функцию,
  • Блок impl Iterator,
  • Весь файл.


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

Такая структура «рекурсия с циклом» имеется во многих языковых серверах. В rust-analyzer посмотрите модуль source_to_def со множеством функций, преобразующих синтаксис (ast: типы) в семантику (неквалифицированные типы).

fn type_alias_to_def(
    &mut self,
    src: InFile,
) -> Option {


В Roslyn входной точкой для всей этой машины является функция GetDeclaredType. Понятно, что BaseTypeDeclarationSyntax — это синтаксис, тогда как в возвращаемом типе NamedTypeSymbol содержится семантическая информация. Сначала Roslyn подыскивает семантическую информацию для синтаксического родительского узла GetDeclaredTypeMemberContainer. Затем в GetDeclaredMember он перебирает одноуровневые семантические узлы и находит тот, в котором содержится подходящий текстовый диапазон.

В Kotlin такая входная точка — это findSourceFirDeclarationByExpression. Эта функция начинается с синтаксического узла (KtExpression — это синтаксис, как и во всех узлах Kt), и эта функция возвращает объявление. При помощи getNonLocalContainingOrThisDeclaration можно получить синтаксический контейнер для актуального узла. Затем findSourceNonLocalFirDeclaration получает Fir для этого родительского узла. Наконец, функция findElementIn обходит потомков Fir, чтобы найти тот, в котором находится исходный код, с которого мы и начали работу.

Ограничения


Для тех языков, где такой подход реализован и работает, характерны два общих свойства:

1. Синтаксическая вложенность должна совпадать с семантической. Рассматривать узлы, расположенные на одном уровне с родительским, целесообразно лишь в том случае, если искомый элемент должен быть среди узлов этого уровня.

2. Получить семантический элемент для конкретного файла — тривиальная задача.
На самом деле, второй тезис в Rust не столь бесспорен как в Kotlin или C#! В двух последних языках каждый файл начинается с объявления пакета, которое сразу же монтирует файл ровно в ту точку семантической модели, где он должен стоять.

В Rust файл foo.rs семантически существует лишь в том случае, если какой-то родительский файл включит его при помощи объявления mod foo;! В принципе, автоматически найти родительский файл в Rust невозможно. Как правило, родителем src/bar/foo.rs будет src/bar.rs, но, поскольку существуют атрибуты #[path], переопределяющие заданные по умолчанию настройки, это правило может и не соблюдаться. Поэтому анализатор Rust здесь будет не так ленив, как хотелось бы. При каждом изменении он реконструирует всё дерево модулей для крейта и заглядывает в каждый файл, даже если прямо сейчас в области видимости находится всего один файл.

Вот ещё один интересный пример: 

mod ast {
    generate_ast_from_grammar!("FooLang.grm");
}


Здесь перед нами гипотетический процедурный макрос, считывающий грамматическое определение из внешнего файла и, следует полагать, генерирующий набор типов Rust для абстрактного синтаксического дерева, описываемого данной грамматикой. Можно помечтать об IDE, где, не зная ничего конкретного о .grammar, всё равно можно будет найти варианты использования узлов AST, определённых в этой грамматике, опираясь лишь на информацию о диапазонах из этого процедурного макроса. Теоретически, такой подход должен работать. Когда макрос создаёт деревья токенов Rust, он также может соорудить диапазоны, охватывающие эту точку внутри FooLang.grm, тем самым соединяя исходный код Rust с грамматикой.

Этот подход нарушается именно при ленивом использовании. Когда пользователь вызывает внутри FooLang.grm функцию «найти случаи применения», IDE никак не может знать заранее, что вызов макроса generate_ast_from_grammar!(«FooLang.grm») нужно развернуть! Единственный вариант реализации — предусмотреть, чтобы IDE постоянно заблаговременно разворачивала все макросы.

© Habrahabr.ru