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"
33 #include "got_lib_delta.h"
34 #include "got_lib_inflate.h"
35 #include "got_lib_object.h"
36 #include "got_lib_object_idset.h"
37 #include "got_lib_path.h"
39 struct got_commit_graph_node {
40 struct got_object_id id;
43 * Each graph node corresponds to a commit object.
44 * Graph vertices are modelled with an adjacency list.
45 * Adjacencies of a graph node are parent (older) commits.
48 struct got_object_id_queue parent_ids;
50 time_t commit_timestamp;
52 /* Used during graph iteration. */
53 TAILQ_ENTRY(got_commit_graph_node) entry;
56 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
58 struct got_commit_graph_branch_tip {
59 struct got_object_id *commit_id;
60 struct got_commit_object *commit;
61 struct got_commit_graph_node *new_node;
66 struct got_commit_graph {
67 /* The set of all commits we have traversed. */
68 struct got_object_idset *node_ids;
70 /* The commit at which traversal began (youngest commit in node_ids). */
71 struct got_commit_graph_node *head_node;
74 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
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;
97 /* Path of tree entry of interest to the API user. */
100 /* The next commit to return when the API user asks for one. */
101 struct got_commit_graph_node *iter_node;
103 /* The graph iteration list contains all nodes in sorted order. */
104 struct got_commit_graph_iter_list iter_list;
107 static struct got_commit_graph *
108 alloc_graph(const char *path)
110 struct got_commit_graph *graph;
112 graph = calloc(1, sizeof(*graph));
116 graph->path = strdup(path);
117 if (graph->path == NULL) {
122 graph->node_ids = got_object_idset_alloc();
123 if (graph->node_ids == NULL) {
129 graph->open_branches = got_object_idset_alloc();
130 if (graph->open_branches == NULL) {
131 got_object_idset_free(graph->node_ids);
137 TAILQ_INIT(&graph->iter_list);
143 is_head_node(struct got_commit_graph_node *node)
145 return node->nchildren == 0;
149 is_branch_point(struct got_commit_graph_node *node)
151 return node->nchildren > 1;
155 is_root_node(struct got_commit_graph_node *node)
157 return node->nparents == 0;
162 is_merge_point(struct got_commit_graph_node *node)
164 return node->nparents > 1;
167 static const struct got_error *
168 detect_changed_path(int *changed, struct got_commit_object *commit,
169 struct got_object_id *commit_id, const char *path,
170 struct got_repository *repo)
172 const struct got_error *err = NULL;
173 struct got_commit_object *pcommit = NULL;
174 struct got_tree_object *tree = NULL, *ptree = NULL;
175 struct got_object_qid *pid;
177 if (got_path_is_root_dir(path)) {
184 pid = SIMPLEQ_FIRST(&commit->parent_ids);
186 struct got_object_id *obj_id;
187 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
189 if (err->code == GOT_ERR_NO_TREE_ENTRY)
192 *changed = 1; /* The path was created in this commit. */
195 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
199 err = got_object_open_as_commit(&pcommit, repo, pid->id);
203 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
207 err = got_object_tree_path_changed(changed, tree, ptree, path,
212 got_object_tree_close(tree);
214 got_object_tree_close(ptree);
216 got_object_commit_close(pcommit);
221 add_node_to_iter_list(struct got_commit_graph *graph,
222 struct got_commit_graph_node *node,
223 struct got_commit_graph_node *child_node)
225 struct got_commit_graph_node *n, *next;
227 if (TAILQ_EMPTY(&graph->iter_list)) {
228 TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
229 graph->iter_node = node;
233 n = graph->iter_node;
234 /* Ensure that an iteration in progress will see this new commit. */
236 next = TAILQ_NEXT(n, entry);
237 if (next && node->commit_timestamp >= next->commit_timestamp) {
238 TAILQ_INSERT_BEFORE(next, node, entry);
243 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
246 static const struct got_error *
247 add_vertex(struct got_object_id_queue *ids, struct got_object_id *id)
249 const struct got_error *err = NULL;
250 struct got_object_qid *qid;
252 err = got_object_qid_alloc(&qid, id);
256 SIMPLEQ_INSERT_TAIL(ids, qid, entry);
260 static const struct got_error *
261 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
263 const struct got_error *err;
265 err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
266 if (err && err->code != GOT_ERR_NO_OBJ)
271 static const struct got_error *
272 advance_branch(struct got_commit_graph *graph,
273 struct got_commit_graph_node *node,
274 struct got_object_id *commit_id, struct got_commit_object *commit,
275 struct got_repository *repo)
277 const struct got_error *err;
278 struct got_object_qid *qid;
280 err = close_branch(graph, commit_id);
284 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
285 qid = SIMPLEQ_FIRST(&commit->parent_ids);
287 got_object_idset_get(graph->open_branches, qid->id))
289 return got_object_idset_add(graph->open_branches,
294 * If we are graphing commits for a specific path, skip branches
295 * which do not contribute any content to this path.
297 if (is_merge_point(node) && !got_path_is_root_dir(graph->path)) {
298 struct got_object_id *merged_id, *prev_id = NULL;
299 int branches_differ = 0;
301 err = got_object_id_by_path(&merged_id, repo, commit_id,
306 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
307 struct got_object_id *id;
309 if (got_object_idset_get(graph->node_ids, qid->id))
310 continue; /* parent already traversed */
311 if (got_object_idset_get(graph->open_branches, qid->id))
314 err = got_object_id_by_path(&id, repo, qid->id,
317 if (err->code == GOT_ERR_NO_TREE_ENTRY) {
327 if (!branches_differ &&
328 got_object_id_cmp(id, prev_id) != 0)
335 * If a branch has created the merged content we can
336 * skip any other branches.
338 if (got_object_id_cmp(merged_id, id) == 0) {
339 err = got_object_idset_add(graph->open_branches,
353 * If the path's content is the same on all branches,
354 * follow the first parent only.
356 if (!branches_differ) {
357 qid = SIMPLEQ_FIRST(&commit->parent_ids);
360 if (got_object_idset_get(graph->node_ids, qid->id))
361 return NULL; /* parent already traversed */
362 if (got_object_idset_get(graph->open_branches, qid->id))
364 return got_object_idset_add(graph->open_branches,
369 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
370 if (got_object_idset_get(graph->node_ids, qid->id))
371 continue; /* parent already traversed */
372 if (got_object_idset_get(graph->open_branches, qid->id))
374 err = got_object_idset_add(graph->open_branches, qid->id, node);
383 free_node(struct got_commit_graph_node *node)
385 while (!SIMPLEQ_EMPTY(&node->parent_ids)) {
386 struct got_object_qid *pid = SIMPLEQ_FIRST(&node->parent_ids);
387 SIMPLEQ_REMOVE_HEAD(&node->parent_ids, entry);
388 got_object_qid_free(pid);
393 static const struct got_error *
394 add_node(struct got_commit_graph_node **new_node, int *changed,
395 int *branch_done, struct got_commit_graph *graph,
396 struct got_object_id *commit_id, struct got_commit_object *commit,
397 struct got_commit_graph_node *child_node, struct got_repository *repo)
399 const struct got_error *err = NULL;
400 struct got_commit_graph_node *node;
401 struct got_object_qid *pid;
407 node = calloc(1, sizeof(*node));
409 return got_error_from_errno();
411 memcpy(&node->id, commit_id, sizeof(node->id));
412 SIMPLEQ_INIT(&node->parent_ids);
413 SIMPLEQ_FOREACH(pid, &commit->parent_ids, entry) {
414 err = add_vertex(&node->parent_ids, pid->id);
421 node->commit_timestamp = commit->committer_time;
423 err = got_object_idset_add(graph->node_ids, &node->id, node);
429 err = detect_changed_path(changed, commit, commit_id, graph->path,
432 if (err->code == GOT_ERR_NO_OBJ) {
434 * History of the path stops here on the current
435 * branch. Keep going on other branches.
440 got_object_idset_remove(NULL, graph->node_ids,
448 add_node_to_iter_list(graph, node, child_node);
453 const struct got_error *
454 got_commit_graph_open(struct got_commit_graph **graph,
455 struct got_object_id *commit_id, const char *path,
456 int first_parent_traversal, struct got_repository *repo)
458 const struct got_error *err = NULL;
459 struct got_commit_object *commit;
460 int changed, branch_done;
464 err = got_object_open_as_commit(&commit, repo, commit_id);
468 /* The path must exist in our initial commit. */
469 if (!got_path_is_root_dir(path)) {
470 struct got_object_id *obj_id;
471 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
477 *graph = alloc_graph(path);
478 if (*graph == NULL) {
479 got_object_commit_close(commit);
480 return got_error_from_errno();
483 if (first_parent_traversal)
484 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
486 err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
487 commit_id, commit, NULL, repo);
489 err = advance_branch(*graph, (*graph)->head_node, commit_id,
492 got_object_commit_close(commit);
494 got_commit_graph_close(*graph);
502 struct add_branch_tip_arg {
503 struct got_commit_graph_branch_tip *tips;
505 struct got_repository *repo;
506 struct got_commit_graph *graph;
509 static const struct got_error *
510 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
512 const struct got_error *err;
513 struct got_commit_graph_node *child_node = data;
514 struct add_branch_tip_arg *a = arg;
515 struct got_commit_graph_node *new_node;
516 struct got_commit_object *commit;
517 int changed, branch_done;
519 err = got_object_open_as_commit(&commit, a->repo, commit_id);
523 err = add_node(&new_node, &changed, &branch_done, a->graph,
524 commit_id, commit, child_node, a->repo);
528 a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
529 a->tips[a->ntips].commit = commit;
530 a->tips[a->ntips].new_node = new_node;
531 a->tips[a->ntips].changed = changed;
532 a->tips[a->ntips].branch_done = branch_done;
538 static const struct got_error *
539 fetch_commits_from_open_branches(int *nfetched,
540 struct got_object_id **changed_id, struct got_commit_graph *graph,
541 struct got_repository *repo)
543 const struct got_error *err;
544 struct add_branch_tip_arg arg;
550 ntips = got_object_idset_num_elements(graph->open_branches);
554 /* (Re-)allocate branch tips array if necessary. */
555 if (graph->ntips < ntips) {
556 struct got_commit_graph_branch_tip *tips;
557 tips = recallocarray(graph->tips, graph->ntips, ntips,
560 return got_error_from_errno();
562 graph->ntips = ntips;
564 arg.tips = graph->tips;
565 arg.ntips = 0; /* add_branch_tip() will increment */
568 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
573 for (i = 0; i < arg.ntips; i++) {
574 struct got_object_id *commit_id;
575 struct got_commit_object *commit;
576 struct got_commit_graph_node *new_node;
577 int branch_done, changed;
579 commit_id = arg.tips[i].commit_id;
580 commit = arg.tips[i].commit;
581 new_node = arg.tips[i].new_node;
582 branch_done = arg.tips[i].branch_done;
583 changed = arg.tips[i].changed;
586 err = close_branch(graph, commit_id);
588 err = advance_branch(graph, new_node, commit_id,
592 if (changed && *changed_id == NULL)
593 *changed_id = commit_id;
596 for (i = 0; i < arg.ntips; i++)
597 got_object_commit_close(arg.tips[i].commit);
598 (*nfetched) = arg.ntips;
602 const struct got_error *
603 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
604 struct got_repository *repo)
606 const struct got_error *err;
607 int nfetched = 0, ncommits;
608 struct got_object_id *changed_id = NULL;
610 while (nfetched < limit) {
611 err = fetch_commits_from_open_branches(&ncommits,
612 &changed_id, graph, repo);
618 nfetched += ncommits;
624 static const struct got_error *
625 free_node_iter(struct got_object_id *id, void *data, void *arg)
627 struct got_commit_graph_node *node = data;
633 got_commit_graph_close(struct got_commit_graph *graph)
635 got_object_idset_free(graph->open_branches);
636 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
637 got_object_idset_free(graph->node_ids);
643 const struct got_error *
644 got_commit_graph_iter_start(struct got_commit_graph *graph,
645 struct got_object_id *id, struct got_repository *repo)
647 const struct got_error *err = NULL;
648 struct got_commit_graph_node *start_node;
649 struct got_commit_object *commit;
652 start_node = got_object_idset_get(graph->node_ids, id);
653 if (start_node == NULL)
654 return got_error_no_obj(id);
656 err = got_object_open_as_commit(&commit, repo, &start_node->id);
660 err = detect_changed_path(&changed, commit, &start_node->id,
663 got_object_commit_close(commit);
668 /* Locate first commit which changed graph->path. */
669 struct got_object_id *changed_id = NULL;
670 while (changed_id == NULL) {
672 err = fetch_commits_from_open_branches(&ncommits,
673 &changed_id, graph, repo);
675 got_object_commit_close(commit);
679 start_node = got_object_idset_get(graph->node_ids, changed_id);
681 got_object_commit_close(commit);
683 graph->iter_node = start_node;
687 const struct got_error *
688 got_commit_graph_iter_next(struct got_object_id **id,
689 struct got_commit_graph *graph)
693 if (graph->iter_node == NULL) {
694 /* We are done iterating, or iteration was not started. */
695 return got_error(GOT_ERR_ITER_COMPLETED);
698 if (graph->iter_node ==
699 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
700 got_object_idset_num_elements(graph->open_branches) == 0) {
701 /* We are done iterating. */
702 *id = &graph->iter_node->id;
703 graph->iter_node = NULL;
707 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
708 return got_error(GOT_ERR_ITER_NEED_MORE);
710 *id = &graph->iter_node->id;
711 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);