Привет, Хабр! Меня зовут Ольга Лукьянова, я работаю в Yandex Infrastructure, в команде, которая делает системы, сервисы и инструменты для разработчиков. Недавно Яндекс анонсировал новый продукт SourceCraft, который уже собирает вокруг себя сообщество. Последний год я руковожу группой навигации по коду этого проекта.

Мои коллеги на конференциях уже рассказывали про планы развития SourceCraft — платформы от Яндекса для создания исходного кода, управления версиями, тестирования, сборки, развёртывания и сопровождения программных продуктов. А также показывали первый доступный компонент — интеллектуальный помощник для работы с кодом Yandex Code Assistant.
Я открою чуть больше деталей про возможности навигации в нашей платформе, которые появятся в публичном доступе в следующем году и помогут разработчикам не переключаться в IDE, а решать наиболее типовые задачи в одном интерфейсе. В статье — рассказ о том, как мы искали способы добавить функциональность навигации по коду при ревью пул-реквестов и каких результатов уже достигли. 

Немного про платформы для разработки и задачи навигации

Платформы для совместной разработки (GitHub, GitLab, BitBucket, Azure DevOps и др.) предлагают разный уровень удобства навигации по кодовой базе. Все платформы подсвечивают синтаксис и предоставляют поиск по коду. Только некоторые из них позволяют найти использования функции или перейти к определению. А ведь это ровна та функциональность, к которой разработчики привыкли при работе с кодом в IDE. Мы считаем очень важным предоставить разработчикам удобную функциональность go to declaration, find usages, quick info при просмотре кода и ревью PR в веб-сервисе.
Вот как это выглядит сейчас:

Слева видим дерево проекта, справа всплывает подсказка с информацией про символ, есть возможность перейти к декларации или найти использования.

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

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

Вот список требований к навигации, который сформировался у нас на старте:

• Быстро работает, но не любой ценой. Здесь у нас есть три взаимосвязанных параметра, которые могут перетягивать друг друга: скорость индексации, скорость перехода к декларации и потребление памяти. Мы хотим, чтобы отработка go to declaration происходила моментально, а если пришёл новый коммит, ответ хочется получать в разумное время (не через 20 минут), поэтому скорость индексации тоже важна. Потребление памяти сильно влияет на первые два параметра, поэтому нам важна и компактность индексов.

• Есть только sources: в репозитории лежат исходники, там нет библиотек, так что важнее сделать навигацию именно по sources. С библиотеками тоже бы хотелось, но это задача с двумя звездочками, и решать мы её будем отдельно.

• Легко расширяется на другие языки программирования: нам важно сразу поддержать около 10 популярных ЯП, а не писать 2 года платформу с идеальной поддержкой одного языка.

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

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

Резолв (Resolve) — алгоритм нахождения по использованию символа в коде его декларации.

И если рассматривать весь спектр возможных решений, здесь возможны два крайних полюса на континууме.

Решение 1. Использовать компилятор

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

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

Когда мы сделали это и получили индекс для одного коммита, нам придётся повторить эту же последовательность действий для следующего коммита. Так мы постепенно получим набор снапшотов (S1, S2, …Sn) с Resolve‑индексами для каждого коммита. Довольно громоздко по памяти. Отдельная задачка дедупликации данных индекса — можно заметить, что большая часть данных каждого снапшота будет повторяться (изменения небольшие).

Итого, для этого решения нам нужно:

• Собрать и построить окружение проекта.

• Вытащить из компилятора информацию.

• Реализовать под каждый язык отдельно.

• Дедуплицировать и хранить все снапшоты индексов для каждого коммита.

Звучит сложно, но есть и плюсы.

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

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

Решение 2. Текстовый индекс

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

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

Как реализовано технически. Для реализации подхода нужен текстовый индекс, а также нужны индексы деклараций и использований для каждого файла. Такие индексы per file позволяют классифицировать найденные через текстовый поиск использования: выделить из них декларации и использования.

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

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

SourceCraft ver.0

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

В качестве текстового индекса мы использовали сервис поиска по коду от Яндекса CodeSearch: оптимизированный под большие объёмы данных компактный текстовый индекс на основе триграмм. Оставалось реализовать индексы деклараций и использований для каждого файла.

Будем искать декларацию для Repository.

Для этого:

• По текстовому индексу находим файлы, в которых встретилось искомое слово.

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

В результате все текстовые вхождения классифицированы на декларации и использования. Соответственно функциональность go to declaration найдёт всё и вернёт только декларации. А Find Usages вернёт и декларации, и использования. Получился алгоритм, похожий на подход GitHub.

Теперь посмотрим внимательнее, что внутри каждого индекса, необходимого для этого алгоритма.

Индекс коммитов

Для реализации нам понадобится ещё индекс коммитов. Обсудим, как он устроен, а затем продемонстрируем, как будем его использовать.

Этот индекс хранит информацию об изменениях в каждом коммите, то есть это отображение графа коммитов, представленное в определённом виде.

Как это работает:

• У нас есть хеш нашего коммита (sha1 hash);

• Для каждого хеша коммита мы храним информацию, какие файлы в этом коммите были добавлены/удалены/изменены;

• И для каждого файла ещё храним sha1 hash его содержимого.
  Итого: commitHash → (fileId, kind) [ ], где fileId = (fullFilePath, fileHash)

Индекс коммитов верхнеуровнево выглядит вот так:

Чтобы его построить, заглянем внутрь устройства самого git.

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

Blob — это по сути файл. Он хранит размер файла и его контент.
А tree — по сути папка. В каждом tree хранится таблица его дочерних элементов, они могут быть либо blob, либо tree. Для каждого ребёнка tree содержит хеш контента, короткое имя и дополнительную информацию filemode.

Пусть у нас есть коммит #1, в котором добавили две папки и три файла. И коммит #2, в котором поменяли один файл storage.go. Выглядеть это будет примерно так:

По этим данным нам совсем несложно построить индекс коммитов: достаточно найти, какие файлы поменялись в новом коммите.

Получается такая карта местности, на которую мы дальше можем полагаться при работе с индексами и навигацией.

Теперь пройдёмся по отдельным индексам по коду.

Индексы по коду

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

Виды индексов по коду:

• Прямые — индексы, которые строятся и обновляются per file. Примером будет уже рассмотренный индекс деклараций и использований для конкретного файла. Если в файле что‑то поменялось, нужно просто построить индекс для новой версии файла.

• Обратные — это агрегирующие индексы, собирающие информацию из нескольких файлов. Например, индекс, который для каждого пакета и типа возвращает всех его мемберов, — Member Index.
  
  Эти индексы бывают
  

  • Инкрементальные, когда по изменению в одном файле легко вычислить, что точечно обновить в индексе (примером будет тот самый Member Index).

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

Прямые индексы per commit

Прямые индексы для каждого коммита мы решили держать в key‑value‑хранилище. Для каждого хеша контента файла мы храним его индекс. Как именно мы это делаем:

• Храним индекс в виде массива байтов byte[ ]. В этом массиве сериализованы все индексы по файлу: индекс деклараций, использований.

• Строим на каждую версию файла (точнее на каждый новый хеш контента файла) новый индекс и пишем в KV‑базу.

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

Текстовый индекс

Для текстового поиска традиционно используют несколько решений.

Word index. Хранит для каждого слова в нашем тексте файлы, в которых это слово встретилось (ещё может хранить offset — где слово находится в файле). Это простой индекс, предоставляющий полнотекстовый поиск. Если изменился какой‑то файл, мы должны обновить индекс для всех слов в файле. То есть, при изменении нужно будет пробежаться и обновить довольно большое количество ключей.

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

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

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

Для нашей задачи вообще достаточен Word Index, однако мы остановились на trigram‑индексе, поскольку на платформе явно нужна будет функциональность гибкого поиска по коду всех репозиториев. Ну и созданный в Яндексе CodeSearch основан именно на триграммах.

Давайте дальше разберёмся, как научить trigram-индекс работать для каждого коммита. Вспомним про наш fileID = (fullFilePath, fileHash), который комбинирует полный путь к файлу и хеш его контента. И будем для каждой триграммы записывать fileID, в которых она встретилась. Так мы учитываем все изменённые версии файла. 

Что получается: у нас есть карта коммитов и мы построили для неё Trigram Index.

  

Допустим, мы ищем слово mapp во втором коммите. Делим его на триграммы и получаем map и app. Идём в индекс, пересекаем результаты для map & app и получаем ответ: (#1, sha1), (#3, sha3). Затем мы идём в индекс коммитов, в commit #2 и смотрим, доступен ли в нём file #1 и file #3. Поскольку file #3 модифицирован, третий файл выкидывается из списка ответов, и у нас остаётся только file #1, который доступен в родительском коммите. File #1 будет корректным ответом.

Что получилось в результате MVP

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

Сравним характеристики:

• Решение легко обобщается на новые языки.

• Занимает мало памяти.

• Скорость зависит от скорости триграмм‑индекса (нам повезло, что CodeSearch быстрый).

• Индексируется быстро.

• Очень не ТОЧНЫЙ.

Далее будем уточнять результат, и поговорим о более продвинутых подходах.

SourceCraft ver.1: локальный resolve и эвристики для уточнения результата

Мы заметили, что в коде на Go часто от функции к функции повторяются имена локальных переменных: например постоянно встречается err, и согласно нашему алгоритму для err вы получите все 40 деклараций и 200 использований в куче. Это несложно исправить.

Мы добавили алгоритм локального резолва: что это такое. Если использованию символа в коде соответствует декларация, которая является локальной переменной, то что бы мы ни делали в соседних файлах, resolve для этого использования не изменится. Такой resolve мы можем посчитать при индексировании и закешировать в индекс per file. После этого для каждого err будет находиться ровно одна корректная декларация.

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

SourceCraft ver.2: глобальный resolve, обратные индексы

В этой версии мы уже движемся в сторону компилятора и своей код‑модели, так что начинаем делать глобальный resolve. Для этого нам понадобится:

• Индекс мемберов для пакетов и типов.

• Разобраться как реализовывать обратные индексы per commit.

Чуть подробнее. У нас есть три файла в пакете p, в них объявлены типы и функция.

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

Это map из строчки в массив деклараций мемберов. Обсудим его реализацию per commit.

Введём две сущности:

• Snapshot — индекс по всем файлам, доступным в этом коммите.

• Delta — дельта индекса, что поменялось в этом коммите.

Member Index строится по прямым индексам. По изменению в файле можно вычислить изменения в индексе, а хранится он в виде снапшотов и дельт изменений между ними.

В примере с тремя файлами в пакете наш Member Index представляет собой снапшот:

Подходы к организации дельт могут быть различны в зависимости от данных индекса.

В дополняющей дельте мы храним только разницу, что для конкретного ключа поменялось в значениях. В коммите #2 удалили Point из структуры TPoint, а в коммите #3 добавили поле Z в структуру Point.

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

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

Теперь пора вспомнить, что все коммиты образуют граф.

Как расставлять снапшоты в этом графе?
Для начала преобразуем граф в его остовное дерево — исключим неоднозначности при построении дельт.

Далее нам важно расстояние между снапшотами (К) — между двумя любыми снапшотами всегда не более K дельт. Это влияет на потребление памяти и скорость работы.

Второй параметр — глубина индексации (N) — сколько мы индексируем от HEAD каждой ветки. Это тоже помогает нам сэкономить память, но может ограничить функциональность — старые коммиты будут без навигации по коду.

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

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

Снапшот один — по памяти отлично, а вот дельт может быть многовато, и бегать по всем будет дорого.

Очень интересна и кажется наиболее перспективной ещё одна стратегия расстановки снапшотов. Можно заметить, что наши дельты индекса со знаками + и -, которые не сложно развернуть на противоположные. Тогда мы получим механизм построения обратных дельт. И сможем ходить по дереву коммитов в любую сторону. Например:

Снапшот стоит где‑то посередине, мы умеем ходить в обе стороны и достроить дельты для всех окрестных коммитов.

Что у нас получилось по характеристикам.

• Решение сложнее обобщается на новые языки.

• Занимает больше памяти.

• Скорость go to declaration значительно возрастает.

• Индексируется в среднем быстро.

• Гораздо ТОЧНЕЕ, так как ближе к компиляторному подходу.

• Имеет возможности к дальнейшим улучшениям.

Что дальше? Совсем скоро мы откроем доступ к платформе SourceCraft, но уже сейчас вы можете записаться в лист ожидания для её тестирования. Будем особенно рады вопросам и предложениям со стороны комьюнити!