1#!/bin/sh
2test_description='basic commit reachability tests'
4. ./test-lib.sh
6# Construct a grid-like commit graph with points (x,y)
8# with 1 <= x <= 10, 1 <= y <= 10, where (x,y) has
9# parents (x-1, y) and (x, y-1), keeping in mind that
10# we drop a parent if a coordinate is nonpositive.
11#
12# (10,10)
13# / \
14# (10,9) (9,10)
15# / \ / \
16# (10,8) (9,9) (8,10)
17# / \ / \ / \
18# ( continued...)
19# \ / \ / \ /
20# (3,1) (2,2) (1,3)
21# \ / \ /
22# (2,1) (2,1)
23# \ /
24# (1,1)
25#
26# We use branch 'commit-x-y' to refer to (x,y).
27# This grid allows interesting reachability and
28# non-reachability queries: (x,y) can reach (x',y')
29# if and only if x' <= x and y' <= y.
30test_expect_success 'setup' '
31 for i in $(test_seq 1 10)
32 do
33 test_commit "1-$i" &&
34 git branch -f commit-1-$i &&
35 git tag -a -m "1-$i" tag-1-$i commit-1-$i
36 done &&
37 for j in $(test_seq 1 9)
38 do
39 git reset --hard commit-$j-1 &&
40 x=$(($j + 1)) &&
41 test_commit "$x-1" &&
42 git branch -f commit-$x-1 &&
43 git tag -a -m "$x-1" tag-$x-1 commit-$x-1 &&
44 for i in $(test_seq 2 10)
46 do
47 git merge commit-$j-$i -m "$x-$i" &&
48 git branch -f commit-$x-$i &&
49 git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i
50 done
51 done &&
52 git commit-graph write --reachable &&
53 mv .git/objects/info/commit-graph commit-graph-full &&
54 git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
55 mv .git/objects/info/commit-graph commit-graph-half &&
56 git config core.commitGraph true
57'
58run_three_modes () {
60 test_when_finished rm -rf .git/objects/info/commit-graph &&
61 "$@" <input >actual &&
62 test_cmp expect actual &&
63 cp commit-graph-full .git/objects/info/commit-graph &&
64 "$@" <input >actual &&
65 test_cmp expect actual &&
66 cp commit-graph-half .git/objects/info/commit-graph &&
67 "$@" <input >actual &&
68 test_cmp expect actual
69}
70test_three_modes () {
72 run_three_modes test-tool reach "$@"
73}
74test_expect_success 'ref_newer:miss' '
76 cat >input <<-\EOF &&
77 A:commit-5-7
78 B:commit-4-9
79 EOF
80 echo "ref_newer(A,B):0" >expect &&
81 test_three_modes ref_newer
82'
83test_expect_success 'ref_newer:hit' '
85 cat >input <<-\EOF &&
86 A:commit-5-7
87 B:commit-2-3
88 EOF
89 echo "ref_newer(A,B):1" >expect &&
90 test_three_modes ref_newer
91'
92test_expect_success 'in_merge_bases:hit' '
94 cat >input <<-\EOF &&
95 A:commit-5-7
96 B:commit-8-8
97 EOF
98 echo "in_merge_bases(A,B):1" >expect &&
99 test_three_modes in_merge_bases
100'
101test_expect_success 'in_merge_bases:miss' '
103 cat >input <<-\EOF &&
104 A:commit-6-8
105 B:commit-5-9
106 EOF
107 echo "in_merge_bases(A,B):0" >expect &&
108 test_three_modes in_merge_bases
109'
110test_expect_success 'is_descendant_of:hit' '
112 cat >input <<-\EOF &&
113 A:commit-5-7
114 X:commit-4-8
115 X:commit-6-6
116 X:commit-1-1
117 EOF
118 echo "is_descendant_of(A,X):1" >expect &&
119 test_three_modes is_descendant_of
120'
121test_expect_success 'is_descendant_of:miss' '
123 cat >input <<-\EOF &&
124 A:commit-6-8
125 X:commit-5-9
126 X:commit-4-10
127 X:commit-7-6
128 EOF
129 echo "is_descendant_of(A,X):0" >expect &&
130 test_three_modes is_descendant_of
131'
132test_expect_success 'get_merge_bases_many' '
134 cat >input <<-\EOF &&
135 A:commit-5-7
136 X:commit-4-8
137 X:commit-6-6
138 X:commit-8-3
139 EOF
140 {
141 echo "get_merge_bases_many(A,X):" &&
142 git rev-parse commit-5-6 \
143 commit-4-7 | sort
144 } >expect &&
145 test_three_modes get_merge_bases_many
146'
147test_expect_success 'reduce_heads' '
149 cat >input <<-\EOF &&
150 X:commit-1-10
151 X:commit-2-8
152 X:commit-3-6
153 X:commit-4-4
154 X:commit-1-7
155 X:commit-2-5
156 X:commit-3-3
157 X:commit-5-1
158 EOF
159 {
160 echo "reduce_heads(X):" &&
161 git rev-parse commit-5-1 \
162 commit-4-4 \
163 commit-3-6 \
164 commit-2-8 \
165 commit-1-10 | sort
166 } >expect &&
167 test_three_modes reduce_heads
168'
169test_expect_success 'can_all_from_reach:hit' '
171 cat >input <<-\EOF &&
172 X:commit-2-10
173 X:commit-3-9
174 X:commit-4-8
175 X:commit-5-7
176 X:commit-6-6
177 X:commit-7-5
178 X:commit-8-4
179 X:commit-9-3
180 Y:commit-1-9
181 Y:commit-2-8
182 Y:commit-3-7
183 Y:commit-4-6
184 Y:commit-5-5
185 Y:commit-6-4
186 Y:commit-7-3
187 Y:commit-8-1
188 EOF
189 echo "can_all_from_reach(X,Y):1" >expect &&
190 test_three_modes can_all_from_reach
191'
192test_expect_success 'can_all_from_reach:miss' '
194 cat >input <<-\EOF &&
195 X:commit-2-10
196 X:commit-3-9
197 X:commit-4-8
198 X:commit-5-7
199 X:commit-6-6
200 X:commit-7-5
201 X:commit-8-4
202 X:commit-9-3
203 Y:commit-1-9
204 Y:commit-2-8
205 Y:commit-3-7
206 Y:commit-4-6
207 Y:commit-5-5
208 Y:commit-6-4
209 Y:commit-8-5
210 EOF
211 echo "can_all_from_reach(X,Y):0" >expect &&
212 test_three_modes can_all_from_reach
213'
214test_expect_success 'can_all_from_reach_with_flag: tags case' '
216 cat >input <<-\EOF &&
217 X:tag-2-10
218 X:tag-3-9
219 X:tag-4-8
220 X:commit-5-7
221 X:commit-6-6
222 X:commit-7-5
223 X:commit-8-4
224 X:commit-9-3
225 Y:tag-1-9
226 Y:tag-2-8
227 Y:tag-3-7
228 Y:commit-4-6
229 Y:commit-5-5
230 Y:commit-6-4
231 Y:commit-7-3
232 Y:commit-8-1
233 EOF
234 echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
235 test_three_modes can_all_from_reach_with_flag
236'
237test_expect_success 'commit_contains:hit' '
239 cat >input <<-\EOF &&
240 A:commit-7-7
241 X:commit-2-10
242 X:commit-3-9
243 X:commit-4-8
244 X:commit-5-7
245 X:commit-6-6
246 X:commit-7-5
247 X:commit-8-4
248 X:commit-9-3
249 EOF
250 echo "commit_contains(_,A,X,_):1" >expect &&
251 test_three_modes commit_contains &&
252 test_three_modes commit_contains --tag
253'
254test_expect_success 'commit_contains:miss' '
256 cat >input <<-\EOF &&
257 A:commit-6-5
258 X:commit-2-10
259 X:commit-3-9
260 X:commit-4-8
261 X:commit-5-7
262 X:commit-6-6
263 X:commit-7-5
264 X:commit-8-4
265 X:commit-9-3
266 EOF
267 echo "commit_contains(_,A,X,_):0" >expect &&
268 test_three_modes commit_contains &&
269 test_three_modes commit_contains --tag
270'
271test_expect_success 'rev-list: basic topo-order' '
273 git rev-parse \
274 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
275 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
276 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
277 commit-6-3 commit-5-3 commit-4-3 commit-3-3 commit-2-3 commit-1-3 \
278 commit-6-2 commit-5-2 commit-4-2 commit-3-2 commit-2-2 commit-1-2 \
279 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
280 >expect &&
281 run_three_modes git rev-list --topo-order commit-6-6
282'
283test_expect_success 'rev-list: first-parent topo-order' '
285 git rev-parse \
286 commit-6-6 \
287 commit-6-5 \
288 commit-6-4 \
289 commit-6-3 \
290 commit-6-2 \
291 commit-6-1 commit-5-1 commit-4-1 commit-3-1 commit-2-1 commit-1-1 \
292 >expect &&
293 run_three_modes git rev-list --first-parent --topo-order commit-6-6
294'
295test_expect_success 'rev-list: range topo-order' '
297 git rev-parse \
298 commit-6-6 commit-5-6 commit-4-6 commit-3-6 commit-2-6 commit-1-6 \
299 commit-6-5 commit-5-5 commit-4-5 commit-3-5 commit-2-5 commit-1-5 \
300 commit-6-4 commit-5-4 commit-4-4 commit-3-4 commit-2-4 commit-1-4 \
301 commit-6-3 commit-5-3 commit-4-3 \
302 commit-6-2 commit-5-2 commit-4-2 \
303 commit-6-1 commit-5-1 commit-4-1 \
304 >expect &&
305 run_three_modes git rev-list --topo-order commit-3-3..commit-6-6
306'
307test_expect_success 'rev-list: range topo-order' '
309 git rev-parse \
310 commit-6-6 commit-5-6 commit-4-6 \
311 commit-6-5 commit-5-5 commit-4-5 \
312 commit-6-4 commit-5-4 commit-4-4 \
313 commit-6-3 commit-5-3 commit-4-3 \
314 commit-6-2 commit-5-2 commit-4-2 \
315 commit-6-1 commit-5-1 commit-4-1 \
316 >expect &&
317 run_three_modes git rev-list --topo-order commit-3-8..commit-6-6
318'
319test_expect_success 'rev-list: first-parent range topo-order' '
321 git rev-parse \
322 commit-6-6 \
323 commit-6-5 \
324 commit-6-4 \
325 commit-6-3 \
326 commit-6-2 \
327 commit-6-1 commit-5-1 commit-4-1 \
328 >expect &&
329 run_three_modes git rev-list --first-parent --topo-order commit-3-8..commit-6-6
330'
331test_expect_success 'rev-list: ancestry-path topo-order' '
333 git rev-parse \
334 commit-6-6 commit-5-6 commit-4-6 commit-3-6 \
335 commit-6-5 commit-5-5 commit-4-5 commit-3-5 \
336 commit-6-4 commit-5-4 commit-4-4 commit-3-4 \
337 commit-6-3 commit-5-3 commit-4-3 \
338 >expect &&
339 run_three_modes git rev-list --topo-order --ancestry-path commit-3-3..commit-6-6
340'
341test_expect_success 'rev-list: symmetric difference topo-order' '
343 git rev-parse \
344 commit-6-6 commit-5-6 commit-4-6 \
345 commit-6-5 commit-5-5 commit-4-5 \
346 commit-6-4 commit-5-4 commit-4-4 \
347 commit-6-3 commit-5-3 commit-4-3 \
348 commit-6-2 commit-5-2 commit-4-2 \
349 commit-6-1 commit-5-1 commit-4-1 \
350 commit-3-8 commit-2-8 commit-1-8 \
351 commit-3-7 commit-2-7 commit-1-7 \
352 >expect &&
353 run_three_modes git rev-list --topo-order commit-3-8...commit-6-6
354'
355test_expect_success 'get_reachable_subset:all' '
357 cat >input <<-\EOF &&
358 X:commit-9-1
359 X:commit-8-3
360 X:commit-7-5
361 X:commit-6-6
362 X:commit-1-7
363 Y:commit-3-3
364 Y:commit-1-7
365 Y:commit-5-6
366 EOF
367 (
368 echo "get_reachable_subset(X,Y)" &&
369 git rev-parse commit-3-3 \
370 commit-1-7 \
371 commit-5-6 | sort
372 ) >expect &&
373 test_three_modes get_reachable_subset
374'
375test_expect_success 'get_reachable_subset:some' '
377 cat >input <<-\EOF &&
378 X:commit-9-1
379 X:commit-8-3
380 X:commit-7-5
381 X:commit-1-7
382 Y:commit-3-3
383 Y:commit-1-7
384 Y:commit-5-6
385 EOF
386 (
387 echo "get_reachable_subset(X,Y)" &&
388 git rev-parse commit-3-3 \
389 commit-1-7 | sort
390 ) >expect &&
391 test_three_modes get_reachable_subset
392'
393test_expect_success 'get_reachable_subset:none' '
395 cat >input <<-\EOF &&
396 X:commit-9-1
397 X:commit-8-3
398 X:commit-7-5
399 X:commit-1-7
400 Y:commit-9-3
401 Y:commit-7-6
402 Y:commit-2-8
403 EOF
404 echo "get_reachable_subset(X,Y)" >expect &&
405 test_three_modes get_reachable_subset
406'
407test_done