Задача

Дано: проект на основе OpenWRT (а он — на основе BuildRoot) с одним дополнительным репозиторием, подключенным как feed. Задача: слить дополнительный репозиторий с основным.

Предыстория

Мы делаем маршрутизаторы и, однажды, захотели дать клиентам возможность включать свои приложения в прошивку. Чтобы не мучаться с выделением SDK, toolchain и сопутствующими сложностями, решили выложить весь проект на github в закрытый репозиторий. Структура репозитория:

/target   // скрипты для сборки ядер
/toolchain   // скрипты для сборки gcc, musl и прочих инструментов сборки 
/feeds   // дополнительные репозитории с приложениями
/package   // скрипты для сборки приложений
...

Было решено часть приложений собственной разработки перенести из основного репозитория в дополнительный, чтоб никто не подсмотрел. Мы всё это сделали, выложили на github и стало хорошо.

Много воды утекло с тех пор…

Клиента того давно уж нет, репозиторий с github убрали, и сама идея открывать клиентам доступ в репозиторий протухла. Однако же, два репозитория в проекте остались. И все скрипты/приложения, так или иначе связанные с git, вынужденно усложняются, чтобы работать с такой структурой. Проще говоря, это технический долг. Например, чтобы обеспечить воспроизводимость релизов, необходимо в основной репозиторий (primary) закоммитить файлик, secondary.version, с хэшем из второго репозитория. Конечно, это делает скрипт, и ему не очень сложно. Но, таких скриптов с десяток, и все они сложнее чем могли бы быть. В общем, я принял волевое решение влить репозиторий secondary обратно в primary. При этом, было поставлено главное условие — сохранить воспроизводимость релизов.

Раз поставлено такое условие, то тривиальные методы слияния, как то, закоммитить всё из secondary отдельно и потом, сверху, сделать merge-коммит двух независимых деревьев, не подойдут. Придётся открыть капот и испачкать руки.

Структура данных git

Для начала, что из себя представляет репозиторий git? Это база объектов. Объекты бывают трёх типов: блобы (blob), деревья (tree) и коммиты (commit). Все объекты адресуются sha1 хэшем своего содержимого. Блоб — это, тупо, данные без каких-либо дополнительных атрибутов. Дерево представляет из себя отсортированный список ссылок на деревья и блобы вида “<права> <тип> <хэш> <имя>” (где <тип> это, либо blob, либо tree). Таким образом дерево, это как бы директория в файловой системе, а блоб — это как бы файл. Коммит содержит имя автора и коммитера, дату создания и добавления, комментарий, хэш дерева и произвольное количество (чаще всего одна или две) ссылок на родительские коммиты. Вот эти ссылки на родительские коммиты, как раз и превращают базу объектов в ациклический орграф (среди иностранцев, известен, как DAG). Подробно читайте тут:


Таким образом, наша задача преобразовалась в задачу построения нового орграфа, повторяющего структуру старого. Но с заменой коммитов файла secondary.version на коммиты из дополнительного репозитория



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

Анализ

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

node = namedtuple(‘Node’, [‘primary_commit’, ‘secondary_commit’, ‘children’])

Кладу его в словарь:

master_tip = repo.commit(‘master’)
commit_map = {master_tip : node(master_tip, get_sec_commit(master_tip), [])}

Туда же кладу все коммиты изменяющие secondary.version:

for c in repo.iter_commits(all=True, path=’secondary.verion’) :
    commit_map[c] = node(c, get_sec_commit(c), [])

И строю простенький рекурсивный алгоритм:

def build_dag(commit, commit_map, node):
    for p in commit.parents :
        if p in commit_map :
           if node not in commit_map[p].children :
               commit_map[p].children.append(node)
           build_dag(p, commit_map, commit_map[p])
        else :
           build_dag(p, commit_map, node)

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

Запускаю, и… RuntimeError max recursion depth exceeded

Как же так получилось? Неужели, слишком много коммитов? git log и wc знают ответ. Всего коммитов с момента разделения около 20000, а затрагивающих secondary.version — почти 700. Рецепт известен, нужна нерекурсивная версия.

def build_dag(master_tip, commit_map, master_node):
    to_process = [(master_tip, master_node)]
    while len(to_process) > 0:
        c, node = to_process.pop()
        for p in c.parents :
            if p in commit_map :
                if node not in commit_map[p].children :
                    commit_map[p].children.append(node)
                to_process.append(p, commit_map[p])
            else :
                to_process.append(p, node)

(А вы говорили, что все эти алгоритмы нужны только чтоб интервью проходить!)

Запускаю, и… оно работает. Минуту, пять, двадцать… Нет, так долго нельзя. Останавливаю. Судя по всему каждый коммит и каждый путь обрабатывается по многу раз. Сколько же в дереве разветвлений? Выяснилось, что в дереве 40 разветвлений и, соответственно, $\$inline\$2^\{40\}\$inline\$$ разных путей только от мастера. И к значительной части ключевых коммитов ведут многие пути. Поскольку тысячи лет у меня в запасе нет, надо поменять алгоритм так, чтобы каждый коммит обрабатывался ровно один раз. Для этого добавляю множество, где отмечаю каждый обработанный коммит. Но тут есть маленькая проблема: при таком подходе часть связей будет утеряна, так как разные пути с разными ключевыми коммитами могут проходить через одни и те же коммиты, и только первый пойдёт дальше. Чтобы обойти эту проблему, множество заменяю на словарь, где ключами будут коммиты, а значениями — списки достижимых ключевых коммитов:

def build_dag(master_tip, commit_map, master_node):
    processed_commits = {}
    to_process = [(master_tip, master_node, [])]
    while len(to_process) > 0:
        c, node, path = to_process.pop()
        p_node = commit_map.get(c)
        if p_node :
            commit_map[p].children.append(p_node)
            for path_c in path :
                if all(p_node.trunk_commit != nc.trunk_commit for nc 
                           in processed_cmmts[path_c]) : 
                    processed_cmmts[path_c].append(p_node)
                path = []
                node = p_node
        processed_cmmts[c] = []        
        for p in c.parents :
            if p != root_commit and and p not in processed_cmmts :
                newpath = path.copy()
                newpath.append(c)
                to_process.append((p, node, newpath,))
            else :
                p_node = commit_map.get(p)
                if p_node is None :
                    p_nodes = processed_cmmts.get(p, [])
                 else :
                    p_nodes = [p_node]
            for pn in p_nodes :
                node.children.append(pn)
                if all(pn.trunk_commit != nc.trunk_commit for nc 
                           in processed_cmmts[c]) :
                    processed_cmmts[c].append(pn)
                for path_c in path :
                    if all(pn.trunk_commit != nc.trunk_commit 
                              for nc in processed_cmmts[path_c]) :
                        processed_cmmts[path_c].append(pn)

В результате этого бесхитростного обмена памяти на время граф строится за 30 сек.

Синтез

Теперь у меня есть commit_map с ключевыми узлами связанными в граф через ссылки на потомков. Для удобства, преобразую его в последовательность пар (предок, потомок). В последовательности должно быть гарантированно, что все пары, где узел встречается в качестве потомка, расположены раньше чем любая пара, где узел встречается в качестве предка. Дальше надо просто пройти по этому списку и закоммитить сначала коммиты из основного репозитория, а потом из дополнительного. Тут надо помнить, что коммит содержит ссылку на дерево, которое является состоянием файловой системы. Так как, дополнительный репозиторий содержит дополнительные поддиректории в директории package/, то надо будет для всех коммитов создать новые деревья. В первой версии, я просто писал блобы в файлы и просил гит построить индекс по рабочей директории. Однако, такой метод оказался не очень производительным. Коммитов всё ещё 20000, и каждый нужно закоммитить ещё раз. Так что, тут производительность имеет большое значение. Небольшое исследование внутренностей GitPython привело меня к классу gitdb.LooseObjectDB, который открывает прямой доступ к объектам git-репозитория. С ним, блобы и деревья (и любые другие объекты, тоже) из одного репозитория можно писать прямо в другой. Замечательным свойством базы объектов git является то, что адресом любого объекта, является хэш от его данных. По этому, одинаковый блоб будет иметь один и тот же адрес, даже в разных репозиториях.

secondary_paths = set()
ldb = gitdb.LooseObjectDB(os.path.join(repo.git_dir, 'objects'))
while len(pc_pairs) > 0:
    parent, child = pc_pairs.pop()
    for c in all_but_last(repo.iter_commits('{}..{}'.format(
                      parent.trunk_commit, child.trunk_commit), reverse = True)) :
        newparents = [new_commits.get(p, p) for p in c.parents]
        new_commits[c] = commit_primary(repo, newparents, c, secondary_paths)
    newparents = [new_commits.get(p, p) for p in child.trunk_commit.parents]
    c = secrepo.commit(child.src_commit)
    sc_message = 'secondary commits {}..{} <devonly>'.format(
           parent.src_commit, child.src_commit)
    scm_details = '\n'.join(
       '{}: {}'.format(i.hexsha[:8], textwrap.shorten(i.message, width = 70))
       for i in secrepo.iter_commits(
               '{}..{}'.format(parent.src_commit, child.src_commit), reverse = True))
    sc_message = '\n\n'.join((sc_message, scm_details))
    new_commits[child.trunk_commit] = commit_secondary(
          repo, newparents, c, secondary_paths, ldb, sc_message)

Сами функции коммита:

    def commit_primary(repo, parents, c, secondary_paths) :
       head_tree = parents[0].tree
       repo.index.reset(parents[0])
       repo.git.read_tree(c.tree)
       for p in secondary_paths :
           # primary commits don't change secondary paths, so we'll just read secondary
           # paths into index
           tree = head_tree.join(p)
           repo.git.read_tree('--prefix', p, tree)
       return repo.index.commit(c.message, author=c.author, committer=c.committer
                         , parent_commits = parents
                         , author_date=git_author_date(c)
                         , commit_date=git_commit_date(c))

    def commit_secondary(repo, parents, sec_commit, sec_paths, ldb, message):
       repo.index.reset(parents[0])
       if len(sec_paths) > 0 :
           repo.index.remove(sec_paths, r=True, force = True, ignore_unmatch = True)
       for o in sec_commit.tree.traverse() :
           if not ldb.has_object(o.binsha) :
               ldb.store(gitdb.IStream(o.type, o.size, o.data_stream))
           if o.path.find(os.sep) < 0 and o.type == 'tree':  # a package root
               repo.git.read_tree('--prefix', path, tree)
               sec_paths.add(p)
       
       return repo.index.commit(message, author=sec_commit.author
                                , committer=sec_commit.committer
                                , parent_commits=parents
                                , author_date=git_author_date(sec_commit)
                                , commit_date=git_commit_date(sec_commit))

Как видите коммиты из secondary репозитория добавляются скопом. Сначала, я сделал чтобы добавлялись индивидуальные коммиты, но (внезапно!) выяснилось, что иногда более новый ключевой коммит содержит предыдущую версию secondary репозитория (проще говоря, версию откатывают). В такой ситуации метод iter_commit пасует и возвращает пустой список. В результате репозиторий получается неправильный. По-этому, пришлось просто коммитить актуальную версию.

Интересна история появления генератора all_but_last. Описание я опустил, но делает он именно то, что вы ожидаете. Сначала там был просто вызов

repo.iter_commits('{}..{}^'.format(parent.trunk_commit, child.trunk_commit), reverse = True)

. Однако, быстро выяснилось, что запись "x..y^" означает совсем не «все коммиты от x до y, исключая сами x и y», а «все коммиты от x до первого родителя y, включая этого родителя». В большинстве случаев, это одно и то же. Но только не тогда, когда у y несколько родителей…

В общем, всё закончилось хорошо. Весь скрипт уместился строчек в 300 и отработал примерно за 6 часов. Мораль: GitPython'ом удобно делать всякие крутые штуки с репозиториями, но лучше техдолг лучше лечить своевременно