8 files changed, 314 insertions, 0 deletions

diff --git a/include/git2/refs.h b/include/git2/refs.h
index e1d425352..48ecc96e0 100644
--- a/include/git2/refs.h
+++ b/include/git2/refs.h
@@ -347,6 +347,31 @@ GIT_EXTERN(void) git_reference_free(git_reference *ref);
 GIT_EXTERN(int) git_reference_cmp(git_reference *ref1, git_reference *ref2);
 
 /**
+ * Create an iterator for the repo's references
+ *
+ * @param out pointer in which to store the iterator
+ * @param repo the repository
+ * @return 0 or an error code
+ */
+GIT_EXTERN(int) git_reference_iterator_new(git_reference_iterator **out, git_repository *repo);
+
+/**
+ * Get the next reference name
+ *
+ * @param out pointer in which to store the string
+ * @param iter the iterator
+ * @param 0, GIT_ITEROVER if there are no more; or an error code
+ */
+GIT_EXTERN(int) git_reference_next(const char **out, git_reference_iterator *iter);
+
+/**
+ * Free the iterator and its associated resources
+ *
+ * @param iter the iterator to free
+ */
+GIT_EXTERN(void) git_reference_iterator_free(git_reference_iterator *iter);
+
+/**
  * Perform a callback on each reference in the repository whose name
  * matches the given pattern.
  *
diff --git a/include/git2/sys/refdb_backend.h b/include/git2/sys/refdb_backend.h
index d5f599fec..4c882b5cd 100644
--- a/include/git2/sys/refdb_backend.h
+++ b/include/git2/sys/refdb_backend.h
@@ -20,6 +20,22 @@
  */
 GIT_BEGIN_DECL
 
+
+/**
+ * Every backend's iterator must have a pointer to itself as the first
+ * element, so the API can talk to it. You'd define your iterator as
+ *
+ *     struct my_iterator {
+ *             git_reference_iterator parent;
+ *             ...
+ *     }
+ *
+ * and assing `iter->parent.backend` to your `git_refdb_backend`.
+ */
+struct git_reference_iterator {
+	git_refdb_backend *backend;
+};
+
 /** An instance for a custom backend */
 struct git_refdb_backend {
     unsigned int version;
@@ -66,6 +82,25 @@ struct git_refdb_backend {
 		void *payload);
 
 	/**
+	 * Allocate an iterator object for the backend
+	 */
+	int (*iterator)(
+		git_reference_iterator **iter,
+		struct git_refdb_backend *backend);
+
+	/**
+	 * Return the current value and advance the iterator.
+	 */
+	int (*next)(
+		const char **name,
+		git_reference_iterator *iter);
+
+	/**
+	 * Free the iterator
+	 */
+	void (*iterator_free)(
+		git_reference_iterator *iter);
+	/*
 	 * Writes the given reference to the refdb.  A refdb implementation
 	 * must provide this function.
 	 */
diff --git a/include/git2/types.h b/include/git2/types.h
index aca9ed927..43751d3b0 100644
--- a/include/git2/types.h
+++ b/include/git2/types.h
@@ -165,6 +165,10 @@ typedef struct git_signature {
 /** In-memory representation of a reference. */
 typedef struct git_reference git_reference;
 
+/** Iterator for references */
+typedef struct git_reference_iterator  git_reference_iterator;
+
+
 /** Basic type of any Git reference. */
 typedef enum {
 	GIT_REF_INVALID = 0, /** Invalid reference */
diff --git a/src/refdb.c b/src/refdb.c
index 33a1934d1..73882e807 100644
--- a/src/refdb.c
+++ b/src/refdb.c
@@ -124,6 +124,30 @@ int git_refdb_lookup(git_reference **out, git_refdb *db, const char *ref_name)
 	return error;
 }
 
+int git_refdb_iterator(git_reference_iterator **out, git_refdb *db)
+{
+	git_reference_iterator *iter;
+
+	/* FIXME: don't segfault when there is no backends */
+	if (db->backend->iterator(&iter, db->backend) < 0) {
+		git__free(iter);
+		return -1;
+	}
+
+	*out = iter;
+	return 0;
+}
+
+int git_refdb_next(const char **out, git_reference_iterator *iter)
+{
+	return iter->backend->next(out, iter);
+}
+
+void git_refdb_iterator_free(git_reference_iterator *iter)
+{
+	iter->backend->iterator_free(iter);
+}
+
 int git_refdb_foreach(
 	git_refdb *db,
 	unsigned int list_flags,
diff --git a/src/refdb.h b/src/refdb.h
index 047113ac8..a243f627c 100644
--- a/src/refdb.h
+++ b/src/refdb.h
@@ -39,6 +39,10 @@ int git_refdb_foreach_glob(
 	git_reference_foreach_cb callback,
 	void *payload);
 
+int git_refdb_iterator(git_reference_iterator **out, git_refdb *db);
+int git_refdb_next(const char **out, git_reference_iterator *iter);
+void git_refdb_iterator_free(git_reference_iterator *iter);
+
 int git_refdb_write(git_refdb *refdb, const git_reference *ref);
 
 int git_refdb_delete(git_refdb *refdb, const git_reference *ref);
diff --git a/src/refdb_fs.c b/src/refdb_fs.c
index c0a32bae7..5c8e59f52 100644
--- a/src/refdb_fs.c
+++ b/src/refdb_fs.c
@@ -13,6 +13,7 @@
 #include "reflog.h"
 #include "refdb.h"
 #include "refdb_fs.h"
+#include "iterator.h"
 
 #include <git2/tag.h>
 #include <git2/object.h>
@@ -652,6 +653,128 @@ static int refdb_fs_backend__foreach(
 	return data.callback_error ? GIT_EUSER : result;
 }
 
+typedef struct {
+	git_reference_iterator parent;
+	unsigned int loose;
+	/* packed */
+	git_strmap *h;
+	khiter_t k;
+	/* loose */
+	git_iterator *fsiter;
+	git_buf buf;
+} refdb_fs_iter;
+
+static int refdb_fs_backend__iterator(git_reference_iterator **out, git_refdb_backend *_backend)
+{
+	refdb_fs_iter *iter;
+	refdb_fs_backend *backend;
+
+	assert(_backend);
+	backend = (refdb_fs_backend *)_backend;
+
+	if (packed_load(backend) < 0)
+		return -1;
+
+	iter = git__calloc(1, sizeof(refdb_fs_iter));
+	GITERR_CHECK_ALLOC(iter);
+
+	iter->parent.backend = _backend;
+	iter->h = backend->refcache.packfile;
+	iter->k = kh_begin(backend->refcache.packfile);
+
+	*out = (git_reference_iterator *)iter;
+
+	return 0;
+}
+
+static void refdb_fs_backend__iterator_free(git_reference_iterator *_iter)
+{
+	refdb_fs_iter *iter = (refdb_fs_iter *) _iter;
+
+	git_buf_free(&iter->buf);
+	git_iterator_free(iter->fsiter);
+	git__free(iter);
+}
+
+static int iter_packed(const char **out, refdb_fs_iter *iter)
+{
+	/* Move forward to the next entry */
+	while (!kh_exist(iter->h, iter->k)) {
+		iter->k++;
+		if (iter->k == kh_end(iter->h))
+			return GIT_ITEROVER;
+	}
+
+	*out = kh_key(iter->h, iter->k);
+	iter->k++;
+
+	return 0;
+}
+
+static int iter_loose(const char **out, refdb_fs_iter *iter)
+{
+	const git_index_entry *entry;
+	int retry;
+	git_strmap *packfile_refs;
+	refdb_fs_backend *backend = (refdb_fs_backend *) iter->parent.backend;
+
+	packfile_refs = backend->refcache.packfile;
+
+	do {
+		khiter_t pos;
+		if (git_iterator_current(&entry, iter->fsiter) < 0)
+			return -1;
+
+		git_buf_clear(&iter->buf);
+		if (!entry)
+			return GIT_ITEROVER;
+
+		if (git_buf_printf(&iter->buf, "refs/%s", entry->path) < 0)
+			return -1;
+
+		git_iterator_advance(NULL, iter->fsiter);
+
+		/* Skip this one if we already listed it in packed */
+		pos = git_strmap_lookup_index(packfile_refs, git_buf_cstr(&iter->buf));
+		retry = 0;
+		if (git_strmap_valid_index(packfile_refs, pos) ||
+		    !git_reference_is_valid_name(git_buf_cstr(&iter->buf)))
+			retry = 1;
+
+		*out = git_buf_cstr(&iter->buf);
+	} while (retry);
+
+	return 0;
+}
+
+static int iter_loose_setup(refdb_fs_iter *iter)
+{
+	refdb_fs_backend *backend = (refdb_fs_backend *) iter->parent.backend;
+
+	git_buf_clear(&iter->buf);
+	if (git_buf_printf(&iter->buf, "%s/refs", backend->path) < 0)
+		return -1;
+
+	return git_iterator_for_filesystem(&iter->fsiter, git_buf_cstr(&iter->buf), 0, NULL, NULL);
+}
+
+static int refdb_fs_backend__next(const char **out, git_reference_iterator *_iter)
+{
+	refdb_fs_iter *iter = (refdb_fs_iter *)_iter;
+
+	/* First round of checks to make sure where we are */
+	if (!iter->loose && iter->k == kh_end(iter->h)) {
+		if (iter_loose_setup(iter) < 0)
+			return -1;
+		iter->loose = 1;
+	}
+
+	if (!iter->loose)
+		return iter_packed(out, iter);
+	else
+		return iter_loose(out, iter);
+}
+
 static int loose_write(refdb_fs_backend *backend, const git_reference *ref)
 {
 	git_filebuf file = GIT_FILEBUF_INIT;
@@ -1082,6 +1205,9 @@ int git_refdb_backend_fs(
 	backend->parent.exists = &refdb_fs_backend__exists;
 	backend->parent.lookup = &refdb_fs_backend__lookup;
 	backend->parent.foreach = &refdb_fs_backend__foreach;
+	backend->parent.iterator = &refdb_fs_backend__iterator;
+	backend->parent.next = &refdb_fs_backend__next;
+	backend->parent.iterator_free = &refdb_fs_backend__iterator_free;
 	backend->parent.write = &refdb_fs_backend__write;
 	backend->parent.delete = &refdb_fs_backend__delete;
 	backend->parent.compress = &refdb_fs_backend__compress;
diff --git a/src/refs.c b/src/refs.c
index b85a2e828..547bd570c 100644
--- a/src/refs.c
+++ b/src/refs.c
@@ -568,6 +568,26 @@ int git_reference_foreach(
 	return git_refdb_foreach(refdb, list_flags, callback, payload);
 }
 
+int git_reference_iterator_new(git_reference_iterator **out, git_repository *repo)
+{
+	git_refdb *refdb;
+
+	if (git_repository_refdb__weakptr(&refdb, repo) < 0)
+		return -1;
+
+	return git_refdb_iterator(out, refdb);
+}
+
+int git_reference_next(const char **out, git_reference_iterator *iter)
+{
+	return git_refdb_next(out, iter);
+}
+
+void git_reference_iterator_free(git_reference_iterator *iter)
+{
+	git_refdb_iterator_free(iter);
+}
+
 static int cb__reflist_add(const char *ref, void *data)
 {
 	return git_vector_insert((git_vector *)data, git__strdup(ref));
diff --git a/tests-clar/refs/iterator.c b/tests-clar/refs/iterator.c
new file mode 100644
index 000000000..aef0453c8
--- /dev/null
+++ b/tests-clar/refs/iterator.c
@@ -0,0 +1,76 @@
+#include "clar_libgit2.h"
+#include "refs.h"
+#include "vector.h"
+
+static git_repository *repo;
+
+void test_refs_iterator__initialize(void)
+{
+	cl_git_pass(git_repository_open(&repo, cl_fixture("testrepo.git")));
+}
+
+void test_refs_iterator__cleanup(void)
+{
+	git_repository_free(repo);
+}
+
+static const char *refnames[] = {
+	"refs/heads/br2",
+	"refs/heads/cannot-fetch",
+	"refs/heads/chomped",
+	"refs/heads/haacked",
+	"refs/heads/master",
+	"refs/heads/not-good",
+	"refs/heads/packed",
+	"refs/heads/packed-test",
+	"refs/heads/subtrees",
+	"refs/heads/test",
+	"refs/heads/track-local",
+	"refs/heads/trailing",
+	"refs/notes/fanout",
+	"refs/remotes/test/master",
+	"refs/tags/annotated_tag_to_blob",
+	"refs/tags/e90810b",
+	"refs/tags/hard_tag",
+	"refs/tags/point_to_blob",
+	"refs/tags/taggerless",
+	"refs/tags/test",
+	"refs/tags/wrapped_tag",
+};
+
+void test_refs_iterator__list(void)
+{
+	git_reference_iterator *iter;
+	git_vector output;
+	char *refname;
+	int error;
+	size_t i;
+
+	cl_git_pass(git_vector_init(&output, 32, git__strcmp_cb));
+	cl_git_pass(git_reference_iterator_new(&iter, repo));
+
+	do {
+		const char *name;
+		error = git_reference_next(&name, iter);
+		cl_assert(error == 0 || error == GIT_ITEROVER);
+		if (error != GIT_ITEROVER) {
+			char *dup = git__strdup(name);
+			cl_assert(dup != NULL);
+			cl_git_pass(git_vector_insert(&output, dup));
+		}
+	} while (!error);
+
+	cl_assert_equal_i(output.length, ARRAY_SIZE(refnames));
+
+	git_vector_sort(&output);
+	git_vector_foreach(&output, i, refname) {
+		cl_assert_equal_s(refname, refnames[i]);
+	}
+
+	git_reference_iterator_free(iter);
+
+	git_vector_foreach(&output, i, refname) {
+		git__free(refname);
+	}
+	git_vector_free(&output);
+}