]>
Commit | Line | Data |
---|---|---|
06160502 | 1 | /* |
5e0de328 | 2 | * Copyright (C) 2009-2012 the libgit2 contributors |
06160502 | 3 | * |
bb742ede VM |
4 | * This file is part of libgit2, distributed under the GNU GPL v2 with |
5 | * a Linking Exception. For full terms see the included COPYING file. | |
06160502 SP |
6 | */ |
7 | ||
64a47c01 | 8 | #include "common.h" |
08d5d000 | 9 | #include "commit.h" |
72a3fe42 | 10 | #include "odb.h" |
da3b391c | 11 | #include "pool.h" |
06160502 | 12 | |
4ff192d3 BS |
13 | #include "revwalk.h" |
14 | #include "merge.h" | |
b5c5f0f8 | 15 | |
155aca2d CMN |
16 | #include <regex.h> |
17 | ||
d5e44d84 RB |
18 | git_commit_list_node *git_revwalk__commit_lookup( |
19 | git_revwalk *walk, const git_oid *oid) | |
3315782c | 20 | { |
4ff192d3 | 21 | git_commit_list_node *commit; |
01fed0a8 RB |
22 | khiter_t pos; |
23 | int ret; | |
58b0cbea | 24 | |
01fed0a8 RB |
25 | /* lookup and reserve space if not already present */ |
26 | pos = kh_get(oid, walk->commits, oid); | |
27 | if (pos != kh_end(walk->commits)) | |
28 | return kh_value(walk->commits, pos); | |
40721f6b | 29 | |
4ff192d3 | 30 | commit = git_commit_list_alloc_node(walk); |
3315782c VM |
31 | if (commit == NULL) |
32 | return NULL; | |
5e15176d | 33 | |
71db842f | 34 | git_oid_cpy(&commit->oid, oid); |
3315782c | 35 | |
01fed0a8 RB |
36 | pos = kh_put(oid, walk->commits, &commit->oid, &ret); |
37 | assert(ret != 0); | |
38 | kh_value(walk->commits, pos) = commit; | |
3315782c VM |
39 | |
40 | return commit; | |
06160502 | 41 | } |
08d5d000 | 42 | |
4ff192d3 | 43 | static void mark_uninteresting(git_commit_list_node *commit) |
3315782c | 44 | { |
71db842f VM |
45 | unsigned short i; |
46 | assert(commit); | |
1f080e2d | 47 | |
71db842f | 48 | commit->uninteresting = 1; |
08d5d000 | 49 | |
2c4ef1dd CMN |
50 | /* This means we've reached a merge base, so there's no need to walk any more */ |
51 | if ((commit->flags & (RESULT | STALE)) == RESULT) | |
52 | return; | |
53 | ||
71db842f VM |
54 | for (i = 0; i < commit->out_degree; ++i) |
55 | if (!commit->parents[i]->uninteresting) | |
56 | mark_uninteresting(commit->parents[i]); | |
3315782c | 57 | } |
1a895dd7 | 58 | |
4ff192d3 | 59 | static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide) |
3315782c | 60 | { |
44ef8b1b RB |
61 | int error; |
62 | ||
c68dee2a VM |
63 | if (hide) |
64 | mark_uninteresting(commit); | |
65 | ||
71db842f | 66 | if (commit->seen) |
eb8117b8 | 67 | return 0; |
3315782c | 68 | |
71db842f | 69 | commit->seen = 1; |
1a895dd7 | 70 | |
4ff192d3 | 71 | if ((error = git_commit_list_parse(walk, commit)) < 0) |
44ef8b1b | 72 | return error; |
e5d1faef | 73 | |
71db842f VM |
74 | return walk->enqueue(walk, commit); |
75 | } | |
3315782c | 76 | |
4ff192d3 | 77 | static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit) |
71db842f VM |
78 | { |
79 | unsigned short i; | |
44ef8b1b | 80 | int error = 0; |
c836c332 | 81 | |
44ef8b1b RB |
82 | for (i = 0; i < commit->out_degree && !error; ++i) |
83 | error = process_commit(walk, commit->parents[i], commit->uninteresting); | |
3315782c | 84 | |
44ef8b1b | 85 | return error; |
08d5d000 VM |
86 | } |
87 | ||
71db842f | 88 | static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting) |
08d5d000 | 89 | { |
4e323ef0 MS |
90 | git_object *obj; |
91 | git_otype type; | |
4ff192d3 | 92 | git_commit_list_node *commit; |
1a895dd7 | 93 | |
4e323ef0 MS |
94 | if (git_object_lookup(&obj, walk->repo, oid, GIT_OBJ_ANY) < 0) |
95 | return -1; | |
96 | ||
97 | type = git_object_type(obj); | |
98 | git_object_free(obj); | |
99 | ||
100 | if (type != GIT_OBJ_COMMIT) { | |
101 | giterr_set(GITERR_INVALID, "Object is no commit object"); | |
102 | return -1; | |
103 | } | |
104 | ||
d5e44d84 | 105 | commit = git_revwalk__commit_lookup(walk, oid); |
71db842f | 106 | if (commit == NULL) |
44ef8b1b | 107 | return -1; /* error already reported by failed lookup */ |
1f080e2d | 108 | |
2c4ef1dd CMN |
109 | commit->uninteresting = uninteresting; |
110 | if (walk->one == NULL && !uninteresting) { | |
111 | walk->one = commit; | |
112 | } else { | |
eb8117b8 CMN |
113 | if (git_vector_insert(&walk->twos, commit) < 0) |
114 | return -1; | |
2c4ef1dd CMN |
115 | } |
116 | ||
eb8117b8 | 117 | return 0; |
3315782c VM |
118 | } |
119 | ||
71db842f VM |
120 | int git_revwalk_push(git_revwalk *walk, const git_oid *oid) |
121 | { | |
122 | assert(walk && oid); | |
123 | return push_commit(walk, oid, 0); | |
124 | } | |
3315782c | 125 | |
155aca2d | 126 | |
71db842f VM |
127 | int git_revwalk_hide(git_revwalk *walk, const git_oid *oid) |
128 | { | |
129 | assert(walk && oid); | |
130 | return push_commit(walk, oid, 1); | |
131 | } | |
3315782c | 132 | |
06b9d915 CMN |
133 | static int push_ref(git_revwalk *walk, const char *refname, int hide) |
134 | { | |
f201d613 | 135 | git_oid oid; |
eb8117b8 | 136 | |
2508cc66 | 137 | if (git_reference_name_to_id(&oid, walk->repo, refname) < 0) |
eb8117b8 CMN |
138 | return -1; |
139 | ||
f201d613 | 140 | return push_commit(walk, &oid, hide); |
06b9d915 CMN |
141 | } |
142 | ||
155aca2d CMN |
143 | struct push_cb_data { |
144 | git_revwalk *walk; | |
155aca2d CMN |
145 | int hide; |
146 | }; | |
147 | ||
148 | static int push_glob_cb(const char *refname, void *data_) | |
149 | { | |
150 | struct push_cb_data *data = (struct push_cb_data *)data_; | |
151 | ||
11634346 | 152 | return push_ref(data->walk, refname, data->hide); |
155aca2d CMN |
153 | } |
154 | ||
155 | static int push_glob(git_revwalk *walk, const char *glob, int hide) | |
156 | { | |
157 | git_buf buf = GIT_BUF_INIT; | |
158 | struct push_cb_data data; | |
155aca2d CMN |
159 | regex_t preg; |
160 | ||
161 | assert(walk && glob); | |
162 | ||
163 | /* refs/ is implied if not given in the glob */ | |
164 | if (strncmp(glob, GIT_REFS_DIR, strlen(GIT_REFS_DIR))) { | |
165 | git_buf_printf(&buf, GIT_REFS_DIR "%s", glob); | |
166 | } else { | |
167 | git_buf_puts(&buf, glob); | |
168 | } | |
169 | ||
170 | /* If no '?', '*' or '[' exist, we append '/ *' to the glob */ | |
171 | memset(&preg, 0x0, sizeof(regex_t)); | |
172 | if (regcomp(&preg, "[?*[]", REG_EXTENDED)) { | |
eb8117b8 CMN |
173 | giterr_set(GITERR_OS, "Regex failed to compile"); |
174 | git_buf_free(&buf); | |
175 | return -1; | |
155aca2d CMN |
176 | } |
177 | ||
178 | if (regexec(&preg, glob, 0, NULL, 0)) | |
179 | git_buf_puts(&buf, "/*"); | |
180 | ||
eb8117b8 CMN |
181 | if (git_buf_oom(&buf)) |
182 | goto on_error; | |
155aca2d CMN |
183 | |
184 | data.walk = walk; | |
155aca2d CMN |
185 | data.hide = hide; |
186 | ||
11634346 | 187 | if (git_reference_foreach_glob( |
188 | walk->repo, git_buf_cstr(&buf), GIT_REF_LISTALL, push_glob_cb, &data) < 0) | |
eb8117b8 | 189 | goto on_error; |
155aca2d | 190 | |
155aca2d CMN |
191 | regfree(&preg); |
192 | git_buf_free(&buf); | |
eb8117b8 CMN |
193 | return 0; |
194 | ||
195 | on_error: | |
196 | regfree(&preg); | |
197 | git_buf_free(&buf); | |
198 | return -1; | |
155aca2d CMN |
199 | } |
200 | ||
201 | int git_revwalk_push_glob(git_revwalk *walk, const char *glob) | |
202 | { | |
203 | assert(walk && glob); | |
204 | return push_glob(walk, glob, 0); | |
205 | } | |
206 | ||
207 | int git_revwalk_hide_glob(git_revwalk *walk, const char *glob) | |
208 | { | |
209 | assert(walk && glob); | |
210 | return push_glob(walk, glob, 1); | |
211 | } | |
212 | ||
f7367993 CMN |
213 | int git_revwalk_push_head(git_revwalk *walk) |
214 | { | |
215 | assert(walk); | |
06b9d915 | 216 | return push_ref(walk, GIT_HEAD_FILE, 0); |
f7367993 CMN |
217 | } |
218 | ||
219 | int git_revwalk_hide_head(git_revwalk *walk) | |
220 | { | |
221 | assert(walk); | |
06b9d915 CMN |
222 | return push_ref(walk, GIT_HEAD_FILE, 1); |
223 | } | |
224 | ||
225 | int git_revwalk_push_ref(git_revwalk *walk, const char *refname) | |
226 | { | |
227 | assert(walk && refname); | |
228 | return push_ref(walk, refname, 0); | |
229 | } | |
230 | ||
231 | int git_revwalk_hide_ref(git_revwalk *walk, const char *refname) | |
232 | { | |
233 | assert(walk && refname); | |
234 | return push_ref(walk, refname, 1); | |
f7367993 CMN |
235 | } |
236 | ||
4ff192d3 | 237 | static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit) |
3315782c | 238 | { |
71db842f VM |
239 | return git_pqueue_insert(&walk->iterator_time, commit); |
240 | } | |
3315782c | 241 | |
4ff192d3 | 242 | static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit) |
71db842f | 243 | { |
4ff192d3 | 244 | return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1; |
71db842f | 245 | } |
3315782c | 246 | |
4ff192d3 | 247 | static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk) |
71db842f VM |
248 | { |
249 | int error; | |
4ff192d3 | 250 | git_commit_list_node *next; |
5e15176d | 251 | |
71db842f | 252 | while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) { |
eb8117b8 | 253 | if ((error = process_commit_parents(walk, next)) < 0) |
44ef8b1b | 254 | return error; |
6bb7aa13 | 255 | |
71db842f VM |
256 | if (!next->uninteresting) { |
257 | *object_out = next; | |
eb8117b8 | 258 | return 0; |
71db842f | 259 | } |
9b3577ed | 260 | } |
08d5d000 | 261 | |
f335ecd6 RB |
262 | giterr_clear(); |
263 | return GIT_ITEROVER; | |
3315782c VM |
264 | } |
265 | ||
4ff192d3 | 266 | static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk) |
3315782c | 267 | { |
71db842f | 268 | int error; |
4ff192d3 | 269 | git_commit_list_node *next; |
3315782c | 270 | |
4ff192d3 | 271 | while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) { |
eb8117b8 | 272 | if ((error = process_commit_parents(walk, next)) < 0) |
44ef8b1b | 273 | return error; |
6bb7aa13 | 274 | |
71db842f VM |
275 | if (!next->uninteresting) { |
276 | *object_out = next; | |
eb8117b8 | 277 | return 0; |
71db842f | 278 | } |
3315782c VM |
279 | } |
280 | ||
f335ecd6 RB |
281 | giterr_clear(); |
282 | return GIT_ITEROVER; | |
a7c182c5 | 283 | } |
1a895dd7 | 284 | |
4ff192d3 | 285 | static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk) |
a7c182c5 | 286 | { |
4ff192d3 | 287 | git_commit_list_node *next; |
71db842f | 288 | unsigned short i; |
1a895dd7 | 289 | |
71db842f | 290 | for (;;) { |
4ff192d3 | 291 | next = git_commit_list_pop(&walk->iterator_topo); |
f335ecd6 RB |
292 | if (next == NULL) { |
293 | giterr_clear(); | |
294 | return GIT_ITEROVER; | |
295 | } | |
5e15176d | 296 | |
71db842f VM |
297 | if (next->in_degree > 0) { |
298 | next->topo_delay = 1; | |
299 | continue; | |
300 | } | |
655d381a | 301 | |
71db842f | 302 | for (i = 0; i < next->out_degree; ++i) { |
4ff192d3 | 303 | git_commit_list_node *parent = next->parents[i]; |
5e15176d | 304 | |
71db842f VM |
305 | if (--parent->in_degree == 0 && parent->topo_delay) { |
306 | parent->topo_delay = 0; | |
4ff192d3 | 307 | if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL) |
eb8117b8 | 308 | return -1; |
71db842f VM |
309 | } |
310 | } | |
5e15176d | 311 | |
71db842f | 312 | *object_out = next; |
eb8117b8 | 313 | return 0; |
71db842f | 314 | } |
5e15176d VM |
315 | } |
316 | ||
4ff192d3 | 317 | static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk) |
5e15176d | 318 | { |
4ff192d3 | 319 | *object_out = git_commit_list_pop(&walk->iterator_reverse); |
f335ecd6 | 320 | return *object_out ? 0 : GIT_ITEROVER; |
71db842f | 321 | } |
5e15176d | 322 | |
3315782c | 323 | |
71db842f VM |
324 | static int prepare_walk(git_revwalk *walk) |
325 | { | |
71db842f | 326 | int error; |
2c4ef1dd | 327 | unsigned int i; |
4ff192d3 BS |
328 | git_commit_list_node *next, *two; |
329 | git_commit_list *bases = NULL; | |
2c4ef1dd | 330 | |
2e3a0055 CMN |
331 | /* |
332 | * If walk->one is NULL, there were no positive references, | |
333 | * so we know that the walk is already over. | |
334 | */ | |
f335ecd6 RB |
335 | if (walk->one == NULL) { |
336 | giterr_clear(); | |
337 | return GIT_ITEROVER; | |
338 | } | |
2e3a0055 | 339 | |
2c4ef1dd | 340 | /* first figure out what the merge bases are */ |
4ff192d3 | 341 | if (git_merge__bases_many(&bases, walk, walk->one, &walk->twos) < 0) |
eb8117b8 | 342 | return -1; |
2c4ef1dd | 343 | |
4ff192d3 | 344 | git_commit_list_free(&bases); |
eb8117b8 CMN |
345 | if (process_commit(walk, walk->one, walk->one->uninteresting) < 0) |
346 | return -1; | |
2c4ef1dd CMN |
347 | |
348 | git_vector_foreach(&walk->twos, i, two) { | |
eb8117b8 CMN |
349 | if (process_commit(walk, two, two->uninteresting) < 0) |
350 | return -1; | |
2c4ef1dd | 351 | } |
08d5d000 | 352 | |
71db842f | 353 | if (walk->sorting & GIT_SORT_TOPOLOGICAL) { |
71db842f | 354 | unsigned short i; |
08d5d000 | 355 | |
eb8117b8 | 356 | while ((error = walk->get_next(&next, walk)) == 0) { |
71db842f | 357 | for (i = 0; i < next->out_degree; ++i) { |
4ff192d3 | 358 | git_commit_list_node *parent = next->parents[i]; |
71db842f VM |
359 | parent->in_degree++; |
360 | } | |
3315782c | 361 | |
4ff192d3 | 362 | if (git_commit_list_insert(next, &walk->iterator_topo) == NULL) |
eb8117b8 | 363 | return -1; |
71db842f | 364 | } |
3315782c | 365 | |
f335ecd6 | 366 | if (error != GIT_ITEROVER) |
44ef8b1b | 367 | return error; |
3315782c | 368 | |
71db842f VM |
369 | walk->get_next = &revwalk_next_toposort; |
370 | } | |
3315782c | 371 | |
71db842f | 372 | if (walk->sorting & GIT_SORT_REVERSE) { |
3315782c | 373 | |
44ef8b1b | 374 | while ((error = walk->get_next(&next, walk)) == 0) |
4ff192d3 | 375 | if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL) |
eb8117b8 | 376 | return -1; |
3315782c | 377 | |
f335ecd6 | 378 | if (error != GIT_ITEROVER) |
44ef8b1b | 379 | return error; |
9bdb7594 | 380 | |
71db842f VM |
381 | walk->get_next = &revwalk_next_reverse; |
382 | } | |
40721f6b | 383 | |
71db842f | 384 | walk->walking = 1; |
eb8117b8 | 385 | return 0; |
71db842f | 386 | } |
3315782c | 387 | |
3315782c | 388 | |
36aaf1ff VM |
389 | int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) |
390 | { | |
391 | git_revwalk *walk; | |
392 | ||
393 | walk = git__malloc(sizeof(git_revwalk)); | |
eb8117b8 | 394 | GITERR_CHECK_ALLOC(walk); |
36aaf1ff VM |
395 | |
396 | memset(walk, 0x0, sizeof(git_revwalk)); | |
397 | ||
c2b67043 | 398 | walk->commits = git_oidmap_alloc(); |
44ef8b1b | 399 | GITERR_CHECK_ALLOC(walk->commits); |
36aaf1ff | 400 | |
4ff192d3 | 401 | if (git_pqueue_init(&walk->iterator_time, 8, git_commit_list_time_cmp) < 0 || |
44ef8b1b | 402 | git_vector_init(&walk->twos, 4, NULL) < 0 || |
da3b391c RB |
403 | git_pool_init(&walk->commit_pool, 1, |
404 | git_pool__suggest_items_per_page(COMMIT_ALLOC) * COMMIT_ALLOC) < 0) | |
eb8117b8 | 405 | return -1; |
36aaf1ff VM |
406 | |
407 | walk->get_next = &revwalk_next_unsorted; | |
408 | walk->enqueue = &revwalk_enqueue_unsorted; | |
409 | ||
410 | walk->repo = repo; | |
411 | ||
eb8117b8 | 412 | if (git_repository_odb(&walk->odb, repo) < 0) { |
9462c471 | 413 | git_revwalk_free(walk); |
eb8117b8 | 414 | return -1; |
9462c471 VM |
415 | } |
416 | ||
36aaf1ff | 417 | *revwalk_out = walk; |
eb8117b8 | 418 | return 0; |
36aaf1ff VM |
419 | } |
420 | ||
421 | void git_revwalk_free(git_revwalk *walk) | |
422 | { | |
36aaf1ff VM |
423 | if (walk == NULL) |
424 | return; | |
425 | ||
426 | git_revwalk_reset(walk); | |
9462c471 | 427 | git_odb_free(walk->odb); |
21d73e71 | 428 | |
c2b67043 | 429 | git_oidmap_free(walk->commits); |
da3b391c | 430 | git_pool_clear(&walk->commit_pool); |
36aaf1ff | 431 | git_pqueue_free(&walk->iterator_time); |
2c4ef1dd | 432 | git_vector_free(&walk->twos); |
3286c408 | 433 | git__free(walk); |
36aaf1ff VM |
434 | } |
435 | ||
436 | git_repository *git_revwalk_repository(git_revwalk *walk) | |
437 | { | |
438 | assert(walk); | |
439 | return walk->repo; | |
440 | } | |
441 | ||
442 | void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode) | |
443 | { | |
444 | assert(walk); | |
445 | ||
446 | if (walk->walking) | |
447 | git_revwalk_reset(walk); | |
448 | ||
449 | walk->sorting = sort_mode; | |
450 | ||
451 | if (walk->sorting & GIT_SORT_TIME) { | |
452 | walk->get_next = &revwalk_next_timesort; | |
453 | walk->enqueue = &revwalk_enqueue_timesort; | |
454 | } else { | |
455 | walk->get_next = &revwalk_next_unsorted; | |
456 | walk->enqueue = &revwalk_enqueue_unsorted; | |
457 | } | |
458 | } | |
459 | ||
71db842f VM |
460 | int git_revwalk_next(git_oid *oid, git_revwalk *walk) |
461 | { | |
462 | int error; | |
4ff192d3 | 463 | git_commit_list_node *next; |
3315782c | 464 | |
71db842f | 465 | assert(walk && oid); |
3315782c | 466 | |
71db842f | 467 | if (!walk->walking) { |
eb8117b8 | 468 | if ((error = prepare_walk(walk)) < 0) |
44ef8b1b | 469 | return error; |
71db842f | 470 | } |
3315782c | 471 | |
71db842f | 472 | error = walk->get_next(&next, walk); |
ce90d81f | 473 | |
f335ecd6 | 474 | if (error == GIT_ITEROVER) { |
ce90d81f | 475 | git_revwalk_reset(walk); |
f335ecd6 RB |
476 | giterr_clear(); |
477 | return GIT_ITEROVER; | |
36aaf1ff | 478 | } |
3315782c | 479 | |
44ef8b1b RB |
480 | if (!error) |
481 | git_oid_cpy(oid, &next->oid); | |
ce90d81f | 482 | |
44ef8b1b | 483 | return error; |
3315782c VM |
484 | } |
485 | ||
71db842f | 486 | void git_revwalk_reset(git_revwalk *walk) |
3315782c | 487 | { |
4ff192d3 | 488 | git_commit_list_node *commit; |
3315782c | 489 | |
71db842f | 490 | assert(walk); |
9bdb7594 | 491 | |
01fed0a8 | 492 | kh_foreach_value(walk->commits, commit, { |
71db842f VM |
493 | commit->seen = 0; |
494 | commit->in_degree = 0; | |
495 | commit->topo_delay = 0; | |
97313ce2 | 496 | commit->uninteresting = 0; |
01fed0a8 | 497 | }); |
9bdb7594 | 498 | |
36aaf1ff | 499 | git_pqueue_clear(&walk->iterator_time); |
4ff192d3 BS |
500 | git_commit_list_free(&walk->iterator_topo); |
501 | git_commit_list_free(&walk->iterator_rand); | |
502 | git_commit_list_free(&walk->iterator_reverse); | |
71db842f | 503 | walk->walking = 0; |
0b86fdf9 NG |
504 | |
505 | walk->one = NULL; | |
506 | git_vector_clear(&walk->twos); | |
08d5d000 | 507 | } |
36b7cdb6 | 508 |