Merge branch 'mh/ref-iterators'

The API to iterate over all the refs (i.e. for_each_ref(), etc.)
has been revamped.

* mh/ref-iterators:
  for_each_reflog(): reimplement using iterators
  dir_iterator: new API for iterating over a directory tree
  for_each_reflog(): don't abort for bad references
  do_for_each_ref(): reimplement using reference iteration
  refs: introduce an iterator interface
  ref_resolves_to_object(): new function
  entry_resolves_to_object(): rename function from ref_resolves_to_object()
  get_ref_cache(): only create an instance if there is a submodule
  remote rm: handle symbolic refs correctly
  delete_refs(): add a flags argument
  refs: use name "prefix" consistently
  do_for_each_ref(): move docstring to the header file
  refs: remove unnecessary "extern" keywords

11 files changed, 1460 insertions, 324 deletions

diff --git a/Makefile b/Makefile
index c1e88dfcdd..bfe85595cd 100644
--- a/Makefile
+++ b/Makefile
@@ -718,6 +718,7 @@ LIB_OBJS += diff-lib.o
 LIB_OBJS += diff-no-index.o
 LIB_OBJS += diff.o
 LIB_OBJS += dir.o
+LIB_OBJS += dir-iterator.o
 LIB_OBJS += editor.o
 LIB_OBJS += entry.o
 LIB_OBJS += environment.o
@@ -782,6 +783,7 @@ LIB_OBJS += read-cache.o
 LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.o
 LIB_OBJS += refs/files-backend.o
+LIB_OBJS += refs/iterator.o
 LIB_OBJS += ref-filter.o
 LIB_OBJS += remote.o
 LIB_OBJS += replace_object.o
diff --git a/builtin/fetch.c b/builtin/fetch.c
index d9ea6f392a..acd0cf1755 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -921,7 +921,7 @@ static int prune_refs(struct refspec *refs, int ref_count, struct ref *ref_map,
 		for (ref = stale_refs; ref; ref = ref->next)
 			string_list_append(&refnames, ref->name);
 
-		result = delete_refs(&refnames);
+		result = delete_refs(&refnames, 0);
 		string_list_clear(&refnames, 0);
 	}
 
diff --git a/builtin/remote.c b/builtin/remote.c
index a4d9c1a8e9..9f6a6b3a9c 100644
--- a/builtin/remote.c
+++ b/builtin/remote.c
@@ -539,10 +539,6 @@ static int add_branch_for_removal(const char *refname,
 		return 0;
 	}
 
-	/* make sure that symrefs are deleted */
-	if (flags & REF_ISSYMREF)
-		return unlink(git_path("%s", refname));
-
 	string_list_append(branches->branches, refname);
 
 	return 0;
@@ -788,7 +784,7 @@ static int rm(int argc, const char **argv)
 	strbuf_release(&buf);
 
 	if (!result)
-		result = delete_refs(&branches);
+		result = delete_refs(&branches, REF_NODEREF);
 	string_list_clear(&branches, 0);
 
 	if (skipped.nr) {
@@ -1304,7 +1300,7 @@ static int prune_remote(const char *remote, int dry_run)
 	string_list_sort(&refs_to_prune);
 
 	if (!dry_run)
-		result |= delete_refs(&refs_to_prune);
+		result |= delete_refs(&refs_to_prune, 0);
 
 	for_each_string_list_item(item, &states.stale) {
 		const char *refname = item->util;
diff --git a/dir-iterator.c b/dir-iterator.c
new file mode 100644
index 0000000000..34182a9a1c
--- /dev/null
+++ b/dir-iterator.c
@@ -0,0 +1,202 @@
+#include "cache.h"
+#include "dir.h"
+#include "iterator.h"
+#include "dir-iterator.h"
+
+struct dir_iterator_level {
+	int initialized;
+
+	DIR *dir;
+
+	/*
+	 * The length of the directory part of path at this level
+	 * (including a trailing '/'):
+	 */
+	size_t prefix_len;
+
+	/*
+	 * The last action that has been taken with the current entry
+	 * (needed for directories, which have to be included in the
+	 * iteration and also iterated into):
+	 */
+	enum {
+		DIR_STATE_ITER,
+		DIR_STATE_RECURSE
+	} dir_state;
+};
+
+/*
+ * The full data structure used to manage the internal directory
+ * iteration state. It includes members that are not part of the
+ * public interface.
+ */
+struct dir_iterator_int {
+	struct dir_iterator base;
+
+	/*
+	 * The number of levels currently on the stack. This is always
+	 * at least 1, because when it becomes zero the iteration is
+	 * ended and this struct is freed.
+	 */
+	size_t levels_nr;
+
+	/* The number of levels that have been allocated on the stack */
+	size_t levels_alloc;
+
+	/*
+	 * A stack of levels. levels[0] is the uppermost directory
+	 * that will be included in this iteration.
+	 */
+	struct dir_iterator_level *levels;
+};
+
+int dir_iterator_advance(struct dir_iterator *dir_iterator)
+{
+	struct dir_iterator_int *iter =
+		(struct dir_iterator_int *)dir_iterator;
+
+	while (1) {
+		struct dir_iterator_level *level =
+			&iter->levels[iter->levels_nr - 1];
+		struct dirent *de;
+
+		if (!level->initialized) {
+			/*
+			 * Note: dir_iterator_begin() ensures that
+			 * path is not the empty string.
+			 */
+			if (!is_dir_sep(iter->base.path.buf[iter->base.path.len - 1]))
+				strbuf_addch(&iter->base.path, '/');
+			level->prefix_len = iter->base.path.len;
+
+			level->dir = opendir(iter->base.path.buf);
+			if (!level->dir && errno != ENOENT) {
+				warning("error opening directory %s: %s",
+					iter->base.path.buf, strerror(errno));
+				/* Popping the level is handled below */
+			}
+
+			level->initialized = 1;
+		} else if (S_ISDIR(iter->base.st.st_mode)) {
+			if (level->dir_state == DIR_STATE_ITER) {
+				/*
+				 * The directory was just iterated
+				 * over; now prepare to iterate into
+				 * it.
+				 */
+				level->dir_state = DIR_STATE_RECURSE;
+				ALLOC_GROW(iter->levels, iter->levels_nr + 1,
+					   iter->levels_alloc);
+				level = &iter->levels[iter->levels_nr++];
+				level->initialized = 0;
+				continue;
+			} else {
+				/*
+				 * The directory has already been
+				 * iterated over and iterated into;
+				 * we're done with it.
+				 */
+			}
+		}
+
+		if (!level->dir) {
+			/*
+			 * This level is exhausted (or wasn't opened
+			 * successfully); pop up a level.
+			 */
+			if (--iter->levels_nr == 0)
+				return dir_iterator_abort(dir_iterator);
+
+			continue;
+		}
+
+		/*
+		 * Loop until we find an entry that we can give back
+		 * to the caller:
+		 */
+		while (1) {
+			strbuf_setlen(&iter->base.path, level->prefix_len);
+			errno = 0;
+			de = readdir(level->dir);
+
+			if (!de) {
+				/* This level is exhausted; pop up a level. */
+				if (errno) {
+					warning("error reading directory %s: %s",
+						iter->base.path.buf, strerror(errno));
+				} else if (closedir(level->dir))
+					warning("error closing directory %s: %s",
+						iter->base.path.buf, strerror(errno));
+
+				level->dir = NULL;
+				if (--iter->levels_nr == 0)
+					return dir_iterator_abort(dir_iterator);
+				break;
+			}
+
+			if (is_dot_or_dotdot(de->d_name))
+				continue;
+
+			strbuf_addstr(&iter->base.path, de->d_name);
+			if (lstat(iter->base.path.buf, &iter->base.st) < 0) {
+				if (errno != ENOENT)
+					warning("error reading path '%s': %s",
+						iter->base.path.buf,
+						strerror(errno));
+				continue;
+			}
+
+			/*
+			 * We have to set these each time because
+			 * the path strbuf might have been realloc()ed.
+			 */
+			iter->base.relative_path =
+				iter->base.path.buf + iter->levels[0].prefix_len;
+			iter->base.basename =
+				iter->base.path.buf + level->prefix_len;
+			level->dir_state = DIR_STATE_ITER;
+
+			return ITER_OK;
+		}
+	}
+}
+
+int dir_iterator_abort(struct dir_iterator *dir_iterator)
+{
+	struct dir_iterator_int *iter = (struct dir_iterator_int *)dir_iterator;
+
+	for (; iter->levels_nr; iter->levels_nr--) {
+		struct dir_iterator_level *level =
+			&iter->levels[iter->levels_nr - 1];
+
+		if (level->dir && closedir(level->dir)) {
+			strbuf_setlen(&iter->base.path, level->prefix_len);
+			warning("error closing directory %s: %s",
+				iter->base.path.buf, strerror(errno));
+		}
+	}
+
+	free(iter->levels);
+	strbuf_release(&iter->base.path);
+	free(iter);
+	return ITER_DONE;
+}
+
+struct dir_iterator *dir_iterator_begin(const char *path)
+{
+	struct dir_iterator_int *iter = xcalloc(1, sizeof(*iter));
+	struct dir_iterator *dir_iterator = &iter->base;
+
+	if (!path || !*path)
+		die("BUG: empty path passed to dir_iterator_begin()");
+
+	strbuf_init(&iter->base.path, PATH_MAX);
+	strbuf_addstr(&iter->base.path, path);
+
+	ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
+
+	iter->levels_nr = 1;
+	iter->levels[0].initialized = 0;
+
+	return dir_iterator;
+}
diff --git a/dir-iterator.h b/dir-iterator.h
new file mode 100644
index 0000000000..27739e6c29
--- /dev/null
+++ b/dir-iterator.h
@@ -0,0 +1,87 @@
+#ifndef DIR_ITERATOR_H
+#define DIR_ITERATOR_H
+
+/*
+ * Iterate over a directory tree.
+ *
+ * Iterate over a directory tree, recursively, including paths of all
+ * types and hidden paths. Skip "." and ".." entries and don't follow
+ * symlinks except for the original path.
+ *
+ * Every time dir_iterator_advance() is called, update the members of
+ * the dir_iterator structure to reflect the next path in the
+ * iteration. The order that paths are iterated over within a
+ * directory is undefined, but directory paths are always iterated
+ * over before the subdirectory contents.
+ *
+ * A typical iteration looks like this:
+ *
+ *     int ok;
+ *     struct iterator *iter = dir_iterator_begin(path);
+ *
+ *     while ((ok = dir_iterator_advance(iter)) == ITER_OK) {
+ *             if (want_to_stop_iteration()) {
+ *                     ok = dir_iterator_abort(iter);
+ *                     break;
+ *             }
+ *
+ *             // Access information about the current path:
+ *             if (S_ISDIR(iter->st.st_mode))
+ *                     printf("%s is a directory\n", iter->relative_path);
+ *     }
+ *
+ *     if (ok != ITER_DONE)
+ *             handle_error();
+ *
+ * Callers are allowed to modify iter->path while they are working,
+ * but they must restore it to its original contents before calling
+ * dir_iterator_advance() again.
+ */
+
+struct dir_iterator {
+	/* The current path: */
+	struct strbuf path;
+
+	/*
+	 * The current path relative to the starting path. This part
+	 * of the path always uses "/" characters to separate path
+	 * components:
+	 */
+	const char *relative_path;
+
+	/* The current basename: */
+	const char *basename;
+
+	/* The result of calling lstat() on path: */
+	struct stat st;
+};
+
+/*
+ * Start a directory iteration over path. Return a dir_iterator that
+ * holds the internal state of the iteration.
+ *
+ * The iteration includes all paths under path, not including path
+ * itself and not including "." or ".." entries.
+ *
+ * path is the starting directory. An internal copy will be made.
+ */
+struct dir_iterator *dir_iterator_begin(const char *path);
+
+/*
+ * Advance the iterator to the first or next item and return ITER_OK.
+ * If the iteration is exhausted, free the dir_iterator and any
+ * resources associated with it and return ITER_DONE. On error, free
+ * dir_iterator and associated resources and return ITER_ERROR. It is
+ * a bug to use iterator or call this function again after it has
+ * returned ITER_DONE or ITER_ERROR.
+ */
+int dir_iterator_advance(struct dir_iterator *iterator);
+
+/*
+ * End the iteration before it has been exhausted. Free the
+ * dir_iterator and any associated resources and return ITER_DONE. On
+ * error, free the dir_iterator and return ITER_ERROR.
+ */
+int dir_iterator_abort(struct dir_iterator *iterator);
+
+#endif
diff --git a/iterator.h b/iterator.h
new file mode 100644
index 0000000000..0f6900e43a
--- /dev/null
+++ b/iterator.h
@@ -0,0 +1,81 @@
+#ifndef ITERATOR_H
+#define ITERATOR_H
+
+/*
+ * Generic constants related to iterators.
+ */
+
+/*
+ * The attempt to advance the iterator was successful; the iterator
+ * reflects the new current entry.
+ */
+#define ITER_OK 0
+
+/*
+ * The iterator is exhausted and has been freed.
+ */
+#define ITER_DONE -1
+
+/*
+ * The iterator experienced an error. The iteration has been aborted
+ * and the iterator has been freed.
+ */
+#define ITER_ERROR -2
+
+/*
+ * Return values for selector functions for merge iterators. The
+ * numerical values of these constants are important and must be
+ * compatible with ITER_DONE and ITER_ERROR.
+ */
+enum iterator_selection {
+	/* End the iteration without an error: */
+	ITER_SELECT_DONE = ITER_DONE,
+
+	/* Report an error and abort the iteration: */
+	ITER_SELECT_ERROR = ITER_ERROR,
+
+	/*
+	 * The next group of constants are masks that are useful
+	 * mainly internally.
+	 */
+
+	/* The LSB selects whether iter0/iter1 is the "current" iterator: */
+	ITER_CURRENT_SELECTION_MASK = 0x01,
+
+	/* iter0 is the "current" iterator this round: */
+	ITER_CURRENT_SELECTION_0 = 0x00,
+
+	/* iter1 is the "current" iterator this round: */
+	ITER_CURRENT_SELECTION_1 = 0x01,
+
+	/* Yield the value from the current iterator? */
+	ITER_YIELD_CURRENT = 0x02,
+
+	/* Discard the value from the secondary iterator? */
+	ITER_SKIP_SECONDARY = 0x04,
+
+	/*
+	 * The constants that a selector function should usually
+	 * return.
+	 */
+
+	/* Yield the value from iter0: */
+	ITER_SELECT_0 = ITER_CURRENT_SELECTION_0 | ITER_YIELD_CURRENT,
+
+	/* Yield the value from iter0 and discard the one from iter1: */
+	ITER_SELECT_0_SKIP_1 = ITER_SELECT_0 | ITER_SKIP_SECONDARY,
+
+	/* Discard the value from iter0 without yielding anything this round: */
+	ITER_SKIP_0 = ITER_CURRENT_SELECTION_1 | ITER_SKIP_SECONDARY,
+
+	/* Yield the value from iter1: */
+	ITER_SELECT_1 = ITER_CURRENT_SELECTION_1 | ITER_YIELD_CURRENT,
+
+	/* Yield the value from iter1 and discard the one from iter0: */
+	ITER_SELECT_1_SKIP_0 = ITER_SELECT_1 | ITER_SKIP_SECONDARY,
+
+	/* Discard the value from iter1 without yielding anything this round: */
+	ITER_SKIP_1 = ITER_CURRENT_SELECTION_0 | ITER_SKIP_SECONDARY
+};
+
+#endif /* ITERATOR_H */
diff --git a/refs.c b/refs.c
index 842c5c7b05..814cad3163 100644
--- a/refs.c
+++ b/refs.c
@@ -1120,6 +1120,26 @@ int head_ref(each_ref_fn fn, void *cb_data)
 	return head_ref_submodule(NULL, fn, cb_data);
 }
 
+/*
+ * Call fn for each reference in the specified submodule for which the
+ * refname begins with prefix. If trim is non-zero, then trim that
+ * many characters off the beginning of each refname before passing
+ * the refname to fn. flags can be DO_FOR_EACH_INCLUDE_BROKEN to
+ * include broken references in the iteration. If fn ever returns a
+ * non-zero value, stop the iteration and return that value;
+ * otherwise, return 0.
+ */
+static int do_for_each_ref(const char *submodule, const char *prefix,
+			   each_ref_fn fn, int trim, int flags, void *cb_data)
+{
+	struct ref_iterator *iter;
+
+	iter = files_ref_iterator_begin(submodule, prefix, flags);
+	iter = prefix_ref_iterator_begin(iter, prefix, trim);
+
+	return do_for_each_ref_iterator(iter, fn, cb_data);
+}
+
 int for_each_ref(each_ref_fn fn, void *cb_data)
 {
 	return do_for_each_ref(NULL, "", fn, 0, 0, cb_data);
diff --git a/refs.h b/refs.h
index 56089d5724..1b02043758 100644
--- a/refs.h
+++ b/refs.h
@@ -52,19 +52,19 @@
 #define RESOLVE_REF_NO_RECURSE 0x02
 #define RESOLVE_REF_ALLOW_BAD_NAME 0x04
 
-extern const char *resolve_ref_unsafe(const char *refname, int resolve_flags,
-				      unsigned char *sha1, int *flags);
+const char *resolve_ref_unsafe(const char *refname, int resolve_flags,
+			       unsigned char *sha1, int *flags);
 
-extern char *resolve_refdup(const char *refname, int resolve_flags,
-			    unsigned char *sha1, int *flags);
+char *resolve_refdup(const char *refname, int resolve_flags,
+		     unsigned char *sha1, int *flags);
 
-extern int read_ref_full(const char *refname, int resolve_flags,
-			 unsigned char *sha1, int *flags);
-extern int read_ref(const char *refname, unsigned char *sha1);
+int read_ref_full(const char *refname, int resolve_flags,
+		  unsigned char *sha1, int *flags);
+int read_ref(const char *refname, unsigned char *sha1);
 
-extern int ref_exists(const char *refname);
+int ref_exists(const char *refname);
 
-extern int is_branch(const char *refname);
+int is_branch(const char *refname);
 
 /*
  * If refname is a non-symbolic reference that refers to a tag object,
@@ -74,24 +74,25 @@ extern int is_branch(const char *refname);
  * Symbolic references are considered unpeelable, even if they
  * ultimately resolve to a peelable tag.
  */
-extern int peel_ref(const char *refname, unsigned char *sha1);
+int peel_ref(const char *refname, unsigned char *sha1);
 
 /**
  * Resolve refname in the nested "gitlink" repository that is located
  * at path.  If the resolution is successful, return 0 and set sha1 to
  * the name of the object; otherwise, return a non-zero value.
  */
-extern int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sha1);
+int resolve_gitlink_ref(const char *path, const char *refname,
+			unsigned char *sha1);
 
 /*
  * Return true iff abbrev_name is a possible abbreviation for
  * full_name according to the rules defined by ref_rev_parse_rules in
  * refs.c.
  */
-extern int refname_match(const char *abbrev_name, const char *full_name);
+int refname_match(const char *abbrev_name, const char *full_name);
 
-extern int dwim_ref(const char *str, int len, unsigned char *sha1, char **ref);
-extern int dwim_log(const char *str, int len, unsigned char *sha1, char **ref);
+int dwim_ref(const char *str, int len, unsigned char *sha1, char **ref);
+int dwim_log(const char *str, int len, unsigned char *sha1, char **ref);
 
 /*
  * A ref_transaction represents a collection of ref updates
@@ -140,7 +141,9 @@ extern int dwim_log(const char *str, int len, unsigned char *sha1, char **ref);
 struct ref_transaction;
 
 /*
- * Bit values set in the flags argument passed to each_ref_fn():
+ * Bit values set in the flags argument passed to each_ref_fn() and
+ * stored in ref_iterator::flags. Other bits are for internal use
+ * only:
  */
 
 /* Reference is a symbolic reference. */
@@ -182,38 +185,45 @@ typedef int each_ref_fn(const char *refname,
  * modifies the reference also returns a nonzero value to immediately
  * stop the iteration.
  */
-extern int head_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data);
-extern int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data, unsigned int broken);
-extern int for_each_tag_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_branch_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_remote_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_replace_ref(each_ref_fn fn, void *cb_data);
-extern int for_each_glob_ref(each_ref_fn fn, const char *pattern, void *cb_data);
-extern int for_each_glob_ref_in(each_ref_fn fn, const char *pattern, const char *prefix, void *cb_data);
-
-extern int head_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
-extern int for_each_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
-extern int for_each_ref_in_submodule(const char *submodule, const char *prefix,
+int head_ref(each_ref_fn fn, void *cb_data);
+int for_each_ref(each_ref_fn fn, void *cb_data);
+int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data);
+int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data,
+			unsigned int broken);
+int for_each_tag_ref(each_ref_fn fn, void *cb_data);
+int for_each_branch_ref(each_ref_fn fn, void *cb_data);
+int for_each_remote_ref(each_ref_fn fn, void *cb_data);
+int for_each_replace_ref(each_ref_fn fn, void *cb_data);
+int for_each_glob_ref(each_ref_fn fn, const char *pattern, void *cb_data);
+int for_each_glob_ref_in(each_ref_fn fn, const char *pattern,
+			 const char *prefix, void *cb_data);
+
+int head_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+int for_each_ref_submodule(const char *submodule,
+			   each_ref_fn fn, void *cb_data);
+int for_each_ref_in_submodule(const char *submodule, const char *prefix,
 		each_ref_fn fn, void *cb_data);
-extern int for_each_tag_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
-extern int for_each_branch_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
-extern int for_each_remote_ref_submodule(const char *submodule, each_ref_fn fn, void *cb_data);
+int for_each_tag_ref_submodule(const char *submodule,
+			       each_ref_fn fn, void *cb_data);
+int for_each_branch_ref_submodule(const char *submodule,
+				  each_ref_fn fn, void *cb_data);
+int for_each_remote_ref_submodule(const char *submodule,
+				  each_ref_fn fn, void *cb_data);
 
-extern int head_ref_namespaced(each_ref_fn fn, void *cb_data);
-extern int for_each_namespaced_ref(each_ref_fn fn, void *cb_data);
+int head_ref_namespaced(each_ref_fn fn, void *cb_data);
+int for_each_namespaced_ref(each_ref_fn fn, void *cb_data);
 
 /* can be used to learn about broken ref and symref */
-extern int for_each_rawref(each_ref_fn fn, void *cb_data);
+int for_each_rawref(each_ref_fn fn, void *cb_data);
 
 static inline const char *has_glob_specials(const char *pattern)
 {
 	return strpbrk(pattern, "?*[");
 }
 
-extern void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname);
-extern void warn_dangling_symrefs(FILE *fp, const char *msg_fmt, const struct string_list *refnames);
+void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname);
+void warn_dangling_symrefs(FILE *fp, const char *msg_fmt,
+			   const struct string_list *refnames);
 
 /*
  * Flags for controlling behaviour of pack_refs()
@@ -245,13 +255,13 @@ int pack_refs(unsigned int flags);
 int safe_create_reflog(const char *refname, int force_create, struct strbuf *err);
 
 /** Reads log for the value of ref during at_time. **/
-extern int read_ref_at(const char *refname, unsigned int flags,
-		       unsigned long at_time, int cnt,
-		       unsigned char *sha1, char **msg,
-		       unsigned long *cutoff_time, int *cutoff_tz, int *cutoff_cnt);
+int read_ref_at(const char *refname, unsigned int flags,
+		unsigned long at_time, int cnt,
+		unsigned char *sha1, char **msg,
+		unsigned long *cutoff_time, int *cutoff_tz, int *cutoff_cnt);
 
 /** Check if a particular reflog exists */
-extern int reflog_exists(const char *refname);
+int reflog_exists(const char *refname);
 
 /*
  * Delete the specified reference. If old_sha1 is non-NULL, then
@@ -260,21 +270,26 @@ extern int reflog_exists(const char *refname);
  * exists, regardless of its old value. It is an error for old_sha1 to
  * be NULL_SHA1. flags is passed through to ref_transaction_delete().
  */
-extern int delete_ref(const char *refname, const unsigned char *old_sha1,
-		      unsigned int flags);
+int delete_ref(const char *refname, const unsigned char *old_sha1,
+	       unsigned int flags);
 
 /*
  * Delete the specified references. If there are any problems, emit
  * errors but attempt to keep going (i.e., the deletes are not done in
- * an all-or-nothing transaction).
+ * an all-or-nothing transaction). flags is passed through to
+ * ref_transaction_delete().
  */
-extern int delete_refs(struct string_list *refnames);
+int delete_refs(struct string_list *refnames, unsigned int flags);
 
 /** Delete a reflog */
-extern int delete_reflog(const char *refname);
+int delete_reflog(const char *refname);
 
 /* iterate over reflog entries */
-typedef int each_reflog_ent_fn(unsigned char *osha1, unsigned char *nsha1, const char *, unsigned long, int, const char *, void *);
+typedef int each_reflog_ent_fn(
+		unsigned char *old_sha1, unsigned char *new_sha1,
+		const char *committer, unsigned long timestamp,
+		int tz, const char *msg, void *cb_data);
+
 int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void *cb_data);
 
@@ -282,7 +297,7 @@ int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn, void
  * Calls the specified function for each reflog file until it returns nonzero,
  * and returns the value
  */
-extern int for_each_reflog(each_ref_fn, void *);
+int for_each_reflog(each_ref_fn fn, void *cb_data);
 
 #define REFNAME_ALLOW_ONELEVEL 1
 #define REFNAME_REFSPEC_PATTERN 2
@@ -295,16 +310,16 @@ extern int for_each_reflog(each_ref_fn, void *);
  * allow a single "*" wildcard character in the refspec. No leading or
  * repeated slashes are accepted.
  */
-extern int check_refname_format(const char *refname, int flags);
+int check_refname_format(const char *refname, int flags);
 
-extern const char *prettify_refname(const char *refname);
+const char *prettify_refname(const char *refname);
 
-extern char *shorten_unambiguous_ref(const char *refname, int strict);
+char *shorten_unambiguous_ref(const char *refname, int strict);
 
 /** rename ref, return 0 on success **/
-extern int rename_ref(const char *oldref, const char *newref, const char *logmsg);
+int rename_ref(const char *oldref, const char *newref, const char *logmsg);
 
-extern int create_symref(const char *refname, const char *target, const char *logmsg);
+int create_symref(const char *refname, const char *target, const char *logmsg);
 
 /*
  * Update HEAD of the specified gitdir.
@@ -313,7 +328,7 @@ extern int create_symref(const char *refname, const char *target, const char *lo
  * $GIT_DIR points to.
  * Return 0 if successful, non-zero otherwise.
  * */
-extern int set_worktree_head_symref(const char *gitdir, const char *target);
+int set_worktree_head_symref(const char *gitdir, const char *target);
 
 enum action_on_err {
 	UPDATE_REFS_MSG_ON_ERR,
@@ -463,7 +478,7 @@ int update_ref(const char *msg, const char *refname,
 	       const unsigned char *new_sha1, const unsigned char *old_sha1,
 	       unsigned int flags, enum action_on_err onerr);
 
-extern int parse_hide_refs_config(const char *var, const char *value, const char *);
+int parse_hide_refs_config(const char *var, const char *value, const char *);
 
 /*
  * Check whether a ref is hidden. If no namespace is set, both the first and
@@ -473,7 +488,7 @@ extern int parse_hide_refs_config(const char *var, const char *value, const char
  * the ref is outside that namespace, the first parameter is NULL. The second
  * parameter always points to the full ref name.
  */
-extern int ref_is_hidden(const char *, const char *);
+int ref_is_hidden(const char *, const char *);
 
 enum ref_type {
 	REF_TYPE_PER_WORKTREE,
@@ -522,11 +537,11 @@ typedef void reflog_expiry_cleanup_fn(void *cb_data);
  * enum expire_reflog_flags. The three function pointers are described
  * above. On success, return zero.
  */
-extern int reflog_expire(const char *refname, const unsigned char *sha1,
-			 unsigned int flags,
-			 reflog_expiry_prepare_fn prepare_fn,
-			 reflog_expiry_should_prune_fn should_prune_fn,
-			 reflog_expiry_cleanup_fn cleanup_fn,
-			 void *policy_cb_data);
+int reflog_expire(const char *refname, const unsigned char *sha1,
+		  unsigned int flags,
+		  reflog_expiry_prepare_fn prepare_fn,
+		  reflog_expiry_should_prune_fn should_prune_fn,
+		  reflog_expiry_cleanup_fn cleanup_fn,
+		  void *policy_cb_data);
 
 #endif /* REFS_H */
diff --git a/refs/files-backend.c b/refs/files-backend.c
index 1bf643025c..12290d2496 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -1,6 +1,8 @@
 #include "../cache.h"
 #include "../refs.h"
 #include "refs-internal.h"
+#include "../iterator.h"
+#include "../dir-iterator.h"
 #include "../lockfile.h"
 #include "../object.h"
 #include "../dir.h"
@@ -513,68 +515,36 @@ static void sort_ref_dir(struct ref_dir *dir)
 }
 
 /*
- * Return true iff the reference described by entry can be resolved to
- * an object in the database.  Emit a warning if the referred-to
- * object does not exist.
+ * Return true if refname, which has the specified oid and flags, can
+ * be resolved to an object in the database. If the referred-to object
+ * does not exist, emit a warning and return false.
  */
-static int ref_resolves_to_object(struct ref_entry *entry)
+static int ref_resolves_to_object(const char *refname,
+				  const struct object_id *oid,
+				  unsigned int flags)
 {
-	if (entry->flag & REF_ISBROKEN)
+	if (flags & REF_ISBROKEN)
 		return 0;
-	if (!has_sha1_file(entry->u.value.oid.hash)) {
-		error("%s does not point to a valid object!", entry->name);
+	if (!has_sha1_file(oid->hash)) {
+		error("%s does not point to a valid object!", refname);
 		return 0;
 	}
 	return 1;
 }
 
 /*
- * current_ref is a performance hack: when iterating over references
- * using the for_each_ref*() functions, current_ref is set to the
- * current reference's entry before calling the callback function.  If
- * the callback function calls peel_ref(), then peel_ref() first
- * checks whether the reference to be peeled is the current reference
- * (it usually is) and if so, returns that reference's peeled version
- * if it is available.  This avoids a refname lookup in a common case.
+ * Return true if the reference described by entry can be resolved to
+ * an object in the database; otherwise, emit a warning and return
+ * false.
  */
-static struct ref_entry *current_ref;
-
-typedef int each_ref_entry_fn(struct ref_entry *entry, void *cb_data);
-
-struct ref_entry_cb {
-	const char *base;
-	int trim;
-	int flags;
-	each_ref_fn *fn;
-	void *cb_data;
-};
-
-/*
- * Handle one reference in a do_for_each_ref*()-style iteration,
- * calling an each_ref_fn for each entry.
- */
-static int do_one_ref(struct ref_entry *entry, void *cb_data)
+static int entry_resolves_to_object(struct ref_entry *entry)
 {
-	struct ref_entry_cb *data = cb_data;
-	struct ref_entry *old_current_ref;
-	int retval;
-
-	if (!starts_with(entry->name, data->base))
-		return 0;
-
-	if (!(data->flags & DO_FOR_EACH_INCLUDE_BROKEN) &&
-	      !ref_resolves_to_object(entry))
-		return 0;
-
-	/* Store the old value, in case this is a recursive call: */
-	old_current_ref = current_ref;
-	current_ref = entry;
-	retval = data->fn(entry->name + data->trim, &entry->u.value.oid,
-			  entry->flag, data->cb_data);
-	current_ref = old_current_ref;
-	return retval;
+	return ref_resolves_to_object(entry->name,
+				      &entry->u.value.oid, entry->flag);
 }
 
+typedef int each_ref_entry_fn(struct ref_entry *entry, void *cb_data);
+
 /*
  * Call fn for each reference in dir that has index in the range
  * offset <= index < dir->nr.  Recurse into subdirectories that are in
@@ -604,78 +574,6 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
 }
 
 /*
- * Call fn for each reference in the union of dir1 and dir2, in order
- * by refname.  Recurse into subdirectories.  If a value entry appears
- * in both dir1 and dir2, then only process the version that is in
- * dir2.  The input dirs must already be sorted, but subdirs will be
- * sorted as needed.  fn is called for all references, including
- * broken ones.
- */
-static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
-				     struct ref_dir *dir2,
-				     each_ref_entry_fn fn, void *cb_data)
-{
-	int retval;
-	int i1 = 0, i2 = 0;
-
-	assert(dir1->sorted == dir1->nr);
-	assert(dir2->sorted == dir2->nr);
-	while (1) {
-		struct ref_entry *e1, *e2;
-		int cmp;
-		if (i1 == dir1->nr) {
-			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data);
-		}
-		if (i2 == dir2->nr) {
-			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data);
-		}
-		e1 = dir1->entries[i1];
-		e2 = dir2->entries[i2];
-		cmp = strcmp(e1->name, e2->name);
-		if (cmp == 0) {
-			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
-				/* Both are directories; descend them in parallel. */
-				struct ref_dir *subdir1 = get_ref_dir(e1);
-				struct ref_dir *subdir2 = get_ref_dir(e2);
-				sort_ref_dir(subdir1);
-				sort_ref_dir(subdir2);
-				retval = do_for_each_entry_in_dirs(
-						subdir1, subdir2, fn, cb_data);
-				i1++;
-				i2++;
-			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
-				/* Both are references; ignore the one from dir1. */
-				retval = fn(e2, cb_data);
-				i1++;
-				i2++;
-			} else {
-				die("conflict between reference and directory: %s",
-				    e1->name);
-			}
-		} else {
-			struct ref_entry *e;
-			if (cmp < 0) {
-				e = e1;
-				i1++;
-			} else {
-				e = e2;
-				i2++;
-			}
-			if (e->flag & REF_DIR) {
-				struct ref_dir *subdir = get_ref_dir(e);
-				sort_ref_dir(subdir);
-				retval = do_for_each_entry_in_dir(
-						subdir, 0, fn, cb_data);
-			} else {
-				retval = fn(e, cb_data);
-			}
-		}
-		if (retval)
-			return retval;
-	}
-}
-
-/*
  * Load all of the refs from the dir into our in-memory cache. The hard work
  * of loading loose refs is done by get_ref_dir(), so we just need to recurse
  * through all of the sub-directories. We do not even need to care about
@@ -691,6 +589,153 @@ static void prime_ref_dir(struct ref_dir *dir)
 	}
 }
 
+/*
+ * A level in the reference hierarchy that is currently being iterated
+ * through.
+ */
+struct cache_ref_iterator_level {
+	/*
+	 * The ref_dir being iterated over at this level. The ref_dir
+	 * is sorted before being stored here.
+	 */