thodg/libgit2

diff --git a/src/commit_list.h b/src/commit_list.h
index a6967bc..9746c28 100644
--- a/src/commit_list.h
+++ b/src/commit_list.h
@@ -28,6 +28,7 @@ typedef struct git_commit_list_node {
 			 uninteresting:1,
 			 topo_delay:1,
 			 parsed:1,
+			 added:1,
 			 flags : FLAG_BITS;
 
 	unsigned short in_degree;
diff --git a/src/revwalk.c b/src/revwalk.c
index 4815a10..cc585ff 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -86,7 +86,7 @@ static int mark_uninteresting(git_revwalk *walk, git_commit_list_node *commit)
 		tmp = git_array_pop(pending);
 		commit = tmp ? *tmp : NULL;
 
-	} while (commit != NULL && !interesting_arr(pending));
+	} while (commit != NULL && interesting_arr(pending));
 
 	git_array_clear(pending);
 
@@ -398,81 +398,194 @@ static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *
 	return *object_out ? 0 : GIT_ITEROVER;
 }
 
-
-static int interesting(git_pqueue *list)
+static int contains(git_pqueue *list, git_commit_list_node *node)
 {
 	size_t i;
 
 	for (i = 0; i < git_pqueue_size(list); i++) {
 		git_commit_list_node *commit = git_pqueue_get(list, i);
-		if (!commit->uninteresting)
+		if (commit == node)
 			return 1;
 	}
 
 	return 0;
 }
 
-static int contains(git_pqueue *list, git_commit_list_node *node)
+static void mark_parents_uninteresting(git_commit_list_node *commit)
 {
-	size_t i;
+	unsigned short i;
+	git_commit_list *parents = NULL;
 
-	for (i = 0; i < git_pqueue_size(list); i++) {
-		git_commit_list_node *commit = git_pqueue_get(list, i);
-		if (commit == node)
-			return 1;
-	}
+	for (i = 0; i < commit->out_degree; i++)
+		git_commit_list_insert(commit->parents[i], &parents);
 
-	return 0;
+
+	while (parents) {
+		git_commit_list_node *commit = git_commit_list_pop(&parents);
+
+		while (commit) {
+			if (commit->uninteresting)
+				break;
+
+			commit->uninteresting = 1;
+			/*
+			 * If we've reached this commit some other way
+			 * already, we need to mark its parents uninteresting
+			 * as well.
+			 */
+			if (!commit->parents)
+				break;
+
+			for (i = 0; i < commit->out_degree; i++)
+				git_commit_list_insert(commit->parents[i], &parents);
+			commit = commit->parents[0];
+		}
+	}
 }
 
-static int premark_uninteresting(git_revwalk *walk)
+static int add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
 {
-	int error = 0;
 	unsigned short i;
-	git_pqueue q;
-	git_commit_list *list;
-	git_commit_list_node *commit, *parent;
+	int error;
 
-	if ((error = git_pqueue_init(&q, 0, 8, git_commit_list_time_cmp)) < 0)
-		return error;
+	if (commit->added)
+		return 0;
 
-	for (list = walk->user_input; list; list = list->next) {
-		if ((error = git_commit_list_parse(walk, list->item)) < 0)
-			goto cleanup;
+	commit->added = 1;
+
+	/* TODO: add the insertion callback here as well */
 
-		if ((error = git_pqueue_insert(&q, list->item)) < 0)
-			goto cleanup;
+	/*
+	 * Go full on in the uninteresting case as we want to include
+	 * as many of these as we can.
+	 *
+	 * Usually we haven't parsed the parent of a parent, but if we
+	 * have it we reached it via other means so we want to mark
+	 * its parents recursively too.
+	 */
+	if (commit->uninteresting) {
+		for (i = 0; i < commit->out_degree; i++) {
+			git_commit_list_node *p = commit->parents[i];
+			p->uninteresting = 1;
+
+			/* git does it gently here, but we don't like missing objects */
+			if ((error = git_commit_list_parse(walk, p)) < 0)
+				return error;
+
+			if (p->parents)
+				mark_parents_uninteresting(p);
+
+			p->seen = 1;
+			git_commit_list_insert_by_date(p, list);
+		}
+
+		return 0;
 	}
 
-	while (interesting(&q)) {
-		commit = git_pqueue_pop(&q);
+	/*
+	 * Now on to what we do if the commit is indeed
+	 * interesting. Here we do want things like first-parent take
+	 * effect as this is what we'll be showing.
+	 */
+	for (i = 0; i < commit->out_degree; i++) {
+		git_commit_list_node *p = commit->parents[i];
 
-		for (i = 0; i < commit->out_degree; i++) {
-			parent = commit->parents[i];
+		if ((error = git_commit_list_parse(walk, p)) < 0)
+			return error;
 
-			if ((error = git_commit_list_parse(walk, parent)) < 0)
-				goto cleanup;
+		if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
+				continue;
 
-			if (commit->uninteresting)
-				parent->uninteresting = 1;
+		if (!p->seen) {
+			p->seen = 1;
+			git_commit_list_insert_by_date(p, list);
+		}
+
+		if (walk->first_parent)
+			break;
+	}
+	return 0;
+}
 
-			if (contains(&q, parent))
+static int everybody_uninteresting(git_commit_list *orig)
+{
+	git_commit_list *list = orig;
+
+	while (list) {
+		git_commit_list_node *commit = list->item;
+		list = list->next;
+		if (commit->uninteresting)
+			continue;
+
+		return 0;
+	}
+
+	return 1;
+}
+
+/* How many unintersting commits we want to look at after we run out of interesting ones */
+#define SLOP 5
+
+static int still_interesting(git_commit_list *list, int64_t time, int slop)
+{
+	/* The empty list is pretty boring */
+	if (!list)
+		return 0;
+
+	/*
+	 * If the destination list has commits with an earlier date
+	 * than our source we want to continue looking.
+	 */
+	if (time <= list->item->time)
+		return SLOP;
+
+	/* If we find interesting commits, we reset the slop count */
+	if (!everybody_uninteresting(list))
+		return SLOP;
+
+	/* Everything's uninteresting, reduce the count */
+	return slop - 1;
+}
+
+static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits)
+{
+	int error, slop = SLOP;
+	int64_t time = ~0ll;
+	git_commit_list *list = commits;
+	git_commit_list *newlist = NULL;
+	git_commit_list **p = &newlist;
+
+	while (list) {
+		git_commit_list_node *commit = git_commit_list_pop(&list);
+
+		if ((error = add_parents_to_list(walk, commit, &list)) < 0)
+			return error;
+
+		if (commit->uninteresting) {
+			mark_parents_uninteresting(commit);
+
+			slop = still_interesting(list, time, slop);
+			if (slop)
 				continue;
 
-			if ((error = git_pqueue_insert(&q, parent)) < 0)
-				goto cleanup;
+			break;
 		}
+
+		if (!commit->uninteresting && walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
+				continue;
+
+		time = commit->time;
+		p = &git_commit_list_insert(commit, p)->next;
 	}
 
-cleanup:
-	git_pqueue_free(&q);
-	return error;
+	*out = newlist;
+	return 0;
 }
 
 static int prepare_walk(git_revwalk *walk)
 {
 	int error;
-	git_commit_list *list;
+	git_commit_list *list, *commits = NULL;
 	git_commit_list_node *next;
 
 	/* If there were no pushes, we know that the walk is already over */
@@ -481,12 +594,29 @@ static int prepare_walk(git_revwalk *walk)
 		return GIT_ITEROVER;
 	}
 
-	if (walk->did_hide && (error = premark_uninteresting(walk)) < 0)
+	for (list = walk->user_input; list; list = list->next) {
+		git_commit_list_node *commit = list->item;
+		if ((error = git_commit_list_parse(walk, commit)) < 0)
+			return error;
+
+		if (commit->uninteresting)
+			mark_parents_uninteresting(commit);
+
+		if (!commit->seen) {
+			commit->seen = 1;
+			git_commit_list_insert(commit, &commits);
+		}
+	}
+
+	if ((error = limit_list(&commits, walk, commits)) < 0)
 		return error;
 
-	for (list = walk->user_input; list; list = list->next) {
-		if (process_commit(walk, list->item, list->item->uninteresting) < 0)
-			return -1;
+	for (list = commits; list; list = list->next) {
+		if (list->item->uninteresting)
+			continue;
+
+		if ((error = walk->enqueue(walk, list->item)) < 0)
+			return error;
 	}
 
 
@@ -632,6 +762,7 @@ void git_revwalk_reset(git_revwalk *walk)
 		commit->in_degree = 0;
 		commit->topo_delay = 0;
 		commit->uninteresting = 0;
+		commit->added = 0;
 		commit->flags = 0;
 		});
 
diff --git a/tests/revwalk/basic.c b/tests/revwalk/basic.c
index 7559f72..89140bc 100644
--- a/tests/revwalk/basic.c
+++ b/tests/revwalk/basic.c
@@ -38,8 +38,9 @@ static const int commit_sorting_time_reverse[][6] = {
 	{4, 5, 2, 1, 3, 0}
 };
 
+/* This is specified unsorted, so both combinations are possible */
 static const int commit_sorting_segment[][6] = {
-	{1, 2, -1, -1, -1, -1}
+	{1, 2, -1, -1, -1, -1}, {2, 1, -1, -1, -1, -1}
 };
 
 #define commit_count 6
@@ -155,9 +156,8 @@ void test_revwalk_basic__glob_heads(void)
 
 	cl_git_pass(git_revwalk_push_glob(_walk, "heads"));
 
-	while (git_revwalk_next(&oid, _walk) == 0) {
+	while (git_revwalk_next(&oid, _walk) == 0)
 		i++;
-	}
 
 	/* git log --branches --oneline | wc -l => 14 */
 	cl_assert_equal_i(i, 14);
@@ -338,7 +338,7 @@ void test_revwalk_basic__push_range(void)
 	git_revwalk_reset(_walk);
 	git_revwalk_sorting(_walk, 0);
 	cl_git_pass(git_revwalk_push_range(_walk, "9fd738e~2..9fd738e"));
-	cl_git_pass(test_walk_only(_walk, commit_sorting_segment, 1));
+	cl_git_pass(test_walk_only(_walk, commit_sorting_segment, 2));
 }
 
 void test_revwalk_basic__push_mixed(void)
diff --git a/tests/revwalk/hidecb.c b/tests/revwalk/hidecb.c
index 14cf39a..ab53ee7 100644
--- a/tests/revwalk/hidecb.c
+++ b/tests/revwalk/hidecb.c
@@ -158,6 +158,7 @@ void test_revwalk_hidecb__hide_some_commits(void)
 
 	cl_git_pass(git_revwalk_new(&walk, _repo));
 	cl_git_pass(git_revwalk_push(walk, &_head_id));
+	git_revwalk_sorting(walk, GIT_SORT_TOPOLOGICAL | GIT_SORT_TIME);
 
 	/* Add hide callback */
 	cl_git_pass(git_revwalk_add_hide_cb(walk, hide_commit_cb, NULL));
@@ -182,6 +183,7 @@ void test_revwalk_hidecb__test_payload(void)
 
 	cl_git_pass(git_revwalk_new(&walk, _repo));
 	cl_git_pass(git_revwalk_push(walk, &_head_id));
+	git_revwalk_sorting(walk, GIT_SORT_TOPOLOGICAL | GIT_SORT_TIME);
 
 	/* Add hide callback, pass id of parent of initial commit as payload data */
 	cl_git_pass(git_revwalk_add_hide_cb(walk, hide_commit_use_payload_cb, &commit_ids[5]));
diff --git a/tests/revwalk/simplify.c b/tests/revwalk/simplify.c
index f65ce6c..6dd068a 100644
--- a/tests/revwalk/simplify.c
+++ b/tests/revwalk/simplify.c
@@ -40,6 +40,7 @@ void test_revwalk_simplify__first_parent(void)
 
 	git_oid_fromstr(&id, commit_head);
 	cl_git_pass(git_revwalk_push(walk, &id));
+	git_revwalk_sorting(walk, GIT_SORT_TOPOLOGICAL);
 	git_revwalk_simplify_first_parent(walk);
 
 	i = 0;