Merge pull request #3921 from libgit2/cmn/walk-limit-enough

Improve revision walk preparation logic

28 files changed, 407 insertions, 205 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index e4fd68dfe..dae86de4a 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -15,6 +15,8 @@ v0.24 + 1
 
 * Support for reading and writing git index v4 files
 
+* Improve the performance of the revwalk and bring us closer to git's code.
+
 ### API additions
 
 * You can now get the user-agent used by libgit2 using the
diff --git a/include/git2/revwalk.h b/include/git2/revwalk.h
index 2cc00536e..d9376ceea 100644
--- a/include/git2/revwalk.h
+++ b/include/git2/revwalk.h
@@ -25,17 +25,15 @@ GIT_BEGIN_DECL
  */
 typedef enum {
 	/**
-	 * Sort the repository contents in no particular ordering;
-	 * this sorting is arbitrary, implementation-specific
-	 * and subject to change at any time.
+	 * Sort the output with the same default time-order method from git.
 	 * This is the default sorting for new walkers.
 	 */
 	GIT_SORT_NONE = 0,
 
 	/**
-	 * Sort the repository contents in topological order
-	 * (parents before children); this sorting mode
-	 * can be combined with time sorting.
+	 * Sort the repository contents in topological order (parents before
+	 * children); this sorting mode can be combined with time sorting to
+	 * produce git's "time-order".
 	 */
 	GIT_SORT_TOPOLOGICAL = 1 << 0,
 
diff --git a/src/commit_list.c b/src/commit_list.c
index 28948c88b..a1681ffae 100644
--- a/src/commit_list.c
+++ b/src/commit_list.c
@@ -13,10 +13,15 @@
 
 int git_commit_list_time_cmp(const void *a, const void *b)
 {
-	const git_commit_list_node *commit_a = a;
-	const git_commit_list_node *commit_b = b;
+	int64_t time_a = ((git_commit_list_node *) a)->time;
+	int64_t time_b = ((git_commit_list_node *) b)->time;
 
-	return (commit_a->time < commit_b->time);
+	if (time_a < time_b)
+		return 1;
+	if (time_a > time_b)
+		return -1;
+
+	return 0;
 }
 
 git_commit_list *git_commit_list_insert(git_commit_list_node *item, git_commit_list **list_p)
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/pqueue.c b/src/pqueue.c
index 54a60ca04..8cfc4390f 100644
--- a/src/pqueue.c
+++ b/src/pqueue.c
@@ -93,7 +93,7 @@ int git_pqueue_insert(git_pqueue *pq, void *item)
 		(void)git_pqueue_pop(pq);
 	}
 
-	if (!(error = git_vector_insert(pq, item)))
+	if (!(error = git_vector_insert(pq, item)) && pq->_cmp)
 		pqueue_up(pq, pq->length - 1);
 
 	return error;
@@ -101,9 +101,15 @@ int git_pqueue_insert(git_pqueue *pq, void *item)
 
 void *git_pqueue_pop(git_pqueue *pq)
 {
-	void *rval = git_pqueue_get(pq, 0);
+	void *rval;
 
-	if (git_pqueue_size(pq) > 1) {
+	if (!pq->_cmp) {
+		rval = git_vector_last(pq);
+	} else {
+		rval = git_pqueue_get(pq, 0);
+	}
+
+	if (git_pqueue_size(pq) > 1 && pq->_cmp) {
 		/* move last item to top of heap, shrink, and push item down */
 		pq->contents[0] = git_vector_last(pq);
 		git_vector_pop(pq);
diff --git a/src/pqueue.h b/src/pqueue.h
index da7b74edf..76b14919e 100644
--- a/src/pqueue.h
+++ b/src/pqueue.h
@@ -35,6 +35,7 @@ extern int git_pqueue_init(
 #define git_pqueue_clear git_vector_clear
 #define git_pqueue_size  git_vector_length
 #define git_pqueue_get   git_vector_get
+#define git_pqueue_reverse git_vector_reverse
 
 /**
  * Insert a new item into the queue
diff --git a/src/rebase.c b/src/rebase.c
index 470e62a23..e86312e7e 100644
--- a/src/rebase.c
+++ b/src/rebase.c
@@ -586,7 +586,7 @@ static int rebase_init_operations(
 		(error = git_revwalk_hide(revwalk, git_annotated_commit_id(upstream))) < 0)
 		goto done;
 
-	git_revwalk_sorting(revwalk, GIT_SORT_REVERSE | GIT_SORT_TIME);
+	git_revwalk_sorting(revwalk, GIT_SORT_REVERSE);
 
 	while ((error = git_revwalk_next(&id, revwalk)) == 0) {
 		if ((error = git_commit_lookup(&commit, repo, &id)) < 0)
diff --git a/src/revwalk.c b/src/revwalk.c
index 4815a1089..0ada5870a 100644
--- a/src/revwalk.c
+++ b/src/revwalk.c
@@ -13,6 +13,7 @@
 #include "revwalk.h"
 #include "git2/revparse.h"
 #include "merge.h"
+#include "vector.h"
 
 GIT__USE_OIDMAP
 
@@ -41,97 +42,6 @@ git_commit_list_node *git_revwalk__commit_lookup(
 	return commit;
 }
 
-typedef git_array_t(git_commit_list_node*) commit_list_node_array;
-
-static bool interesting_arr(commit_list_node_array arr)
-{
-	git_commit_list_node **n;
-	size_t i = 0, size;
-
-	size = git_array_size(arr);
-	for (i = 0; i < size; i++) {
-		n = git_array_get(arr, i);
-		if (!*n)
-			break;
-
-		if (!(*n)->uninteresting)
-			return true;
-	}
-
-	return false;
-}
-
-static int mark_uninteresting(git_revwalk *walk, git_commit_list_node *commit)
-{
-	int error;
-	unsigned short i;
-	commit_list_node_array pending = GIT_ARRAY_INIT;
-	git_commit_list_node **tmp;
-
-	assert(commit);
-
-	do {
-		commit->uninteresting = 1;
-
-		if ((error = git_commit_list_parse(walk, commit)) < 0)
-			return error;
-
-		for (i = 0; i < commit->out_degree; ++i)
-			if (!commit->parents[i]->uninteresting) {
-				git_commit_list_node **node = git_array_alloc(pending);
-				GITERR_CHECK_ALLOC(node);
-				*node = commit->parents[i];
-			}
-
-		tmp = git_array_pop(pending);
-		commit = tmp ? *tmp : NULL;
-
-	} while (commit != NULL && !interesting_arr(pending));
-
-	git_array_clear(pending);
-
-	return 0;
-}
-
-static int process_commit(git_revwalk *walk, git_commit_list_node *commit, int hide)
-{
-	int error;
-
-	if (!hide && walk->hide_cb)
-		hide = walk->hide_cb(&commit->oid, walk->hide_cb_payload);
-
-	if (hide && mark_uninteresting(walk, commit) < 0)
-		return -1;
-
-	if (commit->seen)
-		return 0;
-
-	commit->seen = 1;
-
-	if ((error = git_commit_list_parse(walk, commit)) < 0)
-		return error;
-
-	if (!hide)
-		return walk->enqueue(walk, commit);
-
-	return 0;
-}
-
-static int process_commit_parents(git_revwalk *walk, git_commit_list_node *commit)
-{
-	unsigned short i, max;
-	int error = 0;
-
-	max = commit->out_degree;
-	if (walk->first_parent && commit->out_degree)
-		max = 1;
-
-	for (i = 0; i < max && !error; ++i)
-		error = process_commit(walk, commit->parents[i], commit->uninteresting);
-
-	return error;
-}
-
 static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting, int from_glob)
 {
 	git_oid commit_id;
@@ -321,17 +231,12 @@ static int revwalk_enqueue_unsorted(git_revwalk *walk, git_commit_list_node *com
 
 static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk *walk)
 {
-	int error;
 	git_commit_list_node *next;
 
-	while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL)
-		if (!next->uninteresting) {
-			if ((error = process_commit_parents(walk, next)) < 0)
-				return error;
-
-			*object_out = next;
-			return 0;
-		}
+	if ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
+		*object_out = next;
+		return 0;
+	}
 
 	giterr_clear();
 	return GIT_ITEROVER;
@@ -339,17 +244,15 @@ static int revwalk_next_timesort(git_commit_list_node **object_out, git_revwalk
 
 static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk *walk)
 {
-	int error;
 	git_commit_list_node *next;
 
-	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL)
+	while ((next = git_commit_list_pop(&walk->iterator_rand)) != NULL) {
+		/* Some commits might become uninteresting after being added to the list */
 		if (!next->uninteresting) {
-			if ((error = process_commit_parents(walk, next)) < 0)
-				return error;
-
 			*object_out = next;
 			return 0;
 		}
+	}
 
 	giterr_clear();
 	return GIT_ITEROVER;
@@ -358,121 +261,283 @@ static int revwalk_next_unsorted(git_commit_list_node **object_out, git_revwalk
 static int revwalk_next_toposort(git_commit_list_node **object_out, git_revwalk *walk)
 {
 	git_commit_list_node *next;
-	unsigned short i, max;
 
-	for (;;) {
-		next = git_commit_list_pop(&walk->iterator_topo);
-		if (next == NULL) {
-			giterr_clear();
-			return GIT_ITEROVER;
+	while ((next = git_commit_list_pop(&walk->iterator_topo)) != NULL) {
+		/* Some commits might become uninteresting after being added to the list */
+		if (!next->uninteresting) {
+			*object_out = next;
+			return 0;
 		}
+	}
 
-		if (next->in_degree > 0) {
-			next->topo_delay = 1;
-			continue;
+	giterr_clear();
+	return GIT_ITEROVER;
+}
+
+static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
+{
+	*object_out = git_commit_list_pop(&walk->iterator_reverse);
+	return *object_out ? 0 : GIT_ITEROVER;
+}
+
+static void mark_parents_uninteresting(git_commit_list_node *commit)
+{
+	unsigned short i;
+	git_commit_list *parents = NULL;
+
+	for (i = 0; i < commit->out_degree; i++)
+		git_commit_list_insert(commit->parents[i], &parents);
+
+
+	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 add_parents_to_list(git_revwalk *walk, git_commit_list_node *commit, git_commit_list **list)
+{
+	unsigned short i;
+	int error;
 
-		max = next->out_degree;
-		if (walk->first_parent && next->out_degree)
-			max = 1;
+	if (commit->added)
+		return 0;
 
-		for (i = 0; i < max; ++i) {
-			git_commit_list_node *parent = next->parents[i];
+	commit->added = 1;
+
+	/*
+	 * 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;
 
-			if (--parent->in_degree == 0 && parent->topo_delay) {
-				parent->topo_delay = 0;
-				if (git_commit_list_insert(parent, &walk->iterator_topo) == NULL)
-					return -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);
 		}
 
-		*object_out = next;
 		return 0;
 	}
+
+	/*
+	 * 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];
+
+		if ((error = git_commit_list_parse(walk, p)) < 0)
+			return error;
+
+		if (walk->hide_cb && walk->hide_cb(&p->oid, walk->hide_cb_payload))
+			continue;
+
+		if (!p->seen) {
+			p->seen = 1;
+			git_commit_list_insert_by_date(p, list);
+		}
+
+		if (walk->first_parent)
+			break;
+	}
+	return 0;
 }
 
-static int revwalk_next_reverse(git_commit_list_node **object_out, git_revwalk *walk)
+static int everybody_uninteresting(git_commit_list *orig)
 {
-	*object_out = git_commit_list_pop(&walk->iterator_reverse);
-	return *object_out ? 0 : GIT_ITEROVER;
+	git_commit_list *list = orig;
+
+	while (list) {
+		git_commit_list_node *commit = list->item;
+		list = list->next;
+		if (!commit->uninteresting)
+			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 interesting(git_pqueue *list)
+static int still_interesting(git_commit_list *list, int64_t time, int slop)
 {
-	size_t i;
+	/* The empty list is pretty boring */
+	if (!list)
+		return 0;
 
-	for (i = 0; i < git_pqueue_size(list); i++) {
-		git_commit_list_node *commit = git_pqueue_get(list, i);
-		if (!commit->uninteresting)
-			return 1;
-	}
+	/*
+	 * 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;
 
-	return 0;
+	/* 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 contains(git_pqueue *list, git_commit_list_node *node)
+static int limit_list(git_commit_list **out, git_revwalk *walk, git_commit_list *commits)
 {
-	size_t i;
+	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;
+
+			break;
+		}
+
+		if (!commit->uninteresting && walk->hide_cb && walk->hide_cb(&commit->oid, walk->hide_cb_payload))
+				continue;
 
-	for (i = 0; i < git_pqueue_size(list); i++) {
-		git_commit_list_node *commit = git_pqueue_get(list, i);
-		if (commit == node)
-			return 1;
+		time = commit->time;
+		p = &git_commit_list_insert(commit, p)->next;
 	}
 
+	git_commit_list_free(&list);
+	*out = newlist;
 	return 0;
 }
 
-static int premark_uninteresting(git_revwalk *walk)
+static int sort_in_topological_order(git_commit_list **out, git_revwalk *walk, git_commit_list *list)
 {
-	int error = 0;
+	git_commit_list *ll = NULL, *newlist, **pptr;
+	git_commit_list_node *next;
+	git_pqueue queue;
+	git_vector_cmp queue_cmp = NULL;
 	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 (walk->sorting & GIT_SORT_TIME)
+		queue_cmp = git_commit_list_time_cmp;
 
-	for (list = walk->user_input; list; list = list->next) {
-		if ((error = git_commit_list_parse(walk, list->item)) < 0)
-			goto cleanup;
+	if ((error = git_pqueue_init(&queue, 0, 8, queue_cmp)))
+		return error;
 
-		if ((error = git_pqueue_insert(&q, list->item)) < 0)
-			goto cleanup;
+	/*
+	 * Start by resetting the in-degree to 1 for the commits in
+	 * our list. We want to go through this list again, so we
+	 * store it in the commit list as we extract it from the lower
+	 * machinery.
+	 */
+	for (ll = list; ll; ll = ll->next) {
+		ll->item->in_degree = 1;
 	}
 
-	while (interesting(&q)) {
-		commit = git_pqueue_pop(&q);
-
-		for (i = 0; i < commit->out_degree; i++) {
-			parent = commit->parents[i];
+	/*
+	 * Count up how many children each commit has. We limit
+	 * ourselves to those commits in the original list (in-degree
+	 * of 1) avoiding setting it for any parent that was hidden.
+	 */
+	for(ll = list; ll; ll = ll->next) {
+		for (i = 0; i < ll->item->out_degree; ++i) {
+			git_commit_list_node *parent = ll->item->parents[i];
+			if (parent->in_degree)
+				parent->in_degree++;
+		}
+	}
 
-			if ((error = git_commit_list_parse(walk, parent)) < 0)
+	/*
+	 * Now we find the tips i.e. those not reachable from any other node
+	 * i.e. those which still have an in-degree of 1.
+	 */
+	for(ll = list; ll; ll = ll->next) {
+		if (ll->item->in_degree == 1) {
+			if ((error = git_pqueue_insert(&queue, ll->item)))
 				goto cleanup;
+		}
+	}
+
+	/*
+	 * We need to output the tips in the order that they came out of the
+	 * traversal, so if we're not doing time-sorting, we need to reverse the
+	 * pqueue in order to get them to come out as we inserted them.
+	 */
+	if ((walk->sorting & GIT_SORT_TIME) == 0)
+		git_pqueue_reverse(&queue);
 
-			if (commit->uninteresting)
-				parent->uninteresting = 1;
 
-			if (contains(&q, parent))
+	pptr = &newlist;
+	newlist = NULL;
+	while ((next = git_pqueue_pop(&queue)) != NULL) {
+		for (i = 0; i < next->out_degree; ++i) {
+			git_commit_list_node *parent = next->parents[i];
+			if (parent->in_degree == 0)
 				continue;
 
-			if ((error = git_pqueue_insert(&q, parent)) < 0)
-				goto cleanup;
+			if (--parent->in_degree == 1) {
+				if ((error = git_pqueue_insert(&queue, parent)))
+					goto cleanup;
+			}
 		}
+
+		/* All the children of 'item' have been emitted (since we got to it via the priority queue) */
+		next->in_degree = 0;
+
+		pptr = &git_commit_list_insert(next, pptr)->next;
 	}
 
+	*out = newlist;
+	error = 0;
+
 cleanup:
-	git_pqueue_free(&q);
+	git_pqueue_free(&queue);
 	return error;
 }
 
 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,32 +546,42 @@ static int prepare_walk(git_revwalk *walk)
 		return GIT_ITEROVER;
 	}
 
-	if (walk->did_hide && (error = premark_uninteresting(walk)) < 0)
-		return error;
-
 	for (list = walk->user_input; list; list = list->next) {
-		if (process_commit(walk, list->item, list->item->uninteresting) < 0)
-			return -1;
-	}
+		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 (walk->sorting & GIT_SORT_TOPOLOGICAL) {
-		unsigned short i;
+		if (!commit->seen) {
+			commit->seen = 1;
+			git_commit_list_insert(commit, &commits);
+		}
+	}
 
-		while ((error = walk->get_next(&next, walk)) == 0) {
-			for (i = 0; i < next->out_degree; ++i) {
-				git_commit_list_node *parent = next->parents[i];
-				parent->in_degree++;
-			}
+	if ((error = limit_list(&commits, walk, commits)) < 0)
+		return error;
 
-			if (git_commit_list_insert(next, &walk->iterator_topo) == NULL)
-				return -1;
-		}
+	if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
+		error = sort_in_topological_order(&walk->iterator_topo, walk, commits);
+		git_commit_list_free(&commits);
 
-		if (error != GIT_ITEROVER)
+		if (error < 0)
 			return error;
 
 		walk->get_next = &revwalk_next_toposort;
+	} else if (walk->sorting & GIT_SORT_TIME) {
+		for (list = commits; list && !error; list = list->next)
+			error = walk->enqueue(walk, list->item);
+
+		git_commit_list_free(&commits);
+
+		if (error < 0)
+			return error;
+	} else {
+		walk->iterator_rand = commits;
+		walk->get_next = revwalk_next_unsorted;
 	}
 
 	if (walk->sorting & GIT_SORT_REVERSE) {
@@ -632,6 +707,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/src/vector.c b/src/vector.c
index db1dcf89a..baec8036f 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -401,3 +401,19 @@ int git_vector_verify_sorted(const git_vector *v)
 
 	return 0;
 }
+
+void git_vector_reverse(git_vector *v)
+{
+	size_t a, b;
+
+	a = 0;
+	b = v->length - 1;
+
+	while (a < b) {
+		void *tmp = v->contents[a];
+		v->contents[a] = v->contents[b];
+		v->contents[b] = tmp;
+		a++;
+		b--;
+	}
+}
diff --git a/src/vector.h b/src/vector.h
index 96d149e16..cc4c314d5 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -118,4 +118,9 @@ GIT_INLINE(void) git_vector_set_cmp(git_vector *v, git_vector_cmp cmp)
 /* Just use this in tests, not for realz. returns -1 if not sorted */
 int git_vector_verify_sorted(const git_vector *v);
 
+/**
+ * Reverse the vector in-place.
+ */
+void git_vector_reverse(git_vector *v);
+
 #endif
diff --git a/tests/core/vector.c b/tests/core/vector.c
index c351655a7..336254cce 100644
--- a/tests/core/vector.c
+++ b/tests/core/vector.c
@@ -376,3 +376,32 @@ void test_core_vector__grow_and_shrink(void)
 
 	git_vector_free(&x);
 }
+
+void test_core_vector__reverse(void)
+{
+	git_vector v = GIT_VECTOR_INIT;
+	size_t i;
+
+	void *in1[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3};
+	void *out1[] = {(void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
+
+	void *in2[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3, (void *) 0x4};
+	void *out2[] = {(void *) 0x4, (void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
+
+	for (i = 0; i < 4; i++)
+		cl_git_pass(git_vector_insert(&v, in1[i]));
+
+	git_vector_reverse(&v);
+
+	for (i = 0; i < 4; i++)
+		cl_assert_equal_p(out1[i], git_vector_get(&v, i));
+
+	git_vector_clear(&v);
+	for (i = 0; i < 5; i++)
+		cl_git_pass(git_vector_insert(&v, in2[i]));
+
+	git_vector_reverse(&v);
+
+	for (i = 0; i < 5; i++)
+		cl_assert_equal_p(out2[i], git_vector_get(&v, i));
+}
diff --git a/tests/odb/foreach.c b/tests/odb/foreach.c
index 12b81b4f1..42d706467 100644
--- a/tests/odb/foreach.c
+++ b/tests/odb/foreach.c
@@ -28,8 +28,8 @@ static int foreach_cb(const git_oid *oid, void *data)
 
 /*
  * $ git --git-dir tests/resources/testrepo.git count-objects --verbose
- * count: 47
- * size: 4
+ * count: 60
+ * size: 240
  * in-pack: 1640
  * packs: 3
  * size-pack: 425
@@ -44,7 +44,7 @@ void test_odb_foreach__foreach(void)
 	git_repository_odb(&_odb, _repo);
 
 	cl_git_pass(git_odb_foreach(_odb, foreach_cb, &nobj));
-	cl_assert_equal_i(47 + 1640, nobj); /* count + in-pack */
+	cl_assert_equal_i(60 + 1640, nobj); /* count + in-pack */
 }
 
 void test_odb_foreach__one_pack(void)
@@ -118,7 +118,7 @@ void test_odb_foreach__files_in_objects_dir(void)
 
 	cl_git_pass(git_repository_odb(&odb, repo));
 	cl_git_pass(git_odb_foreach(odb, foreach_cb, &nobj));
-	cl_assert_equal_i(47 + 1640, nobj); /* count + in-pack */
+	cl_assert_equal_i(60 + 1640, nobj); /* count + in-pack */
 
 	git_odb_free(odb);
 	git_repository_free(repo);
diff --git a/tests/resources/testrepo.git/objects/43/da5ec3274dd061df152ff5e69853d562b01842 b/tests/resources/testrepo.git/objects/43/da5ec3274dd061df152ff5e69853d562b01842
new file mode 100644
index 000000000..298feece4
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/43/da5ec3274dd061df152ff5e69853d562b01842
@@ -0,0 +1,2 @@
+x
-�]jC!F��*f)�]��@�
+�
�8��Z��ۯi�v��>����Os0�B%s)f���M�l�h�V4�5������	�&4ѕ@:�D�)oIr`���$�L����Y��w�s¥F��������g������`�$��b����
o�;������U|����zO��u}��/�._���ׁ~��
��J
\ No newline at end of file
diff --git a/tests/resources/testrepo.git/objects/43/e968a905a821532069bb413801d35b200631cf b/tests/resources/testrepo.git/objects/43/e968a905a821532069bb413801d35b200631cf
new file mode 100644
index 000000000..ec04abf68
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/43/e968a905a821532069bb413801d35b200631cf
@@ -0,0 +1,4 @@
+x
��K
+1]�}
%�N'
7�����8����
+���\�u�5zc���
6��8�b,��D�2�0�'�Q�b㭃�@ҩ�R��Q�[��94�)�
�q�smp+��
+�纾�g�G����=�r]/��3�((��tR�a������>���E�
\ No newline at end of file
diff --git a/tests/resources/testrepo.git/objects/5d/0f8f7891e872d284beef38254882dc879b2602 b/tests/resources/testrepo.git/objects/5d/0f8f7891e872d284beef38254882dc879b2602
new file mode 100644
index 000000000..7a22451ed
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/5d/0f8f7891e872d284beef38254882dc879b2602
diff --git a/tests/resources/testrepo.git/objects/5f/34cd6e3285089647165983482cf90873d50940 b/tests/resources/testrepo.git/objects/5f/34cd6e3285089647165983482cf90873d50940
new file mode 100644
index 000000000..b1df3bdd5
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/5f/34cd6e3285089647165983482cf90873d50940
diff --git a/tests/resources/testrepo.git/objects/8e/73b769e97678d684b809b163bebdae2911720f b/tests/resources/testrepo.git/objects/8e/73b769e97678d684b809b163bebdae2911720f
new file mode 100644
index 000000000..d75977a25
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/8e/73b769e97678d684b809b163bebdae2911720f
@@ -0,0 +1,2 @@
+x
���j�0�S�)��*a���㚔��+��l8[A������
�
33������y�M$�m�*�� �$q��G?Y�A�5<
��t����8r���5�����7nD#.d��)~�N�0˄�)R,�|,h��jQ*t������C~�	|�u���zҧ�ݗ>����
+ƒ�d����8��\�����S�]!7������s�,[�P2�fw^�
\ No newline at end of file
diff --git a/tests/resources/testrepo.git/objects/b2/04707bbc546a1a770ef6ced37c7089cc3bfe6b b/tests/resources/testrepo.git/objects/b2/04707bbc546a1a770ef6ced37c7089cc3bfe6b
new file mode 100644
index 000000000..f9ec61c1e
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/b2/04707bbc546a1a770ef6ced37c7089cc3bfe6b
@@ -0,0 +1,2 @@
+x
-�]��0�}�)t�.�QJ),{���-7��^\�^�ҷA�7(���F�W�"��A%�ɣy���g�iTI��d�?_�����#��[��(-�D�0wdp����R*\Bi
~�����[���;�|m�a�djRj���a�
+���k��R�s���t��m��G"7��{�~��LD�
\ No newline at end of file
diff --git a/tests/resources/testrepo.git/objects/b2/35959d89084af8d3544fbdf675e47944f86524 b/tests/resources/testrepo.git/objects/b2/35959d89084af8d3544fbdf675e47944f86524
new file mode 100644
index 000000000..7d563dbd3
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/b2/35959d89084af8d3544fbdf675e47944f86524
diff --git a/tests/resources/testrepo.git/objects/b9/1e763008b10db366442469339f90a2b8400d0a b/tests/resources/testrepo.git/objects/b9/1e763008b10db366442469339f90a2b8400d0a
new file mode 100644
index 000000000..7bab59be8
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/b9/1e763008b10db366442469339f90a2b8400d0a
diff --git a/tests/resources/testrepo.git/objects/bd/758010071961f28336333bc41e9c64c9a64866 b/tests/resources/testrepo.git/objects/bd/758010071961f28336333bc41e9c64c9a64866
new file mode 100644
index 000000000..c5e3b87ad
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/bd/758010071961f28336333bc41e9c64c9a64866
diff --git a/tests/resources/testrepo.git/objects/db/4df74a2fc340a0d0cb0cafc0db471fdfff1048 b/tests/resources/testrepo.git/objects/db/4df74a2fc340a0d0cb0cafc0db471fdfff1048
new file mode 100644
index 000000000..5f3d50efa
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/db/4df74a2fc340a0d0cb0cafc0db471fdfff1048
@@ -0,0 +1,2 @@
+x
-�QJ1P�s����Iz2= � �@/�tz7f"�,^߬�W���պp�FW�gk���ѭ�`�$�8J��0c���������5
+�I҈�J>!+��N�U���(�û�1�Di<_�7�.5�O��X�[��#��f����o�;����]�\���e��=��[@t���&�xH��h���YJn
\ No newline at end of file
diff --git a/tests/resources/testrepo.git/objects/db/793a00a5615eca1aac97e42b3a68b1acfa8bfd b/tests/resources/testrepo.git/objects/db/793a00a5615eca1aac97e42b3a68b1acfa8bfd
new file mode 100644
index 000000000..ae82880de
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/db/793a00a5615eca1aac97e42b3a68b1acfa8bfd
diff --git a/tests/resources/testrepo.git/objects/db/c0be625bed24b5d8f5d9a927484f2065d321af b/tests/resources/testrepo.git/objects/db/c0be625bed24b5d8f5d9a927484f2065d321af
new file mode 100644
index 000000000..b966b0b2f
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/db/c0be625bed24b5d8f5d9a927484f2065d321af
diff --git a/tests/resources/testrepo.git/objects/f0/a2a10243ca64f935dbe3dccb89ec8bf16bdace b/tests/resources/testrepo.git/objects/f0/a2a10243ca64f935dbe3dccb89ec8bf16bdace
new file mode 100644
index 000000000..1b299dc25
--- /dev/null
+++ b/tests/resources/testrepo.git/objects/f0/a2a10243ca64f935dbe3dccb89ec8bf16bdace
diff --git a/tests/revwalk/basic.c b/tests/revwalk/basic.c
index 5ed7da4eb..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)
@@ -473,3 +473,51 @@ void test_revwalk_basic__big_timestamp(void)
 	git_signature_free(sig);
 
 }
+
+/* Ensure that we correctly hide a commit that is (timewise) older
+ * than the commits that we are showing.
+ *
+ * % git rev-list 8e73b76..bd75801
+ * bd758010071961f28336333bc41e9c64c9a64866
+ */
+void test_revwalk_basic__old_hidden_commit_one(void)
+{
+	git_oid new_id, old_id, oid;
+
+	revwalk_basic_setup_walk("testrepo.git");
+
+	cl_git_pass(git_oid_fromstr(&new_id, "bd758010071961f28336333bc41e9c64c9a64866"));
+	cl_git_pass(git_revwalk_push(_walk, &new_id));
+
+	cl_git_pass(git_oid_fromstr(&old_id, "8e73b769e97678d684b809b163bebdae2911720f"));
+	cl_git_pass(git_revwalk_hide(_walk, &old_id));
+
+	cl_git_pass(git_revwalk_next(&oid, _walk));
+	cl_assert(!git_oid_streq(&oid, "bd758010071961f28336333bc41e9c64c9a64866"));
+
+	cl_git_fail_with(GIT_ITEROVER, git_revwalk_next(&oid, _walk));
+}
+
+/* Ensure that we correctly hide a commit that is (timewise) older
+ * than the commits that we are showing.
+ *
+ * % git rev-list bd75801 ^b91e763
+ * bd758010071961f28336333bc41e9c64c9a64866
+ */
+void test_revwalk_basic__old_hidden_commit_two(void)
+{
+	git_oid new_id, old_id, oid;
+
+	revwalk_basic_setup_walk("testrepo.git");
+
+	cl_git_pass(git_oid_fromstr(&new_id, "bd758010071961f28336333bc41e9c64c9a64866"));
+	cl_git_pass(git_revwalk_push(_walk, &new_id));
+
+	cl_git_pass(git_oid_fromstr(&old_id, "b91e763008b10db366442469339f90a2b8400d0a"));
+	cl_git_pass(git_revwalk_hide(_walk, &old_id));
+
+	cl_git_pass(git_revwalk_next(&oid, _walk));
+	cl_assert(!git_oid_streq(&oid, "bd758010071961f28336333bc41e9c64c9a64866"));
+
+	cl_git_fail_with(GIT_ITEROVER, git_revwalk_next(&oid, _walk));
+}
diff --git a/tests/revwalk/hidecb.c b/tests/revwalk/hidecb.c
index 14cf39afd..b274ed86a 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);
 
 	/* 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);
 
 	/* 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;