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"
40 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
43 struct got_commit_graph_node {
44 struct got_object_id id;
47 * Each graph node corresponds to a commit object.
48 * Graph vertices are modelled with an adjacency list.
49 * Adjacencies of a graph node are parent (older) commits.
52 struct got_object_id_queue parent_ids;
54 time_t commit_timestamp;
56 /* Used during graph iteration. */
57 TAILQ_ENTRY(got_commit_graph_node) entry;
60 TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node);
62 struct got_commit_graph_branch_tip {
63 struct got_object_id *commit_id;
64 struct got_commit_object *commit;
65 struct got_commit_graph_node *new_node;
70 struct got_commit_graph {
71 /* The set of all commits we have traversed. */
72 struct got_object_idset *node_ids;
74 /* The commit at which traversal began (youngest commit in node_ids). */
75 struct got_commit_graph_node *head_node;
78 #define GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL 0x01
81 * A set of object IDs of known parent commits which we have not yet
82 * traversed. Each commit ID in this set represents a branch in commit
83 * history: Either the first-parent branch of the head node, or another
84 * branch corresponding to a traversed merge commit for which we have
85 * not traversed a branch point commit yet.
87 * Whenever we add a commit with a matching ID to the graph, we remove
88 * its corresponding element from this set, and add new elements for
89 * each of that commit's parent commits which were not traversed yet.
91 * When API users ask us to fetch more commits, we fetch commits from
92 * all currently open branches. This allows API users to process
93 * commits in linear order even though the history contains branches.
95 struct got_object_idset *open_branches;
97 /* Array of branch tips for fetch_commits_from_open_branches(). */
98 struct got_commit_graph_branch_tip *tips;
100 #define GOT_COMMIT_GRAPH_MIN_TIPS 10 /* minimum amount of tips to allocate */
102 /* Path of tree entry of interest to the API user. */
105 /* The next commit to return when the API user asks for one. */
106 struct got_commit_graph_node *iter_node;
108 /* The graph iteration list contains all nodes in sorted order. */
109 struct got_commit_graph_iter_list iter_list;
112 static struct got_commit_graph *
113 alloc_graph(const char *path)
115 struct got_commit_graph *graph;
117 graph = calloc(1, sizeof(*graph));
121 graph->path = strdup(path);
122 if (graph->path == NULL) {
127 graph->node_ids = got_object_idset_alloc();
128 if (graph->node_ids == NULL) {
134 graph->open_branches = got_object_idset_alloc();
135 if (graph->open_branches == NULL) {
136 got_object_idset_free(graph->node_ids);
142 TAILQ_INIT(&graph->iter_list);
148 is_head_node(struct got_commit_graph_node *node)
150 return node->nchildren == 0;
154 is_branch_point(struct got_commit_graph_node *node)
156 return node->nchildren > 1;
160 is_root_node(struct got_commit_graph_node *node)
162 return node->nparents == 0;
167 is_merge_point(struct got_commit_graph_node *node)
169 return node->nparents > 1;
172 static const struct got_error *
173 detect_changed_path(int *changed, struct got_commit_object *commit,
174 struct got_object_id *commit_id, const char *path,
175 struct got_repository *repo)
177 const struct got_error *err = NULL;
178 struct got_commit_object *pcommit = NULL;
179 struct got_tree_object *tree = NULL, *ptree = NULL;
180 struct got_object_qid *pid;
182 if (got_path_is_root_dir(path)) {
189 err = got_object_open_as_tree(&tree, repo, commit->tree_id);
193 pid = SIMPLEQ_FIRST(&commit->parent_ids);
195 struct got_object_id *obj_id;
196 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
198 if (err->code == GOT_ERR_NO_OBJ)
201 *changed = 1; /* The path was created in this commit. */
204 err = got_object_open_as_commit(&pcommit, repo, pid->id);
208 err = got_object_open_as_tree(&ptree, repo, pcommit->tree_id);
212 err = got_object_tree_path_changed(changed, tree, ptree, path,
217 got_object_tree_close(tree);
219 got_object_tree_close(ptree);
221 got_object_commit_close(pcommit);
226 add_node_to_iter_list(struct got_commit_graph *graph,
227 struct got_commit_graph_node *node,
228 struct got_commit_graph_node *child_node)
230 struct got_commit_graph_node *n, *next;
232 if (TAILQ_EMPTY(&graph->iter_list)) {
233 TAILQ_INSERT_HEAD(&graph->iter_list, node, entry);
234 graph->iter_node = node;
238 n = graph->iter_node;
239 /* Ensure that an iteration in progress will see this new commit. */
241 next = TAILQ_NEXT(n, entry);
242 if (next && node->commit_timestamp >= next->commit_timestamp) {
243 TAILQ_INSERT_BEFORE(next, node, entry);
248 TAILQ_INSERT_TAIL(&graph->iter_list, node, entry);
251 static const struct got_error *
252 add_vertex(struct got_object_id_queue *ids, struct got_object_id *id)
254 const struct got_error *err = NULL;
255 struct got_object_qid *qid;
257 err = got_object_qid_alloc(&qid, id);
261 SIMPLEQ_INSERT_TAIL(ids, qid, entry);
265 static const struct got_error *
266 close_branch(struct got_commit_graph *graph, struct got_object_id *commit_id)
268 const struct got_error *err;
270 err = got_object_idset_remove(NULL, graph->open_branches, commit_id);
271 if (err && err->code != GOT_ERR_NO_OBJ)
276 static const struct got_error *
277 advance_branch(struct got_commit_graph *graph,
278 struct got_commit_graph_node *node,
279 struct got_object_id *commit_id, struct got_commit_object *commit,
280 struct got_repository *repo)
282 const struct got_error *err;
283 struct got_object_qid *qid;
285 err = close_branch(graph, commit_id);
289 if (graph->flags & GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL) {
290 qid = SIMPLEQ_FIRST(&commit->parent_ids);
293 err = got_object_idset_add(graph->open_branches, qid->id, node);
298 * If we are graphing commits for a specific path, skip branches
299 * which do not contribute any content to this path.
301 if (is_merge_point(node) && !got_path_is_root_dir(graph->path)) {
302 struct got_object_id *id, *merged_id, *prev_id = NULL;
303 int branches_differ = 0;
305 err = got_object_id_by_path(&merged_id, repo, commit_id,
310 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
311 if (got_object_idset_get(graph->node_ids, qid->id))
312 continue; /* parent already traversed */
314 err = got_object_id_by_path(&id, repo, qid->id,
317 if (err->code == GOT_ERR_NO_OBJ) {
325 if (!branches_differ &&
326 got_object_id_cmp(merged_id, prev_id) != 0)
332 * If a branch has created the merged content we can
333 * skip any other branches.
335 if (got_object_id_cmp(merged_id, id) == 0) {
336 err = got_object_idset_add(graph->open_branches,
343 * If the path's content is the same on all branches,
344 * follow the first parent only.
346 if (!branches_differ) {
347 qid = SIMPLEQ_FIRST(&commit->parent_ids);
350 if (got_object_idset_get(graph->node_ids, qid->id))
351 return NULL; /* parent already traversed */
352 if (got_object_idset_get(graph->open_branches, qid->id))
354 return got_object_idset_add(graph->open_branches,
359 SIMPLEQ_FOREACH(qid, &commit->parent_ids, entry) {
360 if (got_object_idset_get(graph->node_ids, qid->id))
361 continue; /* parent already traversed */
362 if (got_object_idset_get(graph->open_branches, qid->id))
364 err = got_object_idset_add(graph->open_branches, qid->id, node);
373 free_node(struct got_commit_graph_node *node)
375 while (!SIMPLEQ_EMPTY(&node->parent_ids)) {
376 struct got_object_qid *pid = SIMPLEQ_FIRST(&node->parent_ids);
377 SIMPLEQ_REMOVE_HEAD(&node->parent_ids, entry);
378 got_object_qid_free(pid);
383 static const struct got_error *
384 add_node(struct got_commit_graph_node **new_node, int *changed,
385 int *branch_done, struct got_commit_graph *graph,
386 struct got_object_id *commit_id, struct got_commit_object *commit,
387 struct got_commit_graph_node *child_node, struct got_repository *repo)
389 const struct got_error *err = NULL;
390 struct got_commit_graph_node *node;
391 struct got_object_qid *pid;
397 node = calloc(1, sizeof(*node));
399 return got_error_from_errno();
401 memcpy(&node->id, commit_id, sizeof(node->id));
402 SIMPLEQ_INIT(&node->parent_ids);
403 SIMPLEQ_FOREACH(pid, &commit->parent_ids, entry) {
404 err = add_vertex(&node->parent_ids, pid->id);
411 node->commit_timestamp = commit->committer_time;
413 err = got_object_idset_add(graph->node_ids, &node->id, node);
419 err = detect_changed_path(changed, commit, commit_id, graph->path,
422 if (err->code == GOT_ERR_NO_OBJ) {
424 * History of the path stops here on the current
425 * branch. Keep going on other branches.
436 add_node_to_iter_list(graph, node, child_node);
446 const struct got_error *
447 got_commit_graph_open(struct got_commit_graph **graph,
448 struct got_object_id *commit_id, const char *path,
449 int first_parent_traversal, struct got_repository *repo)
451 const struct got_error *err = NULL;
452 struct got_commit_object *commit;
453 int changed, branch_done;
457 err = got_object_open_as_commit(&commit, repo, commit_id);
461 /* The path must exist in our initial commit. */
462 if (!got_path_is_root_dir(path)) {
463 struct got_object_id *obj_id;
464 err = got_object_id_by_path(&obj_id, repo, commit_id, path);
470 *graph = alloc_graph(path);
471 if (*graph == NULL) {
472 got_object_commit_close(commit);
473 return got_error_from_errno();
476 if (first_parent_traversal)
477 (*graph)->flags |= GOT_COMMIT_GRAPH_FIRST_PARENT_TRAVERSAL;
479 err = add_node(&(*graph)->head_node, &changed, &branch_done, *graph,
480 commit_id, commit, NULL, repo);
482 err = advance_branch(*graph, (*graph)->head_node, commit_id,
485 got_object_commit_close(commit);
487 got_commit_graph_close(*graph);
495 struct add_branch_tip_arg {
496 struct got_commit_graph_branch_tip *tips;
498 struct got_repository *repo;
499 struct got_commit_graph *graph;
502 static const struct got_error *
503 add_branch_tip(struct got_object_id *commit_id, void *data, void *arg)
505 const struct got_error *err;
506 struct got_commit_graph_node *child_node = data;
507 struct add_branch_tip_arg *a = arg;
508 struct got_commit_graph_node *new_node;
509 struct got_commit_object *commit;
510 int changed, branch_done;
512 err = got_object_open_as_commit(&commit, a->repo, commit_id);
516 err = add_node(&new_node, &changed, &branch_done, a->graph,
517 commit_id, commit, child_node, a->repo);
521 a->tips[a->ntips].commit_id = new_node ? &new_node->id : NULL;
522 a->tips[a->ntips].commit = commit;
523 a->tips[a->ntips].new_node = new_node;
524 a->tips[a->ntips].changed = changed;
525 a->tips[a->ntips].branch_done = branch_done;
531 static const struct got_error *
532 fetch_commits_from_open_branches(int *nfetched,
533 struct got_object_id **changed_id, struct got_commit_graph *graph,
534 struct got_repository *repo)
536 const struct got_error *err;
537 struct add_branch_tip_arg arg;
543 ntips = got_object_idset_num_elements(graph->open_branches);
547 /* (Re-)allocate branch tips array if necessary. */
548 if (graph->ntips < ntips) {
549 struct got_commit_graph_branch_tip *tips;
550 tips = reallocarray(graph->tips,
551 MIN(ntips, GOT_COMMIT_GRAPH_MIN_TIPS), sizeof(*tips));
553 return got_error_from_errno();
555 graph->ntips = ntips;
557 arg.tips = graph->tips;
558 arg.ntips = 0; /* add_branch_tip() will increment */
561 err = got_object_idset_for_each(graph->open_branches, add_branch_tip,
566 for (i = 0; i < arg.ntips; i++) {
567 struct got_object_id *commit_id;
568 struct got_commit_object *commit;
569 struct got_commit_graph_node *new_node;
570 int branch_done, changed;
572 commit_id = arg.tips[i].commit_id;
573 commit = arg.tips[i].commit;
574 new_node = arg.tips[i].new_node;
575 branch_done = arg.tips[i].branch_done;
576 changed = arg.tips[i].changed;
579 err = close_branch(graph, commit_id);
581 err = advance_branch(graph, new_node, commit_id,
585 if (changed && *changed_id == NULL)
586 *changed_id = commit_id;
589 for (i = 0; i < ntips; i++)
590 got_object_commit_close(arg.tips[i].commit);
591 (*nfetched) = arg.ntips;
595 const struct got_error *
596 got_commit_graph_fetch_commits(struct got_commit_graph *graph, int limit,
597 struct got_repository *repo)
599 const struct got_error *err;
600 int nfetched = 0, ncommits;
601 struct got_object_id *changed_id = NULL;
603 while (nfetched < limit) {
604 err = fetch_commits_from_open_branches(&ncommits,
605 &changed_id, graph, repo);
611 nfetched += ncommits;
617 static const struct got_error *
618 free_node_iter(struct got_object_id *id, void *data, void *arg)
620 struct got_commit_graph_node *node = data;
626 got_commit_graph_close(struct got_commit_graph *graph)
628 got_object_idset_free(graph->open_branches);
629 got_object_idset_for_each(graph->node_ids, free_node_iter, NULL);
630 got_object_idset_free(graph->node_ids);
636 const struct got_error *
637 got_commit_graph_iter_start(struct got_commit_graph *graph,
638 struct got_object_id *id, struct got_repository *repo)
640 const struct got_error *err = NULL;
641 struct got_commit_graph_node *start_node;
642 struct got_commit_object *commit;
645 start_node = got_object_idset_get(graph->node_ids, id);
646 if (start_node == NULL)
647 return got_error(GOT_ERR_NO_OBJ);
649 err = got_object_open_as_commit(&commit, repo, &start_node->id);
653 err = detect_changed_path(&changed, commit, &start_node->id,
656 got_object_commit_close(commit);
661 /* Locate first commit which changed graph->path. */
662 struct got_object_id *changed_id = NULL;
663 while (changed_id == NULL) {
665 err = fetch_commits_from_open_branches(&ncommits,
666 &changed_id, graph, repo);
668 got_object_commit_close(commit);
672 start_node = got_object_idset_get(graph->node_ids, changed_id);
674 got_object_commit_close(commit);
676 graph->iter_node = start_node;
680 const struct got_error *
681 got_commit_graph_iter_next(struct got_object_id **id,
682 struct got_commit_graph *graph)
686 if (graph->iter_node == NULL) {
687 /* We are done iterating, or iteration was not started. */
688 return got_error(GOT_ERR_ITER_COMPLETED);
691 if (graph->iter_node ==
692 TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) &&
693 got_object_idset_num_elements(graph->open_branches) == 0) {
694 /* We are done iterating. */
695 *id = &graph->iter_node->id;
696 graph->iter_node = NULL;
700 if (TAILQ_NEXT(graph->iter_node, entry) == NULL)
701 return got_error(GOT_ERR_ITER_NEED_MORE);
703 *id = &graph->iter_node->id;
704 graph->iter_node = TAILQ_NEXT(graph->iter_node, entry);