Инкрементальная линеаризация git DAG

Я автор GitX. Одна из особенностей GitX - это визуализация ветвей, как можно видеть здесь.

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

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

Однако я не знаю, какой алгоритм использовать для этого. Важно, чтобы здание было инкрементным, так как загрузка коммитов может занять много времени ( > 5 секунд для 100 000 коммитов, которые все должны отображаться).

Gitk пошел тем же путем, и там патч здесь, который показывает, как он реализован, но мой TCL-навыки слабы, и патч не очень тщательно прокомментирован и немного трудно следовать.

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

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

Input:

У меня есть текущий пул коммитов в виде хеш-таблицы, которая отображает идентификаторы фиксации для фиксации объектов. Этот пул не должен быть полным (все обязательные для заполнения)
У меня есть отдельная загрузка потока в новых коммитах из git, с обратным вызовом, который можно вызывать каждый раз при загрузке нового коммита. Нет гарантированного порядка, в котором совершаются коммиты, но в большинстве случаев следующая фиксация является родителем предыдущего коммита.
Объект фиксации имеет свой собственный идентификатор ревизии и идентификаторы ревизий всех его родителей.
У меня есть список заголовков веток, которые должны быть перечислены. То есть, нет ни одного "верхнего" DAG, который должен отображаться. Там также не обязательно должен быть один корень графа.

Вывод:

Мне нужно линеаризовать эти коммиты в топологическом порядке. То есть, фиксация не может быть указана после того, как ее родители были перечислены.
Мне также нужны "ветки", которые можно увидеть на скриншоте выше. Вероятно, они должны быть предварительно вычислены, поскольку большинство из них зависит от их детей.

Несколько замечаний:

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

Ответ 1

Стандартная топологическая сортировка - это O (n) (OK, O (V + E)), то есть вы должны иметь возможность сортировать миллион задерживается в памяти за долю секунды. Никакой инкрементный взломать, как в Tcl, не требуется.

Кстати, я использую GitX (выглядит намного лучше, чем Gitk на OS X) каждый день, и у меня нет никаких проблем (возможно, потому, что у меня нет этих сумасшедших слияний в моих репозиториях):)

Ответ 2

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

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

Это приводит к некоторой сложности с точки зрения нахождения дуги при чтении нового коммита. Есть несколько ситуаций:

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

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

Как только у вас появятся эти дуги, вы все равно останетесь с линеаризацией. В вашем случае первый алгоритм, описанный на вышеупомянутой странице Wikipedia, звучит полезно, так как у вас есть известный набор точек ветвления для использования в качестве начального установите S.

Другие примечания:

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

В любом случае, я надеюсь, что это поможет. Было интересно подумать, по крайней мере.

Ответ 3

Вам действительно нужно отображать 100 000 коммитов одновременно? Какой пользователь может впитать такую информацию?

Вы думали о пейджинге? Я просто вычислил за ~ 100 коммитов или что-то в этом роде. Если ветка идет назад (за пределами страницы), вы можете использовать что-то вроде стрелки с указателем Github, чтобы показать это.

Ответ 4

Я не использовал GitX, так что, возможно, я что-то пропустил, но похоже, что вы могли бы вернуться от ребенка к родительскому (-ым) из головы каждой текущей ветки, пока не сможете нарисовать несколько экранов графика,

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