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