portable: include utf8d.h in dist tarball
[got-portable.git] / lib / commit_graph.c
blob25522c81fb2b8206f953e4b128d8aa1c9c000bad
1 /*
2 * Copyright (c) 2018, 2019, 2020 Stefan Sperling <stsp@openbsd.org>
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.
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.
17 #include <sys/types.h>
18 #include <sys/stat.h>
19 #include <sys/queue.h>
21 #include <limits.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <zlib.h>
26 #include <ctype.h>
28 #include "got_compat.h"
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"
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"
42 #ifndef nitems
43 #define nitems(_a) (sizeof((_a)) / sizeof((_a)[0]))
44 #endif
46 struct got_commit_graph_node {
47 struct got_object_id id;
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;
55 /* Used only during iteration. */
56 time_t timestamp;
57 TAILQ_ENTRY(got_commit_graph_node) entry;
60 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
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;
68 struct got_commit_graph {
69 /* The set of all commits we have traversed. */
70 struct got_object_idset *node_ids;
72 int flags;
73 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
74 #define GOT_COMMIT_GRAPH_TOPOSORT 0x02
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.
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.
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.
91 struct got_object_idset *open_branches;
93 /* Array of branch tips for fetch_commits_from_open_branches(). */
94 struct got_commit_graph_branch_tip *tips;
95 int ntips;
97 /* Path of tree entry of interest to the API user. */
98 char *path;
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.
105 struct got_commit_graph_iter_list iter_list;
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)
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;
118 if (got_path_is_root_dir(path)) {
119 *changed = 1;
120 return NULL;
123 *changed = 0;
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;
138 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
139 if (err)
140 return err;
142 err = got_object_open_as_commit(&pcommit, repo, &pid->id);
143 if (err)
144 goto done;
146 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
147 if (err)
148 goto done;
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;
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)
165 struct got_commit_graph_node *n, *next;
167 node->timestamp = committer_time;
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;
176 n = next;
178 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
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)
186 const struct got_error *err = NULL;
187 struct got_commit_graph_node *node;
189 *new_node = NULL;
191 node = calloc(1, sizeof(*node));
192 if (node == NULL)
193 return got_error_from_errno("calloc");
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;
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.
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)
216 const struct got_error *err = NULL;
217 struct got_object_id_queue traversed_commits;
218 struct got_object_qid *qid;
220 STAILQ_INIT(&traversed_commits);
221 *ncommits_traversed = 0;
223 err = got_traverse_packed_commits(&traversed_commits,
224 commit_id, graph->path, repo);
225 if (err)
226 return err;
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;
235 (*ncommits_traversed)++;
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;
244 err = got_object_idset_add(graph->node_ids, &qid->id, NULL);
245 if (err)
246 break;
249 got_object_id_queue_free(&traversed_commits);
250 return err;
253 static const struct got_error *
254 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
256 const struct got_error *err;
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;
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)
268 const struct got_error *err;
269 struct got_object_qid *qid;
270 struct got_object_id *merged_id = NULL;
272 err = close_branch(graph, commit_id);
273 if (err)
274 return err;
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;
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'.
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;
297 return got_object_idset_add(graph->open_branches,
298 &qid->id, NULL);
302 * If we are graphing commits for a specific path, skip branches
303 * which do not contribute any content to this path.
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. */
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;
317 STAILQ_FOREACH(qid, &commit->parent_ids, entry) {
318 struct got_object_id *id = NULL;
319 struct got_commit_object *pcommit = NULL;
321 if (got_object_idset_contains(graph->open_branches,
322 &qid->id))
323 continue;
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;
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;
341 free(merged_id);
342 free(prev_id);
343 return err;
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);
352 prev_id = id;
355 * If a branch has created the merged content we can
356 * skip any other branches.
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;
367 free(prev_id);
368 prev_id = NULL;
369 free(merged_id);
370 merged_id = NULL;
373 * If the path's content is the same on all branches,
374 * follow the first parent only.
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);
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;
402 return NULL;
405 const struct got_error *
406 got_commit_graph_open(struct got_commit_graph **graph,
407 const char *path, int first_parent_traversal)
409 const struct got_error *err = NULL;
411 *graph = calloc(1, sizeof(**graph));
412 if (*graph == NULL)
413 return got_error_from_errno("calloc");
415 TAILQ_INIT(&(*graph)->iter_list);
417 (*graph)->path = strdup(path);
418 if ((*graph)->path == NULL) {
419 err = got_error_from_errno("strdup");
420 goto done;
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;
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;
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;
442 return err;
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;
452 static const struct got_error *
453 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
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;
460 err = got_object_open_as_commit(&commit, a->repo, commit_id);
461 if (err)
462 return err;
464 err = add_node(&new_node, a->graph, commit_id, a->repo);
465 if (err) {
466 got_object_commit_close(commit);
467 return err;
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++;
475 return NULL;
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)
482 const struct got_error *err;
483 struct add_branch_tip_arg arg;
484 int i, ntips;
486 ntips = got_object_idset_num_elements(graph->open_branches);
487 if (ntips == 0)
488 return NULL;
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;
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;
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;
515 if (cancel_cb) {
516 err = (*cancel_cb)(cancel_arg);
517 if (err)
518 break;
521 commit_id = arg.tips[i].commit_id;
522 commit = arg.tips[i].commit;
523 new_node = arg.tips[i].new_node;
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;
531 * History of the path stops here on the current
532 * branch. Keep going on other branches.
534 err = close_branch(graph, commit_id);
535 if (err)
536 break;
537 continue;
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;
544 err = advance_branch(graph, commit_id, commit, repo);
545 if (err)
546 break;
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);
553 return err;
556 void
557 got_commit_graph_close(struct got_commit_graph *graph)
559 struct got_commit_graph_node *node;
561 while ((node = TAILQ_FIRST(&graph->iter_list))) {
562 TAILQ_REMOVE(&graph->iter_list, node, entry);
563 free(node->more_parents);
564 free(node);
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);
576 static const struct got_error *
577 remove_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
579 struct got_object_idset *open_branches = arg;
581 return got_object_idset_remove(NULL, open_branches, commit_id);
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)
589 const struct got_error *err = NULL;
590 struct got_commit_graph_node *node;
592 graph->flags &= ~GOT_COMMIT_GRAPH_TOPOSORT;
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;
602 err = got_object_idset_add(graph->open_branches, id, NULL);
603 if (err)
604 return err;
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;
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);
625 return NULL;
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)
633 const struct got_error *err = NULL;
634 struct got_commit_graph_node *node, *pnode;
635 int i;
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);
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;
657 memcpy(id, &node->id, sizeof(*id));
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--;
670 free(node);
671 return NULL;
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)
679 const struct got_error *err = NULL;
680 struct got_object_id id;
682 err = got_commit_graph_iter_next(&id, graph, repo, cancel_cb,
683 cancel_arg);
684 if (err)
685 return err;
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;
694 return got_object_idset_add(commit_ids, &id, NULL);
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.
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.
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)
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;
717 *yca_id = NULL;
719 commit_ids = got_object_idset_alloc();
720 if (commit_ids == NULL)
721 return got_error_from_errno("got_object_idset_alloc");
723 err = got_commit_graph_open(&graph, "/", first_parent_traversal);
724 if (err)
725 goto done;
727 err = got_commit_graph_open(&graph2, "/", first_parent_traversal);
728 if (err)
729 goto done;
731 if (toposort) {
732 err = got_commit_graph_toposort(graph, commit_id, repo,
733 cancel_cb, cancel_arg);
734 if (err)
735 goto done;
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;
747 err = got_commit_graph_bfsort(graph2, commit_id2, repo,
748 cancel_cb, cancel_arg);
749 if (err)
750 goto done;
753 for (;;) {
754 if (cancel_cb) {
755 err = (*cancel_cb)(cancel_arg);
756 if (err)
757 break;
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;
769 if (*yca_id)
770 break;
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;
782 if (*yca_id)
783 break;
786 if (completed && completed2) {
787 err = got_error(GOT_ERR_ANCESTRY);
788 break;
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;
801 * Sort the graph for traversal in topological order.
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:
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.
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.
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)
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;
835 STAILQ_INIT(&commits);
837 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL)
838 return got_commit_graph_bfsort(graph, id, repo,
839 cancel_cb, cancel_arg);
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;
849 graph->flags |= GOT_COMMIT_GRAPH_TOPOSORT;
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.
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;
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;
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);
885 got_object_qid_free(qid);
886 qid = NULL;
888 if (node->timestamp != 0) /* already traversed once */
889 continue;
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;
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;
915 * Increment the in-degree counter every time a given
916 * commit appears as the parent of another commit.
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);
926 pnode->indegree++;
929 * Cache parent pointers on the node to make future
930 * in-degree updates easier.
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;
939 i++;
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;
950 got_object_commit_close(commit);
951 commit = NULL;
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;