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