Ranged iterators and rewritten git_status_file

The goal of this work is to rewrite git_status_file to use the
same underlying code as git_status_foreach.

This is done in 3 phases:

1. Extend iterators to allow ranged iteration with start and
   end prefixes for the range of file names to be covered.
2. Improve diff so that when there is a pathspec and there is
   a common non-wildcard prefix of the pathspec, it will use
   ranged iterators to minimize excess iteration.
3. Rewrite git_status_file to call git_status_foreach_ext
   with a pathspec that covers just the one file being checked.

Since ranged iterators underlie the status & diff implementation,
this is actually fairly efficient.  The workdir iterator does
end up loading the contents of all the directories down to the
single file, which should ideally be avoided, but it is pretty
good.

18 files changed, 761 insertions, 329 deletions

diff --git a/include/git2/status.h b/include/git2/status.h
index 0aff56a65..0130b4011 100644
--- a/include/git2/status.h
+++ b/include/git2/status.h
@@ -36,15 +36,18 @@ GIT_BEGIN_DECL
 /**
  * Gather file statuses and run a callback for each one.
  *
- * The callback is passed the path of the file, the status and the data pointer
- * passed to this function. If the callback returns something other than
- * GIT_SUCCESS, this function will return that value.
+ * The callback is passed the path of the file, the status and the data
+ * pointer passed to this function. If the callback returns something other
+ * than 0, this function will return that value.
  *
  * @param repo a repository object
  * @param callback the function to call on each file
- * @return GIT_SUCCESS or the return value of the callback which did not return GIT_SUCCESS
+ * @return 0 on success or the return value of the callback that was non-zero
  */
-GIT_EXTERN(int) git_status_foreach(git_repository *repo, int (*callback)(const char *, unsigned int, void *), void *payload);
+GIT_EXTERN(int) git_status_foreach(
+	git_repository *repo,
+	int (*callback)(const char *, unsigned int, void *),
+	void *payload);
 
 /**
  * Select the files on which to report status.
@@ -115,7 +118,7 @@ typedef struct {
  */
 GIT_EXTERN(int) git_status_foreach_ext(
 	git_repository *repo,
-	git_status_options *opts,
+	const git_status_options *opts,
 	int (*callback)(const char *, unsigned int, void *),
 	void *payload);
 
@@ -129,7 +132,10 @@ GIT_EXTERN(int) git_status_foreach_ext(
  *		the file doesn't exist in any of HEAD, the index or the worktree,
  *		GIT_SUCCESS otherwise
  */
-GIT_EXTERN(int) git_status_file(unsigned int *status_flags, git_repository *repo, const char *path);
+GIT_EXTERN(int) git_status_file(
+	unsigned int *status_flags,
+	git_repository *repo,
+	const char *path);
 
 /**
  * Test if the ignore rules apply to a given file.
@@ -141,11 +147,14 @@ GIT_EXTERN(int) git_status_file(unsigned int *status_flags, git_repository *repo
  *
  * @param ignored boolean returning 0 if the file is not ignored, 1 if it is
  * @param repo a repository object
- * @param path the file to check ignores for, rooted at the repo's workdir
- * @return GIT_SUCCESS if the ignore rules could be processed for the file
- *		(regardless of whether it exists or not), or an error < 0 if they could not.
+ * @param path the file to check ignores for, rooted at the repo's workdir.
+ * @return 0 if ignore rules could be processed for the file (regardless
+ *         of whether it exists or not), or an error < 0 if they could not.
  */
-GIT_EXTERN(int) git_status_should_ignore(int *ignored, git_repository *repo, const char *path);
+GIT_EXTERN(int) git_status_should_ignore(
+	int *ignored,
+	git_repository *repo,
+	const char *path);
 
 /** @} */
 GIT_END_DECL
diff --git a/src/attr_file.c b/src/attr_file.c
index 49ff7319f..5030ad5de 100644
--- a/src/attr_file.c
+++ b/src/attr_file.c
@@ -378,7 +378,7 @@ int git_attr_fnmatch__parse(
 				pattern++;
 		}
 		/* remember if we see an unescaped wildcard in pattern */
-		else if ((*scan == '*' || *scan == '.' || *scan == '[') &&
+		else if (git__iswildcard(*scan) &&
 			(scan == pattern || (*(scan - 1) != '\\')))
 			spec->flags = spec->flags | GIT_ATTR_FNMATCH_HASWILD;
 	}
diff --git a/src/buffer.c b/src/buffer.c
index 2ecb088f8..8687d5537 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -415,3 +415,30 @@ int git_buf_cmp(const git_buf *a, const git_buf *b)
 	return (result != 0) ? result :
 		(a->size < b->size) ? -1 : (a->size > b->size) ? 1 : 0;
 }
+
+int git_buf_common_prefix(git_buf *buf, const git_strarray *strings)
+{
+	size_t i;
+	const char *str, *pfx;
+
+	git_buf_clear(buf);
+
+	if (!strings || !strings->count)
+		return 0;
+
+	if (git_buf_sets(buf, strings->strings[0]) < 0)
+		return -1;
+
+	for (i = 1; i < strings->count; ++i) {
+		for (str = strings->strings[i], pfx = buf->ptr;
+			 *str && *str == *pfx; str++, pfx++)
+			/* scanning */;
+
+		git_buf_truncate(buf, pfx - buf->ptr);
+
+		if (!buf->size)
+			break;
+	}
+
+	return 0;
+}
diff --git a/src/buffer.h b/src/buffer.h
index 1f0ec1c15..5a0e7d7b2 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -122,4 +122,6 @@ void git_buf_rtrim(git_buf *buf);
 
 int git_buf_cmp(const git_buf *a, const git_buf *b);
 
+int git_buf_common_prefix(git_buf *buf, const git_strarray *strings);
+
 #endif
diff --git a/src/diff.c b/src/diff.c
index fed22f403..c8670b53e 100644
--- a/src/diff.c
+++ b/src/diff.c
@@ -11,6 +11,25 @@
 #include "config.h"
 #include "attr_file.h"
 
+static char *diff_prefix_from_pathspec(const git_strarray *pathspec)
+{
+	git_buf prefix = GIT_BUF_INIT;
+	const char *scan;
+
+	if (git_buf_common_prefix(&prefix, pathspec) < 0)
+		return NULL;
+
+	/* diff prefix will only be leading non-wildcards */
+	for (scan = prefix.ptr; *scan && !git__iswildcard(*scan); ++scan);
+	git_buf_truncate(&prefix, scan - prefix.ptr);
+
+	if (prefix.size > 0)
+		return git_buf_detach(&prefix);
+
+	git_buf_free(&prefix);
+	return NULL;
+}
+
 static bool diff_pathspec_is_interesting(const git_strarray *pathspec)
 {
 	const char *str;
@@ -613,13 +632,16 @@ int git_diff_tree_to_tree(
 	git_diff_list **diff)
 {
 	git_iterator *a = NULL, *b = NULL;
+	char *prefix = opts ? diff_prefix_from_pathspec(&opts->pathspec) : NULL;
 
 	assert(repo && old_tree && new_tree && diff);
 
-	if (git_iterator_for_tree(repo, old_tree, &a) < 0 ||
-		git_iterator_for_tree(repo, new_tree, &b) < 0)
+	if (git_iterator_for_tree_range(&a, repo, old_tree, prefix, prefix) < 0 ||
+		git_iterator_for_tree_range(&b, repo, new_tree, prefix, prefix) < 0)
 		return -1;
 
+	git__free(prefix);
+
 	return diff_from_iterators(repo, opts, a, b, diff);
 }
 
@@ -630,13 +652,16 @@ int git_diff_index_to_tree(
 	git_diff_list **diff)
 {
 	git_iterator *a = NULL, *b = NULL;
+	char *prefix = opts ? diff_prefix_from_pathspec(&opts->pathspec) : NULL;
 
 	assert(repo && diff);
 
-	if (git_iterator_for_tree(repo, old_tree, &a) < 0 ||
-		git_iterator_for_index(repo, &b) < 0)
+	if (git_iterator_for_tree_range(&a, repo, old_tree, prefix, prefix) < 0 ||
+		git_iterator_for_index_range(&b, repo, prefix, prefix) < 0)
 		return -1;
 
+	git__free(prefix);
+
 	return diff_from_iterators(repo, opts, a, b, diff);
 }
 
@@ -646,13 +671,16 @@ int git_diff_workdir_to_index(
 	git_diff_list **diff)
 {
 	git_iterator *a = NULL, *b = NULL;
+	char *prefix = opts ? diff_prefix_from_pathspec(&opts->pathspec) : NULL;
 
 	assert(repo && diff);
 
-	if (git_iterator_for_index(repo, &a) < 0 ||
-		git_iterator_for_workdir(repo, &b) < 0)
+	if (git_iterator_for_index_range(&a, repo, prefix, prefix) < 0 ||
+		git_iterator_for_workdir_range(&b, repo, prefix, prefix) < 0)
 		return -1;
 
+	git__free(prefix);
+
 	return diff_from_iterators(repo, opts, a, b, diff);
 }
 
@@ -664,13 +692,16 @@ int git_diff_workdir_to_tree(
 	git_diff_list **diff)
 {
 	git_iterator *a = NULL, *b = NULL;
+	char *prefix = opts ? diff_prefix_from_pathspec(&opts->pathspec) : NULL;
 
 	assert(repo && old_tree && diff);
 
-	if (git_iterator_for_tree(repo, old_tree, &a) < 0 ||
-		git_iterator_for_workdir(repo, &b) < 0)
+	if (git_iterator_for_tree_range(&a, repo, old_tree, prefix, prefix) < 0 ||
+		git_iterator_for_workdir_range(&b, repo, prefix, prefix) < 0)
 		return -1;
 
+	git__free(prefix);
+
 	return diff_from_iterators(repo, opts, a, b, diff);
 }
 
diff --git a/src/index.c b/src/index.c
index 216ede777..8a6ce0fd8 100644
--- a/src/index.c
+++ b/src/index.c
@@ -502,6 +502,15 @@ int git_index_find(git_index *index, const char *path)
 	return git_vector_bsearch2(&index->entries, index_srch, path);
 }
 
+unsigned int git_index__prefix_position(git_index *index, const char *path)
+{
+	unsigned int pos;
+
+	git_vector_bsearch3(&pos, &index->entries, index_srch, path);
+
+	return pos;
+}
+
 void git_index_uniq(git_index *index)
 {
 	git_vector_uniq(&index->entries);
diff --git a/src/index.h b/src/index.h
index e745c8f69..8515f4fcb 100644
--- a/src/index.h
+++ b/src/index.h
@@ -33,4 +33,6 @@ struct git_index {
 
 extern void git_index__init_entry_from_stat(struct stat *st, git_index_entry *entry);
 
+extern unsigned int git_index__prefix_position(git_index *index, const char *path);
+
 #endif
diff --git a/src/iterator.c b/src/iterator.c
index 646990d3f..c601a6e73 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -11,6 +11,23 @@
 #include "buffer.h"
 #include "git2/submodule.h"
 
+#define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC) do { \
+	(P) = git__calloc(1, sizeof(NAME_LC ## _iterator)); \
+	GITERR_CHECK_ALLOC(P); \
+	(P)->base.type    = GIT_ITERATOR_ ## NAME_UC; \
+	(P)->base.start   = start ? git__strdup(start) : NULL; \
+	(P)->base.end     = end ? git__strdup(end) : NULL; \
+	(P)->base.current = NAME_LC ## _iterator__current; \
+	(P)->base.at_end  = NAME_LC ## _iterator__at_end; \
+	(P)->base.advance = NAME_LC ## _iterator__advance; \
+	(P)->base.seek    = NAME_LC ## _iterator__seek; \
+	(P)->base.reset   = NAME_LC ## _iterator__reset; \
+	(P)->base.free    = NAME_LC ## _iterator__free; \
+	if ((start && !(P)->base.start) || (end && !(P)->base.end)) \
+		return -1; \
+	} while (0)
+
+
 static int empty_iterator__no_item(
 	git_iterator *iter, const git_index_entry **entry)
 {
@@ -31,6 +48,13 @@ static int empty_iterator__noop(git_iterator *iter)
 	return 0;
 }
 
+static int empty_iterator__seek(git_iterator *iter, const char *prefix)
+{
+	GIT_UNUSED(iter);
+	GIT_UNUSED(prefix);
+	return -1;
+}
+
 static void empty_iterator__free(git_iterator *iter)
 {
 	GIT_UNUSED(iter);
@@ -45,6 +69,7 @@ int git_iterator_for_nothing(git_iterator **iter)
 	i->current = empty_iterator__no_item;
 	i->at_end  = empty_iterator__at_end;
 	i->advance = empty_iterator__no_item;
+	i->seek    = empty_iterator__seek;
 	i->reset   = empty_iterator__noop;
 	i->free    = empty_iterator__free;
 
@@ -53,10 +78,12 @@ int git_iterator_for_nothing(git_iterator **iter)
 	return 0;
 }
 
+
 typedef struct tree_iterator_frame tree_iterator_frame;
 struct tree_iterator_frame {
 	tree_iterator_frame *next;
 	git_tree *tree;
+	char *start;
 	unsigned int index;
 };
 
@@ -66,6 +93,7 @@ typedef struct {
 	tree_iterator_frame *stack;
 	git_index_entry entry;
 	git_buf path;
+	bool path_has_filename;
 } tree_iterator;
 
 static const git_tree_entry *tree_iterator__tree_entry(tree_iterator *ti)
@@ -74,25 +102,62 @@ static const git_tree_entry *tree_iterator__tree_entry(tree_iterator *ti)
 		git_tree_entry_byindex(ti->stack->tree, ti->stack->index);
 }
 
+static char *tree_iterator__current_filename(
+	tree_iterator *ti, const git_tree_entry *te)
+{
+	if (!ti->path_has_filename) {
+		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
+			return NULL;
+		ti->path_has_filename = true;
+	}
+
+	return ti->path.ptr;
+}
+
+static void tree_iterator__pop_frame(tree_iterator *ti)
+{
+	tree_iterator_frame *tf = ti->stack;
+	ti->stack = tf->next;
+	if (ti->stack != NULL) /* don't free the initial tree */
+		git_tree_free(tf->tree);
+	git__free(tf);
+}
+
+static int tree_iterator__to_end(tree_iterator *ti)
+{
+	while (ti->stack && ti->stack->next)
+		tree_iterator__pop_frame(ti);
+
+	if (ti->stack)
+		ti->stack->index = git_tree_entrycount(ti->stack->tree);
+
+	return 0;
+}
+
 static int tree_iterator__current(
 	git_iterator *self, const git_index_entry **entry)
 {
 	tree_iterator *ti = (tree_iterator *)self;
 	const git_tree_entry *te = tree_iterator__tree_entry(ti);
 
-	*entry = NULL;
+	if (entry)
+		*entry = NULL;
 
 	if (te == NULL)
 		return 0;
 
 	ti->entry.mode = te->attr;
 	git_oid_cpy(&ti->entry.oid, &te->oid);
-	if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
+
+	ti->entry.path = tree_iterator__current_filename(ti, te);
+	if (ti->entry.path == NULL)
 		return -1;
 
-	ti->entry.path = ti->path.ptr;
+	if (ti->base.end && git__prefixcmp(ti->entry.path, ti->base.end) > 0)
+		return tree_iterator__to_end(ti);
 
-	*entry = &ti->entry;
+	if (entry)
+		*entry = &ti->entry;
 
 	return 0;
 }
@@ -102,11 +167,20 @@ static int tree_iterator__at_end(git_iterator *self)
 	return (tree_iterator__tree_entry((tree_iterator *)self) == NULL);
 }
 
-static tree_iterator_frame *tree_iterator__alloc_frame(git_tree *tree)
+static tree_iterator_frame *tree_iterator__alloc_frame(
+	git_tree *tree, char *start)
 {
 	tree_iterator_frame *tf = git__calloc(1, sizeof(tree_iterator_frame));
-	if (tf != NULL)
-		tf->tree = tree;
+	if (!tf)
+		return NULL;
+
+	tf->tree = tree;
+
+	if (start && *start) {
+		tf->start = start;
+		tf->index = git_tree_entry_prefix_position(tree, start);
+	}
+
 	return tf;
 }
 
@@ -116,35 +190,43 @@ static int tree_iterator__expand_tree(tree_iterator *ti)
 	git_tree *subtree;
 	const git_tree_entry *te = tree_iterator__tree_entry(ti);
 	tree_iterator_frame *tf;
+	char *relpath;
 
 	while (te != NULL && entry_is_tree(te)) {
+		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
+			return -1;
+
+		/* check that we have not passed the range end */
+		if (ti->base.end != NULL &&
+			git__prefixcmp(ti->path.ptr, ti->base.end) > 0)
+			return tree_iterator__to_end(ti);
+
 		if ((error = git_tree_lookup(&subtree, ti->repo, &te->oid)) < 0)
 			return error;
 
-		if ((tf = tree_iterator__alloc_frame(subtree)) == NULL)
+		relpath = NULL;
+
+		/* apply range start to new frame if relevant */
+		if (ti->stack->start &&
+			git__prefixcmp(ti->stack->start, te->filename) == 0)
+		{
+			size_t namelen = strlen(te->filename);
+			if (ti->stack->start[namelen] == '/')
+				relpath = ti->stack->start + namelen + 1;
+		}
+
+		if ((tf = tree_iterator__alloc_frame(subtree, relpath)) == NULL)
 			return -1;
 
 		tf->next  = ti->stack;
 		ti->stack = tf;
 
-		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
-			return -1;
-
 		te = tree_iterator__tree_entry(ti);
 	}
 
 	return 0;
 }
 
-static void tree_iterator__pop_frame(tree_iterator *ti)
-{
-	tree_iterator_frame *tf = ti->stack;
-	ti->stack = tf->next;
-	if (ti->stack != NULL) /* don't free the initial tree */
-		git_tree_free(tf->tree);
-	git__free(tf);
-}
-
 static int tree_iterator__advance(
 	git_iterator *self, const git_index_entry **entry)
 {
@@ -155,26 +237,40 @@ static int tree_iterator__advance(
 	if (entry != NULL)
 		*entry = NULL;
 
-	while (ti->stack != NULL) {
-		/* remove old entry filename */
+	if (ti->path_has_filename) {
 		git_buf_rtruncate_at_char(&ti->path, '/');
+		ti->path_has_filename = false;
+	}
 
+	while (ti->stack != NULL) {
 		te = git_tree_entry_byindex(ti->stack->tree, ++ti->stack->index);
 		if (te != NULL)
 			break;
 
 		tree_iterator__pop_frame(ti);
+
+		git_buf_rtruncate_at_char(&ti->path, '/');
 	}
 
 	if (te && entry_is_tree(te))
 		error = tree_iterator__expand_tree(ti);
 
-	if (!error && entry != NULL)
+	if (!error)
 		error = tree_iterator__current(self, entry);
 
 	return error;
 }
 
+static int tree_iterator__seek(git_iterator *self, const char *prefix)
+{
+	GIT_UNUSED(self);
+	GIT_UNUSED(prefix);
+	/* pop stack until matches prefix */
+	/* seek item in current frame matching prefix */
+	/* push stack which matches prefix */
+	return -1;
+}
+
 static void tree_iterator__free(git_iterator *self)
 {
 	tree_iterator *ti = (tree_iterator *)self;
@@ -186,15 +282,25 @@ static void tree_iterator__free(git_iterator *self)
 static int tree_iterator__reset(git_iterator *self)
 {
 	tree_iterator *ti = (tree_iterator *)self;
+
 	while (ti->stack && ti->stack->next)
 		tree_iterator__pop_frame(ti);
+
 	if (ti->stack)
-		ti->stack->index = 0;
+		ti->stack->index =
+			git_tree_entry_prefix_position(ti->stack->tree, ti->base.start);
+
+	git_buf_clear(&ti->path);
+
 	return tree_iterator__expand_tree(ti);
 }
 
-int git_iterator_for_tree(
-	git_repository *repo, git_tree *tree, git_iterator **iter)
+int git_iterator_for_tree_range(
+	git_iterator **iter,
+	git_repository *repo,
+	git_tree *tree,
+	const char *start,
+	const char *end)
 {
 	int error;
 	tree_iterator *ti;
@@ -202,22 +308,16 @@ int git_iterator_for_tree(
 	if (tree == NULL)
 		return git_iterator_for_nothing(iter);
 
-	ti = git__calloc(1, sizeof(tree_iterator));
-	GITERR_CHECK_ALLOC(ti);
+	ITERATOR_BASE_INIT(ti, tree, TREE);
 
-	ti->base.type    = GIT_ITERATOR_TREE;
-	ti->base.current = tree_iterator__current;
-	ti->base.at_end  = tree_iterator__at_end;
-	ti->base.advance = tree_iterator__advance;
-	ti->base.reset   = tree_iterator__reset;
-	ti->base.free    = tree_iterator__free;
-	ti->repo         = repo;
-	ti->stack        = tree_iterator__alloc_frame(tree);
+	ti->repo  = repo;
+	ti->stack = tree_iterator__alloc_frame(tree, ti->base.start);
 
 	if ((error = tree_iterator__expand_tree(ti)) < 0)
 		git_iterator_free((git_iterator *)ti);
 	else
 		*iter = (git_iterator *)ti;
+
 	return error;
 }
 
@@ -232,7 +332,19 @@ static int index_iterator__current(
 	git_iterator *self, const git_index_entry **entry)
 {
 	index_iterator *ii = (index_iterator *)self;
-	*entry = git_index_get(ii->index, ii->current);
+	git_index_entry *ie = git_index_get(ii->index, ii->current);
+
+	if (ie != NULL &&
+		ii->base.end != NULL &&
+		git__prefixcmp(ie->path, ii->base.end) > 0)
+	{
+		ii->current = git_index_entrycount(ii->index);
+		ie = NULL;
+	}
+
+	if (entry)
+		*entry = ie;
+
 	return 0;
 }
 
@@ -246,11 +358,19 @@ static int index_iterator__advance(
 	git_iterator *self, const git_index_entry **entry)
 {
 	index_iterator *ii = (index_iterator *)self;
+
 	if (ii->current < git_index_entrycount(ii->index))
 		ii->current++;
-	if (entry)
-		*entry = git_index_get(ii->index, ii->current);
-	return 0;
+
+	return index_iterator__current(self, entry);
+}
+
+static int index_iterator__seek(git_iterator *self, const char *prefix)
+{
+	GIT_UNUSED(self);
+	GIT_UNUSED(prefix);
+	/* find last item before prefix */
+	return -1;
 }
 
 static int index_iterator__reset(git_iterator *self)
@@ -267,24 +387,24 @@ static void index_iterator__free(git_iterator *self)
 	ii->index = NULL;
 }
 
-int git_iterator_for_index(git_repository *repo, git_iterator **iter)
+int git_iterator_for_index_range(
+	git_iterator **iter,
+	git_repository *repo,
+	const char *start,
+	const char *end)
 {
 	int error;
-	index_iterator *ii = git__calloc(1, sizeof(index_iterator));
-	GITERR_CHECK_ALLOC(ii);
+	index_iterator *ii;
 
-	ii->base.type    = GIT_ITERATOR_INDEX;
-	ii->base.current = index_iterator__current;
-	ii->base.at_end  = index_iterator__at_end;
-	ii->base.advance = index_iterator__advance;
-	ii->base.reset   = index_iterator__reset;
-	ii->base.free    = index_iterator__free;
-	ii->current      = 0;
+	ITERATOR_BASE_INIT(ii, index, INDEX);
 
 	if ((error = git_repository_index(&ii->index, repo)) < 0)
 		git__free(ii);
-	else
+	else {
+		ii->current = start ? git_index__prefix_position(ii->index, start) : 0;
 		*iter = (git_iterator *)ii;
+	}
+
 	return error;
 }
 
@@ -294,6 +414,7 @@ struct workdir_iterator_frame {
 	workdir_iterator_frame *next;
 	git_vector entries;
 	unsigned int index;
+	char *start;
 };
 
 typedef struct {
@@ -332,6 +453,12 @@ static void workdir_iterator__free_frame(workdir_iterator_frame *wf)
 
 static int workdir_iterator__update_entry(workdir_iterator *wi);
 
+static int workdir_iterator__entry_cmp(const void *prefix, const void *item)
+{
+	const git_path_with_stat *ps = item;
+	return git__prefixcmp((const char *)prefix, ps->path);
+}
+
 static int workdir_iterator__expand_dir(workdir_iterator *wi)
 {
 	int error;
@@ -345,6 +472,17 @@ static int workdir_iterator__expand_dir(workdir_iterator *wi)
 	}
 
 	git_vector_sort(&wf->entries);
+
+	if (!wi->stack)
+		wf->start = wi->base.start;
+	else if (wi->stack->start &&
+		git__prefixcmp(wi->stack->start, wi->path.ptr + wi->root_len) == 0)
+		wf->start = wi->stack->start;
+
+	if (wf->start)
+		git_vector_bsearch3(
+			&wf->index, &wf->entries, workdir_iterator__entry_cmp, wf->start);
+
 	wf->next  = wi->stack;
 	wi->stack = wf;
 
@@ -412,6 +550,16 @@ static int workdir_iterator__advance(
 	return error;
 }
 
+static int workdir_iterator__seek(git_iterator *self, const char *prefix)
+{
+	GIT_UNUSED(self);
+	GIT_UNUSED(prefix);
+	/* pop stack until matching prefix */
+	/* find prefix item in current frame */
+	/* push subdirectories as deep as possible while matching */
+	return 0;
+}
+
 static int workdir_iterator__reset(git_iterator *self)
 {
 	workdir_iterator *wi = (workdir_iterator *)self;
@@ -445,10 +593,18 @@ static int workdir_iterator__update_entry(workdir_iterator *wi)
 	git_path_with_stat *ps = git_vector_get(&wi->stack->entries, wi->stack->index);
 
 	git_buf_truncate(&wi->path, wi->root_len);
+	memset(&wi->entry, 0, sizeof(wi->entry));
+
+	if (!ps)
+		return 0;
+
 	if (git_buf_put(&wi->path, ps->path, ps->path_len) < 0)
 		return -1;
 
-	memset(&wi->entry, 0, sizeof(wi->entry));
+	if (wi->base.end &&
+		git__prefixcmp(wi->path.ptr + wi->root_len, wi->base.end) > 0)
+		return 0;
+
 	wi->entry.path = ps->path;
 
 	/* skip over .git directory */
@@ -495,19 +651,24 @@ static int workdir_iterator__update_entry(workdir_iterator *wi)
 	return 0;
 }
 
-int git_iterator_for_workdir(git_repository *repo, git_iterator **iter)
+int git_iterator_for_workdir_range(
+	git_iterator **iter,
+	git_repository *repo,
+	const char *start,
+	const char *end)
 {
 	int error;
-	workdir_iterator *wi = git__calloc(1, sizeof(workdir_iterator));
-	GITERR_CHECK_ALLOC(wi);
+	workdir_iterator *wi;
 
-	wi->base.type    = GIT_ITERATOR_WORKDIR;
-	wi->base.current = workdir_iterator__current;
-	wi->base.at_end  = workdir_iterator__at_end;
-	wi->base.advance = workdir_iterator__advance;
-	wi->base.reset   = workdir_iterator__reset;
-	wi->base.free    = workdir_iterator__free;
-	wi->repo         = repo;
+	if (git_repository_is_bare(repo)) {
+		giterr_set(GITERR_INVALID,
+			"Cannot scan working directory for bare repo");
+		return -1;
+	}
+
+	ITERATOR_BASE_INIT(wi, workdir, WORKDIR);
+
+	wi->repo = repo;
 
 	if (git_buf_sets(&wi->path, git_repository_workdir(repo)) < 0 ||
 		git_path_to_dir(&wi->path) < 0 ||
@@ -559,3 +720,21 @@ int git_iterator_advance_into_directory(
 
 	return entry ? git_iterator_current(iter, entry) : 0;
 }
+
+int git_iterator_cmp(
+	git_iterator *iter, const char *path_prefix)
+{
+	const git_index_entry *entry;
+
+	/* a "done" iterator is after every prefix */
+	if (git_iterator_current(iter, &entry) < 0 ||
+		entry == NULL)
+		return 1;
+
+	/* a NULL prefix is after any valid iterator */
+	if (!path_prefix)
+		return -1;
+
+	return git__prefixcmp(entry->path, path_prefix);
+}
+
diff --git a/src/iterator.h b/src/iterator.h
index 974c2daeb..b916a9080 100644
--- a/src/iterator.h
+++ b/src/iterator.h
@@ -21,23 +21,48 @@ typedef enum {
 
 struct git_iterator {
 	git_iterator_type_t type;
+	char *start;
+	char *end;
 	int (*current)(git_iterator *, const git_index_entry **);
 	int (*at_end)(git_iterator *);
 	int (*advance)(git_iterator *, const git_index_entry **);
+	int (*seek)(git_iterator *, const char *prefix);
 	int (*reset)(git_iterator *);
 	void (*free)(git_iterator *);
 };
 
-int git_iterator_for_nothing(git_iterator **iter);
+extern int git_iterator_for_nothing(git_iterator **iter);
 
-int git_iterator_for_tree(
-	git_repository *repo, git_tree *tree, git_iterator **iter);
+extern int git_iterator_for_tree_range(
+	git_iterator **iter, git_repository *repo, git_tree *tree,
+	const char *start, const char *end);
 
-int git_iterator_for_index(
-	git_repository *repo, git_iterator **iter);
+GIT_INLINE(int) git_iterator_for_tree(
+	git_iterator **iter, git_repository *repo, git_tree *tree)
+{
+	return git_iterator_for_tree_range(iter, repo, tree, NULL, NULL);
+}
+
+extern int git_iterator_for_index_range(
+	git_iterator **iter, git_repository *repo,
+	const char *start, const char *end);
+
+GIT_INLINE(int) git_iterator_for_index(
+	git_iterator **iter, git_repository *repo)
+{
+	return git_iterator_for_index_range(iter, repo, NULL, NULL);
+}
+
+extern int git_iterator_for_workdir_range(
+	git_iterator **iter, git_repository *repo,
+	const char *start, const char *end);
+
+GIT_INLINE(int) git_iterator_for_workdir(
+	git_iterator **iter, git_repository *repo)
+{
+	return git_iterator_for_workdir_range(iter, repo, NULL, NULL);
+}
 
-int git_iterator_for_workdir(
-	git_repository *repo, git_iterator **iter);
 
 /* Entry is not guaranteed to be fully populated.  For a tree iterator,
  * we will only populate the mode, oid and path, for example.  For a workdir
@@ -64,6 +89,12 @@ GIT_INLINE(int) git_iterator_advance(
 	return iter->advance(iter, entry);
 }
 
+GIT_INLINE(int) git_iterator_seek(
+	git_iterator *iter, const char *prefix)
+{
+	return iter->seek(iter, prefix);
+}
+
 GIT_INLINE(int) git_iterator_reset(git_iterator *iter)
 {
 	return iter->reset(iter);
@@ -75,6 +106,12 @@ GIT_INLINE(void) git_iterator_free(git_iterator *iter)
 		return;
 
 	iter->free(iter);
+
+	git__free(iter->start);
+	git__free(iter->end);
+
+	memset(iter, 0, sizeof(*iter));
+
 	git__free(iter);
 }
 
@@ -108,4 +145,7 @@ extern int git_iterator_current_is_ignored(git_iterator *iter);
 extern int git_iterator_advance_into_directory(
 	git_iterator *iter, const git_index_entry **entry);
 
+extern int git_iterator_cmp(
+	git_iterator *iter, const char *path_prefix);
+
 #endif
diff --git a/src/status.c b/src/status.c
index 1c5609cd8..e9ad3cfe4 100644
--- a/src/status.c
+++ b/src/status.c
@@ -70,7 +70,7 @@ static unsigned int workdir_delta2status(git_delta_t workdir_status)
 
 int git_status_foreach_ext(
 	git_repository *repo,
-	git_status_options *opts,
+	const git_status_options *opts,
 	int (*cb)(const char *, unsigned int, void *),
 	void *cbdata)
 {
@@ -163,245 +163,71 @@ int git_status_foreach(
 	return git_status_foreach_ext(repo, &opts, callback, payload);
 }
 
-
-/*
- * the old stuff
- */
-
-struct status_entry {
-	git_index_time mtime;
-
-	git_oid head_oid;
-	git_oid index_oid;
-	git_oid wt_oid;
-
-	unsigned int status_flags;
-
-	char path[GIT_FLEX_ARRAY]; /* more */
+struct status_file_info {
+	unsigned int count;
+	unsigned int status;
+	char *expected;
 };
 
-static struct status_entry *status_entry_new(git_vector *entries, const char *path)
-{
-	struct status_entry *e = git__calloc(sizeof(*e) + strlen(path) + 1, 1);
-	if (e == NULL)
-		return NULL;
-
-	if (entries != NULL)
-		git_vector_insert(entries, e);
-
-	strcpy(e->path, path);
-
-	return e;
-}
-
-GIT_INLINE(void) status_entry_update_from_tree_entry(struct status_entry *e, const git_tree_entry *tree_entry)
-{
-	assert(e && tree_entry);
-
-	git_oid_cpy(&e->head_oid, &tree_entry->oid);
-}
-
-GIT_INLINE(void) status_entry_update_from_index_entry(struct status_entry *e, const git_index_entry *index_entry)
-{
-	assert(e && index_entry);
-
-	git_oid_cpy(&e->index_oid, &index_entry->oid);
-	e->mtime = index_entry->mtime;
-}
-
-static void status_entry_update_from_index(struct status_entry *e, git_index *index)
-{
-	int idx;
-	git_index_entry *index_entry;
-
-	assert(e && index);
-
-	idx = git_index_find(index, e->path);
-	if (idx < 0)
-		return;
-
-	index_entry = git_index_get(index, idx);
-
-	status_entry_update_from_index_entry(e, index_entry);
-}
-
-static int status_entry_update_from_workdir(struct status_entry *e, const char* full_path)
-{
-	struct stat filest;
-
-	if (p_stat(full_path, &filest) < 0) {
-		giterr_set(GITERR_OS, "Cannot access file '%s'", full_path);
-		return GIT_ENOTFOUND;
-	}
-
-	if (e->mtime.seconds == (git_time_t)filest.st_mtime)
-		git_oid_cpy(&e->wt_oid, &e->index_oid);
-	else
-		git_odb_hashfile(&e->wt_oid, full_path, GIT_OBJ_BLOB);
-
-	return 0;
-}
-
-static int status_entry_update_flags(struct status_entry *e)
-{
-	git_oid zero;
-	int head_zero, index_zero, wt_zero;
-
-	memset(&zero, 0x0, sizeof(git_oid));
-
-	head_zero = git_oid_cmp(&zero, &e->head_oid);
-	index_zero = git_oid_cmp(&zero, &e->index_oid);
-	wt_zero = git_oid_cmp(&zero, &e->wt_oid);
-
-	if (head_zero == 0 && index_zero == 0 && wt_zero == 0)
-		return GIT_ENOTFOUND;
-
-	if (head_zero == 0 && index_zero != 0)
-		e->status_flags |= GIT_STATUS_INDEX_NEW;
-	else if (index_zero == 0 && head_zero != 0)
-		e->status_flags |= GIT_STATUS_INDEX_DELETED;
-	else if (git_oid_cmp(&e->head_oid, &e->index_oid) != 0)
-		e->status_flags |= GIT_STATUS_INDEX_MODIFIED;
-
-	if (index_zero == 0 && wt_zero != 0)
-		e->status_flags |= GIT_STATUS_WT_NEW;
-	else if (wt_zero == 0 && index_zero != 0)
-		e->status_flags |= GIT_STATUS_WT_DELETED;
-	else if (git_oid_cmp(&e->index_oid, &e->wt_oid) != 0)
-		e->status_flags |= GIT_STATUS_WT_MODIFIED;
-
-	return 0;
-}
-
-static int status_entry_is_ignorable(struct status_entry *e)
+static int get_one_status(const char *path, unsigned int status, void *data)
 {
-	/* don't ignore files that exist in head or index already */
-	return (e->status_flags == GIT_STATUS_WT_NEW);
-}
+	struct status_file_info *sfi = data;
 
-static int status_entry_update_ignore(struct status_entry *e, git_ignores *ignores, const char *path)
-{
-	int ignored;
+	sfi->count++;
+	sfi->status = status;
 
-	if (git_ignore__lookup(ignores, path, &ignored) < 0)
+	if (sfi->count > 1 || strcmp(sfi->expected, path) != 0) {
+		giterr_set(GITERR_INVALID,
+			"Ambiguous path '%s' given to git_status_file", sfi->expected);
 		return -1;
-
-	if (ignored)
-		/* toggle off WT_NEW and on IGNORED */
-		e->status_flags =
-			(e->status_flags & ~GIT_STATUS_WT_NEW) | GIT_STATUS_IGNORED;
-
-	return 0;
-}
-
-static int recurse_tree_entry(git_tree *tree, struct status_entry *e, const char *path)
-{
-	char *dir_sep;
-	const git_tree_entry *tree_entry;
-	git_tree *subtree;
-	int error;
-
-	dir_sep = strchr(path, '/');
-	if (!dir_sep) {
-		if ((tree_entry = git_tree_entry_byname(tree, path)) != NULL)
-			/* The leaf exists in the tree*/
-			status_entry_update_from_tree_entry(e, tree_entry);
-		return 0;
-	}
-
-	/* Retrieve subtree name */
-	*dir_sep = '\0';
-
-	if ((tree_entry = git_tree_entry_byname(tree, path)) == NULL)
-		return 0; /* The subtree doesn't exist in the tree*/
-
-	*dir_sep = '/';
-
-	/* Retreive subtree */
-	error = git_tree_lookup(&subtree, tree->object.repo, &tree_entry->oid);
-	if (!error) {
-		error = recurse_tree_entry(subtree, e, dir_sep+1);
-		git_tree_free(subtree);
 	}
 
-	return error;
+	return 0;
 }
 
 int git_status_file(
-	unsigned int *status_flags, git_repository *repo, const char *path)
+	unsigned int *status_flags,
+	git_repository *repo,
+	const char *path)
 {
-	struct status_entry *e;
-	git_index *index = NULL;
-	git_buf temp_path = GIT_BUF_INIT;
-	int error = 0;
-	git_tree *tree = NULL;
-	const char *workdir;
+	int error;
+	git_status_options opts;
+	struct status_file_info sfi;
 
 	assert(status_flags && repo && path);
 
-	if ((workdir = git_repository_workdir(repo)) == NULL) {
-		giterr_set(GITERR_INVALID, "Cannot get file status from bare repo");
+	memset(&sfi, 0, sizeof(sfi));
+	if ((sfi.expected = git__strdup(path)) == NULL)
 		return -1;
-	}
-
-	if (git_buf_joinpath(&temp_path, workdir, path) < 0)
-		return -1;
-
-	if (git_path_isdir(temp_path.ptr)) {
-		giterr_set(GITERR_INVALID, "Cannot get file status for directory '%s'", temp_path.ptr);
-		git_buf_free(&temp_path);
-		return -1;
-	}
-
-	e = status_entry_new(NULL, path);
-	GITERR_CHECK_ALLOC(e);
-
-	/* Find file in Workdir */
-	if (git_path_exists(temp_path.ptr) == true &&
-		(error = status_entry_update_from_workdir(e, temp_path.ptr)) < 0)
-		goto cleanup;
-
-	/* Find file in Index */
-	if ((error = git_repository_index__weakptr(&index, repo)) < 0)
-		goto cleanup;
-	status_entry_update_from_index(e, index);
 
-	/* Try to find file in HEAD */
-	if ((error = git_repository_head_tree(&tree, repo)) < 0)
-		goto cleanup;
-
-	if (tree != NULL) {
-		if ((error = git_buf_sets(&temp_path, path)) < 0 ||
-			(error = recurse_tree_entry(tree, e, temp_path.ptr)) < 0)
-			goto cleanup;
-	}
-
-	/* Determine status */
-	if ((error = status_entry_update_flags(e)) < 0)
-		giterr_set(GITERR_OS, "Cannot find file '%s' to determine status", path);
-
-	if (!error && status_entry_is_ignorable(e)) {
-		git_ignores ignores;
+	memset(&opts, 0, sizeof(opts));
+	opts.show  = GIT_STATUS_SHOW_INDEX_AND_WORKDIR;
+	opts.flags = GIT_STATUS_OPT_INCLUDE_IGNORED |
+		GIT_STATUS_OPT_INCLUDE_UNTRACKED |
+		GIT_STATUS_OPT_RECURSE_UNTRACKED_DIRS |
+		GIT_STATUS_OPT_INCLUDE_UNMODIFIED;
+	opts.pathspec.count = 1;
+	opts.pathspec.strings = &sfi.expected;
 
-		if ((error = git_ignore__for_path(repo, path, &ignores)) == 0)
-			error = status_entry_update_ignore(e, &ignores, path);
+	error = git_status_foreach_ext(repo, &opts, get_one_status, &sfi);
 
-		git_ignore__free(&ignores);
+	if (!error && !sfi.count) {
+		giterr_set(GITERR_INVALID,
+			"Attempt to get status of nonexistent file '%s'", path);
+		error = GIT_ENOTFOUND;
 	}
 
-	if (!error)
-		*status_flags = e->status_flags;
+	*status_flags = sfi.status;
 
-cleanup:
-	git_buf_free(&temp_path);
-	git_tree_free(tree);
-	git__free(e);
+	git__free(sfi.expected);
 
 	return error;
 }
 
 int git_status_should_ignore(
-	int *ignored, git_repository *repo, const char *path)
+	int *ignored,
+	git_repository *repo,
+	const char *path)
 {
 	int error;
 	git_ignores ignores;
diff --git a/src/tree.c b/src/tree.c
index 7e2bfc102..adbf97498 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -195,6 +195,33 @@ const git_tree_entry *git_tree_entry_byindex(git_tree *tree, unsigned int idx)
 	return git_vector_get(&tree->entries, idx);
 }
 
+int git_tree_entry_prefix_position(git_tree *tree, const char *path)
+{
+	git_vector *entries = &tree->entries;
+	struct tree_key_search ksearch;
+	unsigned int at_pos;
+
+	ksearch.filename = path;
+	ksearch.filename_len = strlen(path);
+
+	/* Find tree entry with appropriate prefix */
+	git_vector_bsearch3(&at_pos, entries, &homing_search_cmp, &ksearch);
+
+	for (; at_pos < entries->length; ++at_pos) {
+		const git_tree_entry *entry = entries->contents[at_pos];
+		if (homing_search_cmp(&ksearch, entry) < 0)
+			break;
+	}
+
+	for (; at_pos > 0; --at_pos) {
+		const git_tree_entry *entry = entries->contents[at_pos - 1];
+		if (homing_search_cmp(&ksearch, entry) > 0)
+			break;
+	}
+
+	return at_pos;
+}
+
 unsigned int git_tree_entrycount(git_tree *tree)
 {
 	assert(tree);
diff --git a/src/tree.h b/src/tree.h
index fd00afde5..a5b7f6323 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -38,4 +38,14 @@ GIT_INLINE(unsigned int) entry_is_tree(const struct git_tree_entry *e)
 void git_tree__free(git_tree *tree);
 int git_tree__parse(git_tree *tree, git_odb_object *obj);
 
+/**
+ * Lookup the first position in the tree with a given prefix.
+ *
+ * @param tree a previously loaded tree.
+ * @param prefix the beginning of a path to find in the tree.
+ * @return index of the first item at or after the given prefix.
+ */
+int git_tree_entry_prefix_position(git_tree *tree, const char *prefix);
+
+
 #endif
diff --git a/src/util.h b/src/util.h
index 2081f29f9..cb5e83ce9 100644
--- a/src/util.h
+++ b/src/util.h
@@ -209,4 +209,9 @@ GIT_INLINE(bool) git__isspace(int c)
     return (c == ' ' || c == '\t' || c == '\n' || c == '\f' || c == '\r' || c == '\v');
 }
 
+GIT_INLINE(bool) git__iswildcard(int c)
+{
+	return (c == '*' || c == '?' || c == '[');
+}
+
 #endif /* INCLUDE_util_h__ */
diff --git a/src/vector.c b/src/vector.c
index 304f324f0..6f9aacccf 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -116,8 +116,13 @@ void git_vector_sort(git_vector *v)
 	v->sorted = 1;
 }
 
-int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key)
+int git_vector_bsearch3(
+	unsigned int *at_pos,
+	git_vector *v,
+	git_vector_cmp key_lookup,
+	const void *key)
 {
+	int rval;
 	size_t pos;
 
 	assert(v && key && key_lookup);
@@ -127,13 +132,16 @@ int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *ke
 
 	git_vector_sort(v);
 
-	if (git__bsearch(v->contents, v->length, key, key_lookup, &pos) >= 0)
-		return (int)pos;
+	rval = git__bsearch(v->contents, v->length, key, key_lookup, &pos);
 
-	return GIT_ENOTFOUND;
+	if (at_pos != NULL)
+		*at_pos = (unsigned int)pos;
+
+	return (rval >= 0) ? (int)pos : GIT_ENOTFOUND;
 }
 
-int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key)
+int git_vector_search2(
+	git_vector *v, git_vector_cmp key_lookup, const void *key)
 {
 	unsigned int i;
 
@@ -157,11 +165,6 @@ int git_vector_search(git_vector *v, const void *entry)
 	return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry);
 }
 
-int git_vector_bsearch(git_vector *v, const void *key)
-{
-	return git_vector_bsearch2(v, v->_cmp, key);
-}
-
 int git_vector_remove(git_vector *v, unsigned int idx)
 {
 	unsigned int i;
diff --git a/src/vector.h b/src/vector.h
index 5bc27914a..9139db345 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -26,13 +26,24 @@ void git_vector_free(git_vector *v);
 void git_vector_clear(git_vector *v);
 void git_vector_swap(git_vector *a, git_vector *b);
 
+void git_vector_sort(git_vector *v);
+
 int git_vector_search(git_vector *v, const void *entry);
 int git_vector_search2(git_vector *v, git_vector_cmp cmp, const void *key);
 
-int git_vector_bsearch(git_vector *v, const void *entry);
-int git_vector_bsearch2(git_vector *v, git_vector_cmp cmp, const void *key);
+int git_vector_bsearch3(
+	unsigned int *at_pos, git_vector *v, git_vector_cmp cmp, const void *key);
 
-void git_vector_sort(git_vector *v);
+GIT_INLINE(int) git_vector_bsearch(git_vector *v, const void *key)
+{
+	return git_vector_bsearch3(NULL, v, v->_cmp, key);
+}
+
+GIT_INLINE(int) git_vector_bsearch2(
+	git_vector *v, git_vector_cmp cmp, const void *key)
+{
+	return git_vector_bsearch3(NULL, v, cmp, key);
+}
 
 GIT_INLINE(void *) git_vector_get(git_vector *v, unsigned int position)
 {
diff --git a/tests-clar/core/buffer.c b/tests-clar/core/buffer.c
index 9294ccdfd..6a718f459 100644
--- a/tests-clar/core/buffer.c
+++ b/tests-clar/core/buffer.c
@@ -561,3 +561,53 @@ void test_core_buffer__10(void)
 
 	git_buf_free(&a);
 }
+
+void test_core_buffer__11(void)
+{
+	git_buf a = GIT_BUF_INIT;
+	git_strarray t;
+	char *t1[] = { "nothing", "in", "common" };
+	char *t2[] = { "something", "something else", "some other" };
+	char *t3[] = { "something", "some fun", "no fun" };
+	char *t4[] = { "happy", "happier", "happiest" };
+	char *t5[] = { "happiest", "happier", "happy" };
+	char *t6[] = { "no", "nope", "" };
+	char *t7[] = { "", "doesn't matter" };
+
+	t.strings = t1;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "");
+
+	t.strings = t2;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "some");
+
+	t.strings = t3;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "");
+
+	t.strings = t4;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "happ");
+
+	t.strings = t5;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "happ");
+
+	t.strings = t6;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "");
+
+	t.strings = t7;
+	t.count = 3;
+	cl_git_pass(git_buf_common_prefix(&a, &t));
+	cl_assert_equal_s(a.ptr, "");
+
+	git_buf_free(&a);
+}
diff --git a/tests-clar/diff/iterator.c b/tests-clar/diff/iterator.c
index 0ec2326eb..be29bea66 100644
--- a/tests-clar/diff/iterator.c
+++ b/tests-clar/diff/iterator.c
@@ -22,6 +22,8 @@ void test_diff_iterator__cleanup(void)
 static void tree_iterator_test(
 	const char *sandbox,
 	const char *treeish,
+	const char *start,
+	const char *end,
 	int expected_count,
 	const char **expected_values)
 {
@@ -32,7 +34,7 @@ static void tree_iterator_test(
 	git_repository *repo = cl_git_sandbox_init(sandbox);
 
 	cl_assert(t = resolve_commit_oid_to_tree(repo, treeish));
-	cl_git_pass(git_iterator_for_tree(repo, t, &i));
+	cl_git_pass(git_iterator_for_tree_range(&i, repo, t, start, end));
 	cl_git_pass(git_iterator_current(i, &entry));
 
 	while (entry != NULL) {
@@ -74,7 +76,7 @@ const char *expected_tree_0[] = {
 
 void test_diff_iterator__tree_0(void)
 {
-	tree_iterator_test("attr", "605812a", 16, expected_tree_0);
+	tree_iterator_test("attr", "605812a", NULL, NULL, 16, expected_tree_0);
 }
 
 /* results of: git ls-tree -r --name-only 6bab5c79 */
@@ -97,7 +99,7 @@ const char *expected_tree_1[] = {
 
 void test_diff_iterator__tree_1(void)
 {
-	tree_iterator_test("attr", "6bab5c79cd5", 13, expected_tree_1);
+	tree_iterator_test("attr", "6bab5c79cd5", NULL, NULL, 13, expected_tree_1);
 }
 
 /* results of: git ls-tree -r --name-only 26a125ee1 */
@@ -119,7 +121,7 @@ const char *expected_tree_2[] = {
 
 void test_diff_iterator__tree_2(void)
 {
-	tree_iterator_test("status", "26a125ee1", 12, expected_tree_2);
+	tree_iterator_test("status", "26a125ee1", NULL, NULL, 12, expected_tree_2);
 }
 
 /* $ git ls-tree -r --name-only 0017bd4ab1e */
@@ -136,7 +138,7 @@ const char *expected_tree_3[] = {
 
 void test_diff_iterator__tree_3(void)
 {
-	tree_iterator_test("status", "0017bd4ab1e", 8, expected_tree_3);
+	tree_iterator_test("status", "0017bd4ab1e", NULL, NULL, 8, expected_tree_3);
 }
 
 /* $ git ls-tree -r --name-only 24fa9a9fc4e202313e24b648087495441dab432b */
@@ -170,14 +172,77 @@ const char *expected_tree_4[] = {
 void test_diff_iterator__tree_4(void)
 {
 	tree_iterator_test(
-		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b", NULL, NULL,
 		23, expected_tree_4);
 }
 
+void test_diff_iterator__tree_4_ranged(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"sub", "sub",
+		11, &expected_tree_4[12]);
+}
+
+const char *expected_tree_ranged_0[] = {
+	"gitattributes",
+	"macro_bad",
+	"macro_test",
+	"root_test1",
+	"root_test2",
+	"root_test3",
+	"root_test4.txt",
+	NULL
+};
+
+void test_diff_iterator__tree_ranged_0(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"git", "root",
+		7, expected_tree_ranged_0);
+}
+
+const char *expected_tree_ranged_1[] = {
+	"sub/subdir_test2.txt",
+	NULL
+};
+
+void test_diff_iterator__tree_ranged_1(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"sub/subdir_test2.txt", "sub/subdir_test2.txt",
+		1, expected_tree_ranged_1);
+}
+
+void test_diff_iterator__tree_range_empty_0(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"empty", "empty", 0, NULL);
+}
+
+void test_diff_iterator__tree_range_empty_1(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		"z_empty_after", NULL, 0, NULL);
+}
+
+void test_diff_iterator__tree_range_empty_2(void)
+{
+	tree_iterator_test(
+		"attr", "24fa9a9fc4e202313e24b648087495441dab432b",
+		NULL, ".aaa_empty_before", 0, NULL);
+}
+
 /* -- INDEX ITERATOR TESTS -- */
 
 static void index_iterator_test(
 	const char *sandbox,
+	const char *start,
+	const char *end,
 	int expected_count,
 	const char **expected_names,
 	const char **expected_oids)
@@ -187,7 +252,7 @@ static void index_iterator_test(
 	int count = 0;
 	git_repository *repo = cl_git_sandbox_init(sandbox);
 
-	cl_git_pass(git_iterator_for_index(repo, &i));
+	cl_git_pass(git_iterator_for_index_range(&i, repo, start, end));
 	cl_git_pass(git_iterator_current(i, &entry));
 
 	while (entry != NULL) {
@@ -197,7 +262,7 @@ static void index_iterator_test(
 		if (expected_oids != NULL) {
 			git_oid oid;
 			cl_git_pass(git_oid_fromstr(&oid, expected_oids[count]));
-			cl_assert(git_oid_cmp(&oid, &entry->oid) == 0);
+			cl_assert_equal_i(git_oid_cmp(&oid, &entry->oid), 0);
 		}
 
 		count++;
@@ -206,7 +271,7 @@ static void index_iterator_test(
 
 	git_iterator_free(i);
 
-	cl_assert(count == expected_count);
+	cl_assert_equal_i(expected_count, count);
 }
 
 static const char *expected_index_0[] = {
@@ -263,7 +328,46 @@ static const char *expected_index_oids_0[] = {
 
 void test_diff_iterator__index_0(void)
 {
-	index_iterator_test("attr", 23, expected_index_0, expected_index_oids_0);
+	index_iterator_test(
+		"attr", NULL, NULL, 23, expected_index_0, expected_index_oids_0);
+}
+
+static const char *expected_index_range[] = {
+	"root_test1",
+	"root_test2",
+	"root_test3",
+	"root_test4.txt",
+};
+
+static const char *expected_index_oids_range[] = {
+	"45141a79a77842c59a63229403220a4e4be74e3d",
+	"4d713dc48e6b1bd75b0d61ad078ba9ca3a56745d",
+	"108bb4e7fd7b16490dc33ff7d972151e73d7166e",
+	"fe773770c5a6cc7185580c9204b1ff18a33ff3fc",
+};
+
+void test_diff_iterator__index_range(void)
+{
+	index_iterator_test(
+		"attr", "root", "root", 4, expected_index_range, expected_index_oids_range);
+}
+
+void test_diff_iterator__index_range_empty_0(void)
+{
+	index_iterator_test(
+		"attr", "empty", "empty", 0, NULL, NULL);
+}
+
+void test_diff_iterator__index_range_empty_1(void)
+{
+	index_iterator_test(
+		"attr", "z_empty_after", NULL, 0, NULL, NULL);
+}
+
+void test_diff_iterator__index_range_empty_2(void)
+{
+	index_iterator_test(
+		"attr", NULL, ".aaa_empty_before", 0, NULL, NULL);
 }
 
 static const char *expected_index_1[] = {
@@ -300,7 +404,8 @@ static const char* expected_index_oids_1[] = {
 
 void test_diff_iterator__index_1(void)
 {
-	index_iterator_test("status", 13, expected_index_1, expected_index_oids_1);
+	index_iterator_test(
+		"status", NULL, NULL, 13, expected_index_1, expected_index_oids_1);
 }
 
 
@@ -308,6 +413,8 @@ void test_diff_iterator__index_1(void)
 
 static void workdir_iterator_test(
 	const char *sandbox,
+	const char *start,
+	const char *end,
 	int expected_count,
 	int expected_ignores,
 	const char **expected_names,
@@ -318,7 +425,7 @@ static void workdir_iterator_test(
 	int count = 0, count_all = 0;
 	git_repository *repo = cl_git_sandbox_init(sandbox);
 
-	cl_git_pass(git_iterator_for_workdir(repo, &i));
+	cl_git_pass(git_iterator_for_workdir_range(&i, repo, start, end));
 	cl_git_pass(git_iterator_current(i, &entry));
 
 	while (entry != NULL) {
@@ -350,7 +457,7 @@ static void workdir_iterator_test(
 
 void test_diff_iterator__workdir_0(void)
 {
-	workdir_iterator_test("attr", 25, 2, NULL, "ign");
+	workdir_iterator_test("attr", NULL, NULL, 25, 2, NULL, "ign");
 }
 
 static const char *status_paths[] = {
@@ -372,5 +479,92 @@ static const char *status_paths[] = {
 
 void test_diff_iterator__workdir_1(void)
 {
-	workdir_iterator_test("status", 12, 1, status_paths, "ignored_file");
+	workdir_iterator_test(
+		"status", NULL, NULL, 12, 1, status_paths, "ignored_file");
+}
+
+static const char *status_paths_range_0[] = {
+	"staged_changes",
+	"staged_changes_modified_file",
+	"staged_delete_modified_file",
+	"staged_new_file",
+	"staged_new_file_modified_file",
+	NULL
+};
+
+void test_diff_iterator__workdir_1_ranged_0(void)
+{
+	workdir_iterator_test(
+		"status", "staged", "staged", 5, 0, status_paths_range_0, NULL);
+}
+
+static const char *status_paths_range_1[] = {
+	"modified_file", NULL
+};
+
+void test_diff_iterator__workdir_1_ranged_1(void)
+{
+	workdir_iterator_test(
+		"status", "modified_file", "modified_file",
+		1, 0, status_paths_range_1, NULL);
+}
+
+static const char *status_paths_range_3[] = {
+	"subdir.txt",
+	"subdir/current_file",
+	"subdir/modified_file",
+	NULL
+};
+
+void test_diff_iterator__workdir_1_ranged_3(void)
+{
+	workdir_iterator_test(
+		"status", "subdir", "subdir/modified_file",
+		3, 0, status_paths_range_3, NULL);
+}
+
+static const char *status_paths_range_4[] = {
+	"subdir/current_file",
+	"subdir/modified_file",
+	"subdir/new_file",
+	NULL
+};
+
+void test_diff_iterator__workdir_1_ranged_4(void)
+{
+	workdir_iterator_test(
+		"status", "subdir/", NULL, 3, 0, status_paths_range_4, NULL);
+}
+
+static const char *status_paths_range_5[] = {
+	"subdir/modified_file",
+	NULL
+};
+
+void test_diff_iterator__workdir_1_ranged_5(void)
+{
+	workdir_iterator_test(
+		"status", "subdir/modified_file", "subdir/modified_file",
+		1, 0, status_paths_range_5, NULL);
+}
+
+void test_diff_iterator__workdir_1_ranged_empty_0(void)
+{
+	workdir_iterator_test(
+		"status", "z_does_not_exist", NULL,
+		0, 0, NULL, NULL);
+}
+
+void test_diff_iterator__workdir_1_ranged_empty_1(void)
+{
+	workdir_iterator_test(
+		"status", "empty", "empty",
+		0, 0, NULL, NULL);
+}
+
+void test_diff_iterator__workdir_1_ranged_empty_2(void)
+{
+	workdir_iterator_test(
+		"status", NULL, "aaaa_empty_before",
+		0, 0, NULL, NULL);
 }
diff --git a/tests-clar/status/submodules.c b/tests-clar/status/submodules.c
index de971be19..9423e8490 100644
--- a/tests-clar/status/submodules.c
+++ b/tests-clar/status/submodules.c
@@ -103,3 +103,10 @@ void test_status_submodules__1(void)
 
 	cl_assert(index == 6);
 }
+
+void test_status_submodules__single_file(void)
+{
+	unsigned int status;
+	cl_git_pass( git_status_file(&status, g_repo, "testrepo") );
+	cl_assert(status == 0);
+}