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.

1 files changed, 241 insertions, 62 deletions

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);
+}
+