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