Merge branch 'nd/shallow-clone'

Fetching from a shallow-cloned repository used to be forbidden,
primarily because the codepaths involved were not carefully vetted
and we did not bother supporting such usage. This attempts to allow
object transfer out of a shallow-cloned repository in a controlled
way (i.e. the receiver become a shallow repository with truncated
history).

* nd/shallow-clone: (31 commits)
  t5537: fix incorrect expectation in test case 10
  shallow: remove unused code
  send-pack.c: mark a file-local function static
  git-clone.txt: remove shallow clone limitations
  prune: clean .git/shallow after pruning objects
  clone: use git protocol for cloning shallow repo locally
  send-pack: support pushing from a shallow clone via http
  receive-pack: support pushing to a shallow clone via http
  smart-http: support shallow fetch/clone
  remote-curl: pass ref SHA-1 to fetch-pack as well
  send-pack: support pushing to a shallow clone
  receive-pack: allow pushes that update .git/shallow
  connected.c: add new variant that runs with --shallow-file
  add GIT_SHALLOW_FILE to propagate --shallow-file to subprocesses
  receive/send-pack: support pushing from a shallow clone
  receive-pack: reorder some code in unpack()
  fetch: add --update-shallow to accept refs that update .git/shallow
  upload-pack: make sure deepening preserves shallow roots
  fetch: support fetching from a shallow repository
  clone: support remote shallow repository
  ...

36 files changed, 1535 insertions, 168 deletions

diff --git a/Documentation/config.txt b/Documentation/config.txt
index ed59853190..5f4d7939ed 100644
--- a/Documentation/config.txt
+++ b/Documentation/config.txt
@@ -2030,6 +2030,10 @@ receive.updateserverinfo::
 	If set to true, git-receive-pack will run git-update-server-info
 	after receiving data from git-push and updating refs.
 
+receive.shallowupdate::
+	If set to true, .git/shallow can be updated when new refs
+	require new shallow roots. Otherwise those refs are rejected.
+
 remote.pushdefault::
 	The remote to push to by default.  Overrides
 	`branch.<name>.remote` for all branches, and is overridden by
diff --git a/Documentation/fetch-options.txt b/Documentation/fetch-options.txt
index f0ef7d02a5..92c68c3fda 100644
--- a/Documentation/fetch-options.txt
+++ b/Documentation/fetch-options.txt
@@ -14,8 +14,18 @@
 	branch history. Tags for the deepened commits are not fetched.
 
 --unshallow::
-	Convert a shallow repository to a complete one, removing all
-	the limitations imposed by shallow repositories.
+	If the source repository is complete, convert a shallow
+	repository to a complete one, removing all the limitations
+	imposed by shallow repositories.
++
+If the source repository is shallow, fetch as much as possible so that
+the current repository has the same history as the source repository.
+
+--update-shallow::
+	By default when fetching from a shallow repository,
+	`git fetch` refuses refs that require updating
+	.git/shallow. This option updates .git/shallow and accept such
+	refs.
 
 ifndef::git-pull[]
 --dry-run::
diff --git a/Documentation/git-clone.txt b/Documentation/git-clone.txt
index 450f158779..49878570bf 100644
--- a/Documentation/git-clone.txt
+++ b/Documentation/git-clone.txt
@@ -181,12 +181,7 @@ objects from the source repository into a pack in the cloned repository.
 
 --depth <depth>::
 	Create a 'shallow' clone with a history truncated to the
-	specified number of revisions.  A shallow repository has a
-	number of limitations (you cannot clone or fetch from
-	it, nor push from nor into it), but is adequate if you
-	are only interested in the recent history of a large project
-	with a long history, and would want to send in fixes
-	as patches.
+	specified number of revisions.
 
 --[no-]single-branch::
 	Clone only the history leading to the tip of a single branch,
diff --git a/Documentation/git-prune.txt b/Documentation/git-prune.txt
index bf824108c1..058ac0dc85 100644
--- a/Documentation/git-prune.txt
+++ b/Documentation/git-prune.txt
@@ -24,6 +24,8 @@ objects unreachable from any of these head objects from the object database.
 In addition, it
 prunes the unpacked objects that are also found in packs by
 running 'git prune-packed'.
+It also removes entries from .git/shallow that are not reachable by
+any ref.
 
 Note that unreachable, packed objects will remain.  If this is
 not desired, see linkgit:git-repack[1].
diff --git a/Documentation/gitremote-helpers.txt b/Documentation/gitremote-helpers.txt
index f1f4ca9727..c2908db763 100644
--- a/Documentation/gitremote-helpers.txt
+++ b/Documentation/gitremote-helpers.txt
@@ -437,6 +437,13 @@ set by Git if the remote helper has the 'option' capability.
 'option check-connectivity' \{'true'|'false'\}::
 	Request the helper to check connectivity of a clone.
 
+'option cloning \{'true'|'false'\}::
+	Notify the helper this is a clone request (i.e. the current
+	repository is guaranteed empty).
+
+'option update-shallow \{'true'|'false'\}::
+	Allow to extend .git/shallow if the new refs require it.
+
 SEE ALSO
 --------
 linkgit:git-remote[1]
diff --git a/Documentation/technical/pack-protocol.txt b/Documentation/technical/pack-protocol.txt
index b898e97988..c73b62f5e1 100644
--- a/Documentation/technical/pack-protocol.txt
+++ b/Documentation/technical/pack-protocol.txt
@@ -161,6 +161,7 @@ MUST peel the ref if it's an annotated tag.
 
 ----
   advertised-refs  =  (no-refs / list-of-refs)
+		      *shallow
 		      flush-pkt
 
   no-refs          =  PKT-LINE(zero-id SP "capabilities^{}"
@@ -174,6 +175,8 @@ MUST peel the ref if it's an annotated tag.
   other-tip        =  obj-id SP refname LF
   other-peeled     =  obj-id SP refname "^{}" LF
 
+  shallow          =  PKT-LINE("shallow" SP obj-id)
+
   capability-list  =  capability *(SP capability)
   capability       =  1*(LC_ALPHA / DIGIT / "-" / "_")
   LC_ALPHA         =  %x61-7A
@@ -461,7 +464,9 @@ contain all the objects that the server will need to complete the new
 references.
 
 ----
-  update-request    =  command-list [pack-file]
+  update-request    =  *shallow command-list [pack-file]
+
+  shallow           =  PKT-LINE("shallow" SP obj-id)
 
   command-list      =  PKT-LINE(command NUL capability-list LF)
 		       *PKT-LINE(command LF)
diff --git a/builtin/clone.c b/builtin/clone.c
index f98f52980d..43e772ccdb 100644
--- a/builtin/clone.c
+++ b/builtin/clone.c
@@ -252,6 +252,12 @@ static int add_one_reference(struct string_list_item *item, void *cb_data)
 		die(_("reference repository '%s' is not a local repository."),
 		    item->string);
 
+	if (!access(mkpath("%s/shallow", ref_git), F_OK))
+		die(_("reference repository '%s' is shallow"), item->string);
+
+	if (!access(mkpath("%s/info/grafts", ref_git), F_OK))
+		die(_("reference repository '%s' is grafted"), item->string);
+
 	strbuf_addf(&alternate, "%s/objects", ref_git);
 	add_to_alternates_file(alternate.buf);
 	strbuf_release(&alternate);
@@ -791,8 +797,15 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	else
 		repo = repo_name;
 	is_local = option_local != 0 && path && !is_bundle;
-	if (is_local && option_depth)
-		warning(_("--depth is ignored in local clones; use file:// instead."));
+	if (is_local) {
+		if (option_depth)
+			warning(_("--depth is ignored in local clones; use file:// instead."));
+		if (!access(mkpath("%s/shallow", path), F_OK)) {
+			if (option_local > 0)
+				warning(_("source repository is shallow, ignoring --local"));
+			is_local = 0;
+		}
+	}
 	if (option_local > 0 && !is_local)
 		warning(_("--local is ignored"));
 
@@ -887,6 +900,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 
 	remote = remote_get(option_origin);
 	transport = transport_get(remote, remote->url[0]);
+	transport->cloning = 1;
 
 	if (!transport->get_refs_list || (!is_local && !transport->fetch))
 		die(_("Don't know how to clone %s"), transport->url);
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index 8b8978a252..1262b405f8 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -3,6 +3,7 @@
 #include "fetch-pack.h"
 #include "remote.h"
 #include "connect.h"
+#include "sha1-array.h"
 
 static const char fetch_pack_usage[] =
 "git fetch-pack [--all] [--stdin] [--quiet|-q] [--keep|-k] [--thin] "
@@ -13,6 +14,13 @@ static void add_sought_entry_mem(struct ref ***sought, int *nr, int *alloc,
 				 const char *name, int namelen)
 {
 	struct ref *ref = xcalloc(1, sizeof(*ref) + namelen + 1);
+	unsigned char sha1[20];
+
+	if (namelen > 41 && name[40] == ' ' && !get_sha1_hex(name, sha1)) {
+		hashcpy(ref->old_sha1, sha1);
+		name += 41;
+		namelen -= 41;
+	}
 
 	memcpy(ref->name, name, namelen);
 	ref->name[namelen] = '\0';
@@ -39,6 +47,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 sha1_array shallow = SHA1_ARRAY_INIT;
 
 	packet_trace_identity("fetch-pack");
 
@@ -110,6 +119,14 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 			args.check_self_contained_and_connected = 1;
 			continue;
 		}
+		if (!strcmp("--cloning", arg)) {
+			args.cloning = 1;
+			continue;
+		}
+		if (!strcmp("--update-shallow", arg)) {
+			args.update_shallow = 1;
+			continue;
+		}
 		usage(fetch_pack_usage);
 	}
 
@@ -158,10 +175,10 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 		if (!conn)
 			return args.diag_url ? 0 : 1;
 	}
-	get_remote_heads(fd[0], NULL, 0, &ref, 0, NULL);
+	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);
+	ref = fetch_pack(&args, fd, conn, ref, dest, sought, nr_sought,
+			 &shallow, pack_lockfile_ptr);
 	if (pack_lockfile) {
 		printf("lock %s\n", pack_lockfile);
 		fflush(stdout);
diff --git a/builtin/fetch.c b/builtin/fetch.c
index 09825c84d7..025bc3e38d 100644
--- a/builtin/fetch.c
+++ b/builtin/fetch.c
@@ -36,7 +36,7 @@ static int prune = -1; /* unspecified */
 
 static int all, append, dry_run, force, keep, multiple, update_head_ok, verbosity;
 static int progress = -1, recurse_submodules = RECURSE_SUBMODULES_DEFAULT;
-static int tags = TAGS_DEFAULT, unshallow;
+static int tags = TAGS_DEFAULT, unshallow, update_shallow;
 static const char *depth;
 static const char *upload_pack;
 static struct strbuf default_rla = STRBUF_INIT;
@@ -105,6 +105,8 @@ static struct option builtin_fetch_options[] = {
 	{ OPTION_STRING, 0, "recurse-submodules-default",
 		   &recurse_submodules_default, NULL,
 		   N_("default mode for recursion"), PARSE_OPT_HIDDEN },
+	OPT_BOOL(0, "update-shallow", &update_shallow,
+		 N_("accept refs that update .git/shallow")),
 	OPT_END()
 };
 
@@ -524,6 +526,8 @@ static int iterate_ref_map(void *cb_data, unsigned char sha1[20])
 	struct ref **rm = cb_data;
 	struct ref *ref = *rm;
 
+	while (ref && ref->status == REF_STATUS_REJECT_SHALLOW)
+		ref = ref->next;
 	if (!ref)
 		return -1; /* end of the list */
 	*rm = ref->next;
@@ -570,6 +574,13 @@ static int store_updated_refs(const char *raw_url, const char *remote_name,
 			struct ref *ref = NULL;
 			const char *merge_status_marker = "";
 
+			if (rm->status == REF_STATUS_REJECT_SHALLOW) {
+				if (want_status == FETCH_HEAD_MERGE)
+					warning(_("reject %s because shallow roots are not allowed to be updated"),
+						rm->peer_ref ? rm->peer_ref->name : rm->name);
+				continue;
+			}
+
 			commit = lookup_commit_reference_gently(rm->old_sha1, 1);
 			if (!commit)
 				rm->fetch_head_status = FETCH_HEAD_NOT_FOR_MERGE;
@@ -798,6 +809,8 @@ static struct transport *prepare_transport(struct remote *remote)
 		set_option(transport, TRANS_OPT_KEEP, "yes");
 	if (depth)
 		set_option(transport, TRANS_OPT_DEPTH, depth);
+	if (update_shallow)
+		set_option(transport, TRANS_OPT_UPDATE_SHALLOW, "yes");
 	return transport;
 }
 
diff --git a/builtin/gc.c b/builtin/gc.c
index 25f2237c08..c19545d49e 100644
--- a/builtin/gc.c
+++ b/builtin/gc.c
@@ -16,6 +16,7 @@
 #include "run-command.h"
 #include "sigchain.h"
 #include "argv-array.h"
+#include "commit.h"
 
 #define FAILED_RUN "failed to run %s"
 
diff --git a/builtin/prune.c b/builtin/prune.c
index beb0dc942c..de43b26cfe 100644
--- a/builtin/prune.c
+++ b/builtin/prune.c
@@ -180,5 +180,9 @@ int cmd_prune(int argc, const char **argv, const char *prefix)
 	s = mkpathdup("%s/pack", get_object_directory());
 	remove_temporary_files(s);
 	free(s);
+
+	if (is_repository_shallow())
+		prune_shallow(show_only);
+
 	return 0;
 }
diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index e09994f4df..85bba356fa 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -13,6 +13,7 @@
 #include "string-list.h"
 #include "sha1-array.h"
 #include "connected.h"
+#include "argv-array.h"
 #include "version.h"
 
 static const char receive_pack_usage[] = "git receive-pack <git-dir>";
@@ -43,6 +44,8 @@ static int fix_thin = 1;
 static const char *head_name;
 static void *head_name_to_free;
 static int sent_capabilities;
+static int shallow_update;
+static const char *alt_shallow_file;
 
 static enum deny_action parse_deny_action(const char *var, const char *value)
 {
@@ -121,6 +124,11 @@ static int receive_pack_config(const char *var, const char *value, void *cb)
 		return 0;
 	}
 
+	if (strcmp(var, "receive.shallowupdate") == 0) {
+		shallow_update = git_config_bool(var, value);
+		return 0;
+	}
+
 	return git_default_config(var, value, cb);
 }
 
@@ -178,6 +186,8 @@ static void write_head_info(void)
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
 
+	advertise_shallow_grafts(1);
+
 	/* EOF */
 	packet_flush(1);
 }
@@ -187,6 +197,7 @@ struct command {
 	const char *error_string;
 	unsigned int skip_update:1,
 		     did_not_exist:1;
+	int index;
 	unsigned char old_sha1[20];
 	unsigned char new_sha1[20];
 	char ref_name[FLEX_ARRAY]; /* more */
@@ -418,7 +429,46 @@ static void refuse_unconfigured_deny_delete_current(void)
 		rp_error("%s", refuse_unconfigured_deny_delete_current_msg[i]);
 }
 
-static const char *update(struct command *cmd)
+static int command_singleton_iterator(void *cb_data, unsigned char sha1[20]);
+static int update_shallow_ref(struct command *cmd, struct shallow_info *si)
+{
+	static struct lock_file shallow_lock;
+	struct sha1_array extra = SHA1_ARRAY_INIT;
+	const char *alt_file;
+	uint32_t mask = 1 << (cmd->index % 32);
+	int i;
+
+	trace_printf_key("GIT_TRACE_SHALLOW",
+			 "shallow: update_shallow_ref %s\n", cmd->ref_name);
+	for (i = 0; i < si->shallow->nr; i++)
+		if (si->used_shallow[i] &&
+		    (si->used_shallow[i][cmd->index / 32] & mask) &&
+		    !delayed_reachability_test(si, i))
+			sha1_array_append(&extra, si->shallow->sha1[i]);
+
+	setup_alternate_shallow(&shallow_lock, &alt_file, &extra);
+	if (check_shallow_connected(command_singleton_iterator,
+				    0, cmd, alt_file)) {
+		rollback_lock_file(&shallow_lock);
+		sha1_array_clear(&extra);
+		return -1;
+	}
+
+	commit_lock_file(&shallow_lock);
+
+	/*
+	 * Make sure setup_alternate_shallow() for the next ref does
+	 * not lose these new roots..
+	 */
+	for (i = 0; i < extra.nr; i++)
+		register_shallow(extra.sha1[i]);
+
+	si->shallow_ref[cmd->index] = 0;
+	sha1_array_clear(&extra);
+	return 0;
+}
+
+static const char *update(struct command *cmd, struct shallow_info *si)
 {
 	const char *name = cmd->ref_name;
 	struct strbuf namespaced_name_buf = STRBUF_INIT;
@@ -526,6 +576,10 @@ static const char *update(struct command *cmd)
 		return NULL; /* good */
 	}
 	else {
+		if (shallow_update && si->shallow_ref[cmd->index] &&
+		    update_shallow_ref(cmd, si))
+			return "shallow error";
+
 		lock = lock_any_ref_for_update(namespaced_name, old_sha1,
 					       0, NULL);
 		if (!lock) {
@@ -666,12 +720,16 @@ static int command_singleton_iterator(void *cb_data, unsigned char sha1[20])
 	return 0;
 }
 
-static void set_connectivity_errors(struct command *commands)
+static void set_connectivity_errors(struct command *commands,
+				    struct shallow_info *si)
 {
 	struct command *cmd;
 
 	for (cmd = commands; cmd; cmd = cmd->next) {
 		struct command *singleton = cmd;
+		if (shallow_update && si->shallow_ref[cmd->index])
+			/* to be checked in update_shallow_ref() */
+			continue;
 		if (!check_everything_connected(command_singleton_iterator,
 						0, &singleton))
 			continue;
@@ -679,18 +737,26 @@ static void set_connectivity_errors(struct command *commands)
 	}
 }
 
+struct iterate_data {
+	struct command *cmds;
+	struct shallow_info *si;
+};
+
 static int iterate_receive_command_list(void *cb_data, unsigned char sha1[20])
 {
-	struct command **cmd_list = cb_data;
+	struct iterate_data *data = cb_data;
+	struct command **cmd_list = &data->cmds;
 	struct command *cmd = *cmd_list;
 
-	while (cmd) {
-		if (!is_null_sha1(cmd->new_sha1)) {
+	for (; cmd; cmd = cmd->next) {
+		if (shallow_update && data->si->shallow_ref[cmd->index])
+			/* to be checked in update_shallow_ref() */
+			continue;
+		if (!is_null_sha1(cmd->new_sha1) && !cmd->skip_update) {
 			hashcpy(sha1, cmd->new_sha1);
 			*cmd_list = cmd->next;
 			return 0;
 		}
-		cmd = cmd->next;
 	}
 	*cmd_list = NULL;
 	return -1; /* end of list */
@@ -710,10 +776,14 @@ static void reject_updates_to_hidden(struct command *commands)
 	}
 }
 
-static void execute_commands(struct command *commands, const char *unpacker_error)
+static void execute_commands(struct command *commands,
+			     const char *unpacker_error,
+			     struct shallow_info *si)
 {
+	int checked_connectivity;
 	struct command *cmd;
 	unsigned char sha1[20];
+	struct iterate_data data;
 
 	if (unpacker_error) {
 		for (cmd = commands; cmd; cmd = cmd->next)
@@ -721,10 +791,10 @@ static void execute_commands(struct command *commands, const char *unpacker_erro
 		return;
 	}
 
-	cmd = commands;
-	if (check_everything_connected(iterate_receive_command_list,
-				       0, &cmd))
-		set_connectivity_errors(commands);
+	data.cmds = commands;
+	data.si = si;
+	if (check_everything_connected(iterate_receive_command_list, 0, &data))
+		set_connectivity_errors(commands, si);
 
 	reject_updates_to_hidden(commands);
 
@@ -741,6 +811,7 @@ static void execute_commands(struct command *commands, const char *unpacker_erro
 	free(head_name_to_free);
 	head_name = head_name_to_free = resolve_refdup("HEAD", sha1, 0, NULL);
 
+	checked_connectivity = 1;
 	for (cmd = commands; cmd; cmd = cmd->next) {
 		if (cmd->error_string)
 			continue;
@@ -748,11 +819,26 @@ static void execute_commands(struct command *commands, const char *unpacker_erro
 		if (cmd->skip_update)
 			continue;
 
-		cmd->error_string = update(cmd);
+		cmd->error_string = update(cmd, si);
+		if (shallow_update && !cmd->error_string &&
+		    si->shallow_ref[cmd->index]) {
+			error("BUG: connectivity check has not been run on ref %s",
+			      cmd->ref_name);
+			checked_connectivity = 0;
+		}
+	}
+
+	if (shallow_update) {
+		if (!checked_connectivity)
+			error("BUG: run 'git fsck' for safety.\n"
+			      "If there are errors, try to remove "
+			      "the reported refs above");
+		if (alt_shallow_file && *alt_shallow_file)
+			unlink(alt_shallow_file);
 	}
 }
 
-static struct command *read_head_info(void)
+static struct command *read_head_info(struct sha1_array *shallow)
 {
 	struct command *commands = NULL;
 	struct command **p = &commands;
@@ -766,6 +852,14 @@ static struct command *read_head_info(void)
 		line = packet_read_line(0, &len);
 		if (!line)
 			break;
+
+		if (len == 48 && starts_with(line, "shallow ")) {
+			if (get_sha1_hex(line + 8, old_sha1))
+				die("protocol error: expected shallow sha, got '%s'", line + 8);
+			sha1_array_append(shallow, old_sha1);
+			continue;
+		}
+
 		if (len < 83 ||
 		    line[40] != ' ' ||
 		    line[81] != ' ' ||
@@ -817,11 +911,14 @@ static const char *parse_pack_header(struct pack_header *hdr)
 
 static const char *pack_lockfile;
 
-static const char *unpack(int err_fd)
+static const char *unpack(int err_fd, struct shallow_info *si)
 {
 	struct pack_header hdr;
+	struct argv_array av = ARGV_ARRAY_INIT;
 	const char *hdr_err;
+	int status;
 	char hdr_arg[38];
+	struct child_process child;
 	int fsck_objects = (receive_fsck_objects >= 0
 			    ? receive_fsck_objects
 			    : transfer_fsck_objects >= 0
@@ -838,72 +935,63 @@ static const char *unpack(int err_fd)
 			"--pack_header=%"PRIu32",%"PRIu32,
 			ntohl(hdr.hdr_version), ntohl(hdr.hdr_entries));
 
+	if (si->nr_ours || si->nr_theirs) {
+		alt_shallow_file = setup_temporary_shallow(si->shallow);
+		argv_array_pushl(&av, "--shallow-file", alt_shallow_file, NULL);
+	}
+
+	memset(&child, 0, sizeof(child));
 	if (ntohl(hdr.hdr_entries) < unpack_limit) {
-		int code, i = 0;
-		struct child_process child;
-		const char *unpacker[5];
-		unpacker[i++] = "unpack-objects";
+		argv_array_pushl(&av, "unpack-objects", hdr_arg, NULL);
 		if (quiet)
-			unpacker[i++] = "-q";
+			argv_array_push(&av, "-q");
 		if (fsck_objects)
-			unpacker[i++] = "--strict";
-		unpacker[i++] = hdr_arg;
-		unpacker[i++] = NULL;
-		memset(&child, 0, sizeof(child));
-		child.argv = unpacker;
+			argv_array_push(&av, "--strict");
+		child.argv = av.argv;
 		child.no_stdout = 1;
 		child.err = err_fd;
 		child.git_cmd = 1;
-		code = run_command(&child);
-		if (!code)
-			return NULL;
-		return "unpack-objects abnormal exit";
+		status = run_command(&child);
+		if (status)
+			return "unpack-objects abnormal exit";
 	} else {
-		const char *keeper[7];
-		int s, status, i = 0;
+		int s;
 		char keep_arg[256];
-		struct child_process ip;
 
 		s = sprintf(keep_arg, "--keep=receive-pack %"PRIuMAX" on ", (uintmax_t) getpid());
 		if (gethostname(keep_arg + s, sizeof(keep_arg) - s))
 			strcpy(keep_arg + s, "localhost");
 
-		keeper[i++] = "index-pack";
-		keeper[i++] = "--stdin";
+		argv_array_pushl(&av, "index-pack",
+				 "--stdin", hdr_arg, keep_arg, NULL);
 		if (fsck_objects)
-			keeper[i++] = "--strict";
+			argv_array_push(&av, "--strict");
 		if (fix_thin)
-			keeper[i++] = "--fix-thin";
-		keeper[i++] = hdr_arg;
-		keeper[i++] = keep_arg;
-		keeper[i++] = NULL;
-		memset(&ip, 0, sizeof(ip));
-		ip.argv = keeper;
-		ip.out = -1;
-		ip.err = err_fd;
-		ip.git_cmd = 1;
-		status = start_command(&ip);
-		if (status) {
+			argv_array_push(&av, "--fix-thin");
+		child.argv = av.argv;
+		child.out = -1;
+		child.err = err_fd;
+		child.git_cmd = 1;
+		status = start_command(&child);
+		if (status)
 			return "index-pack fork failed";
-		}
-		pack_lockfile = index_pack_lockfile(ip.out);
-		close(ip.out);
-		status = finish_command(&ip);
-		if (!status) {
-			reprepare_packed_git();
-			return NULL;
-		}
-		return "index-pack abnormal exit";
+		pack_lockfile = index_pack_lockfile(child.out);
+		close(child.out);
+		status = finish_command(&child);
+		if (status)
+			return "index-pack abnormal exit";
+		reprepare_packed_git();
 	}
+	return NULL;
 }
 
-static const char *unpack_with_sideband(void)
+static const char *unpack_with_sideband(struct shallow_info *si)
 {
 	struct async muxer;
 	const char *ret;
 
 	if (!use_sideband)
-		return unpack(0);
+		return unpack(0, si);
 
 	memset(&muxer, 0, sizeof(muxer));
 	muxer.proc = copy_to_sideband;
@@ -911,12 +999,101 @@ static const char *unpack_with_sideband(void)
 	if (start_async(&muxer))
 		return NULL;
 
-	ret = unpack(muxer.in);
+	ret = unpack(muxer.in, si);
 
 	finish_async(&muxer);
 	return ret;
 }
 
+static void prepare_shallow_update(struct command *commands,
+				   struct shallow_info *si)
+{
+	int i, j, k, bitmap_size = (si->ref->nr + 31) / 32;
+
+	si->used_shallow = xmalloc(sizeof(*si->used_shallow) *
+				   si->shallow->nr);
+	assign_shallow_commits_to_refs(si, si->used_shallow, NULL);
+
+	si->need_reachability_test =
+		xcalloc(si->shallow->nr, sizeof(*si->need_reachability_test));
+	si->reachable =
+		xcalloc(si->shallow->nr, sizeof(*si->reachable));
+	si->shallow_ref = xcalloc(si->ref->nr, sizeof(*si->shallow_ref));
+
+	for (i = 0; i < si->nr_ours; i++)
+		si->need_reachability_test[si->ours[i]] = 1;
+
+	for (i = 0; i < si->shallow->nr; i++) {
+		if (!si->used_shallow[i])
+			continue;
+		for (j = 0; j < bitmap_size; j++) {
+			if (!si->used_shallow[i][j])
+				continue;
+			si->need_reachability_test[i]++;
+			for (k = 0; k < 32; k++)
+				if (si->used_shallow[i][j] & (1 << k))
+					si->shallow_ref[j * 32 + k]++;
+		}
+
+		/*
+		 * true for those associated with some refs and belong
+		 * in "ours" list aka "step 7 not done yet"
+		 */
+		si->need_reachability_test[i] =
+			si->need_reachability_test[i] > 1;
+	}
+
+	/*
+	 * keep hooks happy by forcing a temporary shallow file via
+	 * env variable because we can't add --shallow-file to every
+	 * command. check_everything_connected() will be done with
+	 * true .git/shallow though.
+	 */
+	setenv(GIT_SHALLOW_FILE_ENVIRONMENT, alt_shallow_file, 1);
+}
+
+static void update_shallow_info(struct command *commands,
+				struct shallow_info *si,
+				struct sha1_array *ref)
+{
+	struct command *cmd;
+	int *ref_status;
+	remove_nonexistent_theirs_shallow(si);
+	if (!si->nr_ours && !si->nr_theirs) {
+		shallow_update = 0;
+		return;
+	}
+
+	for (cmd = commands; cmd; cmd = cmd->next) {
+		if (is_null_sha1(cmd->new_sha1))
+			continue;
+		sha1_array_append(ref, cmd->new_sha1);
+		cmd->index = ref->nr - 1;
+	}
+	si->ref = ref;
+
+	if (shallow_update) {
+		prepare_shallow_update(commands, si);
+		return;
+	}
+
+	ref_status = xmalloc(sizeof(*ref_status) * ref->nr);
+	assign_shallow_commits_to_refs(si, NULL, ref_status);
+	for (cmd = commands; cmd; cmd = cmd->next) {
+		if (is_null_sha1(cmd->new_sha1))
+			continue;
+		if (ref_status[cmd->index]) {
+			cmd->error_string = "shallow update not allowed";
+			cmd->skip_update = 1;
+		}
+	}
+	if (alt_shallow_file && *alt_shallow_file) {
+		unlink(alt_shallow_file);
+		alt_shallow_file = NULL;
+	}
+	free(ref_status);
+}
+
 static void report(struct command *commands, const char *unpack_status)
 {
 	struct command *cmd;
@@ -958,6 +1135,9 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
 	int i;
 	char *dir = NULL;
 	struct command *commands;
+	struct sha1_array shallow = SHA1_ARRAY_INIT;
+	struct sha1_array ref = SHA1_ARRAY_INIT;
+	struct shallow_info si;
 
 	packet_trace_identity("receive-pack");
 
@@ -998,9 +1178,6 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
 	if (!enter_repo(dir, 0))
 		die("'%s' does not appear to be a git repository", dir);
 
-	if (is_repository_shallow())
-		die("attempt to push into a shallow repository");
-
 	git_config(receive_pack_config, NULL);
 
 	if (0 <= transfer_unpack_limit)
@@ -1014,12 +1191,17 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
 	if (advertise_refs)
 		return 0;
 
-	if ((commands = read_head_info()) != NULL) {
+	if ((commands = read_head_info(&shallow)) != NULL) {
 		const char *unpack_status = NULL;
 
-		if (!delete_only(commands))
-			unpack_status = unpack_with_sideband();
-		execute_commands(commands, unpack_status);
+		prepare_shallow_info(&si, &shallow);
+		if (!si.nr_ours && !si.nr_theirs)
+			shallow_update = 0;
+		if (!delete_only(commands)) {
+			unpack_status = unpack_with_sideband(&si);
+			update_shallow_info(commands, &si, &ref);
+		}
+		execute_commands(commands, unpack_status, &si);
 		if (pack_lockfile)
 			unlink_or_warn(pack_lockfile);
 		if (report_status)
@@ -1035,8 +1217,11 @@ int cmd_receive_pack(int argc, const char **argv, const char *prefix)
 		}
 		if (auto_update_server_info)
 			update_server_info(0);
+		clear_shallow_info(&si);
 	}
 	if (use_sideband)
 		packet_flush(1);
+	sha1_array_clear(&shallow);
+	sha1_array_clear(&ref);
 	return 0;
 }
diff --git a/builtin/send-pack.c b/builtin/send-pack.c
index e7f0b97d31..f420b74665 100644
--- a/builtin/send-pack.c
+++ b/builtin/send-pack.c
@@ -10,6 +10,7 @@
 #include "quote.h"
 #include "transport.h"
 #include "version.h"
+#include "sha1-array.h"
 
 static const char send_pack_usage[] =
 "git send-pack [--all | --mirror] [--dry-run] [--force] [--receive-pack=<git-receive-pack>] [--verbose] [--thin] [<host>:]<directory> [<ref>...]\n"
@@ -99,7 +100,8 @@ int cmd_send_pack(int argc, const char **argv, const char *prefix)
 	const char *dest = NULL;
 	int fd[2];
 	struct child_process *conn;
-	struct extra_have_objects extra_have;
+	struct sha1_array extra_have = SHA1_ARRAY_INIT;
+	struct sha1_array shallow = SHA1_ARRAY_INIT;
 	struct ref *remote_refs, *local_refs;
 	int ret;
 	int helper_status = 0;
@@ -228,9 +230,8 @@ int cmd_send_pack(int argc, const char **argv, const char *prefix)
 			args.verbose ? CONNECT_VERBOSE : 0);
 	}
 
-	memset(&extra_have, 0, sizeof(extra_have));
-
-	get_remote_heads(fd[0], NULL, 0, &remote_refs, REF_NORMAL, &extra_have);
+	get_remote_heads(fd[0], NULL, 0, &remote_refs, REF_NORMAL,
+			 &extra_have, &shallow);
 
 	transport_verify_remote_names(nr_refspecs, refspecs);
 
diff --git a/cache.h b/cache.h
index 83a27269b8..c9efe88e9e 100644
--- a/cache.h
+++ b/cache.h
@@ -354,6 +354,7 @@ static inline enum object_type object_type(unsigned int mode)
 #define DB_ENVIRONMENT "GIT_OBJECT_DIRECTORY"
 #define INDEX_ENVIRONMENT "GIT_INDEX_FILE"
 #define GRAFT_ENVIRONMENT "GIT_GRAFT_FILE"
+#define GIT_SHALLOW_FILE_ENVIRONMENT "GIT_SHALLOW_FILE"
 #define TEMPLATE_DIR_ENVIRONMENT "GIT_TEMPLATE_DIR"
 #define CONFIG_ENVIRONMENT "GIT_CONFIG"
 #define CONFIG_DATA_ENVIRONMENT "GIT_CONFIG_PARAMETERS"
@@ -1243,6 +1244,8 @@ __attribute__((format (printf, 2, 3)))
 extern void trace_argv_printf(const char **argv, const char *format, ...);
 extern void trace_repo_setup(const char *prefix);
 extern int trace_want(const char *key);
+__attribute__((format (printf, 2, 3)))
+extern void trace_printf_key(const char *key, const char *fmt, ...);
 extern void trace_strbuf(const char *key, const struct strbuf *buf);
 
 void packet_trace_identity(const char *prog);
diff --git a/commit.h b/commit.h
index f8a451d864..16d9c43513 100644
--- a/commit.h
+++ b/commit.h
@@ -194,6 +194,8 @@ extern struct commit_list *get_octopus_merge_bases(struct commit_list *in);
 /* largest positive number a signed 32-bit integer can contain */
 #define INFINITE_DEPTH 0x7fffffff
 
+struct sha1_array;
+struct ref;
 extern int register_shallow(const unsigned char *sha1);
 extern int unregister_shallow(const unsigned char *sha1);
 extern int for_each_commit_graft(each_commit_graft_fn, void *);
@@ -201,11 +203,38 @@ extern int is_repository_shallow(void);
 extern struct commit_list *get_shallow_commits(struct object_array *heads,
 		int depth, int shallow_flag, int not_shallow_flag);
 extern void check_shallow_file_for_update(void);
-extern void set_alternate_shallow_file(const char *path);
-extern int write_shallow_commits(struct strbuf *out, int use_pack_protocol);
+extern void set_alternate_shallow_file(const char *path, int override);
+extern int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
+				 const struct sha1_array *extra);
 extern void setup_alternate_shallow(struct lock_file *shallow_lock,
-				    const char **alternate_shallow_file);
-extern char *setup_temporary_shallow(void);
+				    const char **alternate_shallow_file,
+				    const struct sha1_array *extra);
+extern char *setup_temporary_shallow(const struct sha1_array *extra);
+extern void advertise_shallow_grafts(int);
+
+struct shallow_info {
+	struct sha1_array *shallow;
+	int *ours, nr_ours;
+	int *theirs, nr_theirs;
+	struct sha1_array *ref;
+
+	/* for receive-pack */
+	uint32_t **used_shallow;
+	int *need_reachability_test;
+	int *reachable;
+	int *shallow_ref;
+	struct commit **commits;
+	int nr_commits;
+};
+
+extern void prepare_shallow_info(struct shallow_info *, struct sha1_array *);
+extern void clear_shallow_info(struct shallow_info *);
+extern void remove_nonexistent_theirs_shallow(struct shallow_info *);
+extern void assign_shallow_commits_to_refs(struct shallow_info *info,
+					   uint32_t **used,
+					   int *ref_status);
+extern int delayed_reachability_test(struct shallow_info *si, int c);
+extern void prune_shallow(int show_only);
 
 int is_descendant_of(struct commit *, struct commit_list *);
 int in_merge_bases(struct commit *, struct commit *);
diff --git a/connect.c b/connect.c
index c763eeda86..4150412e2c 100644
--- a/connect.c
+++ b/connect.c
@@ -8,6 +8,7 @@
 #include "connect.h"
 #include "url.h"
 #include "string-list.h"
+#include "sha1-array.h"
 
 static char *server_capabilities;
 static const char *parse_feature_value(const char *, const char *, int *);
@@ -45,13 +46,6 @@ int check_ref_type(const struct ref *ref, int flags)
 	return check_ref(ref->name, strlen(ref->name), flags);
 }
 
-static void add_extra_have(struct extra_have_objects *extra, unsigned char *sha1)
-{
-	ALLOC_GROW(extra->array, extra->nr + 1, extra->alloc);
-	hashcpy(&(extra->array[extra->nr][0]), sha1);
-	extra->nr++;
-}
-
 static void die_initial_contact(int got_at_least_one_head)
 {
 	if (got_at_least_one_head)
@@ -122,7 +116,8 @@ static void annotate_refs_with_symref_info(struct ref *ref)
  */
 struct ref **get_remote_heads(int in, char *src_buf, size_t src_len,
 			      struct ref **list, unsigned int flags,
-			      struct extra_have_objects *extra_have)
+			      struct sha1_array *extra_have,
+			      struct sha1_array *shallow_points)
 {
 	struct ref **orig_list = list;
 	int got_at_least_one_head = 0;
@@ -148,6 +143,15 @@ struct ref **get_remote_heads(int in, char *src_buf, size_t src_len,
 		if (len > 4 && starts_with(buffer, "ERR "))
 			die("remote error: %s", buffer + 4);
 
+		if (len == 48 && starts_with(buffer, "shallow ")) {
+			if (get_sha1_hex(buffer + 8, old_sha1))
+				die("protocol error: expected shallow sha-1, got '%s'", buffer + 8);
+			if (!shallow_points)
+				die("repository on the other end cannot be shallow");
+			sha1_array_append(shallow_points, old_sha1);
+			continue;
+		}
+
 		if (len < 42 || get_sha1_hex(buffer, old_sha1) || buffer[40] != ' ')
 			die("protocol error: expected sha/ref, got '%s'", buffer);
 		name = buffer + 41;
@@ -160,7 +164,7 @@ struct ref **get_remote_heads(int in, char *src_buf, size_t src_len,
 
 		if (extra_have &&
 		    name_len == 5 && !memcmp(".have", name, 5)) {
-			add_extra_have(extra_have, old_sha1);
+			sha1_array_append(extra_have, old_sha1);
 			continue;
 		}
 
diff --git a/connected.c b/connected.c
index 51d8ba4bb7..be0253e21b 100644
--- a/connected.c
+++ b/connected.c
@@ -19,17 +19,17 @@ int check_everything_connected(sha1_iterate_fn fn, int quiet, void *cb_data)
  *
  * Returns 0 if everything is connected, non-zero otherwise.
  */
-int check_everything_connected_with_transport(sha1_iterate_fn fn,
-					      int quiet,
-					      void *cb_data,
-					      struct transport *transport)
+static int check_everything_connected_real(sha1_iterate_fn fn,
+					   int quiet,
+					   void *cb_data,
+					   struct transport *transport,
+					   const char *shallow_file)
 {
 	struct child_process rev_list;
-	const char *argv[] = {"rev-list", "--objects",
-			      "--stdin", "--not", "--all", NULL, NULL};
+	const char *argv[9];
 	char commit[41];
 	unsigned char sha1[20];
-	int err = 0;
+	int err = 0, ac = 0;
 	struct packed_git *new_pack = NULL;
 
 	if (fn(cb_data, sha1))
@@ -47,8 +47,18 @@ int check_everything_connected_with_transport(sha1_iterate_fn fn,
 		strbuf_release(&idx_file);
 	}
 
+	if (shallow_file) {
+		argv[ac++] = "--shallow-file";
+		argv[ac++] = shallow_file;
+	}
+	argv[ac++] = "rev-list";
+	argv[ac++] = "--objects";
+	argv[ac++] = "--stdin";
+	argv[ac++] = "--not";
+	argv[ac++] = "--all";
 	if (quiet)
-		argv[5] = "--quiet";
+		argv[ac++] = "--quiet";
+	argv[ac] = NULL;
 
 	memset(&rev_list, 0, sizeof(rev_list));
 	rev_list.argv = argv;
@@ -92,3 +102,19 @@ int check_everything_connected_with_transport(sha1_iterate_fn fn,
 	sigchain_pop(SIGPIPE);
 	return finish_command(&rev_list) || err;
 }
+
+int check_everything_connected_with_transport(sha1_iterate_fn fn,
+					      int quiet,
+					      void *cb_data,
+					      struct transport *transport)
+{
+	return check_everything_connected_real(fn, quiet, cb_data,
+					       transport, NULL);
+}
+
+int check_shallow_connected(sha1_iterate_fn fn, int quiet, void *cb_data,
+			    const char *shallow_file)
+{
+	return check_everything_connected_real(fn, quiet, cb_data,
+					       NULL, shallow_file);
+}
diff --git a/connected.h b/connected.h
index 0b060b7429..071d408f38 100644
--- a/connected.h
+++ b/connected.h
@@ -18,6 +18,8 @@ typedef int (*sha1_iterate_fn)(void *, unsigned char [20]);
  * Return 0 if Ok, non zero otherwise (i.e. some missing objects)
  */
 extern int check_everything_connected(sha1_iterate_fn, int quiet, void *cb_data);
+extern int check_shallow_connected(sha1_iterate_fn, int quiet, void *cb_data,
+				   const char *shallow_file);
 extern int check_everything_connected_with_transport(sha1_iterate_fn, int quiet,
 						     void *cb_data,
 						     struct transport *transport);
diff --git a/environment.c b/environment.c
index 3c76905b9f..4a3437d8a6 100644
--- a/environment.c
+++ b/environment.c
@@ -10,6 +10,7 @@
 #include "cache.h"
 #include "refs.h"
 #include "fmt-merge-msg.h"
+#include "commit.h"
 
 int trust_executable_bit = 1;
 int trust_ctime = 1;
@@ -97,6 +98,7 @@ const char * const local_repo_env[] = {
 	INDEX_ENVIRONMENT,
 	NO_REPLACE_OBJECTS_ENVIRONMENT,
 	GIT_PREFIX_ENVIRONMENT,
+	GIT_SHALLOW_FILE_ENVIRONMENT,
 	NULL
 };
 
@@ -124,6 +126,7 @@ static char *expand_namespace(const char *raw_namespace)
 static void setup_git_env(void)
 {
 	const char *gitfile;
+	const char *shallow_file;
 
 	git_dir = getenv(GIT_DIR_ENVIRONMENT);
 	if (!git_dir)
@@ -147,6 +150,9 @@ static void setup_git_env(void)
 		read_replace_refs = 0;
 	namespace = expand_namespace(getenv(GIT_NAMESPACE_ENVIRONMENT));
 	namespace_len = strlen(namespace);
+	shallow_file = getenv(GIT_SHALLOW_FILE_ENVIRONMENT);
+	if (shallow_file)
+		set_alternate_shallow_file(shallow_file, 0);
 }
 
 int is_bare_repository(void)
diff --git a/fetch-pack.c b/fetch-pack.c
index 760ed16e79..d52de74c4b 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -13,6 +13,7 @@
 #include "transport.h"
 #include "version.h"
 #include "prio-queue.h"
+#include "sha1-array.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
@@ -309,7 +310,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);
 	if (args->depth > 0)
 		packet_buf_write(&req_buf, "deepen %d", args->depth);
 	packet_buf_flush(&req_buf);
@@ -772,6 +773,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 shallow_info *si,
 				 char **pack_lockfile)
 {
 	struct ref *ref = copy_ref_list(orig_ref);
@@ -848,7 +850,10 @@ 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);
+		setup_alternate_shallow(&shallow_lock, &alternate_shallow_file,
+					NULL);
+	else if (si->nr_ours || si->nr_theirs)
+		alternate_shallow_file = setup_temporary_shallow(si->shallow);
 	else
 		alternate_shallow_file = NULL;
 	if (get_pack(args, fd, pack_lockfile))
@@ -922,14 +927,121 @@ static int remove_duplicates_in_refs(struct ref **ref, int nr)
 	return dst;
 }
 
+static void update_shallow(struct fetch_pack_args *args,
+			   struct ref **sought, int nr_sought,
+			   struct shallow_info *si)
+{
+	struct sha1_array ref = SHA1_ARRAY_INIT;
+	int *status;
+	int i;
+
+	if (args->depth > 0 && alternate_shallow_file) {
+		if (*alternate_shallow_file == '\0') { /* --unshallow */
+			unlink_or_warn(git_path("shallow"));
+			rollback_lock_file(&shallow_lock);
+		} else
+			commit_lock_file(&shallow_lock);
+		return;
+	}
+
+	if (!si->shallow || !si->shallow->nr)
+		return;
+
+	if (alternate_shallow_file) {
+		/*
+		 * The temporary shallow file is only useful for
+		 * index-pack and unpack-objects because it may
+		 * contain more roots than we want. Delete it.
+		 */
+		if (*alternate_shallow_file)
+			unlink(alternate_shallow_file);
+		free((char *)alternate_shallow_file);
+	}
+
+	if (args->cloning) {
+		/*
+		 * remote is shallow, but this is a clone, there are
+		 * no objects in repo to worry about. Accept any
+		 * shallow points that exist in the pack (iow in repo
+		 * after get_pack() and reprepare_packed_git())
+		 */
+		struct sha1_array extra = SHA1_ARRAY_INIT;
+		unsigned char (*sha1)[20] = si->shallow->sha1;
+		for (i = 0; i < si->shallow->nr; i++)
+			if (has_sha1_file(sha1[i]))
+				sha1_array_append(&extra, sha1[i]);
+		if (extra.nr) {
+			setup_alternate_shallow(&shallow_lock,
+						&alternate_shallow_file,
+						&extra);
+			commit_lock_file(&shallow_lock);
+		}
+		sha1_array_clear(&extra);
+		return;
+	}
+
+	if (!si->nr_ours && !si->nr_theirs)
+		return;
+
+	remove_nonexistent_theirs_shallow(si);
+	if (!si->nr_ours && !si->nr_theirs)
+		return;
+	for (i = 0; i < nr_sought; i++)
+		sha1_array_append(&ref, sought[i]->old_sha1);
+	si->ref = &ref;
+
+	if (args->update_shallow) {
+		/*
+		 * remote is also shallow, .git/shallow may be updated
+		 * so all refs can be accepted. Make sure we only add
+		 * shallow roots that are actually reachable from new
+		 * refs.
+		 */
+		struct sha1_array extra = SHA1_ARRAY_INIT;
+		unsigned char (*sha1)[20] = si->shallow->sha1;
+		assign_shallow_commits_to_refs(si, NULL, NULL);
+		if (!si->nr_ours && !si->nr_theirs) {
+			sha1_array_clear(&ref);
+			return;
+		}
+		for (i = 0; i < si->nr_ours; i++)
+			sha1_array_append(&extra, sha1[si->ours[i]]);
+		for (i = 0; i < si->nr_theirs; i++)
+			sha1_array_append(&extra, sha1[si->theirs[i]]);
+		setup_alternate_shallow(&shallow_lock,
+					&alternate_shallow_file,
+					&extra);
+		commit_lock_file(&shallow_lock);
+		sha1_array_clear(&extra);
+		sha1_array_clear(&ref);
+		return;
+	}
+
+	/*
+	 * remote is also shallow, check what ref is safe to update
+	 * without updating .git/shallow
+	 */
+	status = xcalloc(nr_sought, sizeof(*status));
+	assign_shallow_commits_to_refs(si, NULL, status);
+	if (si->nr_ours || si->nr_theirs) {
+		for (i = 0; i < nr_sought; i++)
+			if (status[i])
+				sought[i]->status = REF_STATUS_REJECT_SHALLOW;
+	}
+	free(status);
+	sha1_array_clear(&ref);
+}
+
 struct ref *fetch_pack(struct fetch_pack_args *args,
 		       int fd[], struct child_process *conn,
 		       const struct ref *ref,
 		       const char *dest,
 		       struct ref **sought, int nr_sought,
+		       struct sha1_array *shallow,
 		       char **pack_lockfile)
 {
 	struct ref *ref_cpy;
+	struct shallow_info si;
 
 	fetch_pack_setup();
 	if (nr_sought)
@@ -939,16 +1051,11 @@ 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);
-
-	if (args->depth > 0 && alternate_shallow_file) {
-		if (*alternate_shallow_file == '\0') { /* --unshallow */
-			unlink_or_warn(git_path("shallow"));
-			rollback_lock_file(&shallow_lock);
-		} else
-			commit_lock_file(&shallow_lock);
-	}
-
+	prepare_shallow_info(&si, shallow);
+	ref_cpy = do_fetch_pack(args, fd, ref, sought, nr_sought,
+				&si, pack_lockfile);
 	reprepare_packed_git();
+	update_shallow(args, sought, nr_sought, &si);
+	clear_shallow_info(&si);
 	return ref_cpy;
 }
diff --git a/fetch-pack.h b/fetch-pack.h
index 20ccc12e57..bb7fd76e59 100644
--- a/fetch-pack.h
+++ b/fetch-pack.h
@@ -4,23 +4,27 @@
 #include "string-list.h"
 #include "run-command.h"
 
+struct sha1_array;
+
 struct fetch_pack_args {
 	const char *uploadpack;
 	int unpacklimit;
 	int depth;
-	unsigned quiet:1,
-		keep_pack:1,
-		lock_pack:1,
-		use_thin_pack:1,
-		fetch_all:1,
-		stdin_refs:1,
-		diag_url:1,
-		verbose:1,
-		no_progress:1,
-		include_tag:1,
-		stateless_rpc:1,
-		check_self_contained_and_connected:1,
-		self_contained_and_connected:1;
+	unsigned quiet:1;
+	unsigned keep_pack:1;
+	unsigned lock_pack:1;
+	unsigned use_thin_pack:1;
+	unsigned fetch_all:1;
+	unsigned stdin_refs:1;
+	unsigned diag_url:1;
+	unsigned verbose:1;
+	unsigned no_progress:1;
+	unsigned include_tag:1;
+	unsigned stateless_rpc:1;
+	unsigned check_self_contained_and_connected:1;
+	unsigned self_contained_and_connected:1;
+	unsigned cloning:1;
+	unsigned update_shallow:1;
 };
 
 /*
@@ -34,6 +38,7 @@ struct ref *fetch_pack(struct fetch_pack_args *args,
 		       const char *dest,
 		       struct ref **sought,
 		       int nr_sought,
+		       struct sha1_array *shallow,
 		       char **pack_lockfile);
 
 #endif
diff --git a/git.c b/git.c
index bba4378458..7cf2953eff 100644
--- a/git.c
+++ b/git.c
@@ -162,7 +162,7 @@ static int handle_options(const char ***argv, int *argc, int *envchanged)
 		} else if (!strcmp(cmd, "--shallow-file")) {
 			(*argv)++;
 			(*argc)--;
-			set_alternate_shallow_file((*argv)[0]);
+			set_alternate_shallow_file((*argv)[0], 1);
 			if (envchanged)
 				*envchanged = 1;
 		} else if (!strcmp(cmd, "-C")) {
diff --git a/remote-curl.c b/remote-curl.c
index e38c4b026f..10cb0114ea 100644
--- a/remote-curl.c
+++ b/remote-curl.c
@@ -10,6 +10,7 @@
 #include "sideband.h"
 #include "argv-array.h"
 #include "credential.h"
+#include "sha1-array.h"
 
 static struct remote *remote;
 /* always ends with a trailing slash */
@@ -20,6 +21,8 @@ struct options {
 	unsigned long depth;
 	unsigned progress : 1,
 		check_self_contained_and_connected : 1,
+		cloning : 1,
+		update_shallow : 1,
 		followtags : 1,
 		dry_run : 1,
 		thin : 1;
@@ -87,8 +90,23 @@ static int set_option(const char *name, const char *value)
 		string_list_append(&cas_options, val.buf);
 		strbuf_release(&val);
 		return 0;
-	}
-	else {
+	} else if (!strcmp(name, "cloning")) {
+		if (!strcmp(value, "true"))
+			options.cloning = 1;
+		else if (!strcmp(value, "false"))
+			options.cloning = 0;
+		else
+			return -1;
+		return 0;
+	} else if (!strcmp(name, "update-shallow")) {
+		if (!strcmp(value, "true"))
+			options.update_shallow = 1;
+		else if (!strcmp(value, "false"))
+			options.update_shallow = 0;
+		else
+			return -1;
+		return 0;
+	} else {
 		return 1 /* unsupported */;
 	}
 }
@@ -99,6 +117,7 @@ struct discovery {
 	char *buf;
 	size_t len;
 	struct ref *refs;
+	struct sha1_array shallow;
 	unsigned proto_git : 1;
 };
 static struct discovery *last_discovery;
@@ -107,7 +126,7 @@ static struct ref *parse_git_refs(struct discovery *heads, int for_push)
 {
 	struct ref *list = NULL;
 	get_remote_heads(-1, heads->buf, heads->len, &list,
-			 for_push ? REF_NORMAL : 0, NULL);
+			 for_push ? REF_NORMAL : 0, NULL, &heads->shallow);
 	return list;
 }
 
@@ -168,6 +187,7 @@ static void free_discovery(struct discovery *d)
 	if (d) {
 		if (d == last_discovery)
 			last_discovery = NULL;
+		free(d->shallow.sha1);
 		free(d->buf_alloc);
 		free_refs(d->refs);
 		free(d);
@@ -699,7 +719,7 @@ static int fetch_git(struct discovery *heads,
 	struct strbuf preamble = STRBUF_INIT;
 	char *depth_arg = NULL;
 	int argc = 0, i, err;
-	const char *argv[16];
+	const char *argv[17];
 
 	argv[argc++] = "fetch-pack";
 	argv[argc++] = "--stateless-rpc";
@@ -715,6 +735,10 @@ static int fetch_git(struct discovery *heads,
 	}
 	if (options.check_self_contained_and_connected)
 		argv[argc++] = "--check-self-contained-and-connected";
+	if (options.cloning)
+		argv[argc++] = "--cloning";
+	if (options.update_shallow)
+		argv[argc++] = "--update-shallow";
 	if (!options.progress)
 		argv[argc++] = "--no-progress";
 	if (options.depth) {
@@ -730,7 +754,8 @@ static int fetch_git(struct discovery *heads,
 		struct ref *ref = to_fetch[i];
 		if (!ref->name || !*ref->name)
 			die("cannot fetch by sha1 over smart http");
-		packet_buf_write(&preamble, "%s\n", ref->name);
+		packet_buf_write(&preamble, "%s %s\n",
+				 sha1_to_hex(ref->old_sha1), ref->name);
 	}
 	packet_buf_flush(&preamble);
 
diff --git a/remote.h b/remote.h
index 00c6a76ef8..fb7647fab9 100644
--- a/remote.h
+++ b/remote.h
@@ -109,6 +109,7 @@ struct ref {
 		REF_STATUS_REJECT_FETCH_FIRST,
 		REF_STATUS_REJECT_NEEDS_FORCE,
 		REF_STATUS_REJECT_STALE,
+		REF_STATUS_REJECT_SHALLOW,
 		REF_STATUS_UPTODATE,
 		REF_STATUS_REMOTE_REJECT,
 		REF_STATUS_EXPECTING_REPORT
@@ -138,13 +139,11 @@ int check_ref_type(const struct ref *ref, int flags);
  */
 void free_refs(struct ref *ref);
 
-struct extra_have_objects {
-	int nr, alloc;
-	unsigned char (*array)[20];
-};
+struct sha1_array;
 extern struct ref **get_remote_heads(int in, char *src_buf, size_t src_len,
 				     struct ref **list, unsigned int flags,
-				     struct extra_have_objects *);
+				     struct sha1_array *extra_have,
+				     struct sha1_array *shallow);
 
 int resolve_remote_symref(struct ref *ref, struct ref *list);
 int ref_newer(const unsigned char *new_sha1, const unsigned char *old_sha1);
diff --git a/send-pack.c b/send-pack.c
index ac14a4d090..6129b0fd8e 100644
--- a/send-pack.c
+++ b/send-pack.c
@@ -10,6 +10,7 @@
 #include "quote.h"
 #include "transport.h"
 #include "version.h"
+#include "sha1-array.h"
 
 static int feed_object(const unsigned char *sha1, int fd, int negative)
 {
@@ -28,7 +29,7 @@ static int feed_object(const unsigned char *sha1, int fd, int negative)
 /*
  * Make a pack stream and spit it out into file descriptor fd
  */
-static int pack_objects(int fd, struct ref *refs, struct extra_have_objects *extra, struct send_pack_args *args)
+static int pack_objects(int fd, struct ref *refs, struct sha1_array *extra, struct send_pack_args *args)
 {
 	/*
 	 * The child becomes pack-objects --revs; we feed
@@ -71,7 +72,7 @@ static int pack_objects(int fd, struct ref *refs, struct extra_have_objects *ext
 	 * parameters by writing to the pipe.
 	 */
 	for (i = 0; i < extra->nr; i++)
-		if (!feed_object(extra->array[i], po.in, 1))
+		if (!feed_object(extra->sha1[i], po.in, 1))
 			break;
 
 	while (refs) {
@@ -174,10 +175,25 @@ static int sideband_demux(int in, int out, void *data)
 	return ret;
 }
 
+static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
+{
+	struct strbuf *sb = cb;
+	if (graft->nr_parent == -1)
+		packet_buf_write(sb, "shallow %s\n", sha1_to_hex(graft->sha1));
+	return 0;
+}
+
+static void advertise_shallow_grafts_buf(struct strbuf *sb)
+{
+	if (!is_repository_shallow())
+		return;
+	for_each_commit_graft(advertise_shallow_grafts_cb, sb);
+}
+
 int send_pack(struct send_pack_args *args,
 	      int fd[], struct child_process *conn,
 	      struct ref *remote_refs,
-	      struct extra_have_objects *extra_have)
+	      struct sha1_array *extra_have)
 {
 	int in = fd[0];
 	int out = fd[1];
@@ -215,6 +231,9 @@ int send_pack(struct send_pack_args *args,
 		return 0;
 	}
 
+	if (!args->dry_run)
+		advertise_shallow_grafts_buf(&req_buf);
+
 	/*
 	 * Finally, tell the other end!
 	 */
@@ -274,7 +293,7 @@ int send_pack(struct send_pack_args *args,
 	}
 
 	if (args->stateless_rpc) {
-		if (!args->dry_run && cmds_sent) {
+		if (!args->dry_run && (cmds_sent || is_repository_shallow())) {
 			packet_buf_flush(&req_buf);
 			send_sideband(out, -1, req_buf.buf, req_buf.len, LARGE_PACKET_MAX);
 		}
diff --git a/send-pack.h b/send-pack.h
index 05d7ab118b..8e843924cf 100644
--- a/send-pack.h
+++ b/send-pack.h
@@ -16,6 +16,6 @@ struct send_pack_args {
 
 int send_pack(struct send_pack_args *args,
 	      int fd[], struct child_process *conn,
-	      struct ref *remote_refs, struct extra_have_objects *extra_have);
+	      struct ref *remote_refs, struct sha1_array *extra_have);
 
 #endif
diff --git a/shallow.c b/shallow.c
index 961cf6f024..bbc98b55c0 100644
--- a/shallow.c
+++ b/shallow.c
@@ -2,15 +2,23 @@
 #include "commit.h"
 #include "tag.h"
 #include "pkt-line.h"
+#include "remote.h"
+#include "refs.h"
+#include "sha1-array.h"
+#include "diff.h"
+#include "revision.h"
+#include "commit-slab.h"
 
 static int is_shallow = -1;
 static struct stat shallow_stat;
 static char *alternate_shallow_file;
 
-void set_alternate_shallow_file(const char *path)
+void set_alternate_shallow_file(const char *path, int override)
 {
 	if (is_shallow != -1)
 		die("BUG: is_repository_shallow must not be called before set_alternate_shallow_file");
+	if (alternate_shallow_file && !override)
+		return;
 	free(alternate_shallow_file);
 	alternate_shallow_file = path ? xstrdup(path) : NULL;
 }
@@ -69,6 +77,7 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 	struct commit_list *result = NULL;
 	struct object_array stack = OBJECT_ARRAY_INIT;
 	struct commit *commit = NULL;
+	struct commit_graft *graft;
 
 	while (commit || i < heads->nr || stack.nr) {
 		struct commit_list *p;
@@ -92,7 +101,10 @@ struct commit_list *get_shallow_commits(struct object_array *heads, int depth,
 		}
 		parse_commit_or_die(commit);
 		cur_depth++;
-		if (cur_depth >= depth) {
+		if ((depth != INFINITE_DEPTH && cur_depth >= depth) ||
+		    (is_repository_shallow() && !commit->parents &&
+		     (graft = lookup_commit_graft(commit->object.sha1)) != NULL &&
+		     graft->nr_parent < 0)) {
 			commit_list_insert(commit, &result);
 			commit->object.flags |= shallow_flag;
 			commit = NULL;
@@ -142,10 +154,14 @@ void check_shallow_file_for_update(void)
 		die("shallow file was changed during fetch");
 }
 
+#define SEEN_ONLY 1
+#define VERBOSE   2
+
 struct write_shallow_data {
 	struct strbuf *out;
 	int use_pack_protocol;
 	int count;
+	unsigned flags;
 };
 
 static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
@@ -154,6 +170,15 @@ static int write_one_shallow(const struct commit_graft *graft, void *cb_data)
 	const char *hex = sha1_to_hex(graft->sha1);
 	if (graft->nr_parent != -1)
 		return 0;
+	if (data->flags & SEEN_ONLY) {
+		struct commit *c = lookup_commit(graft->sha1);
+		if (!c || !(c->object.flags & SEEN)) {
+			if (data->flags & VERBOSE)
+				printf("Removing %s from .git/shallow\n",
+				       sha1_to_hex(c->object.sha1));
+			return 0;
+		}
+	}
 	data->count++;
 	if (data->use_pack_protocol)
 		packet_buf_write(data->out, "shallow %s", hex);
@@ -164,22 +189,39 @@ 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)
+static int write_shallow_commits_1(struct strbuf *out, int use_pack_protocol,
+				   const struct sha1_array *extra,
+				   unsigned flags)
 {
 	struct write_shallow_data data;
+	int i;
 	data.out = out;
 	data.use_pack_protocol = use_pack_protocol;
 	data.count = 0;
+	data.flags = flags;
 	for_each_commit_graft(write_one_shallow, &data);
+	if (!extra)
+		return data.count;
+	for (i = 0; i < extra->nr; i++) {
+		strbuf_addstr(out, sha1_to_hex(extra->sha1[i]));
+		strbuf_addch(out, '\n');
+		data.count++;
+	}
 	return data.count;
 }
 
-char *setup_temporary_shallow(void)
+int write_shallow_commits(struct strbuf *out, int use_pack_protocol,
+			  const struct sha1_array *extra)
+{
+	return write_shallow_commits_1(out, use_pack_protocol, extra, 0);
+}
+
+char *setup_temporary_shallow(const struct sha1_array *extra)
 {
 	struct strbuf sb = STRBUF_INIT;
 	int fd;
 
-	if (write_shallow_commits(&sb, 0)) {
+	if (write_shallow_commits(&sb, 0, extra)) {
 		struct strbuf path = STRBUF_INIT;
 		strbuf_addstr(&path, git_path("shallow_XXXXXX"));
 		fd = xmkstemp(path.buf);
@@ -198,7 +240,8 @@ char *setup_temporary_shallow(void)
 }
 
 void setup_alternate_shallow(struct lock_file *shallow_lock,
-			     const char **alternate_shallow_file)
+			     const char **alternate_shallow_file,
+			     const struct sha1_array *extra)
 {
 	struct strbuf sb = STRBUF_INIT;
 	int fd;
@@ -206,7 +249,7 @@ void setup_alternate_shallow(struct lock_file *shallow_lock,
 	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 (write_shallow_commits(&sb, 0, extra)) {
 		if (write_in_full(fd, sb.buf, sb.len) != sb.len)
 			die_errno("failed to write to %s",
 				  shallow_lock->filename);
@@ -219,3 +262,415 @@ void setup_alternate_shallow(struct lock_file *shallow_lock,
 		*alternate_shallow_file = "";
 	strbuf_release(&sb);
 }
+
+static int advertise_shallow_grafts_cb(const struct commit_graft *graft, void *cb)
+{
+	int fd = *(int *)cb;
+	if (graft->nr_parent == -1)
+		packet_write(fd, "shallow %s\n", sha1_to_hex(graft->sha1));
+	return 0;
+}
+
+void advertise_shallow_grafts(int fd)
+{
+	if (!is_repository_shallow())
+		return;
+	for_each_commit_graft(advertise_shallow_grafts_cb, &fd);
+}
+
+/*
+ * mark_reachable_objects() should have been run prior to this and all
+ * reachable commits marked as "SEEN".
+ */
+void prune_shallow(int show_only)
+{
+	static struct lock_file shallow_lock;
+	struct strbuf sb = STRBUF_INIT;
+	int fd;
+
+	if (show_only) {
+		write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY | VERBOSE);
+		strbuf_release(&sb);
+		return;
+	}
+	check_shallow_file_for_update();
+	fd = hold_lock_file_for_update(&shallow_lock, git_path("shallow"),
+				       LOCK_DIE_ON_ERROR);
+	if (write_shallow_commits_1(&sb, 0, NULL, SEEN_ONLY)) {
+		if (write_in_full(fd, sb.buf, sb.len) != sb.len)
+			die_errno("failed to write to %s",
+				  shallow_lock.filename);
+		commit_lock_file(&shallow_lock);
+	} else {
+		unlink(git_path("shallow"));
+		rollback_lock_file(&shallow_lock);
+	}
+	strbuf_release(&sb);
+}
+
+#define TRACE_KEY "GIT_TRACE_SHALLOW"
+
+/*
+ * Step 1, split sender shallow commits into "ours" and "theirs"
+ * Step 2, clean "ours" based on .git/shallow
+ */
+void prepare_shallow_info(struct shallow_info *info, struct sha1_array *sa)
+{
+	int i;
+	trace_printf_key(TRACE_KEY, "shallow: prepare_shallow_info\n");
+	memset(info, 0, sizeof(*info));
+	info->shallow = sa;
+	if (!sa)
+		return;
+	info->ours = xmalloc(sizeof(*info->ours) * sa->nr);
+	info->theirs = xmalloc(sizeof(*info->theirs) * sa->nr);
+	for (i = 0; i < sa->nr; i++) {
+		if (has_sha1_file(sa->sha1[i])) {
+			struct commit_graft *graft;
+			graft = lookup_commit_graft(sa->sha1[i]);
+			if (graft && graft->nr_parent < 0)
+				continue;
+			info->ours[info->nr_ours++] = i;
+		} else
+			info->theirs[info->nr_theirs++] = i;
+	}
+}
+
+void clear_shallow_info(struct shallow_info *info)
+{
+	free(info->ours);
+	free(info->theirs);
+}
+
+/* Step 4, remove non-existent ones in "theirs" after getting the pack */
+
+void remove_nonexistent_theirs_shallow(struct shallow_info *info)
+{
+	unsigned char (*sha1)[20] = info->shallow->sha1;
+	int i, dst;
+	trace_printf_key(TRACE_KEY, "shallow: remove_nonexistent_theirs_shallow\n");
+	for (i = dst = 0; i < info->nr_theirs; i++) {
+		if (i != dst)
+			info->theirs[dst] = info->theirs[i];
+		if (has_sha1_file(sha1[info->theirs[i]]))
+			dst++;
+	}
+	info->nr_theirs = dst;
+}
+
+define_commit_slab(ref_bitmap, uint32_t *);
+
+struct paint_info {
+	struct ref_bitmap ref_bitmap;
+	unsigned nr_bits;
+	char **slab;
+	char *free, *end;
+	unsigned slab_count;
+};
+
+static uint32_t *paint_alloc(struct paint_info *info)
+{
+	unsigned nr = (info->nr_bits + 31) / 32;
+	unsigned size = nr * sizeof(uint32_t);
+	void *p;
+	if (!info->slab_count || info->free + size > info->end) {
+		info->slab_count++;
+		info->slab = xrealloc(info->slab,
+				      info->slab_count * sizeof(*info->slab));
+		info->free = xmalloc(COMMIT_SLAB_SIZE);
+		info->slab[info->slab_count - 1] = info->free;
+		info->end = info->free + COMMIT_SLAB_SIZE;
+	}
+	p = info->free;
+	info->free += size;
+	return p;
+}
+
+/*
+ * Given a commit SHA-1, walk down to parents until either SEEN,
+ * UNINTERESTING or BOTTOM is hit. Set the id-th bit in ref_bitmap for
+ * all walked commits.
+ */
+static void paint_down(struct paint_info *info, const unsigned char *sha1,
+		       int id)
+{
+	unsigned int i, nr;
+	struct commit_list *head = NULL;
+	int bitmap_nr = (info->nr_bits + 31) / 32;
+	int bitmap_size = bitmap_nr * sizeof(uint32_t);
+	uint32_t *tmp = xmalloc(bitmap_size); /* to be freed before return */
+	uint32_t *bitmap = paint_alloc(info);
+	struct commit *c = lookup_commit_reference_gently(sha1, 1);
+	if (!c)
+		return;
+	memset(bitmap, 0, bitmap_size);
+	bitmap[id / 32] |= (1 << (id % 32));
+	commit_list_insert(c, &head);
+	while (head) {
+		struct commit_list *p;
+		struct commit *c = head->item;
+		uint32_t **refs = ref_bitmap_at(&info->ref_bitmap, c);
+
+		p = head;
+		head = head->next;
+		free(p);
+
+		/* XXX check "UNINTERESTING" from pack bitmaps if available */
+		if (c->object.flags & (SEEN | UNINTERESTING))
+			continue;
+		else
+			c->object.flags |= SEEN;
+
+		if (*refs == NULL)
+			*refs = bitmap;
+		else {
+			memcpy(tmp, *refs, bitmap_size);
+			for (i = 0; i < bitmap_nr; i++)
+				tmp[i] |= bitmap[i];
+			if (memcmp(tmp, *refs, bitmap_size)) {
+				*refs = paint_alloc(info);
+				memcpy(*refs, tmp, bitmap_size);
+			}
+		}
+
+		if (c->object.flags & BOTTOM)
+			continue;
+
+		if (parse_commit(c))
+			die("unable to parse commit %s",
+			    sha1_to_hex(c->object.sha1));
+
+		for (p = c->parents; p; p = p->next) {
+			uint32_t **p_refs = ref_bitmap_at(&info->ref_bitmap,
+							  p->item);
+			if (p->item->object.flags & SEEN)
+				continue;
+			if (*p_refs == NULL || *p_refs == *refs)
+				*p_refs = *refs;
+			commit_list_insert(p->item, &head);
+		}
+	}
+
+	nr = get_max_object_index();
+	for (i = 0; i < nr; i++) {
+		struct object *o = get_indexed_object(i);
+		if (o && o->type == OBJ_COMMIT)
+			o->flags &= ~SEEN;
+	}
+
+	free(tmp);
+}
+
+static int mark_uninteresting(const char *refname,
+			      const unsigned char *sha1,
+			      int flags, void *cb_data)
+{
+	struct commit *commit = lookup_commit_reference_gently(sha1, 1);
+	if (!commit)
+		return 0;
+	commit->object.flags |= UNINTERESTING;
+	mark_parents_uninteresting(commit);
+	return 0;
+}
+
+static void post_assign_shallow(struct shallow_info *info,
+				struct ref_bitmap *ref_bitmap,
+				int *ref_status);
+/*
+ * Step 6(+7), associate shallow commits with new refs
+ *
+ * info->ref must be initialized before calling this function.
+ *
+ * If used is not NULL, it's an array of info->shallow->nr
+ * bitmaps. The n-th bit set in the m-th bitmap if ref[n] needs the
+ * m-th shallow commit from info->shallow.
+ *
+ * If used is NULL, "ours" and "theirs" are updated. And if ref_status
+ * is not NULL it's an array of ref->nr ints. ref_status[i] is true if
+ * the ref needs some shallow commits from either info->ours or
+ * info->theirs.
+ */
+void assign_shallow_commits_to_refs(struct shallow_info *info,
+				    uint32_t **used, int *ref_status)
+{
+	unsigned char (*sha1)[20] = info->shallow->sha1;
+	struct sha1_array *ref = info->ref;
+	unsigned int i, nr;
+	int *shallow, nr_shallow = 0;
+	struct paint_info pi;
+
+	trace_printf_key(TRACE_KEY, "shallow: assign_shallow_commits_to_refs\n");
+	shallow = xmalloc(sizeof(*shallow) * (info->nr_ours + info->nr_theirs));
+	for (i = 0; i < info->nr_ours; i++)
+		shallow[nr_shallow++] = info->ours[i];
+	for (i = 0; i < info->nr_theirs; i++)
+		shallow[nr_shallow++] = info->theirs[i];
+
+	/*
+	 * Prepare the commit graph to track what refs can reach what
+	 * (new) shallow commits.
+	 */
+	nr = get_max_object_index();
+	for (i = 0; i < nr; i++) {
+		struct object *o = get_indexed_object(i);
+		if (!o || o->type != OBJ_COMMIT)
+			continue;
+
+		o->flags &= ~(UNINTERESTING | BOTTOM | SEEN);
+	}
+
+	memset(&pi, 0, sizeof(pi));
+	init_ref_bitmap(&pi.ref_bitmap);
+	pi.nr_bits = ref->nr;
+
+	/*
+	 * "--not --all" to cut short the traversal if new refs
+	 * connect to old refs. If not (e.g. force ref updates) it'll
+	 * have to go down to the current shallow commits.
+	 */
+	head_ref(mark_uninteresting, NULL);
+	for_each_ref(mark_uninteresting, NULL);
+
+	/* Mark potential bottoms so we won't go out of bound */
+	for (i = 0; i < nr_shallow; i++) {
+		struct commit *c = lookup_commit(sha1[shallow[i]]);
+		c->object.flags |= BOTTOM;
+	}
+
+	for (i = 0; i < ref->nr; i++)
+		paint_down(&pi, ref->sha1[i], i);
+
+	if (used) {
+		int bitmap_size = ((pi.nr_bits + 31) / 32) * sizeof(uint32_t);
+		memset(used, 0, sizeof(*used) * info->shallow->nr);
+		for (i = 0; i < nr_shallow; i++) {
+			const struct commit *c = lookup_commit(sha1[shallow[i]]);
+			uint32_t **map = ref_bitmap_at(&pi.ref_bitmap, c);
+			if (*map)
+				used[shallow[i]] = xmemdupz(*map, bitmap_size);
+		}
+		/*
+		 * unreachable shallow commits are not removed from
+		 * "ours" and "theirs". The user is supposed to run
+		 * step 7 on every ref separately and not trust "ours"
+		 * and "theirs" any more.
+		 */
+	} else
+		post_assign_shallow(info, &pi.ref_bitmap, ref_status);
+
+	clear_ref_bitmap(&pi.ref_bitmap);
+	for (i = 0; i < pi.slab_count; i++)
+		free(pi.slab[i]);
+	free(pi.slab);
+	free(shallow);
+}
+
+struct commit_array {
+	struct commit **commits;
+	int nr, alloc;
+};
+
+static int add_ref(const char *refname,
+		   const unsigned char *sha1, int flags, void *cb_data)
+{
+	struct commit_array *ca = cb_data;
+	ALLOC_GROW(ca->commits, ca->nr + 1, ca->alloc);
+	ca->commits[ca->nr] = lookup_commit_reference_gently(sha1, 1);
+	if (ca->commits[ca->nr])
+		ca->nr++;
+	return 0;
+}
+
+static void update_refstatus(int *ref_status, int nr, uint32_t *bitmap)
+{
+	int i;
+	if (!ref_status)
+		return;
+	for (i = 0; i < nr; i++)
+		if (bitmap[i / 32] & (1 << (i % 32)))
+			ref_status[i]++;
+}
+
+/*
+ * Step 7, reachability test on "ours" at commit level
+ */
+static void post_assign_shallow(struct shallow_info *info,
+				struct ref_bitmap *ref_bitmap,
+				int *ref_status)
+{
+	unsigned char (*sha1)[20] = info->shallow->sha1;
+	struct commit *c;
+	uint32_t **bitmap;
+	int dst, i, j;
+	int bitmap_nr = (info->ref->nr + 31) / 32;
+	struct commit_array ca;
+
+	trace_printf_key(TRACE_KEY, "shallow: post_assign_shallow\n");
+	if (ref_status)
+		memset(ref_status, 0, sizeof(*ref_status) * info->ref->nr);
+
+	/* Remove unreachable shallow commits from "theirs" */
+	for (i = dst = 0; i < info->nr_theirs; i++) {
+		if (i != dst)
+			info->theirs[dst] = info->theirs[i];
+		c = lookup_commit(sha1[info->theirs[i]]);
+		bitmap = ref_bitmap_at(ref_bitmap, c);
+		if (!*bitmap)
+			continue;
+		for (j = 0; j < bitmap_nr; j++)
+			if (bitmap[0][j]) {
+				update_refstatus(ref_status, info->ref->nr, *bitmap);
+				dst++;
+				break;
+			}
+	}
+	info->nr_theirs = dst;
+
+	memset(&ca, 0, sizeof(ca));
+	head_ref(add_ref, &ca);
+	for_each_ref(add_ref, &ca);
+
+	/* Remove unreachable shallow commits from "ours" */
+	for (i = dst = 0; i < info->nr_ours; i++) {
+		if (i != dst)
+			info->ours[dst] = info->ours[i];
+		c = lookup_commit(sha1[info->ours[i]]);
+		bitmap = ref_bitmap_at(ref_bitmap, c);
+		if (!*bitmap)
+			continue;
+		for (j = 0; j < bitmap_nr; j++)
+			if (bitmap[0][j] &&
+			    /* Step 7, reachability test at commit level */
+			    !in_merge_bases_many(c, ca.nr, ca.commits)) {
+				update_refstatus(ref_status, info->ref->nr, *bitmap);
+				dst++;
+				break;
+			}
+	}
+	info->nr_ours = dst;
+
+	free(ca.commits);
+}
+
+/* (Delayed) step 7, reachability test at commit level */
+int delayed_reachability_test(struct shallow_info *si, int c)
+{
+	if (si->need_reachability_test[c]) {
+		struct commit *commit = lookup_commit(si->shallow->sha1[c]);
+
+		if (!si->commits) {
+			struct commit_array ca;
+			memset(&ca, 0, sizeof(ca));
+			head_ref(add_ref, &ca);
+			for_each_ref(add_ref, &ca);
+			si->commits = ca.commits;
+			si->nr_commits = ca.nr;
+		}
+
+		si->reachable[c] = in_merge_bases_many(commit,
+						       si->nr_commits,
+						       si->commits);
+		si->need_reachability_test[c] = 0;
+	}
+	return si->reachable[c];
+}
diff --git a/t/t5304-prune.sh b/t/t5304-prune.sh
index e4bb3a1457..66c9a41739 100755
--- a/t/t5304-prune.sh
+++ b/t/t5304-prune.sh
@@ -221,4 +221,14 @@ EOF
 	test_cmp expected actual
 '
 
+test_expect_success 'prune .git/shallow' '
+	SHA1=`echo hi|git commit-tree HEAD^{tree}` &&
+	echo $SHA1 >.git/shallow &&
+	git prune --dry-run >out &&
+	grep $SHA1 .git/shallow &&
+	grep $SHA1 out &&
+	git prune &&
+	! test -f .git/shallow
+'
+
 test_done
diff --git a/t/t5537-fetch-shallow.sh b/t/t5537-fetch-shallow.sh
new file mode 100755
index 0000000000..b0fa7387cb
--- /dev/null
+++ b/t/t5537-fetch-shallow.sh
@@ -0,0 +1,204 @@
+#!/bin/sh
+
+test_description='fetch/clone from a shallow clone'
+
+. ./test-lib.sh
+
+commit() {
+	echo "$1" >tracked &&
+	git add tracked &&
+	git commit -m "$1"
+}
+
+test_expect_success 'setup' '
+	commit 1 &&
+	commit 2 &&
+	commit 3 &&
+	commit 4 &&
+	git config --global transfer.fsckObjects true
+'
+
+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 &&
+	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 &&
+	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_expect_success 'fetch --unshallow from shallow clone' '
+	(
+	cd shallow2 &&
+	git fetch --unshallow &&
+	git fsck &&
+	git log --format=%s origin/master >actual &&
+	cat <<EOF >expect &&
+6
+5
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'fetch something upstream has but hidden by clients shallow boundaries' '
+	# the blob "1" is available in .git but hidden by the
+	# shallow2/.git/shallow and it should be resent
+	! git --git-dir=shallow2/.git cat-file blob `echo 1|git hash-object --stdin` >/dev/null &&
+	echo 1 >1.t &&
+	git add 1.t &&
+	git commit -m add-1-back &&
+	(
+	cd shallow2 &&
+	git fetch ../.git +refs/heads/master:refs/remotes/top/master &&
+	git fsck &&
+	git log --format=%s top/master >actual &&
+	cat <<EOF >expect &&
+add-1-back
+4
+3
+EOF
+	test_cmp expect actual
+	) &&
+	git --git-dir=shallow2/.git cat-file blob `echo 1|git hash-object --stdin` >/dev/null
+
+'
+
+test_expect_success 'fetch that requires changes in .git/shallow is filtered' '
+	(
+	cd shallow &&
+	git checkout --orphan no-shallow &&
+	commit no-shallow
+	) &&
+	git init notshallow &&
+	(
+	cd notshallow &&
+	git fetch ../shallow/.git refs/heads/*:refs/remotes/shallow/*&&
+	git for-each-ref --format="%(refname)" >actual.refs &&
+	cat <<EOF >expect.refs &&
+refs/remotes/shallow/no-shallow
+EOF
+	test_cmp expect.refs actual.refs &&
+	git log --format=%s shallow/no-shallow >actual &&
+	cat <<EOF >expect &&
+no-shallow
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'fetch --update-shallow' '
+	(
+	cd shallow &&
+	git checkout master &&
+	commit 7 &&
+	git tag -m foo heavy-tag HEAD^ &&
+	git tag light-tag HEAD^:tracked
+	) &&
+	(
+	cd notshallow &&
+	git fetch --update-shallow ../shallow/.git refs/heads/*:refs/remotes/shallow/* &&
+	git fsck &&
+	git for-each-ref --sort=refname --format="%(refname)" >actual.refs &&
+	cat <<EOF >expect.refs &&
+refs/remotes/shallow/master
+refs/remotes/shallow/no-shallow
+refs/tags/heavy-tag
+refs/tags/light-tag
+EOF
+	test_cmp expect.refs actual.refs &&
+	git log --format=%s shallow/master >actual &&
+	cat <<EOF >expect &&
+7
+6
+5
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+if test -n "$NO_CURL" -o -z "$GIT_TEST_HTTPD"; then
+	say 'skipping remaining tests, git built without http support'
+	test_done
+fi
+
+LIB_HTTPD_PORT=${LIB_HTTPD_PORT-'5537'}
+. "$TEST_DIRECTORY"/lib-httpd.sh
+start_httpd
+
+test_expect_success 'clone http repository' '
+	git clone --bare --no-local shallow "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	git clone $HTTPD_URL/smart/repo.git clone &&
+	(
+	cd clone &&
+	git fsck &&
+	git log --format=%s origin/master >actual &&
+	cat <<EOF >expect &&
+7
+6
+5
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+stop_httpd
+test_done
diff --git a/t/t5538-push-shallow.sh b/t/t5538-push-shallow.sh
new file mode 100755
index 0000000000..0a6e40f144
--- /dev/null
+++ b/t/t5538-push-shallow.sh
@@ -0,0 +1,183 @@
+#!/bin/sh
+
+test_description='push from/to a shallow clone'
+
+. ./test-lib.sh
+
+commit() {
+	echo "$1" >tracked &&
+	git add tracked &&
+	git commit -m "$1"
+}
+
+test_expect_success 'setup' '
+	git config --global transfer.fsckObjects true &&
+	commit 1 &&
+	commit 2 &&
+	commit 3 &&
+	commit 4 &&
+	git clone . full &&
+	(
+	git init full-abc &&
+	cd full-abc &&
+	commit a &&
+	commit b &&
+	commit c
+	) &&
+	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 &&
+	git clone --no-local --depth=2 full-abc/.git shallow2 &&
+	git --git-dir=shallow2/.git log --format=%s >actual &&
+	cat <<EOF >expect &&
+c
+b
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'push from shallow clone' '
+	(
+	cd shallow &&
+	commit 5 &&
+	git push ../.git +master:refs/remotes/shallow/master
+	) &&
+	git log --format=%s shallow/master >actual &&
+	git fsck &&
+	cat <<EOF >expect &&
+5
+4
+3
+2
+1
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'push from shallow clone, with grafted roots' '
+	(
+	cd shallow2 &&
+	test_must_fail git push ../.git +master:refs/remotes/shallow2/master 2>err &&
+	grep "shallow2/master.*shallow update not allowed" err
+	) &&
+	test_must_fail git rev-parse shallow2/master &&
+	git fsck
+'
+
+test_expect_success 'add new shallow root with receive.updateshallow on' '
+	test_config receive.shallowupdate true &&
+	(
+	cd shallow2 &&
+	git push ../.git +master:refs/remotes/shallow2/master
+	) &&
+	git log --format=%s shallow2/master >actual &&
+	git fsck &&
+	cat <<EOF >expect &&
+c
+b
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'push from shallow to shallow' '
+	(
+	cd shallow &&
+	git --git-dir=../shallow2/.git config receive.shallowupdate true &&
+	git push ../shallow2/.git +master:refs/remotes/shallow/master &&
+	git --git-dir=../shallow2/.git config receive.shallowupdate false
+	) &&
+	(
+	cd shallow2 &&
+	git log --format=%s shallow/master >actual &&
+	git fsck &&
+	cat <<EOF >expect &&
+5
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'push from full to shallow' '
+	! git --git-dir=shallow2/.git cat-file blob `echo 1|git hash-object --stdin` &&
+	commit 1 &&
+	git push shallow2/.git +master:refs/remotes/top/master &&
+	(
+	cd shallow2 &&
+	git log --format=%s top/master >actual &&
+	git fsck &&
+	cat <<EOF >expect &&
+1
+4
+3
+EOF
+	test_cmp expect actual &&
+	git cat-file blob `echo 1|git hash-object --stdin` >/dev/null
+	)
+'
+
+if test -n "$NO_CURL" -o -z "$GIT_TEST_HTTPD"; then
+	say 'skipping remaining tests, git built without http support'
+	test_done
+fi
+
+LIB_HTTPD_PORT=${LIB_HTTPD_PORT-'5537'}
+. "$TEST_DIRECTORY"/lib-httpd.sh
+start_httpd
+
+test_expect_success 'push to shallow repo via http' '
+	git clone --bare --no-local shallow "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	(
+	cd "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	git config http.receivepack true
+	) &&
+	(
+	cd full &&
+	commit 9 &&
+	git push $HTTPD_URL/smart/repo.git +master:refs/remotes/top/master
+	) &&
+	(
+	cd "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	git fsck &&
+	git log --format=%s top/master >actual &&
+	cat <<EOF >expect &&
+9
+4
+3
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'push from shallow repo via http' '
+	mv "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" shallow-upstream.git &&
+	git clone --bare --no-local full "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	(
+	cd "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	git config http.receivepack true
+	) &&
+	commit 10 &&
+	git push $HTTPD_URL/smart/repo.git +master:refs/remotes/top/master &&
+	(
+	cd "$HTTPD_DOCUMENT_ROOT_PATH/repo.git" &&
+	git fsck &&
+	git log --format=%s top/master >actual &&
+	cat <<EOF >expect &&
+10
+1
+4
+3
+2
+1
+EOF
+	test_cmp expect actual
+	)
+'
+
+stop_httpd
+test_done
diff --git a/t/t5601-clone.sh b/t/t5601-clone.sh
index 62fbd7e664..5e67035be8 100755
--- a/t/t5601-clone.sh
+++ b/t/t5601-clone.sh
@@ -430,4 +430,11 @@ test_expect_success 'clone from a repository with two identical branches' '
 
 '
 
+test_expect_success 'shallow clone locally' '
+	git clone --depth=1 --no-local src ssrrcc &&
+	git clone ssrrcc ddsstt &&
+	test_cmp ssrrcc/.git/shallow ddsstt/.git/shallow &&
+	( cd ddsstt && git fsck )
+'
+
 test_done
diff --git a/trace.c b/trace.c
index 3d744d1d4d..08180a90bc 100644
--- a/trace.c
+++ b/trace.c
@@ -76,7 +76,7 @@ static void trace_vprintf(const char *key, const char *fmt, va_list ap)
 }
 
 __attribute__((format (printf, 2, 3)))
-static void trace_printf_key(const char *key, const char *fmt, ...)
+void trace_printf_key(const char *key, const char *fmt, ...)
 {
 	va_list ap;
 	va_start(ap, fmt);
diff --git a/transport-helper.c b/transport-helper.c
index 2010674bb4..087f617d39 100644
--- a/transport-helper.c
+++ b/transport-helper.c
@@ -360,6 +360,12 @@ static int fetch_with_fetch(struct transport *transport,
 	    data->transport_options.check_self_contained_and_connected)
 		set_helper_option(transport, "check-connectivity", "true");
 
+	if (transport->cloning)
+		set_helper_option(transport, "cloning", "true");
+
+	if (data->transport_options.update_shallow)
+		set_helper_option(transport, "update-shallow", "true");
+
 	for (i = 0; i < nr_heads; i++) {
 		const struct ref *posn = to_fetch[i];
 		if (posn->status & REF_STATUS_UPTODATE)
diff --git a/transport.c b/transport.c
index 824c5b93f9..ca7bb441bf 100644
--- a/transport.c
+++ b/transport.c
@@ -14,6 +14,7 @@
 #include "url.h"
 #include "submodule.h"
 #include "string-list.h"
+#include "sha1-array.h"
 
 /* rsync support */
 
@@ -454,7 +455,8 @@ struct git_transport_data {
 	struct child_process *conn;
 	int fd[2];
 	unsigned got_remote_heads : 1;
-	struct extra_have_objects extra_have;
+	struct sha1_array extra_have;
+	struct sha1_array shallow;
 };
 
 static int set_git_option(struct git_transport_options *opts,
@@ -475,6 +477,9 @@ static int set_git_option(struct git_transport_options *opts,
 	} else if (!strcmp(name, TRANS_OPT_KEEP)) {
 		opts->keep = !!value;
 		return 0;
+	} else if (!strcmp(name, TRANS_OPT_UPDATE_SHALLOW)) {
+		opts->update_shallow = !!value;
+		return 0;
 	} else if (!strcmp(name, TRANS_OPT_DEPTH)) {
 		if (!value)
 			opts->depth = 0;
@@ -511,7 +516,9 @@ 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);
+			 for_push ? REF_NORMAL : 0,
+			 &data->extra_have,
+			 &data->shallow);
 	data->got_remote_heads = 1;
 
 	return refs;
@@ -538,16 +545,19 @@ static int fetch_refs_via_pack(struct transport *transport,
 	args.depth = data->options.depth;
 	args.check_self_contained_and_connected =
 		data->options.check_self_contained_and_connected;
+	args.cloning = transport->cloning;
+	args.update_shallow = data->options.update_shallow;
 
 	if (!data->got_remote_heads) {
 		connect_setup(transport, 0, 0);
-		get_remote_heads(data->fd[0], NULL, 0, &refs_tmp, 0, NULL);
+		get_remote_heads(data->fd[0], NULL, 0, &refs_tmp, 0,
+				 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]);
@@ -713,6 +723,10 @@ static int print_one_push_status(struct ref *ref, const char *dest, int count, i
 		print_ref_status('!', "[rejected]", ref, ref->peer_ref,
 						 "stale info", porcelain);
 		break;
+	case REF_STATUS_REJECT_SHALLOW:
+		print_ref_status('!', "[rejected]", ref, ref->peer_ref,
+						 "new shallow roots not allowed", porcelain);
+		break;
 	case REF_STATUS_REMOTE_REJECT:
 		print_ref_status('!', "[remote rejected]", ref,
 						 ref->deletion ? NULL : ref->peer_ref,
@@ -805,7 +819,8 @@ static int git_transport_push(struct transport *transport, struct ref *remote_re
 		struct ref *tmp_refs;
 		connect_setup(transport, 1, 0);
 
-		get_remote_heads(data->fd[0], NULL, 0, &tmp_refs, REF_NORMAL, NULL);
+		get_remote_heads(data->fd[0], NULL, 0, &tmp_refs, REF_NORMAL,
+				 NULL, &data->shallow);
 		data->got_remote_heads = 1;
 	}
 
diff --git a/transport.h b/transport.h
index 8f96bed775..02ea248db1 100644
--- a/transport.h
+++ b/transport.h
@@ -11,6 +11,7 @@ struct git_transport_options {
 	unsigned followtags : 1;
 	unsigned check_self_contained_and_connected : 1;
 	unsigned self_contained_and_connected : 1;
+	unsigned update_shallow : 1;
 	int depth;
 	const char *uploadpack;
 	const char *receivepack;
@@ -35,6 +36,12 @@ struct transport {
 	 */
 	unsigned cannot_reuse : 1;
 
+	/*
+	 * A hint from caller that it will be performing a clone, not
+	 * normal fetch. IOW the repository is guaranteed empty.
+	 */
+	unsigned cloning : 1;
+
 	/**
 	 * Returns 0 if successful, positive if the option is not
 	 * recognized or is inapplicable, and negative if the option
@@ -146,6 +153,9 @@ struct transport *transport_get(struct remote *, const char *);
 /* Aggressively fetch annotated tags if possible */
 #define TRANS_OPT_FOLLOWTAGS "followtags"
 
+/* Accept refs that may update .git/shallow without --depth */
+#define TRANS_OPT_UPDATE_SHALLOW "updateshallow"
+
 /**
  * Returns 0 if the option was used, non-zero otherwise. Prints a
  * message to stderr if the option is not used.
@@ -193,10 +203,4 @@ void transport_print_push_status(const char *dest, struct ref *refs,
 
 typedef void alternate_ref_fn(const struct ref *, void *);
 extern void for_each_alternate_ref(alternate_ref_fn, void *);
-
-struct send_pack_args;
-extern int send_pack(struct send_pack_args *args,
-		     int fd[], struct child_process *conn,
-		     struct ref *remote_refs,
-		     struct extra_have_objects *extra_have);
 #endif
diff --git a/upload-pack.c b/upload-pack.c
index ec56cdbce9..0c44f6b292 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -84,7 +84,7 @@ static void create_pack_file(void)
 	char *shallow_file = NULL;
 
 	if (shallow_nr) {
-		shallow_file = setup_temporary_shallow();
+		shallow_file = setup_temporary_shallow(NULL);
 		argv[arg++] = "--shallow-file";
 		argv[arg++] = shallow_file;
 	}
@@ -619,7 +619,7 @@ static void receive_needs(void)
 	if (depth > 0) {
 		struct commit_list *result = NULL, *backup = NULL;
 		int i;
-		if (depth == INFINITE_DEPTH)
+		if (depth == INFINITE_DEPTH && !is_repository_shallow())
 			for (i = 0; i < shallows.nr; i++) {
 				struct object *object = shallows.objects[i].item;
 				object->flags |= NOT_SHALLOW;
@@ -757,6 +757,7 @@ static void upload_pack(void)
 		reset_timeout();
 		head_ref_namespaced(send_ref, &symref);
 		for_each_namespaced_ref(send_ref, &symref);
+		advertise_shallow_grafts(1);
 		packet_flush(1);
 	} else {
 		head_ref_namespaced(mark_our_ref, NULL);
@@ -834,8 +835,7 @@ int main(int argc, char **argv)
 
 	if (!enter_repo(dir, strict))
 		die("'%s' does not appear to be a git repository", dir);
-	if (is_repository_shallow())
-		die("attempt to fetch/clone from a shallow repository");
+
 	git_config(upload_pack_config, NULL);
 	upload_pack();
 	return 0;