thodg/got

diff --git a/got/got.c b/got/got.c
index 57706b2..62e4d6a 100644
--- a/got/got.c
+++ b/got/got.c
@@ -393,6 +393,10 @@ print_commits(struct got_object *root_obj, struct got_object_id *root_id,
 
 		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,
diff --git a/include/got_error.h b/include/got_error.h
index c833782..146ee74 100644
--- a/include/got_error.h
+++ b/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" },
 };
 
 /*
diff --git a/lib/commit_graph.c b/lib/commit_graph.c
index f9af65b..09035ff 100644
--- a/lib/commit_graph.c
+++ b/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_object_id *id)
 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 *wanted_id_added,
 		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;
 }
diff --git a/tog/tog.c b/tog/tog.c
index e9d830d..9bf2f9c 100644
--- a/tog/tog.c
+++ b/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;
-
-	/* Follow the first parent (TODO: handle merge commits). */
-	qid = SIMPLEQ_FIRST(&entry->commit->parent_ids);
-	if (qid == NULL)
-		return NULL;
+	struct commit_queue_entry *entry;
 
-	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;
-
-	*ncommits = 0;
+	struct got_object_qid *qid;
 
-	err = got_object_open_as_commit(&commit, repo, first_id);
-	if (err)
-		goto done;
+	*pentry = NULL;
 
-	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;
-
-		/* 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;
+	/* Next entry to display should now be available. */
+	*pentry = TAILQ_NEXT(entry, entry);
+	if (*pentry == NULL)
+		return got_error(GOT_ERR_NO_OBJ);
 
-		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_entry, int maxscroll,
 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_displayed_entry, int maxscroll,
 	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,21 +515,16 @@ 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);
-		if (err)
-			return err;
-	}
-	if (pentry) {
-		err = got_object_open(&obj1, repo, pentry->id);
+	parent_id = SIMPLEQ_FIRST(&entry->commit->parent_ids);
+	if (parent_id) {
+		err = got_object_open(&obj1, repo, parent_id->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 got_repository *repo)
 	} 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 got_repository *repo)
 					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 got_repository *repo)
 		}
 	}
 done:
+	free(head_id);
+	if (graph)
+		got_commit_graph_close(graph);
 	free_commits(&commits);
 	return err;
 }