1 /*
2  * Copyright (c) 2018 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/types.h>
18 #include <sys/stat.h>
19 #include <sys/queue.h>
20 #include <sys/stdint.h>
21 
22 #include <limits.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <sha1.h>
27 #include <zlib.h>
28 #include <ctype.h>
29 
30 #include "got_error.h"
31 #include "got_object.h"
32 #include "got_cancel.h"
33 #include "got_commit_graph.h"
34 #include "got_path.h"
35 
36 #include "got_lib_delta.h"
37 #include "got_lib_inflate.h"
38 #include "got_lib_object.h"
39 #include "got_lib_object_idset.h"
40 
41 struct got_commit_graph_node {
42 	struct got_object_id id;
43 	time_t timestamp;
44 
45 	/* Used during graph iteration. */
46 	TAILQ_ENTRY(got_commit_graph_node) entry;
47 };
48 
49 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
50 
51 struct got_commit_graph_branch_tip {
52 	struct got_object_id *commit_id;
53 	struct got_commit_object *commit;
54 	struct got_commit_graph_node *new_node;
55 	int changed;
56 	int branch_done;
57 };
58 
59 struct got_commit_graph {
60 	/* The set of all commits we have traversed. */
61 	struct got_object_idset *node_ids;
62 
63 	/* The commit at which traversal began (youngest commit in node_ids). */
64 	struct got_commit_graph_node *head_node;
65 
66 	int flags;
67 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL		0x01
68 
69 	/*
70 	 * A set of object IDs of known parent commits which we have not yet
71 	 * traversed. Each commit ID in this set represents a branch in commit
72 	 * history: Either the first-parent branch of the head node, or another
73 	 * branch corresponding to a traversed merge commit for which we have
74 	 * not traversed a branch point commit yet.
75 	 *
76 	 * Whenever we add a commit with a matching ID to the graph, we remove
77 	 * its corresponding element from this set, and add new elements for
78 	 * each of that commit's parent commits which were not traversed yet.
79 	 *
80 	 * When API users ask us to fetch more commits, we fetch commits from
81 	 * all currently open branches. This allows API users to process
82 	 * commits in linear order even though the history contains branches.
83 	 */
84 	struct got_object_idset *open_branches;
85 
86 	/* Array of branch tips for fetch_commits_from_open_branches(). */
87 	struct got_commit_graph_branch_tip *tips;
88 	int ntips;
89 
90 	/* Path of tree entry of interest to the API user. */
91 	char *path;
92 
93 	/* The next commit to return when the API user asks for one. */
94 	struct got_commit_graph_node *iter_node;
95 
96 	/* The graph iteration list contains all nodes in sorted order. */
97 	struct got_commit_graph_iter_list iter_list;
98 };
99 
100 static struct got_commit_graph *
101 alloc_graph(const char *path)
102 {
103 	struct got_commit_graph *graph;
104 
105 	graph = calloc(1, sizeof(*graph));
106 	if (graph == NULL)
107 		return NULL;
108 
109 	graph->path = strdup(path);
110 	if (graph->path == NULL) {
111 		free(graph);
112 		return NULL;
113 	}
114 
115 	graph->node_ids = got_object_idset_alloc();
116 	if (graph->node_ids == NULL) {
117 		free(graph->path);
118 		free(graph);
119 		return NULL;
120 	}
121 
122 	graph->open_branches = got_object_idset_alloc();
123 	if (graph->open_branches == NULL) {
124 		got_object_idset_free(graph->node_ids);
125 		free(graph->path);
126 		free(graph);
127 		return NULL;
128 	}
129 
130 	TAILQ_INIT(&graph->iter_list);
131 	return graph;
132 }
133 
134 static const struct got_error *
135 detect_changed_path(int *changed, struct got_commit_object *commit,
136     struct got_object_id *commit_id, const char *path,
137     struct got_repository *repo)
138 {
139 	const struct got_error *err = NULL;
140 	struct got_commit_object *pcommit = NULL;
141 	struct got_tree_object *tree = NULL, *ptree = NULL;
142 	struct got_object_qid *pid;
143 
144 	if (got_path_is_root_dir(path)) {
145 		*changed = 1;
146 		return NULL;
147 	}
148 
149 	*changed = 0;
150 
151 	pid = SIMPLEQ_FIRST(&commit->parent_ids);
152 	if (pid == NULL) {
153 		struct got_object_id *obj_id;
154 		err = got_object_id_by_path(&obj_id, repo, commit_id, path);
155 		if (err) {
156 			if (err->code == GOT_ERR_NO_TREE_ENTRY)
157 				err = NULL;
158 		} else
159 			*changed = 1; /* The path was created in this commit. */
160 		free(obj_id);
161 		return err;
162 	}
163 
164 	err = got_object_open_as_tree(&tree, repo, commit->tree_id);
165 	if (err)
166 		return err;
167 
168 	err = got_object_open_as_commit(&pcommit, repo, pid->id);
169 	if (err)
170 		goto done;
171 
172 	err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
173 	if (err)
174 		goto done;
175 
176 	err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
177 done:
178 	if (tree)
179 		got_object_tree_close(tree);
180 	if (ptree)
181 		got_object_tree_close(ptree);
182 	if (pcommit)
183 		got_object_commit_close(pcommit);
184 	return err;
185 }
186 
187 static void
188 add_node_to_iter_list(struct got_commit_graph *graph,
189     struct got_commit_graph_node *node,
190     struct got_commit_graph_node *child_node)
191 {
192 	struct got_commit_graph_node *n, *next;
193 
194 	if (TAILQ_EMPTY(&graph->iter_list)) {
195 		TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
196 		graph->iter_node = node;
197 		return;
198 	}
199 
200 	n = graph->iter_node;
201 	/* Ensure that an iteration in progress will see this new commit. */
202 	while (n) {
203 		next = TAILQ_NEXT(n, entry);
204 		if (next && node->timestamp >= next->timestamp) {
205 			TAILQ_INSERT_BEFORE(next, node, entry);
206 			return;
207 		}
208 		n = next;
209 	}
210 	TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
211 }
212 
213 static const struct got_error *
214 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
215 {
216 	const struct got_error *err;
217 
218 	err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
219 	if (err && err->code != GOT_ERR_NO_OBJ)
220 		return err;
221 	return NULL;
222 }
223 
224 static const struct got_error *
225 advance_branch(struct got_commit_graph *graph,
226     struct got_commit_graph_node *node,
227     struct got_object_id *commit_id, struct got_commit_object *commit,
228     struct got_repository *repo)
229 {
230 	const struct got_error *err;
231 	struct got_object_qid *qid;
232 
233 	err = close_branch(graph, commit_id);
234 	if (err)
235 		return err;
236 
237 	if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
238 		qid = SIMPLEQ_FIRST(&commit->parent_ids);
239 		if (qid == NULL ||
240 		    got_object_idset_get(graph->open_branches, qid->id))
241 			return NULL;
242 		return got_object_idset_add(graph->open_branches,
243 		    qid->id, node);
244 	}
245 
246 	/*
247 	 * If we are graphing commits for a specific path, skip branches
248 	 * which do not contribute any content to this path.
249 	 */
250 	if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
251 		struct got_object_id *merged_id, *prev_id = NULL;
252 		int branches_differ = 0;
253 
254 		err = got_object_id_by_path(&merged_id, repo, commit_id,
255 		    graph->path);
256 		if (err)
257 			return err;
258 
259 		SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
260 			struct got_object_id *id;
261 
262 			if (got_object_idset_get(graph->open_branches, qid->id))
263 				continue;
264 
265 			err = got_object_id_by_path(&id, repo, qid->id,
266 			    graph->path);
267 			if (err) {
268 				if (err->code == GOT_ERR_NO_TREE_ENTRY) {
269 					branches_differ = 1;
270 					continue;
271 				}
272 				free(merged_id);
273 				free(prev_id);
274 				return err;
275 			}
276 
277 			if (prev_id) {
278 				if (!branches_differ &&
279 				    got_object_id_cmp(id, prev_id) != 0)
280 					branches_differ = 1;
281 				free(prev_id);
282 			}
283 			prev_id = id;
284 
285 			/*
286 			 * If a branch has created the merged content we can
287 			 * skip any other branches.
288 			 */
289 			if (got_object_id_cmp(merged_id, id) == 0) {
290 				err = got_object_idset_add(graph->open_branches,
291 				    qid->id, node);
292 				free(merged_id);
293 				free(id);
294 				return err;
295 			}
296 		}
297 
298 		free(prev_id);
299 		prev_id = NULL;
300 		free(merged_id);
301 		merged_id = NULL;
302 
303 		/*
304 		 * If the path's content is the same on all branches,
305 		 * follow the first parent only.
306 		 */
307 		if (!branches_differ) {
308 			qid = SIMPLEQ_FIRST(&commit->parent_ids);
309 			if (qid == NULL)
310 				return NULL;
311 			if (got_object_idset_get(graph->open_branches, qid->id))
312 				return NULL;
313 			if (got_object_idset_get(graph->node_ids, qid->id))
314 				return NULL; /* parent already traversed */
315 			return got_object_idset_add(graph->open_branches,
316 			    qid->id, node);
317 		}
318 	}
319 
320 	SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
321 		if (got_object_idset_get(graph->open_branches, qid->id))
322 			continue;
323 		if (got_object_idset_get(graph->node_ids, qid->id))
324 			continue; /* parent already traversed */
325 		err = got_object_idset_add(graph->open_branches, qid->id, node);
326 		if (err)
327 			return err;
328 	}
329 
330 	return NULL;
331 }
332 
333 static const struct got_error *
334 add_node(struct got_commit_graph_node **new_node, int *changed,
335     int *branch_done, struct got_commit_graph *graph,
336     struct got_object_id *commit_id, struct got_commit_object *commit,
337     struct got_commit_graph_node *child_node, struct got_repository *repo)
338 {
339 	const struct got_error *err = NULL;
340 	struct got_commit_graph_node *node;
341 
342 	*new_node = NULL;
343 	*changed = 0;
344 	*branch_done = 0;
345 
346 	node = calloc(1, sizeof(*node));
347 	if (node == NULL)
348 		return got_error_from_errno("calloc");
349 
350 	memcpy(&node->id, commit_id, sizeof(node->id));
351 	node->timestamp = commit->committer_time;
352 
353 	err = got_object_idset_add(graph->node_ids, &node->id, node);
354 	if (err) {
355 		free(node);
356 		return err;
357 	}
358 
359 	err = detect_changed_path(changed, commit, commit_id, graph->path,
360 	    repo);
361 	if (err) {
362 		if (err->code == GOT_ERR_NO_OBJ) {
363 			/*
364 			 * History of the path stops here on the current
365 			 * branch. Keep going on other branches.
366 			 */
367 			err = NULL;
368 			*branch_done = 1;
369 		} else {
370 			got_object_idset_remove(NULL, graph->node_ids,
371 			    &node->id);
372 			free(node);
373 			return err;
374 		}
375 	}
376 
377 	if (*changed)
378 		add_node_to_iter_list(graph, node, child_node);
379 	*new_node = node;
380 	return NULL;
381 }
382 
383 const struct got_error *
384 got_commit_graph_open(struct got_commit_graph **graph,
385     struct got_object_id *commit_id, const char *path,
386     int first_parent_traversal, struct got_repository *repo)
387 {
388 	const struct got_error *err = NULL;
389 	struct got_commit_object *commit;
390 	int changed, branch_done;
391 
392 	*graph = NULL;
393 
394 	err = got_object_open_as_commit(&commit, repo, commit_id);
395 	if (err)
396 		return err;
397 
398 	/* The path must exist in our initial commit. */
399 	if (!got_path_is_root_dir(path)) {
400 		struct got_object_id *obj_id;
401 		err = got_object_id_by_path(&obj_id, repo, commit_id, path);
402 		if (err)
403 			return err;
404 		free(obj_id);
405 	}
406 
407 	*graph = alloc_graph(path);
408 	if (*graph == NULL) {
409 		err = got_error_from_errno("alloc_graph");
410 		got_object_commit_close(commit);
411 		return err;
412 	}
413 
414 	if (first_parent_traversal)
415 		(*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
416 
417 	err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
418 	    commit_id, commit, NULL, repo);
419 	if (err == NULL) {
420 		err = advance_branch(*graph, (*graph)->head_node, commit_id,
421 		    commit, repo);
422 	}
423 	got_object_commit_close(commit);
424 	if (err) {
425 		got_commit_graph_close(*graph);
426 		*graph = NULL;
427 		return err;
428 	}
429 	
430 	return NULL;
431 }
432 
433 struct add_branch_tip_arg {
434 	struct got_commit_graph_branch_tip *tips;
435 	int ntips;
436 	struct got_repository *repo;
437 	struct got_commit_graph *graph;
438 };
439 
440 static const struct got_error *
441 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
442 {
443 	const struct got_error *err;
444 	struct got_commit_graph_node *child_node = data;
445 	struct add_branch_tip_arg *a = arg;
446 	struct got_commit_graph_node *new_node;
447 	struct got_commit_object *commit;
448 	int changed, branch_done;
449 
450 	err = got_object_open_as_commit(&commit, a->repo, commit_id);
451 	if (err)
452 		return err;
453 
454 	err = add_node(&new_node, &changed, &branch_done, a->graph,
455 	    commit_id, commit, child_node, a->repo);
456 	if (err)
457 		return err;
458 
459 	a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
460 	a->tips[a->ntips].commit = commit;
461 	a->tips[a->ntips].new_node = new_node;
462 	a->tips[a->ntips].changed = changed;
463 	a->tips[a->ntips].branch_done = branch_done;
464 	a->ntips++;
465 
466 	return NULL;
467 }
468 
469 static const struct got_error *
470 fetch_commits_from_open_branches(int *nfetched,
471     struct got_object_id **changed_id, struct got_commit_graph *graph,
472     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
473 {
474 	const struct got_error *err;
475 	struct add_branch_tip_arg arg;
476 	int i, ntips;
477 
478 	*nfetched = 0;
479 	if (changed_id)
480 		*changed_id = NULL;
481 
482 	ntips = got_object_idset_num_elements(graph->open_branches);
483 	if (ntips == 0)
484 		return NULL;
485 
486 	/* (Re-)allocate branch tips array if necessary. */
487 	if (graph->ntips < ntips) {
488 		struct got_commit_graph_branch_tip *tips;
489 		tips = recallocarray(graph->tips, graph->ntips, ntips,
490 		    sizeof(*tips));
491 		if (tips == NULL)
492 			return got_error_from_errno("recallocarray");
493 		graph->tips = tips;
494 		graph->ntips = ntips;
495 	}
496 	arg.tips = graph->tips;
497 	arg.ntips = 0; /* add_branch_tip() will increment */
498 	arg.repo = repo;
499 	arg.graph = graph;
500 	err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
501 	    &arg);
502 	if (err)
503 		goto done;
504 
505 	for (i = 0; i < arg.ntips; i++) {
506 		struct got_object_id *commit_id;
507 		struct got_commit_object *commit;
508 		struct got_commit_graph_node *new_node;
509 		int branch_done, changed;
510 
511 		if (cancel_cb) {
512 			err = (*cancel_cb)(cancel_arg);
513 			if (err)
514 				break;
515 		}
516 
517 		commit_id = arg.tips[i].commit_id;
518 		commit = arg.tips[i].commit;
519 		new_node = arg.tips[i].new_node;
520 		branch_done = arg.tips[i].branch_done;
521 		changed = arg.tips[i].changed;
522 
523 		if (branch_done)
524 			err = close_branch(graph, commit_id);
525 		else
526 			err = advance_branch(graph, new_node, commit_id,
527 			    commit, repo);
528 		if (err)
529 			break;
530 		if (changed && changed_id && *changed_id == NULL)
531 			*changed_id = commit_id;
532 	}
533 done:
534 	for (i = 0; i < arg.ntips; i++)
535 		got_object_commit_close(arg.tips[i].commit);
536 	(*nfetched) = arg.ntips;
537 	return err;
538 }
539 
540 const struct got_error *
541 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
542     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
543 {
544 	const struct got_error *err;
545 	int nfetched = 0, ncommits;
546 	struct got_object_id *changed_id = NULL;
547 
548 	while (nfetched < limit) {
549 		if (cancel_cb) {
550 			err = (*cancel_cb)(cancel_arg);
551 			if (err)
552 				return err;
553 		}
554 		err = fetch_commits_from_open_branches(&ncommits,
555 		    &changed_id, graph, repo, cancel_cb, cancel_arg);
556 		if (err)
557 			return err;
558 		if (ncommits == 0)
559 			break;
560 		if (changed_id)
561 			nfetched += ncommits;
562 	}
563 
564 	return NULL;
565 }
566 
567 static const struct got_error *
568 free_node_iter(struct got_object_id *id, void *data, void *arg)
569 {
570 	struct got_commit_graph_node *node = data;
571 	free(node);
572 	return NULL;
573 }
574 
575 void
576 got_commit_graph_close(struct got_commit_graph *graph)
577 {
578 	got_object_idset_free(graph->open_branches);
579 	got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
580 	got_object_idset_free(graph->node_ids);
581 	free(graph->tips);
582 	free(graph->path);
583 	free(graph);
584 }
585 
586 const struct got_error *
587 got_commit_graph_iter_start(struct got_commit_graph *graph,
588     struct got_object_id *id, struct got_repository *repo,
589     got_cancel_cb cancel_cb, void *cancel_arg)
590 {
591 	const struct got_error *err = NULL;
592 	struct got_commit_graph_node *start_node;
593 	struct got_commit_object *commit;
594 	int changed;
595 
596 	start_node = got_object_idset_get(graph->node_ids, id);
597 	while (start_node == NULL) {
598 		int ncommits;
599 		err = fetch_commits_from_open_branches(&ncommits, NULL, graph,
600 		    repo, cancel_cb, cancel_arg);
601 		if (err)
602 			return err;
603 		if (ncommits == 0)
604 			return got_error_no_obj(id);
605 		start_node = got_object_idset_get(graph->node_ids, id);
606 	}
607 
608 	err = got_object_open_as_commit(&commit, repo, &start_node->id);
609 	if (err)
610 		return err;
611 
612 	err = detect_changed_path(&changed, commit, &start_node->id,
613 	    graph->path, repo);
614 	if (err) {
615 		got_object_commit_close(commit);
616 		return err;
617 	}
618 
619 	if (!changed) {
620 		/* Locate first commit which changed graph->path. */
621 		struct got_object_id *changed_id = NULL;
622 		while (changed_id == NULL) {
623 			int ncommits;
624 			err = fetch_commits_from_open_branches(&ncommits,
625 			    &changed_id, graph, repo, cancel_cb, cancel_arg);
626 			if (err) {
627 				got_object_commit_close(commit);
628 				return err;
629 			}
630 		}
631 		start_node = got_object_idset_get(graph->node_ids, changed_id);
632 	}
633 	got_object_commit_close(commit);
634 
635 	graph->iter_node = start_node;
636 	return NULL;
637 }
638 
639 const struct got_error *
640 got_commit_graph_iter_next(struct got_object_id **id,
641     struct got_commit_graph *graph)
642 {
643 	*id = NULL;
644 
645 	if (graph->iter_node == NULL) {
646 		/* We are done iterating, or iteration was not started. */
647 		return got_error(GOT_ERR_ITER_COMPLETED);
648 	}
649 
650 	if (graph->iter_node ==
651 	    TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
652 	    got_object_idset_num_elements(graph->open_branches) == 0) {
653 		/* We are done iterating. */
654 		*id = &graph->iter_node->id;
655 		graph->iter_node = NULL;
656 		return NULL;
657 	}
658 
659 	if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
660 		return got_error(GOT_ERR_ITER_NEED_MORE);
661 
662 	*id = &graph->iter_node->id;
663 	graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
664 	return NULL;
665 }
666 
667 const struct got_error *
668 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
669     struct got_object_id *commit_id, struct got_object_id *commit_id2,
670     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
671 {
672 	const struct got_error *err = NULL;
673 	struct got_commit_graph *graph = NULL, *graph2 = NULL;
674 	int completed = 0, completed2 = 0;
675 	struct got_object_idset *commit_ids;
676 
677 	*yca_id = NULL;
678 
679 	commit_ids = got_object_idset_alloc();
680 	if (commit_ids == NULL)
681 		return got_error_from_errno("got_object_idset_alloc");
682 
683 	err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
684 	if (err)
685 		goto done;
686 
687 	err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
688 	if (err)
689 		goto done;
690 
691 	err = got_commit_graph_iter_start(graph, commit_id, repo,
692 	    cancel_cb, cancel_arg);
693 	if (err)
694 		goto done;
695 
696 	err = got_commit_graph_iter_start(graph2, commit_id2, repo,
697 	    cancel_cb, cancel_arg);
698 	if (err)
699 		goto done;
700 
701 	for (;;) {
702 		struct got_object_id *id, *id2;
703 
704 		if (cancel_cb) {
705 			err = (*cancel_cb)(cancel_arg);
706 			if (err)
707 				break;
708 		}
709 
710 		if (!completed) {
711 			err = got_commit_graph_iter_next(&id, graph);
712 			if (err) {
713 				if (err->code == GOT_ERR_ITER_COMPLETED)
714 					completed = 1;
715 				else if (err->code != GOT_ERR_ITER_NEED_MORE)
716 					break;
717 				err = got_commit_graph_fetch_commits(graph, 1,
718 				    repo, cancel_cb, cancel_arg);
719 				if (err)
720 					break;
721 			}
722 		}
723 
724 		if (!completed2) {
725 			err = got_commit_graph_iter_next(&id2, graph2);
726 			if (err) {
727 				if (err->code == GOT_ERR_ITER_COMPLETED)
728 					completed2 = 1;
729 				else if (err->code != GOT_ERR_ITER_NEED_MORE)
730 					break;
731 				err = got_commit_graph_fetch_commits(graph2, 1,
732 				    repo, cancel_cb, cancel_arg);
733 				if (err)
734 					break;
735 			}
736 		}
737 
738 		if (id) {
739 			if (got_object_idset_get(commit_ids, id)) {
740 				*yca_id = got_object_id_dup(id);
741 				if (*yca_id)
742 					break;
743 				err = got_error_from_errno("got_object_id_dup");
744 				break;
745 
746 			}
747 			err = got_object_idset_add(commit_ids, id, id);
748 			if (err)
749 				break;
750 		}
751 		if (id2) {
752 			if (got_object_idset_get(commit_ids, id2)) {
753 				*yca_id = got_object_id_dup(id2);
754 				if (*yca_id)
755 					break;
756 				err = got_error_from_errno("got_object_id_dup");
757 				break;
758 
759 			}
760 			err = got_object_idset_add(commit_ids, id2, id2);
761 			if (err)
762 				break;
763 		}
764 
765 		if (completed && completed2) {
766 			err = got_error(GOT_ERR_ANCESTRY);
767 			break;
768 		}
769 
770 	}
771 done:
772 	got_object_idset_free(commit_ids);
773 	if (graph)
774 		got_commit_graph_close(graph);
775 	if (graph2)
776 		got_commit_graph_close(graph2);
777 	return err;
778 }