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

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

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

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

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

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

Что касается hg, вы пытались следовать коду в самом hg или в графлоге?

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

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

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

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

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

Примечание. Git 2.18 (второй квартал 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, , коммит 177722b, коммит 4f2542b, commit 1b70dfd, commit 2a2e32b (10 апреля 2018 г.) и фиксировать f237c8b, 8фиксировать 0 , коммит 4ce58ee, зафиксировать ae30d7b, b84f767, коммит cfe8321, commit f2af9f5 (02 апреля 2018 г.), автор Деррик Столи (derrickstolee).
^{(объединено Junio ​​C Hamano -- gitster -- в commit b10edb2, 08 мая 2018 г.)}

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

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

В проектном документе указано:

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 (3 ​​квартал 2018 г.) позаботится о файле блокировки:

См. commit 33286dc (10 мая 2018 г.), коммит 1472978, зафиксировать 7adf526, зафиксировать 04bc8d1, коммит d7c1ec3, commit f9b8908, commit 819807b , зафиксировать e2838d8, зафиксировать 3afc679 , коммит 3258c66 (1 мая 2018 г.) и зафиксировать 83073cc, commit 8fb572a (25 апреля 2018 г.), автор Деррик Столи (derrickstolee).< br /> Помощь: Джефф Кинг (peff).
^{(Объединено < a href="https://github.com/gitster" rel="nofollow noreferrer">Юнио С. Хамано -- gitster -- в commit a856e7d, 25 июня 2018 г.)}

commit-graph: исправлена ​​проблема с UX при наличии файла .lock

Мы используем API файла блокировки, чтобы предотвратить запись несколькими процессами 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.

Another git process seems to be running in this repository, e.g.
an editor opened by 'git commit'. 
Please make sure all processes are terminated then try again. 
If it still fails, a git process may have crashed in this repository earlier:
remove the file manually to continue.

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

См. коммит 4468d44 (27 января 2019 г.) от ШЕДЕР Габор (szeder).
^{(объединено Хунио С. Хамано -- gitster -- в commit 2ed3de4, 05 февраля 2019 г.)}

См. коммит 238def5, коммит f998d54, , коммит b2c8306, коммит 4c9efe8, зафиксировать ef5b83f, зафиксировать c9905be, зафиксировать 10bd0be, зафиксировать 5af8039 , коммит e103f72 (12 июня 2019 г.) и commit c794405 (09 мая 2019 г.), автор Деррик Столи (derrickstolee).
^{(Объединено Юнио С. Хамано - - gitster -- в commit e116894, 09 июля 2019 г.)}

Коммит 10bd0be объясняет изменение области действия.

В Git 2.24 (Q3 2109) код для записи commit-graph по заданным именам объектов фиксации стал немного более надежным.

См. коммит 7c5c9b9, commit 39d8831, commit 9916073 (05 августа 2019 г.), автор ШЕДЕР Габор (szeder).
^{(Объединено Junio ​​C Hamano -- gitster -- в commit 6ba06b5, 22 августа 2019 г.)}

Кроме того, в Git 2.24 (четвертый квартал 2019 г.) код для анализа и использования файла графика коммитов стал более устойчивым к поврежденным входным данным.

См. коммит 806278d, коммит 16749b8, (5 сентября 2019 г.), автор Тейлор Блау (ttaylorr).
^{(Объединено Junio ​​C Hamano -- gitster -- в commit 80693e3, 7 октября 2019 г.)}

t/t5318: введите неудачные тесты "git commit-graph write"

При вызове git commit-graph в поврежденном репозитории можно вызвать segfault, когда наследственные коммиты так или иначе повреждены.
Это связано с двумя вызовами функций в коде 'commit-graph.c', которые могут возвращать NULL , но не проверяются на NULL перед разыменованием.

Следовательно:

commit-graph.c: обрабатывать ошибки синтаксического анализа фиксации

Чтобы записать фрагмент графа коммитов, 'write_graph_chunk_data()' берет список коммитов для записи и анализирует каждый из них перед записью необходимых данных и переходит к следующему коммиту в списке.

Поскольку большинство этих коммитов не анализируются заранее (исключение делается для последнего коммита в списке, который анализируется раньше в пределах 'copy_oids_to_commits'), возможно, что вызов 'parse_commit_no_graph()' на них может быть возвращена ошибка.
Неспособность перехватить эти ошибки до разыменования последующих вызовов может привести к неопределенному доступу к памяти и SIGSEGV. ² Одним из таких примеров является «get_commit_tree_oid()», который ожидает проанализированный объект в качестве входных данных (в этом случае код commit-graph передает «*list»).
Если «*list» вызывает ошибку синтаксического анализа, последующий вызов неудача.

Предотвратите такую ​​проблему, проверив возвращаемое значение 'parse_commit_no_graph()', чтобы избежать передачи непроанализированного объекта функции, которая ожидает проанализированный объект, тем самым предотвращая ошибку сегментации.

В Git 2.26 (1 квартал 2020 г.) код для вычисления графика коммитов научили использовать более надежный способ определить, ссылаются ли два каталога объектов на одно и то же.

См. коммит a7df60c, commit ad2dd5b, (3 февраля 2020 г.), commit 0bd52e2 (4 февраля 2020 г.) и коммит 1793280 (30 января 2020 г.) от Тейлор Блау (ttaylorr).
^{(объединено Хунио С Хамано -- gitster -- в коммит 53c3be2, 14 февраля 2020 г.)}

commit-graph.h: сохранить odb в 'struct write_commit_graph_context'

^{Подписано: Тейлор Блау}

В commit-graph.h есть много мест, где функция либо (или почти имеет) полный struct object_directory *, accesses -›path`, а затем отбрасывает остальную часть структуры.

Это может вызвать головную боль при сравнении местоположений каталогов объектов между альтернативами (например, в случае принятия решения о том, можно ли объединить два слоя графа коммитов).
Эти пути нормализуются с помощью normalize_path_copy(), что устраняет некоторые проблемы со сравнением, но не все 1.

Замените использование char *object_dir на odb->path, сохранив struct object_directory* в структуре write_commit_graph_context.
Это промежуточный шаг к избавлению от нормализации пути в 'commit-graph.c'.

Разрешение предоставленного пользователем аргумента '--object-dir' теперь требует, чтобы мы сравнили его с известными альтернативами на предмет равенства.

До этого исправления неизвестный аргумент '--object-dir' автоматически закрывался с нулевым статусом.

Очевидно, что это может привести к непреднамеренному поведению, например к проверке графов коммитов, которые не находятся в собственном хранилище объектов репозитория (или в одном из его альтернатив), или к тому, что опечатка маскирует законную ошибку проверки графа коммитов.
Сделайте эту ошибку не-тихой, используя 'die()', когда данный '--object-dir' не соответствует ни одному известному альтернативному хранилищу объектов.

В Git 2.28 (3 квартал 2020 г.) commit-graph write --stdin-commits оптимизирован.

См. коммит 2f00c35, коммит 1f1304d, Тейлор Блау (ttaylorr).
^{(Объединено} Junio ​​C Hamano -- gitster -- в коммит dc57a9b, 9 июня 2020 г.)

commit-graph: убрать флаг COMMIT_GRAPH_WRITE_CHECK_OIDS

^{При содействии: Джефф Кинг
Подпись: Тейлор Блау}

Поскольку 7c5c9b9c57 (commit-graph: ошибка при недопустимых коммитах в 'write --stdin-commits', 2019- 05 августа, Git v2.24.0-rc0 -- слияние, указанное в пакет № 1), встроенный график фиксации умирает при получении незафиксированных OID в качестве входных данных для ' --stdin-commits'.

Такое поведение может быть громоздким, чтобы обойти его, например, в случае передачи 'git for-each-ref' в 'git commit-graph write --stdin-commits', если вызывающая сторона не хочет самостоятельно отбрасывать несовершения. В этой ситуации было бы идеально, если бы 'git commit-graph write' написал граф содержащий входные данные, которые действительно относились к коммитам, и молча игнорировал оставшуюся часть ввода.

Для эффекта '--[no-]check-oids' были предложены некоторые варианты, которые позволили бы вызывающим сторонам сделать так, чтобы встроенный граф коммитов делал именно это.
После некоторого обсуждения трудно представить вызывающего абонента, который не хотел бы пройти ' --no-check-oids', предполагая, что мы должны полностью избавиться от поведения, связанного с жалобами на незафиксированные входные данные.

Если вызывающие абоненты хотят сохранить это поведение, они могут легко обойти это изменение, выполнив следующие действия:

git for-each-ref --format='%(objectname) %(objecttype) %(*objecttype)' |
awk '
  !/commit/ { print "not-a-commit:"$1 }
   /commit/ { print $1 }
' |
git commit-graph write --stdin-commits

Чтобы сделать так, чтобы действительные OID, которые ссылаются на несуществующие объекты, действительно были ошибкой после ослабления обработки ошибок, выполните дополнительный поиск, чтобы убедиться, что объект действительно существует, прежде чем отправлять его во внутренние компоненты графа коммитов.

Это проверено с помощью Git 2.28 (3 квартал 2020 г.).

См. commit 94fbd91 (1 июня 2020 г.) и коммит 6334c5f (3 июня 2020 г.), автор Тейлор Блау (ttaylorr).
^{(Объединено Хунио С Хамано - - gitster -- в commit abacefe, 18 июня 2020 г.)}

t5318: проверить, что "--stdin-commits" соответствует "--[no-]progress"

^{Подписано: Тейлор Блау
Подтверждено: Деррик Столи}

Следующие строки не были охвачены в недавнем тесте покрытия строк с Git:

builtin/commit-graph.c
5b6653e5 244) progress = start_delayed_progress(
5b6653e5 268) stop_progress(&progress);

Эти операторы выполняются, когда передаются как '--stdin-commits', так и '--progress'. Введите три теста, которые используют различные комбинации этих параметров, чтобы убедиться, что эти строки покрыты.

Что еще более важно, это реализует (несколько) ранее игнорируемую функцию «--stdin-commits», которая заключается в том, что он уважает «--progress».

До 5b6653e523 ([builtin/commit-graph.c](https://github.com/ git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/builtin/commit-graph.c): встроенные теги разыменования, 13 мая 2020 г., Git v2.28.0 -- слияние, указанное в ), разыменование ввода из '--stdin-commits' было выполнено внутри commit-graph.c.

Теперь, когда дополнительный индикатор прогресса может создаваться извне commit-graph.c, добавьте соответствующий тест, чтобы убедиться, что он также учитывает «--[no]-progress».

Другое расположение, которое генерирует выходные данные индикатора выполнения (от d335ce8f24 ([commit-graph.c](https: //github.com/git/git/blob/94fbd9149a2d59b0dca18448ef9d3e0607a7a19d/commit-graph.c): показать ход поиска доступных коммитов, 13 мая 2020 г., Git v2.28.0 -- объединить, указанный в партия № 2)) уже покрыта любым тестом, прошедшим '--reachable'.

В Git 2.29 (четвертый квартал 2020 г.) in_merge_bases_many(), способ узнать, доступен ли коммит из любого коммита в наборе коммитов, был полностью сломан, когда использовалась функция графика коммитов, которая была исправлена.

См. commit 8791bf1 (2 октября 2020 г.) от Деррик Столи (derrickstolee).
^{(объединено Хунио C Хамано -- gitster -- в commit c01b041, 05 октября 2020 г.)}

commit-reach: исправить ошибку in_merge_bases_many

^{Отчет: Шринидхи Кошик
Сопровождение: Йоханнес Шинделин
Подпись: Деррик Столи}

Еще в f9b8908b ([commit.c](https://github.com/git/git /blob/8791bf18414a37205127e184c04cad53a43aeff1/commit.c): используйте номера поколений для in_merge_bases(), 01 мая 2018 г., Git v2.19.0-rc0 -- слияние, указанное в пакете № 1 ), была использована эвристика, чтобы сократить обход in_merge_bases().
Это работает просто отлично, пока вызывающая сторона проверяет только две фиксации, но когда их несколько, есть вероятность, что эта эвристика очень неправильно.

С тех пор некоторые изменения кода изменили этот метод на repo_in_merge_bases_many() внутри commit-reach.c. Эвристика вычисляет минимальный номер поколения списка ссылок, а затем сравнивает это число с номером поколения фиксации.

В недавней теме был добавлен тест, который использовал in_merge_bases_many() для проверки доступности коммита из нескольких коммитов, извлеченных из журнала ссылок. Однако это выявило проблему: если какой-либо из эталонных коммитов имеет меньший номер поколения, чем данный коммит, то обход пропускается _even, если существуют коммиты с более высоким номером поколения_.

Эта эвристика неверна! Он должен проверять МАКСИМАЛЬНЫЙ номер поколения эталонных коммитов, а не МИНИМАЛЬНЫЙ.

Само исправление заключается в замене min_generation на max_generation в repo_in_merge_bases_many().

До Git 2.32 Hopefullu (1 квартал 2021 г.), когда определенные функции (например, трансплантаты), используемые в репозитории, несовместимы с использованием графика коммитов, мы отключали график коммитов; теперь мы сообщаем пользователю, что мы делаем.

См. commit c85eec7 (11 февраля 2021 г.) от Йоханнес Шинделин (dscho).
^{(объединено Хунио С. Хамано -- gitster -- в commit 726b11d, 17 февраля 2021 г.)}

Это покажет то, что было предназначено для Git 2.31, но это было отменено, поскольку немного переусердствует в его нынешнем виде.

commit-graph: при несовместимости с графиками укажите, почему

^{Подписано: Йоханнес Шинделин
Подтверждено: Деррик Столи}

Когда gc.writeCommitGraph = true, возможно, что график коммитов все еще не записан: объекты замены, трансплантаты и неглубокие репозитории несовместимы с функцией графа коммитов.

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

Предупреждения будут:

repository contains replace objects; skipping commit-graph
repository contains (deprecated) grafts; skipping commit-graph
repository is shallow; skipping commit-graph