commit - 31920504bebc2c8f3ffbad51600262290ac0dd8c
commit + 9ba79e04983cd5159d9153ecfd6da5ce29b1d6d6
blob - 57706b257defb1d2c159334cbf451d10288dbe2d
blob + 62e4d6ab75e22830b973ee01eaacf12b6d95eac7
--- got/got.c
+++ got/got.c
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
#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;
{ 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
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;
/* 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 *
{
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;
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) {
TAILQ_INSERT_BEFORE(n, node, entry);
break;
}
- }
+ n = TAILQ_NEXT(n, entry);
+ } while (n);
}
static const struct got_error *
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;
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;
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);
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;
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)
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;
}
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
#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))
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);
}
}
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 *
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;
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;
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;
}
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)
} 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);
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)
}
}
done:
+ free(head_id);
+ if (graph)
+ got_commit_graph_close(graph);
free_commits(&commits);
return err;
}
