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 static const struct got_error *
541 free_node_iter(struct got_object_id *id, void *data, void *arg)
542 {
543 	struct got_commit_graph_node *node = data;
544 	free(node);
545 	return NULL;
546 }
547 
548 void
549 got_commit_graph_close(struct got_commit_graph *graph)
550 {
551 	got_object_idset_free(graph->open_branches);
552 	got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
553 	got_object_idset_free(graph->node_ids);
554 	free(graph->tips);
555 	free(graph->path);
556 	free(graph);
557 }
558 
559 const struct got_error *
560 got_commit_graph_iter_start(struct got_commit_graph *graph,
561     struct got_object_id *id, struct got_repository *repo,
562     got_cancel_cb cancel_cb, void *cancel_arg)
563 {
564 	const struct got_error *err = NULL;
565 	struct got_commit_graph_node *start_node;
566 	struct got_commit_object *commit;
567 	int changed;
568 
569 	start_node = got_object_idset_get(graph->node_ids, id);
570 	while (start_node == NULL) {
571 		int ncommits;
572 		err = fetch_commits_from_open_branches(&ncommits, NULL, graph,
573 		    repo, cancel_cb, cancel_arg);
574 		if (err)
575 			return err;
576 		if (ncommits == 0)
577 			return got_error_no_obj(id);
578 		start_node = got_object_idset_get(graph->node_ids, id);
579 	}
580 
581 	err = got_object_open_as_commit(&commit, repo, &start_node->id);
582 	if (err)
583 		return err;
584 
585 	err = detect_changed_path(&changed, commit, &start_node->id,
586 	    graph->path, repo);
587 	if (err) {
588 		got_object_commit_close(commit);
589 		return err;
590 	}
591 
592 	if (!changed) {
593 		/* Locate first commit which changed graph->path. */
594 		struct got_object_id *changed_id = NULL;
595 		while (changed_id == NULL) {
596 			int ncommits;
597 			err = fetch_commits_from_open_branches(&ncommits,
598 			    &changed_id, graph, repo, cancel_cb, cancel_arg);
599 			if (err) {
600 				got_object_commit_close(commit);
601 				return err;
602 			}
603 		}
604 		start_node = got_object_idset_get(graph->node_ids, changed_id);
605 	}
606 	got_object_commit_close(commit);
607 
608 	graph->iter_node = start_node;
609 	return NULL;
610 }
611 
612 const struct got_error *
613 got_commit_graph_iter_next(struct got_object_id **id,
614     struct got_commit_graph *graph, struct got_repository *repo,
615     got_cancel_cb cancel_cb, void *cancel_arg)
616 {
617 	const struct got_error *err = NULL;
618 
619 	*id = NULL;
620 
621 	if (graph->iter_node == NULL) {
622 		/* We are done iterating, or iteration was not started. */
623 		return got_error(GOT_ERR_ITER_COMPLETED);
624 	}
625 
626 	if (graph->iter_node ==
627 	    TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
628 	    got_object_idset_num_elements(graph->open_branches) == 0) {
629 		/* We are done iterating. */
630 		*id = &graph->iter_node->id;
631 		graph->iter_node = NULL;
632 		return NULL;
633 	}
634 
635 	while (TAILQ_NEXT(graph->iter_node, entry) == NULL &&
636 	    got_object_idset_num_elements(graph->open_branches) > 0) {
637 		int ncommits;
638 		struct got_object_id *changed_id;
639 		err = fetch_commits_from_open_branches(&ncommits,
640 		    &changed_id, graph, repo, cancel_cb, cancel_arg);
641 		if (err)
642 			return err;
643 	}
644 
645 	*id = &graph->iter_node->id;
646 	graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
647 	return NULL;
648 }
649 
650 const struct got_error *
651 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
652     struct got_object_id *commit_id, struct got_object_id *commit_id2,
653     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
654 {
655 	const struct got_error *err = NULL;
656 	struct got_commit_graph *graph = NULL, *graph2 = NULL;
657 	int completed = 0, completed2 = 0;
658 	struct got_object_idset *commit_ids;
659 
660 	*yca_id = NULL;
661 
662 	commit_ids = got_object_idset_alloc();
663 	if (commit_ids == NULL)
664 		return got_error_from_errno("got_object_idset_alloc");
665 
666 	err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
667 	if (err)
668 		goto done;
669 
670 	err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
671 	if (err)
672 		goto done;
673 
674 	err = got_commit_graph_iter_start(graph, commit_id, repo,
675 	    cancel_cb, cancel_arg);
676 	if (err)
677 		goto done;
678 
679 	err = got_commit_graph_iter_start(graph2, commit_id2, repo,
680 	    cancel_cb, cancel_arg);
681 	if (err)
682 		goto done;
683 
684 	for (;;) {
685 		struct got_object_id *id = NULL, *id2 = NULL;
686 
687 		if (cancel_cb) {
688 			err = (*cancel_cb)(cancel_arg);
689 			if (err)
690 				break;
691 		}
692 
693 		if (!completed) {
694 			err = got_commit_graph_iter_next(&id, graph, repo,
695 			    cancel_cb, cancel_arg);
696 			if (err) {
697 				if (err->code != GOT_ERR_ITER_COMPLETED)
698 					break;
699 				err = NULL;
700 				completed = 1;
701 			}
702 		}
703 
704 		if (!completed2) {
705 			err = got_commit_graph_iter_next(&id2, graph2, repo,
706 			    cancel_cb, cancel_arg);
707 			if (err) {
708 				if (err->code != GOT_ERR_ITER_COMPLETED)
709 					break;
710 				err = NULL;
711 				completed2 = 1;
712 			}
713 		}
714 
715 		if (id) {
716 			if (got_object_idset_get(commit_ids, id)) {
717 				*yca_id = got_object_id_dup(id);
718 				if (*yca_id)
719 					break;
720 				err = got_error_from_errno("got_object_id_dup");
721 				break;
722 
723 			}
724 			err = got_object_idset_add(commit_ids, id, id);
725 			if (err)
726 				break;
727 		}
728 		if (id2) {
729 			if (got_object_idset_get(commit_ids, id2)) {
730 				*yca_id = got_object_id_dup(id2);
731 				if (*yca_id)
732 					break;
733 				err = got_error_from_errno("got_object_id_dup");
734 				break;
735 
736 			}
737 			err = got_object_idset_add(commit_ids, id2, id2);
738 			if (err)
739 				break;
740 		}
741 
742 		if (completed && completed2) {
743 			err = got_error(GOT_ERR_ANCESTRY);
744 			break;
745 		}
746 
747 	}
748 done:
749 	got_object_idset_free(commit_ids);
750 	if (graph)
751 		got_commit_graph_close(graph);
752 	if (graph2)
753 		got_commit_graph_close(graph2);
754 	return err;
755 }