[PATCH 0/5] handle tag recursion in pack-objects --include-tag

[PATCH 0/5] handle tag recursion in pack-objects --include-tag

[Jeff King]

If you have a tag of a tag of a commit, and the middle tag isn't
otherwise reachable, then "pack-objects --include-tag" will not include
the middle tag, and certain invocations of "clone" will fail. See the
final patch below for the gory details.

The first five patches are just test cleanup and modernization in
preparation (though note that the 3rd one actually fixes a minor bug in
the test script).

  [1/5]: t5305: move cleanup into test block
  [2/5]: t5305: drop "dry-run" of unpack-objects
  [3/5]: t5305: use "git -C"
  [4/5]: t5305: simplify packname handling
  [5/5]: pack-objects: walk tag chains for --include-tag

-Peff

[PATCH 1/5] t5305: move cleanup into test block

[Jeff King]

We usually try to avoid doing any significant actions
outside of test blocks. Although "rm -rf" is unlikely to
either fail or to generate output, moving these to the
point of use makes it more clear that they are part of the
overall setup of "clone.git".

Signed-off-by: Jeff King <peff@peff.net>
---
 t/t5305-include-tag.sh | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/t/t5305-include-tag.sh b/t/t5305-include-tag.sh
index f314ad5..6018404 100755
--- a/t/t5305-include-tag.sh
+++ b/t/t5305-include-tag.sh
@@ -25,7 +25,6 @@ test_expect_success setup '
 	} >obj-list
 '
 
-rm -rf clone.git
 test_expect_success 'pack without --include-tag' '
 	packname_1=$(git pack-objects \
 		--window=0 \
@@ -33,6 +32,7 @@ test_expect_success 'pack without --include-tag' '
 '
 
 test_expect_success 'unpack objects' '
+	rm -rf clone.git &&
 	(
 		GIT_DIR=clone.git &&
 		export GIT_DIR &&
@@ -51,7 +51,6 @@ test_expect_success 'check unpacked result (have commit, no tag)' '
 	test_cmp list.expect list.actual
 '
 
-rm -rf clone.git
 test_expect_success 'pack with --include-tag' '
 	packname_1=$(git pack-objects \
 		--window=0 \
@@ -60,6 +59,7 @@ test_expect_success 'pack with --include-tag' '
 '
 
 test_expect_success 'unpack objects' '
+	rm -rf clone.git &&
 	(
 		GIT_DIR=clone.git &&
 		export GIT_DIR &&
-- 
2.10.0.rc2.154.gb4a4b8b

[PATCH 2/5] t5305: drop "dry-run" of unpack-objects

[Jeff King]

For each test we do a dry-run of unpack-objects, followed by
a real run, followed by confirming that it contained the
objects we expected. The dry-run is telling us nothing, as
any errors it encounters would be found in the real run.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/t5305-include-tag.sh | 2 --
 1 file changed, 2 deletions(-)

diff --git a/t/t5305-include-tag.sh b/t/t5305-include-tag.sh
index 6018404..787fc83 100755
--- a/t/t5305-include-tag.sh
+++ b/t/t5305-include-tag.sh
@@ -37,7 +37,6 @@ test_expect_success 'unpack objects' '
 		GIT_DIR=clone.git &&
 		export GIT_DIR &&
 		git init &&
-		git unpack-objects -n <test-1-${packname_1}.pack &&
 		git unpack-objects <test-1-${packname_1}.pack
 	)
 '
@@ -64,7 +63,6 @@ test_expect_success 'unpack objects' '
 		GIT_DIR=clone.git &&
 		export GIT_DIR &&
 		git init &&
-		git unpack-objects -n <test-2-${packname_1}.pack &&
 		git unpack-objects <test-2-${packname_1}.pack
 	)
 '
-- 
2.10.0.rc2.154.gb4a4b8b

[PATCH 3/5] t5305: use "git -C"

[Jeff King]

This test unpacks objects into a separate repository, and
accesses it by setting GIT_DIR in a subshell. We can do the
same thing these days by using "git init <repo>" and "git
-C". In most cases this is shorter, though when there are
multiple commands, we may end up repeating the "-C".

However, this repetition can actually be a good thing. This
patch also fixes a bug introduced by 512477b (tests: use
"env" to run commands with temporary env-var settings,
2014-03-18). That commit essentially converted:

   (GIT_DIR=...; export GIT_DIR
    cmd1 &&
    cmd2)

into:

   (GIT_DIR=... cmd1 &&
    cmd2)

which obviously loses the GIT_DIR setting for cmd2 (we never
noticed the bug because it simply runs "cmd2" in the parent
repo, which means we were simply failing to test anything
interesting). By using "git -C" rather than a subshell, it
becomes quite obvious where each command is supposed to be
running.

Signed-off-by: Jeff King <peff@peff.net>
---
 t/t5305-include-tag.sh | 28 +++++++---------------------
 1 file changed, 7 insertions(+), 21 deletions(-)

diff --git a/t/t5305-include-tag.sh b/t/t5305-include-tag.sh
index 787fc83..089a3e9 100755
--- a/t/t5305-include-tag.sh
+++ b/t/t5305-include-tag.sh
@@ -33,20 +33,14 @@ test_expect_success 'pack without --include-tag' '
 
 test_expect_success 'unpack objects' '
 	rm -rf clone.git &&
-	(
-		GIT_DIR=clone.git &&
-		export GIT_DIR &&
-		git init &&
-		git unpack-objects <test-1-${packname_1}.pack
-	)
+	git init clone.git &&
+	git -C clone.git unpack-objects <test-1-${packname_1}.pack
 '
 
 test_expect_success 'check unpacked result (have commit, no tag)' '
 	git rev-list --objects $commit >list.expect &&
-	(
-		test_must_fail env GIT_DIR=clone.git git cat-file -e $tag &&
-		git rev-list --objects $commit
-	) >list.actual &&
+	test_must_fail git -C clone.git cat-file -e $tag &&
+	git -C clone.git rev-list --objects $commit >list.actual &&
 	test_cmp list.expect list.actual
 '
 
@@ -59,21 +53,13 @@ test_expect_success 'pack with --include-tag' '
 
 test_expect_success 'unpack objects' '
 	rm -rf clone.git &&
-	(
-		GIT_DIR=clone.git &&
-		export GIT_DIR &&
-		git init &&
-		git unpack-objects <test-2-${packname_1}.pack
-	)
+	git init clone.git &&
+	git -C clone.git unpack-objects <test-2-${packname_1}.pack
 '
 
 test_expect_success 'check unpacked result (have commit, have tag)' '
 	git rev-list --objects mytag >list.expect &&
-	(
-		GIT_DIR=clone.git &&
-		export GIT_DIR &&
-		git rev-list --objects $tag
-	) >list.actual &&
+	git -C clone.git rev-list --objects $tag >list.actual &&
 	test_cmp list.expect list.actual
 '
 
-- 
2.10.0.rc2.154.gb4a4b8b

[PATCH 4/5] t5305: simplify packname handling

[Jeff King]

We generate a series of packfiles test-1-$pack,
test-2-$pack, with different properties and then examine
them. However we always store the packname generated by
pack-objects in the variable packname_1. This probably was
meant to be packname_2 in the second test, but it turns out
that it doesn't matter: once we are done with the first
pack, we can just keep using the same $packname variable.

So let's drop the confusing "_1" parameter. At the same
time, let's give test-1 and test-2 more descriptive names,
which can help keep them straight (note that we _could_
likewise overwrite the packfiles in each test, but by using
separate filenames, we are sure that test 2 does not
accidentally use the packfile from test 1).

Signed-off-by: Jeff King <peff@peff.net>
---
 t/t5305-include-tag.sh | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/t/t5305-include-tag.sh b/t/t5305-include-tag.sh
index 089a3e9..e3c6c62 100755
--- a/t/t5305-include-tag.sh
+++ b/t/t5305-include-tag.sh
@@ -26,15 +26,15 @@ test_expect_success setup '
 '
 
 test_expect_success 'pack without --include-tag' '
-	packname_1=$(git pack-objects \
+	packname=$(git pack-objects \
 		--window=0 \
-		test-1 <obj-list)
+		test-no-include <obj-list)
 '
 
 test_expect_success 'unpack objects' '
 	rm -rf clone.git &&
 	git init clone.git &&
-	git -C clone.git unpack-objects <test-1-${packname_1}.pack
+	git -C clone.git unpack-objects <test-no-include-${packname}.pack
 '
 
 test_expect_success 'check unpacked result (have commit, no tag)' '
@@ -45,16 +45,16 @@ test_expect_success 'check unpacked result (have commit, no tag)' '
 '
 
 test_expect_success 'pack with --include-tag' '
-	packname_1=$(git pack-objects \
+	packname=$(git pack-objects \
 		--window=0 \
 		--include-tag \
-		test-2 <obj-list)
+		test-include <obj-list)
 '
 
 test_expect_success 'unpack objects' '
 	rm -rf clone.git &&
 	git init clone.git &&
-	git -C clone.git unpack-objects <test-2-${packname_1}.pack
+	git -C clone.git unpack-objects <test-include-${packname}.pack
 '
 
 test_expect_success 'check unpacked result (have commit, have tag)' '
-- 
2.10.0.rc2.154.gb4a4b8b

[PATCH 5/5] pack-objects: walk tag chains for --include-tag

[Jeff King]

When pack-objects is given --include-tag, it peels each tag
ref down to a non-tag object, and if that non-tag object is
going to be packed, we include the tag, too. But what
happens if we have a chain of tags (e.g., tag "A" points to
tag "B", which points to commit "C")?

We'll peel down to "C" and realize that we want to include
tag "A", but we do not ever consider tag "B", leading to a
broken pack (assuming "B" was not otherwise selected).
Instead, we have to walk the whole chain, adding any tags we
find to the pack.

Interestingly, it doesn't seem possible to trigger this
problem with "git fetch", but you can with "git clone
--single-branch". The reason is that we generate the correct
pack when the client explicitly asks for "A" (because we do
a real reachability analysis there), and "fetch" is more
willing to do so. There are basically two cases:

  1. If "C" is already a ref tip, then the client can deduce
     that it needs "A" itself (via find_non_local_tags), and
     will ask for it explicitly rather than relying on the
     include-tag capability. Everything works.

  2. If "C" is not already a ref tip, then we hope for
     include-tag to send us the correct tag. But it doesn't;
     it generates a broken pack. However, the next step is
     to do a follow-up run of find_non_local_tags(),
     followed by fetch_refs() to backfill any tags we
     learned about.

     In the normal case, fetch_refs() calls quickfetch(),
     which does a connectivity check and sees we have no
     new objects to fetch. We just write the refs.

     But for the broken-pack case, the connectivity check
     fails, and quickfetch will follow-up with the remote,
     asking explicitly for each of the ref tips. This picks
     up the missing object in a new pack.

For a regular "git clone", we are similarly OK, because we
explicitly request all of the tag refs, and get a correct
pack. But with "--single-branch", we kick in tag
auto-following via "include-tag", but do _not_ do a
follow-up backfill. We just take whatever the server sent us
via include-tag and write out tag refs for any tag objects
we were sent. So prior to c6807a4 (clone: open a shortcut
for connectivity check, 2013-05-26), we actually claimed the
clone was a success, but the result was silently
corrupted!  Since c6807a4, index-pack's connectivity
check catches this case, and we correctly complain.

The included test directly checks that pack-objects does not
generate a broken pack, but also confirms that "clone
--single-branch" does not hit the bug.

Note that tag chains introduce another interesting question:
if we are packing the tag "B" but not the commit "C", should
"A" be included?

Both before and after this patch, we do not include "A",
because the initial peel_ref() check only knows about the
bottom-most level, "C". To realize that "B" is involved at
all, we would have to switch to an incremental peel, in
which we examine each tagged object, asking if it is being
packed (and including the outer tag if so).

But that runs contrary to the optimizations in peel_ref(),
which avoid accessing the objects at all, in favor of using
the value we pull from packed-refs. It's OK to walk the
whole chain once we know we're going to include the tag (we
have to access it anyway, so the effort is proportional to
the pack we're generating). But for the initial selection,
we have to look at every ref. If we're only packing a few
objects, we'd still have to parse every single referenced
tag object just to confirm that it isn't part of a tag
chain.

This could be addressed if packed-refs stored the complete
tag chain for each peeled ref (in most cases, this would be
the same cost as now, as each "chain" is only a single
link). But given the size of that project, it's out of scope
for this fix (and probably nobody cares enough anyway, as
it's such an obscure situation). This commit limits itself
to just avoiding the creation of a broken pack.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c | 31 +++++++++++++++++++++++++++++-
 t/t5305-include-tag.sh | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 82 insertions(+), 1 deletion(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 4a63398..0954375 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2123,6 +2123,35 @@ static void ll_find_deltas(struct object_entry **list, unsigned list_size,
 #define ll_find_deltas(l, s, w, d, p)	find_deltas(l, &s, w, d, p)
 #endif
 
+static void add_tag_chain(const struct object_id *oid)
+{
+	struct tag *tag;
+
+	/*
+	 * We catch duplicates already in add_object_entry(), but we'd
+	 * prefer to do this extra check to avoid having to parse the
+	 * tag at all if we already know that it's being packed (e.g., if
+	 * it was included via bitmaps, we would not have parsed it
+	 * previously).
+	 */
+	if (packlist_find(&to_pack, oid->hash, NULL))
+		return;
+
+	tag = lookup_tag(oid->hash);
+	while (1) {
+		if (!tag || parse_tag(tag) || !tag->tagged)
+			die("unable to pack objects reachable from tag %s",
+			    oid_to_hex(oid));
+
+		add_object_entry(tag->object.oid.hash, OBJ_TAG, NULL, 0);
+
+		if (tag->tagged->type != OBJ_TAG)
+			return;
+
+		tag = (struct tag *)tag->tagged;
+	}
+}
+
 static int add_ref_tag(const char *path, const struct object_id *oid, int flag, void *cb_data)
 {
 	struct object_id peeled;
@@ -2130,7 +2159,7 @@ static int add_ref_tag(const char *path, const struct object_id *oid, int flag,
 	if (starts_with(path, "refs/tags/") && /* is a tag? */
 	    !peel_ref(path, peeled.hash)    && /* peelable? */
 	    packlist_find(&to_pack, peeled.hash, NULL))      /* object packed? */
-		add_object_entry(oid->hash, OBJ_TAG, NULL, 0);
+		add_tag_chain(oid);
 	return 0;
 }
 
diff --git a/t/t5305-include-tag.sh b/t/t5305-include-tag.sh
index e3c6c62..a5eca21 100755
--- a/t/t5305-include-tag.sh
+++ b/t/t5305-include-tag.sh
@@ -63,4 +63,56 @@ test_expect_success 'check unpacked result (have commit, have tag)' '
 	test_cmp list.expect list.actual
 '
 
+# A tag of a tag, where the "inner" tag is not otherwise
+# reachable, and a full peel points to a commit reachable from HEAD.
+test_expect_success 'create hidden inner tag' '
+	test_commit commit &&
+	git tag -m inner inner HEAD &&
+	git tag -m outer outer inner &&
+	git tag -d inner
+'
+
+test_expect_success 'pack explicit outer tag' '
+	packname=$(
+		{
+			echo HEAD &&
+			echo outer
+		} |
+		git pack-objects --revs test-hidden-explicit
+	)
+'
+
+test_expect_success 'unpack objects' '
+	rm -rf clone.git &&
+	git init clone.git &&
+	git -C clone.git unpack-objects <test-hidden-explicit-${packname}.pack
+'
+
+test_expect_success 'check unpacked result (have all objects)' '
+	git -C clone.git rev-list --objects $(git rev-parse outer HEAD)
+'
+
+test_expect_success 'pack implied outer tag' '
+	packname=$(
+		echo HEAD |
+		git pack-objects --revs --include-tag test-hidden-implied
+	)
+'
+
+test_expect_success 'unpack objects' '
+	rm -rf clone.git &&
+	git init clone.git &&
+	git -C clone.git unpack-objects <test-hidden-implied-${packname}.pack
+'
+
+test_expect_success 'check unpacked result (have all objects)' '
+	git -C clone.git rev-list --objects $(git rev-parse outer HEAD)
+'
+
+test_expect_success 'single-branch clone can transfer tag' '
+	rm -rf clone.git &&
+	git clone --no-local --single-branch -b master . clone.git &&
+	git -C clone.git fsck
+'
+
 test_done
-- 
2.10.0.rc2.154.gb4a4b8b

Re: [PATCH 5/5] pack-objects: walk tag chains for --include-tag

[Jeff King]

On Mon, Sep 05, 2016 at 05:52:26PM -0400, Jeff King wrote:

> When pack-objects is given --include-tag, it peels each tag
> ref down to a non-tag object, and if that non-tag object is
> going to be packed, we include the tag, too. But what
> happens if we have a chain of tags (e.g., tag "A" points to
> tag "B", which points to commit "C")?
> 
> We'll peel down to "C" and realize that we want to include
> tag "A", but we do not ever consider tag "B", leading to a
> broken pack (assuming "B" was not otherwise selected).
> Instead, we have to walk the whole chain, adding any tags we
> find to the pack.

So technically one might argue that this pack isn't "broken", in that it
_is_ a valid pack. It's just that it doesn't contain what the user was
asking for.

As explained further in the commit message, "fetch" is robust to this,
because it does a real connectivity check and follow-on fetch before
writing anything it thinks it got via include-tag. So perhaps one could
argue that pack-objects is correct; include-tag is best-effort, and it
is the client's job to make sure it has everything it needs. And that
would mean the bug is in git-clone, which should be doing the
connectivity check and follow-on fetch.

I dunno. This seems like the most elegant place to fix it, though it
does mean that pack-objects will go to some slight extra work when
auto-packing a tag (it has to parse the tag to find out whether it's a
chain). I'm doubt it matters much in practice.

-Peff

Re: [PATCH 5/5] pack-objects: walk tag chains for --include-tag

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> As explained further in the commit message, "fetch" is robust to this,
> because it does a real connectivity check and follow-on fetch before
> writing anything it thinks it got via include-tag. So perhaps one could
> argue that pack-objects is correct; include-tag is best-effort, and it
> is the client's job to make sure it has everything it needs. And that
> would mean the bug is in git-clone, which should be doing the
> connectivity check and follow-on fetch.

I think that is probably a more technically correct interpretation
of the history.

I think upgrading "best-effort" to "guarantee" like you did is a
right approach nevertheless.  I think the "best-effort" we initially
did was merely us being lazy.

Re: [PATCH 5/5] pack-objects: walk tag chains for --include-tag

[Jeff King]

On Wed, Sep 07, 2016 at 11:49:28AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > As explained further in the commit message, "fetch" is robust to this,
> > because it does a real connectivity check and follow-on fetch before
> > writing anything it thinks it got via include-tag. So perhaps one could
> > argue that pack-objects is correct; include-tag is best-effort, and it
> > is the client's job to make sure it has everything it needs. And that
> > would mean the bug is in git-clone, which should be doing the
> > connectivity check and follow-on fetch.
> 
> I think that is probably a more technically correct interpretation
> of the history.
> 
> I think upgrading "best-effort" to "guarantee" like you did is a
> right approach nevertheless.  I think the "best-effort" we initially
> did was merely us being lazy.

Yeah, after sleeping on it, the conclusion I came to was that it does
not _hurt_ to have include-tag be a bit more careful.

I also wondered about the corner case I noted in the commit message.  If
you have a tag chain of A->B->C, and you already have "C" (a commit),
but are fetching "B" (a tag), then include-tag does not notice "A".

That's OK for git-fetch. It will collect "A" during its backfill phase
(not because of "B" at all, but because it knows that "A" eventually
peels to "C", which it already has). "git-clone" does not have a
backfill, of course. But neither can it "already have" a commit. So
either we get "C" as part of the clone (in which case include-tag will
include "A"), or it does not (in which case we cannot be getting "B"
either, because "C" is reachable from it).

And of course that's only when single-branch is in use. Normally
git-clone just grabs all the tags blindly. :)

So I think everything Just Works after my patch, though we do still rely
on fetch backfill to pick up some obscure cases.

-Peff

Re: [PATCH 0/5] handle tag recursion in pack-objects --include-tag

[Jeff King]

On Mon, Sep 05, 2016 at 05:51:41PM -0400, Jeff King wrote:

> If you have a tag of a tag of a commit, and the middle tag isn't
> otherwise reachable, then "pack-objects --include-tag" will not include
> the middle tag, and certain invocations of "clone" will fail. See the
> final patch below for the gory details.
> 
> The first five patches are just test cleanup and modernization in
> preparation (though note that the 3rd one actually fixes a minor bug in
> the test script).
> 
>   [1/5]: t5305: move cleanup into test block
>   [2/5]: t5305: drop "dry-run" of unpack-objects
>   [3/5]: t5305: use "git -C"
>   [4/5]: t5305: simplify packname handling
>   [5/5]: pack-objects: walk tag chains for --include-tag

BTW, this is not a new regression; the problem dates back to the origin
of the "include-tag" feature. So there is no urgency to the fix, as it
has been with us for almost a decade. I built it on master, but it
should apply cleanly to maint.

-Peff