]>
Commit | Line | Data |
---|---|---|
06160502 | 1 | /* |
359fc2d2 | 2 | * Copyright (C) the libgit2 contributors. All rights reserved. |
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 | ||
eae0bfdc PP |
8 | #include "revwalk.h" |
9 | ||
08d5d000 | 10 | #include "commit.h" |
72a3fe42 | 11 | #include "odb.h" |
da3b391c | 12 | #include "pool.h" |
06160502 | 13 | |
af079d8b | 14 | #include "git2/revparse.h" |
4ff192d3 | 15 | #include "merge.h" |
9db367bf | 16 | #include "vector.h" |
b5c5f0f8 | 17 | |
ac3d33df JK |
18 | static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list); |
19 | ||
d5e44d84 RB |
20 | git_commit_list_node *git_revwalk__commit_lookup( |
21 | git_revwalk *walk, const git_oid *oid) | |
3315782c | 22 | { |
4ff192d3 | 23 | git_commit_list_node *commit; |
ac3d33df | 24 | size_t pos; |
01fed0a8 | 25 | int ret; |
58b0cbea | 26 | |
01fed0a8 | 27 | /* lookup and reserve space if not already present */ |
a853c527 | 28 | pos = git_oidmap_lookup_index(walk->commits, oid); |
64e46dc3 | 29 | if (git_oidmap_valid_index(walk->commits, pos)) |
cb18386f | 30 | return git_oidmap_value_at(walk->commits, pos); |
40721f6b | 31 | |
4ff192d3 | 32 | commit = git_commit_list_alloc_node(walk); |
3315782c VM |
33 | if (commit == NULL) |
34 | return NULL; | |
5e15176d | 35 | |
71db842f | 36 | git_oid_cpy(&commit->oid, oid); |
3315782c | 37 | |
f31cb45a | 38 | pos = git_oidmap_put(walk->commits, &commit->oid, &ret); |
01fed0a8 | 39 | assert(ret != 0); |
85d2748c | 40 | git_oidmap_set_value_at(walk->commits, pos, commit); |
3315782c VM |
41 | |
42 | return commit; | |
06160502 | 43 | } |
08d5d000 | 44 | |
d465e4e9 | 45 | static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob) |
08d5d000 | 46 | { |
f61272e0 | 47 | git_oid commit_id; |
dab89f9b | 48 | int error; |
f61272e0 | 49 | git_object *obj, *oobj; |
4ff192d3 | 50 | git_commit_list_node *commit; |
ad66bf88 | 51 | git_commit_list *list; |
1a895dd7 | 52 | |
ac3d33df | 53 | if ((error = git_object_lookup(&oobj, walk->repo, oid, GIT_OBJECT_ANY)) < 0) |
dab89f9b | 54 | return error; |
4e323ef0 | 55 | |
ac3d33df | 56 | error = git_object_peel(&obj, oobj, GIT_OBJECT_COMMIT); |
f61272e0 | 57 | git_object_free(oobj); |
4e323ef0 | 58 | |
753e17b0 | 59 | if (error == GIT_ENOTFOUND || error == GIT_EINVALIDSPEC || error == GIT_EPEEL) { |
d465e4e9 CMN |
60 | /* If this comes from e.g. push_glob("tags"), ignore this */ |
61 | if (from_glob) | |
62 | return 0; | |
63 | ||
ac3d33df | 64 | git_error_set(GIT_ERROR_INVALID, "object is not a committish"); |
4e323ef0 MS |
65 | return -1; |
66 | } | |
f61272e0 CMN |
67 | if (error < 0) |
68 | return error; | |
69 | ||
70 | git_oid_cpy(&commit_id, git_object_id(obj)); | |
71 | git_object_free(obj); | |
4e323ef0 | 72 | |
f61272e0 | 73 | commit = git_revwalk__commit_lookup(walk, &commit_id); |
71db842f | 74 | if (commit == NULL) |
44ef8b1b | 75 | return -1; /* error already reported by failed lookup */ |
1f080e2d | 76 | |
50fdfe2b CMN |
77 | /* A previous hide already told us we don't want this commit */ |
78 | if (commit->uninteresting) | |
79 | return 0; | |
80 | ||
ac3d33df JK |
81 | if (uninteresting) { |
82 | walk->limited = 1; | |
9b5d6cea | 83 | walk->did_hide = 1; |
ac3d33df | 84 | } else { |
9b5d6cea | 85 | walk->did_push = 1; |
ac3d33df | 86 | } |
9b5d6cea | 87 | |
2c4ef1dd | 88 | commit->uninteresting = uninteresting; |
ad66bf88 CMN |
89 | list = walk->user_input; |
90 | if (git_commit_list_insert(commit, &list) == NULL) { | |
ac3d33df | 91 | git_error_set_oom(); |
ad66bf88 | 92 | return -1; |
2c4ef1dd CMN |
93 | } |
94 | ||
ad66bf88 CMN |
95 | walk->user_input = list; |
96 | ||
eb8117b8 | 97 | return 0; |
3315782c VM |
98 | } |
99 | ||
71db842f VM |
100 | int git_revwalk_push(git_revwalk *walk, const git_oid *oid) |
101 | { | |
102 | assert(walk && oid); | |
d465e4e9 | 103 | return push_commit(walk, oid, 0, false); |
71db842f | 104 | } |
3315782c | 105 | |
155aca2d | 106 | |
71db842f VM |
107 | int git_revwalk_hide(git_revwalk *walk, const git_oid *oid) |
108 | { | |
109 | assert(walk && oid); | |
d465e4e9 | 110 | return push_commit(walk, oid, 1, false); |
71db842f | 111 | } |
3315782c | 112 | |
d465e4e9 | 113 | static int push_ref(git_revwalk *walk, const char *refname, int hide, int from_glob) |
06b9d915 | 114 | { |
f201d613 | 115 | git_oid oid; |
eb8117b8 | 116 | |
2508cc66 | 117 | if (git_reference_name_to_id(&oid, walk->repo, refname) < 0) |
eb8117b8 CMN |
118 | return -1; |
119 | ||
d465e4e9 | 120 | return push_commit(walk, &oid, hide, from_glob); |
06b9d915 CMN |
121 | } |
122 | ||
155aca2d CMN |
123 | static int push_glob(git_revwalk *walk, const char *glob, int hide) |
124 | { | |
106c12f1 | 125 | int error = 0; |
155aca2d | 126 | git_buf buf = GIT_BUF_INIT; |
af817202 CMN |
127 | git_reference *ref; |
128 | git_reference_iterator *iter; | |
106c12f1 | 129 | size_t wildcard; |
155aca2d CMN |
130 | |
131 | assert(walk && glob); | |
132 | ||
133 | /* refs/ is implied if not given in the glob */ | |
106c12f1 RB |
134 | if (git__prefixcmp(glob, GIT_REFS_DIR) != 0) |
135 | git_buf_joinpath(&buf, GIT_REFS_DIR, glob); | |
136 | else | |
155aca2d | 137 | git_buf_puts(&buf, glob); |
ac3d33df | 138 | GIT_ERROR_CHECK_ALLOC_BUF(&buf); |
155aca2d CMN |
139 | |
140 | /* If no '?', '*' or '[' exist, we append '/ *' to the glob */ | |
106c12f1 RB |
141 | wildcard = strcspn(glob, "?*["); |
142 | if (!glob[wildcard]) | |
143 | git_buf_put(&buf, "/*", 2); | |
155aca2d | 144 | |
af817202 CMN |
145 | if ((error = git_reference_iterator_glob_new(&iter, walk->repo, buf.ptr)) < 0) |
146 | goto out; | |
155aca2d | 147 | |
af817202 CMN |
148 | while ((error = git_reference_next(&ref, iter)) == 0) { |
149 | error = push_ref(walk, git_reference_name(ref), hide, true); | |
150 | git_reference_free(ref); | |
151 | if (error < 0) | |
152 | break; | |
153 | } | |
154 | git_reference_iterator_free(iter); | |
eb8117b8 | 155 | |
af817202 CMN |
156 | if (error == GIT_ITEROVER) |
157 | error = 0; | |
158 | out: | |
ac3d33df | 159 | git_buf_dispose(&buf); |
106c12f1 | 160 | return error; |
155aca2d CMN |
161 | } |
162 | ||
163 | int git_revwalk_push_glob(git_revwalk *walk, const char *glob) | |
164 | { | |
165 | assert(walk && glob); | |
166 | return push_glob(walk, glob, 0); | |
167 | } | |
168 | ||
169 | int git_revwalk_hide_glob(git_revwalk *walk, const char *glob) | |
170 | { | |
171 | assert(walk && glob); | |
172 | return push_glob(walk, glob, 1); | |
173 | } | |
174 | ||
f7367993 CMN |
175 | int git_revwalk_push_head(git_revwalk *walk) |
176 | { | |
177 | assert(walk); | |
d465e4e9 | 178 | return push_ref(walk, GIT_HEAD_FILE, 0, false); |
f7367993 CMN |
179 | } |
180 | ||
181 | int git_revwalk_hide_head(git_revwalk *walk) | |
182 | { | |
183 | assert(walk); | |
d465e4e9 | 184 | return push_ref(walk, GIT_HEAD_FILE, 1, false); |
06b9d915 CMN |
185 | } |
186 | ||
187 | int git_revwalk_push_ref(git_revwalk *walk, const char *refname) | |
188 | { | |
189 | assert(walk && refname); | |
d465e4e9 | 190 | return push_ref(walk, refname, 0, false); |
06b9d915 CMN |
191 | } |
192 | ||
af079d8b GP |
193 | int git_revwalk_push_range(git_revwalk *walk, const char *range) |
194 | { | |
cbda09d0 | 195 | git_revspec revspec; |
af079d8b GP |
196 | int error = 0; |
197 | ||
cbda09d0 | 198 | if ((error = git_revparse(&revspec, walk->repo, range))) |
af079d8b | 199 | return error; |
36c2dfed | 200 | |
cbda09d0 | 201 | if (revspec.flags & GIT_REVPARSE_MERGE_BASE) { |
af079d8b | 202 | /* TODO: support "<commit>...<commit>" */ |
ac3d33df | 203 | git_error_set(GIT_ERROR_INVALID, "symmetric differences not implemented in revwalk"); |
af079d8b GP |
204 | return GIT_EINVALIDSPEC; |
205 | } | |
206 | ||
d465e4e9 | 207 | if ((error = push_commit(walk, git_object_id(revspec.from), 1, false))) |
af079d8b | 208 | goto out; |
af079d8b | 209 | |
d465e4e9 | 210 | error = push_commit(walk, git_object_id(revspec.to), 0, false); |
36c2dfed VM |
211 | |
212 | out: | |
cbda09d0 VM |
213 | git_object_free(revspec.from); |
214 | git_object_free(revspec.to); | |
af079d8b GP |
215 | return error; |
216 | } | |
217 | ||
06b9d915 CMN |
218 | int git_revwalk_hide_ref(git_revwalk *walk, const char *refname) |
219 | { | |
220 | assert(walk && refname); | |
d465e4e9 | 221 | return push_ref(walk, refname, 1, false); |
f7367993 CMN |
222 | } |
223 | ||
4ff192d3 | 224 | static int revwalk_enqueue_timesort(git_revwalk *walk, git_commit_list_node *commit) |
3315782c | 225 | { |
71db842f VM |
226 | return git_pqueue_insert(&walk->iterator_time, commit); |
227 | } | |
3315782c | 228 | |
4ff192d3 | 229 | static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *commit) |
71db842f | 230 | { |
4ff192d3 | 231 | return git_commit_list_insert(commit, &walk->iterator_rand) ? 0 : -1; |
71db842f | 232 | } |
3315782c | 233 | |
4ff192d3 | 234 | static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk) |
71db842f | 235 | { |
4ff192d3 | 236 | git_commit_list_node *next; |
5e15176d | 237 | |
c11c08a5 AN |
238 | while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) { |
239 | /* Some commits might become uninteresting after being added to the list */ | |
240 | if (!next->uninteresting) { | |
241 | *object_out = next; | |
242 | return 0; | |
243 | } | |
9db367bf | 244 | } |
08d5d000 | 245 | |
ac3d33df | 246 | git_error_clear(); |
f335ecd6 | 247 | return GIT_ITEROVER; |
3315782c VM |
248 | } |
249 | ||
4ff192d3 | 250 | static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk) |
3315782c | 251 | { |
ac3d33df | 252 | int error; |
4ff192d3 | 253 | git_commit_list_node *next; |
3315782c | 254 | |
ac3d33df | 255 | while (!(error = get_revision(&next, walk, &walk->iterator_rand))) { |
fedc05c8 CMN |
256 | /* Some commits might become uninteresting after being added to the list */ |
257 | if (!next->uninteresting) { | |
258 | *object_out = next; | |
259 | return 0; | |
260 | } | |
9db367bf | 261 | } |
3315782c | 262 | |
ac3d33df | 263 | return error; |
a7c182c5 | 264 | } |
1a895dd7 | 265 | |
4ff192d3 | 266 | static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk) |
a7c182c5 | 267 | { |
ac3d33df | 268 | int error; |
fedc05c8 | 269 | git_commit_list_node *next; |
15f7b9b8 | 270 | |
ac3d33df | 271 | while (!(error = get_revision(&next, walk, &walk->iterator_topo))) { |
fedc05c8 CMN |
272 | /* Some commits might become uninteresting after being added to the list */ |
273 | if (!next->uninteresting) { | |
274 | *object_out = next; | |
275 | return 0; | |
276 | } | |
71db842f | 277 | } |
48c64362 | 278 | |
ac3d33df | 279 | return error; |
5e15176d VM |
280 | } |
281 | ||
4ff192d3 | 282 | static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk) |
5e15176d | 283 | { |
4ff192d3 | 284 | *object_out = git_commit_list_pop(&walk->iterator_reverse); |
f335ecd6 | 285 | return *object_out ? 0 : GIT_ITEROVER; |
71db842f | 286 | } |
5e15176d | 287 | |
6708618c | 288 | static void mark_parents_uninteresting(git_commit_list_node *commit) |
e7970576 | 289 | { |
6708618c CMN |
290 | unsigned short i; |
291 | git_commit_list *parents = NULL; | |
e7970576 | 292 | |
6708618c CMN |
293 | for (i = 0; i < commit->out_degree; i++) |
294 | git_commit_list_insert(commit->parents[i], &parents); | |
e7970576 | 295 | |
6708618c CMN |
296 | |
297 | while (parents) { | |
013ecb4f | 298 | commit = git_commit_list_pop(&parents); |
6708618c CMN |
299 | |
300 | while (commit) { | |
301 | if (commit->uninteresting) | |
302 | break; | |
303 | ||
304 | commit->uninteresting = 1; | |
305 | /* | |
306 | * If we've reached this commit some other way | |
307 | * already, we need to mark its parents uninteresting | |
308 | * as well. | |
309 | */ | |
310 | if (!commit->parents) | |
311 | break; | |
312 | ||
313 | for (i = 0; i < commit->out_degree; i++) | |
314 | git_commit_list_insert(commit->parents[i], &parents); | |
315 | commit = commit->parents[0]; | |
316 | } | |
317 | } | |
e7970576 CMN |
318 | } |
319 | ||
6708618c | 320 | static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list) |
e7970576 | 321 | { |
e7970576 | 322 | unsigned short i; |
6708618c | 323 | int error; |
e7970576 | 324 | |
6708618c CMN |
325 | if (commit->added) |
326 | return 0; | |
e7970576 | 327 | |
6708618c CMN |
328 | commit->added = 1; |
329 | ||
6708618c CMN |
330 | /* |
331 | * Go full on in the uninteresting case as we want to include | |
332 | * as many of these as we can. | |
333 | * | |
334 | * Usually we haven't parsed the parent of a parent, but if we | |
335 | * have it we reached it via other means so we want to mark | |
336 | * its parents recursively too. | |
337 | */ | |
338 | if (commit->uninteresting) { | |
339 | for (i = 0; i < commit->out_degree; i++) { | |
340 | git_commit_list_node *p = commit->parents[i]; | |
341 | p->uninteresting = 1; | |
342 | ||
343 | /* git does it gently here, but we don't like missing objects */ | |
344 | if ((error = git_commit_list_parse(walk, p)) < 0) | |
345 | return error; | |
346 | ||
347 | if (p->parents) | |
348 | mark_parents_uninteresting(p); | |
349 | ||
350 | p->seen = 1; | |
351 | git_commit_list_insert_by_date(p, list); | |
352 | } | |
353 | ||
354 | return 0; | |
e7970576 CMN |
355 | } |
356 | ||
6708618c CMN |
357 | /* |
358 | * Now on to what we do if the commit is indeed | |
359 | * interesting. Here we do want things like first-parent take | |
360 | * effect as this is what we'll be showing. | |
361 | */ | |
362 | for (i = 0; i < commit->out_degree; i++) { | |
363 | git_commit_list_node *p = commit->parents[i]; | |
e7970576 | 364 | |
6708618c CMN |
365 | if ((error = git_commit_list_parse(walk, p)) < 0) |
366 | return error; | |
e7970576 | 367 | |
6708618c | 368 | if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload)) |
48c64362 | 369 | continue; |
e7970576 | 370 | |
6708618c CMN |
371 | if (!p->seen) { |
372 | p->seen = 1; | |
373 | git_commit_list_insert_by_date(p, list); | |
374 | } | |
375 | ||
376 | if (walk->first_parent) | |
377 | break; | |
378 | } | |
379 | return 0; | |
380 | } | |
e7970576 | 381 | |
6708618c CMN |
382 | /* How many unintersting commits we want to look at after we run out of interesting ones */ |
383 | #define SLOP 5 | |
384 | ||
385 | static int still_interesting(git_commit_list *list, int64_t time, int slop) | |
386 | { | |
387 | /* The empty list is pretty boring */ | |
388 | if (!list) | |
389 | return 0; | |
390 | ||
6c7cee42 RD |
391 | /* |
392 | * If the destination list has commits with an earlier date than our | |
393 | * source, we want to reset the slop counter as we're not done. | |
394 | */ | |
395 | if (time <= list->item->time) | |
396 | return SLOP; | |
397 | ||
4b3ec53c XL |
398 | for (; list; list = list->next) { |
399 | /* | |
6c7cee42 | 400 | * If the destination list still contains interesting commits we |
4b3ec53c XL |
401 | * want to continue looking. |
402 | */ | |
403 | if (!list->item->uninteresting || list->item->time > time) | |
404 | return SLOP; | |
405 | } | |
6708618c CMN |
406 | |
407 | /* Everything's uninteresting, reduce the count */ | |
408 | return slop - 1; | |
409 | } | |
410 | ||
411 | static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits) | |
412 | { | |
413 | int error, slop = SLOP; | |
6c7cee42 | 414 | int64_t time = INT64_MAX; |
6708618c CMN |
415 | git_commit_list *list = commits; |
416 | git_commit_list *newlist = NULL; | |
417 | git_commit_list **p = &newlist; | |
418 | ||
419 | while (list) { | |
420 | git_commit_list_node *commit = git_commit_list_pop(&list); | |
421 | ||
422 | if ((error = add_parents_to_list(walk, commit, &list)) < 0) | |
423 | return error; | |
424 | ||
425 | if (commit->uninteresting) { | |
426 | mark_parents_uninteresting(commit); | |
427 | ||
428 | slop = still_interesting(list, time, slop); | |
429 | if (slop) | |
e7970576 CMN |
430 | continue; |
431 | ||
6708618c | 432 | break; |
e7970576 | 433 | } |
6708618c | 434 | |
ac3d33df JK |
435 | if (walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload)) |
436 | continue; | |
6708618c CMN |
437 | |
438 | time = commit->time; | |
439 | p = &git_commit_list_insert(commit, p)->next; | |
e7970576 CMN |
440 | } |
441 | ||
48c64362 | 442 | git_commit_list_free(&list); |
6708618c CMN |
443 | *out = newlist; |
444 | return 0; | |
e7970576 CMN |
445 | } |
446 | ||
ac3d33df JK |
447 | static int get_revision(git_commit_list_node **out, git_revwalk *walk, git_commit_list **list) |
448 | { | |
449 | int error; | |
450 | git_commit_list_node *commit; | |
451 | ||
452 | commit = git_commit_list_pop(list); | |
453 | if (!commit) { | |
454 | git_error_clear(); | |
455 | return GIT_ITEROVER; | |
456 | } | |
457 | ||
458 | /* | |
459 | * If we did not run limit_list and we must add parents to the | |
460 | * list ourselves. | |
461 | */ | |
462 | if (!walk->limited) { | |
463 | if ((error = add_parents_to_list(walk, commit, list)) < 0) | |
464 | return error; | |
465 | } | |
466 | ||
467 | *out = commit; | |
468 | return 0; | |
469 | } | |
470 | ||
ea1ceb7f | 471 | static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list) |
48c64362 | 472 | { |
ea1ceb7f | 473 | git_commit_list *ll = NULL, *newlist, **pptr; |
48c64362 CMN |
474 | git_commit_list_node *next; |
475 | git_pqueue queue; | |
476 | git_vector_cmp queue_cmp = NULL; | |
477 | unsigned short i; | |
478 | int error; | |
479 | ||
480 | if (walk->sorting & GIT_SORT_TIME) | |
481 | queue_cmp = git_commit_list_time_cmp; | |
482 | ||
483 | if ((error = git_pqueue_init(&queue, 0, 8, queue_cmp))) | |
484 | return error; | |
485 | ||
486 | /* | |
487 | * Start by resetting the in-degree to 1 for the commits in | |
488 | * our list. We want to go through this list again, so we | |
489 | * store it in the commit list as we extract it from the lower | |
490 | * machinery. | |
491 | */ | |
ea1ceb7f CMN |
492 | for (ll = list; ll; ll = ll->next) { |
493 | ll->item->in_degree = 1; | |
48c64362 CMN |
494 | } |
495 | ||
48c64362 CMN |
496 | /* |
497 | * Count up how many children each commit has. We limit | |
498 | * ourselves to those commits in the original list (in-degree | |
499 | * of 1) avoiding setting it for any parent that was hidden. | |
500 | */ | |
501 | for(ll = list; ll; ll = ll->next) { | |
502 | for (i = 0; i < ll->item->out_degree; ++i) { | |
503 | git_commit_list_node *parent = ll->item->parents[i]; | |
504 | if (parent->in_degree) | |
505 | parent->in_degree++; | |
506 | } | |
507 | } | |
508 | ||
509 | /* | |
510 | * Now we find the tips i.e. those not reachable from any other node | |
511 | * i.e. those which still have an in-degree of 1. | |
512 | */ | |
513 | for(ll = list; ll; ll = ll->next) { | |
514 | if (ll->item->in_degree == 1) { | |
515 | if ((error = git_pqueue_insert(&queue, ll->item))) | |
516 | goto cleanup; | |
517 | } | |
518 | } | |
519 | ||
520 | /* | |
521 | * We need to output the tips in the order that they came out of the | |
522 | * traversal, so if we're not doing time-sorting, we need to reverse the | |
523 | * pqueue in order to get them to come out as we inserted them. | |
524 | */ | |
525 | if ((walk->sorting & GIT_SORT_TIME) == 0) | |
526 | git_pqueue_reverse(&queue); | |
527 | ||
528 | ||
529 | pptr = &newlist; | |
530 | newlist = NULL; | |
531 | while ((next = git_pqueue_pop(&queue)) != NULL) { | |
532 | for (i = 0; i < next->out_degree; ++i) { | |
533 | git_commit_list_node *parent = next->parents[i]; | |
534 | if (parent->in_degree == 0) | |
535 | continue; | |
536 | ||
537 | if (--parent->in_degree == 1) { | |
538 | if ((error = git_pqueue_insert(&queue, parent))) | |
539 | goto cleanup; | |
540 | } | |
541 | } | |
542 | ||
543 | /* All the children of 'item' have been emitted (since we got to it via the priority queue) */ | |
544 | next->in_degree = 0; | |
545 | ||
546 | pptr = &git_commit_list_insert(next, pptr)->next; | |
547 | } | |
548 | ||
549 | *out = newlist; | |
550 | error = 0; | |
551 | ||
552 | cleanup: | |
48c64362 CMN |
553 | git_pqueue_free(&queue); |
554 | return error; | |
555 | } | |
556 | ||
71db842f VM |
557 | static int prepare_walk(git_revwalk *walk) |
558 | { | |
6c7cee42 | 559 | int error = 0; |
6708618c | 560 | git_commit_list *list, *commits = NULL; |
ad66bf88 CMN |
561 | git_commit_list_node *next; |
562 | ||
9b5d6cea CMN |
563 | /* If there were no pushes, we know that the walk is already over */ |
564 | if (!walk->did_push) { | |
ac3d33df | 565 | git_error_clear(); |
9b5d6cea CMN |
566 | return GIT_ITEROVER; |
567 | } | |
568 | ||
6708618c CMN |
569 | for (list = walk->user_input; list; list = list->next) { |
570 | git_commit_list_node *commit = list->item; | |
571 | if ((error = git_commit_list_parse(walk, commit)) < 0) | |
572 | return error; | |
573 | ||
574 | if (commit->uninteresting) | |
575 | mark_parents_uninteresting(commit); | |
576 | ||
577 | if (!commit->seen) { | |
578 | commit->seen = 1; | |
579 | git_commit_list_insert(commit, &commits); | |
580 | } | |
581 | } | |
582 | ||
ac3d33df | 583 | if (walk->limited && (error = limit_list(&commits, walk, commits)) < 0) |
ea1ceb7f | 584 | return error; |
2e3a0055 | 585 | |
71db842f | 586 | if (walk->sorting & GIT_SORT_TOPOLOGICAL) { |
ea1ceb7f CMN |
587 | error = sort_in_topological_order(&walk->iterator_topo, walk, commits); |
588 | git_commit_list_free(&commits); | |
589 | ||
590 | if (error < 0) | |
44ef8b1b | 591 | return error; |
3315782c | 592 | |
71db842f | 593 | walk->get_next = &revwalk_next_toposort; |
ea1ceb7f CMN |
594 | } else if (walk->sorting & GIT_SORT_TIME) { |
595 | for (list = commits; list && !error; list = list->next) | |
596 | error = walk->enqueue(walk, list->item); | |
597 | ||
598 | git_commit_list_free(&commits); | |
599 | ||
600 | if (error < 0) | |
601 | return error; | |
602 | } else { | |
603 | walk->iterator_rand = commits; | |
604 | walk->get_next = revwalk_next_unsorted; | |
71db842f | 605 | } |
3315782c | 606 | |
71db842f | 607 | if (walk->sorting & GIT_SORT_REVERSE) { |
3315782c | 608 | |
44ef8b1b | 609 | while ((error = walk->get_next(&next, walk)) == 0) |
4ff192d3 | 610 | if (git_commit_list_insert(next, &walk->iterator_reverse) == NULL) |
eb8117b8 | 611 | return -1; |
3315782c | 612 | |
f335ecd6 | 613 | if (error != GIT_ITEROVER) |
44ef8b1b | 614 | return error; |
9bdb7594 | 615 | |
71db842f VM |
616 | walk->get_next = &revwalk_next_reverse; |
617 | } | |
40721f6b | 618 | |
71db842f | 619 | walk->walking = 1; |
eb8117b8 | 620 | return 0; |
71db842f | 621 | } |
3315782c | 622 | |
3315782c | 623 | |
36aaf1ff VM |
624 | int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo) |
625 | { | |
392702ee | 626 | git_revwalk *walk = git__calloc(1, sizeof(git_revwalk)); |
ac3d33df | 627 | GIT_ERROR_CHECK_ALLOC(walk); |
36aaf1ff | 628 | |
c2b67043 | 629 | walk->commits = git_oidmap_alloc(); |
ac3d33df | 630 | GIT_ERROR_CHECK_ALLOC(walk->commits); |
36aaf1ff | 631 | |
1e5e02b4 | 632 | if (git_pqueue_init(&walk->iterator_time, 0, 8, git_commit_list_time_cmp) < 0) |
eb8117b8 | 633 | return -1; |
36aaf1ff | 634 | |
1e5e02b4 | 635 | git_pool_init(&walk->commit_pool, COMMIT_ALLOC); |
36aaf1ff VM |
636 | walk->get_next = &revwalk_next_unsorted; |
637 | walk->enqueue = &revwalk_enqueue_unsorted; | |
638 | ||
639 | walk->repo = repo; | |
640 | ||
eb8117b8 | 641 | if (git_repository_odb(&walk->odb, repo) < 0) { |
9462c471 | 642 | git_revwalk_free(walk); |
eb8117b8 | 643 | return -1; |
9462c471 VM |
644 | } |
645 | ||
36aaf1ff | 646 | *revwalk_out = walk; |
eb8117b8 | 647 | return 0; |
36aaf1ff VM |
648 | } |
649 | ||
650 | void git_revwalk_free(git_revwalk *walk) | |
651 | { | |
36aaf1ff VM |
652 | if (walk == NULL) |
653 | return; | |
654 | ||
655 | git_revwalk_reset(walk); | |
9462c471 | 656 | git_odb_free(walk->odb); |
21d73e71 | 657 | |
c2b67043 | 658 | git_oidmap_free(walk->commits); |
da3b391c | 659 | git_pool_clear(&walk->commit_pool); |
36aaf1ff | 660 | git_pqueue_free(&walk->iterator_time); |
3286c408 | 661 | git__free(walk); |
36aaf1ff VM |
662 | } |
663 | ||
664 | git_repository *git_revwalk_repository(git_revwalk *walk) | |
665 | { | |
666 | assert(walk); | |
667 | return walk->repo; | |
668 | } | |
669 | ||
670 | void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode) | |
671 | { | |
672 | assert(walk); | |
673 | ||
674 | if (walk->walking) | |
675 | git_revwalk_reset(walk); | |
676 | ||
677 | walk->sorting = sort_mode; | |
678 | ||
679 | if (walk->sorting & GIT_SORT_TIME) { | |
680 | walk->get_next = &revwalk_next_timesort; | |
681 | walk->enqueue = &revwalk_enqueue_timesort; | |
682 | } else { | |
683 | walk->get_next = &revwalk_next_unsorted; | |
684 | walk->enqueue = &revwalk_enqueue_unsorted; | |
685 | } | |
ac3d33df JK |
686 | |
687 | if (walk->sorting != GIT_SORT_NONE) | |
688 | walk->limited = 1; | |
36aaf1ff VM |
689 | } |
690 | ||
15f7b9b8 CMN |
691 | void git_revwalk_simplify_first_parent(git_revwalk *walk) |
692 | { | |
693 | walk->first_parent = 1; | |
694 | } | |
695 | ||
71db842f VM |
696 | int git_revwalk_next(git_oid *oid, git_revwalk *walk) |
697 | { | |
698 | int error; | |
4ff192d3 | 699 | git_commit_list_node *next; |
3315782c | 700 | |
71db842f | 701 | assert(walk && oid); |
3315782c | 702 | |
71db842f | 703 | if (!walk->walking) { |
eb8117b8 | 704 | if ((error = prepare_walk(walk)) < 0) |
44ef8b1b | 705 | return error; |
71db842f | 706 | } |
3315782c | 707 | |
71db842f | 708 | error = walk->get_next(&next, walk); |
ce90d81f | 709 | |
f335ecd6 | 710 | if (error == GIT_ITEROVER) { |
ce90d81f | 711 | git_revwalk_reset(walk); |
ac3d33df | 712 | git_error_clear(); |
f335ecd6 | 713 | return GIT_ITEROVER; |
36aaf1ff | 714 | } |
3315782c | 715 | |
44ef8b1b RB |
716 | if (!error) |
717 | git_oid_cpy(oid, &next->oid); | |
ce90d81f | 718 | |
44ef8b1b | 719 | return error; |
3315782c VM |
720 | } |
721 | ||
71db842f | 722 | void git_revwalk_reset(git_revwalk *walk) |
3315782c | 723 | { |
4ff192d3 | 724 | git_commit_list_node *commit; |
3315782c | 725 | |
71db842f | 726 | assert(walk); |
9bdb7594 | 727 | |
9694d9ba | 728 | git_oidmap_foreach_value(walk->commits, commit, { |
71db842f VM |
729 | commit->seen = 0; |
730 | commit->in_degree = 0; | |
731 | commit->topo_delay = 0; | |
97313ce2 | 732 | commit->uninteresting = 0; |
6708618c | 733 | commit->added = 0; |
42835aa6 | 734 | commit->flags = 0; |
01fed0a8 | 735 | }); |
9bdb7594 | 736 | |
36aaf1ff | 737 | git_pqueue_clear(&walk->iterator_time); |
4ff192d3 BS |
738 | git_commit_list_free(&walk->iterator_topo); |
739 | git_commit_list_free(&walk->iterator_rand); | |
740 | git_commit_list_free(&walk->iterator_reverse); | |
ad66bf88 | 741 | git_commit_list_free(&walk->user_input); |
d6afda62 | 742 | walk->first_parent = 0; |
71db842f | 743 | walk->walking = 0; |
ac3d33df | 744 | walk->limited = 0; |
9b5d6cea | 745 | walk->did_push = walk->did_hide = 0; |
ac3d33df | 746 | walk->sorting = GIT_SORT_NONE; |
08d5d000 | 747 | } |
36b7cdb6 | 748 | |
892aa808 AG |
749 | int git_revwalk_add_hide_cb( |
750 | git_revwalk *walk, | |
751 | git_revwalk_hide_cb hide_cb, | |
752 | void *payload) | |
753 | { | |
754 | assert(walk); | |
755 | ||
756 | if (walk->walking) | |
757 | git_revwalk_reset(walk); | |
758 | ||
892aa808 AG |
759 | walk->hide_cb = hide_cb; |
760 | walk->hide_cb_payload = payload; | |
761 | ||
ac3d33df JK |
762 | if (hide_cb) |
763 | walk->limited = 1; | |
764 | ||
892aa808 AG |
765 | return 0; |
766 | } | |
767 |