[PATCH v3] refs/files: keep root refs out of loose ref cache

[Andy Koppe <andy.koppe@gmail.com>]

With the files backend, root refs such as HEAD or ORIG_HEAD are only
added to the loose ref cache if REFS_FOR_EACH_INCLUDE_ROOT_REFS is
passed when the cache is created. If the cache has already been created
for an earlier ref iterator, root refs are silently omitted. Conversely,
once they have been added, any later iterator also yields them, whether
or not they were requested. This has been the case since d0f00c1ac1
(refs: introduce `refs_for_each_include_root_refs()`, 2024-02-23).

For example, `git for-each-ref --include-root-refs --merged=main` omits
root refs that are merged into main, because looking up the given commit
loads the replace refs, which populates the loose ref cache first. The
reftable backend is not affected, as it filters root refs for each
iterator rather than caching them.

Fix this by keeping the root refs out of the loose ref cache. Instead,
read them into a separate, temporary ref cache whenever an iterator is
requested with REFS_FOR_EACH_INCLUDE_ROOT_REFS, and overlay an iterator
over that cache on the loose ref iterator. The cache is freed along with
the iterator.

Alternatively, the root refs could always be added to the loose ref
cache and skipped during iteration unless requested. But that would mean
reading them in every command that uses the loose ref cache, even though
only two call sites actually request them. Also, keeping the root ref
cache for reuse by later iterators is not worthwhile, because those two
call sites only request the root refs once per command.

Signed-off-by: Andy Koppe <andy.koppe@gmail.com>
---
Changes from v1:
- Amend commit message for clarity and to discuss alternatives.
- Move new create_root_ref_cache() below get_loose_ref_cache() because
  its comment references the loose ref cache and because it makes for
  a cleaner diff. Tighten up the comment.

Changes from v2:
- Drop fixes to documentation of REFS_FOR_EACH_INCLUDE_ROOT_REFS and
  --include-root-refs added in v2. I'll create a separate patch with
  those as well as other fixes for outdated uses of "pseudoref".

The range diff shows the changes from v1, because they're of more
interest than dropping the documentation changes I'd added in v2.

 refs/files-backend.c           | 37 ++++++++++++++++++++++++++--------
 t/t6302-for-each-ref-filter.sh | 12 +++++++++++
 2 files changed, 41 insertions(+), 8 deletions(-)

diff --git a/refs/files-backend.c b/refs/files-backend.c
index 71628550f2..9d1e527114 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -481,8 +481,7 @@ static void add_root_refs(struct files_ref_store *refs,
 	for_each_root_ref(refs, fill_root_ref, &data);
 }
 
-static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs,
-					     unsigned int flags)
+static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs)
 {
 	if (!refs->loose) {
 		struct ref_dir *dir;
@@ -499,9 +498,6 @@ static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs,
 
 		dir = get_ref_dir(refs->loose->root);
 
-		if (flags & REFS_FOR_EACH_INCLUDE_ROOT_REFS)
-			add_root_refs(refs, dir);
-
 		/*
 		 * Add an incomplete entry for "refs/" (to be filled
 		 * lazily):
@@ -511,6 +507,19 @@ static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs,
 	return refs->loose;
 }
 
+/*
+ * Root refs are kept out of the loose ref cache because ref iterators must
+ * only include them when requested with REFS_FOR_EACH_INCLUDE_ROOT_REFS.
+ */
+static struct ref_cache *create_root_ref_cache(struct files_ref_store *refs)
+{
+	struct ref_cache *cache = create_ref_cache(&refs->base, NULL);
+
+	cache->root->flag &= ~REF_INCOMPLETE;
+	add_root_refs(refs, get_ref_dir(cache->root));
+	return cache;
+}
+
 static int read_ref_internal(struct ref_store *ref_store, const char *refname,
 			     struct object_id *oid, struct strbuf *referent,
 			     unsigned int *type, int *failure_errno, int skip_packed_refs)
@@ -1004,6 +1013,7 @@ struct files_ref_iterator {
 	struct ref_iterator base;
 
 	struct ref_iterator *iter0;
+	struct ref_cache *root_refs;
 	struct repository *repo;
 	unsigned int flags;
 };
@@ -1053,6 +1063,7 @@ static void files_ref_iterator_release(struct ref_iterator *ref_iterator)
 	struct files_ref_iterator *iter =
 		(struct files_ref_iterator *)ref_iterator;
 	ref_iterator_free(iter->iter0);
+	free_ref_cache(iter->root_refs);
 }
 
 static struct ref_iterator_vtable files_ref_iterator_vtable = {
@@ -1068,6 +1079,7 @@ static struct ref_iterator *files_ref_iterator_begin(
 {
 	struct files_ref_store *refs;
 	struct ref_iterator *loose_iter, *packed_iter, *overlay_iter;
+	struct ref_cache *root_refs = NULL;
 	struct files_ref_iterator *iter;
 	struct ref_iterator *ref_iterator;
 	unsigned int required_flags = REF_STORE_READ;
@@ -1094,9 +1106,17 @@ static struct ref_iterator *files_ref_iterator_begin(
 	 * disk, and re-reads it if not.
 	 */
 
-	loose_iter = cache_ref_iterator_begin(get_loose_ref_cache(refs, flags),
+	loose_iter = cache_ref_iterator_begin(get_loose_ref_cache(refs),
 					      prefix, ref_store->repo, 1);
 
+	if (flags & REFS_FOR_EACH_INCLUDE_ROOT_REFS) {
+		root_refs = create_root_ref_cache(refs);
+		loose_iter = overlay_ref_iterator_begin(
+				cache_ref_iterator_begin(root_refs, prefix,
+							 ref_store->repo, 0),
+				loose_iter);
+	}
+
 	/*
 	 * The packed-refs file might contain broken references, for
 	 * example an old version of a reference that points at an
@@ -1118,6 +1138,7 @@ static struct ref_iterator *files_ref_iterator_begin(
 	ref_iterator = &iter->base;
 	base_ref_iterator_init(ref_iterator, &files_ref_iterator_vtable);
 	iter->iter0 = overlay_iter;
+	iter->root_refs = root_refs;
 	iter->repo = ref_store->repo;
 	iter->flags = flags;
 
@@ -1490,7 +1511,7 @@ static int should_pack_refs(struct files_ref_store *refs,
 	if (limit < 16)
 		limit = 16;
 
-	iter = cache_ref_iterator_begin(get_loose_ref_cache(refs, 0), NULL,
+	iter = cache_ref_iterator_begin(get_loose_ref_cache(refs), NULL,
 					refs->base.repo, 0);
 	while ((ret = ref_iterator_advance(iter)) == ITER_OK) {
 		if (should_pack_ref(refs, &iter->ref, opts))
@@ -1530,7 +1551,7 @@ static int files_optimize(struct ref_store *ref_store,
 
 	packed_refs_lock(refs->packed_ref_store, LOCK_DIE_ON_ERROR, &err);
 
-	iter = cache_ref_iterator_begin(get_loose_ref_cache(refs, 0), NULL,
+	iter = cache_ref_iterator_begin(get_loose_ref_cache(refs), NULL,
 					refs->base.repo, 0);
 	while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
 		/*
diff --git a/t/t6302-for-each-ref-filter.sh b/t/t6302-for-each-ref-filter.sh
index 7f060d97bf..a2fc257f98 100755
--- a/t/t6302-for-each-ref-filter.sh
+++ b/t/t6302-for-each-ref-filter.sh
@@ -96,6 +96,18 @@ test_expect_success '--include-root-refs omits dangling symrefs' '
 	)
 '
 
+test_expect_success '--include-root-refs with --merged' '
+	cat >expect <<-\EOF &&
+	HEAD
+	ORIG_HEAD
+	EOF
+	test_when_finished "git update-ref -d ORIG_HEAD" &&
+	git update-ref ORIG_HEAD main &&
+	git for-each-ref --format="%(refname)" --include-root-refs \
+		--merged=main "*HEAD" >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'filtering with --points-at' '
 	cat >expect <<-\EOF &&
 	refs/heads/main

Range-diff against v1:
1:  5db169a16e ! 1:  49f2b11aad refs/files: keep root refs out of loose ref cache
    @@ Commit message
     
         With the files backend, root refs such as HEAD or ORIG_HEAD are only
         added to the loose ref cache if REFS_FOR_EACH_INCLUDE_ROOT_REFS is
    -    passed to the iteration that creates the cache. If the cache has already
    -    been created by an earlier iteration, root refs are silently omitted.
    -    Conversely, once they have been added, any later iteration also yields
    -    them, whether or not it asked for them. This has been the case since
    -    d0f00c1ac17 (refs: introduce `refs_for_each_include_root_refs()`).
    +    passed when the cache is created. If the cache has already been created
    +    for an earlier ref iterator, root refs are silently omitted. Conversely,
    +    once they have been added, any later iterator also yields them, whether
    +    or not they were requested. This has been the case since d0f00c1ac1
    +    (refs: introduce `refs_for_each_include_root_refs()`, 2024-02-23).
     
         For example, `git for-each-ref --include-root-refs --merged=main` omits
         root refs that are merged into main, because looking up the given commit
         loads the replace refs, which populates the loose ref cache first. The
    -    reftable backend is not affected.
    +    reftable backend is not affected, as it filters root refs for each
    +    iterator rather than caching them.
     
    -    Fix this by keeping the root refs out of the shared loose ref cache.
    -    Instead, read them into a separate ref cache whenever an iteration asks
    -    for them, and overlay its iterator on the loose ref iterator. The cache
    -    is freed when the iteration finishes.
    +    Fix this by keeping the root refs out of the loose ref cache. Instead,
    +    read them into a separate, temporary ref cache whenever an iterator is
    +    requested with REFS_FOR_EACH_INCLUDE_ROOT_REFS, and overlay an iterator
    +    over that cache on the loose ref iterator. The cache is freed along with
    +    the iterator.
    +
    +    Alternatively, the root refs could always be added to the loose ref
    +    cache and skipped during iteration unless requested. But that would mean
    +    reading them in every command that uses the loose ref cache, even though
    +    only two call sites actually request them. Also, keeping the root ref
    +    cache for reuse by later iterators is not worthwhile, because those two
    +    call sites only request the root refs once per command.
     
         Signed-off-by: Andy Koppe <andy.koppe@gmail.com>
     
    @@ refs/files-backend.c: static void add_root_refs(struct files_ref_store *refs,
      
     -static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs,
     -					     unsigned int flags)
    -+/*
    -+ * Create a separate ref cache containing only the root refs. These are kept
    -+ * out of the loose ref cache, which may already exist and is shared by
    -+ * iterations that should not include them.
    -+ */
    -+static struct ref_cache *create_root_ref_cache(struct files_ref_store *refs)
    -+{
    -+	struct ref_cache *cache = create_ref_cache(&refs->base, NULL);
    -+
    -+	cache->root->flag &= ~REF_INCOMPLETE;
    -+	add_root_refs(refs, get_ref_dir(cache->root));
    -+	return cache;
    -+}
    -+
     +static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs)
      {
      	if (!refs->loose) {
    @@ refs/files-backend.c: static struct ref_cache *get_loose_ref_cache(struct files_
      		/*
      		 * Add an incomplete entry for "refs/" (to be filled
      		 * lazily):
    +@@ refs/files-backend.c: static struct ref_cache *get_loose_ref_cache(struct files_ref_store *refs,
    + 	return refs->loose;
    + }
    + 
    ++/*
    ++ * Root refs are kept out of the loose ref cache because ref iterators must
    ++ * only include them when requested with REFS_FOR_EACH_INCLUDE_ROOT_REFS.
    ++ */
    ++static struct ref_cache *create_root_ref_cache(struct files_ref_store *refs)
    ++{
    ++	struct ref_cache *cache = create_ref_cache(&refs->base, NULL);
    ++
    ++	cache->root->flag &= ~REF_INCOMPLETE;
    ++	add_root_refs(refs, get_ref_dir(cache->root));
    ++	return cache;
    ++}
    ++
    + static int read_ref_internal(struct ref_store *ref_store, const char *refname,
    + 			     struct object_id *oid, struct strbuf *referent,
    + 			     unsigned int *type, int *failure_errno, int skip_packed_refs)
     @@ refs/files-backend.c: struct files_ref_iterator {
      	struct ref_iterator base;
      
-- 
2.56.0