Merge pull request #1408 from arrbee/refactor-iterators

Refactor iterators

1 files changed, 650 insertions, 506 deletions

diff --git a/src/iterator.c b/src/iterator.c
index 8ad639d6b..e6e0ea481 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -14,26 +14,45 @@
 
 #define ITERATOR_SET_CB(P,NAME_LC) do { \
 	(P)->cb.current = NAME_LC ## _iterator__current; \
-	(P)->cb.at_end  = NAME_LC ## _iterator__at_end; \
 	(P)->cb.advance = NAME_LC ## _iterator__advance; \
+	(P)->cb.advance_into = NAME_LC ## _iterator__advance_into; \
 	(P)->cb.seek    = NAME_LC ## _iterator__seek; \
 	(P)->cb.reset   = NAME_LC ## _iterator__reset; \
+	(P)->cb.at_end  = NAME_LC ## _iterator__at_end; \
 	(P)->cb.free    = NAME_LC ## _iterator__free; \
 	} while (0)
 
-#define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC) do { \
+#define ITERATOR_CASE_FLAGS \
+	(GIT_ITERATOR_IGNORE_CASE | GIT_ITERATOR_DONT_IGNORE_CASE)
+
+#define ITERATOR_BASE_INIT(P,NAME_LC,NAME_UC,REPO) do { \
 	(P) = git__calloc(1, sizeof(NAME_LC ## _iterator)); \
 	GITERR_CHECK_ALLOC(P); \
 	(P)->base.type    = GIT_ITERATOR_TYPE_ ## NAME_UC; \
-	(P)->base.cb    = &(P)->cb; \
+	(P)->base.cb      = &(P)->cb; \
 	ITERATOR_SET_CB(P,NAME_LC); \
+	(P)->base.repo    = (REPO); \
 	(P)->base.start   = start ? git__strdup(start) : NULL; \
 	(P)->base.end     = end ? git__strdup(end) : NULL; \
 	if ((start && !(P)->base.start) || (end && !(P)->base.end)) { \
 		git__free(P); return -1; } \
 	(P)->base.prefixcomp = git__prefixcmp; \
+	(P)->base.flags = flags & ~ITERATOR_CASE_FLAGS; \
+	if ((P)->base.flags & GIT_ITERATOR_DONT_AUTOEXPAND) \
+		(P)->base.flags |= GIT_ITERATOR_INCLUDE_TREES; \
 	} while (0)
 
+#define iterator__flag(I,F) ((((git_iterator *)(I))->flags & GIT_ITERATOR_ ## F) != 0)
+#define iterator__ignore_case(I)     iterator__flag(I,IGNORE_CASE)
+#define iterator__include_trees(I)   iterator__flag(I,INCLUDE_TREES)
+#define iterator__dont_autoexpand(I) iterator__flag(I,DONT_AUTOEXPAND)
+#define iterator__do_autoexpand(I)   !iterator__flag(I,DONT_AUTOEXPAND)
+
+#define iterator__end(I) ((git_iterator *)(I))->end
+#define iterator__past_end(I,PATH) \
+	(iterator__end(I) && ((git_iterator *)(I))->prefixcomp((PATH),iterator__end(I)) > 0)
+
+
 static int iterator__reset_range(
 	git_iterator *iter, const char *start, const char *end)
 {
@@ -54,7 +73,7 @@ static int iterator__reset_range(
 	return 0;
 }
 
-static int iterator_update_ignore_case(
+static int iterator__update_ignore_case(
 	git_iterator *iter,
 	git_iterator_flag_t flags)
 {
@@ -76,42 +95,46 @@ static int iterator_update_ignore_case(
 	else if (ignore_case == 0)
 		iter->flags = (iter->flags & ~GIT_ITERATOR_IGNORE_CASE);
 
-	iter->prefixcomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
+	iter->prefixcomp = iterator__ignore_case(iter) ?
 		git__prefixcmp_icase : git__prefixcmp;
 
 	return error;
 }
 
-static int empty_iterator__no_item(
-	git_iterator *iter, const git_index_entry **entry)
+GIT_INLINE(void) iterator__clear_entry(const git_index_entry **entry)
+{
+	if (entry) *entry = NULL;
+}
+
+
+static int empty_iterator__noop(const git_index_entry **e, git_iterator *i)
 {
-	GIT_UNUSED(iter);
-	*entry = NULL;
+	GIT_UNUSED(i);
+	iterator__clear_entry(e);
 	return 0;
 }
 
-static int empty_iterator__at_end(git_iterator *iter)
+static int empty_iterator__seek(git_iterator *i, const char *p)
 {
-	GIT_UNUSED(iter);
-	return 1;
+	GIT_UNUSED(i); GIT_UNUSED(p);
+	return -1;
 }
 
-static int empty_iterator__reset(
-	git_iterator *iter, const char *start, const char *end)
+static int empty_iterator__reset(git_iterator *i, const char *s, const char *e)
 {
-	GIT_UNUSED(iter); GIT_UNUSED(start); GIT_UNUSED(end);
+	GIT_UNUSED(i); GIT_UNUSED(s); GIT_UNUSED(e);
 	return 0;
 }
 
-static int empty_iterator__seek(git_iterator *iter, const char *prefix)
+static int empty_iterator__at_end(git_iterator *i)
 {
-	GIT_UNUSED(iter); GIT_UNUSED(prefix);
-	return -1;
+	GIT_UNUSED(i);
+	return 1;
 }
 
-static void empty_iterator__free(git_iterator *iter)
+static void empty_iterator__free(git_iterator *i)
 {
-	GIT_UNUSED(iter);
+	GIT_UNUSED(i);
 }
 
 typedef struct {
@@ -119,56 +142,82 @@ typedef struct {
 	git_iterator_callbacks cb;
 } empty_iterator;
 
-int git_iterator_for_nothing(git_iterator **iter, git_iterator_flag_t flags)
+int git_iterator_for_nothing(
+	git_iterator **iter,
+	git_iterator_flag_t flags,
+	const char *start,
+	const char *end)
 {
 	empty_iterator *i = git__calloc(1, sizeof(empty_iterator));
 	GITERR_CHECK_ALLOC(i);
 
-	i->base.type  = GIT_ITERATOR_TYPE_EMPTY;
-	i->base.cb    = &i->cb;
-	i->base.flags = flags;
-	i->cb.current = empty_iterator__no_item;
-	i->cb.at_end  = empty_iterator__at_end;
-	i->cb.advance = empty_iterator__no_item;
-	i->cb.seek    = empty_iterator__seek;
-	i->cb.reset   = empty_iterator__reset;
-	i->cb.free    = empty_iterator__free;
+#define empty_iterator__current empty_iterator__noop
+#define empty_iterator__advance empty_iterator__noop
+#define empty_iterator__advance_into empty_iterator__noop
 
-	*iter = (git_iterator *)i;
+	ITERATOR_BASE_INIT(i, empty, EMPTY, NULL);
 
+	if ((flags & GIT_ITERATOR_IGNORE_CASE) != 0)
+		i->base.flags |= GIT_ITERATOR_IGNORE_CASE;
+
+	*iter = (git_iterator *)i;
 	return 0;
 }
 
 
+typedef struct {
+	size_t parent_entry_index;  /* index in parent entries array */
+	size_t parent_tree_index;   /* index in parent entry tree */
+	git_tree *tree; /* this tree if this is tree (only valid while current) */
+} tree_iterator_entry;
+
 typedef struct tree_iterator_frame tree_iterator_frame;
 struct tree_iterator_frame {
-	tree_iterator_frame *next, *prev;
-	git_tree *tree;
-	char *start;
+	tree_iterator_frame *parent, *child;
+
+	size_t n_entries; /* items in this frame */
+	size_t current;   /* start of currently active range in frame */
+	size_t next;      /* start of next range in frame */
+
+	const char *start;
 	size_t startlen;
-	size_t index;
-	void **icase_map;
-	void *icase_data[GIT_FLEX_ARRAY];
+
+	tree_iterator_entry entries[GIT_FLEX_ARRAY];
 };
 
 typedef struct {
 	git_iterator base;
 	git_iterator_callbacks cb;
-	tree_iterator_frame *stack, *tail;
+	tree_iterator_frame *head, *top;
 	git_index_entry entry;
 	git_buf path;
+	int path_ambiguities;
 	bool path_has_filename;
+	int (*strncomp)(const char *a, const char *b, size_t sz);
 } tree_iterator;
 
-GIT_INLINE(const git_tree_entry *)tree_iterator__tree_entry(tree_iterator *ti)
+static const git_tree_entry *tree_iterator__tree_entry(
+	tree_iterator_frame *tf, const tree_iterator_entry *entry)
 {
-	tree_iterator_frame *tf = ti->stack;
+	git_tree *tree = tf->parent->entries[entry->parent_entry_index].tree;
+	if (!tree)
+		return NULL;
+	return git_tree_entry_byindex(tree, entry->parent_tree_index);
+}
 
-	if (tf->index >= git_tree_entrycount(tf->tree))
+static const git_tree_entry *tree_iterator__tree_entry_by_index(
+	tree_iterator_frame *tf, size_t i)
+{
+	git_tree *tree;
+
+	if (i >= tf->n_entries)
+		return NULL;
+
+	tree = tf->parent->entries[tf->entries[i].parent_entry_index].tree;
+	if (!tree)
 		return NULL;
 
-	return git_tree_entry_byindex(
-		tf->tree, tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
+	return git_tree_entry_byindex(tree, tf->entries[i].parent_tree_index);
 }
 
 static char *tree_iterator__current_filename(
@@ -177,274 +226,379 @@ static char *tree_iterator__current_filename(
 	if (!ti->path_has_filename) {
 		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
 			return NULL;
+
+		if (git_tree_entry__is_tree(te) && git_buf_putc(&ti->path, '/') < 0)
+			return NULL;
+
 		ti->path_has_filename = true;
 	}
 
 	return ti->path.ptr;
 }
 
-static void tree_iterator__free_frame(tree_iterator_frame *tf)
+static void tree_iterator__rewrite_filename(tree_iterator *ti)
 {
-	if (!tf)
-		return;
+	tree_iterator_frame *scan = ti->head;
+	size_t current = scan->current;
+	ssize_t strpos = ti->path.size;
+	const git_tree_entry *te;
 
-	git_tree_free(tf->tree);
-	tf->tree = NULL;
+	if (strpos && ti->path.ptr[strpos - 1] == '/')
+		strpos--;
 
-	git__free(tf);
+	while (scan && scan->parent) {
+		tree_iterator_entry *entry = &scan->entries[current];
+
+		if (!(te = tree_iterator__tree_entry(scan, entry)))
+			break;
+
+		strpos -= te->filename_len;
+		memcpy(&ti->path.ptr[strpos], te->filename, te->filename_len);
+		strpos -= 1; /* separator */
+
+		current = entry->parent_entry_index;
+		scan = scan->parent;
+	}
 }
 
-static bool tree_iterator__pop_frame(tree_iterator *ti)
+static int tree_iterator__tree_entry_cmp(
+	const git_tree_entry *a,
+	const git_tree_entry *b,
+	int (*strncomp)(const char *, const char *, size_t))
 {
-	tree_iterator_frame *tf = ti->stack;
+	size_t common = min(a->filename_len, b->filename_len);
+	int cmp = strncomp(a->filename, b->filename, common);
 
-	/* don't free the initial tree/frame */
-	if (!tf->next)
-		return false;
+	if (!cmp) {
+		char a_next = a->filename[common], b_next = b->filename[common];
 
-	ti->stack = tf->next;
-	ti->stack->prev = NULL;
+		if (!a_next && a->attr == GIT_FILEMODE_TREE)
+			a_next = '/';
+		if (!b_next && b->attr == GIT_FILEMODE_TREE)
+			b_next = '/';
 
-	tree_iterator__free_frame(tf);
+		cmp = (int)a_next - (int)b_next;
+	}
 
-	return true;
+	return cmp;
 }
 
-static int tree_iterator__to_end(tree_iterator *ti)
+static int tree_iterator__entry_cmp(const void *a, const void *b, void *p)
 {
-	while (tree_iterator__pop_frame(ti)) /* pop all */;
-	ti->stack->index = git_tree_entrycount(ti->stack->tree);
-	return 0;
+	const tree_iterator_entry *ae = a, *be = b;
+	const git_tree_entry *ate = tree_iterator__tree_entry(p, ae);
+	const git_tree_entry *bte = tree_iterator__tree_entry(p, be);
+	int cmp = tree_iterator__tree_entry_cmp(ate, bte, git__strncasecmp);
+
+	/* stabilize sort order among equivalent names */
+	if (!cmp) {
+		cmp = (ae->parent_entry_index < be->parent_entry_index) ? -1 :
+			(ae->parent_entry_index > be->parent_entry_index) ? 1 : 0;
+		if (!cmp)
+			cmp = (ae->parent_tree_index < be->parent_tree_index) ? -1 :
+				(ae->parent_tree_index > be->parent_tree_index) ? 1 : 0;
+	}
+
+	return cmp;
 }
 
-static int tree_iterator__current(
-	git_iterator *self, const git_index_entry **entry)
+static int tree_iterator__set_next(tree_iterator *ti, tree_iterator_frame *tf)
 {
-	tree_iterator *ti = (tree_iterator *)self;
-	const git_tree_entry *te = tree_iterator__tree_entry(ti);
+	/* find next and load trees for current range */
+	int error = 0;
+	const git_tree_entry *te, *last = NULL;
 
-	if (entry)
-		*entry = NULL;
+	tf->next = tf->current;
 
-	if (te == NULL)
-		return 0;
+	while (tf->next < tf->n_entries) {
+		if (!(te = tree_iterator__tree_entry_by_index(tf, tf->next)) ||
+			(last && tree_iterator__tree_entry_cmp(last, te, ti->strncomp)))
+			break;
 
-	ti->entry.mode = te->attr;
-	git_oid_cpy(&ti->entry.oid, &te->oid);
+		if (git_tree_entry__is_tree(te) &&
+			(error = git_tree_lookup(
+				&tf->entries[tf->next].tree, ti->base.repo, &te->oid)) < 0)
+			break;
 
-	ti->entry.path = tree_iterator__current_filename(ti, te);
-	if (ti->entry.path == NULL)
-		return -1;
+		tf->next++;
+		last = te;
+	}
 
-	if (ti->base.end && ti->base.prefixcomp(ti->entry.path, ti->base.end) > 0)
-		return tree_iterator__to_end(ti);
+	if (tf->next > tf->current + 1)
+		ti->path_ambiguities++;
 
-	if (entry)
-		*entry = &ti->entry;
+	if (last && !tree_iterator__current_filename(ti, last))
+		return -1;
 
-	return 0;
+	return error;
 }
 
-static int tree_iterator__at_end(git_iterator *self)
+GIT_INLINE(bool) tree_iterator__at_tree(tree_iterator *ti)
 {
-	return (tree_iterator__tree_entry((tree_iterator *)self) == NULL);
+	return (ti->head->current < ti->head->n_entries &&
+			ti->head->entries[ti->head->current].tree != NULL);
 }
 
-static int tree_iterator__icase_map_cmp(const void *a, const void *b, void *data)
+static int tree_iterator__push_frame(tree_iterator *ti)
 {
-	git_tree *tree = data;
-	const git_tree_entry *te1 = git_tree_entry_byindex(tree, (size_t)a);
-	const git_tree_entry *te2 = git_tree_entry_byindex(tree, (size_t)b);
+	int error = 0;
+	tree_iterator_frame *tf = ti->head, *new_tf = NULL;
+	size_t i, n_entries = 0, sz = sizeof(tree_iterator_frame);
+	const git_tree_entry *te;
 
-	return te1 ? (te2 ? git_tree_entry_icmp(te1, te2) : 1) : -1;
-}
+	/* if current item in head is not a tree, do nothing */
+	if (tf->current >= tf->n_entries || !tf->entries[tf->current].tree)
+		return 0;
 
-static int tree_iterator__frame_start_icmp(const void *key, const void *el)
-{
-	const tree_iterator_frame *tf = (const tree_iterator_frame *)key;
-	const git_tree_entry *te = git_tree_entry_byindex(tf->tree, (size_t)el);
-	size_t minlen = min(tf->startlen, te->filename_len);
+	/* build frame - sum tree entries from parent range */
+	for (i = tf->current; i < tf->next; ++i)
+		n_entries += git_tree_entrycount(tf->entries[i].tree);
+	sz += n_entries * sizeof(tree_iterator_entry);
+	new_tf = git__calloc(sz, sizeof(char));
+	GITERR_CHECK_ALLOC(new_tf);
+
+	/* populate frame and entries */
+	new_tf->parent = tf;
+	new_tf->n_entries = n_entries;
+
+	for (i = tf->current, n_entries = 0; i < tf->next; ++i) {
+		git_tree *tree = tf->entries[i].tree;
+		size_t j, max_j = git_tree_entrycount(tree);
+
+		for (j = 0; j < max_j; ++j) {
+			new_tf->entries[n_entries].parent_entry_index = i;
+			new_tf->entries[n_entries].parent_tree_index = j;
+			n_entries++;
+		}
+	}
 
-	return git__strncasecmp(tf->start, te->filename, minlen);
-}
+	/* if ignore_case, sort entries case insensitively */
+	if (iterator__ignore_case(ti))
+		git__qsort_r(
+			new_tf->entries, new_tf->n_entries, sizeof(tree_iterator_entry),
+			tree_iterator__entry_cmp, new_tf);
+
+	/* pick new_tf->current based on "start" (or start at zero) */
+	if (tf->startlen > 0) {
+		/* find first item >= start */
+		for (i = 0; i < new_tf->n_entries; ++i) {
+			if (!(te = tree_iterator__tree_entry_by_index(new_tf, i)))
+				break;
+			sz = min(tf->startlen, te->filename_len);
+			if (ti->strncomp(tf->start, te->filename, sz) <= 0 &&
+				(tf->startlen <= te->filename_len ||
+				 tf->start[te->filename_len] == '/'))
+				break;
+		}
+		new_tf->current = i;
 
-static void tree_iterator__frame_seek_start(tree_iterator_frame *tf)
-{
-	if (!tf->start)
-		tf->index = 0;
-	else if (!tf->icase_map)
-		tf->index = git_tree__prefix_position(tf->tree, tf->start);
-	else {
-		if (!git__bsearch(
-				tf->icase_map, git_tree_entrycount(tf->tree),
-				tf, tree_iterator__frame_start_icmp, &tf->index))
-		{
-			while (tf->index > 0) {
-				/* move back while previous entry is still prefixed */
-				if (tree_iterator__frame_start_icmp(
-						tf, (const void *)(tf->index - 1)))
-					break;
-				tf->index--;
-			}
+		if ((new_tf->start = strchr(tf->start, '/')) != NULL) {
+			new_tf->start++;
+			new_tf->startlen = strlen(new_tf->start);
 		}
 	}
+
+	ti->path_has_filename = false;
+
+	/* find next and load trees for current range */
+	if ((error = tree_iterator__set_next(ti, new_tf)) < 0)
+		return error;
+
+	tf->child = new_tf;
+	ti->head  = new_tf;
+
+	if (!iterator__include_trees(ti) && tree_iterator__at_tree(ti))
+		return tree_iterator__push_frame(ti);
+
+	return 0;
 }
 
-static tree_iterator_frame *tree_iterator__alloc_frame(
-	tree_iterator *ti, git_tree *tree, char *start)
+GIT_INLINE(void) tree_iterator__free_tree(tree_iterator_entry *entry)
 {
-	size_t i, max_i = git_tree_entrycount(tree);
-	tree_iterator_frame *tf =
-		git__calloc(1, sizeof(tree_iterator_frame) + max_i * sizeof(void *));
-	if (!tf)
-		return NULL;
+	if (entry->tree) {
+		git_tree_free(entry->tree);
+		entry->tree = NULL;
+	}
+}
 
-	tf->tree = tree;
+static bool tree_iterator__move_to_next(
+	tree_iterator *ti, tree_iterator_frame *tf)
+{
+	if (tf->next > tf->current + 1)
+		ti->path_ambiguities--;
 
-	if (start && *start) {
-		tf->start = start;
-		tf->startlen = strlen(start);
+	for (; tf->current < tf->next; tf->current++) {
+		if (tf->parent)
+			tree_iterator__free_tree(&tf->entries[tf->current]);
 	}
 
-	if (!max_i)
-		return tf;
+	return (tf->current < tf->n_entries);
+}
 
-	if ((ti->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0) {
-		tf->icase_map = tf->icase_data;
+static bool tree_iterator__pop_frame(tree_iterator *ti)
+{
+	tree_iterator_frame *tf = ti->head;
 
-		for (i = 0; i < max_i; ++i)
-			tf->icase_map[i] = (void *)i;
+	if (!tf->parent)
+		return false;
 
-		git__tsort_r(
-			tf->icase_map, max_i, tree_iterator__icase_map_cmp, tf->tree);
-	}
+	tree_iterator__move_to_next(ti, tf);
 
-	tree_iterator__frame_seek_start(tf);
+	ti->head = tf->parent;
+	ti->head->child = NULL;
+	git__free(tf);
+
+	git_buf_rtruncate_at_char(&ti->path, '/');
 
-	return tf;
+	return true;
 }
 
-static int tree_iterator__expand_tree(tree_iterator *ti)
+static int tree_iterator__current(
+	const git_index_entry **entry, git_iterator *self)
 {
-	int error;
-	git_tree *subtree;
-	const git_tree_entry *te = tree_iterator__tree_entry(ti);
-	tree_iterator_frame *tf;
-	char *relpath;
-
-	while (te != NULL && git_tree_entry__is_tree(te)) {
-		if (git_buf_joinpath(&ti->path, ti->path.ptr, te->filename) < 0)
-			return -1;
+	tree_iterator *ti = (tree_iterator *)self;
+	tree_iterator_frame *tf = ti->head;
+	const git_tree_entry *te;
 
-		/* check that we have not passed the range end */
-		if (ti->base.end != NULL &&
-			ti->base.prefixcomp(ti->path.ptr, ti->base.end) > 0)
-			return tree_iterator__to_end(ti);
+	iterator__clear_entry(entry);
 
-		if ((error = git_tree_lookup(&subtree, ti->base.repo, &te->oid)) < 0)
-			return error;
-
-		relpath = NULL;
+	if (!(te = tree_iterator__tree_entry_by_index(tf, tf->current)))
+		return 0;
 
-		/* apply range start to new frame if relevant */
-		if (ti->stack->start &&
-			ti->base.prefixcomp(ti->stack->start, te->filename) == 0)
-		{
-			if (ti->stack->start[te->filename_len] == '/')
-				relpath = ti->stack->start + te->filename_len + 1;
-		}
+	ti->entry.mode = te->attr;
+	git_oid_cpy(&ti->entry.oid, &te->oid);
 
-		if ((tf = tree_iterator__alloc_frame(ti, subtree, relpath)) == NULL)
-			return -1;
+	ti->entry.path = tree_iterator__current_filename(ti, te);
+	if (ti->entry.path == NULL)
+		return -1;
 
-		tf->next  = ti->stack;
-		ti->stack = tf;
-		tf->next->prev = tf;
+	if (ti->path_ambiguities > 0)
+		tree_iterator__rewrite_filename(ti);
 
-		te = tree_iterator__tree_entry(ti);
+	if (iterator__past_end(ti, ti->entry.path)) {
+		while (tree_iterator__pop_frame(ti)) /* pop to top */;
+		ti->head->current = ti->head->n_entries;
+		return 0;
 	}
 
+	if (entry)
+		*entry = &ti->entry;
+
 	return 0;
 }
 
-static int tree_iterator__advance(
-	git_iterator *self, const git_index_entry **entry)
+static int tree_iterator__advance_into(
+	const git_index_entry **entry, git_iterator *self)
 {
 	int error = 0;
 	tree_iterator *ti = (tree_iterator *)self;
-	const git_tree_entry *te = NULL;
 
-	if (entry != NULL)
-		*entry = NULL;
+	iterator__clear_entry(entry);
 
-	if (ti->path_has_filename) {
-		git_buf_rtruncate_at_char(&ti->path, '/');
-		ti->path_has_filename = false;
-	}
+	if (tree_iterator__at_tree(ti) &&
+		!(error = tree_iterator__push_frame(ti)))
+		error = tree_iterator__current(entry, self);
 
-	while (1) {
-		++ti->stack->index;
+	return error;
+}
 
-		if ((te = tree_iterator__tree_entry(ti)) != NULL)
-			break;
+static int tree_iterator__advance(
+	const git_index_entry **entry, git_iterator *self)
+{
+	int error;
+	tree_iterator *ti = (tree_iterator *)self;
+	tree_iterator_frame *tf = ti->head;
+
+	iterator__clear_entry(entry);
+
+	if (tf->current > tf->n_entries)
+		return 0;
 
-		if (!tree_iterator__pop_frame(ti))
-			break; /* no frames left to pop */
+	if (iterator__do_autoexpand(ti) && iterator__include_trees(ti) &&
+		tree_iterator__at_tree(ti))
+		return tree_iterator__advance_into(entry, self);
 
+	if (ti->path_has_filename) {
 		git_buf_rtruncate_at_char(&ti->path, '/');
+		ti->path_has_filename = false;
 	}
 
-	if (te && git_tree_entry__is_tree(te))
-		error = tree_iterator__expand_tree(ti);
+	/* scan forward and up, advancing in frame or popping frame when done */
+	while (!tree_iterator__move_to_next(ti, tf) && tree_iterator__pop_frame(ti))
+		tf = ti->head;
 
-	if (!error)
-		error = tree_iterator__current(self, entry);
+	/* find next and load trees */
+	if ((error = tree_iterator__set_next(ti, tf)) < 0)
+		return error;
 
-	return error;
+	/* deal with include_trees / auto_expand as needed */
+	if (!iterator__include_trees(ti) && tree_iterator__at_tree(ti))
+		return tree_iterator__advance_into(entry, self);
+
+	return tree_iterator__current(entry, self);
 }
 
 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 */
+	GIT_UNUSED(self); GIT_UNUSED(prefix);
 	return -1;
 }
 
-static void tree_iterator__free(git_iterator *self)
+static int tree_iterator__reset(
+	git_iterator *self, const char *start, const char *end)
 {
 	tree_iterator *ti = (tree_iterator *)self;
 
-	while (tree_iterator__pop_frame(ti)) /* pop all */;
+	while (tree_iterator__pop_frame(ti)) /* pop to top */;
+	ti->top->current = 0;
 
-	tree_iterator__free_frame(ti->stack);
-	ti->stack = ti->tail = NULL;
+	if (iterator__reset_range(self, start, end) < 0)
+		return -1;
+	git_buf_clear(&ti->path);
+	ti->path_ambiguities = 0;
 
-	git_buf_free(&ti->path);
+	return tree_iterator__push_frame(ti); /* re-expand top tree */
 }
 
-static int tree_iterator__reset(
-	git_iterator *self, const char *start, const char *end)
+static int tree_iterator__at_end(git_iterator *self)
 {
 	tree_iterator *ti = (tree_iterator *)self;
+	return (ti->head->current >= ti->head->n_entries);
+}
 
-	while (tree_iterator__pop_frame(ti)) /* pop all */;
+static void tree_iterator__free(git_iterator *self)
+{
+	tree_iterator *ti = (tree_iterator *)self;
 
-	if (iterator__reset_range(self, start, end) < 0)
-		return -1;
+	while (tree_iterator__pop_frame(ti)) /* pop to top */;
 
-	/* reset start position */
-	tree_iterator__frame_seek_start(ti->stack);
+	if (ti->head) {
+		tree_iterator__free_tree(&ti->head->entries[0]);
+		git__free(ti->head);
+	}
+	ti->head = ti->top = NULL;
 
-	git_buf_clear(&ti->path);
-	ti->path_has_filename = false;
+	git_buf_free(&ti->path);
+}
+
+static int tree_iterator__create_top_frame(tree_iterator *ti, git_tree *tree)
+{
+	size_t sz = sizeof(tree_iterator_frame) + sizeof(tree_iterator_entry);
+	tree_iterator_frame *top = git__calloc(sz, sizeof(char));
+	GITERR_CHECK_ALLOC(top);
+
+	top->n_entries = 1;
+	top->next = 1;
+	top->start = ti->base.start;
+	top->startlen = top->start ? strlen(top->start) : 0;
+	top->entries[0].tree = tree;
+
+	ti->head = ti->top = top;
 
-	return tree_iterator__expand_tree(ti);
+	return 0;
 }
 
-int git_iterator_for_tree_range(
+int git_iterator_for_tree(
 	git_iterator **iter,
 	git_tree *tree,
 	git_iterator_flag_t flags,
@@ -455,21 +609,19 @@ int git_iterator_for_tree_range(
 	tree_iterator *ti;
 
 	if (tree == NULL)
-		return git_iterator_for_nothing(iter, flags);
+		return git_iterator_for_nothing(iter, flags, start, end);
 
 	if ((error = git_tree__dup(&tree, tree)) < 0)
 		return error;
 
-	ITERATOR_BASE_INIT(ti, tree, TREE);
-
-	ti->base.repo = git_tree_owner(tree);
+	ITERATOR_BASE_INIT(ti, tree, TREE, git_tree_owner(tree));
 
-	if ((error = iterator_update_ignore_case((git_iterator *)ti, flags)) < 0)
+	if ((error = iterator__update_ignore_case((git_iterator *)ti, flags)) < 0)
 		goto fail;
+	ti->strncomp = iterator__ignore_case(ti) ? git__strncasecmp : git__strncmp;
 
-	ti->stack = ti->tail = tree_iterator__alloc_frame(ti, tree, ti->base.start);
-
-	if ((error = tree_iterator__expand_tree(ti)) < 0)
+	if ((error = tree_iterator__create_top_frame(ti, tree)) < 0 ||
+		(error = tree_iterator__push_frame(ti)) < 0) /* expand top right now */
 		goto fail;
 
 	*iter = (git_iterator *)ti;
@@ -486,14 +638,94 @@ typedef struct {
 	git_iterator_callbacks cb;
 	git_index *index;
 	size_t current;
+	/* when not in autoexpand mode, use these to represent "tree" state */
+	git_buf partial;
+	size_t partial_pos;
+	char restore_terminator;
+	git_index_entry tree_entry;
 } index_iterator;
 
+static const git_index_entry *index_iterator__index_entry(index_iterator *ii)
+{
+	const git_index_entry *ie = git_index_get_byindex(ii->index, ii->current);
+
+	if (ie != NULL && iterator__past_end(ii, ie->path)) {
+		ii->current = git_index_entrycount(ii->index);
+		ie = NULL;
+	}
+
+	return ie;
+}
+
+static const git_index_entry *index_iterator__skip_conflicts(index_iterator *ii)
+{
+	const git_index_entry *ie;
+
+	while ((ie = index_iterator__index_entry(ii)) != NULL &&
+		   git_index_entry_stage(ie) != 0)
+		ii->current++;
+
+	return ie;
+}
+
+static void index_iterator__next_prefix_tree(index_iterator *ii)
+{
+	const char *slash;
+
+	if (!iterator__include_trees(ii))
+		return;
+
+	slash = strchr(&ii->partial.ptr[ii->partial_pos], '/');
+
+	if (slash != NULL) {
+		ii->partial_pos = (slash - ii->partial.ptr) + 1;
+		ii->restore_terminator = ii->partial.ptr[ii->partial_pos];
+		ii->partial.ptr[ii->partial_pos] = '\0';
+	} else {
+		ii->partial_pos = ii->partial.size;
+	}
+
+	if (index_iterator__index_entry(ii) == NULL)
+		ii->partial_pos = ii->partial.size;
+}
+
+static int index_iterator__first_prefix_tree(index_iterator *ii)
+{
+	const git_index_entry *ie = index_iterator__skip_conflicts(ii);
+	const char *scan, *prior, *slash;
+
+	if (!ie || !iterator__include_trees(ii))
+		return 0;
+
+	/* find longest common prefix with prior index entry */
+	for (scan = slash = ie->path, prior = ii->partial.ptr;
+		 *scan && *scan == *prior; ++scan, ++prior)
+		if (*scan == '/')
+			slash = scan;
+
+	if (git_buf_sets(&ii->partial, ie->path) < 0)
+		return -1;
+
+	ii->partial_pos = (slash - ie->path) + 1;
+	index_iterator__next_prefix_tree(ii);
+
+	return 0;
+}
+
+#define index_iterator__at_tree(I) \
+	(iterator__include_trees(I) && (I)->partial_pos < (I)->partial.size)
+
 static int index_iterator__current(
-	git_iterator *self, const git_index_entry **entry)
+	const git_index_entry **entry, git_iterator *self)
 {
 	index_iterator *ii = (index_iterator *)self;
 	const git_index_entry *ie = git_index_get_byindex(ii->index, ii->current);
 
+	if (ie != NULL && index_iterator__at_tree(ii)) {
+		ii->tree_entry.path = ii->partial.ptr;
+		ie = &ii->tree_entry;
+	}
+
 	if (entry)
 		*entry = ie;
 
@@ -506,47 +738,59 @@ static int index_iterator__at_end(git_iterator *self)
 	return (ii->current >= git_index_entrycount(ii->index));
 }
 
-static void index_iterator__skip_conflicts(
-	index_iterator *ii)
+static int index_iterator__advance(
+	const git_index_entry **entry, git_iterator *self)
 {
+	index_iterator *ii = (index_iterator *)self;
 	size_t entrycount = git_index_entrycount(ii->index);
 	const git_index_entry *ie;
 
-	while (ii->current < entrycount) {
-		ie = git_index_get_byindex(ii->index, ii->current);
+	if (index_iterator__at_tree(ii)) {
+		if (iterator__do_autoexpand(ii)) {
+			ii->partial.ptr[ii->partial_pos] = ii->restore_terminator;
+			index_iterator__next_prefix_tree(ii);
+		} else {
+			/* advance to sibling tree (i.e. find entry with new prefix) */
+			while (ii->current < entrycount) {
+				ii->current++;
+
+				if (!(ie = git_index_get_byindex(ii->index, ii->current)) ||
+					ii->base.prefixcomp(ie->path, ii->partial.ptr) != 0)
+					break;
+			}
 
-		if (ie == NULL ||
-			(ii->base.end != NULL &&
-			 ii->base.prefixcomp(ie->path, ii->base.end) > 0)) {
-			ii->current = entrycount;
-			break;
+			if (index_iterator__first_prefix_tree(ii) < 0)
+				return -1;
 		}
+	} else {
+		if (ii->current < entrycount)
+			ii->current++;
 
-		if (git_index_entry_stage(ie) == 0)
-			break;
-
-		ii->current++;
+		if (index_iterator__first_prefix_tree(ii) < 0)
+			return -1;
 	}
+
+	return index_iterator__current(entry, self);
 }
 
-static int index_iterator__advance(
-	git_iterator *self, const git_index_entry **entry)
+static int index_iterator__advance_into(
+	const git_index_entry **entry, git_iterator *self)
 {
 	index_iterator *ii = (index_iterator *)self;
+	const git_index_entry *ie = git_index_get_byindex(ii->index, ii->current);
 
-	if (ii->current < git_index_entrycount(ii->index))
-		ii->current++;
-
-	index_iterator__skip_conflicts(ii);
+	if (ie != NULL && index_iterator__at_tree(ii)) {
+		if (ii->restore_terminator)
+			ii->partial.ptr[ii->partial_pos] = ii->restore_terminator;
+		index_iterator__next_prefix_tree(ii);
+	}
 
-	return index_iterator__current(self, entry);
+	return index_iterator__current(entry, self);
 }
 
 static int index_iterator__seek(git_iterator *self, const char *prefix)
 {
-	GIT_UNUSED(self);
-	GIT_UNUSED(prefix);
-	/* find last item before prefix */
+	GIT_UNUSED(self); GIT_UNUSED(prefix);
 	return -1;
 }
 
@@ -554,11 +798,31 @@ static int index_iterator__reset(
 	git_iterator *self, const char *start, const char *end)
 {
 	index_iterator *ii = (index_iterator *)self;
+	const git_index_entry *ie;
+
 	if (iterator__reset_range(self, start, end) < 0)
 		return -1;
+
 	ii->current = ii->base.start ?
 		git_index__prefix_position(ii->index, ii->base.start) : 0;
-	index_iterator__skip_conflicts(ii);
+
+	if ((ie = index_iterator__skip_conflicts(ii)) == NULL)
+		return 0;
+
+	if (git_buf_sets(&ii->partial, ie->path) < 0)
+		return -1;
+
+	ii->partial_pos = 0;
+
+	if (ii->base.start) {
+		size_t startlen = strlen(ii->base.start);
+
+		ii->partial_pos = (startlen > ii->partial.size) ?
+			ii->partial.size : startlen;
+	}
+
+	index_iterator__next_prefix_tree(ii);
+
 	return 0;
 }
 
@@ -567,9 +831,11 @@ static void index_iterator__free(git_iterator *self)
 	index_iterator *ii = (index_iterator *)self;
 	git_index_free(ii->index);
 	ii->index = NULL;
+
+	git_buf_free(&ii->partial);
 }
 
-int git_iterator_for_index_range(
+int git_iterator_for_index(
 	git_iterator **iter,
 	git_index  *index,
 	git_iterator_flag_t flags,
@@ -578,18 +844,19 @@ int git_iterator_for_index_range(
 {
 	index_iterator *ii;
 
-	GIT_UNUSED(flags);
-
-	ITERATOR_BASE_INIT(ii, index, INDEX);
+	ITERATOR_BASE_INIT(ii, index, INDEX, git_index_owner(index));
 
-	ii->base.repo = git_index_owner(index);
 	if (index->ignore_case) {
 		ii->base.flags |= GIT_ITERATOR_IGNORE_CASE;
 		ii->base.prefixcomp = git__prefixcmp_icase;
 	}
+
 	ii->index = index;
 	GIT_REFCOUNT_INC(index);
 
+	git_buf_init(&ii->partial, 0);
+	ii->tree_entry.mode = GIT_FILEMODE_TREE;
+
 	index_iterator__reset((git_iterator *)ii, NULL, NULL);
 
 	*iter = (git_iterator *)ii;
@@ -598,6 +865,8 @@ int git_iterator_for_index_range(
 }
 
 
+#define WORKDIR_MAX_DEPTH 100
+
 typedef struct workdir_iterator_frame workdir_iterator_frame;
 struct workdir_iterator_frame {
 	workdir_iterator_frame *next;
@@ -615,6 +884,7 @@ typedef struct {
 	git_buf path;
 	size_t root_len;
 	int is_ignored;
+	int depth;
 } workdir_iterator;
 
 GIT_INLINE(bool) path_is_dotgit(const git_path_with_stat *ps)
@@ -643,7 +913,7 @@ static workdir_iterator_frame *workdir_iterator__alloc_frame(
 {
 	workdir_iterator_frame *wf = git__calloc(1, sizeof(workdir_iterator_frame));
 	git_vector_cmp entry_compare = CASESELECT(
-		(wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
+		iterator__ignore_case(wi),
 		git_path_with_stat_cmp_icase, git_path_with_stat_cmp);
 
 	if (wf == NULL)
@@ -701,12 +971,18 @@ static void workdir_iterator__seek_frame_start(
 static int workdir_iterator__expand_dir(workdir_iterator *wi)
 {
 	int error;
-	workdir_iterator_frame *wf = workdir_iterator__alloc_frame(wi);
+	workdir_iterator_frame *wf;
+
+	if (++(wi->depth) > WORKDIR_MAX_DEPTH) {
+		giterr_set(GITERR_REPOSITORY, "Working directory is too deep");
+		return -1;
+	}
+
+	wf = workdir_iterator__alloc_frame(wi);
 	GITERR_CHECK_ALLOC(wf);
 
 	error = git_path_dirload_with_stat(
-		wi->path.ptr, wi->root_len,
-		(wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0,
+		wi->path.ptr, wi->root_len, iterator__ignore_case(wi),
 		wi->base.start, wi->base.end, &wf->entries);
 
 	if (error < 0 || wf->entries.length == 0) {
@@ -729,10 +1005,11 @@ static int workdir_iterator__expand_dir(workdir_iterator *wi)
 }
 
 static int workdir_iterator__current(
-	git_iterator *self, const git_index_entry **entry)
+	const git_index_entry **entry, git_iterator *self)
 {
 	workdir_iterator *wi = (workdir_iterator *)self;
-	*entry = (wi->entry.path == NULL) ? NULL : &wi->entry;
+	if (entry)
+		*entry = (wi->entry.path == NULL) ? NULL : &wi->entry;
 	return 0;
 }
 
@@ -741,21 +1018,56 @@ static int workdir_iterator__at_end(git_iterator *self)
 	return (((workdir_iterator *)self)->entry.path == NULL);
 }
 
+static int workdir_iterator__advance_into(
+	const git_index_entry **entry, git_iterator *iter)
+{
+	int error = 0;
+	workdir_iterator *wi = (workdir_iterator *)iter;
+
+	iterator__clear_entry(entry);
+
+	/* workdir iterator will allow you to explicitly advance into a
+	 * commit/submodule (as well as a tree) to avoid some cases where an
+	 * entry is mislabeled as a submodule in the working directory
+	 */
+	if (wi->entry.path != NULL &&
+		(wi->entry.mode == GIT_FILEMODE_TREE ||
+		 wi->entry.mode == GIT_FILEMODE_COMMIT))
+		/* returns GIT_ENOTFOUND if the directory is empty */
+		error = workdir_iterator__expand_dir(wi);
+
+	if (!error && entry)
+		error = workdir_iterator__current(entry, iter);
+
+	return error;
+}
+
 static int workdir_iterator__advance(
-	git_iterator *self, const git_index_entry **entry)
+	const git_index_entry **entry, git_iterator *self)
 {
-	int error;
+	int error = 0;
 	workdir_iterator *wi = (workdir_iterator *)self;
 	workdir_iterator_frame *wf;
 	git_path_with_stat *next;
 
+	/* given include_trees & autoexpand, we might have to go into a tree */
+	if (iterator__do_autoexpand(wi) &&
+		wi->entry.path != NULL &&
+		wi->entry.mode == GIT_FILEMODE_TREE)
+	{
+		error = workdir_iterator__advance_into(entry, self);
+
+		/* continue silently past empty directories if autoexpanding */
+		if (error != GIT_ENOTFOUND)
+			return error;
+		giterr_clear();
+		error = 0;
+	}
+
 	if (entry != NULL)
 		*entry = NULL;
 
-	if (wi->entry.path == NULL)
-		return 0;
-
-	while (1) {
+	while (wi->entry.path != NULL) {
 		wf   = wi->stack;
 		next = git_vector_get(&wf->entries, ++wf->index);
 
@@ -781,7 +1093,7 @@ static int workdir_iterator__advance(
 	error = workdir_iterator__update_entry(wi);
 
 	if (!error && entry != NULL)
-		error = workdir_iterator__current(self, entry);
+		error = workdir_iterator__current(entry, self);
 
 	return error;
 }
@@ -832,6 +1144,7 @@ static void workdir_iterator__free(git_iterator *self)
 
 static int workdir_iterator__update_entry(workdir_iterator *wi)
 {
+	int error = 0;
 	git_path_with_stat *ps =
 		git_vector_get(&wi->stack->entries, wi->stack->index);
 
@@ -841,19 +1154,18 @@ static int workdir_iterator__update_entry(workdir_iterator *wi)
 	if (!ps)
 		return 0;
 
+	/* skip over .git entries */
+	if (path_is_dotgit(ps))
+		return workdir_iterator__advance(NULL, (git_iterator *)wi);
+
 	if (git_buf_put(&wi->path, ps->path, ps->path_len) < 0)
 		return -1;
 
-	if (wi->base.end &&
-		wi->base.prefixcomp(wi->path.ptr + wi->root_len, wi->base.end) > 0)
+	if (iterator__past_end(wi, wi->path.ptr + wi->root_len))
 		return 0;
 
 	wi->entry.path = ps->path;
 
-	/* skip over .git entries */
-	if (path_is_dotgit(ps))
-		return workdir_iterator__advance((git_iterator *)wi, NULL);
-
 	wi->is_ignored = -1;
 
 	git_index_entry__init_from_stat(&wi->entry, &ps->st);
@@ -867,26 +1179,32 @@ static int workdir_iterator__update_entry(workdir_iterator *wi)
 		return 0;
 	}
 
+	/* if this isn't a tree, then we're done */
+	if (wi->entry.mode != GIT_FILEMODE_TREE)
+		return 0;
+
 	/* detect submodules */
-	if (S_ISDIR(wi->entry.mode)) {
-		int res = git_submodule_lookup(NULL, wi->base.repo, wi->entry.path);
-		bool is_submodule = (res == 0);
-		if (res == GIT_ENOTFOUND)
-			giterr_clear();
-
-		/* if submodule, mark as GITLINK and remove trailing slash */
-		if (is_submodule) {
-			size_t len = strlen(wi->entry.path);
-			assert(wi->entry.path[len - 1] == '/');
-			wi->entry.path[len - 1] = '\0';
-			wi->entry.mode = S_IFGITLINK;
-		}
+
+	error = git_submodule_lookup(NULL, wi->base.repo, wi->entry.path);
+	if (error == GIT_ENOTFOUND)
+		giterr_clear();
+
+	/* if submodule, mark as GITLINK and remove trailing slash */
+	if (!error) {
+		size_t len = strlen(wi->entry.path);
+		assert(wi->entry.path[len - 1] == '/');
+		wi->entry.path[len - 1] = '\0';
+		wi->entry.mode = S_IFGITLINK;
+		return 0;
 	}
 
-	return 0;
+	if (iterator__include_trees(wi))
+		return 0;
+
+	return workdir_iterator__advance_into(NULL, (git_iterator *)wi);
 }
 
-int git_iterator_for_workdir_range(
+int git_iterator_for_workdir(
 	git_iterator **iter,
 	git_repository *repo,
 	git_iterator_flag_t flags,
@@ -899,13 +1217,12 @@ int git_iterator_for_workdir_range(
 	assert(iter && repo);
 
 	if ((error = git_repository__ensure_not_bare(
-			repo, "scan working directory")) < 0)
+			 repo, "scan working directory")) < 0)
 		return error;
 
-	ITERATOR_BASE_INIT(wi, workdir, WORKDIR);
-	wi->base.repo = repo;
+	ITERATOR_BASE_INIT(wi, workdir, WORKDIR, repo);
 
-	if ((error = iterator_update_ignore_case((git_iterator *)wi, flags)) < 0)
+	if ((error = iterator__update_ignore_case((git_iterator *)wi, flags)) < 0)
 		goto fail;
 
 	if (git_buf_sets(&wi->path, git_repository_workdir(repo)) < 0 ||
@@ -917,7 +1234,7 @@ int git_iterator_for_workdir_range(
 	}
 
 	wi->root_len = wi->path.size;
-	wi->entrycmp = (wi->base.flags & GIT_ITERATOR_IGNORE_CASE) != 0 ?
+	wi->entrycmp = iterator__ignore_case(wi) ?
 		workdir_iterator__entry_cmp_icase : workdir_iterator__entry_cmp_case;
 
 	if ((error = workdir_iterator__expand_dir(wi)) < 0) {
@@ -935,161 +1252,6 @@ fail:
 }
 
 
-typedef struct {
-	/* replacement callbacks */
-	git_iterator_callbacks cb;
-	/* original iterator values */
-	git_iterator_callbacks *orig;
-	git_iterator_type_t orig_type;
-	/* spoolandsort data */
-	git_vector entries;
-	git_pool entry_pool;
-	git_pool string_pool;
-	size_t position;
-} spoolandsort_callbacks;
-
-static int spoolandsort_iterator__current(
-	git_iterator *self, const git_index_entry **entry)
-{
-	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
-
-	*entry = (const git_index_entry *)
-		git_vector_get(&scb->entries, scb->position);
-
-	return 0;
-}
-
-static int spoolandsort_iterator__at_end(git_iterator *self)
-{
-	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
-
-	return 0 == scb->entries.length || scb->entries.length - 1 <= scb->position;
-}
-
-static int spoolandsort_iterator__advance(
-	git_iterator *self, const git_index_entry **entry)
-{
-	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
-
-	*entry = (const git_index_entry *)
-		git_vector_get(&scb->entries, ++scb->position);
-
-	return 0;
-}
-
-static int spoolandsort_iterator__seek(git_iterator *self, const char *prefix)
-{
-	GIT_UNUSED(self);
-	GIT_UNUSED(prefix);
-
-	return -1;
-}
-
-static int spoolandsort_iterator__reset(
-	git_iterator *self, const char *start, const char *end)
-{
-	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
-
-	GIT_UNUSED(start); GIT_UNUSED(end);
-
-	scb->position = 0;
-
-	return 0;
-}
-
-static void spoolandsort_iterator__free_callbacks(spoolandsort_callbacks *scb)
-{
-	git_pool_clear(&scb->string_pool);
-	git_pool_clear(&scb->entry_pool);
-	git_vector_free(&scb->entries);
-	git__free(scb);
-}
-
-void git_iterator_spoolandsort_pop(git_iterator *self)
-{
-	spoolandsort_callbacks *scb = (spoolandsort_callbacks *)self->cb;
-
-	if (self->type != GIT_ITERATOR_TYPE_SPOOLANDSORT)
-		return;
-
-	self->cb   = scb->orig;
-	self->type = scb->orig_type;
-	self->flags ^= GIT_ITERATOR_IGNORE_CASE;
-
-	spoolandsort_iterator__free_callbacks(scb);
-}
-
-static void spoolandsort_iterator__free(git_iterator *self)
-{
-	git_iterator_spoolandsort_pop(self);
-	self->cb->free(self);
-}
-
-int git_iterator_spoolandsort_push(git_iterator *iter, bool ignore_case)
-{
-	const git_index_entry *item;
-	spoolandsort_callbacks *scb;
-	int (*entrycomp)(const void *a, const void *b);
-
-	if (((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) == (ignore_case != 0))
-		return 0;
-
-	if (iter->type == GIT_ITERATOR_TYPE_EMPTY) {
-		iter->flags = (iter->flags ^ GIT_ITERATOR_IGNORE_CASE);
-		return 0;
-	}
-
-	scb = git__calloc(1, sizeof(spoolandsort_callbacks));
-	GITERR_CHECK_ALLOC(scb);
-
-	ITERATOR_SET_CB(scb,spoolandsort);
-
-	scb->orig      = iter->cb;
-	scb->orig_type = iter->type;
-	scb->position  = 0;
-
-	entrycomp = ignore_case ? git_index_entry__cmp_icase : git_index_entry__cmp;
-
-	if (git_vector_init(&scb->entries, 16, entrycomp) < 0 ||
-		git_pool_init(&scb->entry_pool, sizeof(git_index_entry), 0) < 0 ||
-		git_pool_init(&scb->string_pool, 1, 0) < 0 ||
-		git_iterator_current(iter, &item) < 0)
-		goto fail;
-
-	while (item) {
-		git_index_entry *clone = git_pool_malloc(&scb->entry_pool, 1);
-		if (!clone)
-			goto fail;
-
-		memcpy(clone, item, sizeof(git_index_entry));
-
-		if (item->path) {
-			clone->path = git_pool_strdup(&scb->string_pool, item->path);
-			if (!clone->path)
-				goto fail;
-		}
-
-		if (git_vector_insert(&scb->entries, clone) < 0)
-			goto fail;
-
-		if (git_iterator_advance(iter, &item) < 0)
-			goto fail;
-	}
-
-	git_vector_sort(&scb->entries);
-
-	iter->cb   = (git_iterator_callbacks *)scb;
-	iter->type = GIT_ITERATOR_TYPE_SPOOLANDSORT;
-	iter->flags ^= GIT_ITERATOR_IGNORE_CASE;
-
-	return 0;
-
-fail:
-	spoolandsort_iterator__free_callbacks(scb);
-	return -1;
-}
-
-
 void git_iterator_free(git_iterator *iter)
 {
 	if (iter == NULL)
@@ -1105,110 +1267,94 @@ void git_iterator_free(git_iterator *iter)
 	git__free(iter);
 }
 
-git_index *git_iterator_index_get_index(git_iterator *iter)
+int git_iterator_set_ignore_case(git_iterator *iter, bool ignore_case)
 {
-	if (iter->type == GIT_ITERATOR_TYPE_INDEX)
-		return ((index_iterator *)iter)->index;
+	bool desire_ignore_case  = (ignore_case != 0);
 
-	if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT &&
-		((spoolandsort_callbacks *)iter->cb)->orig_type == GIT_ITERATOR_TYPE_INDEX)
-		return ((index_iterator *)iter)->index;
+	if (iterator__ignore_case(iter) == desire_ignore_case)
+		return 0;
 
-	return NULL;
+	if (iter->type == GIT_ITERATOR_TYPE_EMPTY) {
+		if (desire_ignore_case)
+			iter->flags |= GIT_ITERATOR_IGNORE_CASE;
+		else
+			iter->flags &= ~GIT_ITERATOR_IGNORE_CASE;
+	} else {
+		giterr_set(GITERR_INVALID,
+			"Cannot currently set ignore case on non-empty iterators");
+		return -1;
+	}
+
+	return 0;
 }
 
-git_iterator_type_t git_iterator_inner_type(git_iterator *iter)
+git_index *git_iterator_get_index(git_iterator *iter)
 {
-	if (iter->type == GIT_ITERATOR_TYPE_SPOOLANDSORT)
-		return ((spoolandsort_callbacks *)iter->cb)->orig_type;
-
-	return iter->type;
+	if (iter->type == GIT_ITERATOR_TYPE_INDEX)
+		return ((index_iterator *)iter)->index;
+	return NULL;
 }
 
 int git_iterator_current_tree_entry(
-	git_iterator *iter, const git_tree_entry **tree_entry)
+	const git_tree_entry **tree_entry, git_iterator *iter)
 {
-	*tree_entry = (iter->type != GIT_ITERATOR_TYPE_TREE) ? NULL :
-		tree_iterator__tree_entry((tree_iterator *)iter);
+	if (iter->type != GIT_ITERATOR_TYPE_TREE)
+		*tree_entry = NULL;
+	else {
+		tree_iterator_frame *tf = ((tree_iterator *)iter)->head;
+		*tree_entry = tree_iterator__tree_entry_by_index(tf, tf->current);
+	}
+
 	return 0;
 }
 
 int git_iterator_current_parent_tree(
+	const git_tree **tree_ptr,
 	git_iterator *iter,
-	const char *parent_path,
-	const git_tree **tree_ptr)
+	const char *parent_path)
 {
 	tree_iterator *ti = (tree_iterator *)iter;
 	tree_iterator_frame *tf;
 	const char *scan = parent_path;
-	int (*strncomp)(const char *a, const char *b, size_t sz);
+	const git_tree_entry *te;
 
-	if (iter->type != GIT_ITERATOR_TYPE_TREE || ti->stack == NULL)
-		goto notfound;
+	*tree_ptr = NULL;
 
-	strncomp = ((iter->flags & GIT_ITERATOR_IGNORE_CASE) != 0) ?
-		git__strncasecmp : git__strncmp;
+	if (iter->type != GIT_ITERATOR_TYPE_TREE)
+		return 0;
 
-	for (tf = ti->tail; tf != NULL; tf = tf->prev) {
-		const git_tree_entry *te;
+	tf = ti->top;
 
-		if (!*scan) {
-			*tree_ptr = tf->tree;
+	while (*scan) {
+		/* get entry of this parent that child is currently on */
+		if (!(tf = tf->child) ||
+			!(te = tree_iterator__tree_entry_by_index(tf, tf->current)) ||
+			ti->strncomp(scan, te->filename, te->filename_len) != 0)
 			return 0;
-		}
-
-		te = git_tree_entry_byindex(tf->tree,
-			tf->icase_map ? (size_t)tf->icase_map[tf->index] : tf->index);
-
-		if (strncomp(scan, te->filename, te->filename_len) != 0)
-			goto notfound;
 
 		scan += te->filename_len;
-
-		if (*scan) {
-			if (*scan != '/')
-				goto notfound;
+		if (*scan == '/')
 			scan++;
-		}
 	}
 
-notfound:
-	*tree_ptr = NULL;
+	*tree_ptr = tf->entries[tf->current].tree;
 	return 0;
 }
 
-int git_iterator_current_is_ignored(git_iterator *iter)
+bool git_iterator_current_is_ignored(git_iterator *iter)
 {
 	workdir_iterator *wi = (workdir_iterator *)iter;
 
 	if (iter->type != GIT_ITERATOR_TYPE_WORKDIR)
-		return 0;
+		return false;
 
 	if (wi->is_ignored != -1)
-		return wi->is_ignored;
+		return (bool)(wi->is_ignored != 0);
 
 	if (git_ignore__lookup(&wi->ignores, wi->entry.path, &wi->is_ignored) < 0)
-		wi->is_ignored = 1;
+		wi->is_ignored = true;
 
-	return wi->is_ignored;
-}
-
-int git_iterator_advance_into_directory(
-	git_iterator *iter, const git_index_entry **entry)
-{
-	workdir_iterator *wi = (workdir_iterator *)iter;
-
-	if (iter->type == GIT_ITERATOR_TYPE_WORKDIR &&
-		wi->entry.path &&
-		(wi->entry.mode == GIT_FILEMODE_TREE ||
-		 wi->entry.mode == GIT_FILEMODE_COMMIT))
-	{
-		if (workdir_iterator__expand_dir(wi) < 0)
-			/* if error loading or if empty, skip the directory. */
-			return workdir_iterator__advance(iter, entry);
-	}
-
-	return entry ? git_iterator_current(iter, entry) : 0;
+	return (bool)wi->is_ignored;
 }
 
 int git_iterator_cmp(git_iterator *iter, const char *path_prefix)
@@ -1216,8 +1362,7 @@ 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)
+	if (git_iterator_current(&entry, iter) < 0 || entry == NULL)
 		return 1;
 
 	/* a NULL prefix is after any valid iterator */
@@ -1227,7 +1372,7 @@ int git_iterator_cmp(git_iterator *iter, const char *path_prefix)
 	return iter->prefixcomp(entry->path, path_prefix);
 }
 
-int git_iterator_current_workdir_path(git_iterator *iter, git_buf **path)
+int git_iterator_current_workdir_path(git_buf **path, git_iterator *iter)
 {
 	workdir_iterator *wi = (workdir_iterator *)iter;
 
@@ -1238,4 +1383,3 @@ int git_iterator_current_workdir_path(git_iterator *iter, git_buf **path)
 
 	return 0;
 }
-