1#!/bin/sh
2#
3# Copyright (c) 2005 Junio C Hamano
4#
5
6test_description='Merge base and parent list computation.
7'
8
9. ./test-lib.sh
10
11M=1130000000
12Z=+0000
13
14GIT_COMMITTER_EMAIL=git@comm.iter.xz
15GIT_COMMITTER_NAME='C O Mmiter'
16GIT_AUTHOR_NAME='A U Thor'
17GIT_AUTHOR_EMAIL=git@au.thor.xz
18export GIT_COMMITTER_EMAIL GIT_COMMITTER_NAME GIT_AUTHOR_NAME GIT_AUTHOR_EMAIL
19
20doit () {
21	OFFSET=$1 &&
22	NAME=$2 &&
23	shift 2 &&
24
25	PARENTS= &&
26	for P
27	do
28		PARENTS="${PARENTS}-p $P "
29	done &&
30
31	GIT_COMMITTER_DATE="$(($M + $OFFSET)) $Z" &&
32	GIT_AUTHOR_DATE=$GIT_COMMITTER_DATE &&
33	export GIT_COMMITTER_DATE GIT_AUTHOR_DATE &&
34
35	commit=$(echo $NAME | git commit-tree $T $PARENTS) &&
36
37	git update-ref "refs/tags/$NAME" "$commit" &&
38	echo $commit
39}
40
41test_expect_success 'setup' '
42	T=$(git mktree </dev/null)
43'
44
45test_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'
60
61test_expect_success 'merge-base G H' '
62	git name-rev $B >expected &&
63
64	MB=$(git merge-base G H) &&
65	git name-rev "$MB" >actual.single &&
66
67	MB=$(git merge-base --all G H) &&
68	git name-rev "$MB" >actual.all &&
69
70	MB=$(git show-branch --merge-base G H) &&
71	git name-rev "$MB" >actual.sb &&
72
73	test_cmp expected actual.single &&
74	test_cmp expected actual.all &&
75	test_cmp expected actual.sb
76'
77
78test_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
98test_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) &&
134	PR=$(doit  4 PR $C2 $R2) &&
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'
147
148test_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
165test_expect_success 'merge-base for octopus-step (setup)' '
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 &&
186	git checkout MM1 &&
187	test_commit MM-r &&
188	test_commit MM-s &&
189	test_commit MM-t &&
190	test_commit MMB &&
191	git checkout MMR &&
192	test_commit MM-u &&
193	test_commit MM-v &&
194	test_commit MM-w &&
195	test_commit MM-x &&
196	test_commit MMC
197'
198
199test_expect_success 'merge-base A B C' '
200	git rev-parse --verify MM1 >expected &&
201	git rev-parse --verify MMR >expected.sb &&
202
203	git merge-base --all MMA MMB MMC >actual &&
204	git merge-base --all --octopus MMA MMB MMC >actual.common &&
205	git show-branch --merge-base MMA MMB MMC >actual.sb &&
206
207	test_cmp expected actual &&
208	test_cmp expected.sb actual.common &&
209	test_cmp expected.sb actual.sb
210'
211
212test_expect_success 'criss-cross merge-base for octopus-step' '
213	git reset --hard MMR &&
214	test_commit CC1 &&
215	git reset --hard E &&
216	test_commit CC2 &&
217	test_tick &&
218	# E is a root commit unrelated to MMR root on which CC1 is based
219	git merge -s ours --allow-unrelated-histories CC1 &&
220	test_commit CC-o &&
221	test_commit CCB &&
222	git reset --hard CC1 &&
223	# E is a root commit unrelated to MMR root on which CC1 is based
224	git merge -s ours --allow-unrelated-histories CC2 &&
225	test_commit CCA &&
226
227	git rev-parse CC1 CC2 >expected &&
228	git merge-base --all CCB CCA^^ CCA^^2 >actual &&
229
230	sort expected >expected.sorted &&
231	sort actual >actual.sorted &&
232	test_cmp expected.sorted actual.sorted
233'
234
235test_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
248		done &&
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
263test_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
269test_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
308test_done
309