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
  ...

1 files changed, 462 insertions, 7 deletions

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];
+}