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>
30 #include "got_error.h"
31 #include "got_object.h"
32 #include "got_cancel.h"
33 #include "got_commit_graph.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"
41 struct got_commit_graph_node {
42 struct got_object_id id;
45 /* Used during graph iteration. */
46 TAILQ_ENTRY(got_commit_graph_node) entry;
49 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
51 struct got_commit_graph_branch_tip {
52 struct got_object_id *commit_id;
53 struct got_commit_object *commit;
54 struct got_commit_graph_node *new_node;
59 struct got_commit_graph {
60 /* The set of all commits we have traversed. */
61 struct got_object_idset *node_ids;
63 /* The commit at which traversal began (youngest commit in node_ids). */
64 struct got_commit_graph_node *head_node;
67 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
70 * A set of object IDs of known parent commits which we have not yet
71 * traversed. Each commit ID in this set represents a branch in commit
72 * history: Either the first-parent branch of the head node, or another
73 * branch corresponding to a traversed merge commit for which we have
74 * not traversed a branch point commit yet.
76 * Whenever we add a commit with a matching ID to the graph, we remove
77 * its corresponding element from this set, and add new elements for
78 * each of that commit's parent commits which were not traversed yet.
80 * When API users ask us to fetch more commits, we fetch commits from
81 * all currently open branches. This allows API users to process
82 * commits in linear order even though the history contains branches.
84 struct got_object_idset *open_branches;
86 /* Array of branch tips for fetch_commits_from_open_branches(). */
87 struct got_commit_graph_branch_tip *tips;
90 /* Path of tree entry of interest to the API user. */
93 /* The next commit to return when the API user asks for one. */
94 struct got_commit_graph_node *iter_node;
96 /* The graph iteration list contains all nodes in sorted order. */
97 struct got_commit_graph_iter_list iter_list;
100 static struct got_commit_graph *
101 alloc_graph(const char *path)
103 struct got_commit_graph *graph;
105 graph = calloc(1, sizeof(*graph));
109 graph->path = strdup(path);
110 if (graph->path == NULL) {
115 graph->node_ids = got_object_idset_alloc();
116 if (graph->node_ids == NULL) {
122 graph->open_branches = got_object_idset_alloc();
123 if (graph->open_branches == NULL) {
124 got_object_idset_free(graph->node_ids);
130 TAILQ_INIT(&graph->iter_list);
134 static const struct got_error *
135 detect_changed_path(int *changed, struct got_commit_object *commit,
136 struct got_object_id *commit_id, const char *path,
137 struct got_repository *repo)
139 const struct got_error *err = NULL;
140 struct got_commit_object *pcommit = NULL;
141 struct got_tree_object *tree = NULL, *ptree = NULL;
142 struct got_object_qid *pid;
144 if (got_path_is_root_dir(path)) {
151 pid = SIMPLEQ_FIRST(&commit->parent_ids);
153 struct got_object_id *obj_id;
154 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
156 if (err->code == GOT_ERR_NO_TREE_ENTRY)
159 *changed = 1; /* The path was created in this commit. */
164 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
168 err = got_object_open_as_commit(&pcommit, repo, pid->id);
172 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
176 err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
179 got_object_tree_close(tree);
181 got_object_tree_close(ptree);
183 got_object_commit_close(pcommit);
188 add_node_to_iter_list(struct got_commit_graph *graph,
189 struct got_commit_graph_node *node,
190 struct got_commit_graph_node *child_node)
192 struct got_commit_graph_node *n, *next;
194 if (TAILQ_EMPTY(&graph->iter_list)) {
195 TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
196 graph->iter_node = node;
200 n = graph->iter_node;
201 /* Ensure that an iteration in progress will see this new commit. */
203 next = TAILQ_NEXT(n, entry);
204 if (next && node->timestamp >= next->timestamp) {
205 TAILQ_INSERT_BEFORE(next, node, entry);
210 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
213 static const struct got_error *
214 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
216 const struct got_error *err;
218 err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
219 if (err && err->code != GOT_ERR_NO_OBJ)
224 static const struct got_error *
225 advance_branch(struct got_commit_graph *graph,
226 struct got_commit_graph_node *node,
227 struct got_object_id *commit_id, struct got_commit_object *commit,
228 struct got_repository *repo)
230 const struct got_error *err;
231 struct got_object_qid *qid;
233 err = close_branch(graph, commit_id);
237 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
238 qid = SIMPLEQ_FIRST(&commit->parent_ids);
240 got_object_idset_get(graph->open_branches, qid->id))
242 return got_object_idset_add(graph->open_branches,
247 * If we are graphing commits for a specific path, skip branches
248 * which do not contribute any content to this path.
250 if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
251 struct got_object_id *merged_id, *prev_id = NULL;
252 int branches_differ = 0;
254 err = got_object_id_by_path(&merged_id, repo, commit_id,
259 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
260 struct got_object_id *id;
262 if (got_object_idset_get(graph->open_branches, qid->id))
265 err = got_object_id_by_path(&id, repo, qid->id,
268 if (err->code == GOT_ERR_NO_TREE_ENTRY) {
278 if (!branches_differ &&
279 got_object_id_cmp(id, prev_id) != 0)
286 * If a branch has created the merged content we can
287 * skip any other branches.
289 if (got_object_id_cmp(merged_id, id) == 0) {
290 err = got_object_idset_add(graph->open_branches,
304 * If the path's content is the same on all branches,
305 * follow the first parent only.
307 if (!branches_differ) {
308 qid = SIMPLEQ_FIRST(&commit->parent_ids);
311 if (got_object_idset_get(graph->open_branches, qid->id))
313 if (got_object_idset_get(graph->node_ids, qid->id))
314 return NULL; /* parent already traversed */
315 return got_object_idset_add(graph->open_branches,
320 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
321 if (got_object_idset_get(graph->open_branches, qid->id))
323 if (got_object_idset_get(graph->node_ids, qid->id))
324 continue; /* parent already traversed */
325 err = got_object_idset_add(graph->open_branches, qid->id, node);
333 static const struct got_error *
334 add_node(struct got_commit_graph_node **new_node, int *changed,
335 int *branch_done, struct got_commit_graph *graph,
336 struct got_object_id *commit_id, struct got_commit_object *commit,
337 struct got_commit_graph_node *child_node, struct got_repository *repo)
339 const struct got_error *err = NULL;
340 struct got_commit_graph_node *node;
346 node = calloc(1, sizeof(*node));
348 return got_error_from_errno("calloc");
350 memcpy(&node->id, commit_id, sizeof(node->id));
351 node->timestamp = commit->committer_time;
353 err = got_object_idset_add(graph->node_ids, &node->id, node);
359 err = detect_changed_path(changed, commit, commit_id, graph->path,
362 if (err->code == GOT_ERR_NO_OBJ) {
364 * History of the path stops here on the current
365 * branch. Keep going on other branches.
370 got_object_idset_remove(NULL, graph->node_ids,
378 add_node_to_iter_list(graph, node, child_node);
383 const struct got_error *
384 got_commit_graph_open(struct got_commit_graph **graph,
385 struct got_object_id *commit_id, const char *path,
386 int first_parent_traversal, struct got_repository *repo)
388 const struct got_error *err = NULL;
389 struct got_commit_object *commit;
390 int changed, branch_done;
394 err = got_object_open_as_commit(&commit, repo, commit_id);
398 /* The path must exist in our initial commit. */
399 if (!got_path_is_root_dir(path)) {
400 struct got_object_id *obj_id;
401 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
407 *graph = alloc_graph(path);
408 if (*graph == NULL) {
409 err = got_error_from_errno("alloc_graph");
410 got_object_commit_close(commit);
414 if (first_parent_traversal)
415 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
417 err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
418 commit_id, commit, NULL, repo);
420 err = advance_branch(*graph, (*graph)->head_node, commit_id,
423 got_object_commit_close(commit);
425 got_commit_graph_close(*graph);
433 struct add_branch_tip_arg {
434 struct got_commit_graph_branch_tip *tips;
436 struct got_repository *repo;
437 struct got_commit_graph *graph;
440 static const struct got_error *
441 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
443 const struct got_error *err;
444 struct got_commit_graph_node *child_node = data;
445 struct add_branch_tip_arg *a = arg;
446 struct got_commit_graph_node *new_node;
447 struct got_commit_object *commit;
448 int changed, branch_done;
450 err = got_object_open_as_commit(&commit, a->repo, commit_id);
454 err = add_node(&new_node, &changed, &branch_done, a->graph,
455 commit_id, commit, child_node, a->repo);
459 a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
460 a->tips[a->ntips].commit = commit;
461 a->tips[a->ntips].new_node = new_node;
462 a->tips[a->ntips].changed = changed;
463 a->tips[a->ntips].branch_done = branch_done;
469 static const struct got_error *
470 fetch_commits_from_open_branches(int *nfetched,
471 struct got_object_id **changed_id, struct got_commit_graph *graph,
472 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
474 const struct got_error *err;
475 struct add_branch_tip_arg arg;
482 ntips = got_object_idset_num_elements(graph->open_branches);
486 /* (Re-)allocate branch tips array if necessary. */
487 if (graph->ntips < ntips) {
488 struct got_commit_graph_branch_tip *tips;
489 tips = recallocarray(graph->tips, graph->ntips, ntips,
492 return got_error_from_errno("recallocarray");
494 graph->ntips = ntips;
496 arg.tips = graph->tips;
497 arg.ntips = 0; /* add_branch_tip() will increment */
500 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
505 for (i = 0; i < arg.ntips; i++) {
506 struct got_object_id *commit_id;
507 struct got_commit_object *commit;
508 struct got_commit_graph_node *new_node;
509 int branch_done, changed;
512 err = (*cancel_cb)(cancel_arg);
517 commit_id = arg.tips[i].commit_id;
518 commit = arg.tips[i].commit;
519 new_node = arg.tips[i].new_node;
520 branch_done = arg.tips[i].branch_done;
521 changed = arg.tips[i].changed;
524 err = close_branch(graph, commit_id);
526 err = advance_branch(graph, new_node, commit_id,
530 if (changed && changed_id && *changed_id == NULL)
531 *changed_id = commit_id;
534 for (i = 0; i < arg.ntips; i++)
535 got_object_commit_close(arg.tips[i].commit);
536 (*nfetched) = arg.ntips;
540 const struct got_error *
541 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
542 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
544 const struct got_error *err;
545 int nfetched = 0, ncommits;
546 struct got_object_id *changed_id = NULL;
548 while (nfetched < limit) {
550 err = (*cancel_cb)(cancel_arg);
554 err = fetch_commits_from_open_branches(&ncommits,
555 &changed_id, graph, repo, cancel_cb, cancel_arg);
561 nfetched += ncommits;
567 static const struct got_error *
568 free_node_iter(struct got_object_id *id, void *data, void *arg)
570 struct got_commit_graph_node *node = data;
576 got_commit_graph_close(struct got_commit_graph *graph)
578 got_object_idset_free(graph->open_branches);
579 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
580 got_object_idset_free(graph->node_ids);
586 const struct got_error *
587 got_commit_graph_iter_start(struct got_commit_graph *graph,
588 struct got_object_id *id, struct got_repository *repo,
589 got_cancel_cb cancel_cb, void *cancel_arg)
591 const struct got_error *err = NULL;
592 struct got_commit_graph_node *start_node;
593 struct got_commit_object *commit;
596 start_node = got_object_idset_get(graph->node_ids, id);
597 while (start_node == NULL) {
599 err = fetch_commits_from_open_branches(&ncommits, NULL, graph,
600 repo, cancel_cb, cancel_arg);
604 return got_error_no_obj(id);
605 start_node = got_object_idset_get(graph->node_ids, id);
608 err = got_object_open_as_commit(&commit, repo, &start_node->id);
612 err = detect_changed_path(&changed, commit, &start_node->id,
615 got_object_commit_close(commit);
620 /* Locate first commit which changed graph->path. */
621 struct got_object_id *changed_id = NULL;
622 while (changed_id == NULL) {
624 err = fetch_commits_from_open_branches(&ncommits,
625 &changed_id, graph, repo, cancel_cb, cancel_arg);
627 got_object_commit_close(commit);
631 start_node = got_object_idset_get(graph->node_ids, changed_id);
633 got_object_commit_close(commit);
635 graph->iter_node = start_node;
639 const struct got_error *
640 got_commit_graph_iter_next(struct got_object_id **id,
641 struct got_commit_graph *graph)
645 if (graph->iter_node == NULL) {
646 /* We are done iterating, or iteration was not started. */
647 return got_error(GOT_ERR_ITER_COMPLETED);
650 if (graph->iter_node ==
651 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
652 got_object_idset_num_elements(graph->open_branches) == 0) {
653 /* We are done iterating. */
654 *id = &graph->iter_node->id;
655 graph->iter_node = NULL;
659 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
660 return got_error(GOT_ERR_ITER_NEED_MORE);
662 *id = &graph->iter_node->id;
663 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
667 const struct got_error *
668 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
669 struct got_object_id *commit_id, struct got_object_id *commit_id2,
670 struct got_repository *repo, got_cancel_cb cancel_cb, void *cancel_arg)
672 const struct got_error *err = NULL;
673 struct got_commit_graph *graph = NULL, *graph2 = NULL;
674 int completed = 0, completed2 = 0;
675 struct got_object_idset *commit_ids;
679 commit_ids = got_object_idset_alloc();
680 if (commit_ids == NULL)
681 return got_error_from_errno("got_object_idset_alloc");
683 err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
687 err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
691 err = got_commit_graph_iter_start(graph, commit_id, repo,
692 cancel_cb, cancel_arg);
696 err = got_commit_graph_iter_start(graph2, commit_id2, repo,
697 cancel_cb, cancel_arg);
702 struct got_object_id *id, *id2;
705 err = (*cancel_cb)(cancel_arg);
711 err = got_commit_graph_iter_next(&id, graph);
713 if (err->code == GOT_ERR_ITER_COMPLETED)
715 else if (err->code != GOT_ERR_ITER_NEED_MORE)
717 err = got_commit_graph_fetch_commits(graph, 1,
718 repo, cancel_cb, cancel_arg);
725 err = got_commit_graph_iter_next(&id2, graph2);
727 if (err->code == GOT_ERR_ITER_COMPLETED)
729 else if (err->code != GOT_ERR_ITER_NEED_MORE)
731 err = got_commit_graph_fetch_commits(graph2, 1,
732 repo, cancel_cb, cancel_arg);
739 if (got_object_idset_get(commit_ids, id)) {
740 *yca_id = got_object_id_dup(id);
743 err = got_error_from_errno("got_object_id_dup");
747 err = got_object_idset_add(commit_ids, id, id);
752 if (got_object_idset_get(commit_ids, id2)) {
753 *yca_id = got_object_id_dup(id2);
756 err = got_error_from_errno("got_object_id_dup");
760 err = got_object_idset_add(commit_ids, id2, id2);
765 if (completed && completed2) {
766 err = got_error(GOT_ERR_ANCESTRY);
772 got_object_idset_free(commit_ids);
774 got_commit_graph_close(graph);
776 got_commit_graph_close(graph2);