Подтвердить что ты не робот

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

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

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

Может ли кто-нибудь написать какой-нибудь псевдокод, который его демонстрирует?

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Для каждого фиксации:

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

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

Пример

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

Ответ 2

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

Для hg вы пытались выполнить код в самом hg или в graphlog?

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

Ответ 3

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

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

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

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

Ответ 4

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

Понятие коммитов действительно меняет работу 'git log --graph'.

Как упоминалось здесь mentioned here:

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) ) . (Merged by Junio C Hamano -- [TG43] -- in commit b10edb2, 08 May 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 г.), коммит 1472978, коммит 7adf526, коммит 04bc8d1, коммит d7c1ec3, commit f9b8908, commit 819807b, commit e2838d8, commit 3afc679, commit 3258c66(01 мая 2018 г.) и зафиксировать 83073cc, зафиксировать 8fb572a(25 апреля 2018 г.) Дерриком Столи (derrickstolee). Помощник: Джефф Кинг (peff)
. (Merged by Junio C Hamano -- [TG412] -- in commit a856e7d, 25 Jun 2018) commit-graph: исправлена проблема с UX при наличии файла .lock
Мы используем API-интерфейс lockfile, чтобы избежать записи в несколько процессов Git файл графика фиксации в каталоге .git/objects/info

.

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

Если это не удается, попробуйте создать каталог .git/object/info.

  1. Попробуйте получить блокировку, если это не удалось.
  2. Проблема в том, что если файл блокировки существует, то mkdir не работает, давая ошибка, которая не помогает пользователю:
  3. "fatal: cannot mkdir .git/objects/info: File exists"

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

Instead, do the following:

Проверьте наличие .git/objects/info; создать при необходимости.

Попробуйте получить блокировку, если это не удалось.
  1. Новый вывод выглядит так:
  2. fatal: Unable to create
'<dir>/.git/objects/info/commit-graph.lock': File exists.

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

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

См.

коммит 4468d44

(27 января 2019 года) SZEDER Gábor (szeder). (Merged by Junio C Hamano -- [TG421] -- in commit 2ed3de4, 05 Feb 2019) Этот алгоритм подвергается рефакторингу в Git 2.23 (Q3 2019).
См.

commit 238def5

commit f998d54, commit 014e344, commit b2c8306, commit 4c9efe8, commit ef5b83f, коммит c9905be, коммит 10bd0be, коммит 5af8039, коммит e103f72(12 июня 2019 г.) и зафиксировать c794405 (09 мая 2019 года) Дерриком Столи (derrickstolee). (Merged by Junio C Hamano -- [TG423] -- in commit e116894, 09 Jul 2019) Фиксация 10bd0be
объясняет изменение области видимости.

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

коммит 7c5c9b9

коммит 39d8831, коммит 9916073(05 августа 2019 г.) от SZEDER Gábor (szeder). . (Merged by Junio C Hamano -- [TG426] -- in commit 6ba06b5, 22 Aug 2019)
И все же с Git 2.24 (Q4 2019) код для анализа и использования файла commit-graph был сделан более устойчивым к поврежденному вводу.

Смотрите

коммит 806278d , коммит 16749b8 , коммит 23424ea (05 сентября 2019 г.) от Тейлор Блау (ttaylorr) ..
(Merged by Junio C Hamano -- [TG428] -- in commit 80693e3, 07 Oct 2019)

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

При вызове "git commit-graph" в поврежденном хранилище может возникнуть ошибка по умолчанию, когда наследственные коммиты так или иначе повреждены.
Это связано с двумя вызовами функций в коде "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(), чтобы избежать передачи непарсированного объекта в функцию, которая ожидает анализируемый объект, таким образом предотвращая segfault.