[PATCH 00/16] Subtree clone proof of concept

@@ -551,6 +551,7 @@ extern int read_replace_refs;
 extern int fsync_object_files;
 extern int core_preload_index;
 extern int core_apply_sparse_checkout;
+extern const char *core_subtree;
 
 enum safe_crlf {
 	SAFE_CRLF_FALSE = 0,

@@ -595,6 +595,9 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.subtree"))
+		return git_config_string(&core_subtree, var, value);
+
 	/* Add other config variables here and to Documentation/config.txt. */
 	return 0;
 }

@@ -57,6 +57,8 @@ int core_apply_sparse_checkout;
 /* Parallel index stat data preload? */
 int core_preload_index = 0;
 
+const char *core_subtree;
+
 /* This is set by setup_git_dir_gently() and/or git_default_config() */
 char *git_work_tree_cfg;
 static char *work_tree;

@@ -61,12 +61,15 @@ static void process_tree(struct rev_info *revs,
 			 struct tree *tree,
 			 show_object_fn show,
 			 struct name_path *path,
-			 const char *name)
+			 const char *name,
+			 const char *subtree)
 {
 	struct object *obj = &tree->object;
 	struct tree_desc desc;
 	struct name_entry entry;
 	struct name_path me;
+	const char *slash;
+	int subtree_len;
 
 	if (!revs->tree_objects)
 		return;

@@ -82,13 +85,21 @@ static void process_tree(struct rev_info *revs,
 	me.elem = name;
 	me.elem_len = strlen(name);
 
+	if (subtree) {
+		slash = strchr(subtree, '/');
+		subtree_len = slash ? slash - subtree : strlen(subtree);
+	}
+
 	init_tree_desc(&desc, tree->buffer, tree->size);
 
 	while (tree_entry(&desc, &entry)) {
-		if (S_ISDIR(entry.mode))
-			process_tree(revs,
-				     lookup_tree(entry.sha1),
-				     show, &me, entry.path);
+		if (S_ISDIR(entry.mode)) {
+			if (!subtree || !strncmp(entry.path, subtree, subtree_len))
+				process_tree(revs,
+					     lookup_tree(entry.sha1),
+					     show, &me, entry.path,
+					     slash && slash[1] ? slash+1 : NULL);
+		}
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
 					show, &me, entry.path);

@@ -164,7 +175,7 @@ void traverse_commit_list(struct rev_info *revs,
 		}
 		if (obj->type == OBJ_TREE) {
 			process_tree(revs, (struct tree *)obj, show_object,
-				     NULL, name);
+				     NULL, name, core_subtree);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {

@@ -199,7 +199,7 @@ struct object *parse_object(const unsigned char *sha1)
 			return NULL;
 		}
 
-		obj = parse_object_buffer(repl, type, size, buffer, &eaten);
+		obj = parse_object_buffer(sha1, type, size, buffer, &eaten);
 		if (!eaten)
 			free(buffer);
 		return obj;

@@ -315,6 +315,21 @@ int parse_commit(struct commit *item)
 	return ret;
 }
 
+int invalidate_commit(struct commit *item)
+{
+	if (!item)
+		return -1;
+
+	if (item->object.parsed) {
+		item->object.parsed = 0;
+		if (item->buffer) {
+			free(item->buffer);
+			item->buffer = NULL;
+		}
+	}
+	return 0;
+}
+
 struct commit_list *commit_list_insert(struct commit *item, struct commit_list **list_p)
 {
 	struct commit_list *new_list = xmalloc(sizeof(struct commit_list));

@@ -41,6 +41,8 @@ int parse_commit_buffer(struct commit *item, void *buffer, unsigned long size);
 
 int parse_commit(struct commit *item);
 
+int invalidate_commit(struct commit *item);
+
 struct commit_list * commit_list_insert(struct commit *item, struct commit_list **list_p);
 unsigned commit_list_count(const struct commit_list *l);
 struct commit_list * insert_by_date(struct commit *item, struct commit_list **list);

@@ -525,6 +525,7 @@ LIB_H += sigchain.h
 LIB_H += strbuf.h
 LIB_H += string-list.h
 LIB_H += submodule.h
+LIB_H += subtree.h
 LIB_H += tag.h
 LIB_H += transport.h
 LIB_H += tree.h

@@ -629,6 +630,7 @@ LIB_OBJS += sigchain.o
 LIB_OBJS += strbuf.o
 LIB_OBJS += string-list.o
 LIB_OBJS += submodule.o
+LIB_OBJS += subtree.o
 LIB_OBJS += symlinks.o
 LIB_OBJS += tag.o
 LIB_OBJS += trace.o

@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "sha1-lookup.h"
 #include "refs.h"
+#include "subtree.h"
 
 static struct replace_object {
 	unsigned char sha1[2][20];

@@ -82,6 +83,7 @@ static void prepare_replace_object(void)
 	if (replace_object_prepared)
 		return;
 
+	prepare_subtree_commit();
 	for_each_replace_ref(register_replace_ref, NULL);
 	replace_object_prepared = 1;
 }

@@ -99,6 +101,9 @@ const unsigned char *lookup_replace_object(const unsigned char *sha1)
 
 	prepare_replace_object();
 
+	if (core_subtree)
+		cur = subtree_lookup_object(cur);
+
 	/* Try to recursively replace the object */
 	do {
 		if (--depth < 0)

@@ -0,0 +1,117 @@
+#include "cache.h"
+#include "commit.h"
+#include "tree.h"
+#include "diff.h"
+#include "revision.h"
+#include "refs.h"
+#include "tag.h"
+#include "progress.h"
+#include "pack.h"
+#include "sha1-lookup.h"
+#include "csum-file.h"
+
+static struct replace_object {
+	unsigned char sha1[2][20];
+} **subtree_commit;
+
+static struct replace_object **subtree_commit, **subtree_commit_r;
+static int subtree_commit_nr, subtree_commit_r_nr, subtree_commit_alloc;
+
+static const unsigned char *replace_sha1_access(size_t index, void *table)
+{
+	struct replace_object **replace = table;
+	return replace[index]->sha1[0];
+}
+
+static int subtree_replace_object_pos(struct replace_object **store, int nr,
+				      const unsigned char *sha1)
+{
+	return sha1_pos(sha1, store, nr, replace_sha1_access);
+}
+
+static int subtree_register_object(struct replace_object **store,
+					   int *nr,
+					   const unsigned char *sha1,
+					   struct replace_object *replace,
+					   int ignore_dups)
+{
+	int pos = subtree_replace_object_pos(store, *nr, sha1);
+
+	if (0 <= pos) {
+		if (ignore_dups)
+			free(replace);
+		else {
+			free(store[pos]);
+			store[pos] = replace;
+		}
+		return 1;
+	}
+	pos = -pos - 1;
+	(*nr)++;
+	if (pos < *nr)
+		memmove(store + pos + 1,
+			store + pos,
+			(*nr - pos - 1) *
+			sizeof(*store));
+	store[pos] = replace;
+	return 0;
+}
+
+void prepare_subtree_commit()
+{
+	int fd;
+	struct stat stat;
+	struct replace_object *ro;
+	int ro_size, ro_table_size;
+	char *subtree, *entry;
+
+	if (!core_subtree)
+		return;
+
+	fd = open(git_path("subtree"), O_RDONLY);
+	if (fd == -1)
+		return;
+
+	if (fstat(fd, &stat))
+		die("Could not stat .git/subtree");
+
+	if (stat.st_size % 82)
+		die("Invalid .git/subtree size");
+
+	subtree_commit_alloc = stat.st_size / 82;
+	ro_size = sizeof(struct replace_object) * subtree_commit_alloc;
+	ro_table_size = sizeof(struct replace_object*) * subtree_commit_alloc;
+	subtree_commit_nr = 0;
+	subtree_commit_r_nr = 0;
+
+	subtree_commit = xmalloc(ro_size + ro_table_size*2);
+	subtree_commit_r = (struct replace_object **)(((char*)subtree_commit) + ro_table_size);
+	ro = (struct replace_object *)(((char*)subtree_commit) + 2*ro_table_size);
+
+	entry = subtree = xmmap(NULL, stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+
+	for (entry = subtree; subtree_commit_nr < subtree_commit_alloc; entry += 82, ro++) {
+		if (entry[40] != ' ' || entry[81] != '\n')
+			die("Broken .git/subtree");
+
+		get_sha1_hex(entry,    ro->sha1[0]);
+		get_sha1_hex(entry+41, ro->sha1[1]);
+		if (subtree_register_object(subtree_commit, &subtree_commit_nr,
+						    ro->sha1[0], ro, 1) ||
+		    subtree_register_object(subtree_commit_r, &subtree_commit_r_nr,
+						    ro->sha1[1], ro, 1))
+			die("duplicate replace ref: %s", sha1_to_hex(ro->sha1[0]));
+	}
+	munmap(subtree, stat.st_size);
+	close(fd);
+}
+
+const unsigned char *subtree_lookup_object(const unsigned char *sha1)
+{
+	int pos = subtree_replace_object_pos(subtree_commit,
+					     subtree_commit_nr,
+					     sha1);
+	if (0 <= pos)
+		return subtree_commit[pos]->sha1[1];
+	return sha1;
+}

@@ -0,0 +1,2 @@
+void prepare_subtree_commit();
+const unsigned char *subtree_lookup_object(const unsigned char *sha1);

@@ -160,8 +160,9 @@ static void create_pack_file(void)
 	ssize_t sz;
 	const char *argv[10];
 	int arg = 0;
+	int internal_rev_list = shallow_nr;
 
-	if (shallow_nr) {
+	if (internal_rev_list) {
 		memset(&rev_list, 0, sizeof(rev_list));
 		rev_list.proc = do_rev_list;
 		rev_list.out = -1;

@@ -187,7 +188,7 @@ static void create_pack_file(void)
 	argv[arg++] = NULL;
 
 	memset(&pack_objects, 0, sizeof(pack_objects));
-	pack_objects.in = shallow_nr ? rev_list.out : -1;
+	pack_objects.in = internal_rev_list ? rev_list.out : -1;
 	pack_objects.out = -1;
 	pack_objects.err = -1;
 	pack_objects.git_cmd = 1;

@@ -197,7 +198,7 @@ static void create_pack_file(void)
 		die("git upload-pack: unable to fork git-pack-objects");
 
 	/* pass on revisions we (don't) want */
-	if (!shallow_nr) {
+	if (!internal_rev_list) {
 		FILE *pipe_fd = xfdopen(pack_objects.in, "w");
 		if (!create_full_pack) {
 			int i;

@@ -311,7 +312,7 @@ static void create_pack_file(void)
 		error("git upload-pack: git-pack-objects died with error.");
 		goto fail;
 	}
-	if (shallow_nr && finish_async(&rev_list))
+	if (internal_rev_list && finish_async(&rev_list))
 		goto fail;	/* error was already reported */
 
 	/* flush the data */

@@ -160,7 +160,7 @@ static void create_pack_file(void)
 	ssize_t sz;
 	const char *argv[10];
 	int arg = 0;
-	int internal_rev_list = shallow_nr;
+	int internal_rev_list = shallow_nr || core_subtree;
 
 	if (internal_rev_list) {
 		memset(&rev_list, 0, sizeof(rev_list));

@@ -505,6 +505,20 @@ static void receive_needs(void)
 		if (debug_fd)
 			write_in_full(debug_fd, line, len);
 
+		if (!prefixcmp(line, "subtree ")) {
+			int len;
+			char *subtree;
+			if (core_subtree)
+				die("sorry, only one subtree supported");
+			len = strlen(line+8);
+			subtree = malloc(len+1);
+			memcpy(subtree, line+8, len-1);
+			subtree[len-1] = '\0'; /* \n */
+			if (subtree[len-2] != '/')
+				die("subtree request must end with a slash");
+			core_subtree = subtree;
+			continue;
+		}
 		if (!prefixcmp(line, "shallow ")) {
 			unsigned char sha1[20];
 			struct object *object;

@@ -624,7 +638,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo
 {
 	static const char *capabilities = "multi_ack thin-pack side-band"
 		" side-band-64k ofs-delta shallow no-progress"
-		" include-tag multi_ack_detailed";
+		" include-tag multi_ack_detailed subtree";
 	struct object *o = parse_object(sha1);
 
 	if (!o)

@@ -237,6 +237,8 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 	for_each_ref(rev_list_insert_ref, NULL);
 
 	fetching = 0;
+	if (core_subtree)
+		packet_buf_write(&req_buf, "subtree %s\n", core_subtree);
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
 		const char *remote_hex;

@@ -692,6 +694,8 @@ static struct ref *do_fetch_pack(int fd[2],
 
 	if (is_repository_shallow() && !server_supports("shallow"))
 		die("Server does not support shallow clients");
+	if (core_subtree && !server_supports("subtree"))
+		die("Server does not support subtree");
 	if (server_supports("multi_ack_detailed")) {
 		if (args.verbose)
 			fprintf(stderr, "Server supports multi_ack_detailed\n");

@@ -860,6 +864,10 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 				pack_lockfile_ptr = &pack_lockfile;
 				continue;
 			}
+			if (!prefixcmp(arg, "--subtree=")) {
+				core_subtree = arg + 10;
+				continue;
+			}
 			usage(fetch_pack_usage);
 		}
 		dest = (char *)arg;

@@ -115,3 +115,247 @@ const unsigned char *subtree_lookup_object(const unsigned char *sha1)
 		return subtree_commit[pos]->sha1[1];
 	return sha1;
 }
+
+static unsigned long do_compress(void **pptr, unsigned long size)
+{
+	z_stream stream;
+	void *in, *out;
+	unsigned long maxsize;
+
+	memset(&stream, 0, sizeof(stream));
+	deflateInit(&stream, Z_DEFAULT_COMPRESSION);
+	maxsize = deflateBound(&stream, size);
+
+	in = *pptr;
+	out = xmalloc(maxsize);
+	*pptr = out;
+
+	stream.next_in = in;
+	stream.avail_in = size;
+	stream.next_out = out;
+	stream.avail_out = maxsize;
+	while (deflate(&stream, Z_FINISH) == Z_OK)
+		; /* nothing */
+	deflateEnd(&stream);
+
+	return stream.total_out;
+}
+
+static int nr_written;
+static int add_sha1_to_pack(int fd, void *buf, unsigned long size, enum object_type type)
+{
+	unsigned long datalen;
+	unsigned hdrlen;
+	unsigned char header[10];
+
+	datalen = do_compress(&buf, size);
+	hdrlen = encode_in_pack_object_header(type, size, header);
+	write(fd, header, hdrlen);
+	write(fd, buf, datalen);
+	nr_written++;
+	free(buf);
+	return 0;
+}
+
+/*
+ * Take sha1 of a tree, rewrite it to only return the prefix and return
+ * the newsha1.
+ *
+ * If if is zero, write to object store. If fd is greater than zero,
+ * it's a pack file handle.
+ */
+static int narrow_tree(const unsigned char *sha1, unsigned char *newsha1,
+		       const char *prefix, int fd)
+{
+	struct tree_desc desc;
+	struct name_entry entry;
+	struct strbuf buffer;
+	const char *slash;
+	int subtree_len;
+	enum object_type type;
+	unsigned long size;
+	char *tree;
+	struct object *obj;
+
+	slash = strchr(prefix, '/');
+	subtree_len = slash ? slash - prefix : strlen(prefix);
+
+	tree = read_sha1_file(sha1, &type, &size);
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(sha1));
+
+	init_tree_desc(&desc, tree, size);
+	strbuf_init(&buffer, 1024);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+
+		if (subtree_len == strlen(entry.path) &&
+		    !strncmp(entry.path, prefix, subtree_len)) {
+			unsigned char newtree_sha1[20];
+
+			if (slash && slash[1]) /* trailing slash does not count */
+				narrow_tree(entry.sha1, newtree_sha1, prefix+subtree_len+1, fd);
+			else
+				memcpy(newtree_sha1, entry.sha1, 20);
+
+			strbuf_addf(&buffer, "%o %.*s%c", entry.mode, strlen(entry.path), entry.path, '\0');
+			strbuf_add(&buffer, newtree_sha1, 20);
+			break;
+		}
+	}
+	free(tree);
+
+	if (fd == 0) {
+		if (write_sha1_file(buffer.buf, buffer.len, tree_type, newsha1)) {
+			error("Could not write replaced tree for %s", sha1_to_hex(sha1));
+			strbuf_release(&buffer);
+			return 1;
+		}
+		strbuf_release(&buffer);
+		return 0;
+	}
+
+	hash_sha1_file(buffer.buf, buffer.len, tree_type, newsha1);
+	obj = (struct object *)lookup_tree(newsha1);
+	if (fd > 0 &&
+	    !(obj->flags & SEEN) &&
+	    add_sha1_to_pack(fd, buffer.buf, buffer.len, OBJ_TREE)) {
+		error("Could not write replaced tree for %s", sha1_to_hex(sha1));
+		strbuf_release(&buffer);
+		return 1;
+	}
+	obj->flags |= SEEN;
+
+	strbuf_release(&buffer);
+	return 0;
+}
+
+/*
+ * Take sha1 of a commit, rewrite its tree using narrow_tree(), then
+ * add a replace entry to file pointer fp (which is $GIT_DIR/subtree).
+ *
+ * Also update replace-object database so that the given sha1 can be
+ * replaced with the new one right after this function returns.
+ */
+static int shadow_commit(const unsigned char *sha1, const char *prefix, int fd, FILE *fp)
+{
+	unsigned char newsha1[20], treesha1[20];
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+	struct object *obj;
+	int saved_read_replace_refs = read_replace_refs;
+
+	read_replace_refs = 0;
+	buffer = read_sha1_file(sha1, &type, &size);
+	read_replace_refs = saved_read_replace_refs;
+	get_sha1_hex(buffer+5, treesha1);
+
+	if (!buffer || type != OBJ_COMMIT ||
+	    narrow_tree(treesha1, newsha1, prefix, fd)) {
+		free(buffer);
+		error("Failed to narrow tree for commit %s", sha1_to_hex(sha1));
+		return 1;
+	}
+
+	/* replace new tree in */
+	memcpy((char*)buffer+5, sha1_to_hex(newsha1), 40);
+
+	if (fd == 0) {
+		if (write_sha1_file(buffer, size, commit_type, newsha1)) {
+			free(buffer);
+			error("Could not write replaced commit for %s", sha1_to_hex(sha1));
+			return 1;
+		}
+	}
+	else {
+		hash_sha1_file(buffer, size, commit_type, newsha1);
+		obj = (struct object *)lookup_commit(newsha1);
+		if (fd > 0 &&
+		    !(obj->flags & SEEN) &&
+		    add_sha1_to_pack(fd, buffer, size, OBJ_COMMIT)) {
+			free(buffer);
+			error("Could not write replaced commit for %s", sha1_to_hex(sha1));
+			return 1;
+		}
+		obj->flags |= SEEN;
+	}
+
+	if (fp) {
+		char buf[82];
+		memcpy(buf, sha1_to_hex(sha1), 40);
+		buf[40] = ' ';
+		memcpy(buf+41, sha1_to_hex(newsha1), 40);
+		buf[81] = '\n';
+		fwrite(buf, 82, 1, fp);
+	}
+	free(buffer);
+
+	return 0;
+}
+
+/*
+ * Rewrite all reachable commits in repo using shadow_commit().
+ * Write out the pack that contains new tree/commit objects.
+ */
+void subtree_import()
+{
+	const char *args[] = {"rev-list", "--all", NULL};
+	struct pack_header hdr;
+	struct progress *ps;
+	struct rev_info revs;
+	struct commit *c;
+	unsigned char sha1[20];
+	unsigned commit_nr = 0;
+	char *pack_tmp_name;
+	char tmpname[PATH_MAX];
+	int pack_fd, i;
+	FILE *fp;
+	char cmd[1024];
+
+	/* Packing */
+	init_revisions(&revs, NULL);
+	setup_revisions(2, args, &revs, NULL);
+	if (prepare_revision_walk(&revs))
+		die("revision walk setup failed");
+	fp = fopen(git_path("subtree"), "w+");
+
+	pack_fd = odb_mkstemp(tmpname, sizeof(tmpname), "pack/tmp_pack_XXXXXX");
+	pack_tmp_name = xstrdup(tmpname);
+
+	hdr.hdr_signature = htonl(PACK_SIGNATURE);
+	hdr.hdr_version = htonl(PACK_VERSION);
+	hdr.hdr_entries = htonl(0);
+	write(pack_fd, &hdr, sizeof(hdr));
+
+	ps = start_progress("Preparing subtree commits", 0);
+	while ((c = get_revision(&revs)) != NULL) {
+		if (shadow_commit(c->object.sha1, core_subtree, pack_fd, fp))
+			die("Failed to shadow commit %s", c->object.sha1);
+		display_progress(ps, ++commit_nr);
+	}
+	stop_progress(&ps);
+	fclose(fp);
+	fixup_pack_header_footer(pack_fd, sha1, pack_tmp_name, nr_written, NULL, 0);
+	close(pack_fd);
+	sprintf(cmd, "git index-pack --stdin < %s", pack_tmp_name);
+	system(cmd);
+	unlink(pack_tmp_name);
+
+	reprepare_packed_git();
+	if (subtree_commit)
+		free(subtree_commit);
+	prepare_subtree_commit();
+
+	/* Invalidate all replaced commits */
+	for (i = 0; i < subtree_commit_nr; i++) {
+		/* lookup_commit() would create new objects, we don't want that */
+		c = (struct commit *)lookup_object(subtree_commit[i]->sha1[0]);
+		if (c)
+			invalidate_commit(c);
+	}
+
+	if (revs.pending.nr)
+		free(revs.pending.objects);
+}

@@ -1,2 +1,3 @@
 void prepare_subtree_commit();
 const unsigned char *subtree_lookup_object(const unsigned char *sha1);
+void subtree_import();

@@ -23,6 +23,7 @@
 #include "branch.h"
 #include "remote.h"
 #include "run-command.h"
+#include "subtree.h"
 
 /*
  * Overall FIXMEs:

@@ -78,6 +79,8 @@ static struct option builtin_clone_options[] = {
 		   "path to git-upload-pack on the remote"),
 	OPT_STRING(0, "depth", &option_depth, "depth",
 		    "create a shallow clone of that depth"),
+	OPT_STRING(0, "subtree", &core_subtree, "subtree",
+		   "subtree clone"),
 
 	OPT_END()
 };

@@ -515,6 +518,8 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	strbuf_reset(&value);
 
 	if (path && !is_bundle) {
+		if (core_subtree)
+			die("Local subtree clone does not work (now)");
 		refs = clone_local(path, git_dir);
 		mapped_refs = wanted_peer_refs(refs, refspec);
 	} else {

@@ -623,6 +628,11 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		transport_disconnect(transport);
 	}
 
+	if (core_subtree) {
+		git_config_set("core.subtree", core_subtree);
+		subtree_import();
+	}
+
 	if (!option_no_checkout) {
 		struct lock_file *lock_file = xcalloc(1, sizeof(struct lock_file));
 		struct unpack_trees_options opts;

@@ -2277,6 +2277,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			grafts_replace_parents = 0;
 			continue;
 		}
+		if (!prefixcmp(arg, "--subtree=")) {
+			core_subtree = arg + 10;
+			continue;
+		}
 		usage(pack_usage);
 	}
 

@@ -359,3 +359,176 @@ void subtree_import()
 	if (revs.pending.nr)
 		free(revs.pending.objects);
 }
+
+/*
+ * The opposite of narrow_tree(). Put the subtree back to the original tree.
+ */
+static int widen_tree(const unsigned char *sha1,
+		      unsigned char *newsha1,
+		      const unsigned char *subtree_sha1,
+		      const char *prefix)
+{
+	struct tree_desc desc;
+	struct name_entry entry;
+	struct strbuf buffer;
+	const char *slash;
+	int subtree_len;
+	enum object_type type;
+	unsigned long size;
+	char *tree;
+
+	slash = strchr(prefix, '/');
+	subtree_len = slash ? slash - prefix : strlen(prefix);
+
+	tree = read_sha1_file(sha1, &type, &size);
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(sha1));
+
+	init_tree_desc(&desc, tree, size);
+	strbuf_init(&buffer, 8192);
+	while (tree_entry(&desc, &entry)) {
+		strbuf_addf(&buffer, "%o %.*s%c", entry.mode, strlen(entry.path), entry.path, '\0');
+
+		if (S_ISDIR(entry.mode) &&
+		    subtree_len == strlen(entry.path) &&
+		    !strncmp(entry.path, prefix, subtree_len)) {
+			unsigned char newtree_sha1[20];
+
+			if (slash && slash[1]) /* trailing slash does not count */
+				widen_tree(entry.sha1, newtree_sha1, subtree_sha1,
+					   prefix+subtree_len+1);
+			else
+				/* replace the tree */
+				memcpy(newtree_sha1, subtree_sha1, 20);
+
+			strbuf_add(&buffer, newtree_sha1, 20);
+		}
+		else
+			strbuf_add(&buffer, entry.sha1, 20);
+	}
+	free(tree);
+
+	if (write_sha1_file(buffer.buf, buffer.len, tree_type, newsha1)) {
+		error("Could not write replaced tree for %s", sha1_to_hex(sha1));
+		strbuf_release(&buffer);
+		return 1;
+	}
+	strbuf_release(&buffer);
+	return 0;
+}
+
+static int find_subtree(const unsigned char *sha1, unsigned char *newsha1, const char *prefix)
+{
+	struct tree_desc desc;
+	struct name_entry entry;
+	const char *slash;
+	enum object_type type;
+	unsigned long size;
+	int subtree_len;
+	char *tree;
+
+	slash = strchr(prefix, '/');
+	subtree_len = slash ? slash - prefix : strlen(prefix);
+
+	tree = read_sha1_file(sha1, &type, &size);
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(sha1));
+
+	init_tree_desc(&desc, tree, size);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+
+		if (subtree_len == strlen(entry.path) &&
+		    !strncmp(entry.path, prefix, subtree_len)) {
+
+			if (slash && slash[1]) { /* trailing slash does not count */
+				if (find_subtree(entry.sha1, newsha1, prefix+subtree_len+1))
+					return 1;
+			}
+			else
+				memcpy(newsha1, entry.sha1, 20);
+			free(tree);
+			return 0;
+		}
+	}
+	free(tree);
+
+	return 1;
+}
+
+/* The opposite of shadow_commit() */
+static int expose_commit(const unsigned char *sha1, unsigned char *newsha1,
+			 const unsigned char *basesha1,
+			 const char *prefix, FILE *fp)
+{
+	unsigned char treesha1[20], subtree_sha1[20];
+	enum object_type type;
+	unsigned long size, base_size;
+	void *base_buffer, *buffer;
+	int saved_read_replace_refs = read_replace_refs;
+
+	/* Get subtree from the new commit, sha1 */
+	read_replace_refs = 0;
+	buffer = read_sha1_file(sha1, &type, &size);
+	read_replace_refs = saved_read_replace_refs;
+	get_sha1_hex(buffer+5, treesha1);
+
+	if (!buffer || type != OBJ_COMMIT ||
+	    find_subtree(treesha1, subtree_sha1, prefix)) {
+		free(buffer);
+		error("Failed to find subtree tree in base commit %s", sha1_to_hex(sha1));
+		return 1;
+	}
+
+	/* Get the old base tree from basesha1 */
+	read_replace_refs = 0;
+	base_buffer = read_sha1_file(basesha1, &type, &base_size);
+	read_replace_refs = saved_read_replace_refs;
+	get_sha1_hex(base_buffer+5, treesha1);
+
+	if (!buffer || type != OBJ_COMMIT ||
+	    widen_tree(treesha1, newsha1, subtree_sha1, prefix)) {
+		free(buffer);
+		error("Failed to widen tree for commit %s", sha1_to_hex(sha1));
+		return 1;
+	}
+	free(base_buffer);
+
+	/* replace new tree in */
+	memcpy((char*)buffer+5, sha1_to_hex(newsha1), 40);
+
+	if (write_sha1_file(buffer, size, commit_type, newsha1)) {
+		free(buffer);
+		error("Could not write replaced commit for %s", sha1_to_hex(sha1));
+		return 1;
+	}
+
+	if (fp) {
+		char buf[82];
+		memcpy(buf, sha1_to_hex(newsha1), 40);
+		buf[40] = ' ';
+		memcpy(buf+41, sha1_to_hex(sha1), 40);
+		buf[81] = '\n';
+		fwrite(buf, 82, 1, fp);
+	}
+	free(buffer);
+
+	return 0;
+}
+
+int subtree_export(unsigned char *sha1, unsigned char *basesha1, unsigned char *newsha1)
+{
+	FILE *fp;
+
+	fp = fopen(git_path("subtree"), "a+");
+	if (expose_commit(sha1, newsha1, basesha1, core_subtree, fp))
+		die("Failed to rewrite commit %s", sha1_to_hex(sha1));
+	fclose(fp);
+
+	if (subtree_commit)
+		free(subtree_commit);
+	prepare_subtree_commit();
+
+	return 0;
+}