mergiraf — AST-ориентированный инструмент для трёхстороннего слияния в Git

Опубликован релиз проекта mergiraf 0.4, развивающего драйвер для Git с реализацией возможности трёхстороннего слияния. Mergiraf поддерживает разрешение различных видов конфликтов при слиянии и может использоваться для различных языков программирования и форматов файлов. Возможно как отдельный вызов mergiraf для обработки конфликтов, возникающих при работе со штатным Git, так и замена в Git обработчика слияний для расширения возможностей таких команд, как merge, revert, rebase и cherry-pick. Код распространяется под лицензией GPLv3. В новой версии добавлена поддержка языков Python, TOML, Scala и Typescript, а также проведена оптимизация производительности.

Ниже представлено подробное описание проблем, решаемых при помощи mergiraf:

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

В контексте продуктов каждый узел называется «версией», представляющей собой определённый набор функций и антифункций. Любое изменение этого набора считается мутацией, формирующей ребро в нашем направленном ациклическом графе. Эти функции по своей сути абстрактны; они не отражают напрямую способы функционирования физических систем, а скорее демонстрируют, как разумные агенты воспринимают полезность этих систем. Чтобы перевести идеи в существующие в реальном мире реализации, необходимо засучить рукава и нырнуть в *достаточно* низкоуровневые детали, на языке которых можно выразить и объяснить, как конкретно всё работает. В разработке ПО эти низкоуровневые обычно представлены исходным кодом.

Чтобы постепенно привести исходный код в состояние, проявляющее требуемое поведение, и задокументировать, как они его туда привели, программисты представляют свою работу в терминах snapshot-ов и changest-ов. Snapshot представляет собой определённое состояние продукта со всеми низкоуровневыми деталями, в то время как changeset обозначает переход между snapshot-ами. Обычно snapshot-ы порождаются одиночных changeset-ов к их родителям, поэтому эти snapshot-ы почти всегда маркируют тем, что делают changeset-ы, которые их создали, поэтому эти термины часто используются взаимозаменяемо.

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

Эта функциональность позволяет разработчикам писать семантически значимую историю проекта, что имеет решающее значение для отладки и ответов на вопросы вроде «Зачем была введена эта низкоуровневая деталь (напр., переменная)?», «Сколько процентов приблизительно мой вклад в этот проект?», «Кого взломали внедрения закладки и когда?», «Какое низкоуровневое изменение сломало эту функцию (хотя вроде бы не должно было, мы всё проверили!?)»

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

Обычно делается основная ветка, представляющая «официальный» продукт, от которой ветвятся боковые ветки для каждой функции, которые регулярно (в идеале — после каждого коммита) синхронизируются с основной веткой, что позволяет разработчикам работать с наисвежайшей версией продукта и одновременно внедрять функции, которые они в данный момент разрабатывают, детектируя проблемы, проистекающие от действий других разработчиков, как можно раньше.

При попытке комбинирования функций различных snapshot-ов (что есть просто нахождения общего предка, и применения changesetов, их порождающих, последовательно поверх другого, эта операция называется rebase, слияние же — это почти как rebase, просто структурирует граф коммитов по-другому, в результате чего им становится неудобно манипулировать, поэтому от слияний стараются отказаться в пользу rebase-ов) возникают проблемы. Современные системы контроля версий (VCS) используют внутренние алгоритмы объединения изменений, которые просто разбивают файлы на отдельные строки, рассматривают каждую строку как символ, а файлы — как их последовательности, и затем применяют алгоритмы для их объединения, которые родом из биоинформатики.

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

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

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

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

Наиболее выдающаяся свободная реализация того периода, GumTree, создана исследователем с академическим бэкграундом, написана на Java, имеет своё абстрактное внутреннее представление, предшествующее treesitter, имеет бэкэнды, как основанные на treesitter, так и основанные на других инструментов для парсинга исходного кода в абстрактные представления. Данная система умеет только генерировать (в виде текстового лога событий, также имеется API, которое можно тривиально вызвать из любого ЯП, имеющего биндинги к Java) и визуализировать изменения. Однако для слияния изменений, а равно для просмотра сгенерированных ею diff-файлов, она из коробки неприменима (впрочем, вероятно, что загрузку diff-ов можно реализовать через API).

Более молодая и более применимая на практике реализация difftastic написана на Rust, основана на treesitter, сфокусирована на генерации подсвеченных diff-ов в консоли. Данная система тоже направлена на визуализацию diff-ов и вообще не ставит своей целью слияние изменений или применение патчей.

Совсем недавно появился и активно развивается проект mergiraf. Этот написанный на Rust инструмент (занимает 21 MiB!) также основан на treesitter, который уже стал таким же стандартом для парсеров контекстно-свободных грамматик в инструментах разработки, каким стал LLVM для оптимизации низкоуровневых представлений инструкций. В отличии от конкурентов mergiraf предоставляет функции не для генерации diff-ов, а для автоматического разрешения конфликтов слияний. Под капотом mergiraf использует для генерации патчей реализацию алгоритма, используемого в GumTree, а для применения — реализацию алгоритма, используемого в spork, адаптированные под структуры treesitter.

Cериализация патчей в файлы, которые могут быть применены потом, к сожалению, не реализована (но вполне вероятно, что может быть реализована путём парсинга логов событий, генерируемых GumTree). Другим перспективным способом применения различий может быть применение различий не через патчи, а через функциональность рефакторинга LSP-серверов, что может помочь в детектировании конфликтов на уровне всего проекта. Визуализация поддерживается только для конфликтов.

Пример работы: общий предок «base.py» (отступы табами, лишняя строка в начале) foo = 1 def main(): print(foo + 2 + 3) «a.py» (отступы по-прежнему табами, 2 лишних строки в начале вместо одной, для отладочной печати задействована библиотека icecream, добавлен класс «baz»: from icecream import ic foo = 1 def main(): ic(foo + 2 + 3) class baz: def __init__(self): «»»baz»»» «b.py» (переменная «foo» переименована в «bar», обработано с помощью «black» после изменений, в результате отступы — пробелами и лишние строки вырезаны): bar = 1 def main(): print(bar + 2 + 3) Вызов ./mergiraf merge ./base.py ./a.py ./b.py -x a.py -y b.py -s base.py -o ./res.py даёт следующий результат from icecream import ic bar = 1 def main(): ic(bar + 2 + 3) class baz: def __init__(self): «»»baz»»» (для отладочной печати задействована библиотека «icecream», переменная «foo» переименована в «bar», обработано с помощью «black» после изменений, в результате отступы — пробелами и лишние строки вырезаны, смесь табов и пробелов для отступа, но разрешённый вид).

Тут же виден недостаток инструмента. Стиль документа обычно конфигурируется в файлах «.editorconfig», и глобальные изменения стиля, вроде смены табов на пробелы и принятия стиля black-а, как было сделано в «b.py», обычно сопровождаются изменениями в «.editorconfig». Поэтому для более корректного применения подобных изменений инструмент должен иметь концепцию для глобального стиля «по умолчанию», и уметь подтягивать настройки из «.editorconfig».

Источник: opennet.ru