Как работает "git log --graph" или "hg graphlog"?
Я знаю, что история в Git хранится в структуре данных, называемой DAG. Я слышал о DFS и знаю, что это несколько связано.
Мне интересно, как работают такие программы как git log --graph или же hg graphlog нарисовать историю? Я всегда думал, что довольно сложно нарисовать дорожки и все так хорошо.
Может ли кто-нибудь написать какой-нибудь псевдокод, демонстрирующий это?
примечание: я попытался просмотреть код Git или hg, но очень трудно следить и получить общее представление о том, что происходит.
4 ответа
Во-первых, получается список коммитов (как с git rev-list) и родители каждого совершают. "Список резервирования столбцов" хранится в памяти.
Затем для каждого коммита:
- Если для коммита нет зарезервированного для него столбца, присвойте его свободному столбцу. Вот так начнутся руководители филиалов.
- Распечатайте древовидную графику в соответствии со списком резервирования столбцов, а затем сообщение о фиксации.
- Запись списка резервирования для текущего столбца / коммита обновляется первым родителем текущего коммита, так что родительский объект будет напечатан в том же столбце.
- Другие родители получают новую бесплатную колонку.
- Если это было слияние, следующая строка будет пытаться связать второго родителя со столбцом, где ожидается фиксация (это делает для циклов и "≡ bridge")
Пример, показывающий вывод git-forest на aufs2-util с дополнительным коммитом, чтобы иметь более одной ветки).
С предвкушением можно предвидеть, насколько далеко будет точка слияния, и сжать древесину между двумя колоннами, чтобы получить более эстетичный результат.
Я попытался просмотреть код Git или hg, но очень трудно следить и получить общее представление о том, что происходит.
Для hg, вы пытались следовать коду в самой hg или в графе?
Потому что код графа очень короткий. Вы можете найти его в hgext / graphlog.py, и действительно важная часть - это верхние ~200 строк, остальные - это самозагрузка расширения и поиск выбранного графа ревизий. Функция генерации кода asciiс последним параметром, являющимся результатом вызова asciiedge (сам вызов выполняется в последней строке generateфункция предоставляется generate от graphlog)
Эта конкретная проблема не так сложна, по сравнению с графическим отображением в целом. Поскольку вы хотите сохранить узлы в порядке их фиксации, проблема становится намного проще.
Также обратите внимание, что модель отображения основана на сетке, строки - это коммиты, а столбцы - ребра прошлого / будущего.
Хотя я не читал исходники git, вы, вероятно, просто просматриваете список коммитов, начиная с самых новых, и ведете список открытых граней в прошлое. Следование по краям естественным образом приводит к разделению / объединению столбцов, и вы в конечном итоге получаете вид дерева git / hg display.
При объединении ребер вы хотите избегать пересечения других ребер, поэтому вам придется постараться упорядочить столбцы заранее. Это на самом деле единственная часть, которая может быть не простой. Например, можно сделать двухпроходный алгоритм, составив порядок столбцов для ребер в первом проходе и выполняя рисование во втором проходе.
Примечание: Git 2.18 (Q2 2018) теперь предварительно вычисляет и сохраняет информацию, необходимую для обхода предков, в отдельном файле для оптимизации обхода графа.
Это понятие графов коммитов меняет как git log --graph ' работает.
См. Коммит 7547b95, коммит 3d5df01, коммит 049d51a, коммит 177722b, коммит 4f2542b, коммит 1b70dfd, коммит 2a2e32b (10 апреля 2018 г.) и коммит f237c8b, коммит 08fd81c, коммит 4ce58ee, коммит ae30d7b, коммит b84f767, коммит ffef2322, коммит ff832 Апрель 2018) Деррик Столи ( derrickstolee )
(Объединено Юнио С Хамано - gitster - в комитете b10edb2 от 08 мая 2018 года)
Теперь у вас есть команда git commit-graph: Напишите и проверьте файлы графов Git commit.
Напишите файл графика коммитов, основанный на коммитах, найденных в пакетных файлах.
Включает все коммиты из существующего файла графа коммитов.
Проектный документ гласит:
Git просматривает график коммитов по многим причинам, включая:
- Вывод списка и фильтрация истории коммитов.
- Вычислительные базы слияния.
Эти операции могут стать медленными по мере увеличения количества коммитов. Расчет базы слияния обнаруживается во многих пользовательских командах, таких как "база слияния" или "статус", и может потребоваться минуты для вычисления в зависимости от формы истории.
Здесь есть две основные затраты:
- Распаковка и разбор коммитов.
- Ходить по всему графику, чтобы удовлетворить ограничения топологического порядка.
Файл графа фиксации - это дополнительная структура данных, которая ускоряет обход графа фиксации. Если пользователь понижает или отключает
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, коммит 7adf526, коммит 04bc8d1, коммит d7c1ec3, коммит f9b8908, коммит 819807b, коммит e2838d8, коммит 3afc679, коммит 3258c66 (01 мая 2018 г.) и коммит 83073cc, коммит 8fb57 2018) Деррик Столи ( derrickstolee )
Помогает: Джефф Кинг ( peff )
(Объединено Юнио С Хамано - gitster - в комитете a856e7d, 25 июня 2018 г.)
commit-graph: исправить проблему UX, когда.lockФайл существуетМы используем API-интерфейс lockfile, чтобы избежать записи несколькими процессами Git в файл commit-graph в
.git/objects/infoкаталог.
В некоторых случаях этот каталог может не существовать, поэтому мы проверяем его наличие.Существующий код выполняет следующие действия при получении блокировки:
- Попробуйте приобрести замок.
- Если это не удается, попробуйте создать
.git/object/infoкаталог.- Попробуйте получить блокировку, если это не удалось.
Проблема заключается в том, что если файл блокировки существует, то mkdir завершается ошибкой, выдавая ошибку, которая не помогает пользователю:
"fatal: cannot mkdir .git/objects/info: File exists"Хотя технически это учитывает файл блокировки, это не помогает пользователю.
Вместо этого сделайте следующее:
- Проверить на наличие
.git/objects/info; создать при необходимости.- Попробуйте получить блокировку, если это не удалось.
Новый вывод выглядит так:
fatal: Unable to create '<dir>/.git/objects/info/commit-graph.lock': File exists.Похоже, в этом репозитории запущен другой процесс git, например, редактор, открытый git commit. Пожалуйста, убедитесь, что все процессы завершены, затем повторите попытку. Если это все еще не удается, возможно, произошел сбой в этом хранилище в этом хранилище: удалите файл вручную, чтобы продолжить.