2 * Copyright (c) 2018 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>
19 #include <sys/queue.h>
20 #include <sys/stdint.h>
29 #include "got_error.h"
30 #include "got_object.h"
31 #include "got_cancel.h"
32 #include "got_commit_graph.h"
35 #include "got_lib_delta.h"
36 #include "got_lib_inflate.h"
37 #include "got_lib_object.h"
38 #include "got_lib_object_idset.h"
40 struct got_commit_graph_node {
41 struct got_object_id id;
44 /* Used during graph iteration. */
45 TAILQ_ENTRY(got_commit_graph_node) entry;
48 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
50 struct got_commit_graph_branch_tip {
51 struct got_object_id *commit_id;
52 struct got_commit_object *commit;
53 struct got_commit_graph_node *new_node;
58 struct got_commit_graph {
59 /* The set of all commits we have traversed. */
60 struct got_object_idset *node_ids;
62 /* The commit at which traversal began (youngest commit in node_ids). */
63 struct got_commit_graph_node *head_node;
66 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
69 * A set of object IDs of known parent commits which we have not yet
70 * traversed. Each commit ID in this set represents a branch in commit
71 * history: Either the first-parent branch of the head node, or another
72 * branch corresponding to a traversed merge commit for which we have
73 * not traversed a branch point commit yet.
75 * Whenever we add a commit with a matching ID to the graph, we remove
76 * its corresponding element from this set, and add new elements for
77 * each of that commit's parent commits which were not traversed yet.
79 * When API users ask us to fetch more commits, we fetch commits from
80 * all currently open branches. This allows API users to process
81 * commits in linear order even though the history contains branches.
83 struct got_object_idset *open_branches;
85 /* Array of branch tips for fetch_commits_from_open_branches(). */
86 struct got_commit_graph_branch_tip *tips;
89 /* Path of tree entry of interest to the API user. */
92 /* The next commit to return when the API user asks for one. */
93 struct got_commit_graph_node *iter_node;
95 /* The graph iteration list contains all nodes in sorted order. */
96 struct got_commit_graph_iter_list iter_list;
99 static struct got_commit_graph *
100 alloc_graph(const char *path)
102 struct got_commit_graph *graph;
104 graph = calloc(1, sizeof(*graph));
108 graph->path = strdup(path);
109 if (graph->path == NULL) {
114 graph->node_ids = got_object_idset_alloc();
115 if (graph->node_ids == NULL) {
121 graph->open_branches = got_object_idset_alloc();
122 if (graph->open_branches == NULL) {
123 got_object_idset_free(graph->node_ids);
129 TAILQ_INIT(&graph->iter_list);
133 static const struct got_error *
134 detect_changed_path(int *changed, struct got_commit_object *commit,
135 struct got_object_id *commit_id, const char *path,
136 struct got_repository *repo)
138 const struct got_error *err = NULL;
139 struct got_commit_object *pcommit = NULL;
140 struct got_tree_object *tree = NULL, *ptree = NULL;
141 struct got_object_qid *pid;
143 if (got_path_is_root_dir(path)) {
150 pid = SIMPLEQ_FIRST(&commit->parent_ids);
152 struct got_object_id *obj_id;
153 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
155 if (err->code == GOT_ERR_NO_TREE_ENTRY)
158 *changed = 1; /* The path was created in this commit. */
163 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
167 err = got_object_open_as_commit(&pcommit, repo, pid->id);
171 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
175 err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
178 got_object_tree_close(tree);
180 got_object_tree_close(ptree);
182 got_object_commit_close(pcommit);
187 add_node_to_iter_list(struct got_commit_graph *graph,
188 struct got_commit_graph_node *node,
189 struct got_commit_graph_node *child_node)
191 struct got_commit_graph_node *n, *next;
193 if (TAILQ_EMPTY(&graph->iter_list)) {
194 TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
195 graph->iter_node = node;
199 n = graph->iter_node;
200 /* Ensure that an iteration in progress will see this new commit. */
202 next = TAILQ_NEXT(n, entry);
203 if (next && node->timestamp >= next->timestamp) {
204 TAILQ_INSERT_BEFORE(next, node, entry);
209 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
212 static const struct got_error *
213 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
215 const struct got_error *err;
217 err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
218 if (err && err->code != GOT_ERR_NO_OBJ)
223 static const struct got_error *
224 advance_branch(struct got_commit_graph *graph,
225 struct got_commit_graph_node *node,
226 struct got_object_id *commit_id, struct got_commit_object *commit,
227 struct got_repository *repo)
229 const struct got_error *err;
230 struct got_object_qid *qid;
232 err = close_branch(graph, commit_id);
236 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
237 qid = SIMPLEQ_FIRST(&commit->parent_ids);
239 got_object_idset_get(graph->open_branches, qid->id))
241 return got_object_idset_add(graph->open_branches,
246 * If we are graphing commits for a specific path, skip branches
247 * which do not contribute any content to this path.
249 if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
250 struct got_object_id *merged_id, *prev_id = NULL;
251 int branches_differ = 0;
253 err = got_object_id_by_path(&merged_id, repo, commit_id,
258 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
259 struct got_object_id *id;
261 if (got_object_idset_get(graph->open_branches, qid->id))
264 err = got_object_id_by_path(&id, repo, qid->id,
267 if (err->code == GOT_ERR_NO_TREE_ENTRY) {
277 if (!branches_differ &&
278 got_object_id_cmp(id, prev_id) != 0)
285 * If a branch has created the merged content we can
286 * skip any other branches.
288 if (got_object_id_cmp(merged_id, id) == 0) {
289 err = got_object_idset_add(graph->open_branches,
303 * If the path's content is the same on all branches,
304 * follow the first parent only.
306 if (!branches_differ) {
307 qid = SIMPLEQ_FIRST(&commit->parent_ids);
310 if (got_object_idset_get(graph->open_branches, qid->id))
312 if (got_object_idset_get(graph->node_ids, qid->id))
313 return NULL; /* parent already traversed */
314 return got_object_idset_add(graph->open_branches,
319 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
320 if (got_object_idset_get(graph->open_branches, qid->id))
322 if (got_object_idset_get(graph->node_ids, qid->id))
323 continue; /* parent already traversed */
324 err = got_object_idset_add(graph->open_branches, qid->id, node);
332 static const struct got_error *
333 add_node(struct got_commit_graph_node **new_node, int *changed,
334 int *branch_done, struct got_commit_graph *graph,
335 struct got_object_id *commit_id, struct got_commit_object *commit,
336 struct got_commit_graph_node *child_node, struct got_repository *repo)
338 const struct got_error *err = NULL;
339 struct got_commit_graph_node *node;
345 node = calloc(1, sizeof(*node));
347 return got_error_from_errno("calloc");
349 memcpy(&node->id, commit_id, sizeof(node->id));
350 node->timestamp = commit->committer_time;
352 err = got_object_idset_add(graph->node_ids, &node->id, node);
358 err = detect_changed_path(changed, commit, commit_id, graph->path,
361 if (err->code == GOT_ERR_NO_OBJ) {
363 * History of the path stops here on the current
364 * branch. Keep going on other branches.
369 got_object_idset_remove(NULL, graph->node_ids,
377 add_node_to_iter_list(graph, node, child_node);
382 const struct got_error *
383 got_commit_graph_open(struct got_commit_graph **graph,
384 struct got_object_id *commit_id, const char *path,
385 int first_parent_traversal, struct got_repository *repo)
387 const struct got_error *err = NULL;
388 struct got_commit_object *commit;
389 int changed, branch_done;
393 err = got_object_open_as_commit(&commit, repo, commit_id);
397 /* The path must exist in our initial commit. */
398 if (!got_path_is_root_dir(path)) {
399 struct got_object_id *obj_id;
400 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
406 *graph = alloc_graph(path);
407 if (*graph == NULL) {
408 err = got_error_from_errno("alloc_graph");
409 got_object_commit_close(commit);
413 if (first_parent_traversal)
414 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
416 err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
417 commit_id, commit, NULL, repo);
419 err = advance_branch(*graph, (*graph)->head_node, commit_id,
422 got_object_commit_close(commit);
424 got_commit_graph_close(*graph);
432 struct add_branch_tip_arg {
433 struct got_commit_graph_branch_tip *tips;
435 struct got_repository *repo;
436 struct got_commit_graph *graph;
439 static const struct got_error *
440 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
442 const struct got_error *err;
443 struct got_commit_graph_node *child_node = data;
444 struct add_branch_tip_arg *a = arg;
445 struct got_commit_graph_node *new_node;
446 struct got_commit_object *commit;
447 int changed, branch_done;
449 err = got_object_open_as_commit(&commit, a->repo, commit_id);
453 err = add_node(&new_node, &changed, &branch_done, a->graph,
454 commit_id, commit, child_node, a->repo);
458 a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
459 a->tips[a->ntips].commit = commit;
460 a->tips[a->ntips].new_node = new_node;
461 a->tips[a->ntips].changed = changed;
462 a->tips[a->ntips].branch_done = branch_done;
468 static const struct got_error *
469 fetch_commits_from_open_branches(int *nfetched,
470 struct got_object_id **changed_id, struct got_commit_graph *graph,
471 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
473 const struct got_error *err;
474 struct add_branch_tip_arg arg;
481 ntips = got_object_idset_num_elements(graph->open_branches);
485 /* (Re-)allocate branch tips array if necessary. */
486 if (graph->ntips < ntips) {
487 struct got_commit_graph_branch_tip *tips;
488 tips = recallocarray(graph->tips, graph->ntips, ntips,
491 return got_error_from_errno("recallocarray");
493 graph->ntips = ntips;
495 arg.tips = graph->tips;
496 arg.ntips = 0; /* add_branch_tip() will increment */
499 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
504 for (i = 0; i < arg.ntips; i++) {
505 struct got_object_id *commit_id;
506 struct got_commit_object *commit;
507 struct got_commit_graph_node *new_node;
508 int branch_done, changed;
511 err = (*cancel_cb)(cancel_arg);
516 commit_id = arg.tips[i].commit_id;
517 commit = arg.tips[i].commit;
518 new_node = arg.tips[i].new_node;
519 branch_done = arg.tips[i].branch_done;
520 changed = arg.tips[i].changed;
523 err = close_branch(graph, commit_id);
525 err = advance_branch(graph, new_node, commit_id,
529 if (changed && changed_id && *changed_id == NULL)
530 *changed_id = commit_id;
533 for (i = 0; i < arg.ntips; i++)
534 got_object_commit_close(arg.tips[i].commit);
535 (*nfetched) = arg.ntips;
539 const struct got_error *
540 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
541 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
543 const struct got_error *err;
544 int nfetched = 0, ncommits;
545 struct got_object_id *changed_id = NULL;
547 while (nfetched < limit) {
549 err = (*cancel_cb)(cancel_arg);
553 err = fetch_commits_from_open_branches(&ncommits,
554 &changed_id, graph, repo, cancel_cb, cancel_arg);
560 nfetched += ncommits;
566 static const struct got_error *
567 free_node_iter(struct got_object_id *id, void *data, void *arg)
569 struct got_commit_graph_node *node = data;
575 got_commit_graph_close(struct got_commit_graph *graph)
577 got_object_idset_free(graph->open_branches);
578 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
579 got_object_idset_free(graph->node_ids);
585 const struct got_error *
586 got_commit_graph_iter_start(struct got_commit_graph *graph,
587 struct got_object_id *id, struct got_repository *repo,
588 got_cancel_cb cancel_cb, void *cancel_arg)
590 const struct got_error *err = NULL;
591 struct got_commit_graph_node *start_node;
592 struct got_commit_object *commit;
595 start_node = got_object_idset_get(graph->node_ids, id);
596 while (start_node == NULL) {
598 err = fetch_commits_from_open_branches(&ncommits, NULL, graph,
599 repo, cancel_cb, cancel_arg);
603 return got_error_no_obj(id);
604 start_node = got_object_idset_get(graph->node_ids, id);
607 err = got_object_open_as_commit(&commit, repo, &start_node->id);
611 err = detect_changed_path(&changed, commit, &start_node->id,
614 got_object_commit_close(commit);
619 /* Locate first commit which changed graph->path. */
620 struct got_object_id *changed_id = NULL;
621 while (changed_id == NULL) {
623 err = fetch_commits_from_open_branches(&ncommits,
624 &changed_id, graph, repo, cancel_cb, cancel_arg);
626 got_object_commit_close(commit);
630 start_node = got_object_idset_get(graph->node_ids, changed_id);
632 got_object_commit_close(commit);
634 graph->iter_node = start_node;
638 const struct got_error *
639 got_commit_graph_iter_next(struct got_object_id **id,
640 struct got_commit_graph *graph)
644 if (graph->iter_node == NULL) {
645 /* We are done iterating, or iteration was not started. */
646 return got_error(GOT_ERR_ITER_COMPLETED);
649 if (graph->iter_node ==
650 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
651 got_object_idset_num_elements(graph->open_branches) == 0) {
652 /* We are done iterating. */
653 *id = &graph->iter_node->id;
654 graph->iter_node = NULL;
658 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
659 return got_error(GOT_ERR_ITER_NEED_MORE);
661 *id = &graph->iter_node->id;
662 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
666 const struct got_error *
667 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
668 struct got_object_id *commit_id, struct got_object_id *commit_id2,
669 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
671 const struct got_error *err = NULL;
672 struct got_commit_graph *graph = NULL, *graph2 = NULL;
673 int completed = 0, completed2 = 0;
674 struct got_object_idset *commit_ids;
678 commit_ids = got_object_idset_alloc();
679 if (commit_ids == NULL)
680 return got_error_from_errno("got_object_idset_alloc");
682 err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
686 err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
690 err = got_commit_graph_iter_start(graph, commit_id, repo,
691 cancel_cb, cancel_arg);
695 err = got_commit_graph_iter_start(graph2, commit_id2, repo,
696 cancel_cb, cancel_arg);
701 struct got_object_id *id, *id2;
704 err = (*cancel_cb)(cancel_arg);
710 err = got_commit_graph_iter_next(&id, graph);
712 if (err->code == GOT_ERR_ITER_COMPLETED)
714 else if (err->code != GOT_ERR_ITER_NEED_MORE)
716 err = got_commit_graph_fetch_commits(graph, 1,
717 repo, cancel_cb, cancel_arg);
724 err = got_commit_graph_iter_next(&id2, graph2);
726 if (err->code == GOT_ERR_ITER_COMPLETED)
728 else if (err->code != GOT_ERR_ITER_NEED_MORE)
730 err = got_commit_graph_fetch_commits(graph2, 1,
731 repo, cancel_cb, cancel_arg);
738 if (got_object_idset_get(commit_ids, id)) {
739 *yca_id = got_object_id_dup(id);
742 err = got_error_from_errno("got_object_id_dup");
746 err = got_object_idset_add(commit_ids, id, id);
751 if (got_object_idset_get(commit_ids, id2)) {
752 *yca_id = got_object_id_dup(id2);
755 err = got_error_from_errno("got_object_id_dup");
759 err = got_object_idset_add(commit_ids, id2, id2);
764 if (completed && completed2) {
765 err = got_error(GOT_ERR_ANCESTRY);
771 got_object_idset_free(commit_ids);
773 got_commit_graph_close(graph);
775 got_commit_graph_close(graph2);