[RFD PATCH 00/32] subtree clone v2

[RFD PATCH 00/32] subtree clone v2

[Nguyễn Thái Ngọc Duy]

This is a follow-up from the subtree clone proof of concept [1] I
posted a few weeks ago. I think it's getting closer to an acceptable
design. Hence the purpose of this post: to ask for opinions about the
design issues I'm facing.

The good news is that tree rewrite/replace has gone. The repo now is
perfectly "normal". Git client has to be modified to live peacefully
within a narrow tree. How much modification is still a question ahead.

Other things from the previous series are pretty much unchanged:
single narrow tree, only send necessary trees, can be used together
with shallow clone, can't be fetch source.

A new thing is the index is now narrowed down, because I don't have
all trees to fully populate it, and tree rewrite mechanism is now
gone. One item for RFD.

Another major thing (you guys are going to hate me) is merge could not
always be done locally. So I introduce "trivial 3-way remote
merge". RFD material (any other aproaches?). More details in commit
messages.

Is there any other full-tree operations, like merge, that I should pay
attention to? What commands can be troublesome?

Last note, please don't look too closely. The code is full of bugs :-)


Patches 1..7
  add const to ce_write()
  cache-tree: abstract out write_sha1_file from cache_tree_update()
  cache-tree: ignore CE_REMOVE entries in verify_cache()
  move do_compress() from pack-objects.c to pack-write.c
  pack-write: add functions for creating simple packs
  tree.c: Add {set,clear}_tree_marks
  tree.c: find_subtree() to search for a tree

Helper patches. You can skip these if you are only interested in the
narrow ideas.


Patches 8..14
  Add $GIT_DIR/narrow check
  index: make narrow index incompatible with older git
  rev-list: support traversing in narrow repository mode
  rev-list: support --narrow-tree
  pack-objects: support --narrow-tree
  upload-pack: support narrow-tree capability
  fetch-pack: support --narrow-tree

Narrow clone. traverse_commit_list() does not change much since the
last series.


Patches 15..19
  unpack_trees: only unpack $GIT_DIR/narrow subtree in narrow
    repository
  cache-tree: only cache tree within narrow area
  tree-diff: add narrow versions of diff_{root_,}tree_sha1
  log-tree: use narrow version of diff_tree_sha1
  clone: support --narrow option

Client support so that you can check files out, diff them... This is WIP.
Basically if you stay inside narrow tree, you'd be safe :-) Elijah may
want to reuse some of these code in his sparse clone, if he can extend
it to support multiple narrow trees, I think.


Patches 20..25
  narrow-tree: add join_narrow_tree to do tree fixup for commits
  commit: add narrow's commit_tree version
  commit: use commit_narrow_tree() to support narrow repo
  commit-tree: require --narrow-base in narrow repo
  merge: refuse to merge if narrow bases are different
  merge: prepare commit properly in narrow mode

Commit part, how to use narrow index and make proper commits. This is
where merge issue arises. Because a merge can have many parents, which
parent can be used as a base to create new commits?


Patches 26..30
  Add upload-narrow-base command
  rev-list: traverse some more trees to make upload-narrow-base happy
  narrow-tree: add oldest_narrow_base()
  Add command fetch-narrow-base
  merge: support merging when narrow bases are different

Remote merge part.

Split a merge operation into two parts, the real merge will be done
within narrow tree. Conflicts can happen and be resolved in the narrow
index, locally.

Everything outside narrow tree will be merged (trivially) by
server. Then server sends the base tree back, so join_narrow_tree() in
patch 20 can be used to create proper commit.

Server can disable this remote merge feature, which means users are
forced to do rebase/fast-forward. Not too bad.


Patches 31..32
  send-pack: do not use thin pack in narrow mode
  daemon: support upload-narrow-base

Misc stuff..

[1] http://mid.gmane.org/1280593105-22015-1-git-send-email-pclouds@gmail.com

 Makefile                     |    4 +
 builtin.h                    |    2 +
 builtin/clone.c              |   15 +++-
 builtin/commit-tree.c        |   20 ++++-
 builtin/commit.c             |   10 ++-
 builtin/fetch-narrow-base.c  |   89 +++++++++++++++++
 builtin/fetch-pack.c         |   11 ++
 builtin/merge.c              |   45 +++++++++-
 builtin/pack-objects.c       |   33 +++----
 builtin/send-pack.c          |    4 +
 builtin/upload-narrow-base.c |  215 ++++++++++++++++++++++++++++++++++++++++++
 cache-tree.c                 |   37 ++++++--
 cache-tree.h                 |    3 +
 cache.h                      |    4 +
 commit.c                     |   21 ++++
 commit.h                     |    5 +
 daemon.c                     |    7 ++
 diff.h                       |    5 +
 environment.c                |    2 +
 git.c                        |    2 +
 list-objects.c               |   91 +++++++++++++++++-
 log-tree.c                   |   23 ++++-
 narrow-tree.c                |  200 +++++++++++++++++++++++++++++++++++++++
 narrow-tree.h                |    9 ++
 pack-write.c                 |  112 ++++++++++++++++++++++
 pack.h                       |   18 ++++
 read-cache.c                 |   37 ++++++-
 revision.c                   |    5 +
 revision.h                   |    4 +-
 t/t1013-read-tree-narrow.sh  |   72 ++++++++++++++
 t/t6060-narrow-tree.sh       |   28 ++++++
 t/t6061-rev-list-narrow.sh   |  185 ++++++++++++++++++++++++++++++++++++
 tree-diff.c                  |   74 ++++++++++++++
 tree.c                       |   79 +++++++++++++++
 tree.h                       |    4 +
 unpack-trees.c               |   70 ++++++++++++++-
 upload-pack.c                |   31 ++++++-
 37 files changed, 1528 insertions(+), 48 deletions(-)
 create mode 100644 builtin/fetch-narrow-base.c
 create mode 100644 builtin/upload-narrow-base.c
 create mode 100644 narrow-tree.c
 create mode 100644 narrow-tree.h
 create mode 100755 t/t1013-read-tree-narrow.sh
 create mode 100755 t/t6060-narrow-tree.sh
 create mode 100755 t/t6061-rev-list-narrow.sh

[PATCH 01/32] add const to ce_write()

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 read-cache.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/read-cache.c b/read-cache.c
index 1f42473..881dd93 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1409,7 +1409,7 @@ static int ce_write_flush(git_SHA_CTX *context, int fd)
 	return 0;
 }
 
-static int ce_write(git_SHA_CTX *context, int fd, void *data, unsigned int len)
+static int ce_write(git_SHA_CTX *context, int fd, const void *data, unsigned int len)
 {
 	while (len) {
 		unsigned int buffered = write_buffer_len;
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 02/32] cache-tree: abstract out write_sha1_file from cache_tree_update()

[Nguyễn Thái Ngọc Duy]

This allows cache-tree to produce trees directly in a pack, for instance.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache-tree.c |   18 +++++++++++++++---
 cache-tree.h |    3 +++
 2 files changed, 18 insertions(+), 3 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index c60cf91..7fd7203 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -237,6 +237,7 @@ static int update_one(struct cache_tree *it,
 		      int entries,
 		      const char *base,
 		      int baselen,
+		      write_tree_fn write_tree,
 		      int missing_ok,
 		      int dryrun)
 {
@@ -284,6 +285,7 @@ static int update_one(struct cache_tree *it,
 				    cache + i, entries - i,
 				    path,
 				    baselen + sublen + 1,
+				    write_tree,
 				    missing_ok,
 				    dryrun);
 		if (subcnt < 0)
@@ -349,7 +351,7 @@ static int update_one(struct cache_tree *it,
 
 	if (dryrun)
 		hash_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1);
-	else if (write_sha1_file(buffer.buf, buffer.len, tree_type, it->sha1)) {
+	else if (write_tree(buffer.buf, buffer.len, tree_type, it->sha1)) {
 		strbuf_release(&buffer);
 		return -1;
 	}
@@ -364,9 +366,10 @@ static int update_one(struct cache_tree *it,
 	return i;
 }
 
-int cache_tree_update(struct cache_tree *it,
+int cache_tree_update_fn(struct cache_tree *it,
 		      struct cache_entry **cache,
 		      int entries,
+		      write_tree_fn write_tree,
 		      int missing_ok,
 		      int dryrun)
 {
@@ -374,12 +377,21 @@ int cache_tree_update(struct cache_tree *it,
 	i = verify_cache(cache, entries);
 	if (i)
 		return i;
-	i = update_one(it, cache, entries, "", 0, missing_ok, dryrun);
+	i = update_one(it, cache, entries, "", 0, write_tree, missing_ok, dryrun);
 	if (i < 0)
 		return i;
 	return 0;
 }
 
+int cache_tree_update(struct cache_tree *it,
+		      struct cache_entry **cache,
+		      int entries,
+		      int missing_ok,
+		      int dryrun)
+{
+	return cache_tree_update_fn(it, cache, entries, write_sha1_file, missing_ok, dryrun);
+}
+
 static void write_one(struct strbuf *buffer, struct cache_tree *it,
                       const char *path, int pathlen)
 {
diff --git a/cache-tree.h b/cache-tree.h
index 3df641f..b32ae41 100644
--- a/cache-tree.h
+++ b/cache-tree.h
@@ -20,6 +20,8 @@ struct cache_tree {
 	struct cache_tree_sub **down;
 };
 
+typedef int (*write_tree_fn)(const void *, unsigned long, const char *, unsigned char *);
+
 struct cache_tree *cache_tree(void);
 void cache_tree_free(struct cache_tree **);
 void cache_tree_invalidate_path(struct cache_tree *, const char *);
@@ -29,6 +31,7 @@ void cache_tree_write(struct strbuf *, struct cache_tree *root);
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);
 
 int cache_tree_fully_valid(struct cache_tree *);
+int cache_tree_update_fn(struct cache_tree *, struct cache_entry **, int, write_tree_fn, int, int);
 int cache_tree_update(struct cache_tree *, struct cache_entry **, int, int, int);
 
 /* bitmasks to write_cache_as_tree flags */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 03/32] cache-tree: ignore CE_REMOVE entries in verify_cache()

[Nguyễn Thái Ngọc Duy]

Those entries are not to be written out. MAY HAVE NEGATIVE IMPACT!!

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache-tree.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 7fd7203..03952c7 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
 	funny = 0;
 	for (i = 0; i < entries; i++) {
 		struct cache_entry *ce = cache[i];
+		if (ce->ce_flags & CE_REMOVE)
+			continue;
 		if (ce_stage(ce) || (ce->ce_flags & CE_INTENT_TO_ADD)) {
 			if (10 < ++funny) {
 				fprintf(stderr, "...\n");
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 04/32] move do_compress() from pack-objects.c to pack-write.c

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/pack-objects.c |   24 +++---------------------
 pack-write.c           |   25 +++++++++++++++++++++++++
 pack.h                 |    1 +
 3 files changed, 29 insertions(+), 21 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 0e81673..a664223 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -130,28 +130,10 @@ static void *get_delta(struct object_entry *entry)
 
 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, pack_compression_level);
-	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);
-
+	void **in = *pptr;
+	unsigned total_out = compress_object(pptr, size);
 	free(in);
-	return stream.total_out;
+	return total_out;
 }
 
 /*
diff --git a/pack-write.c b/pack-write.c
index a905ca4..cc7761e 100644
--- a/pack-write.c
+++ b/pack-write.c
@@ -280,3 +280,28 @@ int encode_in_pack_object_header(enum object_type type, uintmax_t size, unsigned
 	*hdr = c;
 	return n;
 }
+
+unsigned long compress_object(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;
+}
diff --git a/pack.h b/pack.h
index bb27576..28a966b 100644
--- a/pack.h
+++ b/pack.h
@@ -62,6 +62,7 @@ extern int verify_pack(struct packed_git *);
 extern void fixup_pack_header_footer(int, unsigned char *, const char *, uint32_t, unsigned char *, off_t);
 extern char *index_pack_lockfile(int fd);
 extern int encode_in_pack_object_header(enum object_type, uintmax_t, unsigned char *);
+extern unsigned long compress_object(void **, unsigned long size);
 
 #define PH_ERROR_EOF		(-1)
 #define PH_ERROR_PACK_SIGNATURE	(-2)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 05/32] pack-write: add functions for creating simple packs

[Nguyễn Thái Ngọc Duy]

These are ripoffs from pack-objects and do not do deltas at all.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 pack-write.c |   87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 pack.h       |   17 +++++++++++
 2 files changed, 104 insertions(+), 0 deletions(-)

diff --git a/pack-write.c b/pack-write.c
index cc7761e..2b71bd2 100644
--- a/pack-write.c
+++ b/pack-write.c
@@ -305,3 +305,90 @@ unsigned long compress_object(void **pptr, unsigned long size)
 
 	return stream.total_out;
 }
+
+int create_pack(struct simple_pack *pack)
+{
+	char tmpname[PATH_MAX];
+	struct pack_header hdr;
+
+	if (pack->fd <= 0) {
+		pack->fd = odb_mkstemp(tmpname, sizeof(tmpname), "pack/tmp_pack_XXXXXX");
+		pack->pack_tmp_name = xstrdup(tmpname);
+	}
+	pack->f = sha1fd(pack->fd, pack->pack_tmp_name ? pack->pack_tmp_name : "<unknown>");
+
+	if (pack->nr_objects) {
+		int pointer_size = sizeof(struct pack_idx_entry*) * pack->nr_objects;
+		int item_size = sizeof(struct pack_idx_entry) * pack->nr_objects;
+		void *buf = xmalloc(item_size + pointer_size);
+		pack->written_list = buf;
+		pack->written_items = (void*)(((char*)buf) + pointer_size);
+	}
+
+	hdr.hdr_signature = htonl(PACK_SIGNATURE);
+	hdr.hdr_version = htonl(PACK_VERSION);
+	hdr.hdr_entries = htonl(pack->nr_objects);
+	sha1write(pack->f, &hdr, sizeof(hdr));
+	if (pack->written_list)
+		pack->offset = sizeof(hdr);
+
+	return 0;
+}
+
+int write_object_to_pack(struct simple_pack *pack,
+			 const unsigned char *sha1,
+			 void *buf,
+			 unsigned long size,
+			 enum object_type type)
+{
+	unsigned long datalen;
+	unsigned hdrlen;
+	unsigned char header[10];
+
+	datalen = compress_object(&buf, size);
+	hdrlen = encode_in_pack_object_header(type, size, header);
+	if (pack->written_list)
+		crc32_begin(pack->f);
+	sha1write(pack->f, header, hdrlen);
+	sha1write(pack->f, buf, datalen);
+	free(buf);
+
+	if (pack->written_list) {
+		struct pack_idx_entry *e;
+
+		e = pack->written_list[pack->nr_written] = pack->written_items;
+		e->crc32 = crc32_end(pack->f);
+		hashcpy(e->sha1, sha1);
+		e->offset = pack->offset;
+		pack->offset += datalen+hdrlen;
+	}
+	pack->nr_written++;
+	pack->written_items++;
+
+	return 0;
+}
+
+int close_pack(struct simple_pack *pack)
+{
+	sha1close(pack->f, pack->sha1, CSUM_CLOSE);
+	if (pack->written_list) {
+		char tmpname[PATH_MAX];
+		const char *idx_tmp_name;
+
+		idx_tmp_name = write_idx_file(NULL, pack->written_list, pack->nr_written, pack->sha1);
+
+		snprintf(tmpname, sizeof(tmpname), "%s/pack/pack-%s.pack", get_object_directory(), sha1_to_hex(pack->sha1));
+		free_pack_by_name(tmpname);
+		if (adjust_shared_perm(pack->pack_tmp_name))
+			die_errno("unable to make temporary pack file readable");
+		if (rename(pack->pack_tmp_name, tmpname))
+			die_errno("unable to rename temporary pack file");
+		snprintf(tmpname, sizeof(tmpname), "%s/pack/pack-%s.idx", get_object_directory(), sha1_to_hex(pack->sha1));
+		if (rename(idx_tmp_name, tmpname))
+			die_errno("unable to rename temporary pack file");
+		free(pack->written_list);
+	}
+	if (pack->pack_tmp_name)
+		free(pack->pack_tmp_name);
+	return 0;
+}
diff --git a/pack.h b/pack.h
index 28a966b..a2e32c7 100644
--- a/pack.h
+++ b/pack.h
@@ -55,6 +55,19 @@ struct pack_idx_entry {
 	off_t offset;
 };
 
+struct simple_pack {
+	uint32_t nr_objects;
+	unsigned char sha1[20];
+
+	int fd;
+	struct sha1file *f;
+	uint32_t nr_written;
+	off_t offset;
+	char *pack_tmp_name;
+	struct pack_idx_entry **written_list;
+	struct pack_idx_entry *written_items;
+};
+
 extern const char *write_idx_file(const char *index_name, struct pack_idx_entry **objects, int nr_objects, unsigned char *sha1);
 extern int check_pack_crc(struct packed_git *p, struct pack_window **w_curs, off_t offset, off_t len, unsigned int nr);
 extern int verify_pack_index(struct packed_git *);
@@ -64,6 +77,10 @@ extern char *index_pack_lockfile(int fd);
 extern int encode_in_pack_object_header(enum object_type, uintmax_t, unsigned char *);
 extern unsigned long compress_object(void **, unsigned long size);
 
+extern int create_pack(struct simple_pack *);
+extern int write_object_to_pack(struct simple_pack *, const unsigned char *, void *, unsigned long, enum object_type);
+extern int close_pack(struct simple_pack *);
+
 #define PH_ERROR_EOF		(-1)
 #define PH_ERROR_PACK_SIGNATURE	(-2)
 #define PH_ERROR_PROTOCOL	(-3)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 06/32] tree.c: Add {set,clear}_tree_marks

[Nguyễn Thái Ngọc Duy]

These function traverse the given tree and set/clear object.flags

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 tree.c |   44 ++++++++++++++++++++++++++++++++++++++++++++
 tree.h |    3 +++
 2 files changed, 47 insertions(+), 0 deletions(-)

diff --git a/tree.c b/tree.c
index 5ab90af..434bf56 100644
--- a/tree.c
+++ b/tree.c
@@ -284,3 +284,47 @@ struct tree *parse_tree_indirect(const unsigned char *sha1)
 			parse_object(obj->sha1);
 	} while (1);
 }
+
+void set_tree_marks(struct tree *tree, unsigned mark)
+{
+	struct name_entry entry;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+
+	tree->object.flags |= mark;
+
+	buffer = read_sha1_file(tree->object.sha1, &type, &size);
+	if (!buffer || type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(tree->object.sha1));
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (S_ISDIR(entry.mode))
+			set_tree_marks(lookup_tree(entry.sha1), mark);
+	}
+	free(buffer);
+}
+
+void clear_tree_marks(struct tree *tree, unsigned mark)
+{
+	struct name_entry entry;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+
+	tree->object.flags &= ~mark;
+
+	buffer = read_sha1_file(tree->object.sha1, &type, &size);
+	if (!buffer || type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(tree->object.sha1));
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (S_ISDIR(entry.mode))
+			clear_tree_marks(lookup_tree(entry.sha1), mark);
+	}
+	free(buffer);
+}
diff --git a/tree.h b/tree.h
index 2ff01a4..4376a3a 100644
--- a/tree.h
+++ b/tree.h
@@ -30,4 +30,7 @@ extern int read_tree_recursive(struct tree *tree,
 
 extern int read_tree(struct tree *tree, int stage, const char **paths);
 
+extern void set_tree_marks(struct tree *tree, unsigned mark);
+extern void clear_tree_marks(struct tree *tree, unsigned mark);
+
 #endif /* TREE_H */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 07/32] tree.c: find_subtree() to search for a tree

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 tree.c |   35 +++++++++++++++++++++++++++++++++++
 tree.h |    1 +
 2 files changed, 36 insertions(+), 0 deletions(-)

diff --git a/tree.c b/tree.c
index 434bf56..684afb5 100644
--- a/tree.c
+++ b/tree.c
@@ -328,3 +328,38 @@ void clear_tree_marks(struct tree *tree, unsigned mark)
 	}
 	free(buffer);
 }
+
+int find_tree(const unsigned char *sha1, unsigned char *newsha1, const char *path)
+{
+	struct name_entry entry;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+	const char *slash;
+	int len;
+
+	buffer = read_sha1_file(sha1, &type, &size);
+	if (!buffer || type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(sha1));
+
+	slash = strchr(path, '/');
+	len = slash ? slash - path : strlen(path);
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+		if (!strncmp(entry.path, path, len)) {
+			free(buffer);
+			if (slash)
+				return find_tree(entry.sha1, newsha1, slash+1);
+			else {
+				hashcpy(newsha1, entry.sha1);
+				return 1;
+			}
+		}
+	}
+	free(buffer);
+	return 0;
+}
diff --git a/tree.h b/tree.h
index 4376a3a..6ba1034 100644
--- a/tree.h
+++ b/tree.h
@@ -32,5 +32,6 @@ extern int read_tree(struct tree *tree, int stage, const char **paths);
 
 extern void set_tree_marks(struct tree *tree, unsigned mark);
 extern void clear_tree_marks(struct tree *tree, unsigned mark);
+extern int find_tree(const unsigned char *sha1, unsigned char *newsha1, const char *path);
 
 #endif /* TREE_H */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 08/32] Add $GIT_DIR/narrow check

[Nguyễn Thái Ngọc Duy]

This file contains the narrow prefix. With get_narrow_prefix() being
non-empty behavior of git may be totally different.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile      |    2 ++
 cache.h       |    3 +++
 environment.c |    2 ++
 narrow-tree.c |   31 +++++++++++++++++++++++++++++++
 narrow-tree.h |    1 +
 5 files changed, 39 insertions(+), 0 deletions(-)
 create mode 100644 narrow-tree.c
 create mode 100644 narrow-tree.h

diff --git a/Makefile b/Makefile
index 1f11618..54c435e 100644
--- a/Makefile
+++ b/Makefile
@@ -525,6 +525,7 @@ LIB_H += sigchain.h
 LIB_H += strbuf.h
 LIB_H += string-list.h
 LIB_H += submodule.h
+LIB_H += narrow-tree.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 += narrow-tree.o
 LIB_OBJS += symlinks.o
 LIB_OBJS += tag.o
 LIB_OBJS += trace.o
diff --git a/cache.h b/cache.h
index 37ef9d8..ff401ec 100644
--- a/cache.h
+++ b/cache.h
@@ -1101,4 +1101,7 @@ int split_cmdline(char *cmdline, const char ***argv);
 /* builtin/merge.c */
 int checkout_fast_forward(const unsigned char *from, const unsigned char *to);
 
+/* narrow-tree.c */
+extern const char *get_narrow_prefix();
+
 #endif /* CACHE_H */
diff --git a/environment.c b/environment.c
index 83d38d3..41fcbd4 100644
--- a/environment.c
+++ b/environment.c
@@ -8,6 +8,7 @@
  * are.
  */
 #include "cache.h"
+#include "narrow-tree.h"
 
 char git_default_email[MAX_GITNAME];
 char git_default_name[MAX_GITNAME];
@@ -105,6 +106,7 @@ static void setup_git_env(void)
 		git_graft_file = git_pathdup("info/grafts");
 	if (getenv(NO_REPLACE_OBJECTS_ENVIRONMENT))
 		read_replace_refs = 0;
+	check_narrow_prefix();
 }
 
 int is_bare_repository(void)
diff --git a/narrow-tree.c b/narrow-tree.c
new file mode 100644
index 0000000..46e913d
--- /dev/null
+++ b/narrow-tree.c
@@ -0,0 +1,31 @@
+#include "cache.h"
+#include "narrow-tree.h"
+
+static const char *narrow_prefix;
+
+int check_narrow_prefix()
+{
+	int fd;
+	static char buf[PATH_MAX];
+	int ret;
+
+	fd = open(git_path("narrow"), O_RDONLY);
+	if (fd == -1)
+		return 0;
+
+	ret = read(fd, buf, PATH_MAX);
+	if (ret > 0) {
+		/* $GIT_DIR/narrow is not meant for manual editing, anyway.. */
+		while (ret && buf[ret-1] == '\n')
+			ret--;
+		buf[ret] = '\0';
+		narrow_prefix = buf;
+	}
+	close(fd);
+	return 0;
+}
+
+const char *get_narrow_prefix()
+{
+	return narrow_prefix;
+}
diff --git a/narrow-tree.h b/narrow-tree.h
new file mode 100644
index 0000000..aa8c94f
--- /dev/null
+++ b/narrow-tree.h
@@ -0,0 +1 @@
+extern int check_narrow_prefix();
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 09/32] index: make narrow index incompatible with older git

[Nguyễn Thái Ngọc Duy]

Index in narrow repos is not a full index and should not be used
to create commits without modification (to be explained later on).

Also save narrow prefix inside index and check against
$GIT_DIR/narrow, just in case.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h                |    1 +
 read-cache.c           |   35 +++++++++++++++++++++++++++++++----
 t/t6060-narrow-tree.sh |   28 ++++++++++++++++++++++++++++
 3 files changed, 60 insertions(+), 4 deletions(-)
 create mode 100755 t/t6060-narrow-tree.sh

diff --git a/cache.h b/cache.h
index ff401ec..6bc80b3 100644
--- a/cache.h
+++ b/cache.h
@@ -293,6 +293,7 @@ struct index_state {
 	struct string_list *resolve_undo;
 	struct cache_tree *cache_tree;
 	struct cache_time timestamp;
+	char *narrow_prefix;
 	void *alloc;
 	unsigned name_hash_initialized : 1,
 		 initialized : 1;
diff --git a/read-cache.c b/read-cache.c
index 881dd93..20b619c 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -25,8 +25,9 @@ static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int reall
  */
 
 #define CACHE_EXT(s) ( (s[0]<<24)|(s[1]<<16)|(s[2]<<8)|(s[3]) )
-#define CACHE_EXT_TREE 0x54524545	/* "TREE" */
+#define CACHE_EXT_TREE 0x54524545	  /* "TREE" */
 #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* "REUC" */
+#define CACHE_EXT_NARROW 0x4e415257	  /* "NARW" */
 
 struct index_state the_index;
 
@@ -1168,7 +1169,9 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
 
 	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
 		return error("bad signature");
-	if (hdr->hdr_version != htonl(2) && hdr->hdr_version != htonl(3))
+	if (hdr->hdr_version != htonl(2) &&
+	    hdr->hdr_version != htonl(3) &&
+	    hdr->hdr_version != htonl(4))
 		return error("bad index version");
 	git_SHA1_Init(&c);
 	git_SHA1_Update(&c, hdr, size - 20);
@@ -1188,6 +1191,9 @@ static int read_index_extension(struct index_state *istate,
 	case CACHE_EXT_RESOLVE_UNDO:
 		istate->resolve_undo = resolve_undo_read(data, sz);
 		break;
+	case CACHE_EXT_NARROW:
+		istate->narrow_prefix = xstrdup(data);
+		break;
 	default:
 		if (*ext < 'A' || 'Z' < *ext)
 			return error("index uses %.4s extension, which we do not understand",
@@ -1352,6 +1358,16 @@ int read_index_from(struct index_state *istate, const char *path)
 		src_offset += extsize;
 	}
 	munmap(mmap, mmap_size);
+
+	if ((!get_narrow_prefix() && !istate->narrow_prefix) ||
+	    (get_narrow_prefix() && istate->narrow_prefix &&
+	     !strcmp(get_narrow_prefix(), istate->narrow_prefix)))
+		;		/* good */
+	else
+		die("Incompatible index and narrow mode (%s/%s)",
+		    get_narrow_prefix(),
+		    istate->narrow_prefix);
+
 	return istate->cache_nr;
 
 unmap:
@@ -1549,7 +1565,7 @@ int write_index(struct index_state *istate, int newfd)
 {
 	git_SHA_CTX c;
 	struct cache_header hdr;
-	int i, err, removed, extended;
+	int i, err, removed, extended, ver;
 	struct cache_entry **cache = istate->cache;
 	int entries = istate->cache_nr;
 	struct stat st;
@@ -1568,7 +1584,11 @@ int write_index(struct index_state *istate, int newfd)
 
 	hdr.hdr_signature = htonl(CACHE_SIGNATURE);
 	/* for extended format, increase version so older git won't try to read it */
-	hdr.hdr_version = htonl(extended ? 3 : 2);
+	ver = extended ? 3 : 2;
+	if (get_narrow_prefix() && ver < 4)
+		ver = 4;	/* narrow-unaware git should to touch this index */
+
+	hdr.hdr_version = htonl(ver);
 	hdr.hdr_entries = htonl(entries - removed);
 
 	git_SHA1_Init(&c);
@@ -1607,6 +1627,13 @@ int write_index(struct index_state *istate, int newfd)
 		if (err)
 			return -1;
 	}
+	if (get_narrow_prefix()) {
+		int len = strlen(get_narrow_prefix())+1;
+		err = write_index_ext_header(&c, newfd, CACHE_EXT_NARROW, len) < 0 ||
+			ce_write(&c, newfd, get_narrow_prefix(), len) < 0;
+		if (err)
+			return -1;
+	}
 
 	if (ce_flush(&c, newfd) || fstat(newfd, &st))
 		return -1;
diff --git a/t/t6060-narrow-tree.sh b/t/t6060-narrow-tree.sh
new file mode 100755
index 0000000..0e561c8
--- /dev/null
+++ b/t/t6060-narrow-tree.sh
@@ -0,0 +1,28 @@
+#!/bin/sh
+
+test_description='narrow-tree tests'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	: >test
+'
+
+test_expect_success 'index ver 4 in narrow mode' '
+	echo foo >.git/narrow &&
+	git update-index --add test &&
+	echo 4 >expected &&
+	test-index-version < .git/index >result &&
+	test_cmp expected result
+'
+
+test_expect_success 'index ver < 4 when narrow mode is gone' '
+	rm .git/narrow &&
+	rm .git/index &&
+	git update-index --add test &&
+	echo 2 >expected &&
+	test-index-version < .git/index >result &&
+	test_cmp expected result
+'
+
+test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 10/32] rev-list: support traversing in narrow repository mode

[Nguyễn Thái Ngọc Duy]

In this mode, only trees within revs->narrow_prefix is traversed. This
narrows down the whole repository to the given subtree. This mode will
be used by upload-pack/pack-objects to create a narrow pack, and by
all git operations in narrow repository (i.e. $GIT_DIR/narrow exists).

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 list-objects.c |   36 +++++++++++++++++++++++++++++++++---
 revision.h     |    4 +++-
 2 files changed, 36 insertions(+), 4 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index 8953548..7014926 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -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 = NULL;
+	int subtree_len;
 
 	if (!revs->tree_objects)
 		return;
@@ -82,13 +85,34 @@ 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)) {
+		/*
+		 * FIXME, does not follow tree rename
+		 * some sort of rename hints would be nice
+		 * (because diff machinery should not be used
+		 * here for detecting renames)
+		 */
+		if (!subtree)
+			; 	/* no subtree restriction, go on */
+		else if (S_ISDIR(entry.mode) &&
+			 !strncmp(entry.path, subtree, subtree_len) &&
+			 entry.path[subtree_len] == '\0')
+			;	/* inside subtree, go on */
+		else
+			continue; /* stop */
+
 		if (S_ISDIR(entry.mode))
 			process_tree(revs,
 				     lookup_tree(entry.sha1),
-				     show, &me, entry.path);
+				     show, &me, entry.path,
+				     slash ? slash+1 : NULL);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
 					show, &me, entry.path);
@@ -147,6 +171,11 @@ void traverse_commit_list(struct rev_info *revs,
 	int i;
 	struct commit *commit;
 
+	if (get_narrow_prefix() && !revs->narrow_tree) {
+		revs->narrow_tree = 1;
+		revs->narrow_prefix = get_narrow_prefix();
+	}
+
 	while ((commit = get_revision(revs)) != NULL) {
 		add_pending_tree(revs, commit->tree);
 		show_commit(commit, data);
@@ -164,7 +193,8 @@ 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,
+				     revs->narrow_tree ? revs->narrow_prefix : NULL);
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
diff --git a/revision.h b/revision.h
index 36fdf22..ccdf28a 100644
--- a/revision.h
+++ b/revision.h
@@ -33,6 +33,7 @@ struct rev_info {
 
 	/* Basic information */
 	const char *prefix;
+	const char *narrow_prefix;
 	const char *def;
 	void *prune_data;
 	unsigned int early_output;
@@ -68,7 +69,8 @@ struct rev_info {
 			cherry_pick:1,
 			bisect:1,
 			ancestry_path:1,
-			first_parent_only:1;
+			first_parent_only:1,
+			narrow_tree:1;
 
 	/* Diff flags */
 	unsigned int	diff:1,
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 11/32] rev-list: support --narrow-tree

[Nguyễn Thái Ngọc Duy]

These options allow plumbing to access narrow tree traverse modes.
As a consequence, tests can now be written to test these modes.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 revision.c                 |    5 ++
 t/t6061-rev-list-narrow.sh |  158 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 163 insertions(+), 0 deletions(-)
 create mode 100755 t/t6061-rev-list-narrow.sh

diff --git a/revision.c b/revision.c
index 7e82efd..a4eb11f 100644
--- a/revision.c
+++ b/revision.c
@@ -1562,6 +1562,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 				read_revisions_from_stdin(revs, &prune_data);
 				continue;
 			}
+			if (!prefixcmp(arg, "--narrow-tree=")) {
+				revs->narrow_prefix = arg + 14;
+				revs->narrow_tree = 1;
+				continue;
+			}
 
 			opts = handle_revision_opt(revs, argc - i, argv + i, &left, argv);
 			if (opts > 0) {
diff --git a/t/t6061-rev-list-narrow.sh b/t/t6061-rev-list-narrow.sh
new file mode 100755
index 0000000..e489347
--- /dev/null
+++ b/t/t6061-rev-list-narrow.sh
@@ -0,0 +1,158 @@
+#!/bin/sh
+
+test_description='rev-list in narrow tree mode'
+
+. ./test-lib.sh
+
+# Normal tree
+cat <<EOF >revlist.expected
+ba7a30916c792624a8372cb26da50f5594098222
+3b52e9990a52d9ea46b25199b5810566324759f4 
+573541ac9702dd3969c9bc859d2b91ec1f7e6e56 f0
+fa0bba1767985729582729a12a5459cd041d6cf6 t1
+f599e28b8ab0d8c9c57a486c89c4a5132dcbd3b2 t1/f10
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
+209e3ef4b6247ce746048d5711befda46206d235 t2/f20
+EOF
+
+# narrowed down tree
+cat <<EOF >t12.expected
+ba7a30916c792624a8372cb26da50f5594098222
+3b52e9990a52d9ea46b25199b5810566324759f4 
+fa0bba1767985729582729a12a5459cd041d6cf6 t1
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+EOF
+
+# local tree
+cat <<EOF >t12-subtree.expected
+ba7a30916c792624a8372cb26da50f5594098222
+c0167b5ce78e9fb801ef96dcc319f3411d35278b 
+e9a12654c859aff51978b25b2a6c5eddf6c1e13c t1
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+EOF
+
+cat <<EOF >t2.expected
+ba7a30916c792624a8372cb26da50f5594098222
+3b52e9990a52d9ea46b25199b5810566324759f4 
+74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
+209e3ef4b6247ce746048d5711befda46206d235 t2/f20
+EOF
+
+test_expect_success setup '
+	test_tick &&
+	mkdir t1 t2 t1/t12 &&
+	echo 0 > f0 &&
+	echo 10 > t1/f10 &&
+	echo 120 > t1/t12/f120 &&
+	echo 20 > t2/f20
+	git add t1 t2 f0 && git commit -m initial &&
+	C1=`git rev-parse HEAD` &&
+	T2=`git rev-parse HEAD^{tree}` &&
+	git rev-list --objects HEAD >result &&
+	test_cmp revlist.expected result
+'
+
+cat <<EOF >branch1.expected
+7475cb8a389b36ce238b9ee6cbfdfa26a1b67e35
+ba7a30916c792624a8372cb26da50f5594098222
+aa0602ee56ea4cb5e5bfff8713bb8a9a6ab4303e 
+407c07594c8083c3d0521a1cb463b1204d880c13 f0
+d77d258d806b2aa7cdb5a301e6a54f023d9bdcfe t1
+737483f30ba682e414d715f7976fe9a9904fdbc0 t1/f10
+ab246f7eb05e94f695d2a0e30093d94fde7b837e t1/t12
+04156ae83e615fa5b6019170928bc131539f9996 t1/t12/f120
+1da4df952e59f2fa7ff211a8ee9f72b3174bbfb7 t2
+9aa2407894b849226773016ef5d68c5b87a23926 t2/f20
+3b52e9990a52d9ea46b25199b5810566324759f4 
+573541ac9702dd3969c9bc859d2b91ec1f7e6e56 f0
+fa0bba1767985729582729a12a5459cd041d6cf6 t1
+f599e28b8ab0d8c9c57a486c89c4a5132dcbd3b2 t1/f10
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
+209e3ef4b6247ce746048d5711befda46206d235 t2/f20
+EOF
+
+test_expect_success 'setup branch1' '
+	echo common >> t1/t12/f120 &&
+	echo branch1 >> t1/f10 &&
+	echo branch1 >> t2/f20 &&
+	echo branch1 >> f0 &&
+	git add -u && git commit -m branch1 &&
+	BRANCH1=`git rev-parse HEAD` &&
+	git rev-list --objects $BRANCH1 > result &&
+	test_cmp branch1.expected result
+'
+
+cat <<EOF >branch2.expected
+af9c31c0e217154296d93d66b9a5a41892c7b321
+ba7a30916c792624a8372cb26da50f5594098222
+72e05e456b9ff4c01ccf6178ce60d9b52b41aae4 
+573541ac9702dd3969c9bc859d2b91ec1f7e6e56 f0
+4fc1656b01ce8b21987c55a2870b8c9a431ec772 t1
+f599e28b8ab0d8c9c57a486c89c4a5132dcbd3b2 t1/f10
+ab246f7eb05e94f695d2a0e30093d94fde7b837e t1/t12
+04156ae83e615fa5b6019170928bc131539f9996 t1/t12/f120
+cef4db52388f5e0853acc772faa68058436a95ff t2
+7319a2144592e50a564d49902302a8b1bad2f49c t2/f20
+3b52e9990a52d9ea46b25199b5810566324759f4 
+fa0bba1767985729582729a12a5459cd041d6cf6 t1
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
+209e3ef4b6247ce746048d5711befda46206d235 t2/f20
+EOF
+
+test_expect_success 'setup branch2' '
+	git reset --hard HEAD^ &&
+	echo common >> t1/t12/f120 &&
+	echo branch2 >> t2/f20 &&
+	git add -u && git commit -m branch2 &&
+	BRANCH2=`git rev-parse HEAD` &&
+	git rev-list --objects $BRANCH2 > result &&
+	test_cmp branch2.expected result
+'
+
+test_expect_success 'setup merge' '
+	git reset --hard HEAD^
+	MERGE=`echo merge | git commit-tree $T2 -p $BRANCH1 -p $BRANCH2`
+'
+
+test_expect_success 'rev-list --narrow-tree=t2' '
+	git rev-list --objects --narrow-tree=t2 HEAD >result &&
+	test_cmp t2.expected result
+'
+
+test_expect_success 'rev-list --narrow-tree=t1/t12' '
+	git rev-list --objects --narrow-tree=t1/t12 HEAD >result &&
+	test_cmp t12.expected result
+'
+
+cat <<EOF >merge.expected
+0da28f8308e336bd4b2c26b61c7fc44e41a30e49
+7475cb8a389b36ce238b9ee6cbfdfa26a1b67e35
+af9c31c0e217154296d93d66b9a5a41892c7b321
+ba7a30916c792624a8372cb26da50f5594098222
+74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
+3b52e9990a52d9ea46b25199b5810566324759f4 
+fa0bba1767985729582729a12a5459cd041d6cf6 t1
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
+aa0602ee56ea4cb5e5bfff8713bb8a9a6ab4303e 
+d77d258d806b2aa7cdb5a301e6a54f023d9bdcfe t1
+ab246f7eb05e94f695d2a0e30093d94fde7b837e t1/t12
+04156ae83e615fa5b6019170928bc131539f9996 t1/t12/f120
+72e05e456b9ff4c01ccf6178ce60d9b52b41aae4 
+4fc1656b01ce8b21987c55a2870b8c9a431ec772 t1
+EOF
+
+test_expect_success 'rev-list --narrow-tree=t1/t12 with merges' '
+	git rev-list --objects --narrow-tree=t1/t12 $MERGE >result &&
+	test_cmp merge.expected result
+'
+
+test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 12/32] pack-objects: support --narrow-tree

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/pack-objects.c     |    9 +++++++++
 t/t6061-rev-list-narrow.sh |   27 +++++++++++++++++++++++++++
 2 files changed, 36 insertions(+), 0 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index a664223..36ab350 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -106,6 +106,7 @@ static int object_ix_hashsz;
 static uint32_t written, written_delta;
 static uint32_t reused, reused_delta;
 
+const char *narrow_prefix;
 
 static void *get_delta(struct object_entry *entry)
 {
@@ -2055,6 +2056,10 @@ static void get_object_list(int ac, const char **av)
 	init_revisions(&revs, NULL);
 	save_commit_buffer = 0;
 	setup_revisions(ac, av, &revs, NULL);
+	if (narrow_prefix) {
+		revs.narrow_tree = 1;
+		revs.narrow_prefix = narrow_prefix;
+	}
 
 	while (fgets(line, sizeof(line), stdin) != NULL) {
 		int len = strlen(line);
@@ -2259,6 +2264,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			grafts_replace_parents = 0;
 			continue;
 		}
+		if (!prefixcmp(arg, "--narrow-tree=")) {
+			narrow_prefix = arg + 14;
+			continue;
+		}
 		usage(pack_usage);
 	}
 
diff --git a/t/t6061-rev-list-narrow.sh b/t/t6061-rev-list-narrow.sh
index e489347..30ef46f 100755
--- a/t/t6061-rev-list-narrow.sh
+++ b/t/t6061-rev-list-narrow.sh
@@ -155,4 +155,31 @@ test_expect_success 'rev-list --narrow-tree=t1/t12 with merges' '
 	test_cmp merge.expected result
 '
 
+cat <<EOF >pack.expected
+04156ae83e615fa5b6019170928bc131539f9996
+0da28f8308e336bd4b2c26b61c7fc44e41a30e49
+3b52e9990a52d9ea46b25199b5810566324759f4
+4fc1656b01ce8b21987c55a2870b8c9a431ec772
+52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4
+72e05e456b9ff4c01ccf6178ce60d9b52b41aae4
+7475cb8a389b36ce238b9ee6cbfdfa26a1b67e35
+74a398027f0b59183db54ca8c67dc30b5aeed0ff
+aa0602ee56ea4cb5e5bfff8713bb8a9a6ab4303e
+ab246f7eb05e94f695d2a0e30093d94fde7b837e
+af9c31c0e217154296d93d66b9a5a41892c7b321
+ba7a30916c792624a8372cb26da50f5594098222
+d77d258d806b2aa7cdb5a301e6a54f023d9bdcfe
+d81015b2a1c40fc6cbc5bf5a8b16949018c3aede
+fa0bba1767985729582729a12a5459cd041d6cf6
+EOF
+
+test_expect_success 'pack-object --narrow-tree=t1/t12' '
+	echo $MERGE|git pack-objects --revs --narrow-tree=t1/t12 --stdout >p.pack &&
+	git index-pack -o p.idx p.pack &&
+	git verify-pack -v p.pack |
+		grep "^[0-9a-f][0-9a-f][0-9a-f][0-9a-f]" |
+		cut -d " " -f 1 >result &&
+	test_cmp pack.expected result
+'
+
 test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 13/32] upload-pack: support narrow-tree capability

[Nguyễn Thái Ngọc Duy]

If narrow-tree line is sent from fetch-pack, rev-walk will be put in
narrow mode.

Currently only one narrow-tree is supported.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 upload-pack.c |   31 +++++++++++++++++++++++++++++--
 1 files changed, 29 insertions(+), 2 deletions(-)

diff --git a/upload-pack.c b/upload-pack.c
index fc79dde..571fcb6 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -41,6 +41,7 @@ static int use_sideband;
 static int debug_fd;
 static int advertise_refs;
 static int stateless_rpc;
+char *narrow_prefix;
 
 static void reset_timeout(void)
 {
@@ -117,6 +118,10 @@ static int do_rev_list(int in, int out, void *user_data)
 	revs.blob_objects = 1;
 	if (use_thin_pack)
 		revs.edge_hint = 1;
+	if (narrow_prefix) {
+		revs.narrow_tree = 1;
+		revs.narrow_prefix = narrow_prefix;
+	}
 
 	for (i = 0; i < want_obj.nr; i++) {
 		struct object *o = want_obj.objects[i].item;
@@ -153,7 +158,8 @@ static void create_pack_file(void)
 		"corruption on the remote side.";
 	int buffered = -1;
 	ssize_t sz;
-	const char *argv[10];
+	const char *argv[11];
+	char arg_narrow[PATH_MAX];
 	int arg = 0;
 
 	if (shallow_nr) {
@@ -173,6 +179,10 @@ static void create_pack_file(void)
 	}
 
 	argv[arg++] = "--stdout";
+	if (narrow_prefix) {
+		sprintf(arg_narrow, "--narrow-tree=%s", narrow_prefix);
+		argv[arg++] = arg_narrow;
+	}
 	if (!no_progress)
 		argv[arg++] = "--progress";
 	if (use_ofs_delta)
@@ -499,6 +509,18 @@ static void receive_needs(void)
 		if (debug_fd)
 			write_in_full(debug_fd, line, len);
 
+		if (!prefixcmp(line, "narrow-tree ")) {
+			int len;
+			if (narrow_prefix)
+				die("sorry, only one narrow prefix is supported");
+			len = strlen(line+12);
+			narrow_prefix = malloc(len+1);
+			memcpy(narrow_prefix, line+12, len-1);
+			narrow_prefix[len-1] = '\0'; /* \n */
+			if (narrow_prefix[len-2] == '/')
+				die("trailing slash in narrow prefix not allowed");
+			continue;
+		}
 		if (!prefixcmp(line, "shallow ")) {
 			unsigned char sha1[20];
 			struct object *object;
@@ -562,6 +584,9 @@ static void receive_needs(void)
 	if (!use_sideband && daemon_mode)
 		no_progress = 1;
 
+	if (narrow_prefix)
+		use_thin_pack = 0;
+
 	if (depth == 0 && shallows.nr == 0)
 		return;
 	if (depth > 0) {
@@ -619,7 +644,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 narrow-tree";
 	struct object *o = parse_object(sha1);
 
 	if (!o)
@@ -724,6 +749,8 @@ int main(int argc, char **argv)
 		die("'%s' does not appear to be a git repository", dir);
 	if (is_repository_shallow())
 		die("attempt to fetch/clone from a shallow repository");
+	if (get_narrow_prefix())
+		die("attempt to fetch/clone from a narrow repository");
 	if (getenv("GIT_DEBUG_SEND_PACK"))
 		debug_fd = atoi(getenv("GIT_DEBUG_SEND_PACK"));
 	upload_pack();
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 14/32] fetch-pack: support --narrow-tree

[Nguyễn Thái Ngọc Duy]

This options requires narrow-tree capability from upload-pack. It
simply sends narrow-tree line from argument to to upload-pack.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/fetch-pack.c |   11 +++++++++++
 1 files changed, 11 insertions(+), 0 deletions(-)

diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index dbd8b7b..821b713 100644
--- a/builtin/fetch-pack.c
+++ b/builtin/fetch-pack.c
@@ -37,6 +37,7 @@ static int marked;
 
 static struct commit_list *rev_list;
 static int non_common_revs, multi_ack, use_sideband;
+const char *narrow_prefix;
 
 static void rev_list_push(struct commit *commit, int mark)
 {
@@ -237,6 +238,10 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 	for_each_ref(rev_list_insert_ref, NULL);
 
 	fetching = 0;
+	if (get_narrow_prefix() && !narrow_prefix)
+		narrow_prefix = get_narrow_prefix();
+	if (narrow_prefix)
+		packet_buf_write(&req_buf, "narrow-tree %s\n", narrow_prefix);
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
 		const char *remote_hex;
@@ -692,6 +697,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 (narrow_prefix && !server_supports("narrow-tree"))
+		die("Server does not support narrow-tree");
 	if (server_supports("multi_ack_detailed")) {
 		if (args.verbose)
 			fprintf(stderr, "Server supports multi_ack_detailed\n");
@@ -860,6 +867,10 @@ int cmd_fetch_pack(int argc, const char **argv, const char *prefix)
 				pack_lockfile_ptr = &pack_lockfile;
 				continue;
 			}
+			if (!prefixcmp(arg, "--narrow-tree=")) {
+				narrow_prefix = arg + 14;
+				continue;
+			}
 			usage(fetch_pack_usage);
 		}
 		dest = (char *)arg;
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 15/32] unpack_trees: only unpack $GIT_DIR/narrow subtree in narrow repository

[Nguyễn Thái Ngọc Duy]

By definition, narrow repository is incomplete. It does not even have
enough tree for a single commit. So populating a full index is
impossible.

Because of this, unpack_trees() is modified to only unpack trees
within $GIT_DIR/narrow, which narrow repo has all needed trees. This
makes the resulting index unsuitable for creating commits later on.
This is the reason index version is increased to 4, to avoid older
git from using it.

The resulting tree objects created from the index is only part of the
full tree. Manipulation will be needed at commit time to create proper
tree for commits.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t1013-read-tree-narrow.sh |   72 +++++++++++++++++++++++++++++++++++++++++++
 unpack-trees.c              |   70 +++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 141 insertions(+), 1 deletions(-)
 create mode 100755 t/t1013-read-tree-narrow.sh

diff --git a/t/t1013-read-tree-narrow.sh b/t/t1013-read-tree-narrow.sh
new file mode 100755
index 0000000..1921985
--- /dev/null
+++ b/t/t1013-read-tree-narrow.sh
@@ -0,0 +1,72 @@
+#!/bin/sh
+
+test_description='read-tree in narrow mode'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	test_tick &&
+	test_commit 1 &&
+	mkdir t1 t2 t1/t12 &&
+	echo 0 > f0 &&
+	echo 10 > t1/f10 &&
+	echo 120 > t1/t12/f120 &&
+	echo 20 > t2/f20
+	git add t1 t2 f0 && git commit -m initial &&
+	HEAD=`git rev-parse HEAD` &&
+	git rev-parse HEAD | git pack-objects --revs --narrow-tree=t1/t12 pack &&
+	test_create_repo narrow &&
+	mv pack-* narrow/.git/objects/pack &&
+	cd narrow &&
+	echo $HEAD >.git/refs/heads/master &&
+	echo "ref: refs/heads/master" >.git/HEAD &&
+	echo t1/t12 >.git/narrow
+'
+
+test_expect_failure ls-tree '
+	git ls-tree -r HEAD &&
+	git ls-files --stage >result &&
+	echo "100644 blob 52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4	t1/t12/f120" >expected &&
+	test_cmp expected result
+'
+
+test_expect_success read-tree '
+	git read-tree HEAD &&
+	git ls-files --stage >result &&
+	echo "100644 52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 0	t1/t12/f120" >expected &&
+	test_cmp expected result
+'
+
+test_expect_success checkout '
+	git checkout . &&
+	test_cmp ../t1/t12/f120 t1/t12/f120
+'
+
+cat <<EOF >diff.expected
+diff --git a/t1/t12/f120 b/t1/t12/f120
+index 52bd8e4..645fb94 100644
+--- a/t1/t12/f120
++++ b/t1/t12/f120
+@@ -1 +1,2 @@
+ 120
++modified
+EOF
+
+test_expect_success diff '
+	echo modified >> t1/t12/f120 &&
+	git diff >result &&
+	test_cmp diff.expected result
+'
+
+test_expect_success 'diff HEAD' '
+	git diff HEAD >result &&
+	test_cmp diff.expected result
+'
+
+test_expect_success 'diff --cached' '
+	git add -u . &&
+	git diff --cached >result &&
+	test_cmp diff.expected result
+'
+
+test_done
diff --git a/unpack-trees.c b/unpack-trees.c
index f561d88..661fcb7 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -713,7 +713,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
  * N-way merge "len" trees.  Returns 0 on success, -1 on failure to manipulate the
  * resulting index, -2 on failure to reflect the changes to the work tree.
  */
-int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
+static int unpack_trees_1(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
 	int i, ret;
 	static struct cache_entry *dfc;
@@ -839,6 +839,74 @@ return_failed:
 	goto done;
 }
 
+static int find_tree_desc(struct tree_desc *desc, unsigned char *newsha1, const char *path)
+{
+	struct name_entry entry;
+	const char *slash;
+	int len;
+
+	slash = strchr(path, '/');
+	len = slash ? slash - path : strlen(path);
+
+	while (tree_entry(desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+		if (!strncmp(entry.path, path, len)) {
+			if (slash)
+				return find_tree(entry.sha1, newsha1, slash+1);
+			else {
+				hashcpy(newsha1, entry.sha1);
+				return 1;
+			}
+		}
+	}
+	return 0;
+}
+
+int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
+{
+	if (!get_narrow_prefix())
+		return unpack_trees_1(len, t, o);
+	else {
+		struct tree_desc *t2;
+		struct unpack_trees_options o2;
+		char *prefix = NULL;
+		void **buf;
+		int i, ret;
+		t2 = xmalloc(sizeof(*t2)*len);
+		buf = xmalloc(sizeof(*buf)*len);
+		for (i = 0; i < len; i++) {
+			unsigned char sha1[20];
+			unsigned long size;
+			enum object_type type;
+
+			if (!find_tree_desc(t+i, sha1, get_narrow_prefix()))
+				return -1;
+			buf[i] = read_sha1_file(sha1, &type, &size);
+			if (type != OBJ_TREE)
+				return -1;
+			init_tree_desc(t2+i, buf[i], size);
+		}
+		o2 = *o;
+		if (!o->prefix)
+			o2.prefix = xstrdup(get_narrow_prefix());
+		else {
+			prefix = xmalloc(strlen(get_narrow_prefix()) + strlen(o->prefix)+1);
+			strcpy(prefix, o->prefix);
+			strcat(prefix, get_narrow_prefix());
+			o2.prefix = prefix;
+		}
+		ret = unpack_trees_1(len, t2, &o2);
+		for (i = 0; i < len; i++) {
+			free(buf[i]);
+		}
+		free(prefix);
+		free(t2);
+		free(buf);
+		return ret;
+	}
+}
+
 /* Here come the merge functions */
 
 static int reject_merge(struct cache_entry *ce, struct unpack_trees_options *o)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 16/32] cache-tree: only cache tree within narrow area

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache-tree.c |   17 +++++++++++++----
 1 files changed, 13 insertions(+), 4 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index 03952c7..69ce0a2 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -616,11 +616,17 @@ int write_cache_as_tree(unsigned char *sha1, int flags, const char *prefix)
 	return 0;
 }
 
-static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
+static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree, const char *path)
 {
 	struct tree_desc desc;
 	struct name_entry entry;
-	int cnt;
+	const char *slash;
+	int len = 0, cnt;
+
+	if (path) {
+		slash = strchr(path, '/');
+		len = slash ? slash - path : strlen(path);
+	}
 
 	hashcpy(it->sha1, tree->object.sha1);
 	init_tree_desc(&desc, tree->buffer, tree->size);
@@ -628,6 +634,8 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 	while (tree_entry(&desc, &entry)) {
 		if (!S_ISDIR(entry.mode))
 			cnt++;
+		else if (get_narrow_prefix() && len && strncmp(entry.path, path, len))
+			cnt++;
 		else {
 			struct cache_tree_sub *sub;
 			struct tree *subtree = lookup_tree(entry.sha1);
@@ -635,7 +643,8 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 				parse_tree(subtree);
 			sub = cache_tree_sub(it, entry.path);
 			sub->cache_tree = cache_tree();
-			prime_cache_tree_rec(sub->cache_tree, subtree);
+			prime_cache_tree_rec(sub->cache_tree, subtree,
+					     slash ? slash+1 : NULL);
 			cnt += sub->cache_tree->entry_count;
 		}
 	}
@@ -646,7 +655,7 @@ void prime_cache_tree(struct cache_tree **it, struct tree *tree)
 {
 	cache_tree_free(it);
 	*it = cache_tree();
-	prime_cache_tree_rec(*it, tree);
+	prime_cache_tree_rec(*it, tree, get_narrow_prefix());
 }
 
 /*
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 17/32] tree-diff: add narrow versions of diff_{root_,}tree_sha1

[Nguyễn Thái Ngọc Duy]

These versions assume that the given trees for diff are toplevel
trees. They simply go down to find $GIT_DIR/narrow subtree and do diff
on those trees instead. diff_tree_sha1 callers must be adapted to use
this version to support narrow repos.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 diff.h      |    5 ++++
 tree-diff.c |   74 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 79 insertions(+), 0 deletions(-)

diff --git a/diff.h b/diff.h
index d43da9d..13b4f10 100644
--- a/diff.h
+++ b/diff.h
@@ -171,6 +171,11 @@ extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 extern int diff_root_tree_sha1(const unsigned char *new, const char *base,
                                struct diff_options *opt);
 
+extern int narrow_diff_tree_sha1(const unsigned char *old, const unsigned char *new,
+				 const char *base, struct diff_options *opt);
+extern int narrow_diff_root_tree_sha1(const unsigned char *new, const char *base,
+				      struct diff_options *opt);
+
 struct combine_diff_path {
 	struct combine_diff_path *next;
 	int len;
diff --git a/tree-diff.c b/tree-diff.c
index cd659c6..31b0842 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -433,6 +433,45 @@ int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const cha
 	return retval;
 }
 
+int narrow_diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
+{
+	unsigned char old2[20], new2[20];
+	char *new_base = NULL;
+	int retval;
+
+	if (get_narrow_prefix()) {
+		int len1 = strlen(get_narrow_prefix());
+		int len2 = base ? strlen(base) : 0;
+		unsigned long size;
+		unsigned char deref_sha1[20];
+
+		if (len2 && !strncmp(base, get_narrow_prefix(), len1) &&
+		    (base[len1] == '/' || base[len1] == '\0'))
+			;	/* good */
+		else {
+			new_base = xmalloc(len1 + 1 + len2 + 1);
+			memcpy(new_base, get_narrow_prefix, len1+1);
+			if (len2) {
+				new_base[len1] = '/';
+				memcpy(new_base+len1+1, base, len2+1);
+			}
+			base = new_base;
+		}
+
+		free(read_object_with_reference(old, tree_type, &size, deref_sha1));
+		if (!find_tree(deref_sha1, old2, get_narrow_prefix()))
+			hashcpy(old2, (const unsigned char *)EMPTY_TREE_SHA1_BIN);
+		old = old2;
+		free(read_object_with_reference(new, tree_type, &size, deref_sha1));
+		if (!find_tree(deref_sha1, new2, get_narrow_prefix()))
+			hashcpy(new2, (const unsigned char *)EMPTY_TREE_SHA1_BIN);
+		new = new2;
+	}
+	retval = diff_tree_sha1(old, new, base, opt);
+	free(new_base);
+	return retval;
+}
+
 int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
 {
 	int retval;
@@ -451,6 +490,41 @@ int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_
 	return retval;
 }
 
+int narrow_diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_options *opt)
+{
+	unsigned char new2[20];
+	char *new_base = NULL;
+	int retval;
+
+	if (get_narrow_prefix()) {
+		int len1 = strlen(get_narrow_prefix());
+		int len2 = base ? strlen(base) : 0;
+		unsigned long size;
+		unsigned char deref_sha1[20];
+
+		if (len2 && !strncmp(base, get_narrow_prefix(), len1) &&
+		    (base[len1] == '/' || base[len1] == '\0'))
+			;	/* good */
+		else {
+			new_base = xmalloc(len1 + 1 + len2 + 1);
+			memcpy(new_base, get_narrow_prefix, len1+1);
+			if (len2) {
+				new_base[len1] = '/';
+				memcpy(new_base+len1+1, base, len2+1);
+			}
+			base = new_base;
+		}
+
+		free(read_object_with_reference(new, tree_type, &size, deref_sha1));
+		if (!find_tree(deref_sha1, new2, get_narrow_prefix()))
+			hashcpy(new2, (const unsigned char *)EMPTY_TREE_SHA1_BIN);
+		new = new2;
+	}
+	retval = diff_root_tree_sha1(new, base, opt);
+	free(new_base);
+	return retval;
+}
+
 static int count_paths(const char **paths)
 {
 	int i = 0;
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 18/32] log-tree: use narrow version of diff_tree_sha1

[Nguyễn Thái Ngọc Duy]

This makes "git log" work in narrow repos.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 log-tree.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/log-tree.c b/log-tree.c
index b46ed3b..693992a 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -600,7 +600,10 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 	parents = commit->parents;
 	if (!parents) {
 		if (opt->show_root_diff) {
-			diff_root_tree_sha1(sha1, "", &opt->diffopt);
+			if (get_narrow_prefix())
+				narrow_diff_root_tree_sha1(sha1, NULL, &opt->diffopt);
+			else
+				diff_root_tree_sha1(sha1, "", &opt->diffopt);
 			log_tree_diff_flush(opt);
 		}
 		return !opt->loginfo;
@@ -618,7 +621,14 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 			 * parent, showing summary diff of the others
 			 * we merged _in_.
 			 */
-			diff_tree_sha1(parents->item->object.sha1, sha1, "", &opt->diffopt);
+			if (get_narrow_prefix())
+				narrow_diff_tree_sha1(parents->item->object.sha1,
+						      sha1,
+						      NULL,
+						      &opt->diffopt);
+			else
+				diff_tree_sha1(parents->item->object.sha1, sha1,
+					       "", &opt->diffopt);
 			log_tree_diff_flush(opt);
 			return !opt->loginfo;
 		}
@@ -631,7 +641,14 @@ static int log_tree_diff(struct rev_info *opt, struct commit *commit, struct log
 	for (;;) {
 		struct commit *parent = parents->item;
 
-		diff_tree_sha1(parent->object.sha1, sha1, "", &opt->diffopt);
+		if (get_narrow_prefix())
+			narrow_diff_tree_sha1(parent->object.sha1,
+					      sha1,
+					      NULL,
+					      &opt->diffopt);
+		else
+			diff_tree_sha1(parent->object.sha1, sha1,
+				       "", &opt->diffopt);
 		log_tree_diff_flush(opt);
 
 		showed_log |= !opt->loginfo;
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 19/32] clone: support --narrow option

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/clone.c |   15 ++++++++++++++-
 1 files changed, 14 insertions(+), 1 deletions(-)

diff --git a/builtin/clone.c b/builtin/clone.c
index efb1e6f..65c4cee 100644
--- a/builtin/clone.c
+++ b/builtin/clone.c
@@ -23,6 +23,7 @@
 #include "branch.h"
 #include "remote.h"
 #include "run-command.h"
+#include "narrow-tree.h"
 
 /*
  * Overall FIXMEs:
@@ -39,7 +40,7 @@ static const char * const builtin_clone_usage[] = {
 
 static int option_no_checkout, option_bare, option_mirror;
 static int option_local, option_no_hardlinks, option_shared, option_recursive;
-static char *option_template, *option_reference, *option_depth;
+static char *option_template, *option_reference, *option_depth, *option_narrow;
 static char *option_origin = NULL;
 static char *option_branch = NULL;
 static char *option_upload_pack = "git-upload-pack";
@@ -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, "narrow", &option_narrow, "tree",
+		   "narrow 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 (option_narrow)
+			die("--narrow is not really for local clone. Please consider --shared");
 		refs = clone_local(path, git_dir);
 		mapped_refs = wanted_peer_refs(refs, refspec);
 	} else {
@@ -530,6 +535,14 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 			transport_set_option(transport, TRANS_OPT_DEPTH,
 					     option_depth);
 
+		/* Do this early in order to set get_narrow_prefix() != NULL */
+		if (option_narrow) {
+			int fd = open(git_path("narrow"), O_RDWR | O_CREAT, 0644);
+			write(fd, option_narrow, strlen(option_narrow));
+			close(fd);
+			check_narrow_prefix();
+		}
+
 		transport_set_verbosity(transport, option_verbosity, option_progress);
 
 		if (option_upload_pack)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 20/32] narrow-tree: add join_narrow_tree to do tree fixup for commits

[Nguyễn Thái Ngọc Duy]

As stated somewhere, the index in narrow repo is also narrowed. When a
users are done with his changes and about to commit, the new narrow
tree created from index will be grafted back to a base toplevel tree
(usually from parent commit). The result is a new toplevel tree with
user's changes and suitable for commits.

This function does exactly that.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 narrow-tree.c |   66 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h |    2 +
 2 files changed, 68 insertions(+), 0 deletions(-)

diff --git a/narrow-tree.c b/narrow-tree.c
index 46e913d..73d4f22 100644
--- a/narrow-tree.c
+++ b/narrow-tree.c
@@ -1,4 +1,14 @@
 #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"
 #include "narrow-tree.h"
 
 static const char *narrow_prefix;
@@ -29,3 +39,59 @@ const char *get_narrow_prefix()
 {
 	return narrow_prefix;
 }
+
+/*
+ * The opposite of narrow_tree(). Put the subtree back to the original tree.
+ */
+int join_narrow_tree(const unsigned char *base,
+		     unsigned char *newsha1,
+		     const unsigned char *subtree_sha1,
+		     const char *prefix)
+{
+	struct tree_desc desc;
+	struct name_entry entry;
+	struct strbuf buffer;
+	enum object_type type;
+	const char *slash;
+	char *buf;
+	int subtree_len;
+	unsigned long size;
+
+	slash = strchr(prefix, '/');
+	subtree_len = slash ? slash - prefix : strlen(prefix);
+
+	buf = read_sha1_file(base, &type, &size);
+	if (!buf || type != OBJ_TREE)
+		die("Bad tree %s", sha1_to_hex(base));
+
+	init_tree_desc(&desc, buf, 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)) {
+			if (slash && slash[1]) /* trailing slash does not count */
+				join_narrow_tree(entry.sha1, newsha1,
+						 subtree_sha1, slash+1);
+			else
+				memcpy(newsha1, subtree_sha1, 20); /* replace the tree */
+
+			/* FIXME, what if placeholder tree does not exist? */
+
+			strbuf_add(&buffer, newsha1, 20);
+		}
+		else
+			strbuf_add(&buffer, entry.sha1, 20);
+	}
+
+	free(buf);
+	if (write_sha1_file(buffer.buf, buffer.len, tree_type, newsha1)) {
+		error("Could not write replaced tree for %s", sha1_to_hex(subtree_sha1));
+		strbuf_release(&buffer);
+		return 1;
+	}
+	strbuf_release(&buffer);
+	return 0;
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index aa8c94f..ecb3ded 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -1 +1,3 @@
 extern int check_narrow_prefix();
+extern int join_narrow_tree(const unsigned char *base, unsigned char *newsha1,
+			    const unsigned char *subtree_sha1, const char *prefix);
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 21/32] commit: add narrow's commit_tree version

[Nguyễn Thái Ngọc Duy]

The narrow version uses join_narrow_tree() to recreate a full tree
from a base toplevel tree (typically commit parent's tree) and a tree
created from index.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 commit.c |   21 +++++++++++++++++++++
 commit.h |    5 +++++
 2 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index 0094ec1..77ed9fd 100644
--- a/commit.c
+++ b/commit.c
@@ -6,6 +6,7 @@
 #include "diff.h"
 #include "revision.h"
 #include "notes.h"
+#include "narrow-tree.h"
 
 int save_commit_buffer = 1;
 
@@ -864,3 +865,23 @@ int commit_tree(const char *msg, unsigned char *tree,
 	strbuf_release(&buffer);
 	return result;
 }
+
+int commit_narrow_tree(const char *msg, unsigned char *tree,
+		       const unsigned char *narrow_base,
+		       struct commit_list *parents, unsigned char *ret,
+		       const char *author)
+{
+	unsigned char result_tree[20];
+
+	if (get_narrow_prefix()) {
+		unsigned char sha1[20];
+
+		if (!find_tree(tree, sha1, get_narrow_prefix()))
+			die("Narrow tree %s not found", get_narrow_prefix());
+		if (join_narrow_tree(narrow_base, result_tree, sha1,
+				     get_narrow_prefix()))
+			die("Failed to join tree");
+		tree = result_tree;
+	}
+	return commit_tree(msg, tree, parents, ret, author);
+}
diff --git a/commit.h b/commit.h
index 9113bbe..c718439 100644
--- a/commit.h
+++ b/commit.h
@@ -170,5 +170,10 @@ struct commit_list *reduce_heads(struct commit_list *heads);
 extern int commit_tree(const char *msg, unsigned char *tree,
 		struct commit_list *parents, unsigned char *ret,
 		const char *author);
+extern int commit_narrow_tree(const char *msg, unsigned char *tree,
+			      const unsigned char *narrow_base,
+			      struct commit_list *parents,
+			      unsigned char *ret,
+			      const char *author);
 
 #endif /* COMMIT_H */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 22/32] commit: use commit_narrow_tree() to support narrow repo

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/commit.c |   10 +++++++++-
 1 files changed, 9 insertions(+), 1 deletions(-)

diff --git a/builtin/commit.c b/builtin/commit.c
index 66fdd22..59da654 100644
--- a/builtin/commit.c
+++ b/builtin/commit.c
@@ -1351,7 +1351,15 @@ int cmd_commit(int argc, const char **argv, const char *prefix)
 		exit(1);
 	}
 
-	if (commit_tree(sb.buf, active_cache_tree->sha1, parents, commit_sha1,
+	if (get_narrow_prefix()) {
+		if (!parents)
+			die("Narrow mode does not support initial commit (yet)");
+		if (parse_commit(parents->item))
+			die("Bad commit %s", parents->item->object.sha1);
+	}
+	if (commit_narrow_tree(sb.buf, active_cache_tree->sha1,
+			parents ? parents->item->tree->object.sha1 : NULL,
+			parents, commit_sha1,
 			fmt_ident(author_name, author_email, author_date,
 				IDENT_ERROR_ON_NO_NAME))) {
 		rollback_index_files();
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 23/32] commit-tree: require --narrow-base in narrow repo

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/commit-tree.c |   20 +++++++++++++++++++-
 1 files changed, 19 insertions(+), 1 deletions(-)

diff --git a/builtin/commit-tree.c b/builtin/commit-tree.c
index 87f0591..0c71925 100644
--- a/builtin/commit-tree.c
+++ b/builtin/commit-tree.c
@@ -32,11 +32,29 @@ int cmd_commit_tree(int argc, const char **argv, const char *prefix)
 	unsigned char tree_sha1[20];
 	unsigned char commit_sha1[20];
 	struct strbuf buffer = STRBUF_INIT;
+	unsigned char narrow_base[20];
 
 	git_config(git_default_config, NULL);
 
 	if (argc < 2 || !strcmp(argv[1], "-h"))
 		usage(commit_tree_usage);
+
+	if (get_narrow_prefix()) {
+		unsigned char sha1[20];
+		unsigned long size;
+		void *buf;
+
+		if (prefixcmp(argv[1], "--narrow-base="))
+			die("--narrow-base required in narrow mode");
+		if (get_sha1(argv[1]+4, sha1))
+			die("Invalid SHA1");
+		buf = read_object_with_reference(sha1, tree_type, &size, narrow_base);
+		if (!buf)
+			die("Bad treeish %s", sha1_to_hex(sha1));
+		free(buf);
+		argv++;
+	}
+
 	if (get_sha1(argv[1], tree_sha1))
 		die("Not a valid object name %s", argv[1]);
 
@@ -56,7 +74,7 @@ int cmd_commit_tree(int argc, const char **argv, const char *prefix)
 	if (strbuf_read(&buffer, 0, 0) < 0)
 		die_errno("git commit-tree: failed to read");
 
-	if (!commit_tree(buffer.buf, tree_sha1, parents, commit_sha1, NULL)) {
+	if (!commit_narrow_tree(buffer.buf, tree_sha1, narrow_base, parents, commit_sha1, NULL)) {
 		printf("%s\n", sha1_to_hex(commit_sha1));
 		return 0;
 	}
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 24/32] merge: refuse to merge if narrow bases are different

[Nguyễn Thái Ngọc Duy]

commit_narrow_tree() works with a single narrow base. Unfortunately a
merge may have more than one parent. If all parents have the same
trees outside $GIT_DIR/narrow tree, then it's actually "a single
narrow base".

Other than that, refuse to merge. A merge in such case will need
server support because narrow repos do not have enough trees to
perform merge locally.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/merge.c |   18 ++++++++++++++++++
 narrow-tree.c   |   55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h   |    1 +
 3 files changed, 74 insertions(+), 0 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index 37ce4f5..c70d39d 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -25,6 +25,7 @@
 #include "help.h"
 #include "merge-recursive.h"
 #include "resolve-undo.h"
+#include "narrow-tree.h"
 
 #define DEFAULT_TWOHEAD (1<<0)
 #define DEFAULT_OCTOPUS (1<<1)
@@ -1048,6 +1049,23 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 			allow_trivial = 0;
 	}
 
+	if (get_narrow_prefix()) {
+		struct commit_list *item = remoteheads;
+		struct commit *head_commit = lookup_commit(head);
+
+		parse_commit(head_commit);
+		while (item) {
+			parse_commit(item->item);
+			if (!same_narrow_base(head_commit->tree->object.sha1,
+					      item->item->tree->object.sha1,
+					      get_narrow_prefix()))
+				break;
+			item = item->next;
+		}
+		if (item)
+			die("Different narrow base, couldn't do merge (yet)");
+	}
+
 	if (!remoteheads->next)
 		common = get_merge_bases(lookup_commit(head),
 				remoteheads->item, 1);
diff --git a/narrow-tree.c b/narrow-tree.c
index 73d4f22..4a16647 100644
--- a/narrow-tree.c
+++ b/narrow-tree.c
@@ -95,3 +95,58 @@ int join_narrow_tree(const unsigned char *base,
 	strbuf_release(&buffer);
 	return 0;
 }
+
+int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const char *prefix)
+{
+	struct tree_desc desc1, desc2;
+	struct name_entry entry1, entry2;
+	char *buf1, *buf2;
+	enum object_type type;
+	unsigned long size;
+	const char *slash;
+	int prefix_len;
+
+	slash = strchr(prefix, '/');
+	prefix_len = slash ? slash - prefix : strlen(prefix);
+
+	buf1 = read_sha1_file(t1, &type, &size);
+	if (type != OBJ_TREE)
+		die("Bad tree %s", sha1_to_hex(t1));
+	init_tree_desc(&desc1, buf1, size);
+
+	buf2 = read_sha1_file(t2, &type, &size);
+	if (type != OBJ_TREE)
+		die("Bad tree %s", sha1_to_hex(t2));
+	init_tree_desc(&desc2, buf2, size);
+
+	while (tree_entry(&desc1, &entry1) && tree_entry(&desc2, &entry2)) {
+		if (strcmp(entry1.path, entry2.path) ||
+		    entry1.mode != entry2.mode) {
+			free(buf1);
+			free(buf2);
+			return 0;
+		}
+
+		if (!hashcmp(entry1.sha1, entry2.sha1))
+			continue;
+
+		if (S_ISDIR(entry1.mode) &&
+		    !strncmp(entry1.path, prefix, prefix_len) &&
+		    entry1.path[prefix_len] == '\0') {
+
+			/* This is subtree, SHA-1 does not matter */
+			if (!slash)
+				continue;
+
+			if (same_narrow_base(entry1.sha1, entry2.sha1, slash+1))
+				continue;
+		}
+
+		free(buf1);
+		free(buf2);
+		return 0;
+	}
+	free(buf1);
+	free(buf2);
+	return !desc1.size && !desc2.size;
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index ecb3ded..8756094 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -1,3 +1,4 @@
 extern int check_narrow_prefix();
 extern int join_narrow_tree(const unsigned char *base, unsigned char *newsha1,
 			    const unsigned char *subtree_sha1, const char *prefix);
+int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const char *prefix);
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 25/32] merge: prepare commit properly in narrow mode

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/merge.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index c70d39d..d05c528 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -57,6 +57,7 @@ static size_t xopts_nr, xopts_alloc;
 static const char *branch;
 static int verbosity;
 static int allow_rerere_auto;
+static unsigned char narrow_base[20];
 
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
@@ -780,7 +781,8 @@ static int merge_trivial(void)
 	parent->next = xmalloc(sizeof(*parent->next));
 	parent->next->item = remoteheads->item;
 	parent->next->next = NULL;
-	commit_tree(merge_msg.buf, result_tree, parent, result_commit, NULL);
+	commit_narrow_tree(merge_msg.buf, result_tree, narrow_base,
+			   parent, result_commit, NULL);
 	finish(result_commit, "In-index merge");
 	drop_save();
 	return 0;
@@ -809,7 +811,8 @@ static int finish_automerge(struct commit_list *common,
 	}
 	free_commit_list(remoteheads);
 	strbuf_addch(&merge_msg, '\n');
-	commit_tree(merge_msg.buf, result_tree, parents, result_commit, NULL);
+	commit_narrow_tree(merge_msg.buf, result_tree, narrow_base,
+			   parents, result_commit, NULL);
 	strbuf_addf(&buf, "Merge made by %s.", wt_strategy);
 	finish(result_commit, buf.buf);
 	strbuf_release(&buf);
@@ -1064,6 +1067,7 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 		}
 		if (item)
 			die("Different narrow base, couldn't do merge (yet)");
+		hashcpy(narrow_base, lookup_commit(head)->tree->object.sha1);
 	}
 
 	if (!remoteheads->next)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 26/32] Add upload-narrow-base command

[Nguyễn Thái Ngọc Duy]

A narrow repo only has enough trees within a given subtree. That would
mean even a trivial three-way merge is impossible because it needs
full tree walk.

On the other hand, doing merge remotely is non-sense because conflicts
can happen, and there would be no index on remote side for people to
inspect/resolve conflicts. Such a merge in narrow repo would be
splitted into two phases: 3-way trivial merge for everything outside
narrow tree, and real merge within narrow tree.

The first phase is done in server by this command. Given two commits,
it will do 3-way merge and return result trees of the merge (no blob
should be created because this is trivial merge). No new objects will
be stored in server after this operation.

For local repo, parent trees of narrow tree should be enough for
join_narrow_tree() to do its job. But because remote side does not
store any result objects, in order to push a merge, we would need to
send all necessary trees that the remote side does not have.

For this reason, upload-narrow-base would return a pack of all new
trees (those that are not in either merge parents). It is expected
that git client would push all these trees back to server when it does
a push.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile                     |    1 +
 builtin.h                    |    1 +
 builtin/upload-narrow-base.c |  215 ++++++++++++++++++++++++++++++++++++++++++
 git.c                        |    1 +
 4 files changed, 218 insertions(+), 0 deletions(-)
 create mode 100644 builtin/upload-narrow-base.c

diff --git a/Makefile b/Makefile
index 54c435e..7b33a0e 100644
--- a/Makefile
+++ b/Makefile
@@ -737,6 +737,7 @@ BUILTIN_OBJS += builtin/update-index.o
 BUILTIN_OBJS += builtin/update-ref.o
 BUILTIN_OBJS += builtin/update-server-info.o
 BUILTIN_OBJS += builtin/upload-archive.o
+BUILTIN_OBJS += builtin/upload-narrow-base.o
 BUILTIN_OBJS += builtin/var.o
 BUILTIN_OBJS += builtin/verify-pack.o
 BUILTIN_OBJS += builtin/verify-tag.o
diff --git a/builtin.h b/builtin.h
index ed6ee26..0383328 100644
--- a/builtin.h
+++ b/builtin.h
@@ -131,6 +131,7 @@ extern int cmd_update_index(int argc, const char **argv, const char *prefix);
 extern int cmd_update_ref(int argc, const char **argv, const char *prefix);
 extern int cmd_update_server_info(int argc, const char **argv, const char *prefix);
 extern int cmd_upload_archive(int argc, const char **argv, const char *prefix);
+extern int cmd_upload_narrow_base(int argc, const char **argv, const char *prefix);
 extern int cmd_upload_tar(int argc, const char **argv, const char *prefix);
 extern int cmd_var(int argc, const char **argv, const char *prefix);
 extern int cmd_verify_tag(int argc, const char **argv, const char *prefix);
diff --git a/builtin/upload-narrow-base.c b/builtin/upload-narrow-base.c
new file mode 100644
index 0000000..f31f03e
--- /dev/null
+++ b/builtin/upload-narrow-base.c
@@ -0,0 +1,215 @@
+#include "cache.h"
+#include "builtin.h"
+#include "cache-tree.h"
+#include "diff.h"
+#include "diffcore.h"
+#include "commit.h"
+#include "revision.h"
+#include "unpack-trees.h"
+#include "pkt-line.h"
+#include "pack.h"
+#include "transport.h"
+#include "sideband.h"
+
+const char *narrow_prefix;
+
+#define PARENT1		(1u<<16)
+#define PARENT2		(1u<<17)
+
+static void write_object(struct tree *t,
+			 const char *base,
+			 struct simple_pack *pack)
+{
+	struct name_entry entry;
+	struct tree *subtree;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	int len = 0;
+	void *buffer;
+	char *path = xmalloc(PATH_MAX);
+
+	if (base) {
+		len = strlen(base);
+		memcpy(path, base, len);
+		path[len++] = '/';
+	}
+
+	buffer = read_sha1_file(t->object.sha1, &type, &size);
+	if (!buffer || type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(t->object.sha1));
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+
+		subtree = lookup_tree(entry.sha1);
+		strcpy(path+len, entry.path);
+		if (!strcmp(path, narrow_prefix))
+			;
+		else if (!prefixcmp(narrow_prefix, path) && /* subtree predecessor */
+			 narrow_prefix[strlen(path)] == '/')
+			;
+		else if (!(subtree->object.flags & (PARENT1 | PARENT2))) {
+			subtree->object.flags |= TMP_MARK; /* non recursive */
+			write_object_to_pack(pack, entry.sha1, subtree->buffer,
+					     subtree->size, OBJ_TREE);
+		}
+
+		write_object(subtree, path, pack);
+	}
+	free(path);
+	free(buffer);
+}
+
+static int read_tree_trivial(struct tree *trees[3])
+{
+	int i;
+	struct tree_desc t[3];
+	struct unpack_trees_options opts;
+
+	memset(&opts, 0, sizeof(opts));
+	opts.head_idx = 2;
+	opts.src_index = &the_index;
+	opts.dst_index = &the_index;
+	opts.merge = 1;
+	opts.fn = threeway_merge;
+	cache_tree_free(&active_cache_tree);
+	for (i = 0; i < 3; i++) {
+		parse_tree(trees[i]);
+		init_tree_desc(t+i, trees[i]->buffer, trees[i]->size);
+	}
+	if (unpack_trees(3, t, &opts))
+		return -1;
+	return 0;
+}
+
+static int create_tree_object(const void *buf, unsigned long len,
+			      const char *type, unsigned char *sha1)
+{
+	struct tree *t;
+	if (type != tree_type)
+		die("Invalid type %s", type);
+	hash_sha1_file(buf, len, tree_type, sha1);
+	t = lookup_tree(sha1);
+	if (!t->object.parsed) {
+		t->buffer = xmalloc(len);
+		memcpy(t->buffer, buf, len);
+		t->size = len;
+		t->object.parsed = 1;
+	}
+	return 0;
+}
+
+int cmd_upload_narrow_base(int argc, const char **argv, const char *prefix)
+{
+	char buf[LARGE_PACKET_MAX];
+	unsigned char sha1[2][20];
+	struct tree *t[3];
+	struct commit_list *common;
+	struct simple_pack pack;
+	int i, len;
+
+	strcpy(buf, argv[1]); /* enter-repo smudges its argument */
+
+	if (!enter_repo(buf, 0))
+		die("'%s' does not appear to be a git repository", buf);
+
+	len = packet_read_line(0, buf, sizeof(buf));
+	if (!len)
+		die("narrow-merge: narrow-tree missing");
+	if (!prefixcmp(buf, "narrow-tree ")) {
+		narrow_prefix = xstrdup(buf+12);
+		len = strlen(narrow_prefix);
+		if (!len)
+			die("narrow-merge: empty narrow-tree");
+		if (narrow_prefix[len-1] == '/')
+			die("narrow-merge: trailing slash not allowed %s", narrow_prefix);
+	}
+	else
+		die("narrow-merge: invalid narrow-tree %s", buf);
+
+	for (i = 0; i < 2; i++) {
+		len = packet_read_line(0, buf, sizeof(buf));
+		if (!len)
+			die("narrow-merge: parent missing");
+		if (!prefixcmp(buf, "parent ")) {
+			if (get_sha1_hex(buf+7, sha1[i]))
+				die("narrow-merge: invalid SHA1 %s", buf);
+			if (!lookup_commit_reference(sha1[i]))
+				return 1;
+		}
+		else
+			die("narrow-merge: invalid parent %s", buf);
+	}
+	len = packet_read_line(0, buf, sizeof(buf));
+	if (len)
+		die("narrow-merge: expected a flush");
+
+	common = get_merge_bases(lookup_commit(sha1[0]),
+				 lookup_commit(sha1[1]),
+				 1);
+	if (!common || common->next)
+		die("narrow-merge: no common or too many common found, can't merge");
+
+	t[0] = common->item->tree;
+	t[1] = lookup_commit(sha1[0])->tree;
+	t[2] = lookup_commit(sha1[1])->tree;
+
+	/* Three way merge to index */
+	discard_index(&the_index);
+	if (read_tree_trivial(t))
+		die("narrow-merge: non trivial merge");
+
+	/* Make sure merge is good (no conflicts outside subtree) */
+	len = strlen(narrow_prefix);
+	for (i = 0; i < the_index.cache_nr; i++) {
+		struct cache_entry *ce = the_index.cache[i];
+
+		/*
+		 * No staged entries within subtree, prefer stage 1:
+		 * (the goal is no staged entries, the content is
+		 * not really important as subtree client must do
+		 * a real merge within subtree)
+		 * stage 0: move on
+		 * stage 1: turn it to stage 0,
+		 * stage 2: mark CE_REMOVE
+		 */
+		if (!prefixcmp(ce->name, narrow_prefix) &&
+		    ce->name[len] == '/') {
+			switch (ce_stage(ce)) {
+			case 1: ce->ce_flags &= ~CE_STAGEMASK; break;
+			case 2: ce->ce_flags |= CE_REMOVE; break;
+			}
+			continue;
+		}
+		if (ce_stage(ce))
+			die("git upload-pack: unmerged entry %s", ce->name);
+	}
+
+	/* Generate trees in memory */
+	the_index.cache_tree = cache_tree();
+	if (cache_tree_update_fn(the_index.cache_tree,
+				 the_index.cache,
+				 the_index.cache_nr,
+				 create_tree_object,
+				 0, 0))
+		die("narrow-merge: error generating trees");
+
+	/* Everything is OK. Send root SHA-1 */
+	packet_write(1, "ACK %s\n", sha1_to_hex(the_index.cache_tree->sha1));
+
+	/* Traverse and send only missing trees */
+	memset(&pack, 0, sizeof(pack));
+	pack.fd = 1;
+	create_pack(&pack);
+
+	t[0] = lookup_tree(the_index.cache_tree->sha1);
+	set_tree_marks(t[1], PARENT1);
+	set_tree_marks(t[2], PARENT2);
+	write_object(t[0], NULL, &pack);
+
+	close_pack(&pack);
+	return 0;
+}
diff --git a/git.c b/git.c
index f37028b..edb379f 100644
--- a/git.c
+++ b/git.c
@@ -392,6 +392,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "update-ref", cmd_update_ref, RUN_SETUP },
 		{ "update-server-info", cmd_update_server_info, RUN_SETUP },
 		{ "upload-archive", cmd_upload_archive },
+		{ "upload-narrow-base", cmd_upload_narrow_base },
 		{ "var", cmd_var },
 		{ "verify-tag", cmd_verify_tag, RUN_SETUP },
 		{ "version", cmd_version },
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 27/32] rev-list: traverse some more trees to make upload-narrow-base happy

[Nguyễn Thái Ngọc Duy]

When in narrow repo and a merge is met, just traverse every valid
trees that could be found, regardless whether they are in narrow tree.

This is a weak point because fsck won't be able to find out missing
trees. Hopefully the remote end won't accept incomplete push.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 list-objects.c |   61 +++++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 58 insertions(+), 3 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index 7014926..ccdd64b 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -62,7 +62,8 @@ static void process_tree(struct rev_info *revs,
 			 show_object_fn show,
 			 struct name_path *path,
 			 const char *name,
-			 const char *subtree)
+			 const char *subtree,
+			 int recursive)
 {
 	struct object *obj = &tree->object;
 	struct tree_desc desc;
@@ -81,6 +82,10 @@ static void process_tree(struct rev_info *revs,
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
 	obj->flags |= SEEN;
 	show(obj, path, name);
+
+	if (!recursive)
+		return;
+
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -112,7 +117,8 @@ static void process_tree(struct rev_info *revs,
 			process_tree(revs,
 				     lookup_tree(entry.sha1),
 				     show, &me, entry.path,
-				     slash ? slash+1 : NULL);
+				     slash ? slash+1 : NULL,
+				     1);
 		else if (S_ISGITLINK(entry.mode))
 			process_gitlink(revs, entry.sha1,
 					show, &me, entry.path);
@@ -163,6 +169,48 @@ static void add_pending_tree(struct rev_info *revs, struct tree *tree)
 	add_pending_object(revs, &tree->object, "");
 }
 
+static void add_pending_reachable_tree(struct rev_info *revs,
+				       const unsigned char *sha1,
+				       const char *base)
+{
+	struct name_entry entry;
+	struct object *subtree;
+	struct tree_desc desc;
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+	char *path = xmalloc(PATH_MAX);
+	int len;
+
+	buffer = read_sha1_file(sha1, &type, &size);
+	if (!buffer) {
+		free(path);
+		return;
+	}
+	if (type != OBJ_TREE)
+		die("%s is not a tree", sha1_to_hex(sha1));
+
+	len = strlen(base);
+	memcpy(path, base, len);
+	path[len++] = '/';
+
+	init_tree_desc(&desc, buffer, size);
+	while (tree_entry(&desc, &entry)) {
+		if (!S_ISDIR(entry.mode))
+			continue;
+
+		subtree = lookup_object(entry.sha1);
+		strcpy(path+len, entry.path);
+		if (subtree) {
+			subtree->flags |= TMP_MARK; /* non recursive */
+			add_pending_object(revs, subtree, xstrdup(path));
+		}
+		add_pending_reachable_tree(revs, entry.sha1, path);
+	}
+	free(path);
+	free(buffer);
+}
+
 void traverse_commit_list(struct rev_info *revs,
 			  show_commit_fn show_commit,
 			  show_object_fn show_object,
@@ -177,6 +225,8 @@ void traverse_commit_list(struct rev_info *revs,
 	}
 
 	while ((commit = get_revision(revs)) != NULL) {
+		if (get_narrow_prefix())
+			add_pending_reachable_tree(revs, commit->tree->object.sha1, "");
 		add_pending_tree(revs, commit->tree);
 		show_commit(commit, data);
 	}
@@ -194,7 +244,12 @@ void traverse_commit_list(struct rev_info *revs,
 		if (obj->type == OBJ_TREE) {
 			process_tree(revs, (struct tree *)obj, show_object,
 				     NULL, name,
-				     revs->narrow_tree ? revs->narrow_prefix : NULL);
+				     revs->narrow_tree ? revs->narrow_prefix : NULL,
+				     (obj->flags & TMP_MARK) == 0);
+			if (obj->flags & TMP_MARK) {
+				obj->flags &= ~TMP_MARK;
+				//free((char*)name);
+			}
 			continue;
 		}
 		if (obj->type == OBJ_BLOB) {
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 28/32] narrow-tree: add oldest_narrow_base()

[Nguyễn Thái Ngọc Duy]

This function helps solve another problem at client. Because
upload-narrow-base receives commits. What if they don't have those
commits because they are created locally?

The solution is to find the oldest commits that still have the same
narrow base (trees outside narrow tree) and use those commits with
hope that the server side also have them.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 narrow-tree.c |   48 ++++++++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h |    1 +
 2 files changed, 49 insertions(+), 0 deletions(-)

diff --git a/narrow-tree.c b/narrow-tree.c
index 4a16647..f1b8902 100644
--- a/narrow-tree.c
+++ b/narrow-tree.c
@@ -150,3 +150,51 @@ int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const cha
 	free(buf2);
 	return !desc1.size && !desc2.size;
 }
+
+int oldest_narrow_base(const unsigned char *sha1, unsigned char *newsha1)
+{
+	enum object_type type;
+	unsigned long size;
+	char *buf, *bufptr;
+	unsigned char base[20], newbase[20], parent[20];
+
+	buf = read_sha1_file(sha1, &type, &size);
+	if (!buf || type != OBJ_COMMIT) {
+		if (buf)
+			free(buf);
+		error("Not a commit %s", sha1_to_hex(sha1));
+		return 1;
+	}
+	get_sha1_hex(buf+5, base);
+	hashcpy(newsha1, sha1);
+
+	while (1) {
+		bufptr = buf + 46;	/* "tree " + "hex sha1" + "\n" */
+		if (!memcmp(bufptr, "parent ", 7)) {
+
+			/* more than one parent, a merge */
+			if (!memcmp(bufptr + 48, "parent ", 7))
+				break;
+
+			free(buf);
+			get_sha1_hex(bufptr + 7, parent);
+			buf = read_sha1_file(parent, &type, &size);
+			if (!buf ||type != OBJ_COMMIT) {
+				if (buf)
+					free(buf);
+				error("Not a commit %s", sha1_to_hex(sha1));
+				return 1;
+			}
+			get_sha1_hex(buf+5, newbase);
+			if (!same_narrow_base(base, newbase, get_narrow_prefix()))
+				break;
+
+			hashcpy(newsha1, parent);
+			/* keep searching */
+		}
+		else		/* root commit */
+			break;
+	}
+	free(buf);
+	return 0;
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index 8756094..78d6f39 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -2,3 +2,4 @@ extern int check_narrow_prefix();
 extern int join_narrow_tree(const unsigned char *base, unsigned char *newsha1,
 			    const unsigned char *subtree_sha1, const char *prefix);
 int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const char *prefix);
+int oldest_narrow_base(const unsigned char *sha1, unsigned char *newsha1);
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 29/32] Add command fetch-narrow-base

[Nguyễn Thái Ngọc Duy]

This is the client side of upload-narrow-base. It sends two commits, a
narrow prefix, receives a pack and unpacks it.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Makefile                    |    1 +
 builtin.h                   |    1 +
 builtin/fetch-narrow-base.c |   89 +++++++++++++++++++++++++++++++++++++++++++
 git.c                       |    1 +
 narrow-tree.h               |    4 ++
 5 files changed, 96 insertions(+), 0 deletions(-)
 create mode 100644 builtin/fetch-narrow-base.c

diff --git a/Makefile b/Makefile
index 7b33a0e..a10eb00 100644
--- a/Makefile
+++ b/Makefile
@@ -676,6 +676,7 @@ BUILTIN_OBJS += builtin/diff-index.o
 BUILTIN_OBJS += builtin/diff-tree.o
 BUILTIN_OBJS += builtin/diff.o
 BUILTIN_OBJS += builtin/fast-export.o
+BUILTIN_OBJS += builtin/fetch-narrow-base.o
 BUILTIN_OBJS += builtin/fetch-pack.o
 BUILTIN_OBJS += builtin/fetch.o
 BUILTIN_OBJS += builtin/fmt-merge-msg.o
diff --git a/builtin.h b/builtin.h
index 0383328..9eefa0f 100644
--- a/builtin.h
+++ b/builtin.h
@@ -66,6 +66,7 @@ extern int cmd_diff(int argc, const char **argv, const char *prefix);
 extern int cmd_diff_tree(int argc, const char **argv, const char *prefix);
 extern int cmd_fast_export(int argc, const char **argv, const char *prefix);
 extern int cmd_fetch(int argc, const char **argv, const char *prefix);
+extern int cmd_fetch_narrow_base(int argc, const char **argv, const char *prefix);
 extern int cmd_fetch_pack(int argc, const char **argv, const char *prefix);
 extern int cmd_fmt_merge_msg(int argc, const char **argv, const char *prefix);
 extern int cmd_for_each_ref(int argc, const char **argv, const char *prefix);
diff --git a/builtin/fetch-narrow-base.c b/builtin/fetch-narrow-base.c
new file mode 100644
index 0000000..0162ad0
--- /dev/null
+++ b/builtin/fetch-narrow-base.c
@@ -0,0 +1,89 @@
+#include "cache.h"
+#include "builtin.h"
+#include "commit.h"
+#include "pkt-line.h"
+#include "transport.h"
+#include "sideband.h"
+#include "run-command.h"
+#include "parse-options.h"
+
+int fetch_narrow_base(const unsigned char *c1,
+		      const unsigned char *c2,
+		      unsigned char *newsha1,
+		      const char *narrow_prefix,
+		      const char *remote,
+		      const char *exec)
+{
+	char buf[LARGE_PACKET_MAX];
+	int fd[2], len;
+	struct transport *transport;
+	struct remote *_remote;
+	const char *argv[] = { "unpack-objects", "-q", NULL };
+	struct child_process cmd;
+
+	_remote = remote_get(remote);
+	if (!_remote->url[0])
+		die("narrow-base: Remote with no URL");
+	transport = transport_get(_remote, _remote->url[0]);
+	if (!exec)
+		exec = "git-upload-narrow-base";
+	transport_connect(transport, "git-upload-narrow-base", exec, fd);
+
+	packet_write(fd[1], "narrow-tree %s\n", narrow_prefix);
+	packet_write(fd[1], "parent %s\n", sha1_to_hex(c1));
+	packet_write(fd[1], "parent %s\n", sha1_to_hex(c2));
+	packet_flush(fd[1]);
+
+	len = packet_read_line(fd[0], buf, sizeof(buf));
+	if (!len)
+		die("narrow-base: expected ACK/NAK, got EOF");
+	if (buf[len-1] == '\n')
+		buf[--len] = 0;
+	if (prefixcmp(buf, "ACK "))
+		die("narrow-base: protocol error");
+
+	get_sha1_hex(buf+4, newsha1);
+
+	memset(&cmd, 0, sizeof(cmd));
+	cmd.argv = argv;
+	cmd.in = fd[0];
+	cmd.git_cmd = 1;
+
+	if (run_command(&cmd))
+		die("unable to run %s", argv[0]);
+
+	return transport_disconnect(transport);
+}
+
+int cmd_fetch_narrow_base(int argc, const char **argv, const char *prefix)
+{
+	unsigned char c1[20], c2[20], sha1[20];
+	const char *remote;
+	const char *exec;
+	const char *narrow_prefix = get_narrow_prefix();
+	struct option options[] = {
+		OPT_STRING(0, "remote", &remote, "remote", "remote host"),
+		OPT_STRING(0, "upload-narrow-base", &exec, "path", "path to upload-narrow-base"),
+		OPT_STRING(0, "narrow-tree", &narrow_prefix, "narrow prefix", "narrow prefix"),
+		OPT_END()
+	};
+	const char *usage[] = { "git narrow-base [options] parent1 parent2", NULL };
+
+	argc = parse_options(argc, argv, prefix, options, usage, 0);
+
+	if (argc != 2)
+		die("Insufficient arguments");
+
+	if (get_sha1(argv[0], c1) ||
+	    get_sha1(argv[1], c2) ||
+	    !lookup_commit_reference(c1) ||
+	    !lookup_commit_reference(c2))
+		return 1;
+
+	if (!fetch_narrow_base(c1, c2, sha1, narrow_prefix, remote, exec)) {
+		printf("%s\n", sha1_to_hex(sha1));
+		return 0;
+	}
+
+	return 1;
+}
diff --git a/git.c b/git.c
index edb379f..f4370b1 100644
--- a/git.c
+++ b/git.c
@@ -322,6 +322,7 @@ static void handle_internal_command(int argc, const char **argv)
 		{ "diff-tree", cmd_diff_tree, RUN_SETUP },
 		{ "fast-export", cmd_fast_export, RUN_SETUP },
 		{ "fetch", cmd_fetch, RUN_SETUP },
+		{ "fetch-narrow-base", cmd_fetch_narrow_base, RUN_SETUP },
 		{ "fetch-pack", cmd_fetch_pack, RUN_SETUP },
 		{ "fmt-merge-msg", cmd_fmt_merge_msg, RUN_SETUP },
 		{ "for-each-ref", cmd_for_each_ref, RUN_SETUP },
diff --git a/narrow-tree.h b/narrow-tree.h
index 78d6f39..614d677 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -3,3 +3,7 @@ extern int join_narrow_tree(const unsigned char *base, unsigned char *newsha1,
 			    const unsigned char *subtree_sha1, const char *prefix);
 int same_narrow_base(const unsigned char *t1, const unsigned char *t2, const char *prefix);
 int oldest_narrow_base(const unsigned char *sha1, unsigned char *newsha1);
+int fetch_narrow_base(const unsigned char *c1, const unsigned char *c2,
+		      unsigned char *newsha1,
+		      const char *narrow_prefix,
+		      const char *remote, const char *exec);
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 30/32] merge: support merging when narrow bases are different

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/merge.c |   25 ++++++++++++++++++++++---
 1 files changed, 22 insertions(+), 3 deletions(-)

diff --git a/builtin/merge.c b/builtin/merge.c
index d05c528..1c70193 100644
--- a/builtin/merge.c
+++ b/builtin/merge.c
@@ -58,6 +58,7 @@ static const char *branch;
 static int verbosity;
 static int allow_rerere_auto;
 static unsigned char narrow_base[20];
+static const char *narrow_remote, *narrow_exec;
 
 static struct strategy all_strategy[] = {
 	{ "recursive",  DEFAULT_TWOHEAD | NO_TRIVIAL },
@@ -195,6 +196,10 @@ static struct option builtin_merge_options[] = {
 	OPT_CALLBACK('m', "message", &merge_msg, "message",
 		"message to be used for the merge commit (if any)",
 		option_parse_message),
+	OPT_STRING(0, "remote", &narrow_remote, "repo",
+		   "remote repo to perform narrow base calculation"),
+	OPT_STRING(0, "upload-narrow-base", &narrow_exec, "path",
+		   "path to git-upload-narrow-base"),
 	OPT__VERBOSITY(&verbosity),
 	OPT_END()
 };
@@ -1065,9 +1070,23 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 				break;
 			item = item->next;
 		}
-		if (item)
-			die("Different narrow base, couldn't do merge (yet)");
-		hashcpy(narrow_base, lookup_commit(head)->tree->object.sha1);
+		if (item) {
+			unsigned char sha1[2][20];
+
+			if (remoteheads->next)
+				die("Octopus merge is not supported in narrow repository");
+			if (!narrow_remote)
+				die("This merge cannot be fully performed locally.\n"
+				    "Please specify remote repo with --remote.");
+			oldest_narrow_base(head, sha1[0]);
+			oldest_narrow_base(remoteheads->item->object.sha1, sha1[1]);
+			if (fetch_narrow_base(sha1[0], sha1[1], narrow_base,
+					      get_narrow_prefix(),
+					      narrow_remote, narrow_exec))
+				die("Failed to request narrow base from remote repo");
+		}
+		else
+			hashcpy(narrow_base, lookup_commit(head)->tree->object.sha1);
 	}
 
 	if (!remoteheads->next)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 31/32] send-pack: do not use thin pack in narrow mode

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/send-pack.c |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/builtin/send-pack.c b/builtin/send-pack.c
index 481602d..c2138df 100644
--- a/builtin/send-pack.c
+++ b/builtin/send-pack.c
@@ -457,6 +457,10 @@ int cmd_send_pack(int argc, const char **argv, const char *prefix)
 	}
 	if (!dest)
 		usage(send_pack_usage);
+
+	if (get_narrow_prefix())
+		args.use_thin_pack = 0;
+
 	/*
 	 * --all and --mirror are incompatible; neither makes sense
 	 * with any refspecs.
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 32/32] daemon: support upload-narrow-base

[Nguyễn Thái Ngọc Duy]

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 daemon.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)

diff --git a/daemon.c b/daemon.c
index e22a2b7..58794b7 100644
--- a/daemon.c
+++ b/daemon.c
@@ -356,6 +356,12 @@ static int upload_archive(void)
 	return run_service_command(argv);
 }
 
+static int upload_narrow_base(void)
+{
+	static const char *argv[] = { "upload-narrow-base", ".", NULL };
+	return run_service_command(argv);
+}
+
 static int receive_pack(void)
 {
 	static const char *argv[] = { "receive-pack", ".", NULL };
@@ -364,6 +370,7 @@ static int receive_pack(void)
 
 static struct daemon_service daemon_service[] = {
 	{ "upload-archive", "uploadarch", upload_archive, 0, 1 },
+	{ "upload-narrow-base", "narrowbase", upload_narrow_base, 0, 1 },
 	{ "upload-pack", "uploadpack", upload_pack, 1, 1 },
 	{ "receive-pack", "receivepack", receive_pack, 0, 1 },
 };
-- 
1.7.1.rc1.69.g24c2f7

Re: [RFD PATCH 00/32] subtree clone v2

[Jonathan Nieder]

Nguyễn Thái Ngọc Duy wrote:

> Patches 26..30
>   Add upload-narrow-base command
>   rev-list: traverse some more trees to make upload-narrow-base happy
>   narrow-tree: add oldest_narrow_base()
>   Add command fetch-narrow-base
>   merge: support merging when narrow bases are different
> 
> Remote merge part.
> 
> Split a merge operation into two parts, the real merge will be done
> within narrow tree. Conflicts can happen and be resolved in the narrow
> index, locally.
> 
> Everything outside narrow tree will be merged (trivially) by
> server. Then server sends the base tree back, so join_narrow_tree() in
> patch 20 can be used to create proper commit.
> 
> Server can disable this remote merge feature, which means users are
> forced to do rebase/fast-forward. Not too bad.

Yikes.  Naïve question (please forgive my laziness): is it possible to
merge without remote contact in the boring case, when no changes have
occured outside the narrow tree?

Re: [PATCH 02/32] cache-tree: abstract out write_sha1_file from cache_tree_update()

[Jonathan Nieder]

Nguyễn Thái Ngọc Duy wrote:

> This allows cache-tree to produce trees directly in a pack, for instance.

Neat.

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 8:37 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Nguyễn Thái Ngọc Duy wrote:
>
>> Patches 26..30
>>   Add upload-narrow-base command
>>   rev-list: traverse some more trees to make upload-narrow-base happy
>>   narrow-tree: add oldest_narrow_base()
>>   Add command fetch-narrow-base
>>   merge: support merging when narrow bases are different
>>
>> Remote merge part.
>>
>> Split a merge operation into two parts, the real merge will be done
>> within narrow tree. Conflicts can happen and be resolved in the narrow
>> index, locally.
>>
>> Everything outside narrow tree will be merged (trivially) by
>> server. Then server sends the base tree back, so join_narrow_tree() in
>> patch 20 can be used to create proper commit.
>>
>> Server can disable this remote merge feature, which means users are
>> forced to do rebase/fast-forward. Not too bad.
>
> Yikes.  Naïve question (please forgive my laziness): is it possible to
> merge without remote contact in the boring case, when no changes have
> occured outside the narrow tree?

That's possible (and is implemented in my series). But I guess as soon
as you do "git pull", the boring case is likely not applicable
anymore.
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Jonathan Nieder]

Nguyen Thai Ngoc Duy wrote:
> On Wed, Aug 25, 2010 at 8:37 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:

>> is it possible to
>> merge without remote contact in the boring case, when no changes have
>> occured outside the narrow tree?
>
> That's possible (and is implemented in my series). But I guess as soon
> as you do "git pull", the boring case is likely not applicable
> anymore.

Makes sense.

One slightly less boring case.  Is it possible to merge when the
simplified history, looking only at changes outside the narrow tree,
would have permitted a fast-forward?

If so, a git contributor who is only interested in Documentation/
could work on "next" between releases and keep up with "maint" and
"master" longer term, without the help of a full-tree-merging machine.

More realistically, a linux-2.6 contributor only interested in one
subsystem could always keep up with "master".  Which would be nice.

Re: [PATCH 03/32] cache-tree: ignore CE_REMOVE entries in verify_cache()

[Jonathan Nieder]

Nguyễn Thái Ngọc Duy wrote:

> --- a/cache-tree.c
> +++ b/cache-tree.c
> @@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
>  	funny = 0;
>  	for (i = 0; i < entries; i++) {
>  		struct cache_entry *ce = cache[i];
> +		if (ce->ce_flags & CE_REMOVE)
> +			continue;
>  		if (ce_stage(ce) || (ce->ce_flags & CE_INTENT_TO_ADD)) {
>  			if (10 < ++funny) {
>  				fprintf(stderr, "...\n");

In other words, this teaches internal write-tree callers to ignore
unmerged and intent-to-add entries marked with CE_REMOVE.

Why?  When does this come up?

Re: [PATCH 04/32] move do_compress() from pack-objects.c to pack-write.c

[Jonathan Nieder]

Nguyễn Thái Ngọc Duy wrote:

> Subject: [PATCH 04/32] move do_compress() from pack-objects.c to pack-write.c

exposing it as internal API.  Makes sense.

> +unsigned long compress_object(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;
> +}

However, there is nothing particularly specialized to git objects
about this.  e.g. deflate_it() from diff.c could use this.

Re: [PATCH 09/32] index: make narrow index incompatible with older git

[Jonathan Nieder]

Nguyễn Thái Ngọc Duy wrote:

> Index in narrow repos is not a full index and should not be used
> to create commits without modification (to be explained later on).
[...]
> +++ b/read-cache.c
> @@ -25,8 +25,9 @@ static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int reall
>   */
>  
>  #define CACHE_EXT(s) ( (s[0]<<24)|(s[1]<<16)|(s[2]<<8)|(s[3]) )
> -#define CACHE_EXT_TREE 0x54524545	/* "TREE" */
> +#define CACHE_EXT_TREE 0x54524545	  /* "TREE" */
>  #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* "REUC" */
> +#define CACHE_EXT_NARROW 0x4e415257	  /* "NARW" */

Just curious: why aren't we using

 #define CACHE_EXT_TREE CACHE_EXT("TREE")
 #define CACHE_EXT_RESOLVE_UNDO CACHE_EXT("REUC")
 #define CACHE_EXT_NARROW CACHE_EXT("NARW")

Are they invalid case labels?

I think non-optional extensions might need to be lowercase ("narw")
though I am not sure.

> @@ -1168,7 +1169,9 @@ static int verify_hdr(struct cache_header *hdr, unsigned long size)
>  
>  	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
>  		return error("bad signature");
> -	if (hdr->hdr_version != htonl(2) && hdr->hdr_version != htonl(3))
> +	if (hdr->hdr_version != htonl(2) &&
> +	    hdr->hdr_version != htonl(3) &&
> +	    hdr->hdr_version != htonl(4))
>  		return error("bad index version");
[...]
> @@ -1568,7 +1584,11 @@ int write_index(struct index_state *istate, int newfd)
[...]
> +	if (get_narrow_prefix() && ver < 4)
> +		ver = 4;	/* narrow-unaware git should to touch this index */
> +
> +	hdr.hdr_version = htonl(ver);
>  	hdr.hdr_entries = htonl(entries - removed);
>  
>  	git_SHA1_Init(&c);

Oh, or you can do this. :)

Thanks for a pleasant read.  Looks good so far, though I didn't read
the tests.

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 9:09 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Nguyen Thai Ngoc Duy wrote:
>> On Wed, Aug 25, 2010 at 8:37 AM, Jonathan Nieder <jrnieder@gmail.com>
>> wrote:
>
>>> is it possible to
>>> merge without remote contact in the boring case, when no changes have
>>> occured outside the narrow tree?
>>
>> That's possible (and is implemented in my series). But I guess as soon
>> as you do "git pull", the boring case is likely not applicable
>> anymore.
>
> Makes sense.
>
> One slightly less boring case.  Is it possible to merge when the
> simplified history, looking only at changes outside the narrow tree,
> would have permitted a fast-forward?

Yes, as long as there is no changes outside narrow tree.

>
> If so, a git contributor who is only interested in Documentation/
> could work on "next" between releases and keep up with "maint" and
> "master" longer term, without the help of a full-tree-merging machine.
>
> More realistically, a linux-2.6 contributor only interested in one
> subsystem could always keep up with "master".  Which would be nice.
>



-- 
Duy

Re: [PATCH 03/32] cache-tree: ignore CE_REMOVE entries in verify_cache()

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 9:15 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Nguyễn Thái Ngọc Duy wrote:
>
>> --- a/cache-tree.c
>> +++ b/cache-tree.c
>> @@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
>>       funny = 0;
>>       for (i = 0; i < entries; i++) {
>>               struct cache_entry *ce = cache[i];
>> +             if (ce->ce_flags & CE_REMOVE)
>> +                     continue;
>>               if (ce_stage(ce) || (ce->ce_flags & CE_INTENT_TO_ADD)) {
>>                       if (10 < ++funny) {
>>                               fprintf(stderr, "...\n");
>
> In other words, this teaches internal write-tree callers to ignore
> unmerged and intent-to-add entries marked with CE_REMOVE.
>
> Why?  When does this come up?

I was lazy. In patch 26, upload-narrow-merge do three way merge and
drop staged entries within narrow tree (this is at server side,
conflicts within narrow tree will be handled at client side later).
Instead of removing staged entries, I mark them CE_REMOVE.
-- 
Duy

Re: [PATCH 09/32] index: make narrow index incompatible with older git

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 9:43 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
> Nguyễn Thái Ngọc Duy wrote:
>
>> Index in narrow repos is not a full index and should not be used
>> to create commits without modification (to be explained later on).
> [...]
>> +++ b/read-cache.c
>> @@ -25,8 +25,9 @@ static struct cache_entry *refresh_cache_entry(struct
>> cache_entry *ce, int reall
>>   */
>>
>>  #define CACHE_EXT(s) ( (s[0]<<24)|(s[1]<<16)|(s[2]<<8)|(s[3]) )
>> -#define CACHE_EXT_TREE 0x54524545    /* "TREE" */
>> +#define CACHE_EXT_TREE 0x54524545      /* "TREE" */
>>  #define CACHE_EXT_RESOLVE_UNDO 0x52455543 /* "REUC" */
>> +#define CACHE_EXT_NARROW 0x4e415257    /* "NARW" */
>
> Just curious: why aren't we using
>
>  #define CACHE_EXT_TREE CACHE_EXT("TREE")
>  #define CACHE_EXT_RESOLVE_UNDO CACHE_EXT("REUC")
>  #define CACHE_EXT_NARROW CACHE_EXT("NARW")
>
> Are they invalid case labels?
>
> I think non-optional extensions might need to be lowercase ("narw")
> though I am not sure.

No idea. I need to dig into history to figure it out later.
-- 
Duy

Re: [PATCH 03/32] cache-tree: ignore CE_REMOVE entries in verify_cache()

[Jonathan Nieder]

Nguyen Thai Ngoc Duy wrote:
>> Nguyễn Thái Ngọc Duy wrote:

>>> --- a/cache-tree.c
>>> +++ b/cache-tree.c
>>> @@ -156,6 +156,8 @@ static int verify_cache(struct cache_entry **cache,
>>>       funny = 0;
>>>       for (i = 0; i < entries; i++) {
>>>               struct cache_entry *ce = cache[i];
>>> +             if (ce->ce_flags & CE_REMOVE)
>>> +                     continue;
[...]
> I was lazy. In patch 26, upload-narrow-merge do three way merge and
> drop staged entries within narrow tree (this is at server side,
> conflicts within narrow tree will be handled at client side later).
> Instead of removing staged entries, I mark them CE_REMOVE.

Ah, ok; so it's to avoid spending time in remove_marked_cache_entries().

I think (though it wouldn't come up in your application) that to keep
this and avoid caller confusion one would need something like

		if ((cache[i]->ce_flags & CE_REMOVE) ||
		    (cache[i+1]->ce_flags & CE_REMOVE))
			continue;

in the other loop.  I say "something like" because a person could have
marked some some but not all stages with CE_REMOVE, causing
file/directory conflicts to be missed.

Thanks for the explanation.

Re: [PATCH 04/32] move do_compress() from pack-objects.c to pack-write.c

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 9:25 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
>> +unsigned long compress_object(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;
>> +}
>
> However, there is nothing particularly specialized to git objects
> about this.  e.g. deflate_it() from diff.c could use this.

Also archive-zip.c, fast-import.c, http-push.c and remote-curl.c have
very similar code. I'll see if I can reduce some code duplication.
-- 
Duy

Re: [PATCH 07/32] tree.c: find_subtree() to search for a tree

[Elijah Newren]

2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
<snip>
> +int find_tree(const unsigned char *sha1, unsigned char *newsha1, const char *path)

Trivial nit: Subject doesn't match the name of the function in the code.  ;-)

Also, when trying to apply your series locally on master, it seems to
die on this patch.  What commit is your series based on?

Re: [PATCH 07/32] tree.c: find_subtree() to search for a tree

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 1:35 PM, Elijah Newren <newren@gmail.com> wrote:
> 2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> <snip>
>> +int find_tree(const unsigned char *sha1, unsigned char *newsha1, const
>> char *path)
>
> Trivial nit: Subject doesn't match the name of the function in the code.
>  ;-)

Yeah. Been busy fixing code than commit messages..

> Also, when trying to apply your series locally on master, it seems to
> die on this patch.  What commit is your series based on?

c11969de, master at Aug 19.
-- 
Duy

Re: [PATCH 11/32] rev-list: support --narrow-tree

[Elijah Newren]

Hi,

2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> These options allow plumbing to access narrow tree traverse modes.
> As a consequence, tests can now be written to test these modes.
>
<snip>
> +                       if (!prefixcmp(arg, "--narrow-tree=")) {
> +                               revs->narrow_prefix = arg + 14;
> +                               revs->narrow_tree = 1;
> +                               continue;
> +                       }

Seems somewhat non-gittish.  Why not 'git rev-list --objects HEAD --
<subtree_path>' rather than 'git rev-list --objects
--narrow-tree=<subtree_path> HEAD'?  (Was it due to the current bug in
rev-list when specifying both --objects and paths?  If so, that's
addressed in the patch series I just sent.)


> +cat <<EOF >merge.expected
> +0da28f8308e336bd4b2c26b61c7fc44e41a30e49
> +7475cb8a389b36ce238b9ee6cbfdfa26a1b67e35
> +af9c31c0e217154296d93d66b9a5a41892c7b321
> +ba7a30916c792624a8372cb26da50f5594098222
> +74a398027f0b59183db54ca8c67dc30b5aeed0ff t2

Is this right?  Do you expect to see a t2 entry when filtering for t1/t12?

> +3b52e9990a52d9ea46b25199b5810566324759f4
> +fa0bba1767985729582729a12a5459cd041d6cf6 t1
> +d81015b2a1c40fc6cbc5bf5a8b16949018c3aede t1/t12
> +52bd8e43afb01d0c9747f1fedf2fc94684ee4cc4 t1/t12/f120
> +aa0602ee56ea4cb5e5bfff8713bb8a9a6ab4303e
> +d77d258d806b2aa7cdb5a301e6a54f023d9bdcfe t1
> +ab246f7eb05e94f695d2a0e30093d94fde7b837e t1/t12
> +04156ae83e615fa5b6019170928bc131539f9996 t1/t12/f120
> +72e05e456b9ff4c01ccf6178ce60d9b52b41aae4
> +4fc1656b01ce8b21987c55a2870b8c9a431ec772 t1
> +EOF
> +
> +test_expect_success 'rev-list --narrow-tree=t1/t12 with merges' '
> +       git rev-list --objects --narrow-tree=t1/t12 $MERGE >result &&
> +       test_cmp merge.expected result

Re: [PATCH 10/32] rev-list: support traversing in narrow repository mode

[Elijah Newren]

2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> In this mode, only trees within revs->narrow_prefix is traversed. This
> narrows down the whole repository to the given subtree. This mode will
> be used by upload-pack/pack-objects to create a narrow pack, and by
> all git operations in narrow repository (i.e. $GIT_DIR/narrow exists).

My fix-rev-list series I posted is going to cause a few conflicts with
this patch...

<snip>
> +               if (!subtree)
> +                       ;       /* no subtree restriction, go on */
> +               else if (S_ISDIR(entry.mode) &&
> +                        !strncmp(entry.path, subtree, subtree_len) &&
> +                        entry.path[subtree_len] == '\0')
> +                       ;       /* inside subtree, go on */

Instead of writing your own comparison code, you may want to consider
using tree_entry_interesting() here.  That would also provide you with
a natural extension to multiple subtrees, rather than your currently
hardcoded single tree.  You may want to take a look at
tree-diff.c:show_tree() for inspiration here.

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

On Tue, Aug 24, 2010 at 4:47 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> On Wed, Aug 25, 2010 at 8:37 AM, Jonathan Nieder <jrnieder@gmail.com> wrote:
>> Nguyễn Thái Ngọc Duy wrote:
>>
>>> Patches 26..30
>>>   Add upload-narrow-base command
>>>   rev-list: traverse some more trees to make upload-narrow-base happy
>>>   narrow-tree: add oldest_narrow_base()
>>>   Add command fetch-narrow-base
>>>   merge: support merging when narrow bases are different
>>>
>>> Remote merge part.
>>>
>>> Split a merge operation into two parts, the real merge will be done
>>> within narrow tree. Conflicts can happen and be resolved in the narrow
>>> index, locally.
>>>
>>> Everything outside narrow tree will be merged (trivially) by
>>> server. Then server sends the base tree back, so join_narrow_tree() in
>>> patch 20 can be used to create proper commit.
>>>
>>> Server can disable this remote merge feature, which means users are
>>> forced to do rebase/fast-forward. Not too bad.
>>
>> Yikes.  Naïve question (please forgive my laziness): is it possible to
>> merge without remote contact in the boring case, when no changes have
>> occured outside the narrow tree?
>
> That's possible (and is implemented in my series). But I guess as soon
> as you do "git pull", the boring case is likely not applicable
> anymore.

I'm not sure I follow.  Are you allowing changes outside the narrow
tree to occur?  If you're not, I would have assumed that repeated
pulls just work, without any need to talk to the server, using a
resolve-like strategy (with no special rename detection).

Here's my understanding, though it might have holes:

If you have a narrow/subtree clone, it means that you only have the
data for a certain paths.  I'm assuming that also meant you would only
allow modifying those paths.  In other words, you have no changes
outside the narrow tree.  Because of that, I think you can handle
paths outside the narrow region using trivial-merge logic:  From
Documentation/technical/trivial-merge.txt, I think the relevant cases
are 2, 3, 8, 10, 13, or 14.  13 & 14 already have a specified
resolution.  There's already a comment in the file that cases 8 & 10
could validly be resolved as (empty), it just hasn't been done in the
code as it tends to happen with the follow-up automatic merge anyway.
That only leaves cases 2 & 3 as being slightly tricky -- if a path on
one side of the merge started empty and ended empty, it would seem to
make sense that the non-empty path on the other side would be the
resolution.  We can't do that in the non-narrow clone case because the
non-empty path may have been created due to a rename and we'd like to
have changes follow the rename appropriately.  However, in the narrow
clone case, one can't rename from a path you don't have to a path you
do, so this possibility is eliminated.


So, if my understanding is correct, then if you have no changes from
upstream outside the sparse/narrow/whatever paths (where "paths"
currently means a single tree in your current patches), I think you
should be able to do a merge locally in that sparse clone.  The end
result will also have no changes from upstream outside those paths.
Thus, you should be able to merge again.


Does that seem reasonable?  Am I missing anything?

Re: [PATCH 15/32] unpack_trees: only unpack $GIT_DIR/narrow subtree in narrow repository

[Elijah Newren]

Hi,

2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> By definition, narrow repository is incomplete. It does not even have
> enough tree for a single commit. So populating a full index is
> impossible.
>
> Because of this, unpack_trees() is modified to only unpack trees
> within $GIT_DIR/narrow, which narrow repo has all needed trees. This
> makes the resulting index unsuitable for creating commits later on.
> This is the reason index version is increased to 4, to avoid older
> git from using it.
>
> The resulting tree objects created from the index is only part of the
> full tree. Manipulation will be needed at commit time to create proper
> tree for commits.

I spent a while thinking about this a couple weeks ago and never came
to a strong conclusion about which of two alternatives should be
preferred; I'm curious why you decided to go for this solution.  An
alternative I thought of was having the index have entries for missing
files (whose contents did not exist in the repository or the working
copy; rather all we know is the filename and its sha1sum) and also
gain the ability to have entries for missing trees (which behave
similarly; all we know is their name and their sha1sum, but the
contents of that sha1sum are not in the repository or the working
directory)  Is there a reason to prefer one alternative over the
other?  Does the alternative I thought of even make sense?

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 2:37 PM, Elijah Newren <newren@gmail.com> wrote:
>>>> Remote merge part.
>>>>
>>>> Split a merge operation into two parts, the real merge will be done
>>>> within narrow tree. Conflicts can happen and be resolved in the narrow
>>>> index, locally.
>>>>
>>>> Everything outside narrow tree will be merged (trivially) by
>>>> server. Then server sends the base tree back, so join_narrow_tree() in
>>>> patch 20 can be used to create proper commit.
>>>>
>>>> Server can disable this remote merge feature, which means users are
>>>> forced to do rebase/fast-forward. Not too bad.
>>>
>>> Yikes.  Naïve question (please forgive my laziness): is it possible to
>>> merge without remote contact in the boring case, when no changes have
>>> occured outside the narrow tree?
>>
>> That's possible (and is implemented in my series). But I guess as soon
>> as you do "git pull", the boring case is likely not applicable
>> anymore.
>
> I'm not sure I follow.  Are you allowing changes outside the narrow
> tree to occur?  If you're not, I would have assumed that repeated
> pulls just work, without any need to talk to the server, using a
> resolve-like strategy (with no special rename detection).

I don't. But I can't stop all other users (who use full repos) change
outside the narrow tree and push their changes back upstream. When
narrow user pulls from upstream again, the tree outside narrow tree
might be not the same as before.

> Here's my understanding, though it might have holes:
>
> If you have a narrow/subtree clone, it means that you only have the
> data for a certain paths.  I'm assuming that also meant you would only
> allow modifying those paths.  In other words, you have no changes
> outside the narrow tree.  Because of that, I think you can handle
> paths outside the narrow region using trivial-merge logic:  From
> Documentation/technical/trivial-merge.txt, I think the relevant cases
> are 2, 3, 8, 10, 13, or 14.  13 & 14 already have a specified
> resolution.  There's already a comment in the file that cases 8 & 10
> could validly be resolved as (empty), it just hasn't been done in the
> code as it tends to happen with the follow-up automatic merge anyway.
> That only leaves cases 2 & 3 as being slightly tricky -- if a path on
> one side of the merge started empty and ended empty, it would seem to
> make sense that the non-empty path on the other side would be the
> resolution.  We can't do that in the non-narrow clone case because the
> non-empty path may have been created due to a rename and we'd like to
> have changes follow the rename appropriately.  However, in the narrow
> clone case, one can't rename from a path you don't have to a path you
> do, so this possibility is eliminated.

Trivial merge did not work outside narrow tree for me because I did
not have all trees of a commit. So as soon as it steps on the narrow
border, it has to stop (without retrieving full path to files outside
narrow tree). trivial-merge.txt takes input as files, not directories.
Given two directories (because we don't have further details what
inside those directories), I don't know how to do trivial merge.

> So, if my understanding is correct, then if you have no changes from
> upstream outside the sparse/narrow/whatever paths (where "paths"
> currently means a single tree in your current patches), I think you
> should be able to do a merge locally in that sparse clone.  The end
> result will also have no changes from upstream outside those paths.
> Thus, you should be able to merge again.

Yes. But other people will change outside narrow tree, unfortunately.
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

Replying to myself...

On Tue, Aug 24, 2010 at 10:37 PM, Elijah Newren <newren@gmail.com> wrote:
<snip>
> outside the narrow tree.  Because of that, I think you can handle
> paths outside the narrow region using trivial-merge logic:  From
> Documentation/technical/trivial-merge.txt, I think the relevant cases
> are 2, 3, 8, 10, 13, or 14.  13 & 14 already have a specified
<snip>
> That only leaves cases 2 & 3 as being slightly tricky -- if a path on
> one side of the merge started empty and ended empty, it would seem to
> make sense that the non-empty path on the other side would be the
> resolution.  We can't do that in the non-narrow clone case because the
> non-empty path may have been created due to a rename and we'd like to
> have changes follow the rename appropriately.  However, in the narrow
> clone case, one can't rename from a path you don't have to a path you
> do, so this possibility is eliminated.

I just realized I was assuming the path was empty in the merge base
and in upstream, but non-empty on the side of the merge corresponding
to the local sparse/narrow repository.  My wording certainly reflected
that assumption.  If so, I still think what I said was correct.  If
not, it's slightly more subtle.  If the non-empty side is upstream,
then it may be a rename case that needs special handling.  If it's a
rename from a path outside our subtree (and we can somehow detect this
case), then although we don't have the data to do any special
handling, it wouldn't be necessary since we did not modify either the
source or destination of the rename.  The tricky case is if it's a
rename from a path within our subtree to a file outside; we'd only be
able to handle such situations if there was no modification other than
the rename.  Unfortunately, we can't distinguish between (1) renames
from paths outside our subtree to outside our subtree and (2) renames
plus changes from paths inside our subtree to outside our subtree.

That puts us in a bit of a pickle for the empty->empty vs. non-empty
case.  We can only resolve it if the non-empty side is in our subtree,
or if we decide to just ignore renames in our merges.

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

Hi,

On Tue, Aug 24, 2010 at 11:21 PM, Nguyen Thai Ngoc Duy
<pclouds@gmail.com> wrote:
> On Wed, Aug 25, 2010 at 2:37 PM, Elijah Newren <newren@gmail.com> wrote:
<snip>
>> I'm not sure I follow.  Are you allowing changes outside the narrow
>> tree to occur?  If you're not, I would have assumed that repeated
>> pulls just work, without any need to talk to the server, using a
>> resolve-like strategy (with no special rename detection).
>
> I don't. But I can't stop all other users (who use full repos) change
> outside the narrow tree and push their changes back upstream. When
> narrow user pulls from upstream again, the tree outside narrow tree
> might be not the same as before.

Sure, they will modify paths outside your subtree, but you know that
you didn't do so.  So if you neglect renames then the situation is
pretty simple:

Merge-side: ancestor    you         upstream
            --------    --------    --------------
Sha1sum:    ancestor    ancestor    new-stuff

Which could be true for either a file or a tree.  Either way, if you
ignore renames, then the trivial merge is 'new-stuff' for any such
blob/tree.  (Yeah, you'd have to create a new merge algorithm that
does 'trivial' merges at tree levels in addition to file levels, but
the concept is relatively simple at least.)

After your merge, a subsequent pull would look like this at the same
file/tree path:

Merge-side: ancestor    you         upstream
            --------    --------    --------------
Sha1sum:    new-stuff   new-stuff   newer-stuff

For which the resolution would be 'newer-stuff' (again, ignoring the
problems that renames could cause, which I discussed elsewhere).

Unless, of course, I'm missing something still...

Re: [PATCH 07/32] tree.c: find_subtree() to search for a tree

[Elijah Newren]

On Tue, Aug 24, 2010 at 9:43 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> Also, when trying to apply your series locally on master, it seems to
>> die on this patch.  What commit is your series based on?
>
> c11969de, master at Aug 19.

Hmm...seems they don't apply there either, but the reason is because
gmane changed the order of your patches.  That's unfortunate.  :-/

Re: [PATCH 15/32] unpack_trees: only unpack $GIT_DIR/narrow subtree in narrow repository

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 3:04 PM, Elijah Newren <newren@gmail.com> wrote:
> Hi,
>
> 2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> By definition, narrow repository is incomplete. It does not even have
>> enough tree for a single commit. So populating a full index is
>> impossible.
>>
>> Because of this, unpack_trees() is modified to only unpack trees
>> within $GIT_DIR/narrow, which narrow repo has all needed trees. This
>> makes the resulting index unsuitable for creating commits later on.
>> This is the reason index version is increased to 4, to avoid older
>> git from using it.
>>
>> The resulting tree objects created from the index is only part of the
>> full tree. Manipulation will be needed at commit time to create proper
>> tree for commits.
>
> I spent a while thinking about this a couple weeks ago and never came
> to a strong conclusion about which of two alternatives should be
> preferred; I'm curious why you decided to go for this solution.  An
> alternative I thought of was having the index have entries for missing
> files (whose contents did not exist in the repository or the working
> copy; rather all we know is the filename and its sha1sum) and also
> gain the ability to have entries for missing trees (which behave
> similarly; all we know is their name and their sha1sum, but the
> contents of that sha1sum are not in the repository or the working
> directory)  Is there a reason to prefer one alternative over the
> other?  Does the alternative I thought of even make sense?

That was nightmare. I had to deal with unpack_callback() and skip
uninterested paths. And that function is, I think, quite optimized. I
tried another approach, putting directories in index with hope that it
would cut down the number of code path I'd have to touch. It did, but
then index sorting order is just weird and I couldn't get it right
(felt to risky).

unpack_trees() is used by diff (all diffs except diff_tree_sha1).
traverse_trees()/unpack_trees() is also used by merge strategy. All
those code is really complicated that I'd rather stay away from them.

That was before I went with tree rewrites. Soon after I realized the
nice effect of tree rewrites is that the index is narrowed down. So I
can get rid of tree rewrites as long as the index is still narrow.
That's how I come to this approach.

Back to your questions. I think the alternative makes sense, it just
looks a lot of work and quite intrusive. On the other hand, my current
approach is quite simple (but it probably won't work for more than a
single narrow tree)
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 3:31 PM, Elijah Newren <newren@gmail.com> wrote:
> Sure, they will modify paths outside your subtree, but you know that
> you didn't do so.  So if you neglect renames then the situation is
> pretty simple:
>
> Merge-side: ancestor    you         upstream
>            --------    --------    --------------
> Sha1sum:    ancestor    ancestor    new-stuff
>
> Which could be true for either a file or a tree.  Either way, if you
> ignore renames, then the trivial merge is 'new-stuff' for any such
> blob/tree.  (Yeah, you'd have to create a new merge algorithm that
> does 'trivial' merges at tree levels in addition to file levels, but
> the concept is relatively simple at least.)
>
> After your merge, a subsequent pull would look like this at the same
> file/tree path:
>
> Merge-side: ancestor    you         upstream
>            --------    --------    --------------
> Sha1sum:    new-stuff   new-stuff   newer-stuff
>
> For which the resolution would be 'newer-stuff' (again, ignoring the
> problems that renames could cause, which I discussed elsewhere).
>
> Unless, of course, I'm missing something still...

OK here is the story. And I could be wrong on this merge stuff.

I was deep in merge-tree.c code (which was the base for my narrow
merge) and was stuck at

"If either "you" or "upstream" is as same as ancestor (all as dirs),
then it's easy. What if neither of them is the same as ancestor? If we
have more trees, we could just descend and figure out. But we don't
because it's outside narrow area. It could be that "you" added a new
file and "upstream" added another file, which is trivial at file
level."

I was deep in code and forgot that in narrow repo, I did not allow to
change outside narrow area, so it "you" must be as same as ancestor.
But the question was, what if user decides to branch from some commit
in history? If he/she does, "you" might not be as same as ancestor. If
it's non trivial merge, merge should fail (expected).

But the "it could be that "you" added ... at file level" above
bothered me. I had a feeling that I could miss a trivial merge (at
file level) because I could not make a judgement at (shallow) tree
level. And I did not have all trees to do merge at file level.

Still puzzling thinking about this.. Did I make wrong assumptions?
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

Hi,

On Wed, Aug 25, 2010 at 12:21 AM, Nguyen Thai Ngoc Duy
<pclouds@gmail.com> wrote:
> OK here is the story. And I could be wrong on this merge stuff.
>
> I was deep in merge-tree.c code (which was the base for my narrow
> merge) and was stuck at
>
> "If either "you" or "upstream" is as same as ancestor (all as dirs),
> then it's easy. What if neither of them is the same as ancestor? If we
> have more trees, we could just descend and figure out. But we don't
> because it's outside narrow area. It could be that "you" added a new
> file and "upstream" added another file, which is trivial at file
> level."
>
> I was deep in code and forgot that in narrow repo, I did not allow to
> change outside narrow area, so it "you" must be as same as ancestor.
> But the question was, what if user decides to branch from some commit
> in history? If he/she does, "you" might not be as same as ancestor. If
> it's non trivial merge, merge should fail (expected).

If you branch from some older commit, then naturally the common
ancestor between you and upstream changes as well (namely, to that
older commit).  Since you don't/can't change anything outside your
subtree, that puts you in the following situation for paths outside
your subtree when you try to merge:

Merge-side: ancestor    you         upstream
            --------    --------    --------------
Sha1sum:    old-stuff   old-stuff   newest-stuff

> But the "it could be that "you" added ... at file level" above
> bothered me. I had a feeling that I could miss a trivial merge (at
> file level) because I could not make a judgement at (shallow) tree
> level. And I did not have all trees to do merge at file level.
>
> Still puzzling thinking about this.. Did I make wrong assumptions?

I'm not sure I understand why there would be any issue with you adding
one file in your subtree, and upstream adding (another/the same?) file
outside your subtree.  The only problematic case I see is when files
are renamed upstream from within the subtree to outside the subtree
and subsequently changed.  If on your side of history you modify one
of these files that were renamed from upstream, there's no way to
apply your changes to the new file.  It'd look something like this:

Merge-side: ancestor    you         upstream
            --------    --------    --------------
old-file:   original    modify1     (missing)
new-file:   (missing)   (missing)   modify2

The correct resolution is a three-way merge between original, modify1,
and modify2, stored in new-file with old-file being deleted.  However,
you don't have access to new-file/modify2 since it's outside your
subtree.  All you'd see is a modify/delete conflict in old-file and
the 'trivial merge' logic I suggested above (which ignores renames)
would result in new-file still having contents of modify2.

Hopefully the modify/delete conflict would be enough to trigger the
user to ask rather than just randomly pick some resolution and
proceed, which makes me think it should be okay to have a renaming
ignoring 'trivial' merge algorithm for subtrees.


Elijah

Re: [RFD PATCH 00/32] subtree clone v2

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> I'm not sure I follow.  Are you allowing changes outside the narrow
> tree to occur?  If you're not, I would have assumed that repeated
> pulls just work, without any need to talk to the server, using a
> resolve-like strategy (with no special rename detection).
>
> Here's my understanding, though it might have holes:
>
> If you have a narrow/subtree clone, it means that you only have the
> data for a certain paths.  I'm assuming that also meant you would only
> allow modifying those paths.  In other words, you have no changes
> outside the narrow tree.  Because of that, I think you can handle
> paths outside the narrow region using trivial-merge logic ...

I think you can do a merge only once, but after that you would be lost.

Suppose you forked from commit A, narrowed to one subdirectory and created
B (iow, diff(A, B) contains only changes to that subdirectory).  Somebody
else worked on the whole tree and queued commit C on top of A.

      B---?
     /   /
 ---A---C

Your merge between B and C that uses A as the common ancestor can take all
changes outside the subdirectory from C (but you need to know all the tree
object names in C near the top outside your area).  So far, so good.

While this was going on, somebody else also forked from A and made changes
that touch both inside and outside your area, and its tip commit is E.

      B---D---?
     /   /   /
 ---A---C   /
     \     /
      o---E

Now you want to merge changes made on the branch that leads to E to your
copy.  How would we do that?

You cannot merge D and E without having enough information necessary to
make a merge between C and E with full tree, can you?

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

On Wed, Aug 25, 2010 at 1:27 PM, Junio C Hamano <gitster@pobox.com> wrote:
<snip>
>> If you have a narrow/subtree clone, it means that you only have the
>> data for a certain paths.  I'm assuming that also meant you would only
>> allow modifying those paths.  In other words, you have no changes
>> outside the narrow tree.  Because of that, I think you can handle
>> paths outside the narrow region using trivial-merge logic ...
>
> I think you can do a merge only once, but after that you would be lost.
>
> Suppose you forked from commit A, narrowed to one subdirectory and created
> B (iow, diff(A, B) contains only changes to that subdirectory).  Somebody
> else worked on the whole tree and queued commit C on top of A.
>
>      B---?
>     /   /
>  ---A---C
>
> Your merge between B and C that uses A as the common ancestor can take all
> changes outside the subdirectory from C (but you need to know all the tree
> object names in C near the top outside your area).  So far, so good.
>
> While this was going on, somebody else also forked from A and made changes
> that touch both inside and outside your area, and its tip commit is E.
>
>      B---D---?
>     /   /   /
>  ---A---C   /
>     \     /
>      o---E
>
> Now you want to merge changes made on the branch that leads to E to your
> copy.  How would we do that?
>
> You cannot merge D and E without having enough information necessary to
> make a merge between C and E with full tree, can you?

Ah, now I think I see what Duy was getting at; thanks for making that clear.

You are correct, of course[1].  Failing merges with
"not-enough-information-available" will sometimes be a fact of life
with sparse/narrow/subtree/partial/whatever clones[2] -- either that
or "server-side merging" as Duy suggests (though I personally am not a
fan of that).  I was just pointing out that I think we're not limited
to a single merge ever; for example, if I understand correctly, if
someone else merges C & E then you'll be able to merge from them[3]
(and thus, you'll be able to merge "more than once").

Elijah


[1] Outside your subtree, D does not match the merge-base A, thus so
you can't employ 'trivial merge' logic and you don't have the data for
any other kind of merge.

[2] As noted as item 7 at
http://article.gmane.org/gmane.comp.version-control.git/152020.

[3] This is because outside your subtree, D would match the new
merge-base (C), allowing you to use trivial merge logic again.

Re: [PATCH 11/32] rev-list: support --narrow-tree

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 1:59 PM, Elijah Newren <newren@gmail.com> wrote:
> Hi,
>
> 2010/8/24 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> These options allow plumbing to access narrow tree traverse modes.
>> As a consequence, tests can now be written to test these modes.
>>
> <snip>
>> +                       if (!prefixcmp(arg, "--narrow-tree=")) {
>> +                               revs->narrow_prefix = arg + 14;
>> +                               revs->narrow_tree = 1;
>> +                               continue;
>> +                       }
>
> Seems somewhat non-gittish.  Why not 'git rev-list --objects HEAD --
> <subtree_path>' rather than 'git rev-list --objects
> --narrow-tree=<subtree_path> HEAD'?  (Was it due to the current bug in
> rev-list when specifying both --objects and paths?  If so, that's
> addressed in the patch series I just sent.)

Yeah probably because of the --object bug that I did not know. Anyway
I still need "--narrow" signal because in my series, I would send all
trees that are not found in parents' trees for merge commits. A
requirement from remote merge.

>> +cat <<EOF >merge.expected
>> +0da28f8308e336bd4b2c26b61c7fc44e41a30e49
>> +7475cb8a389b36ce238b9ee6cbfdfa26a1b67e35
>> +af9c31c0e217154296d93d66b9a5a41892c7b321
>> +ba7a30916c792624a8372cb26da50f5594098222
>> +74a398027f0b59183db54ca8c67dc30b5aeed0ff t2
>
> Is this right?  Do you expect to see a t2 entry when filtering for t1/t12?

As I said above, if this "t2" is not seen in either parents, then it
must be sent/traversed, unfortunately.
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Wed, Aug 25, 2010 at 3:31 PM, Elijah Newren <newren@gmail.com> wrote:
> Sure, they will modify paths outside your subtree, but you know that
> you didn't do so.  So if you neglect renames then the situation is
> pretty simple:
> ....
>
> Unless, of course, I'm missing something still...

I remember it!

So there are two points: the "no changes outside narrow tree from
"you"" assumption and whether it is trivial to do a merge outside
narrow tree without whole trees.

The first point. That assumption holds if user clones, starts working,
then does "pull origin". But if user merges another branch, say "next"
into "master", the common commit may be somewhere down in history and
there may be changes outside narrow tree from both "you" and
"upstream" (though user does not make those changes).

The second point (probably not needed if the above assumption is no
longer true, but I post anyway in case I forget it again). Without
whole trees, it's impossible to determine a trivial merge reliably. If
"you" adds a file and "upstream" adds another file, predecessor trees
will look different but merging them is trivial (at file level). If we
miss some trees that lead to those new files, the best thing we can do
is to claim it non-trivial.
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

On Wed, Aug 25, 2010 at 4:13 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> On Wed, Aug 25, 2010 at 3:31 PM, Elijah Newren <newren@gmail.com> wrote:
> I remember it!
>
> So there are two points: the "no changes outside narrow tree from
> "you"" assumption and whether it is trivial to do a merge outside
> narrow tree without whole trees.
>
> The first point. That assumption holds if user clones, starts working,
> then does "pull origin". But if user merges another branch, say "next"
> into "master", the common commit may be somewhere down in history and
> there may be changes outside narrow tree from both "you" and
> "upstream" (though user does not make those changes).

Yes, I agree; you can't merge with the data you have in such a case.

> The second point (probably not needed if the above assumption is no
> longer true, but I post anyway in case I forget it again). Without
> whole trees, it's impossible to determine a trivial merge reliably. If
> "you" adds a file and "upstream" adds another file, predecessor trees
> will look different but merging them is trivial (at file level). If we
> miss some trees that lead to those new files, the best thing we can do
> is to claim it non-trivial.

I'm not following this one.  Could you provide more detail?

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Thu, Aug 26, 2010 at 12:50 PM, Elijah Newren <newren@gmail.com> wrote:
>> The second point (probably not needed if the above assumption is no
>> longer true, but I post anyway in case I forget it again). Without
>> whole trees, it's impossible to determine a trivial merge reliably. If
>> "you" adds a file and "upstream" adds another file, predecessor trees
>> will look different but merging them is trivial (at file level). If we
>> miss some trees that lead to those new files, the best thing we can do
>> is to claim it non-trivial.
>
> I'm not following this one.  Could you provide more detail?
>

Let's say in "ancestor" tree, we have

t1/f0
t2/t3/f0

In "you" tree, we have

t1/f0
t2/t3/f0
t2/t3/f1

In "upstream" tree, we have

t1/f0
t2/t3/f0
t2/t3/f2

The narrow tree is t1, so we the trees we have are toplevel tree and
t1. If we have all trees, that should be a trivial merge, which
results in f0, f1 and f2 inside t2/t3. But we don't have t2 and t3
trees in narrow repo. When we traverse toplevel tree of "ancestor",
"you" and "upstream", we can only see that t2 sha-1 is different. If
"t2" is a file, not a tree, then we can conclude non-trivial here. And
because we don't have t2, we can't descend to make better conclusion.
-- 
Duy

Re: [RFD PATCH 00/32] subtree clone v2

[Elijah Newren]

On Wed, Aug 25, 2010 at 9:52 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> Let's say in "ancestor" tree, we have
>
> t1/f0
> t2/t3/f0
>
> In "you" tree, we have
>
> t1/f0
> t2/t3/f0
> t2/t3/f1
>
> In "upstream" tree, we have
>
> t1/f0
> t2/t3/f0
> t2/t3/f2
>
> The narrow tree is t1, so we the trees we have are toplevel tree and

How would you get the "you" tree?  Since you don't have the data for
t2 or t2/t3, there's no way you can create and commit this tree.

Re: [RFD PATCH 00/32] subtree clone v2

[Nguyen Thai Ngoc Duy]

On Thu, Aug 26, 2010 at 2:39 PM, Elijah Newren <newren@gmail.com> wrote:
> On Wed, Aug 25, 2010 at 9:52 PM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
>> Let's say in "ancestor" tree, we have
>>
>> t1/f0
>> t2/t3/f0
>>
>> In "you" tree, we have
>>
>> t1/f0
>> t2/t3/f0
>> t2/t3/f1
>>
>> In "upstream" tree, we have
>>
>> t1/f0
>> t2/t3/f0
>> t2/t3/f2
>>
>> The narrow tree is t1, so we the trees we have are toplevel tree and
>
> How would you get the "you" tree?  Since you don't have the data for
> t2 or t2/t3, there's no way you can create and commit this tree.

"you" tree does not create that file. It's been there. It's the
"ancestor" tree that did not have that file. So if you happen to
choose an "upstream" tree that git-merge-base would give you that
particular "ancestor" tree, we're in this situation.
-- 
Duy