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'
58test_three_modes () {
60 test_when_finished rm -rf .git/objects/info/commit-graph &&
61 test-tool reach $1 <input >actual &&
62 test_cmp expect actual &&
63 cp commit-graph-full .git/objects/info/commit-graph &&
64 test-tool reach $1 <input >actual &&
65 test_cmp expect actual &&
66 cp commit-graph-half .git/objects/info/commit-graph &&
67 test-tool reach $1 <input >actual &&
68 test_cmp expect actual
69}
70test_expect_success 'ref_newer:miss' '
72 cat >input <<-\EOF &&
73 A:commit-5-7
74 B:commit-4-9
75 EOF
76 echo "ref_newer(A,B):0" >expect &&
77 test_three_modes ref_newer
78'
79test_expect_success 'ref_newer:hit' '
81 cat >input <<-\EOF &&
82 A:commit-5-7
83 B:commit-2-3
84 EOF
85 echo "ref_newer(A,B):1" >expect &&
86 test_three_modes ref_newer
87'
88test_expect_success 'in_merge_bases:hit' '
90 cat >input <<-\EOF &&
91 A:commit-5-7
92 B:commit-8-8
93 EOF
94 echo "in_merge_bases(A,B):1" >expect &&
95 test_three_modes in_merge_bases
96'
97test_expect_success 'in_merge_bases:miss' '
99 cat >input <<-\EOF &&
100 A:commit-6-8
101 B:commit-5-9
102 EOF
103 echo "in_merge_bases(A,B):0" >expect &&
104 test_three_modes in_merge_bases
105'
106test_expect_success 'is_descendant_of:hit' '
108 cat >input <<-\EOF &&
109 A:commit-5-7
110 X:commit-4-8
111 X:commit-6-6
112 X:commit-1-1
113 EOF
114 echo "is_descendant_of(A,X):1" >expect &&
115 test_three_modes is_descendant_of
116'
117test_expect_success 'is_descendant_of:miss' '
119 cat >input <<-\EOF &&
120 A:commit-6-8
121 X:commit-5-9
122 X:commit-4-10
123 X:commit-7-6
124 EOF
125 echo "is_descendant_of(A,X):0" >expect &&
126 test_three_modes is_descendant_of
127'
128test_expect_success 'get_merge_bases_many' '
130 cat >input <<-\EOF &&
131 A:commit-5-7
132 X:commit-4-8
133 X:commit-6-6
134 X:commit-8-3
135 EOF
136 {
137 echo "get_merge_bases_many(A,X):" &&
138 git rev-parse commit-5-6 \
139 commit-4-7 | sort
140 } >expect &&
141 test_three_modes get_merge_bases_many
142'
143test_expect_success 'reduce_heads' '
145 cat >input <<-\EOF &&
146 X:commit-1-10
147 X:commit-2-8
148 X:commit-3-6
149 X:commit-4-4
150 X:commit-1-7
151 X:commit-2-5
152 X:commit-3-3
153 X:commit-5-1
154 EOF
155 {
156 echo "reduce_heads(X):" &&
157 git rev-parse commit-5-1 \
158 commit-4-4 \
159 commit-3-6 \
160 commit-2-8 \
161 commit-1-10 | sort
162 } >expect &&
163 test_three_modes reduce_heads
164'
165test_expect_success 'can_all_from_reach:hit' '
167 cat >input <<-\EOF &&
168 X:commit-2-10
169 X:commit-3-9
170 X:commit-4-8
171 X:commit-5-7
172 X:commit-6-6
173 X:commit-7-5
174 X:commit-8-4
175 X:commit-9-3
176 Y:commit-1-9
177 Y:commit-2-8
178 Y:commit-3-7
179 Y:commit-4-6
180 Y:commit-5-5
181 Y:commit-6-4
182 Y:commit-7-3
183 Y:commit-8-1
184 EOF
185 echo "can_all_from_reach(X,Y):1" >expect &&
186 test_three_modes can_all_from_reach
187'
188test_expect_success 'can_all_from_reach:miss' '
190 cat >input <<-\EOF &&
191 X:commit-2-10
192 X:commit-3-9
193 X:commit-4-8
194 X:commit-5-7
195 X:commit-6-6
196 X:commit-7-5
197 X:commit-8-4
198 X:commit-9-3
199 Y:commit-1-9
200 Y:commit-2-8
201 Y:commit-3-7
202 Y:commit-4-6
203 Y:commit-5-5
204 Y:commit-6-4
205 Y:commit-8-5
206 EOF
207 echo "can_all_from_reach(X,Y):0" >expect &&
208 test_three_modes can_all_from_reach
209'
210test_expect_success 'can_all_from_reach_with_flag: tags case' '
212 cat >input <<-\EOF &&
213 X:tag-2-10
214 X:tag-3-9
215 X:tag-4-8
216 X:commit-5-7
217 X:commit-6-6
218 X:commit-7-5
219 X:commit-8-4
220 X:commit-9-3
221 Y:tag-1-9
222 Y:tag-2-8
223 Y:tag-3-7
224 Y:commit-4-6
225 Y:commit-5-5
226 Y:commit-6-4
227 Y:commit-7-3
228 Y:commit-8-1
229 EOF
230 echo "can_all_from_reach_with_flag(X,_,_,0,0):1" >expect &&
231 test_three_modes can_all_from_reach_with_flag
232'
233test_expect_success 'commit_contains:hit' '
235 cat >input <<-\EOF &&
236 A:commit-7-7
237 X:commit-2-10
238 X:commit-3-9
239 X:commit-4-8
240 X:commit-5-7
241 X:commit-6-6
242 X:commit-7-5
243 X:commit-8-4
244 X:commit-9-3
245 EOF
246 echo "commit_contains(_,A,X,_):1" >expect &&
247 test_three_modes commit_contains &&
248 test_three_modes commit_contains --tag
249'
250test_expect_success 'commit_contains:miss' '
252 cat >input <<-\EOF &&
253 A:commit-6-5
254 X:commit-2-10
255 X:commit-3-9
256 X:commit-4-8
257 X:commit-5-7
258 X:commit-6-6
259 X:commit-7-5
260 X:commit-8-4
261 X:commit-9-3
262 EOF
263 echo "commit_contains(_,A,X,_):0" >expect &&
264 test_three_modes commit_contains &&
265 test_three_modes commit_contains --tag
266'
267test_expect_success 'get_reachable_subset:all' '
269 cat >input <<-\EOF &&
270 X:commit-9-1
271 X:commit-8-3
272 X:commit-7-5
273 X:commit-6-6
274 X:commit-1-7
275 Y:commit-3-3
276 Y:commit-1-7
277 Y:commit-5-6
278 EOF
279 (
280 echo "get_reachable_subset(X,Y)" &&
281 git rev-parse commit-3-3 \
282 commit-1-7 \
283 commit-5-6 | sort
284 ) >expect &&
285 test_three_modes get_reachable_subset
286'
287test_expect_success 'get_reachable_subset:some' '
289 cat >input <<-\EOF &&
290 X:commit-9-1
291 X:commit-8-3
292 X:commit-7-5
293 X:commit-1-7
294 Y:commit-3-3
295 Y:commit-1-7
296 Y:commit-5-6
297 EOF
298 (
299 echo "get_reachable_subset(X,Y)" &&
300 git rev-parse commit-3-3 \
301 commit-1-7 | sort
302 ) >expect &&
303 test_three_modes get_reachable_subset
304'
305test_expect_success 'get_reachable_subset:none' '
307 cat >input <<-\EOF &&
308 X:commit-9-1
309 X:commit-8-3
310 X:commit-7-5
311 X:commit-1-7
312 Y:commit-9-3
313 Y:commit-7-6
314 Y:commit-2-8
315 EOF
316 echo "get_reachable_subset(X,Y)" >expect &&
317 test_three_modes get_reachable_subset
318'
319test_done