[thirdparty/git.git] / t / t6010-merge-base.sh

#!/bin/sh
#
# Copyright (c) 2005 Junio C Hamano
#

test_description='Merge base and parent list computation.
'

. ./test-lib.sh

M=1130000000
Z=+0000

GIT_COMMITTER_EMAIL=git@comm.iter.xz
GIT_COMMITTER_NAME='C O Mmiter'
GIT_AUTHOR_NAME='A U Thor'
GIT_AUTHOR_EMAIL=git@au.thor.xz
export GIT_COMMITTER_EMAIL GIT_COMMITTER_NAME GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL

doit () {
	OFFSET=$1 &&
	NAME=$2 &&
	shift 2 &&

	PARENTS= &&
	for P
	do
		PARENTS="${PARENTS}-p $P "
	done &&

	GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z" &&
	GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE &&
	export GIT_COMMITTER_DATE GIT_AUTHOR_DATE &&

	commit=$(echo $NAME | git commit-tree $T $PARENTS) &&

	git update-ref "refs/tags/$NAME" "$commit" &&
	echo $commit
}

test_expect_success 'setup' '
	T=$(git mktree </dev/null)
'

test_expect_success 'set up G and H' '
	# E---D---C---B---A
	# \"-_         \   \
	#  \  `---------G   \
	#   \                \
	#    F----------------H
	E=$(doit 5 E) &&
	D=$(doit 4 D $E) &&
	F=$(doit 6 F $E) &&
	C=$(doit 3 C $D) &&
	B=$(doit 2 B $C) &&
	A=$(doit 1 A $B) &&
	G=$(doit 7 G $B $E) &&
	H=$(doit 8 H $A $F)
'

test_expect_success 'merge-base G H' '
	git name-rev $B >expected &&

	MB=$(git merge-base G H) &&
	git name-rev "$MB" >actual.single &&

	MB=$(git merge-base --all G H) &&
	git name-rev "$MB" >actual.all &&

	MB=$(git show-branch --merge-base G H) &&
	git name-rev "$MB" >actual.sb &&

	test_cmp expected actual.single &&
	test_cmp expected actual.all &&
	test_cmp expected actual.sb
'

test_expect_success 'merge-base/show-branch --independent' '
	git name-rev "$H" >expected1 &&
	git name-rev "$H" "$G" >expected2 &&

	parents=$(git merge-base --independent H) &&
	git name-rev $parents >actual1.mb &&
	parents=$(git merge-base --independent A H G) &&
	git name-rev $parents >actual2.mb &&

	parents=$(git show-branch --independent H) &&
	git name-rev $parents >actual1.sb &&
	parents=$(git show-branch --independent A H G) &&
	git name-rev $parents >actual2.sb &&

	test_cmp expected1 actual1.mb &&
	test_cmp expected2 actual2.mb &&
	test_cmp expected1 actual1.sb &&
	test_cmp expected2 actual2.sb
'

test_expect_success 'unsynchronized clocks' '
	# This test is to demonstrate that relying on timestamps in a distributed
	# SCM to provide a _consistent_ partial ordering of commits leads to
	# insanity.
	#
	#               Relative
	# Structure     timestamps
	#
	#   PL  PR        +4  +4
	#  /  \/  \      /  \/  \
	# L2  C2  R2    +3  -1  +3
	# |   |   |     |   |   |
	# L1  C1  R1    +2  -2  +2
	# |   |   |     |   |   |
	# L0  C0  R0    +1  -3  +1
	#   \ |  /        \ |  /
	#     S             0
	#
	# The left and right chains of commits can be of any length and complexity as
	# long as all of the timestamps are greater than that of S.

	S=$(doit  0 S) &&

	C0=$(doit -3 C0 $S) &&
	C1=$(doit -2 C1 $C0) &&
	C2=$(doit -1 C2 $C1) &&

	L0=$(doit  1 L0 $S) &&
	L1=$(doit  2 L1 $L0) &&
	L2=$(doit  3 L2 $L1) &&

	R0=$(doit  1 R0 $S) &&
	R1=$(doit  2 R1 $R0) &&
	R2=$(doit  3 R2 $R1) &&

	PL=$(doit  4 PL $L2 $C2) &&
	PR=$(doit  4 PR $C2 $R2) &&

	git name-rev $C2 >expected &&

	MB=$(git merge-base PL PR) &&
	git name-rev "$MB" >actual.single &&

	MB=$(git merge-base --all PL PR) &&
	git name-rev "$MB" >actual.all &&

	test_cmp expected actual.single &&
	test_cmp expected actual.all
'

test_expect_success '--independent with unsynchronized clocks' '
	IB=$(doit 0 IB) &&
	I1=$(doit -10 I1 $IB) &&
	I2=$(doit  -9 I2 $I1) &&
	I3=$(doit  -8 I3 $I2) &&
	I4=$(doit  -7 I4 $I3) &&
	I5=$(doit  -6 I5 $I4) &&
	I6=$(doit  -5 I6 $I5) &&
	I7=$(doit  -4 I7 $I6) &&
	I8=$(doit  -3 I8 $I7) &&
	IH=$(doit  -2 IH $I8) &&

	echo $IH >expected &&
	git merge-base --independent IB IH >actual &&
	test_cmp expected actual
'

test_expect_success 'merge-base for octopus-step (setup)' '
	# Another set to demonstrate base between one commit and a merge
	# in the documentation.
	#
	# * C (MMC) * B (MMB) * A  (MMA)
	# * o       * o       * o
	# * o       * o       * o
	# * o       * o       * o
	# * o       | _______/
	# |         |/
	# |         * 1 (MM1)
	# | _______/
	# |/
	# * root (MMR)

	test_commit MMR &&
	test_commit MM1 &&
	test_commit MM-o &&
	test_commit MM-p &&
	test_commit MM-q &&
	test_commit MMA &&
	git checkout MM1 &&
	test_commit MM-r &&
	test_commit MM-s &&
	test_commit MM-t &&
	test_commit MMB &&
	git checkout MMR &&
	test_commit MM-u &&
	test_commit MM-v &&
	test_commit MM-w &&
	test_commit MM-x &&
	test_commit MMC
'

test_expect_success 'merge-base A B C' '
	git rev-parse --verify MM1 >expected &&
	git rev-parse --verify MMR >expected.sb &&

	git merge-base --all MMA MMB MMC >actual &&
	git merge-base --all --octopus MMA MMB MMC >actual.common &&
	git show-branch --merge-base MMA MMB MMC >actual.sb &&

	test_cmp expected actual &&
	test_cmp expected.sb actual.common &&
	test_cmp expected.sb actual.sb
'

test_expect_success 'criss-cross merge-base for octopus-step' '
	git reset --hard MMR &&
	test_commit CC1 &&
	git reset --hard E &&
	test_commit CC2 &&
	test_tick &&
	# E is a root commit unrelated to MMR root on which CC1 is based
	git merge -s ours --allow-unrelated-histories CC1 &&
	test_commit CC-o &&
	test_commit CCB &&
	git reset --hard CC1 &&
	# E is a root commit unrelated to MMR root on which CC1 is based
	git merge -s ours --allow-unrelated-histories CC2 &&
	test_commit CCA &&

	git rev-parse CC1 CC2 >expected &&
	git merge-base --all CCB CCA^^ CCA^^2 >actual &&

	sort expected >expected.sorted &&
	sort actual >actual.sorted &&
	test_cmp expected.sorted actual.sorted
'

test_expect_success 'using reflog to find the fork point' '
	git reset --hard &&
	git checkout -b base $E &&

	(
		for count in 1 2 3
		do
			git commit --allow-empty -m "Base commit #$count" &&
			git rev-parse HEAD >expect$count &&
			git checkout -B derived &&
			git commit --allow-empty -m "Derived #$count" &&
			git rev-parse HEAD >derived$count &&
			git checkout -B base $E || exit 1
		done &&

		for count in 1 2 3
		do
			git merge-base --fork-point base $(cat derived$count) >actual &&
			test_cmp expect$count actual || exit 1
		done

	) &&
	# check that we correctly default to HEAD
	git checkout derived &&
	git merge-base --fork-point base >actual &&
	test_cmp expect3 actual
'

test_expect_success '--fork-point works with empty reflog' '
	git -c core.logallrefupdates=false branch no-reflog base &&
	git merge-base --fork-point no-reflog derived &&
	test_cmp expect3 actual
'

test_expect_success 'merge-base --octopus --all for complex tree' '
	# Best common ancestor for JE, JAA and JDD is JC
	#             JE
	#            / |
	#           /  |
	#          /   |
	#  JAA    /    |
	#   |\   /     |
	#   | \  | JDD |
	#   |  \ |/ |  |
	#   |   JC JD  |
	#   |    | /|  |
	#   |    |/ |  |
	#  JA    |  |  |
	#   |\  /|  |  |
	#   X JB |  X  X
	#   \  \ | /   /
	#    \__\|/___/
	#        J
	test_commit J &&
	test_commit JB &&
	git reset --hard J &&
	test_commit JC &&
	git reset --hard J &&
	test_commit JTEMP1 &&
	test_merge JA JB &&
	test_merge JAA JC &&
	git reset --hard J &&
	test_commit JTEMP2 &&
	test_merge JD JB &&
	test_merge JDD JC &&
	git reset --hard J &&
	test_commit JTEMP3 &&
	test_merge JE JC &&
	git rev-parse JC >expected &&
	git merge-base --all --octopus JAA JDD JE >actual &&
	test_cmp expected actual
'

test_done
Commit	Line	Data
53de71f8 JH	1	#!/bin/sh
	2	#
	3	# Copyright (c) 2005 Junio C Hamano
	4	#
	5
a1e0ad78	6	test_description='Merge base and parent list computation.
53de71f8 JH	7	'
	8
	9	. ./test-lib.sh
	10
73151df0 JN	11	M=1130000000
73151df0 JN	12	Z=+0000
9cbdd76e	13
73151df0 JN	14	GIT_COMMITTER_EMAIL=git@comm.iter.xz
	15	GIT_COMMITTER_NAME='C O Mmiter'
	16	GIT_AUTHOR_NAME='A U Thor'
	17	GIT_AUTHOR_EMAIL=git@au.thor.xz
	18	export GIT_COMMITTER_EMAIL GIT_COMMITTER_NAME GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL
9cbdd76e	19
73151df0 JN	20	doit () {
	21	OFFSET=$1 &&
	22	NAME=$2 &&
	23	shift 2 &&
9cbdd76e	24
73151df0 JN	25	PARENTS= &&
	26	for P
	27	do
	28	PARENTS="${PARENTS}-p $P "
	29	done &&
9cbdd76e	30
73151df0 JN	31	GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z" &&
	32	GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE &&
	33	export GIT_COMMITTER_DATE GIT_AUTHOR_DATE &&
9cbdd76e	34
73151df0	35	commit=$(echo $NAME \| git commit-tree $T $PARENTS) &&
9cbdd76e	36
cbc5cf7c	37	git update-ref "refs/tags/$NAME" "$commit" &&
73151df0 JN	38	echo $commit
73151df0 JN	39	}
9cbdd76e	40
73151df0 JN	41	test_expect_success 'setup' '
73151df0 JN	42	T=$(git mktree </dev/null)
9cbdd76e	43	'
cd6f207a	44
9cbdd76e JN	45	test_expect_success 'set up G and H' '
	46	# E---D---C---B---A
	47	# \"-_ \ \
	48	# \ `---------G \
	49	# \ \
	50	# F----------------H
	51	E=$(doit 5 E) &&
	52	D=$(doit 4 D $E) &&
	53	F=$(doit 6 F $E) &&
	54	C=$(doit 3 C $D) &&
	55	B=$(doit 2 B $C) &&
	56	A=$(doit 1 A $B) &&
	57	G=$(doit 7 G $B $E) &&
	58	H=$(doit 8 H $A $F)
	59	'
cd6f207a	60
9cbdd76e JN	61	test_expect_success 'merge-base G H' '
9cbdd76e JN	62	git name-rev $B >expected &&
cd6f207a	63
9cbdd76e JN	64	MB=$(git merge-base G H) &&
9cbdd76e JN	65	git name-rev "$MB" >actual.single &&
cd6f207a	66
9cbdd76e JN	67	MB=$(git merge-base --all G H) &&
9cbdd76e JN	68	git name-rev "$MB" >actual.all &&
cd6f207a	69
9cbdd76e JN	70	MB=$(git show-branch --merge-base G H) &&
9cbdd76e JN	71	git name-rev "$MB" >actual.sb &&
cd6f207a	72
9cbdd76e JN	73	test_cmp expected actual.single &&
	74	test_cmp expected actual.all &&
	75	test_cmp expected actual.sb
	76	'
30ca4ca7	77
a1e0ad78 JN	78	test_expect_success 'merge-base/show-branch --independent' '
	79	git name-rev "$H" >expected1 &&
	80	git name-rev "$H" "$G" >expected2 &&
	81
	82	parents=$(git merge-base --independent H) &&
	83	git name-rev $parents >actual1.mb &&
	84	parents=$(git merge-base --independent A H G) &&
	85	git name-rev $parents >actual2.mb &&
	86
	87	parents=$(git show-branch --independent H) &&
	88	git name-rev $parents >actual1.sb &&
	89	parents=$(git show-branch --independent A H G) &&
	90	git name-rev $parents >actual2.sb &&
	91
	92	test_cmp expected1 actual1.mb &&
	93	test_cmp expected2 actual2.mb &&
	94	test_cmp expected1 actual1.sb &&
	95	test_cmp expected2 actual2.sb
	96	'
	97
9cbdd76e JN	98	test_expect_success 'unsynchronized clocks' '
	99	# This test is to demonstrate that relying on timestamps in a distributed
	100	# SCM to provide a _consistent_ partial ordering of commits leads to
	101	# insanity.
	102	#
	103	# Relative
	104	# Structure timestamps
	105	#
	106	# PL PR +4 +4
	107	# / \/ \ / \/ \
	108	# L2 C2 R2 +3 -1 +3
	109	# \| \| \| \| \| \|
	110	# L1 C1 R1 +2 -2 +2
	111	# \| \| \| \| \| \|
	112	# L0 C0 R0 +1 -3 +1
	113	# \ \| / \ \| /
	114	# S 0
	115	#
	116	# The left and right chains of commits can be of any length and complexity as
	117	# long as all of the timestamps are greater than that of S.
	118
	119	S=$(doit 0 S) &&
	120
	121	C0=$(doit -3 C0 $S) &&
	122	C1=$(doit -2 C1 $C0) &&
	123	C2=$(doit -1 C2 $C1) &&
	124
	125	L0=$(doit 1 L0 $S) &&
	126	L1=$(doit 2 L1 $L0) &&
	127	L2=$(doit 3 L2 $L1) &&
	128
	129	R0=$(doit 1 R0 $S) &&
	130	R1=$(doit 2 R1 $R0) &&
	131	R2=$(doit 3 R2 $R1) &&
	132
	133	PL=$(doit 4 PL $L2 $C2) &&
a48fcd83	134	PR=$(doit 4 PR $C2 $R2) &&
9cbdd76e JN	135
	136	git name-rev $C2 >expected &&
	137
	138	MB=$(git merge-base PL PR) &&
	139	git name-rev "$MB" >actual.single &&
	140
	141	MB=$(git merge-base --all PL PR) &&
	142	git name-rev "$MB" >actual.all &&
	143
	144	test_cmp expected actual.single &&
	145	test_cmp expected actual.all
	146	'
a7a66921	147
a1e0ad78 JN	148	test_expect_success '--independent with unsynchronized clocks' '
	149	IB=$(doit 0 IB) &&
	150	I1=$(doit -10 I1 $IB) &&
	151	I2=$(doit -9 I2 $I1) &&
	152	I3=$(doit -8 I3 $I2) &&
	153	I4=$(doit -7 I4 $I3) &&
	154	I5=$(doit -6 I5 $I4) &&
	155	I6=$(doit -5 I6 $I5) &&
	156	I7=$(doit -4 I7 $I6) &&
	157	I8=$(doit -3 I8 $I7) &&
	158	IH=$(doit -2 IH $I8) &&
	159
	160	echo $IH >expected &&
	161	git merge-base --independent IB IH >actual &&
	162	test_cmp expected actual
	163	'
	164
a7a66921	165	test_expect_success 'merge-base for octopus-step (setup)' '
9cbdd76e JN	166	# Another set to demonstrate base between one commit and a merge
	167	# in the documentation.
	168	#
	169	# * C (MMC) * B (MMB) * A (MMA)
	170	# * o * o * o
	171	# * o * o * o
	172	# * o * o * o
	173	# * o \| _______/
	174	# \| \|/
	175	# \| * 1 (MM1)
	176	# \| _______/
	177	# \|/
	178	# * root (MMR)
	179
	180	test_commit MMR &&
	181	test_commit MM1 &&
	182	test_commit MM-o &&
	183	test_commit MM-p &&
	184	test_commit MM-q &&
	185	test_commit MMA &&
a7a66921	186	git checkout MM1 &&
9cbdd76e JN	187	test_commit MM-r &&
	188	test_commit MM-s &&
	189	test_commit MM-t &&
	190	test_commit MMB &&
a7a66921	191	git checkout MMR &&
9cbdd76e JN	192	test_commit MM-u &&
	193	test_commit MM-v &&
	194	test_commit MM-w &&
	195	test_commit MM-x &&
	196	test_commit MMC
a7a66921 JH	197	'
	198
	199	test_expect_success 'merge-base A B C' '
9cbdd76e JN	200	git rev-parse --verify MM1 >expected &&
9cbdd76e JN	201	git rev-parse --verify MMR >expected.sb &&
a7a66921	202
9cbdd76e	203	git merge-base --all MMA MMB MMC >actual &&
aa8f98c1	204	git merge-base --all --octopus MMA MMB MMC >actual.common &&
9cbdd76e JN	205	git show-branch --merge-base MMA MMB MMC >actual.sb &&
	206
	207	test_cmp expected actual &&
aa8f98c1	208	test_cmp expected.sb actual.common &&
9cbdd76e	209	test_cmp expected.sb actual.sb
f621a845 MG	210	'
f621a845 MG	211
9cbdd76e	212	test_expect_success 'criss-cross merge-base for octopus-step' '
a7a66921	213	git reset --hard MMR &&
9cbdd76e	214	test_commit CC1 &&
a7a66921	215	git reset --hard E &&
9cbdd76e JN	216	test_commit CC2 &&
9cbdd76e JN	217	test_tick &&
e379fdf3 JH	218	# E is a root commit unrelated to MMR root on which CC1 is based
e379fdf3 JH	219	git merge -s ours --allow-unrelated-histories CC1 &&
9cbdd76e JN	220	test_commit CC-o &&
9cbdd76e JN	221	test_commit CCB &&
a7a66921	222	git reset --hard CC1 &&
e379fdf3 JH	223	# E is a root commit unrelated to MMR root on which CC1 is based
e379fdf3 JH	224	git merge -s ours --allow-unrelated-histories CC2 &&
9cbdd76e JN	225	test_commit CCA &&
	226
	227	git rev-parse CC1 CC2 >expected &&
	228	git merge-base --all CCB CCA^^ CCA^^2 >actual &&
a7a66921	229
9cbdd76e JN	230	sort expected >expected.sorted &&
	231	sort actual >actual.sorted &&
	232	test_cmp expected.sorted actual.sorted
a7a66921 JH	233	'
a7a66921 JH	234
d96855ff JH	235	test_expect_success 'using reflog to find the fork point' '
	236	git reset --hard &&
	237	git checkout -b base $E &&
	238
	239	(
	240	for count in 1 2 3
	241	do
	242	git commit --allow-empty -m "Base commit #$count" &&
	243	git rev-parse HEAD >expect$count &&
	244	git checkout -B derived &&
	245	git commit --allow-empty -m "Derived #$count" &&
	246	git rev-parse HEAD >derived$count &&
	247	git checkout -B base $E \|\| exit 1
c8ce3763	248	done &&
d96855ff JH	249
	250	for count in 1 2 3
	251	do
	252	git merge-base --fork-point base $(cat derived$count) >actual &&
	253	test_cmp expect$count actual \|\| exit 1
	254	done
	255
	256	) &&
	257	# check that we correctly default to HEAD
	258	git checkout derived &&
	259	git merge-base --fork-point base >actual &&
	260	test_cmp expect3 actual
	261	'
	262
4f21454b JK	263	test_expect_success '--fork-point works with empty reflog' '
	264	git -c core.logallrefupdates=false branch no-reflog base &&
	265	git merge-base --fork-point no-reflog derived &&
	266	test_cmp expect3 actual
	267	'
	268
8f292991 JH	269	test_expect_success 'merge-base --octopus --all for complex tree' '
	270	# Best common ancestor for JE, JAA and JDD is JC
	271	# JE
	272	# / \|
	273	# / \|
	274	# / \|
	275	# JAA / \|
	276	# \|\ / \|
	277	# \| \ \| JDD \|
	278	# \| \ \|/ \| \|
	279	# \| JC JD \|
	280	# \| \| /\| \|
	281	# \| \|/ \| \|
	282	# JA \| \| \|
	283	# \|\ /\| \| \|
	284	# X JB \| X X
	285	# \ \ \| / /
	286	# \__\\|/___/
	287	# J
	288	test_commit J &&
	289	test_commit JB &&
	290	git reset --hard J &&
	291	test_commit JC &&
	292	git reset --hard J &&
	293	test_commit JTEMP1 &&
	294	test_merge JA JB &&
	295	test_merge JAA JC &&
	296	git reset --hard J &&
	297	test_commit JTEMP2 &&
	298	test_merge JD JB &&
	299	test_merge JDD JC &&
	300	git reset --hard J &&
	301	test_commit JTEMP3 &&
	302	test_merge JE JC &&
	303	git rev-parse JC >expected &&
	304	git merge-base --all --octopus JAA JDD JE >actual &&
	305	test_cmp expected actual
	306	'
	307
53de71f8	308	test_done