ref_iterator: keep track of whether the iterator output is ordered

References are iterated over in order by refname, but reflogs are not.
Some consumers of reference iteration care about the difference. Teach
each `ref_iterator` to keep track of whether its output is ordered.

`overlay_ref_iterator` is one of the picky consumers. Add a sanity
check in `overlay_ref_iterator_begin()` to verify that its inputs are
ordered.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/refs.c b/refs.c
index b0106b8162c7b8e3770e04c212abb05f1afbd0c3..101c107ee85569e5c453dc5964bf405a3c734976 100644 (file)
--- a/refs.c
+++ b/refs.c
@@ -1309,6 +1309,10 @@ struct ref_iterator *refs_ref_iterator_begin(
        if (trim)
                iter = prefix_ref_iterator_begin(iter, "", trim);
 
+       /* Sanity check for subclasses: */
+       if (!iter->ordered)
+               BUG("reference iterator is not ordered");
+
        return iter;
 }
 

diff --git a/refs/files-backend.c b/refs/files-backend.c
index 961424a4ea7e9d08f65e053243ad2def93456feb..35648c89fc7c152755f486905a94eae93900224e 100644 (file)
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -762,7 +762,7 @@ static struct ref_iterator *files_ref_iterator_begin(
                const char *prefix, unsigned int flags)
 {
        struct files_ref_store *refs;
-       struct ref_iterator *loose_iter, *packed_iter;
+       struct ref_iterator *loose_iter, *packed_iter, *overlay_iter;
        struct files_ref_iterator *iter;
        struct ref_iterator *ref_iterator;
        unsigned int required_flags = REF_STORE_READ;
@@ -772,10 +772,6 @@ static struct ref_iterator *files_ref_iterator_begin(
 
        refs = files_downcast(ref_store, required_flags, "ref_iterator_begin");
 
-       iter = xcalloc(1, sizeof(*iter));
-       ref_iterator = &iter->base;
-       base_ref_iterator_init(ref_iterator, &files_ref_iterator_vtable);
-
        /*
         * We must make sure that all loose refs are read before
         * accessing the packed-refs file; this avoids a race
@@ -811,7 +807,13 @@ static struct ref_iterator *files_ref_iterator_begin(
                        refs->packed_ref_store, prefix, 0,
                        DO_FOR_EACH_INCLUDE_BROKEN);
 
-       iter->iter0 = overlay_ref_iterator_begin(loose_iter, packed_iter);
+       overlay_iter = overlay_ref_iterator_begin(loose_iter, packed_iter);
+
+       iter = xcalloc(1, sizeof(*iter));
+       ref_iterator = &iter->base;
+       base_ref_iterator_init(ref_iterator, &files_ref_iterator_vtable,
+                              overlay_iter->ordered);
+       iter->iter0 = overlay_iter;
        iter->flags = flags;
 
        return ref_iterator;
@@ -2084,7 +2086,7 @@ static struct ref_iterator *files_reflog_iterator_begin(struct ref_store *ref_st
        struct ref_iterator *ref_iterator = &iter->base;
        struct strbuf sb = STRBUF_INIT;
 
-       base_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &files_reflog_iterator_vtable, 0);
        files_reflog_path(refs, &sb, NULL);
        iter->dir_iterator = dir_iterator_begin(sb.buf);
        iter->ref_store = ref_store;

diff --git a/refs/iterator.c b/refs/iterator.c
index 4cf449ef660e2bc9ee5b6ddb4efd8662d27e12b3..c475360f0a8c6bc5aa26876f8fd8d2ca5ebc3ebd 100644 (file)
--- a/refs/iterator.c
+++ b/refs/iterator.c
@@ -25,9 +25,11 @@ int ref_iterator_abort(struct ref_iterator *ref_iterator)
 }
 
 void base_ref_iterator_init(struct ref_iterator *iter,
-                           struct ref_iterator_vtable *vtable)
+                           struct ref_iterator_vtable *vtable,
+                           int ordered)
 {
        iter->vtable = vtable;
+       iter->ordered = !!ordered;
        iter->refname = NULL;
        iter->oid = NULL;
        iter->flags = 0;
@@ -72,7 +74,7 @@ struct ref_iterator *empty_ref_iterator_begin(void)
        struct empty_ref_iterator *iter = xcalloc(1, sizeof(*iter));
        struct ref_iterator *ref_iterator = &iter->base;
 
-       base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &empty_ref_iterator_vtable, 1);
        return ref_iterator;
 }
 
@@ -205,6 +207,7 @@ static struct ref_iterator_vtable merge_ref_iterator_vtable = {
 };
 
 struct ref_iterator *merge_ref_iterator_begin(
+               int ordered,
                struct ref_iterator *iter0, struct ref_iterator *iter1,
                ref_iterator_select_fn *select, void *cb_data)
 {
@@ -219,7 +222,7 @@ struct ref_iterator *merge_ref_iterator_begin(
         * references through only if they exist in both iterators.
         */
 
-       base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable, ordered);
        iter->iter0 = iter0;
        iter->iter1 = iter1;
        iter->select = select;
@@ -268,9 +271,11 @@ struct ref_iterator *overlay_ref_iterator_begin(
        } else if (is_empty_ref_iterator(back)) {
                ref_iterator_abort(back);
                return front;
+       } else if (!front->ordered || !back->ordered) {
+               BUG("overlay_ref_iterator requires ordered inputs");
        }
 
-       return merge_ref_iterator_begin(front, back,
+       return merge_ref_iterator_begin(1, front, back,
                                        overlay_iterator_select, NULL);
 }
 
@@ -361,7 +366,7 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
        iter = xcalloc(1, sizeof(*iter));
        ref_iterator = &iter->base;
 
-       base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &prefix_ref_iterator_vtable, iter0->ordered);
 
        iter->iter0 = iter0;
        iter->prefix = xstrdup(prefix);

diff --git a/refs/packed-backend.c b/refs/packed-backend.c
index 0279aeceeaeb7026feb33b91b53e361ef5413b6b..e411501871d32827f60a89ca2d9a7eda39f1e5d3 100644 (file)
--- a/refs/packed-backend.c
+++ b/refs/packed-backend.c
@@ -437,7 +437,7 @@ static struct ref_iterator *packed_ref_iterator_begin(
 
        iter = xcalloc(1, sizeof(*iter));
        ref_iterator = &iter->base;
-       base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable, 1);
 
        /*
         * Note that get_packed_ref_cache() internally checks whether

diff --git a/refs/ref-cache.c b/refs/ref-cache.c
index 76bb723c8674c3022b271c93b587d941c8e6d397..54dfb5218cab33271cbf5451deaef9379ce50f27 100644 (file)
--- a/refs/ref-cache.c
+++ b/refs/ref-cache.c
@@ -574,7 +574,7 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
 
        iter = xcalloc(1, sizeof(*iter));
        ref_iterator = &iter->base;
-       base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);
+       base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable, 1);
        ALLOC_GROW(iter->levels, 10, iter->levels_alloc);
 
        iter->levels_nr = 1;

diff --git a/refs/ref-cache.h b/refs/ref-cache.h
index 794f000fd31ebad3ce340ffd9af3fc843b089479..a082bfb06c8c420ee5bc4cb81c8b3624f1ba76bc 100644 (file)
--- a/refs/ref-cache.h
+++ b/refs/ref-cache.h
@@ -245,7 +245,8 @@ struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname);
  * Start iterating over references in `cache`. If `prefix` is
  * specified, only include references whose names start with that
  * prefix. If `prime_dir` is true, then fill any incomplete
- * directories before beginning the iteration.
+ * directories before beginning the iteration. The output is ordered
+ * by refname.
  */
 struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,
                                              const char *prefix,

diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index d7d344de73e6f85fed1e8460bce246a894eab6da..d7f233beba00e8fd84625e0eb5092a441fe7676c 100644 (file)
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -329,6 +329,13 @@ int refs_rename_ref_available(struct ref_store *refs,
  */
 struct ref_iterator {
        struct ref_iterator_vtable *vtable;
+
+       /*
+        * Does this `ref_iterator` iterate over references in order
+        * by refname?
+        */
+       unsigned int ordered : 1;
+
        const char *refname;
        const struct object_id *oid;
        unsigned int flags;
@@ -374,7 +381,7 @@ int is_empty_ref_iterator(struct ref_iterator *ref_iterator);
  * which the refname begins with prefix. If trim is non-zero, then
  * trim that many characters off the beginning of each refname. flags
  * can be DO_FOR_EACH_INCLUDE_BROKEN to include broken references in
- * the iteration.
+ * the iteration. The output is ordered by refname.
  */
 struct ref_iterator *refs_ref_iterator_begin(
                struct ref_store *refs,
@@ -400,9 +407,11 @@ typedef enum iterator_selection ref_iterator_select_fn(
  * Iterate over the entries from iter0 and iter1, with the values
  * interleaved as directed by the select function. The iterator takes
  * ownership of iter0 and iter1 and frees them when the iteration is
- * over.
+ * over. A derived class should set `ordered` to 1 or 0 based on
+ * whether it generates its output in order by reference name.
  */
 struct ref_iterator *merge_ref_iterator_begin(
+               int ordered,
                struct ref_iterator *iter0, struct ref_iterator *iter1,
                ref_iterator_select_fn *select, void *cb_data);
 
@@ -431,6 +440,8 @@ struct ref_iterator *overlay_ref_iterator_begin(
  * As an convenience to callers, if prefix is the empty string and
  * trim is zero, this function returns iter0 directly, without
  * wrapping it.
+ *
+ * The resulting ref_iterator is ordered if iter0 is.
  */
 struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
                                               const char *prefix,
@@ -441,11 +452,14 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0,
 /*
  * Base class constructor for ref_iterators. Initialize the
  * ref_iterator part of iter, setting its vtable pointer as specified.
+ * `ordered` should be set to 1 if the iterator will iterate over
+ * references in order by refname; otherwise it should be set to 0.
  * This is meant to be called only by the initializers of derived
  * classes.
  */
 void base_ref_iterator_init(struct ref_iterator *iter,
-                           struct ref_iterator_vtable *vtable);
+                           struct ref_iterator_vtable *vtable,
+                           int ordered);
 
 /*
  * Base class destructor for ref_iterators. Destroy the ref_iterator
@@ -564,7 +578,8 @@ typedef int rename_ref_fn(struct ref_store *ref_store,
  * Iterate over the references in `ref_store` whose names start with
  * `prefix`. `prefix` is matched as a literal string, without regard
  * for path separators. If prefix is NULL or the empty string, iterate
- * over all references in `ref_store`.
+ * over all references in `ref_store`. The output is ordered by
+ * refname.
  */
 typedef struct ref_iterator *ref_iterator_begin_fn(
                struct ref_store *ref_store,