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