commit 9ba79e04983cd5159d9153ecfd6da5ce29b1d6d6 from: Stefan Sperling date: Mon Jun 11 16:42:04 2018 UTC commit graph support for tog(1) commit - 31920504bebc2c8f3ffbad51600262290ac0dd8c commit + 9ba79e04983cd5159d9153ecfd6da5ce29b1d6d6 blob - 57706b257defb1d2c159334cbf451d10288dbe2d blob + 62e4d6ab75e22830b973ee01eaacf12b6d95eac7 --- got/got.c +++ got/got.c @@ -393,6 +393,10 @@ print_commits(struct got_object *root_obj, struct got_ err = got_commit_graph_iter_next(&id, graph); if (err) { + if (err->code == GOT_ERR_ITER_COMPLETED) { + err = NULL; + break; + } if (err->code != GOT_ERR_ITER_NEED_MORE) break; err = got_commit_graph_fetch_commits(&ncommits, blob - c833782d857cbadfdabe946bb49707a3c7fa881c blob + 146ee742c19732ef9f95fcec97540f7ead972b02 --- include/got_error.h +++ include/got_error.h @@ -59,6 +59,7 @@ #define GOT_ERR_OBJ_EXISTS 43 #define GOT_ERR_BAD_OBJ_ID 44 #define GOT_ERR_ITER_NEED_MORE 45 +#define GOT_ERR_ITER_COMPLETED 46 static const struct got_error { int code; @@ -107,6 +108,7 @@ static const struct got_error { { GOT_ERR_OBJ_EXISTS, "object already exists" }, { GOT_ERR_BAD_OBJ_ID, "bad object id" }, { GOT_ERR_ITER_NEED_MORE,"more items needed to continue iteration" }, + { GOT_ERR_ITER_COMPLETED,"iteration completed" }, }; /* blob - f9af65bf970a89bbc65b7cf4f26194474ac4f70d blob + 09035ff59b7dcf9f8612b5ed112bf58ad4c5b22b --- lib/commit_graph.c +++ lib/commit_graph.c @@ -55,6 +55,8 @@ struct got_commit_graph_node { TAILQ_ENTRY(got_commit_graph_node) entry; }; +TAILQ_HEAD(got_commit_graph_iter_list, got_commit_graph_node); + struct got_commit_graph { /* The set of all commits we have traversed. */ struct got_object_idset *node_ids; @@ -82,7 +84,8 @@ struct got_commit_graph { /* The next commit to return when the API user asks for one. */ struct got_commit_graph_node *iter_node; - TAILQ_HEAD(, got_commit_graph_node) iter_list; + /* The graph iteration list contains all nodes in sorted order. */ + struct got_commit_graph_iter_list iter_list; }; static struct got_commit_graph * @@ -129,17 +132,18 @@ is_branch_point(struct got_commit_graph_node *node) { return node->nchildren > 1; } -#endif static int is_root_node(struct got_commit_graph_node *node) { return node->nparents == 0; } +#endif static void -add_iteration_candidate(struct got_commit_graph *graph, - struct got_commit_graph_node *node) +add_node_to_iter_list(struct got_commit_graph *graph, + struct got_commit_graph_node *node, + struct got_commit_graph_node *child_node) { struct got_commit_graph_node *n, *next; @@ -148,7 +152,14 @@ add_iteration_candidate(struct got_commit_graph *graph return; } - TAILQ_FOREACH(n, &graph->iter_list, entry) { + /* + * If a child node is known, start iterating there. + * All parent commits *should* appear before their children unless + * commit timestamps are broken (in which case the ordering of + * commits will be broken either way). + */ + n = child_node ? child_node : TAILQ_FIRST(&graph->iter_list); + do { if (node->commit_timestamp < n->commit_timestamp) { next = TAILQ_NEXT(n, entry); if (next == NULL) { @@ -164,7 +175,8 @@ add_iteration_candidate(struct got_commit_graph *graph TAILQ_INSERT_BEFORE(n, node, entry); break; } - } + n = TAILQ_NEXT(n, entry); + } while (n); } static const struct got_error * @@ -190,7 +202,7 @@ add_vertex(struct got_object_id_queue *ids, struct got static const struct got_error * add_node(struct got_commit_graph_node **new_node, struct got_commit_graph *graph, struct got_object_id *commit_id, - struct got_commit_object *commit, struct got_object_id *child_commit_id) + struct got_commit_object *commit, struct got_commit_graph_node *child_node) { const struct got_error *err = NULL; struct got_commit_graph_node *node, *existing_node; @@ -218,7 +230,7 @@ add_node(struct got_commit_graph_node **new_node, if (err == NULL) { struct got_object_qid *qid; - add_iteration_candidate(graph, node); + add_node_to_iter_list(graph, node, child_node); err = got_object_idset_remove(graph->open_branches, commit_id); if (err && err->code != GOT_ERR_NO_OBJ) return err; @@ -231,11 +243,6 @@ add_node(struct got_commit_graph_node **new_node, return err; } *new_node = node; - { - char *id_str; - if (got_object_id_str(&id_str, &node->id) == NULL) - fprintf(stderr, "added node %s\n", id_str); - } } else if (err->code == GOT_ERR_OBJ_EXISTS) { err = NULL; free(node); @@ -245,24 +252,23 @@ add_node(struct got_commit_graph_node **new_node, return err; } - if (child_commit_id) { + if (child_node) { struct got_object_qid *cid; /* Prevent linking to self. */ - if (got_object_id_cmp(commit_id, child_commit_id) == 0) + if (got_object_id_cmp(commit_id, &child_node->id) == 0) return got_error(GOT_ERR_BAD_OBJ_ID); /* Prevent double-linking to the same child. */ SIMPLEQ_FOREACH(cid, &node->child_ids, entry) { - if (got_object_id_cmp(cid->id, child_commit_id) == 0) + if (got_object_id_cmp(cid->id, &child_node->id) == 0) return got_error(GOT_ERR_BAD_OBJ_ID); } - err = add_vertex(&node->child_ids, child_commit_id); + err = add_vertex(&node->child_ids, &child_node->id); if (err) return err; node->nchildren++; - } return err; @@ -358,8 +364,7 @@ fetch_commits_from_open_branches(int *ncommits, int *w if (err) break; - err = add_node(&new_node, graph, commit_id, commit, - &child_node->id); + err = add_node(&new_node, graph, commit_id, commit, child_node); got_object_commit_close(commit); if (err) { if (err->code != GOT_ERR_OBJ_EXISTS) @@ -449,27 +454,13 @@ const struct got_error * got_commit_graph_iter_start(struct got_commit_graph *graph, struct got_object_id *id) { - struct got_commit_graph_node *start_node, *node; - struct got_object_qid *qid; + struct got_commit_graph_node *start_node; start_node = got_object_idset_get(graph->node_ids, id); if (start_node == NULL) return got_error(GOT_ERR_NO_OBJ); graph->iter_node = start_node; - - while (!TAILQ_EMPTY(&graph->iter_list)) { - node = TAILQ_FIRST(&graph->iter_list); - TAILQ_REMOVE(&graph->iter_list, node, entry); - } - - /* Put all known parents of this commit on the candidate list. */ - SIMPLEQ_FOREACH(qid, &start_node->parent_ids, entry) { - node = got_object_idset_get(graph->node_ids, qid->id); - if (node) - add_iteration_candidate(graph, node); - } - return NULL; } @@ -477,28 +468,26 @@ const struct got_error * got_commit_graph_iter_next(struct got_object_id **id, struct got_commit_graph *graph) { - struct got_commit_graph_node *node; + *id = NULL; if (graph->iter_node == NULL) { /* We are done interating, or iteration was not started. */ - *id = NULL; + return got_error(GOT_ERR_ITER_COMPLETED); + } + + if (graph->iter_node == + TAILQ_LAST(&graph->iter_list, got_commit_graph_iter_list) && + got_object_idset_num_elements(graph->open_branches) == 0) { + *id = &graph->iter_node->id; + /* We are done interating. */ + graph->iter_node = NULL; return NULL; } - if (TAILQ_EMPTY(&graph->iter_list)) { - if (is_root_node(graph->iter_node) && - got_object_idset_num_elements(graph->open_branches) == 0) { - *id = &graph->iter_node->id; - /* We are done interating. */ - graph->iter_node = NULL; - return NULL; - } + if (TAILQ_NEXT(graph->iter_node, entry) == NULL) return got_error(GOT_ERR_ITER_NEED_MORE); - } *id = &graph->iter_node->id; - node = TAILQ_FIRST(&graph->iter_list); - TAILQ_REMOVE(&graph->iter_list, node, entry); - graph->iter_node = node; + graph->iter_node = TAILQ_NEXT(graph->iter_node, entry); return NULL; } blob - e9d830ddae7ec0081ab0ac6f89dc5db4ee284958 blob + 9bf2f9c79faacaeba0a3fd9bda9c541d785217c9 --- tog/tog.c +++ tog/tog.c @@ -38,6 +38,7 @@ #include "got_repository.h" #include "got_diff.h" #include "got_opentemp.h" +#include "got_commit_graph.h" #ifndef MIN #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) @@ -292,7 +293,7 @@ pop_commit(struct commit_queue *commits) entry = TAILQ_FIRST(commits); TAILQ_REMOVE(commits, entry, entry); got_object_commit_close(entry->commit); - free(entry->id); + /* Don't free entry->id! It is owned by the commit graph. */ free(entry); } @@ -304,194 +305,112 @@ free_commits(struct commit_queue *commits) } static const struct got_error * -fetch_parent_commit(struct commit_queue_entry **pentry, - struct commit_queue_entry *entry, struct got_repository *repo) +queue_commits(struct got_commit_graph *graph, struct commit_queue *commits, + struct got_object_id *start_id, struct got_repository *repo) { const struct got_error *err = NULL; - struct got_commit_object *commit; struct got_object_id *id; - struct got_object_qid *qid; - - *pentry = NULL; + struct commit_queue_entry *entry; - /* Follow the first parent (TODO: handle merge commits). */ - qid = SIMPLEQ_FIRST(&entry->commit->parent_ids); - if (qid == NULL) - return NULL; - - err = got_object_open_as_commit(&commit, repo, qid->id); + err = got_commit_graph_iter_start(graph, start_id); if (err) return err; - id = got_object_id_dup(qid->id); - if (id == NULL) { - err = got_error_from_errno(); - got_object_commit_close(commit); - return err;; - } + entry = TAILQ_LAST(commits, commit_queue); + if (entry && got_object_id_cmp(entry->id, start_id) == 0) { + int nfetched; - *pentry = alloc_commit_queue_entry(commit, id); - if (*pentry == NULL) { - err = got_error_from_errno(); - got_object_commit_close(commit); + /* Start ID's commit is already on the queue; skip over it. */ + err = got_commit_graph_iter_next(&id, graph); + if (err && err->code != GOT_ERR_ITER_NEED_MORE) + return err; + + err = got_commit_graph_fetch_commits(&nfetched, graph, 1, repo); + if (err) + return err; } - return err;; -} + while (1) { + struct got_commit_object *commit; -static const struct got_error * -get_head_commit_id(struct got_object_id **head_id, struct got_repository *repo) -{ - const struct got_error *err = NULL; - struct got_reference *head_ref; + err = got_commit_graph_iter_next(&id, graph); + if (err) { + if (err->code == GOT_ERR_ITER_NEED_MORE) + err = NULL; + break; + } - *head_id = NULL; + err = got_object_open_as_commit(&commit, repo, id); + if (err) + break; - err = got_ref_open(&head_ref, repo, GOT_REF_HEAD); - if (err) - return err; + entry = alloc_commit_queue_entry(commit, id); + if (entry == NULL) { + err = got_error_from_errno(); + break; + } - err = got_ref_resolve(head_id, repo, head_ref); - got_ref_close(head_ref); - if (err) { - *head_id = NULL; - return err; + TAILQ_INSERT_TAIL(commits, entry, entry); } - return NULL; + return err; } static const struct got_error * -prepend_commits(int *ncommits, struct commit_queue *commits, - struct got_object_id *first_id, struct got_object_id *last_id, - int limit, struct got_repository *repo) +fetch_next_commit(struct commit_queue_entry **pentry, + struct commit_queue_entry *entry, struct commit_queue *commits, + struct got_commit_graph *graph, struct got_repository *repo) { const struct got_error *err = NULL; - struct got_object *last_obj = NULL; - struct got_commit_object *commit = NULL; - struct got_object_id *id = NULL; - struct commit_queue_entry *entry, *old_head_entry; + struct got_object_qid *qid; - *ncommits = 0; + *pentry = NULL; - err = got_object_open_as_commit(&commit, repo, first_id); - if (err) - goto done; - - err = got_object_open(&last_obj, repo, last_id); - if (err) - goto done; - if (got_object_get_type(last_obj) != GOT_OBJ_TYPE_COMMIT) { - err = got_error(GOT_ERR_OBJ_TYPE); - goto done; + /* Populate commit graph with entry's parent commits. */ + SIMPLEQ_FOREACH(qid, &entry->commit->parent_ids, entry) { + int nfetched; + err = got_commit_graph_fetch_commits_up_to(&nfetched, + graph, qid->id, repo); + if (err) + return err; } - id = got_object_id_dup(first_id); - if (id == NULL) { - err = got_error_from_errno(); - goto done; + /* Append outstanding commits to queue in graph sort order. */ + err = queue_commits(graph, commits, entry->id, repo); + if (err) { + if (err->code == GOT_ERR_ITER_COMPLETED) + err = NULL; + return err; } - entry = alloc_commit_queue_entry(commit, id); - if (entry == NULL) - return got_error_from_errno(); - - old_head_entry = TAILQ_FIRST(commits); - if (old_head_entry) - TAILQ_INSERT_BEFORE(old_head_entry, entry, entry); - else - TAILQ_INSERT_HEAD(commits, entry, entry); - - *ncommits = 1; - - /* - * Fetch parent commits. - * XXX If first and last commit aren't ancestrally related this loop - * we will keep iterating until a root commit is encountered. - */ - while (1) { - struct commit_queue_entry *pentry; - - err = fetch_parent_commit(&pentry, entry, repo); - if (err) - goto done; - if (pentry == NULL) - break; - - /* - * Fill up to old HEAD commit if commit queue was not empty. - * We must not leave a gap in history. - */ - if (old_head_entry && - got_object_id_cmp(pentry->id, old_head_entry->id) == 0) - break; - - TAILQ_INSERT_AFTER(commits, entry, pentry, entry); - (*ncommits)++; - if (*ncommits >= limit) - break; + /* Next entry to display should now be available. */ + *pentry = TAILQ_NEXT(entry, entry); + if (*pentry == NULL) + return got_error(GOT_ERR_NO_OBJ); - /* Fill up to last requested commit if queue was empty. */ - if (old_head_entry == NULL && - got_object_id_cmp(pentry->id, last_id) == 0) - break; - - entry = pentry; - } - -done: - if (last_obj) - got_object_close(last_obj); - return err; + return NULL; } static const struct got_error * -fetch_commits(struct commit_queue_entry **start_entry, - struct got_object_id *start_id, struct commit_queue *commits, - int limit, struct got_repository *repo) +get_head_commit_id(struct got_object_id **head_id, struct got_repository *repo) { - const struct got_error *err; - struct commit_queue_entry *entry; - int ncommits = 0; - struct got_object_id *head_id = NULL; + const struct got_error *err = NULL; + struct got_reference *head_ref; - *start_entry = NULL; + *head_id = NULL; - err = get_head_commit_id(&head_id, repo); + err = got_ref_open(&head_ref, repo, GOT_REF_HEAD); if (err) return err; - /* Prepend HEAD commit and all ancestors up to start commit. */ - err = prepend_commits(&ncommits, commits, head_id, start_id, limit, - repo); - if (err) + err = got_ref_resolve(head_id, repo, head_ref); + got_ref_close(head_ref); + if (err) { + *head_id = NULL; return err; - - if (got_object_id_cmp(head_id, start_id) == 0) - *start_entry = TAILQ_FIRST(commits); - else - *start_entry = TAILQ_LAST(commits, commit_queue); - - if (ncommits >= limit) - return NULL; - - /* Append more commits from start commit up to the requested limit. */ - entry = TAILQ_LAST(commits, commit_queue); - while (entry && ncommits < limit) { - struct commit_queue_entry *pentry; - - err = fetch_parent_commit(&pentry, entry, repo); - if (err) - break; - if (pentry) - TAILQ_INSERT_TAIL(commits, pentry, entry); - entry = pentry; - ncommits++; } - if (err) - *start_entry = NULL; - return err; + return NULL; } static const struct got_error * @@ -553,7 +472,8 @@ scroll_up(struct commit_queue_entry **first_displayed_ static const struct got_error * scroll_down(struct commit_queue_entry **first_displayed_entry, int maxscroll, struct commit_queue_entry *last_displayed_entry, - struct commit_queue *commits, struct got_repository *repo) + struct commit_queue *commits, struct got_commit_graph *graph, + struct got_repository *repo) { const struct got_error *err = NULL; struct commit_queue_entry *pentry; @@ -562,11 +482,10 @@ scroll_down(struct commit_queue_entry **first_displaye do { pentry = TAILQ_NEXT(last_displayed_entry, entry); if (pentry == NULL) { - err = fetch_parent_commit(&pentry, - last_displayed_entry, repo); + err = fetch_next_commit(&pentry, last_displayed_entry, + commits, graph, repo); if (err || pentry == NULL) break; - TAILQ_INSERT_TAIL(commits, pentry, entry); } last_displayed_entry = pentry; @@ -596,22 +515,17 @@ static const struct got_error * show_commit(struct commit_queue_entry *entry, struct got_repository *repo) { const struct got_error *err; - struct commit_queue_entry *pentry; struct got_object *obj1 = NULL, *obj2 = NULL; + struct got_object_qid *parent_id; err = got_object_open(&obj2, repo, entry->id); if (err) return err; - pentry = TAILQ_NEXT(entry, entry); - if (pentry == NULL) { - err = fetch_parent_commit(&pentry, entry, repo); + parent_id = SIMPLEQ_FIRST(&entry->commit->parent_ids); + if (parent_id) { + err = got_object_open(&obj1, repo, parent_id->id); if (err) - return err; - } - if (pentry) { - err = got_object_open(&obj1, repo, pentry->id); - if (err) goto done; } @@ -628,17 +542,15 @@ static const struct got_error * show_log_view(struct got_object_id *start_id, struct got_repository *repo) { const struct got_error *err = NULL; - struct got_object_id *id; - int ch, done = 0, selected = 0, nparents; + struct got_object_id *head_id = NULL; + int ch, done = 0, selected = 0, nparents, nfetched; + struct got_commit_graph *graph; struct commit_queue commits; + struct commit_queue_entry *entry = NULL; struct commit_queue_entry *first_displayed_entry = NULL; struct commit_queue_entry *last_displayed_entry = NULL; struct commit_queue_entry *selected_entry = NULL; - id = got_object_id_dup(start_id); - if (id == NULL) - return got_error_from_errno(); - if (tog_log_view.window == NULL) { tog_log_view.window = newwin(0, 0, 0, 0); if (tog_log_view.window == NULL) @@ -652,10 +564,47 @@ show_log_view(struct got_object_id *start_id, struct g } else show_panel(tog_log_view.panel); + err = get_head_commit_id(&head_id, repo); + if (err) + return err; + TAILQ_INIT(&commits); - err = fetch_commits(&first_displayed_entry, id, &commits, LINES, repo); + + err = got_commit_graph_open(&graph, head_id, repo); + if (err) + goto done; + + /* Populate commit graph with a sufficient number of commits. */ + err = got_commit_graph_fetch_commits_up_to(&nfetched, graph, start_id, + repo); + if (err) + goto done; + err = got_commit_graph_fetch_commits(&nfetched, graph, LINES, repo); if (err) + goto done; + + /* + * Open the initial batch of commits, sorted in commit graph order. + * We keep all commits open throughout the lifetime of the log view + * in order to avoid having to re-fetch commits from disk while + * updating the display. + */ + err = queue_commits(graph, &commits, head_id, repo); + if (err && err->code != GOT_ERR_ITER_COMPLETED) + goto done; + + /* Find entry corresponding to the first commit to display. */ + TAILQ_FOREACH(entry, &commits, entry) { + if (got_object_id_cmp(entry->id, start_id) == 0) { + first_displayed_entry = entry; + break; + } + } + if (first_displayed_entry == NULL) { + err = got_error(GOT_ERR_NO_OBJ); goto done; + } + while (!done) { err = draw_commits(&last_displayed_entry, &selected_entry, first_displayed_entry, selected, LINES); @@ -701,13 +650,15 @@ show_log_view(struct got_object_id *start_id, struct g break; } err = scroll_down(&first_displayed_entry, 1, - last_displayed_entry, &commits, repo); + last_displayed_entry, &commits, graph, + repo); if (err) goto done; break; case KEY_NPAGE: err = scroll_down(&first_displayed_entry, LINES, - last_displayed_entry, &commits, repo); + last_displayed_entry, &commits, graph, + repo); if (err) goto done; if (last_displayed_entry->commit->nparents > 0) @@ -734,6 +685,9 @@ show_log_view(struct got_object_id *start_id, struct g } } done: + free(head_id); + if (graph) + got_commit_graph_close(graph); free_commits(&commits); return err; }