revwalk: get closer to git

We had some home-grown logic to figure out which objects to show during
the revision walk, but it was rather inefficient, looking over the same
list multiple times to figure out when we had run out of interesting
commits. We now use the lists in a smarter way.

We also introduce the slop mechanism to determine when to stpo
looking. When we run out of interesting objects, we continue preparing
the walk for another 5 rounds in order to make it less likely that we
miss objects in situations with complex graphs.

5 files changed, 182 insertions, 47 deletions

diff --git a/src/commit_list.h b/src/commit_list.h
index a6967bcef..9746c2801 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 4815a1089..cc585ff4f 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 7559f72e9..89140bc54 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 14cf39afd..ab53ee780 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 f65ce6c59..6dd068a42 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;