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