Как работает git log --graph или hg graphlog?

Question

Я знаю, что история в Git хранится в структуре данных, называемой DAG.Я слышал о DFS и знаю, что это несколько связано.

Мне интересно, как такие программы, как git log --graph или hg graphlog рисуют историю?Я всегда думал, что довольно сложно рисовать дорожки и все таким приятным способом.

Может ли кто-нибудь написать какой-нибудь псевдокод, демонстрирующий это?но очень трудно следить и получить общее представление о том, что происходит.

Answer 1

Сначала получают список коммитов (как с git rev-list) и родителей каждого коммита. «Список резервирования столбцов» хранится в памяти.

Для каждого коммита затем:

• Если для коммита нет зарезервированного для него столбца, присвойте его свободному столбцу. Вот так начнутся главы филиалов.
• Распечатать графику дерева в соответствии со списком резервирования столбцов, а затем сообщение о фиксации
• Запись списка резервирования для текущего столбца / коммита обновляется первым родителем текущего коммита, так что родительский объект будет напечатан в том же столбце.
• Другие родители получают новую бесплатную колонку.
• Если это было слияние, следующая строка будет пытаться связать второго родителя со столбцом, в котором ожидается фиксация (это относится к циклам и "≡ bridge")

Пример, показывающий вывод git-forest на aufs2-util с дополнительным коммитом, имеющим более одной ветви).

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

Answer 2

Я попытался просмотреть код Git или hg, но очень трудно следить и получить общее представление о том, что происходит.

Для hg, вы пытались следовать коду вhg сам по себе, или в graphlog?

Потому что код graphlog довольно короткий.Вы можете найти его в hgext / graphlog.py , и действительно важная часть - это верхние ~ 200 строк, остальные - это самозагрузка расширения и поиск выбранного графа ревизий.Функция генерации кода - ascii, последний параметр которой является результатом вызова asciiedge (сам вызов выполняется в последней строке generate, функция предоставляется generate graphlog)

Answer 3

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

Также обратите внимание, что модель отображения основана на сетке, строки - это фиксации, а столбцы - ребра в прошлое / будущее.

Хотя я не читал исходники git, вы, вероятно, просто просматриваете список коммитов, начиная с самых новых, и сохраняете список открытых ребер в прошлом.Следование по краям естественным образом приводит к разбиению / объединению столбцов, и в итоге вы получаете вид дерева git / hg display.

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

Answer 4

Примечание: Git 2.18 (Q2 2018) теперь предварительно вычисляет и сохраняет информацию, необходимую для обхода предков, в отдельном файле для оптимизации обхода графа.

То, что фиксирует график , действительно меняет принцип работы git log --graph.

Как упомянуто здесь :

git config --global core.commitGraph true
git config --global gc.writeCommitGraph true
cd /path/to/repo
git commit-graph write

См. коммит 7547b95 , коммит 3d5df01 , коммит 049d51a , коммит 177722b , коммит 4f2542b , commit 1b70dfd , commit 2a2e32b (10 апреля 2018) и commit f237c8b , commit 08fd81c , commit 4ce58ee , коммит ae30d7b , коммит b84f767 , коммит cfe8321 , коммит f2af9f5 (02 апреля 2018) Деррик Столи (derrickstolee) ) .
^{(Объединено с Junio ​​C Hamano - gitster - в commit b10edb2 , 08 мая 2018 г.)}

Теперь у вас есть команда git commit-graph: запись и проверка файлов графиков Git commit.

Напишите файл графика коммитов, основанный на коммитах, найденных в пакетных файлах.
Включает все коммиты из существующего файла графа коммитов.

Проектный документ гласит:

Git просматривает граф фиксации по многим причинам, включая:

1. Просмотр и фильтрация истории коммитов.
2. Вычисление базисов слияния.

Эти операции могут замедляться по мере увеличения количества коммитов. Слияние базовый расчет отображается во многих пользовательских командах, таких как «объединение базы» или «статус» и может занять несколько минут для расчета в зависимости от формы истории.

Здесь есть две основные затраты:

1. Распаковка и разбор коммитов.
2. Обход графа для удовлетворения ограничений топологического порядка.

Файл графа фиксации представляет собой дополнительную структуру данных, которая ускоряет совершить прогулку по графу . Если пользователь понижает или отключает настройку конфигурации «core.commitGraph», то существующего ODB достаточно.

Файл сохраняется как "commit-graph" либо в каталоге .git/objects/info, либо в информационном каталоге альтернативного файла.

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

Вы можете увидеть тестовые сценарии использования :

git log --oneline $BRANCH
git log --topo-order $BRANCH
git log --graph $COMPARE..$BRANCH
git branch -vv
git merge-base -a $BRANCH $COMPARE

Это улучшит git log производительность .

---

Git 2.19 (Q3 2018) позаботится о файле блокировки:

См. commit 33286dc (10 мая 2018), commit 1472978 , commit 7adf526 , commit 04bc8d1 , commit d7c1ec3 , commit f9b8908 , commit 819807b , commit e2838d8 , commit 3afc679 , commit 3258c66 (01 Май 2018) и коммит 83073cc , коммит 8fb572a (25 апреля 2018) Деррик Столи (derrickstolee) .
Помощник: Джефф Кинг (peff) .
^{(Объединено Junio ​​C Hamano - gitster - в коммит a856e7d , 25 июня 2018 г.)}

commit-graph: исправлена ​​проблема с UX, когда .lock файл существует

Мы используем API-интерфейс lockfile, чтобы избежать записи в несколько процессов Git файл графика фиксации в каталоге .git/objects/info .
В некоторых случаях этот каталог может не существовать, поэтому мы проверяем его наличие.

При получении блокировки существующий код выполняет следующие действия:

1. Попробуйте получить замок.
2. Если не получится, попробуйте создать каталог .git/object/info.
3. Попытайтесь заполучить замок, если не получится.

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

"fatal: cannot mkdir .git/objects/info: File exists"

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

Вместо этого сделайте следующее:

1. Проверка на наличие .git/objects/info; создать при необходимости.
2. Попытайтесь заполучить блокировку, если не получится.

Новый вывод выглядит так:

fatal: Unable to create
'<dir>/.git/objects/info/commit-graph.lock': File exists.

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

---

Примечание. Средство коммит-графа не работало, когда внутриядерные объекты продвигаются из неизвестного типа для фиксации (например, коммит, который доступ через тег, который ссылается на него) были вовлечены, который был исправлено с помощью Git 2.21 (февраль 2019 г.)

См. коммит 4468d44 (27 января 2019 г.) SZEDER Gábor (szeder) .
^{(Объединено с Junio ​​C Hamano - gitster - в коммит 2ed3de4 , 05 февраля 2019)}