]>
Commit | Line | Data |
---|---|---|
c25aa7cd PP |
1 | #include "clar_libgit2.h" |
2 | ||
3 | #include <git2.h> | |
4 | ||
5 | #include "commit_graph.h" | |
6 | #include "bitvec.h" | |
7 | #include "vector.h" | |
8 | ||
9 | static git_repository *repo; | |
10 | ||
11 | #define TEST_REPO_PATH "merge-recursive" | |
12 | ||
13 | void test_graph_reachable_from_any__initialize(void) | |
14 | { | |
15 | git_oid oid; | |
16 | git_commit *commit; | |
17 | ||
18 | repo = cl_git_sandbox_init(TEST_REPO_PATH); | |
19 | ||
20 | git_oid_fromstr(&oid, "539bd011c4822c560c1d17cab095006b7a10f707"); | |
21 | cl_git_pass(git_commit_lookup(&commit, repo, &oid)); | |
22 | cl_git_pass(git_reset(repo, (git_object *)commit, GIT_RESET_HARD, NULL)); | |
23 | git_commit_free(commit); | |
24 | } | |
25 | ||
26 | void test_graph_reachable_from_any__cleanup(void) | |
27 | { | |
28 | cl_git_sandbox_cleanup(); | |
29 | } | |
30 | ||
31 | void test_graph_reachable_from_any__returns_correct_result(void) | |
32 | { | |
33 | git_object *branchA1, *branchA2, *branchB1, *branchB2, *branchC1, *branchC2, *branchH1, | |
34 | *branchH2; | |
35 | git_oid descendants[7]; | |
36 | ||
37 | cl_git_pass(git_revparse_single(&branchA1, repo, "branchA-1")); | |
38 | cl_git_pass(git_revparse_single(&branchA2, repo, "branchA-2")); | |
39 | cl_git_pass(git_revparse_single(&branchB1, repo, "branchB-1")); | |
40 | cl_git_pass(git_revparse_single(&branchB2, repo, "branchB-2")); | |
41 | cl_git_pass(git_revparse_single(&branchC1, repo, "branchC-1")); | |
42 | cl_git_pass(git_revparse_single(&branchC2, repo, "branchC-2")); | |
43 | cl_git_pass(git_revparse_single(&branchH1, repo, "branchH-1")); | |
44 | cl_git_pass(git_revparse_single(&branchH2, repo, "branchH-2")); | |
45 | ||
46 | cl_assert_equal_i( | |
47 | git_graph_reachable_from_any( | |
48 | repo, git_object_id(branchH1), git_object_id(branchA1), 1), | |
49 | 0); | |
50 | cl_assert_equal_i( | |
51 | git_graph_reachable_from_any( | |
52 | repo, git_object_id(branchH1), git_object_id(branchA2), 1), | |
53 | 0); | |
54 | ||
55 | cl_git_pass(git_oid_cpy(&descendants[0], git_object_id(branchA1))); | |
56 | cl_git_pass(git_oid_cpy(&descendants[1], git_object_id(branchA2))); | |
57 | cl_git_pass(git_oid_cpy(&descendants[2], git_object_id(branchB1))); | |
58 | cl_git_pass(git_oid_cpy(&descendants[3], git_object_id(branchB2))); | |
59 | cl_git_pass(git_oid_cpy(&descendants[4], git_object_id(branchC1))); | |
60 | cl_git_pass(git_oid_cpy(&descendants[5], git_object_id(branchC2))); | |
61 | cl_git_pass(git_oid_cpy(&descendants[6], git_object_id(branchH2))); | |
62 | cl_assert_equal_i( | |
63 | git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 6), | |
64 | 0); | |
65 | cl_assert_equal_i( | |
66 | git_graph_reachable_from_any(repo, git_object_id(branchH2), descendants, 7), | |
67 | 1); | |
68 | ||
69 | git_object_free(branchA1); | |
70 | git_object_free(branchA2); | |
71 | git_object_free(branchB1); | |
72 | git_object_free(branchB2); | |
73 | git_object_free(branchC1); | |
74 | git_object_free(branchC2); | |
75 | git_object_free(branchH1); | |
76 | git_object_free(branchH2); | |
77 | } | |
78 | ||
79 | struct exhaustive_state { | |
80 | git_odb *db; | |
81 | git_vector commits; | |
82 | }; | |
83 | ||
84 | /** Get all commits from the repository. */ | |
85 | static int exhaustive_commits(const git_oid *id, void *payload) | |
86 | { | |
87 | struct exhaustive_state *mc = (struct exhaustive_state *)payload; | |
88 | size_t header_len; | |
89 | git_object_t header_type; | |
90 | int error = 0; | |
91 | ||
92 | error = git_odb_read_header(&header_len, &header_type, mc->db, id); | |
93 | if (error < 0) | |
94 | return error; | |
95 | ||
96 | if (header_type == GIT_OBJECT_COMMIT) { | |
97 | git_commit *commit = NULL; | |
98 | ||
99 | cl_git_pass(git_commit_lookup(&commit, repo, id)); | |
100 | cl_git_pass(git_vector_insert(&mc->commits, commit)); | |
101 | } | |
102 | ||
103 | return 0; | |
104 | } | |
105 | ||
106 | /** Compare the `git_oid`s of two `git_commit` objects. */ | |
107 | static int commit_id_cmp(const void *a, const void *b) | |
108 | { | |
109 | return git_oid_cmp( | |
110 | git_commit_id((const git_commit *)a), git_commit_id((const git_commit *)b)); | |
111 | } | |
112 | ||
113 | /** Find a `git_commit` whose ID matches the provided `git_oid` key. */ | |
114 | static int id_commit_id_cmp(const void *key, const void *commit) | |
115 | { | |
116 | return git_oid_cmp((const git_oid *)key, git_commit_id((const git_commit *)commit)); | |
117 | } | |
118 | ||
119 | void test_graph_reachable_from_any__exhaustive(void) | |
120 | { | |
121 | struct exhaustive_state mc = { | |
122 | .db = NULL, | |
123 | .commits = GIT_VECTOR_INIT, | |
124 | }; | |
125 | size_t child_idx, commit_count; | |
126 | size_t n_descendants; | |
127 | git_commit *child_commit; | |
128 | git_bitvec reachable; | |
129 | ||
130 | cl_git_pass(git_repository_odb(&mc.db, repo)); | |
131 | cl_git_pass(git_odb_foreach(mc.db, &exhaustive_commits, &mc)); | |
132 | git_vector_set_cmp(&mc.commits, commit_id_cmp); | |
133 | git_vector_sort(&mc.commits); | |
134 | cl_git_pass(git_bitvec_init( | |
135 | &reachable, | |
136 | git_vector_length(&mc.commits) * git_vector_length(&mc.commits))); | |
137 | ||
138 | commit_count = git_vector_length(&mc.commits); | |
139 | git_vector_foreach (&mc.commits, child_idx, child_commit) { | |
140 | unsigned int parent_i; | |
141 | ||
142 | /* We treat each commit as being able to reach itself. */ | |
143 | git_bitvec_set(&reachable, child_idx * commit_count + child_idx, true); | |
144 | ||
145 | for (parent_i = 0; parent_i < git_commit_parentcount(child_commit); ++parent_i) { | |
146 | size_t parent_idx = -1; | |
147 | cl_git_pass(git_vector_bsearch2( | |
148 | &parent_idx, | |
149 | &mc.commits, | |
150 | id_commit_id_cmp, | |
151 | git_commit_parent_id(child_commit, parent_i))); | |
152 | ||
153 | /* We have established that parent_idx is reachable from child_idx */ | |
154 | git_bitvec_set(&reachable, parent_idx * commit_count + child_idx, true); | |
155 | } | |
156 | } | |
157 | ||
158 | /* Floyd-Warshall */ | |
159 | { | |
160 | size_t i, j, k; | |
161 | for (k = 0; k < commit_count; ++k) { | |
162 | for (i = 0; i < commit_count; ++i) { | |
163 | if (!git_bitvec_get(&reachable, i * commit_count + k)) | |
164 | continue; | |
165 | for (j = 0; j < commit_count; ++j) { | |
166 | if (!git_bitvec_get(&reachable, k * commit_count + j)) | |
167 | continue; | |
168 | git_bitvec_set(&reachable, i * commit_count + j, true); | |
169 | } | |
170 | } | |
171 | } | |
172 | } | |
173 | ||
174 | /* Try 1000 subsets of 1 through 10 entries each. */ | |
175 | srand(0x223ddc4b); | |
176 | for (n_descendants = 1; n_descendants < 10; ++n_descendants) { | |
177 | size_t test_iteration; | |
178 | git_oid descendants[10]; | |
179 | ||
180 | for (test_iteration = 0; test_iteration < 1000; ++test_iteration) { | |
181 | size_t descendant_i; | |
182 | size_t child_idx, parent_idx; | |
183 | int expected_reachable = false, actual_reachable; | |
184 | git_commit *child_commit, *parent_commit; | |
185 | ||
186 | parent_idx = rand() % commit_count; | |
187 | parent_commit = (git_commit *)git_vector_get(&mc.commits, parent_idx); | |
188 | for (descendant_i = 0; descendant_i < n_descendants; ++descendant_i) { | |
189 | child_idx = rand() % commit_count; | |
190 | child_commit = (git_commit *)git_vector_get(&mc.commits, child_idx); | |
191 | expected_reachable |= git_bitvec_get( | |
192 | &reachable, parent_idx * commit_count + child_idx); | |
193 | git_oid_cpy(&descendants[descendant_i], | |
194 | git_commit_id(child_commit)); | |
195 | } | |
196 | ||
197 | actual_reachable = git_graph_reachable_from_any( | |
198 | repo, | |
199 | git_commit_id(parent_commit), | |
200 | descendants, | |
201 | n_descendants); | |
202 | if (actual_reachable != expected_reachable) { | |
e579e0f7 | 203 | git_str error_message_buf = GIT_STR_INIT; |
c25aa7cd PP |
204 | char parent_oidbuf[9] = {0}, child_oidbuf[9] = {0}; |
205 | ||
206 | cl_git_pass(git_oid_nfmt( | |
207 | parent_oidbuf, 8, git_commit_id(parent_commit))); | |
e579e0f7 | 208 | git_str_printf(&error_message_buf, |
c25aa7cd PP |
209 | "git_graph_reachable_from_any(\"%s\", %zu, " |
210 | "{", | |
211 | parent_oidbuf, | |
212 | n_descendants); | |
213 | for (descendant_i = 0; descendant_i < n_descendants; | |
214 | ++descendant_i) { | |
215 | cl_git_pass( | |
216 | git_oid_nfmt(child_oidbuf, | |
217 | 8, | |
218 | &descendants[descendant_i])); | |
e579e0f7 | 219 | git_str_printf(&error_message_buf, " \"%s\"", child_oidbuf); |
c25aa7cd | 220 | } |
e579e0f7 | 221 | git_str_printf(&error_message_buf, |
c25aa7cd PP |
222 | " }) = %d, expected = %d", |
223 | actual_reachable, | |
224 | expected_reachable); | |
225 | cl_check_(actual_reachable == expected_reachable, | |
e579e0f7 | 226 | git_str_cstr(&error_message_buf)); |
c25aa7cd PP |
227 | } |
228 | } | |
229 | } | |
230 | ||
231 | git_vector_foreach (&mc.commits, child_idx, child_commit) | |
232 | git_commit_free(child_commit); | |
233 | git_bitvec_free(&reachable); | |
234 | git_vector_free(&mc.commits); | |
235 | git_odb_free(mc.db); | |
236 | } |