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.

14 files changed, 476 insertions, 304 deletions

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)
 {