[PATCH 5/7] fetch-pack: support fetching from a shallow repository

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

upload-pack already advertises all shallow grafts if server repository
is shallow. This information can be used to add more grafts to the
client if the server sends commit chains down to its graft points.

If the server is shallow, before we receive the pack, we setup a
temporary shallow file that contains both local graft points and the
server's. This stops index-pack from going beyond server's graft
points.

Only server graft points that do not have corresponding SHA-1s in
local repo are added to the temp shallow file because we don't want to
accidentally cut the client history because the server's is
shorter. The client cutting can only happen when --depth is requested.

After index-pack finishes successfully, we write the temporary shallow
down with one exception: unused graft points provided by the server
are removed. We don't want those lying around and suddenly become
active.

Note that in the "shallow -> shallow" case, the server might not have
enough information to find common roots to create an optimum pack. It
might send complete commit chains down to the graft points as a
result. I don't think we can improve this, unless upload-pack somehow
has access to a full repository.

"shallow -> shallow" case only makes sense when the upstream provides
a stable shallow repo (e.g. make a cut every year or so and ask devs
to all move to the new base). If the cloned repos are all based on a
stable (shallow) upstream, the above problem is unlikely to happen.

A side effect of this change is we can now clone from a shallow
repository. And a full repository may automatically become shallow if
you fetch from a shallow repository.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/fetch-pack.c              |  6 ++--
 commit.h                          |  8 +++--
 fetch-pack.c                      | 27 +++++++++++---
 fetch-pack.h                      |  1 +
 shallow.c                         | 46 ++++++++++++++++++++----
 t/t5536-fetch-shallow.sh (new +x) | 75 +++++++++++++++++++++++++++++++++++++++
 transport.c                       |  8 +++--
 7 files changed, 153 insertions(+), 18 deletions(-)
 create mode 100755 t/t5536-fetch-shallow.sh

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 080e599..b89d753 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -37,6 +37,7 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 	char **pack_lockfile_ptr = NULL;
 	struct child_process *conn;
 	struct fetch_pack_args args;
+	struct extra_have_objects shallow;
 
 	packet_trace_identity("fetch-pack");
 
@@ -144,10 +145,11 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 				   args.verbose ? CONNECT_VERBOSE : 0);
 	}
 
-	get_remote_heads(fd[0], NULL, 0, &ref, 0, NULL, NULL);
+	memset(&shallow, 0, sizeof(shallow));
+	get_remote_heads(fd[0], NULL, 0, &ref, 0, NULL, &shallow);
 
 	ref = fetch_pack(&args, fd, conn, ref, dest,
-			 sought, nr_sought, pack_lockfile_ptr);
+			 sought, nr_sought, &shallow, pack_lockfile_ptr);
 	if (pack_lockfile) {
 		printf("lock %s\n", pack_lockfile);
 		fflush(stdout);
diff --git a/commit.h b/commit.h
index 678fa20..7faf0e4 100644
--- a/commit.h
+++ b/commit.h
@@ -188,9 +188,13 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,
 extern void check_shallow_file_for_update(void);
 extern void set_alternate_shallow_file(const char *path);
 extern void advertise_shallow_grafts(int);
-extern int write_shallow_commits(struct strbuf *out, int use_pack_protocol);
+extern int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
+				 struct extra_have_objects *extra,
+				 int remove_unused_grafts);
 extern void setup_alternate_shallow(struct lock_file *shallow_lock,
-				    const char **alternate_shallow_file);
+				    const char **alternate_shallow_file,
+				    struct extra_have_objects *extra,
+				    int rewrite);
 
 int is_descendant_of(struct commit *, struct commit_list *);
 int in_merge_bases(struct commit *, struct commit *);
diff --git a/fetch-pack.c b/fetch-pack.c
index dc71a2b..68b95a5 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -311,7 +311,7 @@ static int find_common(struct fetch_pack_args *args,
 	}
 
 	if (is_repository_shallow())
-		write_shallow_commits(&req_buf, 1);
+		write_shallow_commits(&req_buf, 1, NULL, 0);
 	if (args->depth > 0)
 		packet_buf_write(&req_buf, "deepen %d", args->depth);
 	packet_buf_flush(&req_buf);
@@ -769,6 +769,7 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 				 int fd[2],
 				 const struct ref *orig_ref,
 				 struct ref **sought, int nr_sought,
+				 struct extra_have_objects *shallow,
 				 char **pack_lockfile)
 {
 	struct ref *ref = copy_ref_list(orig_ref);
@@ -844,8 +845,9 @@ static struct ref *do_fetch_pack(struct fetch_pack_args *args,
 
 	if (args->stateless_rpc)
 		packet_flush(fd[1]);
-	if (args->depth > 0)
-		setup_alternate_shallow(&shallow_lock, &alternate_shallow_file);
+	if (args->depth > 0 || shallow->nr)
+		setup_alternate_shallow(&shallow_lock, &alternate_shallow_file,
+					shallow, 0);
 	if (get_pack(args, fd, pack_lockfile))
 		die("git fetch-pack: fetch failed.");
 
@@ -922,6 +924,7 @@ struct ref *fetch_pack(struct fetch_pack_args *args,
 		       const struct ref *ref,
 		       const char *dest,
 		       struct ref **sought, int nr_sought,
+		       struct extra_have_objects *shallow,
 		       char **pack_lockfile)
 {
 	struct ref *ref_cpy;
@@ -934,14 +937,28 @@ struct ref *fetch_pack(struct fetch_pack_args *args,
 		packet_flush(fd[1]);
 		die("no matching remote head");
 	}
-	ref_cpy = do_fetch_pack(args, fd, ref, sought, nr_sought, pack_lockfile);
+	ref_cpy = do_fetch_pack(args, fd, ref, sought, nr_sought,
+				shallow, pack_lockfile);
 
 	if (alternate_shallow_file) {
 		if (*alternate_shallow_file == '\0') { /* --unshallow */
 			unlink_or_warn(git_path("shallow"));
 			rollback_lock_file(&shallow_lock);
-		} else
+		} else {
+			/*
+			 *  The server is a shallow clone and it sends
+			 *  us all of its shallow grafts. Some may be
+			 *  needed if the server sends objects down to
+			 *  the bottom. Remove all unused grafts.
+			 */
+			if (shallow->nr) {
+				reprepare_packed_git();
+				setup_alternate_shallow(&shallow_lock,
+							&alternate_shallow_file,
+							shallow, 1);
+			}
 			commit_lock_file(&shallow_lock);
+		}
 	}
 
 	reprepare_packed_git();
diff --git a/fetch-pack.h b/fetch-pack.h
index 40f08ba..c55bf1c 100644
--- a/fetch-pack.h
+++ b/fetch-pack.h
@@ -32,6 +32,7 @@ struct ref *fetch_pack(struct fetch_pack_args *args,
 		       const char *dest,
 		       struct ref **sought,
 		       int nr_sought,
+		       struct extra_have_objects *shallow,
 		       char **pack_lockfile);
 
 #endif
diff --git a/shallow.c b/shallow.c
index ee9edd4..d909d95 100644
--- a/shallow.c
+++ b/shallow.c
@@ -183,26 +183,60 @@ static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
 	return 0;
 }
 
-int write_shallow_commits(struct strbuf *out, int use_pack_protocol)
+int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
+			  struct extra_have_objects *extra,
+			  int remove_unused_grafts)
 {
 	struct write_shallow_data data;
+	int i;
 	data.out = out;
 	data.use_pack_protocol = use_pack_protocol;
 	data.count = 0;
 	for_each_commit_graft(write_one_shallow, &data);
+	if (!extra)
+		return data.count;
+
+	for (i = 0; i < extra->nr; i++) {
+		if (!remove_unused_grafts && has_sha1_file(extra->array[i]))
+			/*
+			 * The server may have even shorter history
+			 * than the client (e.g. the client has
+			 * A-B-C-D but the server only has C-D). We do
+			 * NOT want to cut client's history down to
+			 * C-D simply because the server is set up
+			 * so. If we don't have "C" and the server
+			 * sends C-D to us, then we set up a graft at
+			 * "C".
+			 */
+			continue;
+		if (remove_unused_grafts && !has_sha1_file(extra->array[i]))
+			continue;
+		strbuf_addstr(out, sha1_to_hex(extra->array[i]));
+		strbuf_addch(out, '\n');
+		data.count++;
+	}
 	return data.count;
 }
 
 void setup_alternate_shallow(struct lock_file *shallow_lock,
-			     const char **alternate_shallow_file)
+			     const char **alternate_shallow_file,
+			     struct extra_have_objects *extra,
+			     int rewrite)
 {
 	struct strbuf sb = STRBUF_INIT;
 	int fd;
 
-	check_shallow_file_for_update();
-	fd = hold_lock_file_for_update(shallow_lock, git_path("shallow"),
-				       LOCK_DIE_ON_ERROR);
-	if (write_shallow_commits(&sb, 0)) {
+	if (!rewrite)
+		fd = hold_lock_file_for_update(shallow_lock,
+					       git_path("shallow"),
+					       LOCK_DIE_ON_ERROR);
+	else
+		fd = shallow_lock->fd;
+	if (write_shallow_commits(&sb, 0, extra, rewrite)) {
+		if (rewrite && (lseek(fd, 0, SEEK_SET) == -1 ||
+				ftruncate(fd, 0) == -1))
+			die_errno("unable to truncate the new shallow file %s",
+				  shallow_lock->filename);
 		if (write_in_full(fd, sb.buf, sb.len) != sb.len)
 			die_errno("failed to write to %s",
 				  shallow_lock->filename);
diff --git a/t/t5536-fetch-shallow.sh b/t/t5536-fetch-shallow.sh
new file mode 100755
index 0000000..599928f
--- /dev/null
+++ b/t/t5536-fetch-shallow.sh
@@ -0,0 +1,75 @@
+#!/bin/sh
+
+test_description='fetch/clone from a shallow clone'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	test_commit 1 &&
+	test_commit 2 &&
+	test_commit 3 &&
+	test_commit 4
+'
+
+test_expect_success 'setup shallow clone' '
+	git clone --no-local --depth=2 .git shallow &&
+	git --git-dir=shallow/.git log --format=%s >actual &&
+	cat <<EOF >expect &&
+4
+3
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'clone from shallow clone' '
+	git clone --no-local shallow shallow2 &&
+	(
+	cd shallow2 &&
+	git fsck &&
+	git log --format=%s >actual &&
+	cat <<EOF >expect &&
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'fetch from shallow clone' '
+	(
+	cd shallow &&
+	test_commit 5
+	) &&
+	(
+	cd shallow2 &&
+	git fetch &&
+	git fsck &&
+	git log --format=%s origin/master >actual &&
+	cat <<EOF >expect &&
+5
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'fetch --depth from shallow clone' '
+	(
+	cd shallow &&
+	test_commit 6
+	) &&
+	(
+	cd shallow2 &&
+	git fetch --depth=2 &&
+	git fsck &&
+	git log --format=%s origin/master >actual &&
+	cat <<EOF >expect &&
+6
+5
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_done
diff --git a/transport.c b/transport.c
index 10a8cb8..17fef16 100644
--- a/transport.c
+++ b/transport.c
@@ -453,6 +453,7 @@ struct git_transport_data {
 	int fd[2];
 	unsigned got_remote_heads : 1;
 	struct extra_have_objects extra_have;
+	struct extra_have_objects shallow;
 };
 
 static int set_git_option(struct git_transport_options *opts,
@@ -509,7 +510,8 @@ static struct ref *get_refs_via_connect(struct transport *transport, int for_pus
 
 	connect_setup(transport, for_push, 0);
 	get_remote_heads(data->fd[0], NULL, 0, &refs,
-			 for_push ? REF_NORMAL : 0, &data->extra_have, NULL);
+			 for_push ? REF_NORMAL : 0,
+			 &data->extra_have, &data->shallow);
 	data->got_remote_heads = 1;
 
 	return refs;
@@ -540,13 +542,13 @@ static int fetch_refs_via_pack(struct transport *transport,
 	if (!data->got_remote_heads) {
 		connect_setup(transport, 0, 0);
 		get_remote_heads(data->fd[0], NULL, 0, &refs_tmp, 0,
-				 NULL, NULL);
+				 NULL, &data->shallow);
 		data->got_remote_heads = 1;
 	}
 
 	refs = fetch_pack(&args, data->fd, data->conn,
 			  refs_tmp ? refs_tmp : transport->remote_refs,
-			  dest, to_fetch, nr_heads,
+			  dest, to_fetch, nr_heads, &data->shallow,
 			  &transport->pack_lockfile);
 	close(data->fd[0]);
 	close(data->fd[1]);
-- 
1.8.2.83.gc99314b