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_commit_graph.h"
34 #include "got_lib_delta.h"
35 #include "got_lib_inflate.h"
36 #include "got_lib_object.h"
37 #include "got_lib_object_idset.h"
39 struct got_commit_graph_node {
40 struct got_object_id id;
43 /* Used during graph iteration. */
44 TAILQ_ENTRY(got_commit_graph_node) entry;
47 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
49 struct got_commit_graph_branch_tip {
50 struct got_object_id *commit_id;
51 struct got_commit_object *commit;
52 struct got_commit_graph_node *new_node;
57 struct got_commit_graph {
58 /* The set of all commits we have traversed. */
59 struct got_object_idset *node_ids;
61 /* The commit at which traversal began (youngest commit in node_ids). */
62 struct got_commit_graph_node *head_node;
65 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
68 * A set of object IDs of known parent commits which we have not yet
69 * traversed. Each commit ID in this set represents a branch in commit
70 * history: Either the first-parent branch of the head node, or another
71 * branch corresponding to a traversed merge commit for which we have
72 * not traversed a branch point commit yet.
74 * Whenever we add a commit with a matching ID to the graph, we remove
75 * its corresponding element from this set, and add new elements for
76 * each of that commit's parent commits which were not traversed yet.
78 * When API users ask us to fetch more commits, we fetch commits from
79 * all currently open branches. This allows API users to process
80 * commits in linear order even though the history contains branches.
82 struct got_object_idset *open_branches;
84 /* Array of branch tips for fetch_commits_from_open_branches(). */
85 struct got_commit_graph_branch_tip *tips;
88 /* Path of tree entry of interest to the API user. */
91 /* The next commit to return when the API user asks for one. */
92 struct got_commit_graph_node *iter_node;
94 /* The graph iteration list contains all nodes in sorted order. */
95 struct got_commit_graph_iter_list iter_list;
98 static struct got_commit_graph *
99 alloc_graph(const char *path)
101 struct got_commit_graph *graph;
103 graph = calloc(1, sizeof(*graph));
107 graph->path = strdup(path);
108 if (graph->path == NULL) {
113 graph->node_ids = got_object_idset_alloc();
114 if (graph->node_ids == NULL) {
120 graph->open_branches = got_object_idset_alloc();
121 if (graph->open_branches == NULL) {
122 got_object_idset_free(graph->node_ids);
128 TAILQ_INIT(&graph->iter_list);
132 static const struct got_error *
133 detect_changed_path(int *changed, struct got_commit_object *commit,
134 struct got_object_id *commit_id, const char *path,
135 struct got_repository *repo)
137 const struct got_error *err = NULL;
138 struct got_commit_object *pcommit = NULL;
139 struct got_tree_object *tree = NULL, *ptree = NULL;
140 struct got_object_qid *pid;
142 if (got_path_is_root_dir(path)) {
149 pid = SIMPLEQ_FIRST(&commit->parent_ids);
151 struct got_object_id *obj_id;
152 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
154 if (err->code == GOT_ERR_NO_TREE_ENTRY)
157 *changed = 1; /* The path was created in this commit. */
162 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
166 err = got_object_open_as_commit(&pcommit, repo, pid->id);
170 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
174 err = got_object_tree_path_changed(changed, tree, ptree, path, repo);
177 got_object_tree_close(tree);
179 got_object_tree_close(ptree);
181 got_object_commit_close(pcommit);
186 add_node_to_iter_list(struct got_commit_graph *graph,
187 struct got_commit_graph_node *node,
188 struct got_commit_graph_node *child_node)
190 struct got_commit_graph_node *n, *next;
192 if (TAILQ_EMPTY(&graph->iter_list)) {
193 TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
194 graph->iter_node = node;
198 n = graph->iter_node;
199 /* Ensure that an iteration in progress will see this new commit. */
201 next = TAILQ_NEXT(n, entry);
202 if (next && node->timestamp >= next->timestamp) {
203 TAILQ_INSERT_BEFORE(next, node, entry);
208 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
211 static const struct got_error *
212 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
214 const struct got_error *err;
216 err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
217 if (err && err->code != GOT_ERR_NO_OBJ)
222 static const struct got_error *
223 advance_branch(struct got_commit_graph *graph,
224 struct got_commit_graph_node *node,
225 struct got_object_id *commit_id, struct got_commit_object *commit,
226 struct got_repository *repo)
228 const struct got_error *err;
229 struct got_object_qid *qid;
231 err = close_branch(graph, commit_id);
235 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
236 qid = SIMPLEQ_FIRST(&commit->parent_ids);
238 got_object_idset_get(graph->open_branches, qid->id))
240 return got_object_idset_add(graph->open_branches,
245 * If we are graphing commits for a specific path, skip branches
246 * which do not contribute any content to this path.
248 if (commit->nparents > 1 && !got_path_is_root_dir(graph->path)) {
249 struct got_object_id *merged_id, *prev_id = NULL;
250 int branches_differ = 0;
252 err = got_object_id_by_path(&merged_id, repo, commit_id,
257 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
258 struct got_object_id *id;
260 if (got_object_idset_get(graph->open_branches, qid->id))
263 err = got_object_id_by_path(&id, repo, qid->id,
266 if (err->code == GOT_ERR_NO_TREE_ENTRY) {
276 if (!branches_differ &&
277 got_object_id_cmp(id, prev_id) != 0)
284 * If a branch has created the merged content we can
285 * skip any other branches.
287 if (got_object_id_cmp(merged_id, id) == 0) {
288 err = got_object_idset_add(graph->open_branches,
302 * If the path's content is the same on all branches,
303 * follow the first parent only.
305 if (!branches_differ) {
306 qid = SIMPLEQ_FIRST(&commit->parent_ids);
309 if (got_object_idset_get(graph->open_branches, qid->id))
311 if (got_object_idset_get(graph->node_ids, qid->id))
312 return NULL; /* parent already traversed */
313 return got_object_idset_add(graph->open_branches,
318 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
319 if (got_object_idset_get(graph->open_branches, qid->id))
321 if (got_object_idset_get(graph->node_ids, qid->id))
322 continue; /* parent already traversed */
323 err = got_object_idset_add(graph->open_branches, qid->id, node);
331 static const struct got_error *
332 add_node(struct got_commit_graph_node **new_node, int *changed,
333 int *branch_done, struct got_commit_graph *graph,
334 struct got_object_id *commit_id, struct got_commit_object *commit,
335 struct got_commit_graph_node *child_node, struct got_repository *repo)
337 const struct got_error *err = NULL;
338 struct got_commit_graph_node *node;
344 node = calloc(1, sizeof(*node));
346 return got_error_prefix_errno("calloc");
348 memcpy(&node->id, commit_id, sizeof(node->id));
349 node->timestamp = commit->committer_time;
351 err = got_object_idset_add(graph->node_ids, &node->id, node);
357 err = detect_changed_path(changed, commit, commit_id, graph->path,
360 if (err->code == GOT_ERR_NO_OBJ) {
362 * History of the path stops here on the current
363 * branch. Keep going on other branches.
368 got_object_idset_remove(NULL, graph->node_ids,
376 add_node_to_iter_list(graph, node, child_node);
381 const struct got_error *
382 got_commit_graph_open(struct got_commit_graph **graph,
383 struct got_object_id *commit_id, const char *path,
384 int first_parent_traversal, struct got_repository *repo)
386 const struct got_error *err = NULL;
387 struct got_commit_object *commit;
388 int changed, branch_done;
392 err = got_object_open_as_commit(&commit, repo, commit_id);
396 /* The path must exist in our initial commit. */
397 if (!got_path_is_root_dir(path)) {
398 struct got_object_id *obj_id;
399 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
405 *graph = alloc_graph(path);
406 if (*graph == NULL) {
407 got_object_commit_close(commit);
408 return got_error_prefix_errno("alloc_graph");
411 if (first_parent_traversal)
412 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
414 err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
415 commit_id, commit, NULL, repo);
417 err = advance_branch(*graph, (*graph)->head_node, commit_id,
420 got_object_commit_close(commit);
422 got_commit_graph_close(*graph);
430 struct add_branch_tip_arg {
431 struct got_commit_graph_branch_tip *tips;
433 struct got_repository *repo;
434 struct got_commit_graph *graph;
437 static const struct got_error *
438 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
440 const struct got_error *err;
441 struct got_commit_graph_node *child_node = data;
442 struct add_branch_tip_arg *a = arg;
443 struct got_commit_graph_node *new_node;
444 struct got_commit_object *commit;
445 int changed, branch_done;
447 err = got_object_open_as_commit(&commit, a->repo, commit_id);
451 err = add_node(&new_node, &changed, &branch_done, a->graph,
452 commit_id, commit, child_node, a->repo);
456 a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
457 a->tips[a->ntips].commit = commit;
458 a->tips[a->ntips].new_node = new_node;
459 a->tips[a->ntips].changed = changed;
460 a->tips[a->ntips].branch_done = branch_done;
466 static const struct got_error *
467 fetch_commits_from_open_branches(int *nfetched,
468 struct got_object_id **changed_id, struct got_commit_graph *graph,
469 struct got_repository *repo)
471 const struct got_error *err;
472 struct add_branch_tip_arg arg;
478 ntips = got_object_idset_num_elements(graph->open_branches);
482 /* (Re-)allocate branch tips array if necessary. */
483 if (graph->ntips < ntips) {
484 struct got_commit_graph_branch_tip *tips;
485 tips = recallocarray(graph->tips, graph->ntips, ntips,
488 return got_error_prefix_errno("recallocarray");
490 graph->ntips = ntips;
492 arg.tips = graph->tips;
493 arg.ntips = 0; /* add_branch_tip() will increment */
496 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
501 for (i = 0; i < arg.ntips; i++) {
502 struct got_object_id *commit_id;
503 struct got_commit_object *commit;
504 struct got_commit_graph_node *new_node;
505 int branch_done, changed;
507 commit_id = arg.tips[i].commit_id;
508 commit = arg.tips[i].commit;
509 new_node = arg.tips[i].new_node;
510 branch_done = arg.tips[i].branch_done;
511 changed = arg.tips[i].changed;
514 err = close_branch(graph, commit_id);
516 err = advance_branch(graph, new_node, commit_id,
520 if (changed && *changed_id == NULL)
521 *changed_id = commit_id;
524 for (i = 0; i < arg.ntips; i++)
525 got_object_commit_close(arg.tips[i].commit);
526 (*nfetched) = arg.ntips;
530 const struct got_error *
531 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
532 struct got_repository *repo)
534 const struct got_error *err;
535 int nfetched = 0, ncommits;
536 struct got_object_id *changed_id = NULL;
538 while (nfetched < limit) {
539 err = fetch_commits_from_open_branches(&ncommits,
540 &changed_id, graph, repo);
546 nfetched += ncommits;
552 static const struct got_error *
553 free_node_iter(struct got_object_id *id, void *data, void *arg)
555 struct got_commit_graph_node *node = data;
561 got_commit_graph_close(struct got_commit_graph *graph)
563 got_object_idset_free(graph->open_branches);
564 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
565 got_object_idset_free(graph->node_ids);
571 const struct got_error *
572 got_commit_graph_iter_start(struct got_commit_graph *graph,
573 struct got_object_id *id, struct got_repository *repo)
575 const struct got_error *err = NULL;
576 struct got_commit_graph_node *start_node;
577 struct got_commit_object *commit;
580 start_node = got_object_idset_get(graph->node_ids, id);
581 if (start_node == NULL)
582 return got_error_no_obj(id);
584 err = got_object_open_as_commit(&commit, repo, &start_node->id);
588 err = detect_changed_path(&changed, commit, &start_node->id,
591 got_object_commit_close(commit);
596 /* Locate first commit which changed graph->path. */
597 struct got_object_id *changed_id = NULL;
598 while (changed_id == NULL) {
600 err = fetch_commits_from_open_branches(&ncommits,
601 &changed_id, graph, repo);
603 got_object_commit_close(commit);
607 start_node = got_object_idset_get(graph->node_ids, changed_id);
609 got_object_commit_close(commit);
611 graph->iter_node = start_node;
615 const struct got_error *
616 got_commit_graph_iter_next(struct got_object_id **id,
617 struct got_commit_graph *graph)
621 if (graph->iter_node == NULL) {
622 /* We are done iterating, or iteration was not started. */
623 return got_error(GOT_ERR_ITER_COMPLETED);
626 if (graph->iter_node ==
627 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
628 got_object_idset_num_elements(graph->open_branches) == 0) {
629 /* We are done iterating. */
630 *id = &graph->iter_node->id;
631 graph->iter_node = NULL;
635 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
636 return got_error(GOT_ERR_ITER_NEED_MORE);
638 *id = &graph->iter_node->id;
639 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
643 const struct got_error *
644 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
645 struct got_object_id *commit_id, struct got_object_id *commit_id2,
646 struct got_repository *repo)
648 const struct got_error *err = NULL;
649 struct got_commit_graph *graph = NULL, *graph2 = NULL;
650 int completed = 0, completed2 = 0;
651 struct got_object_idset *commit_ids;
655 commit_ids = got_object_idset_alloc();
656 if (commit_ids == NULL)
657 return got_error_prefix_errno("got_object_idset_alloc");
659 err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
663 err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
667 err = got_commit_graph_iter_start(graph, commit_id, repo);
671 err = got_commit_graph_iter_start(graph2, commit_id2, repo);
676 struct got_object_id *id, *id2;
679 err = got_commit_graph_iter_next(&id, graph);
681 if (err->code == GOT_ERR_ITER_COMPLETED)
683 else if (err->code != GOT_ERR_ITER_NEED_MORE)
685 err = got_commit_graph_fetch_commits(graph, 1,
693 err = got_commit_graph_iter_next(&id2, graph2);
695 if (err->code == GOT_ERR_ITER_COMPLETED)
697 else if (err->code != GOT_ERR_ITER_NEED_MORE)
699 err = got_commit_graph_fetch_commits(graph2, 1,
707 if (got_object_idset_get(commit_ids, id)) {
708 *yca_id = got_object_id_dup(id);
712 err = got_error_prefix_errno(
717 err = got_object_idset_add(commit_ids, id, id);
722 if (got_object_idset_get(commit_ids, id2)) {
723 *yca_id = got_object_id_dup(id2);
727 err = got_error_prefix_errno(
732 err = got_object_idset_add(commit_ids, id2, id2);
737 if (completed && completed2) {
738 err = got_error(GOT_ERR_ANCESTRY);
744 got_object_idset_free(commit_ids);
746 got_commit_graph_close(graph);
748 got_commit_graph_close(graph2);