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

Question

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

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

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

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

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

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

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

Введите:

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

Выход:

• Мне нужно будет линеаризовать эти коммиты в топологическом порядке. То есть, коммит не может быть указан после того, как были перечислены его родители.
• Мне также нужны «ветки», которые можно увидеть на скриншоте выше. Это, вероятно, необходимо предварительно вычислить, так как большинство из них зависят от своих детей.

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

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

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

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

В любом случае, надеюсь, это поможет. Интересно было хотя бы подумать.

Answer 3

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

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

Answer 4

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

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