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_from_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_from_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;
479 ntips = got_object_idset_num_elements(graph->open_branches);
483 /* (Re-)allocate branch tips array if necessary. */
484 if (graph->ntips < ntips) {
485 struct got_commit_graph_branch_tip *tips;
486 tips = recallocarray(graph->tips, graph->ntips, ntips,
489 return got_error_from_errno("recallocarray");
491 graph->ntips = ntips;
493 arg.tips = graph->tips;
494 arg.ntips = 0; /* add_branch_tip() will increment */
497 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
502 for (i = 0; i < arg.ntips; i++) {
503 struct got_object_id *commit_id;
504 struct got_commit_object *commit;
505 struct got_commit_graph_node *new_node;
506 int branch_done, changed;
508 commit_id = arg.tips[i].commit_id;
509 commit = arg.tips[i].commit;
510 new_node = arg.tips[i].new_node;
511 branch_done = arg.tips[i].branch_done;
512 changed = arg.tips[i].changed;
515 err = close_branch(graph, commit_id);
517 err = advance_branch(graph, new_node, commit_id,
521 if (changed && changed_id && *changed_id == NULL)
522 *changed_id = commit_id;
525 for (i = 0; i < arg.ntips; i++)
526 got_object_commit_close(arg.tips[i].commit);
527 (*nfetched) = arg.ntips;
531 const struct got_error *
532 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
533 struct got_repository *repo)
535 const struct got_error *err;
536 int nfetched = 0, ncommits;
537 struct got_object_id *changed_id = NULL;
539 while (nfetched < limit) {
540 err = fetch_commits_from_open_branches(&ncommits,
541 &changed_id, graph, repo);
547 nfetched += ncommits;
553 static const struct got_error *
554 free_node_iter(struct got_object_id *id, void *data, void *arg)
556 struct got_commit_graph_node *node = data;
562 got_commit_graph_close(struct got_commit_graph *graph)
564 got_object_idset_free(graph->open_branches);
565 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
566 got_object_idset_free(graph->node_ids);
572 const struct got_error *
573 got_commit_graph_iter_start(struct got_commit_graph *graph,
574 struct got_object_id *id, struct got_repository *repo)
576 const struct got_error *err = NULL;
577 struct got_commit_graph_node *start_node;
578 struct got_commit_object *commit;
581 start_node = got_object_idset_get(graph->node_ids, id);
582 while (start_node == NULL) {
584 err = fetch_commits_from_open_branches(&ncommits, NULL, graph,
589 return got_error_no_obj(id);
590 start_node = got_object_idset_get(graph->node_ids, id);
593 err = got_object_open_as_commit(&commit, repo, &start_node->id);
597 err = detect_changed_path(&changed, commit, &start_node->id,
600 got_object_commit_close(commit);
605 /* Locate first commit which changed graph->path. */
606 struct got_object_id *changed_id = NULL;
607 while (changed_id == NULL) {
609 err = fetch_commits_from_open_branches(&ncommits,
610 &changed_id, graph, repo);
612 got_object_commit_close(commit);
616 start_node = got_object_idset_get(graph->node_ids, changed_id);
618 got_object_commit_close(commit);
620 graph->iter_node = start_node;
624 const struct got_error *
625 got_commit_graph_iter_next(struct got_object_id **id,
626 struct got_commit_graph *graph)
630 if (graph->iter_node == NULL) {
631 /* We are done iterating, or iteration was not started. */
632 return got_error(GOT_ERR_ITER_COMPLETED);
635 if (graph->iter_node ==
636 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
637 got_object_idset_num_elements(graph->open_branches) == 0) {
638 /* We are done iterating. */
639 *id = &graph->iter_node->id;
640 graph->iter_node = NULL;
644 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
645 return got_error(GOT_ERR_ITER_NEED_MORE);
647 *id = &graph->iter_node->id;
648 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);
652 const struct got_error *
653 got_commit_graph_find_youngest_common_ancestor(struct got_object_id **yca_id,
654 struct got_object_id *commit_id, struct got_object_id *commit_id2,
655 struct got_repository *repo)
657 const struct got_error *err = NULL;
658 struct got_commit_graph *graph = NULL, *graph2 = NULL;
659 int completed = 0, completed2 = 0;
660 struct got_object_idset *commit_ids;
664 commit_ids = got_object_idset_alloc();
665 if (commit_ids == NULL)
666 return got_error_from_errno("got_object_idset_alloc");
668 err = got_commit_graph_open(&graph, commit_id, "/", 1, repo);
672 err = got_commit_graph_open(&graph2, commit_id2, "/", 1, repo);
676 err = got_commit_graph_iter_start(graph, commit_id, repo);
680 err = got_commit_graph_iter_start(graph2, commit_id2, repo);
685 struct got_object_id *id, *id2;
688 err = got_commit_graph_iter_next(&id, graph);
690 if (err->code == GOT_ERR_ITER_COMPLETED)
692 else if (err->code != GOT_ERR_ITER_NEED_MORE)
694 err = got_commit_graph_fetch_commits(graph, 1,
702 err = got_commit_graph_iter_next(&id2, graph2);
704 if (err->code == GOT_ERR_ITER_COMPLETED)
706 else if (err->code != GOT_ERR_ITER_NEED_MORE)
708 err = got_commit_graph_fetch_commits(graph2, 1,
716 if (got_object_idset_get(commit_ids, id)) {
717 *yca_id = got_object_id_dup(id);
720 err = got_error_from_errno("got_object_id_dup");
724 err = got_object_idset_add(commit_ids, id, id);
729 if (got_object_idset_get(commit_ids, id2)) {
730 *yca_id = got_object_id_dup(id2);
733 err = got_error_from_errno("got_object_id_dup");
737 err = got_object_idset_add(commit_ids, id2, id2);
742 if (completed && completed2) {
743 err = got_error(GOT_ERR_ANCESTRY);
749 got_object_idset_free(commit_ids);
751 got_commit_graph_close(graph);
753 got_commit_graph_close(graph2);