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 done &&
36 for j in $(test_seq 1 9)
37 do
38 git reset --hard commit-$j-1 &&
39 x=$(($j + 1)) &&
40 test_commit "$x-1" &&
41 git branch -f commit-$x-1 &&
42 for i in $(test_seq 2 10)
44 do
45 git merge commit-$j-$i -m "$x-$i" &&
46 git branch -f commit-$x-$i
47 done
48 done &&
49 git commit-graph write --reachable &&
50 mv .git/objects/info/commit-graph commit-graph-full &&
51 git show-ref -s commit-5-5 | git commit-graph write --stdin-commits &&
52 mv .git/objects/info/commit-graph commit-graph-half &&
53 git config core.commitGraph true
54'
55test_three_modes () {
57 test_when_finished rm -rf .git/objects/info/commit-graph &&
58 test-tool reach $1 <input >actual &&
59 test_cmp expect actual &&
60 cp commit-graph-full .git/objects/info/commit-graph &&
61 test-tool reach $1 <input >actual &&
62 test_cmp expect actual &&
63 cp commit-graph-half .git/objects/info/commit-graph &&
64 test-tool reach $1 <input >actual &&
65 test_cmp expect actual
66}
67test_expect_success 'ref_newer:miss' '
69 cat >input <<-\EOF &&
70 A:commit-5-7
71 B:commit-4-9
72 EOF
73 echo "ref_newer(A,B):0" >expect &&
74 test_three_modes ref_newer
75'
76test_expect_success 'ref_newer:hit' '
78 cat >input <<-\EOF &&
79 A:commit-5-7
80 B:commit-2-3
81 EOF
82 echo "ref_newer(A,B):1" >expect &&
83 test_three_modes ref_newer
84'
85test_expect_success 'in_merge_bases:hit' '
87 cat >input <<-\EOF &&
88 A:commit-5-7
89 B:commit-8-8
90 EOF
91 echo "in_merge_bases(A,B):1" >expect &&
92 test_three_modes in_merge_bases
93'
94test_expect_success 'in_merge_bases:miss' '
96 cat >input <<-\EOF &&
97 A:commit-6-8
98 B:commit-5-9
99 EOF
100 echo "in_merge_bases(A,B):0" >expect &&
101 test_three_modes in_merge_bases
102'
103test_expect_success 'is_descendant_of:hit' '
105 cat >input <<-\EOF &&
106 A:commit-5-7
107 X:commit-4-8
108 X:commit-6-6
109 X:commit-1-1
110 EOF
111 echo "is_descendant_of(A,X):1" >expect &&
112 test_three_modes is_descendant_of
113'
114test_expect_success 'is_descendant_of:miss' '
116 cat >input <<-\EOF &&
117 A:commit-6-8
118 X:commit-5-9
119 X:commit-4-10
120 X:commit-7-6
121 EOF
122 echo "is_descendant_of(A,X):0" >expect &&
123 test_three_modes is_descendant_of
124'
125test_expect_success 'get_merge_bases_many' '
127 cat >input <<-\EOF &&
128 A:commit-5-7
129 X:commit-4-8
130 X:commit-6-6
131 X:commit-8-3
132 EOF
133 {
134 echo "get_merge_bases_many(A,X):" &&
135 git rev-parse commit-5-6 \
136 commit-4-7 | sort
137 } >expect &&
138 test_three_modes get_merge_bases_many
139'
140test_expect_success 'reduce_heads' '
142 cat >input <<-\EOF &&
143 X:commit-1-10
144 X:commit-2-8
145 X:commit-3-6
146 X:commit-4-4
147 X:commit-1-7
148 X:commit-2-5
149 X:commit-3-3
150 X:commit-5-1
151 EOF
152 {
153 echo "reduce_heads(X):" &&
154 git rev-parse commit-5-1 \
155 commit-4-4 \
156 commit-3-6 \
157 commit-2-8 \
158 commit-1-10 | sort
159 } >expect &&
160 test_three_modes reduce_heads
161'
162test_expect_success 'can_all_from_reach:hit' '
164 cat >input <<-\EOF &&
165 X:commit-2-10
166 X:commit-3-9
167 X:commit-4-8
168 X:commit-5-7
169 X:commit-6-6
170 X:commit-7-5
171 X:commit-8-4
172 X:commit-9-3
173 Y:commit-1-9
174 Y:commit-2-8
175 Y:commit-3-7
176 Y:commit-4-6
177 Y:commit-5-5
178 Y:commit-6-4
179 Y:commit-7-3
180 Y:commit-8-1
181 EOF
182 echo "can_all_from_reach(X,Y):1" >expect &&
183 test_three_modes can_all_from_reach
184'
185test_expect_success 'can_all_from_reach:miss' '
187 cat >input <<-\EOF &&
188 X:commit-2-10
189 X:commit-3-9
190 X:commit-4-8
191 X:commit-5-7
192 X:commit-6-6
193 X:commit-7-5
194 X:commit-8-4
195 X:commit-9-3
196 Y:commit-1-9
197 Y:commit-2-8
198 Y:commit-3-7
199 Y:commit-4-6
200 Y:commit-5-5
201 Y:commit-6-4
202 Y:commit-8-5
203 EOF
204 echo "can_all_from_reach(X,Y):0" >expect &&
205 test_three_modes can_all_from_reach
206'
207test_expect_success 'commit_contains:hit' '
209 cat >input <<-\EOF &&
210 A:commit-7-7
211 X:commit-2-10
212 X:commit-3-9
213 X:commit-4-8
214 X:commit-5-7
215 X:commit-6-6
216 X:commit-7-5
217 X:commit-8-4
218 X:commit-9-3
219 EOF
220 echo "commit_contains(_,A,X,_):1" >expect &&
221 test_three_modes commit_contains &&
222 test_three_modes commit_contains --tag
223'
224test_expect_success 'commit_contains:miss' '
226 cat >input <<-\EOF &&
227 A:commit-6-5
228 X:commit-2-10
229 X:commit-3-9
230 X:commit-4-8
231 X:commit-5-7
232 X:commit-6-6
233 X:commit-7-5
234 X:commit-8-4
235 X:commit-9-3
236 EOF
237 echo "commit_contains(_,A,X,_):0" >expect &&
238 test_three_modes commit_contains &&
239 test_three_modes commit_contains --tag
240'
241test_done