Как мне найти дерево, которое ближе всего к другому дереву?

Question

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

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

Это звучит для меня как проблема вычисления «расстояний деревьев». Но поскольку у хэшей SHA1 нет метрики расстояния, есть ли другой способ сделать это, кроме очевидного ручного глубокого поиска при каждом коммите, чтобы выяснить, какой из них имеет наибольшее количество похожих BLOB-объектов?

ОБНОВЛЕНИЕ: см. Ниже, нашел способ сделать это для конкретного домена.

Answer 1

Спасибо за ответы!

Оказывается, мне повезло с моим конкретным приложением. Целевая система удаляет файл описания, который содержит файлы и номера версий, которые составляют текущее состояние ветви. Я фиксирую их, чтобы найти все эти такие файлы и использовать простую систему оценки, чтобы выяснить, насколько «близки» два из этих файлов друг к другу, положительные оценки означают, что у вас новее, а отрицательные - ветвь новее. Сопряжение со счетом, ближайшим к нулю, находит коммит, который больше всего похож на новую ветвь.

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

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

Answer 2

Один общий способ сделать это - создать файлы патчей для каждой из ветвей-кандидатов и посмотреть, какая из них самая маленькая.

Answer 3

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

Похоже, вам может понадобиться Vendor Branch для решения.

Answer 4

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

В надежде, что это редкое событие, я бы клонировал git-репозиторий и начал откатывать версии, чтобы найти коммит, ближайший к дереву, которое вы хотите дублировать. Было бы неплохо подумать об использовании git bisect для этого, но, поскольку нет полного упорядочения и нет абсолютной концепции good или bad, я не вижу, как избежать попытки каждого коммита.

Минимальное расстояние редактирования также NP-сложное, так что у вас настоящая боль в заднице здесь.

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