lib/commit_graph.c

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