1 files changed, 260 insertions, 227 deletions

diff --git a/src/iterator.c b/src/iterator.c
index 6c7764736..84664c0f8 100644
--- a/src/iterator.c
+++ b/src/iterator.c
@@ -94,7 +94,7 @@ 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;
@@ -162,41 +162,38 @@ int git_iterator_for_nothing(
 }
 
 
+
+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;
+	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;
-	/* secondary tree index for case-insensitive sort */
-	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;
 	bool path_has_filename;
+	int (*strcomp)(const char *a, const char *b);
+	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)
-{
-	tree_iterator_frame *tf = ti->stack;
-	size_t entries = git_tree_entrycount(tf->tree), idx = tf->index;
-
-	if (idx >= entries)
-		return NULL;
-
-	if (tf->icase_map)
-		idx = (size_t)tf->icase_map[idx];
-
-	return git_tree_entry_byindex(tf->tree, idx);
-}
-
 static char *tree_iterator__current_filename(
 	tree_iterator *ti, const git_tree_entry *te)
 {
@@ -213,193 +210,232 @@ static char *tree_iterator__current_filename(
 	return ti->path.ptr;
 }
 
-static void tree_iterator__free_frame(tree_iterator_frame *tf)
+static int tree_iterator__create_top_frame(tree_iterator *ti, git_tree *tree)
 {
-	if (!tf)
-		return;
+	size_t sz = sizeof(tree_iterator_frame) + sizeof(tree_iterator_entry);
+	tree_iterator_frame *top = git__calloc(sz, sizeof(char));
+	GITERR_CHECK_ALLOC(top);
 
-	git_tree_free(tf->tree);
-	tf->tree = NULL;
+	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;
 
-	git__free(tf);
+	ti->head = ti->top = top;
+
+	return 0;
 }
 
-static bool tree_iterator__pop_frame(tree_iterator *ti)
+static const git_tree_entry *tree_iterator__get_tree_entry(
+	tree_iterator_frame *tf, const tree_iterator_entry *entry, size_t i)
 {
-	tree_iterator_frame *tf = ti->stack;
-
-	/* don't free the initial tree/frame */
-	if (!tf->next)
-		return false;
+	git_tree *tree;
 
-	ti->stack = tf->next;
-	ti->stack->prev = NULL;
+	if (!entry) {
+		if (i >= tf->n_entries)
+			return NULL;
+		entry = &tf->entries[i];
+	}
 
-	tree_iterator__free_frame(tf);
+	tree = tf->parent->entries[entry->parent_entry_index].tree;
+	if (!tree)
+		return NULL;
 
-	return true;
+	return git_tree_entry_byindex(tree, entry->parent_tree_index);
 }
 
-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;
+	tree_iterator_frame *tf = p;
+	const git_tree_entry *ae = tree_iterator__get_tree_entry(tf, a, 0);
+	const git_tree_entry *be = tree_iterator__get_tree_entry(tf, b, 0);
+	size_t common_len = min(ae->filename_len, be->filename_len);
+	int cmp = git__strncasecmp(ae->filename, be->filename, common_len);
+
+	if (!cmp) {
+		char a_next = ae->filename[common_len];
+		char b_next = be->filename[common_len];
+
+		if (!a_next && ae->attr == GIT_FILEMODE_TREE)
+			a_next = '/';
+		if (!b_next && be->attr == GIT_FILEMODE_TREE)
+			b_next = '/';
+
+		cmp = (int)a_next - (int)b_next;
+	}
+
+	return cmp;
 }
 
-static int tree_iterator__current(
-	const git_index_entry **entry, git_iterator *self)
+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);
-
-	if (entry)
-		*entry = NULL;
-
-	if (te == NULL)
-		return 0;
+	/* find next and load trees for current range */
+	int error = 0;
+	const git_tree_entry *te, *last_te = NULL;
 
-	ti->entry.mode = te->attr;
-	git_oid_cpy(&ti->entry.oid, &te->oid);
+	tf->next = tf->current;
 
-	ti->entry.path = tree_iterator__current_filename(ti, te);
-	if (ti->entry.path == NULL)
-		return -1;
+	while (tf->next < tf->n_entries) {
+		if (!(te = tree_iterator__get_tree_entry(tf, 0, tf->next)) ||
+			(last_te && ti->strcomp(last_te->filename, te->filename) != 0))
+			break;
 
-	if (iterator__past_end(ti, ti->entry.path))
-		return tree_iterator__to_end(ti);
+		if (git_tree_entry__is_tree(te) &&
+			(error = git_tree_lookup(
+				&tf->entries[tf->next].tree, ti->base.repo, &te->oid)) < 0)
+			break;
 
-	if (entry)
-		*entry = &ti->entry;
+		tf->next++;
+		last_te = te;
+	}
 
-	return 0;
-}
+	if (last_te && !tree_iterator__current_filename(ti, last_te))
+		return -1;
 
-static int tree_iterator__at_end(git_iterator *self)
-{
-	return (tree_iterator__tree_entry((tree_iterator *)self) == NULL);
+	return error;
 }
 
-static int tree_iterator__icase_map_cmp(const void *a, const void *b, void *data)
+GIT_INLINE(bool) tree_iterator__at_tree(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);
-
-	return te1 ? (te2 ? git_tree_entry_icmp(te1, te2) : 1) : -1;
+	return (ti->head->current < ti->head->n_entries &&
+			ti->head->entries[ti->head->current].tree != NULL);
 }
 
-static int tree_iterator__frame_start_icmp(const void *key, const void *el)
+static int tree_iterator__push_frame(tree_iterator *ti)
 {
-	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);
+	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 git__strncasecmp(tf->start, te->filename, minlen);
-}
+	/* 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 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--;
-			}
+	/* 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++;
 		}
 	}
-}
-
-static int tree_iterator__push_frame(
-	tree_iterator *ti, git_tree *tree, const char *start)
-{
-	size_t i, max_i = git_tree_entrycount(tree);
-	tree_iterator_frame *tf =
-		git__calloc(1, sizeof(tree_iterator_frame) + max_i * sizeof(void *));
-	GITERR_CHECK_ALLOC(tf);
-
-	tf->tree  = tree;
 
-	tf->next  = ti->stack;
-	ti->stack = tf;
-	if (tf->next)
-		tf->next->prev = tf;
-	else
-		ti->tail = tf;
+	/* 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__get_tree_entry(new_tf, NULL, 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;
 
-	if (start && *start) {
-		tf->start    = start;
-		tf->startlen = strlen(start);
+		if ((new_tf->start = strchr(tf->start, '/')) != NULL) {
+			new_tf->start++;
+			new_tf->startlen = strlen(new_tf->start);
+		}
 	}
 
 	ti->path_has_filename = false;
 
-	if (!max_i)
-		return 0;
+	/* find next and load trees for current range */
+	if ((error = tree_iterator__set_next(ti, new_tf)) < 0)
+		return error;
 
-	/* build secondary index if iterator is case-insensitive */
-	if (iterator__ignore_case(ti)) {
-		tf->icase_map = tf->icase_data;
+	tf->child = new_tf;
+	ti->head  = new_tf;
 
-		for (i = 0; i < max_i; ++i)
-			tf->icase_map[i] = (void *)i;
+	if (!iterator__include_trees(ti) && tree_iterator__at_tree(ti))
+		return tree_iterator__push_frame(ti);
 
-		git__tsort_r(
-			tf->icase_map, max_i, tree_iterator__icase_map_cmp, tf->tree);
-	}
+	return 0;
+}
 
-	tree_iterator__frame_seek_start(tf);
+static bool tree_iterator__move_to_next(tree_iterator_frame *tf)
+{
+	while (tf->current < tf->next) {
+		if (tf->parent && tf->entries[tf->current].tree) {
+			git_tree_free(tf->entries[tf->current].tree);
+			tf->entries[tf->current].tree = NULL;
+		}
+		tf->current++;
+	}
 
-	return 0;
+	return (tf->current < tf->n_entries);
 }
 
-static int tree_iterator__expand_tree(tree_iterator *ti)
+static bool tree_iterator__pop_frame(tree_iterator *ti)
 {
-	int error;
-	git_tree *subtree;
-	const git_tree_entry *te = tree_iterator__tree_entry(ti);
-	const char *relpath;
+	tree_iterator_frame *tf = ti->head;
 
-	while (te != NULL && git_tree_entry__is_tree(te)) {
-		relpath = tree_iterator__current_filename(ti, te);
+	if (!tf->parent)
+		return false;
 
-		/* check that we have not passed the range end */
-		if (iterator__past_end(ti, relpath))
-			return tree_iterator__to_end(ti);
+	tree_iterator__move_to_next(tf);
 
-		if ((error = git_tree_lookup(&subtree, ti->base.repo, &te->oid)) < 0)
-			return error;
+	ti->head = tf->parent;
+	ti->head->child = NULL;
+	git__free(tf);
 
-		relpath = NULL;
+	git_buf_rtruncate_at_char(&ti->path, '/');
 
-		/* 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;
-		}
+	return true;
+}
 
-		if ((error = tree_iterator__push_frame(ti, subtree, relpath)) < 0)
-			return error;
+static int tree_iterator__current(
+	const git_index_entry **entry, git_iterator *self)
+{
+	tree_iterator *ti = (tree_iterator *)self;
+	tree_iterator_frame *tf = ti->head;
+	const git_tree_entry *te;
 
-		/* if including trees, then one expansion is always enough */
-		if (iterator__include_trees(ti))
-			break;
+	if (entry)
+		*entry = NULL;
+
+	if (!(te = tree_iterator__get_tree_entry(tf, NULL, tf->current)))
+		return 0;
 
-		te = tree_iterator__tree_entry(ti);
+	ti->entry.mode = te->attr;
+	git_oid_cpy(&ti->entry.oid, &te->oid);
+
+	ti->entry.path = tree_iterator__current_filename(ti, te);
+	if (ti->entry.path == NULL)
+		return -1;
+
+	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;
 }
 
@@ -408,16 +444,12 @@ static int tree_iterator__advance_into(
 {
 	int error = 0;
 	tree_iterator *ti = (tree_iterator *)self;
-	const git_tree_entry *te = tree_iterator__tree_entry(ti);
 
 	if (entry)
 		*entry = NULL;
 
-	/* if DONT_AUTOEXPAND is off, the following will always be false */
-	if (te && git_tree_entry__is_tree(te))
-		error = tree_iterator__expand_tree(ti);
-
-	if (!error && entry)
+	if (tree_iterator__at_tree(ti) &&
+		!(error = tree_iterator__push_frame(ti)))
 		error = tree_iterator__current(entry, self);
 
 	return error;
@@ -426,14 +458,18 @@ static int tree_iterator__advance_into(
 static int tree_iterator__advance(
 	const git_index_entry **entry, git_iterator *self)
 {
+	int error;
 	tree_iterator *ti = (tree_iterator *)self;
-	const git_tree_entry *te = tree_iterator__tree_entry(ti);
+	tree_iterator_frame *tf = ti->head;
 
-	if (entry != NULL)
+	if (entry)
 		*entry = NULL;
 
-	/* given include_trees & autoexpand, we might have to go into a tree */
-	if (te && git_tree_entry__is_tree(te) && iterator__do_autoexpand(ti))
+	if (tf->current > tf->n_entries)
+		return 0;
+
+	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) {
@@ -441,19 +477,16 @@ static int tree_iterator__advance(
 		ti->path_has_filename = false;
 	}
 
-	while (1) {
-		++ti->stack->index;
-
-		if ((te = tree_iterator__tree_entry(ti)) != NULL)
-			break;
-
-		if (!tree_iterator__pop_frame(ti))
-			break; /* no frames left to pop */
+	/* scan forward and up, advancing in frame or popping frame when done */
+	while (!tree_iterator__move_to_next(tf) && tree_iterator__pop_frame(ti))
+		tf = ti->head;
 
-		git_buf_rtruncate_at_char(&ti->path, '/');
-	}
+	/* find next and load trees */
+	if ((error = tree_iterator__set_next(ti, tf)) < 0)
+		return error;
 
-	if (te && git_tree_entry__is_tree(te) && !iterator__include_trees(ti))
+	/* 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);
@@ -463,44 +496,45 @@ 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)
+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);
 
-	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 */;
-
-	if (iterator__reset_range(self, start, end) < 0)
-		return -1;
-
-	/* reset start position */
-	tree_iterator__frame_seek_start(ti->stack);
+static void tree_iterator__free(git_iterator *self)
+{
+	tree_iterator *ti = (tree_iterator *)self;
 
-	git_buf_clear(&ti->path);
-	ti->path_has_filename = false;
+	while (tree_iterator__pop_frame(ti)) /* pop to top */;
 
-	if (iterator__do_autoexpand(ti) && !iterator__include_trees(ti))
-		return tree_iterator__expand_tree(ti);
+	/* free base frame */
+	if (ti->head) {
+		git_tree_free(ti->head->entries[0].tree);
+		ti->head->entries[0].tree = NULL;
+		git__free(ti->head);
+	}
+	ti->head = ti->top = NULL;
 
-	return 0;
+	git_buf_free(&ti->path);
 }
 
 int git_iterator_for_tree(
@@ -520,15 +554,19 @@ int git_iterator_for_tree(
 		return error;
 
 	ITERATOR_BASE_INIT(ti, tree, TREE);
-
 	ti->base.repo = git_tree_owner(tree);
 
-	if ((error = iterator_update_ignore_case((git_iterator *)ti, flags)) < 0 ||
-		(error = tree_iterator__push_frame(ti, tree, ti->base.start)) < 0)
+	if ((error = iterator_update_ignore_case((git_iterator *)ti, flags)) < 0)
 		goto fail;
 
-	if (iterator__do_autoexpand(ti) && !iterator__include_trees(ti) &&
-		(error = tree_iterator__expand_tree(ti)) < 0)
+	if (iterator__ignore_case(ti)) {
+		ti->strcomp = git__strcasecmp; ti->strncomp = git__strncasecmp;
+	} else {
+		ti->strcomp = git__strcmp; ti->strncomp = git__strncmp;
+	}
+
+	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;
@@ -1216,8 +1254,14 @@ git_index *git_iterator_get_index(git_iterator *iter)
 int git_iterator_current_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 *ti = (tree_iterator *)iter;
+		*tree_entry =
+			tree_iterator__get_tree_entry(ti->head, NULL, ti->head->current);
+	}
+
 	return 0;
 }
 
@@ -1229,39 +1273,28 @@ int git_iterator_current_parent_tree(
 	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__get_tree_entry(tf, NULL, 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;
 }