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 #include <sys/queue.h>
  20 #include <sys/tree.h>
  21 #include <sys/stdint.h>
  22
  23 #include <limits.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27 #include <zlib.h>
  28 #include <ctype.h>
  29
  30 #include "got_compat.h"
  31
  32 #include "got_error.h"
  33 #include "got_object.h"
  34 #include "got_cancel.h"
  35 #include "got_commit_graph.h"
  36 #include "got_path.h"
  37
  38 #include "got_lib_delta.h"
  39 #include "got_lib_inflate.h"
  40 #include "got_lib_object.h"
  41 #include "got_lib_object_idset.h"
  42 #include "got_lib_object_qid.h"
  43
  44 #ifndef nitems
  45 #define nitems(_a)      (sizeof((_a)) / sizeof((_a)[0]))
  46 #endif
  47
  48 struct got_commit_graph_node {
  49         struct got_object_id id;
  50
  51         /* Used for topological sorting. */
  52         struct got_commit_graph_node *parents[2];
  53         struct got_commit_graph_node **more_parents;
  54         int nparents;
  55         int indegree;
  56
  57         /* Used only during iteration. */
  58         time_t timestamp;
  59         TAILQ_ENTRY(got_commit_graph_node) entry;
  60 };
  61
  62 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
  63
  64 struct got_commit_graph_branch_tip {
  65         struct got_object_id *commit_id;
  66         struct got_commit_object *commit;
  67         struct got_commit_graph_node *new_node;
  68 };
  69
  70 struct got_commit_graph {
  71         /* The set of all commits we have traversed. */
  72         struct got_object_idset *node_ids;
  73
  74         int flags;
  75 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL         0x01
  76 #define GOT_COMMIT_GRAPH_TOPOSORT                       0x02
  77
  78         /*
  79          * A set of object IDs of known parent commits which we have not yet
  80          * traversed. Each commit ID in this set represents a branch in commit
  81          * history: Either the first-parent branch of the head node, or another
  82          * branch corresponding to a traversed merge commit for which we have
  83          * not traversed a branch point commit yet.
  84          *
  85          * Whenever we add a commit with a matching ID to the graph, we remove
  86          * its corresponding element from this set, and add new elements for
  87          * each of that commit's parent commits which were not traversed yet.
  88          *
  89          * When API users ask us to fetch more commits, we fetch commits from
  90          * all currently open branches. This allows API users to process
  91          * commits in linear order even though the history contains branches.
  92          */
  93         struct got_object_idset *open_branches;
  94
  95         /* Array of branch tips for fetch_commits_from_open_branches(). */
  96         struct got_commit_graph_branch_tip *tips;
  97         int ntips;
  98
  99         /* Path of tree entry of interest to the API user. */
 100         char *path;
 101
 102         /*
 103          * Nodes which will be passed to the API user next, sorted by
 104          * commit timestamp. Sorted in topological order only if topological
 105          * sorting was requested.
 106          */
 107         struct got_commit_graph_iter_list iter_list;
 108 };
 109
 110 static const struct got_error *
 111 detect_changed_path(int *changed, struct got_commit_object *commit,
 112     struct got_object_id *commit_id, const char *path,
 113     struct got_repository *repo)
 114 {
 115         const struct got_error *err = NULL;
 116         struct got_commit_object *pcommit = NULL;
 117         struct got_tree_object *tree = NULL, *ptree = NULL;
 118         struct got_object_qid *pid;
 119
 120         if (got_path_is_root_dir(path)) {
 121                 *changed = 1;
 122                 return NULL;
 123         }
 124
 125         *changed = 0;
 126
 127         pid = STAILQ_FIRST(&commit->parent_ids);
 128         if (pid == NULL) {
 129                 struct got_object_id *obj_id;
 130                 err = got_object_id_by_path(&obj_id, repo, commit, path);
 131                 if (err) {
 132                         if (err->code == GOT_ERR_NO_TREE_ENTRY)
 133                                 err = NULL;
 134                 } else
 135                         *changed = 1; /* The path was created in this commit. */
 136                 free(obj_id);
 137                 return err;
 138         }
 139
 140         err = got_object_open_as_tree(&tree, repo, commit->tree_id);
 141         if (err)
 142                 return err;
 143
 144         err = got_object_open_as_commit(&pcommit, repo, &pid->id);
 145         if (err)
 146                 goto done;
 147
 148         err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
 149         if (err)
 150                 goto done;
 151
 152         err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
 153 done:
 154         if (tree)
 155                 got_object_tree_close(tree);
 156         if (ptree)
 157                 got_object_tree_close(ptree);
 158         if (pcommit)
 159                 got_object_commit_close(pcommit);
 160         return err;
 161 }
 162
 163 static void
 164 add_node_to_iter_list(struct got_commit_graph *graph,
 165     struct got_commit_graph_node *node, time_t committer_time)
 166 {
 167         struct got_commit_graph_node *n, *next;
 168
 169         node->timestamp = committer_time;
 170
 171         n = TAILQ_FIRST(&graph->iter_list);
 172         while (n) {
 173                 next = TAILQ_NEXT(n, entry);
 174                 if (next && node->timestamp >= next->timestamp) {
 175                         TAILQ_INSERT_BEFORE(next, node, entry);
 176                         return;
 177                 }
 178                 n = next;
 179         }
 180         TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
 181 }
 182
 183 static const struct got_error *
 184 add_node(struct got_commit_graph_node **new_node,
 185     struct got_commit_graph *graph, struct got_object_id *commit_id,
 186     struct got_repository *repo)
 187 {
 188         const struct got_error *err = NULL;
 189         struct got_commit_graph_node *node;
 190
 191         *new_node = NULL;
 192
 193         node = calloc(1, sizeof(*node));
 194         if (node == NULL)
 195                 return got_error_from_errno("calloc");
 196
 197         memcpy(&node->id, commit_id, sizeof(node->id));
 198         node->nparents = -1;
 199         err = got_object_idset_add(graph->node_ids, &node->id, node);
 200         if (err)
 201                 free(node);
 202         else
 203                 *new_node = node;
 204         return err;
 205 }
 206
 207 /*
 208  * Ask got-read-pack to traverse first-parent history until a commit is
 209  * encountered which modified graph->path, or until the pack file runs
 210  * out of relevant commits. This is faster than sending an individual
 211  * request for each commit stored in the pack file.
 212  */
 213 static const struct got_error *
 214 packed_first_parent_traversal(int *ncommits_traversed,
 215     struct got_commit_graph *graph, struct got_object_id *commit_id,
 216     struct got_repository *repo)
 217 {
 218         const struct got_error *err = NULL;
 219         struct got_object_id_queue traversed_commits;
 220         struct got_object_qid *qid;
 221
 222         STAILQ_INIT(&traversed_commits);
 223         *ncommits_traversed = 0;
 224
 225         err = got_traverse_packed_commits(&traversed_commits,
 226             commit_id, graph->path, repo);
 227         if (err)
 228                 return err;
 229
 230         /* Add all traversed commits to the graph... */
 231         STAILQ_FOREACH(qid, &traversed_commits, entry) {
 232                 if (got_object_idset_contains(graph->open_branches, &qid->id))
 233                         continue;
 234                 if (got_object_idset_contains(graph->node_ids, &qid->id))
 235                         continue;
 236
 237                 (*ncommits_traversed)++;
 238
 239                 /* ... except the last commit is the new branch tip. */
 240                 if (STAILQ_NEXT(qid, entry) == NULL) {
 241                         err = got_object_idset_add(graph->open_branches,
 242                             &qid->id, NULL);
 243                         break;
 244                 }
 245
 246                 err = got_object_idset_add(graph->node_ids, &qid->id, NULL);
 247                 if (err)
 248                         break;
 249         }
 250
 251         got_object_id_queue_free(&traversed_commits);
 252         return err;
 253 }
 254
 255 static const struct got_error *
 256 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
 257 {
 258         const struct got_error *err;
 259
 260         err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
 261         if (err && err->code != GOT_ERR_NO_OBJ)
 262                 return err;
 263         return NULL;
 264 }
 265
 266 static const struct got_error *
 267 advance_branch(struct got_commit_graph *graph, struct got_object_id *commit_id,
 268     struct got_commit_object *commit, struct got_repository *repo)
 269 {
 270         const struct got_error *err;
 271         struct got_object_qid *qid;
 272         struct got_object_id *merged_id = NULL;
 273
 274         err = close_branch(graph, commit_id);
 275         if (err)
 276                 return err;
 277
 278         if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
 279                 qid = STAILQ_FIRST(&commit->parent_ids);
 280                 if (qid == NULL ||
 281                     got_object_idset_contains(graph->open_branches, &qid->id))
 282                         return NULL;
 283                 /*
 284                  * The root directory always changes by definition, and when
 285                  * logging the root we want to traverse consecutive commits
 286                  * even if they point at the same tree.
 287                  * But if we are looking for a specific path then we can avoid
 288                  * fetching packed commits which did not modify the path and
 289                  * only fetch their IDs. This speeds up 'got blame'.
 290                  */
 291                 if (!got_path_is_root_dir(graph->path) &&
 292                     (commit->flags & GOT_COMMIT_FLAG_PACKED)) {
 293                         int ncommits = 0;
 294                         err = packed_first_parent_traversal(&ncommits,
 295                             graph, &qid->id, repo);
 296                         if (err || ncommits > 0)
 297                                 return err;
 298                 }
 299                 return got_object_idset_add(graph->open_branches,
 300                     &qid->id, NULL);
 301         }
 302
 303         /*
 304          * If we are graphing commits for a specific path, skip branches
 305          * which do not contribute any content to this path.
 306          */
 307         if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
 308                 err = got_object_id_by_path(&merged_id, repo, commit, graph->path);
 309                 if (err && err->code != GOT_ERR_NO_TREE_ENTRY)
 310                         return err;
 311                 /* The requested path does not exist in this merge commit. */
 312         }
 313         if (commit->nparents > 1 && !got_path_is_root_dir(graph->path) &&
 314             merged_id != NULL) {
 315                 struct got_object_id *prev_id = NULL;
 316                 int branches_differ = 0;
 317
 318
 319                 STAILQ_FOREACH(qid, &commit->parent_ids, entry) {
 320                         struct got_object_id *id = NULL;
 321                         struct got_commit_object *pcommit = NULL;
 322
 323                         if (got_object_idset_contains(graph->open_branches,
 324                             &qid->id))
 325                                 continue;
 326
 327                         err = got_object_open_as_commit(&pcommit, repo,
 328                             &qid->id);
 329                         if (err) {
 330                                 free(merged_id);
 331                                 free(prev_id);
 332                                 return err;
 333                         }
 334                         err = got_object_id_by_path(&id, repo, pcommit,
 335                             graph->path);
 336                         got_object_commit_close(pcommit);
 337                         pcommit = NULL;
 338                         if (err) {
 339                                 if (err->code == GOT_ERR_NO_TREE_ENTRY) {
 340                                         branches_differ = 1;
 341                                         continue;
 342                                 }
 343                                 free(merged_id);
 344                                 free(prev_id);
 345                                 return err;
 346                         }
 347
 348                         if (prev_id) {
 349                                 if (!branches_differ &&
 350                                     got_object_id_cmp(id, prev_id) != 0)
 351                                         branches_differ = 1;
 352                                 free(prev_id);
 353                         }
 354                         prev_id = id;
 355
 356                         /*
 357                          * If a branch has created the merged content we can
 358                          * skip any other branches.
 359                          */
 360                         if (got_object_id_cmp(merged_id, id) == 0) {
 361                                 err = got_object_idset_add(graph->open_branches,
 362                                     &qid->id, NULL);
 363                                 free(merged_id);
 364                                 free(id);
 365                                 return err;
 366                         }
 367                 }
 368
 369                 free(prev_id);
 370                 prev_id = NULL;
 371                 free(merged_id);
 372                 merged_id = NULL;
 373
 374                 /*
 375                  * If the path's content is the same on all branches,
 376                  * follow the first parent only.
 377                  */
 378                 if (!branches_differ) {
 379                         qid = STAILQ_FIRST(&commit->parent_ids);
 380                         if (qid == NULL)
 381                                 return NULL;
 382                         if (got_object_idset_contains(graph->open_branches,
 383                             &qid->id))
 384                                 return NULL;
 385                         if (got_object_idset_contains(graph->node_ids,
 386                             &qid->id))
 387                                 return NULL; /* parent already traversed */
 388                         return got_object_idset_add(graph->open_branches,
 389                             &qid->id, NULL);
 390                 }
 391         }
 392
 393         STAILQ_FOREACH(qid, &commit->parent_ids, entry) {
 394                 if (got_object_idset_contains(graph->open_branches, &qid->id))
 395                         continue;
 396                 if (got_object_idset_contains(graph->node_ids, &qid->id))
 397                         continue; /* parent already traversed */
 398                 err = got_object_idset_add(graph->open_branches, &qid->id,
 399                     NULL);
 400                 if (err)
 401                         return err;
 402         }
 403
 404         return NULL;
 405 }
 406
 407 const struct got_error *
 408 got_commit_graph_open(struct got_commit_graph **graph,
 409     const char *path, int first_parent_traversal)
 410 {
 411         const struct got_error *err = NULL;
 412
 413         *graph = calloc(1, sizeof(**graph));
 414         if (*graph == NULL)
 415                 return got_error_from_errno("calloc");
 416
 417         TAILQ_INIT(&(*graph)->iter_list);
 418
 419         (*graph)->path = strdup(path);
 420         if ((*graph)->path == NULL) {
 421                 err = got_error_from_errno("strdup");
 422                 goto done;
 423         }
 424
 425         (*graph)->node_ids = got_object_idset_alloc();
 426         if ((*graph)->node_ids == NULL) {
 427                 err = got_error_from_errno("got_object_idset_alloc");
 428                 goto done;
 429         }
 430
 431         (*graph)->open_branches = got_object_idset_alloc();
 432         if ((*graph)->open_branches == NULL) {
 433                 err = got_error_from_errno("got_object_idset_alloc");
 434                 goto done;
 435         }
 436
 437         if (first_parent_traversal)
 438                 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
 439 done:
 440         if (err) {
 441                 got_commit_graph_close(*graph);
 442                 *graph = NULL;
 443         }
 444         return err;
 445 }
 446
 447 struct add_branch_tip_arg {
 448         struct got_commit_graph_branch_tip *tips;
 449         int ntips;
 450         struct got_repository *repo;
 451         struct got_commit_graph *graph;
 452 };
 453
 454 static const struct got_error *
 455 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
 456 {
 457         const struct got_error *err;
 458         struct add_branch_tip_arg *a = arg;
 459         struct got_commit_graph_node *new_node;
 460         struct got_commit_object *commit;
 461
 462         err = got_object_open_as_commit(&commit, a->repo, commit_id);
 463         if (err)
 464                 return err;
 465
 466         err = add_node(&new_node, a->graph, commit_id, a->repo);
 467         if (err) {
 468                 got_object_commit_close(commit);
 469                 return err;
 470         }
 471
 472         a->tips[a->ntips].commit_id = &new_node->id;
 473         a->tips[a->ntips].commit = commit;
 474         a->tips[a->ntips].new_node = new_node;
 475         a->ntips++;
 476
 477         return NULL;
 478 }
 479
 480 static const struct got_error *
 481 fetch_commits_from_open_branches(struct got_commit_graph *graph,
 482     struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
 483 {
 484         const struct got_error *err;
 485         struct add_branch_tip_arg arg;
 486         int i, ntips;
 487
 488         ntips = got_object_idset_num_elements(graph->open_branches);
 489         if (ntips == 0)
 490                 return NULL;
 491
 492         /* (Re-)allocate branch tips array if necessary. */
 493         if (graph->ntips < ntips) {
 494                 struct got_commit_graph_branch_tip *tips;
 495                 tips = recallocarray(graph->tips, graph->ntips, ntips,
 496                     sizeof(*tips));
 497                 if (tips == NULL)
 498                         return got_error_from_errno("recallocarray");
 499                 graph->tips = tips;
 500                 graph->ntips = ntips;
 501         }
 502         arg.tips = graph->tips;
 503         arg.ntips = 0; /* add_branch_tip() will increment */
 504         arg.repo = repo;
 505         arg.graph = graph;
 506         err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
 507             &arg);
 508         if (err)
 509                 goto done;
 510
 511         for (i = 0; i < arg.ntips; i++) {
 512                 struct got_object_id *commit_id;
 513                 struct got_commit_object *commit;
 514                 struct got_commit_graph_node *new_node;
 515                 int changed;
 516
 517                 if (cancel_cb) {
 518                         err = (*cancel_cb)(cancel_arg);
 519                         if (err)
 520                                 break;
 521                 }
 522
 523                 commit_id = arg.tips[i].commit_id;
 524                 commit = arg.tips[i].commit;
 525                 new_node = arg.tips[i].new_node;
 526
 527                 err = detect_changed_path(&changed, commit, commit_id,
 528                     graph->path, repo);
 529                 if (err) {
 530                         if (err->code != GOT_ERR_NO_OBJ)
 531                                 break;
 532                         /*
 533                          * History of the path stops here on the current
 534                          * branch. Keep going on other branches.
 535                          */
 536                         err = close_branch(graph, commit_id);
 537                         if (err)
 538                                 break;
 539                         continue;
 540                 }
 541                 if (changed) {
 542                         add_node_to_iter_list(graph, new_node,
 543                             got_object_commit_get_committer_time(commit));
 544                         arg.tips[i].new_node = NULL;
 545                 }
 546                 err = advance_branch(graph, commit_id, commit, repo);
 547                 if (err)
 548                         break;
 549         }
 550 done:
 551         for (i = 0; i < arg.ntips; i++) {
 552                 got_object_commit_close(arg.tips[i].commit);
 553                 free(arg.tips[i].new_node);
 554         }
 555         return err;
 556 }
 557
 558 void
 559 got_commit_graph_close(struct got_commit_graph *graph)
 560 {
 561         struct got_commit_graph_node *node;
 562
 563         while ((node = TAILQ_FIRST(&graph->iter_list))) {
 564                 TAILQ_REMOVE(&graph->iter_list, node, entry);
 565                 free(node->more_parents);
 566                 free(node);
 567         }
 568
 569         if (graph->open_branches)
 570                 got_object_idset_free(graph->open_branches);
 571         if (graph->node_ids)
 572                 got_object_idset_free(graph->node_ids);
 573         free(graph->tips);
 574         free(graph->path);
 575         free(graph);
 576 }
 577
 578 static const struct got_error *
 579 remove_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
 580 {
 581         struct got_object_idset *open_branches = arg;
 582
 583         return got_object_idset_remove(NULL, open_branches, commit_id);
 584 }
 585
 586 const struct got_error *
 587 got_commit_graph_bfsort(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 *node;
 593
 594         graph->flags &= ~GOT_COMMIT_GRAPH_TOPOSORT;
 595
 596         /* Clear left-over state from previous iteration attempts. */
 597         while ((node = TAILQ_FIRST(&graph->iter_list)))
 598                 TAILQ_REMOVE(&graph->iter_list, node, entry);
 599         err = got_object_idset_for_each(graph->open_branches,
 600             remove_branch_tip, graph->open_branches);
 601         if (err)
 602                 return err;
 603
 604         err = got_object_idset_add(graph->open_branches, id, NULL);
 605         if (err)
 606                 return err;
 607
 608         /* Locate first commit which changed graph->path. */
 609         while (TAILQ_EMPTY(&graph->iter_list) &&
 610             got_object_idset_num_elements(graph->open_branches) > 0) {
 611                 err = fetch_commits_from_open_branches(graph, repo,
 612                     cancel_cb, cancel_arg);
 613                 if (err)
 614                         return err;
 615         }
 616
 617         if (TAILQ_EMPTY(&graph->iter_list)) {
 618                 const char *path;
 619                 if (got_path_is_root_dir(graph->path))
 620                         return got_error_no_obj(id);
 621                 path = graph->path;
 622                 while (path[0] == '/')
 623                         path++;
 624                 return got_error_path(path, GOT_ERR_NO_TREE_ENTRY);
 625         }
 626
 627         return NULL;
 628 }
 629
 630 const struct got_error *
 631 got_commit_graph_iter_next(struct got_object_id *id,
 632     struct got_commit_graph *graph, struct got_repository *repo,
 633     got_cancel_cb cancel_cb, void *cancel_arg)
 634 {
 635         const struct got_error *err = NULL;
 636         struct got_commit_graph_node *node, *pnode;
 637         int i;
 638
 639         node = TAILQ_FIRST(&graph->iter_list);
 640         if (node == NULL) {
 641                 /* We are done iterating, or iteration was not started. */
 642                 return got_error(GOT_ERR_ITER_COMPLETED);
 643         }
 644
 645         if (graph->flags & GOT_COMMIT_GRAPH_TOPOSORT) {
 646                 /* At least one node with in-degree zero must exist. */
 647                 while (node->indegree != 0)
 648                         node = TAILQ_NEXT(node, entry);
 649         } else {
 650                 while (TAILQ_NEXT(node, entry) == NULL &&
 651                     got_object_idset_num_elements(graph->open_branches) > 0) {
 652                         err = fetch_commits_from_open_branches(graph, repo,
 653                             cancel_cb, cancel_arg);
 654                         if (err)
 655                                 return err;
 656                 }
 657         }
 658
 659         memcpy(id, &node->id, sizeof(*id));
 660
 661         TAILQ_REMOVE(&graph->iter_list, node, entry);
 662         if (graph->flags & GOT_COMMIT_GRAPH_TOPOSORT) {
 663                 /* When visiting a commit decrement in-degree of all parents. */
 664                 for (i = 0; i < node->nparents; i++) {
 665                         if (i < nitems(node->parents))
 666                                 pnode = node->parents[i];
 667                         else
 668                                 pnode = node->more_parents[i];
 669                         pnode->indegree--;
 670                 }
 671         }
 672         free(node);
 673         return NULL;
 674 }
 675
 676 static const struct got_error *
 677 find_yca_add_id(struct got_object_id **yca_id, struct got_commit_graph *graph,
 678     struct got_object_idset *commit_ids, struct got_repository *repo,
 679     got_cancel_cb cancel_cb, void *cancel_arg)
 680 {
 681         const struct got_error *err = NULL;
 682         struct got_object_id id;
 683
 684         err = got_commit_graph_iter_next(&id, graph, repo, cancel_cb,
 685             cancel_arg);
 686         if (err)
 687                 return err;
 688
 689         if (got_object_idset_contains(commit_ids, &id)) {
 690                 *yca_id = got_object_id_dup(&id);
 691                 if (*yca_id == NULL)
 692                         err = got_error_from_errno("got_object_id_dup");
 693                 return err;
 694         }
 695
 696         return got_object_idset_add(commit_ids, &id, NULL);
 697 }
 698
 699 /*
 700  * Sets *yca_id to the youngest common ancestor of commit_id and
 701  * commit_id2. Returns got_error(GOT_ERR_ANCESTRY) if they have no
 702  * common ancestors.
 703  *
 704  * If first_parent_traversal is nonzero, only linear history is considered.
 705  * If toposort is set then sort commits in topological order before
 706  * traversing them.
 707  */
 708 const struct got_error *
 709 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
 710     struct got_object_id *commit_id, struct got_object_id *commit_id2,
 711     int first_parent_traversal, int toposort, struct got_repository *repo,
 712     got_cancel_cb cancel_cb, void *cancel_arg)
 713 {
 714         const struct got_error *err = NULL;
 715         struct got_commit_graph *graph = NULL, *graph2 = NULL;
 716         int completed = 0, completed2 = 0;
 717         struct got_object_idset *commit_ids;
 718
 719         *yca_id = NULL;
 720
 721         commit_ids = got_object_idset_alloc();
 722         if (commit_ids == NULL)
 723                 return got_error_from_errno("got_object_idset_alloc");
 724
 725         err = got_commit_graph_open(&graph, "/", first_parent_traversal);
 726         if (err)
 727                 goto done;
 728
 729         err = got_commit_graph_open(&graph2, "/", first_parent_traversal);
 730         if (err)
 731                 goto done;
 732
 733         if (toposort) {
 734                 err = got_commit_graph_toposort(graph, commit_id, repo,
 735                     cancel_cb, cancel_arg);
 736                 if (err)
 737                         goto done;
 738
 739                 err = got_commit_graph_toposort(graph2, commit_id2, repo,
 740                     cancel_cb, cancel_arg);
 741                 if (err)
 742                         goto done;
 743         } else {
 744                 err = got_commit_graph_bfsort(graph, commit_id, repo,
 745                     cancel_cb, cancel_arg);
 746                 if (err)
 747                         goto done;
 748
 749                 err = got_commit_graph_bfsort(graph2, commit_id2, repo,
 750                     cancel_cb, cancel_arg);
 751                 if (err)
 752                         goto done;
 753         }
 754
 755         for (;;) {
 756                 if (cancel_cb) {
 757                         err = (*cancel_cb)(cancel_arg);
 758                         if (err)
 759                                 break;
 760                 }
 761
 762                 if (!completed) {
 763                         err = find_yca_add_id(yca_id, graph, commit_ids, repo,
 764                             cancel_cb, cancel_arg);
 765                         if (err) {
 766                                 if (err->code != GOT_ERR_ITER_COMPLETED)
 767                                         break;
 768                                 err = NULL;
 769                                 completed = 1;
 770                         }
 771                         if (*yca_id)
 772                                 break;
 773                 }
 774
 775                 if (!completed2) {
 776                         err = find_yca_add_id(yca_id, graph2, commit_ids, repo,
 777                             cancel_cb, cancel_arg);
 778                         if (err) {
 779                                 if (err->code != GOT_ERR_ITER_COMPLETED)
 780                                         break;
 781                                 err = NULL;
 782                                 completed2 = 1;
 783                         }
 784                         if (*yca_id)
 785                                 break;
 786                 }
 787
 788                 if (completed && completed2) {
 789                         err = got_error(GOT_ERR_ANCESTRY);
 790                         break;
 791                 }
 792         }
 793 done:
 794         got_object_idset_free(commit_ids);
 795         if (graph)
 796                 got_commit_graph_close(graph);
 797         if (graph2)
 798                 got_commit_graph_close(graph2);
 799         return err;
 800 }
 801
 802 /*
 803  * Sort the graph for traversal in topological order.
 804  *
 805  * This implementation is based on the description of topological sorting
 806  * of git commits by Derrick Stolee at
 807  * https://github.blog/2022-08-30-gits-database-internals-ii-commit-history-queries/#topological-sorting
 808  * which reads as follows:
 809  *
 810  * The basic algorithm for topological sorting is Kahn’s algorithm which
 811  * follows two big steps:
 812  * 1. Walk all reachable commits, counting the number of times a commit appears
 813  * as a parent of another commit. Call these numbers the in-degree of the
 814  * commit, referencing the number of incoming edges.
 815  * 2. Walk the reachable commits, but only visit a commit if its in-degree
 816  * value is zero. When visiting a commit, decrement the in-degree value of
 817  * each parent.
 818  *
 819  * This algorithm works because at least one of our starting points will
 820  * have in-degree zero, and then decrementing the in-degree value is similar
 821  * to deleting the commit from the graph, always having at least one commit
 822  * with in-degree zero.
 823  */
 824 const struct got_error *
 825 got_commit_graph_toposort(struct got_commit_graph *graph,
 826     struct got_object_id *id, struct got_repository *repo,
 827     got_cancel_cb cancel_cb, void *cancel_arg)
 828 {
 829         const struct got_error *err = NULL;
 830         struct got_commit_graph_node *node = NULL, *pnode = NULL;
 831         struct got_commit_object *commit = NULL;
 832         struct got_object_id_queue commits;
 833         const struct got_object_id_queue *parent_ids;
 834         struct got_object_qid *qid = NULL, *pid;
 835         int i;
 836
 837         STAILQ_INIT(&commits);
 838
 839         if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL)
 840                 return got_commit_graph_bfsort(graph, id, repo,
 841                     cancel_cb, cancel_arg);
 842
 843         /* Clear left-over state from previous iteration attempts. */
 844         while ((node = TAILQ_FIRST(&graph->iter_list)))
 845                 TAILQ_REMOVE(&graph->iter_list, node, entry);
 846         err = got_object_idset_for_each(graph->open_branches,
 847             remove_branch_tip, graph->open_branches);
 848         if (err)
 849                 return err;
 850
 851         graph->flags |= GOT_COMMIT_GRAPH_TOPOSORT;
 852
 853         /*
 854          * Sorting the commit graph in topological order requires visiting
 855          * every reachable commit. This is very expensive but there are
 856          * ways to speed this up significantly in the future:
 857          * 1) Run this loop in got-read-pack if possible.
 858          * 2) Use Git's commit-graph file to compute the result incrementally.
 859          *    See the blog post linked above for details.
 860          */
 861         err = got_object_qid_alloc_partial(&qid);
 862         if (err)
 863                 return err;
 864         memcpy(&qid->id, id, sizeof(qid->id));
 865         STAILQ_INSERT_TAIL(&commits, qid, entry);
 866         while (!STAILQ_EMPTY(&commits)) {
 867                 if (cancel_cb) {
 868                         err = (*cancel_cb)(cancel_arg);
 869                         if (err)
 870                                 break;
 871                 }
 872
 873                 qid = STAILQ_FIRST(&commits);
 874                 STAILQ_REMOVE_HEAD(&commits, entry);
 875                 err = got_object_open_as_commit(&commit, repo, &qid->id);
 876                 if (err)
 877                         break;
 878
 879                 node = got_object_idset_get(graph->node_ids, &qid->id);
 880                 if (node == NULL) {
 881                         err = add_node(&node, graph, id, repo);
 882                         if (err)
 883                                 break;
 884                         TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
 885                 }
 886
 887                 got_object_qid_free(qid);
 888                 qid = NULL;
 889
 890                 if (node->timestamp != 0) /* already traversed once */
 891                         continue;
 892
 893                 if (node->nparents == -1) {
 894                         node->nparents = got_object_commit_get_nparents(commit);
 895                         if (node->nparents > nitems(node->parents)) {
 896                                 node->more_parents = calloc(node->nparents,
 897                                     sizeof(*node->more_parents));
 898                                 if (node->more_parents == NULL) {
 899                                         err = got_error_from_errno("calloc");
 900                                         break;
 901                                 }
 902                         }
 903
 904                 }
 905
 906                 node->timestamp = got_object_commit_get_committer_time(commit);
 907                 parent_ids = got_object_commit_get_parent_ids(commit);
 908                 i = 0;
 909                 STAILQ_FOREACH(pid, parent_ids, entry) {
 910                         if (cancel_cb) {
 911                                 err = (*cancel_cb)(cancel_arg);
 912                                 if (err)
 913                                         goto done;
 914                         }
 915
 916                         /*
 917                          * Increment the in-degree counter every time a given
 918                          * commit appears as the parent of another commit.
 919                          */
 920                         pnode = got_object_idset_get(graph->node_ids, &pid->id);
 921                         if (pnode == NULL) {
 922                                 err = add_node(&pnode, graph, &pid->id, repo);
 923                                 if (err)
 924                                         goto done;
 925                                 TAILQ_INSERT_TAIL(&graph->iter_list, pnode,
 926                                     entry);
 927                         }
 928                         pnode->indegree++;
 929
 930                         /*
 931                          * Cache parent pointers on the node to make future
 932                          * in-degree updates easier.
 933                          */
 934                         if (node->nparents <= nitems(node->parents)) {
 935                                 node->parents[i] = pnode;
 936                         } else {
 937                                 node->more_parents[i] = pnode;
 938                                 if (i < nitems(node->parents))
 939                                         node->parents[i] = pnode;
 940                         }
 941                         i++;
 942
 943                         /* Keep traversing through all parent commits. */
 944                         err = got_object_qid_alloc_partial(&qid);
 945                         if (err)
 946                                 goto done;
 947                         memcpy(&qid->id, &pid->id, sizeof(qid->id));
 948                         STAILQ_INSERT_TAIL(&commits, qid, entry);
 949                         qid = NULL;
 950                 }
 951
 952                 got_object_commit_close(commit);
 953                 commit = NULL;
 954         }
 955 done:
 956         if (commit)
 957                 got_object_commit_close(commit);
 958         got_object_qid_free(qid);
 959         got_object_id_queue_free(&commits);
 960         return err;
 961 }