Какой простой способ проверить, не связаны ли два git-репозитория?

Question

Какой простой способ проверить, не связаны ли два git-репозитория?

Например, давайте предположим, что мы клонировали следующие репозитории:

• https://github.com/spring-petclinic/spring-framework-petclinic
• https://github.com/spring-projects/spring-petclinic

Как я могу проверить, что один не делится историей с другим?

Как я могу проверить, что один общий частичный журнал с другим? Как я могу просмотреть общий DAG и просмотреть разницу?

Примечание: Git позволяет мелкое копирование + история репозиториев может расходиться со временем ...

Answer 1

Легко доказать, что два репозитория связаны : если они содержат совпадающие коммиты - коммиты с одинаковыми хэш-идентификаторами и содержимым, хотя обычно достаточно "одинаковых хеш-идентификаторов" ¹ - они связаны.

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

Если у вас есть оба репозитория и вы убедитесь, что оба они завершены, просто перечислите все идентификаторы хеша фиксации в обоих репозиториях и найдите общие идентификаторы. Если общие идентификаторы существуют, оба, вероятно, связаны между собой. Чтобы перечислить все идентификаторы хэша фиксации, запустите git rev-list --all (перенаправить вывод в файл или в программу, которая считывает оба набора выходных данных и проверяет общие идентификаторы хэша).

См. Сноску 1 для исключения слова «вероятно», но TL; DR - это то, что на данный момент любые два идентичных идентификатора означают общую историю.

---

¹ При заданной равномерной хеш-функции h (k) с диапазоном r = | {h (k) | , вероятность случайного столкновения хэшей для двух разных ключей k ₁ , k ₂ равно p = 1 / r . Вероятность уникальности является дополнением к этому p̄ = 1 - (1 / r) . Обобщая до n ключей и используя двухчленное расширение Тейлора e ^x ≈ 1 + x для x ≪ 1 , мы получаем p̄ ≈ e ^{(- n (n-1)) / 2r} , если r достаточно велико.

Хэш-функцией Git в настоящее время является SHA1, которая имеет довольно равномерное распределение и имеет r = 2 ¹⁶⁰ = 1461501637330902918203684832716283019655932542976. Это удовлетворяет нашей формуле, что означает, что мы можем использовать приближение.

Следовательно, если вы суммируете общее количество хэшей n и включите его в формулу:

r=1461501637330902918203684832716283019655932542976
1 - exp(-n*(n-1)/(2*r))

(помните, мы хотим p, а не p-bar), Вы получаете вероятность столкновения. Конечно, чтобы проверить фактическое столкновение, вы можете просто сравнить лежащие в основе фактические объекты: если хэши совпадают, сравните объекты напрямую, чтобы обнаружить столкновение. Но это крайне маловероятно, во-первых. Если мы берем два репозитория, которые вместе содержат десять миллионов коммитов, мы вычисляем:

$ bc -l
r=2^160
n=10*1000*1000
scale=100
1 - e(-n*(n-1)/(2*r))
.0000000000000000000000000000000000342113848680412753525884397196522\
895097282878872708411144841034243

, который, как вы можете видеть, все еще довольно крошечный. Пока мы не доберемся до:

n=10*1000*1000*1000*1000*1000*1000*1000

(десять секстиллионных объектов, используя краткую запись)

что мы находим:

1 - e(-n*(n-1)/(2*r))
.0000342108030863093209851036344159518189002166758764416221121344549\
079733424124497666779807175655625

заметный шанс случайного столкновения, около 0,0035%. На 100 объектах секстиллиона у нас вероятность 0,35%:

n=100*1000*1000*1000*1000*1000*1000*1000
1 - e(-n*(n-1)/(2*r))
.0034152934013810288444649336362559390942558976421984312395097770719\
923433072593638116228277476790795

и из-за 1 септиллиона объектов мы сталкиваемся с серьезными рисками:

1 - e(-n*(n-1)/(2*r))
.2897326871923714506502211457721853341644126909116947422293621066225\
555385326652788789421475224989232

К счастью, задолго до этого у нас закончилось место на диске. :-) Кроме того, ребята из Git думают о переходе на один из хэшей SHA-256, который увеличит r до 2 ²⁵⁶ , что помогает нашему знаменателю.

(я использую bc выше, в котором ^ - возведение в степень, а библиотека -l добавляет e(x) для вычисления e ^x .)

Answer 2

Чтобы найти какие-либо общие ревизии:

comm -12 <(cd repo1; git rev-list --all | sort) <(cd repo2; git rev-list --all | sort)

В моем случае оба хранилища делятся коммитами:

bash# (cd spring-petclinic; git rev-list --all) | wc -l
670

bash# (cd spring-framework-petclinic; git rev-list --all) | wc -l
571

bash# comm -12 <(cd spring-framework-petclinic/; git rev-list --all | sort) <(cd spring-petclinic; git rev-list --all | sort) | wc -l
427

Answer 3

Вы можете клонировать первый, а затем добавить второй как дополнительный пульт:

git clone https://github.com/spring-petclinic/spring-framework-petclinic
cd spring-framework-petclinic
git remote add other https://github.com/spring-projects/spring-petclinic
git fetch --all

Затем вы можете просмотреть оба DAG:

git log --graph --all --oneline --decorate

И посмотрите, есть ли у них общая история, посмотрев на базу слияния двух стволов:

git merge-base origin/master other/master