[PATCH 00/17] Narrow clone v3 (was subtree clone)

[PATCH 00/17] Narrow clone v3 (was subtree clone)

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

I'll describe differences between this series and Elijah's one [1].
I think it's more interesting. Changes from v2 [2] will follow later.

In short I think the two series are converging. The outstanding
difference is Elijah drops shallow clone in favor of more flexible
history cutting while I only focus on tree cutting.

Two other differences are tree traversal and tree generating. I admit
that changing traverse_trees() the way Elijah does is more flexible
and is probably the only way to support negative pathspec. And I think
his sparse clone supports even cloning a single file. Mine does not
support that. I'm going to steal some of his patches at some point.

Tree generating from index, Elijah merges the base tree inside
write_cache_as_tree() while it does it inside commit_tree(). Again the
principle is pretty much the same. I'll see if I can resist from
stealing some more :)

OK, changes from v2:

 - Require en/object-list-with-pathspec
 - Use lower-case index extension instead of stepping index version to 4
 - Support cloning multiple tree
 - Remote merge is dropped. It may be resurrected at some point if
   people like to merge so much.

Things that won't work:

 - fsck/prune/...
 - Shell scripts that use "git write-tree"

What's next:
 - stealing
 - fsck (will probably make fsck use rev-list in narrow repo)
 - only send commits that have changes in narrow area and graft it at
   client side

[1] http://mid.gmane.org/1283645647-1891-1-git-send-email-newren@gmail.com
[2] http://mid.gmane.org/1282688422-7738-1-git-send-email-pclouds@gmail.com 

Nguyễn Thái Ngọc Duy (17):
  rev-list: do not do commit simplification if simplify_history = 0
  tree.c: add path_to_sha1()
  Introduce $GIT_DIR/narrow
  index: make narrow index incompatible with older git
  pack-objects: support narrow packs with pathspecs
  {fetch,upload}-pack: support narrow repository
  unpack-trees: split traverse_trees() code into a separate function
  unpack-trees: support unpack trees in narrow repository
  cache-tree: only cache tree within narrow area
  get_pathspec(): support narrow pathspec rewriting
  pathspec retrieval fix
  clone: support --narrow option
  commit: add narrow's commit_tree version
  commit: use commit_narrow_tree() to support narrow repo
  write-tree: requires --narrow-base in narrow repository
  merge: try to do local merge if possible in narrow repo
  Add narrow clone demonstration test

 .gitignore                                |    1 +
 Documentation/git-clone.txt               |   14 ++-
 Documentation/git-fetch-pack.txt          |    3 +
 Documentation/git-merge.txt               |   16 ++
 Documentation/git-pack-objects.txt        |    2 +-
 Documentation/git-rev-parse.txt           |    3 +
 Documentation/gitrepository-layout.txt    |    5 +
 Documentation/technical/pack-protocol.txt |    3 +
 Makefile                                  |    3 +
 builtin/clone.c                           |   43 +++++
 builtin/commit.c                          |   16 +-
 builtin/fetch-pack.c                      |    9 +
 builtin/grep.c                            |    5 +-
 builtin/ls-files.c                        |    2 +-
 builtin/ls-tree.c                         |    2 +-
 builtin/merge.c                           |   60 ++++++-
 builtin/pack-objects.c                    |   19 ++-
 builtin/reset.c                           |    3 +-
 builtin/rev-parse.c                       |    8 +
 builtin/write-tree.c                      |   25 +++
 cache-tree.c                              |   41 ++++-
 cache.h                                   |    5 +
 commit.c                                  |   16 ++
 commit.h                                  |    5 +
 environment.c                             |    2 +
 git-am.sh                                 |    2 +-
 narrow-tree.c                             |  285 +++++++++++++++++++++++++++++
 narrow-tree.h                             |    8 +
 read-cache.c                              |   32 +++-
 revision.c                                |    7 +-
 setup.c                                   |  172 +++++++++++++++++-
 t/t0062-narrow-pathspec.sh                |  150 +++++++++++++++
 t/t0063-narrow-repo.sh                    |   74 ++++++++
 t/t1013-read-tree-narrow.sh               |   72 ++++++++
 t/t6000-rev-list-misc.sh                  |    9 +
 t/t7510-commit-narrow.sh                  |   30 +++
 t/t9999-narrow.sh                         |   87 +++++++++
 test-get-pathspec.c                       |   17 ++
 tree.c                                    |   35 ++++
 tree.h                                    |    2 +
 unpack-trees.c                            |  153 +++++++++++++---
 upload-pack.c                             |   39 ++++-
 42 files changed, 1420 insertions(+), 65 deletions(-)
 create mode 100644 narrow-tree.c
 create mode 100644 narrow-tree.h
 create mode 100755 t/t0062-narrow-pathspec.sh
 create mode 100755 t/t0063-narrow-repo.sh
 create mode 100755 t/t1013-read-tree-narrow.sh
 create mode 100755 t/t7510-commit-narrow.sh
 create mode 100755 t/t9999-narrow.sh
 create mode 100644 test-get-pathspec.c

[PATCH 01/17] rev-list: do not do commit simplification if simplify_history = 0

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

This is just a workaround to make my series work. Currently, commit
chain will be simplified if pathspecs are given. That would make
pack-objects generate commit chain with gaps.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Equivalence of Elijah's evil commit, 14/15.

 builtin/pack-objects.c |    1 +
 revision.c             |    2 +-
 upload-pack.c          |    1 +
 3 files changed, 3 insertions(+), 1 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 0e81673..789f6bf 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2072,6 +2072,7 @@ static void get_object_list(int ac, const char **av)
 
 	init_revisions(&revs, NULL);
 	save_commit_buffer = 0;
+	revs.simplify_history = 0;
 	setup_revisions(ac, av, &revs, NULL);
 
 	while (fgets(line, sizeof(line), stdin) != NULL) {
diff --git a/revision.c b/revision.c
index 55c4586..ea64970 100644
--- a/revision.c
+++ b/revision.c
@@ -372,7 +372,7 @@ static void try_to_simplify_commit(struct rev_info *revs, struct commit *commit)
 	/*
 	 * If we don't do pruning, everything is interesting
 	 */
-	if (!revs->prune)
+	if (!revs->prune || !revs->simplify_history)
 		return;
 
 	if (!commit->tree)
diff --git a/upload-pack.c b/upload-pack.c
index fc79dde..cc1983f 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -115,6 +115,7 @@ static int do_rev_list(int in, int out, void *user_data)
 	revs.tag_objects = 1;
 	revs.tree_objects = 1;
 	revs.blob_objects = 1;
+	revs.simplify_history = 0;
 	if (use_thin_pack)
 		revs.edge_hint = 1;
 
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 02/17] tree.c: add path_to_sha1()

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

Given a tree and a path, it will traverse down the tree, follow the
path and return sha1 of the path.

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

diff --git a/tree.c b/tree.c
index 5ab90af..2c7ae45 100644
--- a/tree.c
+++ b/tree.c
@@ -284,3 +284,38 @@ struct tree *parse_tree_indirect(const unsigned char *sha1)
 			parse_object(obj->sha1);
 	} while (1);
 }
+
+int path_to_tree_sha1(unsigned char *newsha1, const unsigned char *sha1, 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 path_to_tree_sha1(newsha1, entry.sha1, slash+1);
+			else {
+				hashcpy(newsha1, entry.sha1);
+				return 1;
+			}
+		}
+	}
+	free(buffer);
+	return 0;
+}
diff --git a/tree.h b/tree.h
index 2ff01a4..d246a6c 100644
--- a/tree.h
+++ b/tree.h
@@ -30,4 +30,6 @@ extern int read_tree_recursive(struct tree *tree,
 
 extern int read_tree(struct tree *tree, int stage, const char **paths);
 
+extern int path_to_tree_sha1(unsigned char *newsha1, const unsigned char *sha1, const char *path);
+
 #endif /* TREE_H */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 03/17] Introduce $GIT_DIR/narrow

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

This file contains a sorted list of narrow prefix, used in narrow
repositories.

rev-parse also learns --narrow-prefix to print $GIT_DIR/narrow out

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Documentation/git-rev-parse.txt        |    3 +
 Documentation/gitrepository-layout.txt |    5 ++
 Makefile                               |    2 +
 builtin/rev-parse.c                    |    8 +++
 cache.h                                |    3 +
 environment.c                          |    2 +
 narrow-tree.c                          |  106 ++++++++++++++++++++++++++++++++
 narrow-tree.h                          |    3 +
 t/t0063-narrow-repo.sh                 |   46 ++++++++++++++
 9 files changed, 178 insertions(+), 0 deletions(-)
 create mode 100644 narrow-tree.c
 create mode 100644 narrow-tree.h
 create mode 100755 t/t0063-narrow-repo.sh

diff --git a/Documentation/git-rev-parse.txt b/Documentation/git-rev-parse.txt
index be4c053..5d5e77b 100644
--- a/Documentation/git-rev-parse.txt
+++ b/Documentation/git-rev-parse.txt
@@ -148,6 +148,9 @@ shown.  If the pattern does not contain a globbing character (`?`,
 --is-bare-repository::
 	When the repository is bare print "true", otherwise "false".
 
+--narrow-prefix::
+	Print narrow prefix git reads from $GIT_DIR/narrow.
+
 --local-env-vars::
 	List the GIT_* environment variables that are local to the
 	repository (e.g. GIT_DIR or GIT_WORK_TREE, but not GIT_EDITOR).
diff --git a/Documentation/gitrepository-layout.txt b/Documentation/gitrepository-layout.txt
index eb3d040..82e0350 100644
--- a/Documentation/gitrepository-layout.txt
+++ b/Documentation/gitrepository-layout.txt
@@ -193,6 +193,11 @@ shallow::
 	and maintained by shallow clone mechanism.  See `--depth`
 	option to linkgit:git-clone[1] and linkgit:git-fetch[1].
 
+narrow::
+	This file contains narrow prefix in sorted order. It is
+	internally used and maintained by narrow clone mechanism.
+	See `--narrow-tree` option to linkgit:git-clone[1].
+
 SEE ALSO
 --------
 linkgit:git-init[1],
diff --git a/Makefile b/Makefile
index b4745a5..f1aaba9 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/builtin/rev-parse.c b/builtin/rev-parse.c
index a5a1c86..590df6f 100644
--- a/builtin/rev-parse.c
+++ b/builtin/rev-parse.c
@@ -675,6 +675,14 @@ int cmd_rev_parse(int argc, const char **argv, const char *prefix)
 						: "false");
 				continue;
 			}
+			if (!strcmp(arg, "--narrow-prefix")) {
+				const char **p = get_narrow_prefix();
+				if (!p)
+					continue;
+				while (*p)
+					printf("%s\n", *p++);
+				continue;
+			}
 			if (!prefixcmp(arg, "--since=")) {
 				show_datestring("--max-age=", arg+8);
 				continue;
diff --git a/cache.h b/cache.h
index eb77e1d..d09c4fc 100644
--- a/cache.h
+++ b/cache.h
@@ -1105,4 +1105,7 @@ const char *split_cmdline_strerror(int cmdline_errno);
 /* 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..85dbab4
--- /dev/null
+++ b/narrow-tree.c
@@ -0,0 +1,106 @@
+#include "cache.h"
+#include "narrow-tree.h"
+
+static const char **narrow_prefix;
+static char *narrow_buf;
+
+int valid_narrow_prefix(const char *prefix, const char *prev_prefix, int quiet)
+{
+	int len = strlen(prefix);
+
+	if (!*prefix) {
+		if (!quiet)
+			error("Empty line in $GIT_DIR/narrow");
+		return 0;
+	}
+
+	if (prefix[len-1] == '/') {
+		if (!quiet)
+			error("Trailing slash not allowed in $GIT_DIR: %s", prefix);
+		return 0;
+	}
+
+	if (prev_prefix) {
+		if (strcmp(prev_prefix, prefix) >= 0) {
+			if (!quiet)
+				error("$GIT_DIR/narrow is unsorted at %s", prefix);
+			return 0;
+		}
+		len = strlen(prev_prefix);
+		if (!strncmp(prev_prefix, prefix, len) &&
+		    prefix[len] == '/') {
+			if (!quiet) {
+				error("$GIT_DIR/narrow has nested prefix (%s and %s)",
+				      prev_prefix, prefix);
+				return 0;
+			}
+		}
+	}
+	return 1;
+}
+
+int check_narrow_prefix()
+{
+	struct stat st;
+	int fd, i, n, len;
+	char *p, *pp;
+
+	if (stat(git_path("narrow"), &st) || st.st_size == 0)
+		return 0;
+
+	narrow_buf = xmalloc(st.st_size+2); /* NULL and \n */
+
+	fd = open(git_path("narrow"), O_RDONLY);
+	if (fd == -1)
+		return 0;
+
+	if (xread(fd, narrow_buf, st.st_size) != st.st_size)
+		die("failed to read $GIT_DIR/narrow");
+	close(fd);
+
+	if (narrow_buf[st.st_size-1] == '\n')
+		narrow_buf[st.st_size] = '\0';
+	else {
+		narrow_buf[st.st_size] = '\n';
+		narrow_buf[st.st_size+1] = '\0';
+	}
+	n = 0;
+	for (p = narrow_buf; *p; p = strchr(p, '\n')+1)
+		n++;
+	if (!n)
+		return 0;
+	narrow_prefix = xmalloc(sizeof(*narrow_prefix)*(n+1));
+	p = narrow_buf;
+	for (i = 0; i < n; i++) {
+		pp = p;
+		p = strchr(p, '\n') + 1;
+		len = p - pp;
+		while (len &&
+		       (pp[len-1] == '\n' ||
+			pp[len-1] == '\r'))
+			len--;
+		pp[len] = '\0';
+		if (!valid_narrow_prefix(pp, i ? narrow_prefix[i-1] : NULL, 0))
+			die("Invalid $GIT_DIR/narrow");
+		narrow_prefix[i] = pp;
+	}
+	narrow_prefix[n] = NULL;
+	return 0;
+}
+
+const char **get_narrow_prefix()
+{
+	return narrow_prefix;
+}
+
+char *get_narrow_string()
+{
+	struct strbuf sb = STRBUF_INIT;
+	const char **prefix = get_narrow_prefix();
+	while (*prefix) {
+		strbuf_addstr(&sb, *prefix);
+		strbuf_addch(&sb, '\n');
+		prefix++;
+	}
+	return strbuf_detach(&sb, NULL);
+}
diff --git a/narrow-tree.h b/narrow-tree.h
new file mode 100644
index 0000000..2097436
--- /dev/null
+++ b/narrow-tree.h
@@ -0,0 +1,3 @@
+extern int valid_narrow_prefix(const char *prefix, const char *prev_prefix, int quiet);
+extern int check_narrow_prefix();
+extern char *get_narrow_string();
diff --git a/t/t0063-narrow-repo.sh b/t/t0063-narrow-repo.sh
new file mode 100755
index 0000000..51b753d
--- /dev/null
+++ b/t/t0063-narrow-repo.sh
@@ -0,0 +1,46 @@
+#!/bin/sh
+
+test_description='narrow index'
+
+. ./test-lib.sh
+
+test_expect_success 'empty $GIT_DIR/narrow' '
+	: >.git/narrow &&
+	git rev-parse --narrow-prefix >result &&
+	: >expected
+	test_cmp expected result
+'
+
+test_expect_success 'empty line' '
+	echo >.git/narrow &&
+	test_must_fail git rev-parse --narrow-prefix
+'
+
+test_expect_success 'single prefix' '
+	echo a >.git/narrow &&
+	git rev-parse --narrow-prefix >result &&
+	echo a >expected
+	test_cmp expected result
+'
+
+test_expect_success 'trailing slash in prefix' '
+	echo a/ >.git/narrow &&
+	test_must_fail git rev-parse --narrow-prefix
+'
+
+test_expect_success 'sorted multiple prefix' '
+	echo a >.git/narrow &&
+	echo b >>.git/narrow &&
+	git rev-parse --narrow-prefix >result &&
+	echo a >expected
+	echo b >>expected
+	test_cmp expected result
+'
+
+test_expect_success 'unsorted multiple prefix' '
+	echo b >.git/narrow &&
+	echo a >>.git/narrow &&
+	test_must_fail git rev-parse --narrow-prefix
+'
+
+test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 04/17] index: make narrow index incompatible with older git

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

Index in narrow repos is also narrowed and should not be used to
create commits straight away (to be explained later on). On the other
hand, while normal index can still be used in narrow repos, it should
be narrowed when the repo becomes narrow. Disallow that case too.

Add non-optional extension "narw" so that older git will refuse to
read it. Also check narrow prefix in index 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           |   32 ++++++++++++++++++++++++++++++--
 t/t0063-narrow-repo.sh |   28 ++++++++++++++++++++++++++++
 3 files changed, 59 insertions(+), 2 deletions(-)

diff --git a/cache.h b/cache.h
index d09c4fc..88a2ec6 100644
--- a/cache.h
+++ b/cache.h
@@ -292,6 +292,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 1f42473..250013c 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -12,6 +12,7 @@
 #include "commit.h"
 #include "blob.h"
 #include "resolve-undo.h"
+#include "narrow-tree.h"
 
 static struct cache_entry *refresh_cache_entry(struct cache_entry *ce, int really);
 
@@ -25,8 +26,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_RESOLVE_UNDO 0x52455543 /* "REUC" */
+#define CACHE_EXT_TREE		0x54524545	/* "TREE" */
+#define CACHE_EXT_RESOLVE_UNDO	0x52455543	/* "REUC" */
+#define CACHE_EXT_NARROW	0x6e617277	/* "narw" */
 
 struct index_state the_index;
 
@@ -1188,6 +1190,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 +1357,18 @@ 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))
+		;		/* good */
+	else if (get_narrow_prefix() && istate->narrow_prefix) {
+		char *buf = get_narrow_string();
+		if (strcmp(buf, istate->narrow_prefix))
+			die("Invalid index, narrow prefix does not match $GIT_DIR/narrow");
+		free(buf);
+	}
+	else
+		die("Invalid index, not suitable for narrow repository");
+
 	return istate->cache_nr;
 
 unmap:
@@ -1378,6 +1395,8 @@ int discard_index(struct index_state *istate)
 	free(istate->alloc);
 	istate->alloc = NULL;
 	istate->initialized = 0;
+	free(istate->narrow_prefix);
+	istate->narrow_prefix = NULL;
 
 	/* no need to throw away allocated active_cache */
 	return 0;
@@ -1607,6 +1626,15 @@ int write_index(struct index_state *istate, int newfd)
 		if (err)
 			return -1;
 	}
+	if (get_narrow_prefix()) {
+		char *buf = get_narrow_string();
+		int len = strlen(buf)+1;
+		err = write_index_ext_header(&c, newfd, CACHE_EXT_NARROW, len) < 0 ||
+			ce_write(&c, newfd, buf, len) < 0;
+		free(buf);
+		if (err)
+			return -1;
+	}
 
 	if (ce_flush(&c, newfd) || fstat(newfd, &st))
 		return -1;
diff --git a/t/t0063-narrow-repo.sh b/t/t0063-narrow-repo.sh
index 51b753d..926802c 100755
--- a/t/t0063-narrow-repo.sh
+++ b/t/t0063-narrow-repo.sh
@@ -43,4 +43,32 @@ test_expect_success 'unsorted multiple prefix' '
 	test_must_fail git rev-parse --narrow-prefix
 '
 
+test_expect_success 'create narrow index' '
+	echo a >.git/narrow &&
+	: >foo
+	git add foo &&
+	test -f .git/index
+'
+
+test_expect_success '$GIT_DIR/narrow and index do not match' '
+	echo b >.git/narrow &&
+	test_must_fail git add foo
+'
+
+test_expect_success 'narrow index and normal repo' '
+	rm .git/narrow &&
+	test_must_fail git add foo
+'
+
+test_expect_success 'turn to normal index again' '
+	rm .git/index &&
+	git add foo &&
+	test -f .git/index
+'
+
+test_expect_success 'normal index and narrow repo' '
+	echo a >.git/narrow &&
+	test_must_fail git add foo
+'
+
 test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 05/17] pack-objects: support narrow packs with pathspecs

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Documentation/git-pack-objects.txt |    2 +-
 builtin/pack-objects.c             |   18 ++++++++++++++++--
 t/t6000-rev-list-misc.sh           |    9 +++++++++
 3 files changed, 26 insertions(+), 3 deletions(-)

diff --git a/Documentation/git-pack-objects.txt b/Documentation/git-pack-objects.txt
index 8ed09c0..cad8c06 100644
--- a/Documentation/git-pack-objects.txt
+++ b/Documentation/git-pack-objects.txt
@@ -13,7 +13,7 @@ SYNOPSIS
 	[--no-reuse-delta] [--delta-base-offset] [--non-empty]
 	[--local] [--incremental] [--window=N] [--depth=N]
 	[--revs [--unpacked | --all]*] [--stdout | base-name]
-	[--keep-true-parents] < object-list
+	[--keep-true-parents] [ -- path... ] < object-list
 
 
 DESCRIPTION
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 789f6bf..26044b8 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -30,8 +30,8 @@ static const char pack_usage[] =
   "        [--no-reuse-delta] [--no-reuse-object] [--delta-base-offset]\n"
   "        [--threads=N] [--non-empty] [--revs [--unpacked | --all]*]\n"
   "        [--reflog] [--stdout | base-name] [--include-tag]\n"
-  "        [--keep-unreachable | --unpack-unreachable \n"
-  "        [<ref-list | <object-list]";
+  "        [--keep-unreachable | --unpack-unreachable]\n"
+  "        [ -- path ... ] [<ref-list | <object-list]";
 
 struct object_entry {
 	struct pack_idx_entry idx;
@@ -2278,6 +2278,11 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			grafts_replace_parents = 0;
 			continue;
 		}
+		if (!strcmp(arg, "--")) {
+			if (!pack_to_stdout)
+				die("either --stdout of pack basename must be specified");
+			break;
+		}
 		usage(pack_usage);
 	}
 
@@ -2300,6 +2305,15 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	if (pack_to_stdout != !base_name)
 		usage(pack_usage);
 
+	if (!argv[i] || !strcmp(argv[i], "--")) {
+		if (rp_ac+(argc-i)+1 >= rp_ac_alloc) {
+			rp_ac_alloc = rp_ac + (argc-i) + 1;
+			rp_av = xrealloc(rp_av, rp_ac_alloc * sizeof(*rp_av));
+		}
+		memcpy(rp_av+rp_ac, argv+i, sizeof(*argv)*(argc-i));
+		rp_ac += argc-i;
+	}
+
 	if (!pack_to_stdout && !pack_size_limit)
 		pack_size_limit = pack_size_limit_cfg;
 	if (pack_to_stdout && pack_size_limit)
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index b6a7c9c..0386313 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -31,6 +31,15 @@ test_expect_success 'rev-list --objects with pathspecs and deeper paths' '
 	! grep unwanted_file output
 '
 
+test_expect_success 'pack-objects with pathspecs' '
+	echo HEAD|git pack-objects --revs --stdout -- foo > output.pack &&
+	git index-pack --stdin -o output.idx < output.pack &&
+	git verify-pack -v output.pack >output &&
+	grep "^e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 blob" output &&
+	test "$(grep blob output|wc -l)" = 1 &&
+	test "$(grep tree output|wc -l)" = 2
+'
+
 test_expect_success 'rev-list --objects with pathspecs and copied files' '
 	git checkout --orphan junio-testcase &&
 	git rm -rf . &&
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 06/17] {fetch,upload}-pack: support narrow repository

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

If $GIT_DIR/narrow is set, fetch-pack will send "narrow-tree" lines to
upload-pack, where the prefixes are passed to rev-list mechanism to
produce a narrow pack.

"narrow-tree" capability is required for this to work.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Documentation/git-fetch-pack.txt          |    3 ++
 Documentation/technical/pack-protocol.txt |    3 ++
 builtin/fetch-pack.c                      |    9 +++++++
 upload-pack.c                             |   38 +++++++++++++++++++++++++++-
 4 files changed, 51 insertions(+), 2 deletions(-)

diff --git a/Documentation/git-fetch-pack.txt b/Documentation/git-fetch-pack.txt
index 4a8487c..19b0d92 100644
--- a/Documentation/git-fetch-pack.txt
+++ b/Documentation/git-fetch-pack.txt
@@ -25,6 +25,9 @@ This command degenerates to download everything to complete the
 asked refs from the remote side when the local side does not
 have a common ancestor commit.
 
+In narrow repositories, it asks 'git-upload-pack' to send only objects
+within narrow area defined in $GIT_DIR/narrow.
+
 
 OPTIONS
 -------
diff --git a/Documentation/technical/pack-protocol.txt b/Documentation/technical/pack-protocol.txt
index 369f91d..39474d2 100644
--- a/Documentation/technical/pack-protocol.txt
+++ b/Documentation/technical/pack-protocol.txt
@@ -215,6 +215,9 @@ discovery phase as 'want' lines. Clients MUST send at least one
 obj-id in a 'want' command which did not appear in the response
 obtained through ref discovery.
 
+If client is requesting narrow clone, it must send 'narrow-tree'
+lines before 'want' lines.
+
 If client is requesting a shallow clone, it will now send a 'deepen'
 line with the depth it is requesting.
 
diff --git a/builtin/fetch-pack.c b/builtin/fetch-pack.c
index dbd8b7b..591e0e4 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,12 @@ static int find_common(int fd[2], unsigned char *result_sha1,
 	for_each_ref(rev_list_insert_ref, NULL);
 
 	fetching = 0;
+	narrow_prefix = get_narrow_prefix();
+	if (narrow_prefix) {
+		const char **p = narrow_prefix;
+		while (*p)
+			packet_buf_write(&req_buf, "narrow-tree %s\n", *p++);
+	}
 	for ( ; refs ; refs = refs->next) {
 		unsigned char *remote = refs->old_sha1;
 		const char *remote_hex;
@@ -692,6 +699,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");
diff --git a/upload-pack.c b/upload-pack.c
index cc1983f..f3747e5 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -41,6 +41,8 @@ static int use_sideband;
 static int debug_fd;
 static int advertise_refs;
 static int stateless_rpc;
+const char **narrow_prefix;
+int narrow_prefix_nr;
 
 static void reset_timeout(void)
 {
@@ -118,6 +120,10 @@ static int do_rev_list(int in, int out, void *user_data)
 	revs.simplify_history = 0;
 	if (use_thin_pack)
 		revs.edge_hint = 1;
+	if (narrow_prefix) {
+		revs.prune_data = narrow_prefix;
+		narrow_prefix[narrow_prefix_nr] = NULL;
+	}
 
 	for (i = 0; i < want_obj.nr; i++) {
 		struct object *o = want_obj.objects[i].item;
@@ -154,9 +160,10 @@ static void create_pack_file(void)
 		"corruption on the remote side.";
 	int buffered = -1;
 	ssize_t sz;
-	const char *argv[10];
+	const char **argv;
 	int arg = 0;
 
+	argv = xmalloc(sizeof(*argv)*(11+narrow_prefix_nr));
 	if (shallow_nr) {
 		memset(&rev_list, 0, sizeof(rev_list));
 		rev_list.proc = do_rev_list;
@@ -180,6 +187,11 @@ static void create_pack_file(void)
 		argv[arg++] = "--delta-base-offset";
 	if (use_include_tag)
 		argv[arg++] = "--include-tag";
+	if (narrow_prefix) {
+		argv[arg++] = "--";
+		memcpy(argv+arg, narrow_prefix, narrow_prefix_nr*sizeof(*argv));
+		arg += narrow_prefix_nr;
+	}
 	argv[arg++] = NULL;
 
 	memset(&pack_objects, 0, sizeof(pack_objects));
@@ -307,6 +319,7 @@ static void create_pack_file(void)
 		error("git upload-pack: git-pack-objects died with error.");
 		goto fail;
 	}
+	free(argv);
 	if (shallow_nr && finish_async(&rev_list))
 		goto fail;	/* error was already reported */
 
@@ -500,6 +513,22 @@ static void receive_needs(void)
 		if (debug_fd)
 			write_in_full(debug_fd, line, len);
 
+		if (!prefixcmp(line, "narrow-tree ")) {
+			char *s;
+			int len;
+			len = strlen(line+12);
+			s = malloc(len+1);
+			memcpy(s, line+12, len-1);
+			s[len-1] = '\0'; /* \n */
+			if (s[len-2] == '/')
+				die("trailing slash in narrow prefix not allowed, %s", line);
+
+			narrow_prefix_nr++;
+			narrow_prefix = xrealloc(narrow_prefix,
+						 sizeof(*narrow_prefix)*(narrow_prefix_nr+1));
+			narrow_prefix[narrow_prefix_nr-1] = s;
+			continue;
+		}
 		if (!prefixcmp(line, "shallow ")) {
 			unsigned char sha1[20];
 			struct object *object;
@@ -563,6 +592,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) {
@@ -620,7 +652,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)
@@ -725,6 +757,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 07/17] unpack-trees: split traverse_trees() code into a separate function

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

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

diff --git a/unpack-trees.c b/unpack-trees.c
index 3c7a7c9..4889e24 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -792,6 +792,39 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	return mask;
 }
 
+static int unpack_traverse(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
+{
+	const char *prefix = o->prefix ? o->prefix : "";
+	struct traverse_info info;
+
+	if (!len)
+		return 0;
+
+	setup_traverse_info(&info, prefix);
+	info.fn = unpack_callback;
+	info.data = o;
+	info.show_all_errors = o->show_all_errors;
+
+	if (o->prefix) {
+		/*
+		 * Unpack existing index entries that sort before the
+		 * prefix the tree is spliced into.  Note that o->merge
+		 * is always true in this case.
+		 */
+		while (1) {
+			struct cache_entry *ce = next_cache_entry(o);
+			if (!ce)
+				break;
+			if (ce_in_traverse_path(ce, &info))
+				break;
+			if (unpack_index_entry(ce, o) < 0)
+				return 1;
+		}
+	}
+
+	return traverse_trees(len, t, &info) < 0;
+}
+
 /*
  * 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.
@@ -831,35 +864,8 @@ int unpack_trees(unsigned len, struct tree_desc *t, struct unpack_trees_options
 		dfc = xcalloc(1, cache_entry_size(0));
 	o->df_conflict_entry = dfc;
 
-	if (len) {
-		const char *prefix = o->prefix ? o->prefix : "";
-		struct traverse_info info;
-
-		setup_traverse_info(&info, prefix);
-		info.fn = unpack_callback;
-		info.data = o;
-		info.show_all_errors = o->show_all_errors;
-
-		if (o->prefix) {
-			/*
-			 * Unpack existing index entries that sort before the
-			 * prefix the tree is spliced into.  Note that o->merge
-			 * is always true in this case.
-			 */
-			while (1) {
-				struct cache_entry *ce = next_cache_entry(o);
-				if (!ce)
-					break;
-				if (ce_in_traverse_path(ce, &info))
-					break;
-				if (unpack_index_entry(ce, o) < 0)
-					goto return_failed;
-			}
-		}
-
-		if (traverse_trees(len, t, &info) < 0)
-			goto return_failed;
-	}
+	if (unpack_traverse(len, t, o))
+		goto return_failed;
 
 	/* Any left-over entries in the index? */
 	if (o->merge) {
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 08/17] unpack-trees: support unpack trees 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
specified in $GIT_DIR/narrow, which narrow repo has all needed trees
and blobs. This makes the result index unsuitable for creating commits
(you would have "narrow commits", which are not what anybody
wants). An extra step will be needed to create a proper commit.

On the other hand, because all paths in narrow index are reachable,
and other worktree/index or tree/index operations rely on
unpack_trees() to traverse, which is already narrow-adapted, most
operations will not need modification to work in narrow repositories.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Will probably drop this and the previous patch in favor of Elijah's
 04/15 and 05/15.


 t/t1013-read-tree-narrow.sh |   72 ++++++++++++++++++++++++++++++++++
 unpack-trees.c              |   91 ++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 162 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..8fa37d9
--- /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 pack -- t1/t12 &&
+	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 4889e24..f945e5f 100644
--- a/unpack-trees.c
+++ b/unpack-trees.c
@@ -792,7 +792,7 @@ static int unpack_callback(int n, unsigned long mask, unsigned long dirmask, str
 	return mask;
 }
 
-static int unpack_traverse(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
+static int unpack_traverse_1(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
 {
 	const char *prefix = o->prefix ? o->prefix : "";
 	struct traverse_info info;
@@ -826,6 +826,95 @@ static int unpack_traverse(unsigned len, struct tree_desc *t, struct unpack_tree
 }
 
 /*
+ * path_to_tree_sha1() does not accept tree_desc, so we need to
+ * process the first tree. path_to_tree_sha1() can then do the rest
+ */
+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 path_to_tree_sha1(newsha1, entry.sha1, slash+1);
+			else {
+				hashcpy(newsha1, entry.sha1);
+				return 1;
+			}
+		}
+	}
+	return 0;
+}
+
+static int unpack_traverse_narrow(unsigned len, struct tree_desc *t,
+				  struct unpack_trees_options *o,
+				  const char *narrow_prefix)
+{
+	struct tree_desc *t2;
+	char *prefix = NULL;
+	const char *old_prefix;
+	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, 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);
+	}
+	old_prefix = o->prefix;
+	if (!old_prefix)
+		prefix = xstrdup(narrow_prefix);
+	else {
+		prefix = xmalloc(strlen(narrow_prefix) + strlen(o->prefix)+1);
+		strcpy(prefix, o->prefix);
+		strcat(prefix, narrow_prefix);
+	}
+	o->prefix = prefix;
+	ret = unpack_traverse_1(len, t2, o);
+	o->prefix = old_prefix;
+	for (i = 0; i < len; i++)
+		free(buf[i]);
+	free(prefix);
+	free(t2);
+	free(buf);
+	return ret;
+}
+
+static int unpack_traverse(unsigned len, struct tree_desc *t, struct unpack_trees_options *o)
+{
+	const char **p = get_narrow_prefix();
+
+	if (!len)
+		return 0;
+
+	if (!p)
+		return unpack_traverse_1(len, t, o);
+
+	while (*p) {
+		int ret = unpack_traverse_narrow(len, t, o, *p);
+		if (ret)
+			return ret;
+		p++;
+	}
+	return 0;
+}
+
+/*
  * 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.
  */
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 09/17] 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 |   41 +++++++++++++++++++++++++++++++++++++----
 1 files changed, 37 insertions(+), 4 deletions(-)

diff --git a/cache-tree.c b/cache-tree.c
index c60cf91..6aaf265 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -602,7 +602,8 @@ 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,
+				 char *base, int baselen)
 {
 	struct tree_desc desc;
 	struct name_entry entry;
@@ -611,17 +612,48 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 	hashcpy(it->sha1, tree->object.sha1);
 	init_tree_desc(&desc, tree->buffer, tree->size);
 	cnt = 0;
+	if (base && baselen)
+		base[baselen++] = '/';
 	while (tree_entry(&desc, &entry)) {
 		if (!S_ISDIR(entry.mode))
 			cnt++;
 		else {
 			struct cache_tree_sub *sub;
-			struct tree *subtree = lookup_tree(entry.sha1);
+			struct tree *subtree;
+			int found = 2; /* all interesting */
+			const char **p = get_narrow_prefix();
+			int len = 0;
+
+			if (p) {
+				found = 0; /* not interesting */
+				len = strlen(entry.path);
+				if (base)
+					memcpy(base+baselen, entry.path, len+1);
+				while (*p) {
+					if (!prefixcmp(entry.path, *p)) {
+						found = 2;
+						break;
+					}
+					if (!prefixcmp(*p, entry.path)) {
+						found = 1;
+						break;
+					}
+					p++;
+				}
+				if (!found) {
+					cnt++;
+					continue;
+				}
+			}
+
+			subtree = lookup_tree(entry.sha1);
 			if (!subtree->object.parsed)
 				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,
+					     found == 1 ? base : NULL,
+					     baselen+len);
 			cnt += sub->cache_tree->entry_count;
 		}
 	}
@@ -630,9 +662,10 @@ static void prime_cache_tree_rec(struct cache_tree *it, struct tree *tree)
 
 void prime_cache_tree(struct cache_tree **it, struct tree *tree)
 {
+	char path[PATH_MAX];
 	cache_tree_free(it);
 	*it = cache_tree();
-	prime_cache_tree_rec(*it, tree);
+	prime_cache_tree_rec(*it, tree, get_narrow_prefix() ? path : NULL, 0);
 }
 
 /*
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 10/17] get_pathspec(): support narrow pathspec rewriting

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

Operations in a narrow repository would only work if you limit
yourself within narrow area. Usually that means users have to either
stay inside narrow area, or do "git blah blah -- narrow/prefix" so
that git won't step on the line. (Of course that only affects commands
that take pathspec)

Make their life easier by appending narrow prefix automatically, as
long as the given pathspecs are simple enough. In other words, fancy
wildcards might not work.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 .gitignore                 |    1 +
 Makefile                   |    1 +
 cache.h                    |    1 +
 setup.c                    |  172 ++++++++++++++++++++++++++++++++++++++++++--
 t/t0062-narrow-pathspec.sh |  150 ++++++++++++++++++++++++++++++++++++++
 test-get-pathspec.c        |   17 +++++
 6 files changed, 337 insertions(+), 5 deletions(-)
 create mode 100755 t/t0062-narrow-pathspec.sh
 create mode 100644 test-get-pathspec.c

diff --git a/.gitignore b/.gitignore
index fcdd822..af9bae6 100644
--- a/.gitignore
+++ b/.gitignore
@@ -165,6 +165,7 @@
 /test-delta
 /test-dump-cache-tree
 /test-genrandom
+/test-get-pathspec
 /test-index-version
 /test-match-trees
 /test-parse-options
diff --git a/Makefile b/Makefile
index f1aaba9..3bbb571 100644
--- a/Makefile
+++ b/Makefile
@@ -408,6 +408,7 @@ TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
 TEST_PROGRAMS_NEED_X += test-dump-cache-tree
 TEST_PROGRAMS_NEED_X += test-genrandom
+TEST_PROGRAMS_NEED_X += test-get-pathspec
 TEST_PROGRAMS_NEED_X += test-match-trees
 TEST_PROGRAMS_NEED_X += test-parse-options
 TEST_PROGRAMS_NEED_X += test-path-utils
diff --git a/cache.h b/cache.h
index 88a2ec6..9c014ef 100644
--- a/cache.h
+++ b/cache.h
@@ -417,6 +417,7 @@ extern void set_git_work_tree(const char *tree);
 
 #define ALTERNATE_DB_ENVIRONMENT "GIT_ALTERNATE_OBJECT_DIRECTORIES"
 
+extern const char **get_pathspec_narrow(const char *prefix, const char **pathspec, int narrow);
 extern const char **get_pathspec(const char *prefix, const char **pathspec);
 extern void setup_work_tree(void);
 extern const char *setup_git_directory_gently(int *);
diff --git a/setup.c b/setup.c
index 2769160..c19d53d 100644
--- a/setup.c
+++ b/setup.c
@@ -123,20 +123,61 @@ void verify_non_filename(const char *prefix, const char *arg)
 	    "Use '--' to separate filenames from revisions", arg);
 }
 
-const char **get_pathspec(const char *prefix, const char **pathspec)
+static const char **dup_pathspec(const char **pathspec)
+{
+	const char **p = pathspec;
+	int n = 1;
+	if (!p)
+		return NULL;
+	while (*p) {
+		n++;
+		p++;
+	}
+	p = xmalloc(sizeof(*p)*n);
+	memcpy(p, pathspec, sizeof(*p)*n);
+	return p;
+}
+
+
+const char **get_pathspec_narrow(const char *prefix, const char **pathspec, int narrow)
 {
 	const char *entry = *pathspec;
-	const char **src, **dst;
+	const char **src, **dst, **p;
 	int prefixlen;
+	const char **narrow_prefix = narrow ? get_narrow_prefix() : NULL;
+	int ps_hit_count, np_hit_count;
+	int *ps_hitmap, *np_hitmap;
+	int i, n;
+
+	if (!entry && !prefix) {
+		pathspec = dup_pathspec(narrow_prefix);
+		goto done;
+	}
 
-	if (!prefix && !entry)
-		return NULL;
+	/*
+	 * if prefix is also a prefix of narrow_prefix, use
+	 * it. Otherwise just return narrow_prefix
+	 */
+	if (!entry && narrow_prefix) {
+		p = narrow_prefix;
+		while (*p) {
+			if (!prefixcmp(prefix, *p))
+				break;
+			p++;
+		}
+		if (!*p) {
+			pathspec = dup_pathspec(narrow_prefix);
+			goto done;
+		}
+		/* otherwise fall through */
+	}
 
 	if (!entry) {
 		static const char *spec[2];
 		spec[0] = prefix;
 		spec[1] = NULL;
-		return spec;
+		pathspec = spec;
+		goto done;
 	}
 
 	/* Otherwise we have to re-write the entries.. */
@@ -149,11 +190,132 @@ const char **get_pathspec(const char *prefix, const char **pathspec)
 		src++;
 	}
 	*dst = NULL;
+
+	/*
+	 * And filter rewritten entries against narrow_prefix..  The
+	 * rule is, if a prefix is "x" and we have narrow prefix x/y,
+	 * then that prefix is taken out and replaced by x/y. If we
+	 * have two narrow prefix x/y and x/z, both will be in.
+	 */
+	if (narrow_prefix) {
+		for (n = 0, p = narrow_prefix; *p; p++)
+			n++;
+
+		np_hitmap = xmalloc(sizeof(*np_hitmap) * ((n+32)/32));
+		memset(np_hitmap, 0, sizeof(*np_hitmap) * ((n+32)/32));
+		ps_hitmap = xmalloc(sizeof(*ps_hitmap) * ((dst-pathspec+32)/32));
+		memset(ps_hitmap, 0, sizeof(*ps_hitmap) * ((dst-pathspec+32)/32));
+
+#define HIT(hitmap, x) hitmap[(x) / 32] |= 1 << ((x) % 32)
+#define GOT_HIT(hitmap, x) (hitmap[(x) / 32] & (1 << ((x) % 32)))
+		/*
+		 * Let's see how many narrow prefix we hit, then we
+		 * know if pathspec has enough space, or we need a
+		 * bigger one.
+		 */
+		src = pathspec;
+		ps_hit_count = 0;
+		/* np_hit_count can't be counted here because one
+		   narrow prefix can be hit many times */
+		while (*src) {
+			int pathspec_hit = 0, hit = 0;
+			p = narrow_prefix;
+			while (*p) {
+				if (!prefixcmp(*p, *src)) {
+					HIT(np_hitmap, p - narrow_prefix);
+					pathspec_hit++;
+				}
+				else if (!prefixcmp(*src, *p)) {
+					/*
+					 * If any of previous pathspec has hit
+					 * a narrow prefix, that narrow prefix
+					 * will be included as a replacement for
+					 * the pathspec. So any other pathspecs
+					 * that are stricter than that pathspec
+					 * is redundant, mark pathspec_hit to remove
+					 * it.
+					 */
+					if (GOT_HIT(np_hitmap, p - narrow_prefix))
+						pathspec_hit++;
+					hit++;
+				}
+				p++;
+			}
+			if (!hit && !pathspec_hit)
+				die("Pathspec %s is outside narrow area", *src);
+			if (pathspec_hit) {
+				HIT(ps_hitmap, src-pathspec);
+				ps_hit_count++;
+			}
+			src++;
+		}
+
+		/* All pathspec is inside narrow area */
+		if (!ps_hit_count)
+			goto done;
+
+		np_hit_count = 0;
+		for (i = 0; i < n; i++)
+			if (GOT_HIT(np_hitmap, i))
+				np_hit_count++;
+
+		/*
+		 * All pathspec is a prefix of narrow_prefix, or one
+		 * pathspec hits all narrow_prefix, just use
+		 * narrow_prefix instead. Of course we need to check
+		 * what narrow_prefix is hit.
+		 */
+		if (ps_hit_count == (dst - pathspec) || n == np_hit_count) {
+			pathspec = dup_pathspec(narrow_prefix);
+			for (i = 0; i < n; i++) {
+				if (GOT_HIT(np_hitmap, i))
+					continue; /* hit, go on */
+				memcpy(pathspec+i, pathspec+i+1, (n-i) * sizeof(*pathspec));
+			}
+			goto done;
+		}
+
+		/*
+		 * So we have ps_hit pathspecs hit, which will be
+		 * removed, and a np_hit_count prefixes hit, which
+		 * will be in.
+		 *
+		 * Check if we have enough space for the new
+		 * np_hit_count prefix.
+		 */
+		p = ps_hit_count < np_hit_count ? xmalloc(sizeof(*p)*(dst-pathspec-ps_hit_count+np_hit_count+1)) : pathspec;
+		src = pathspec;
+		dst = p;
+		while (*src) {
+			if (GOT_HIT(ps_hitmap, src-pathspec)) {
+				src++;
+				continue;
+			}
+			*dst++ = *src++;
+		}
+		for (i = 0; i < n; i++) {
+			if (GOT_HIT(np_hitmap, i))
+				*dst++ = narrow_prefix[i];
+		}
+		*dst = NULL;
+		pathspec = p;
+	}
+
 	if (!*pathspec)
 		return NULL;
+done:
+	if (pathspec)
+		trace_argv_printf(pathspec, "trace: pathspec: ");
+	else
+		trace_printf("trace: pathspec: <empty>\n");
 	return pathspec;
 }
 
+const char **get_pathspec(const char *prefix, const char **pathspec)
+{
+	return get_pathspec_narrow(prefix, pathspec, 1);
+}
+
 /*
  * Test if it looks like we're at a git directory.
  * We want to see:
diff --git a/t/t0062-narrow-pathspec.sh b/t/t0062-narrow-pathspec.sh
new file mode 100755
index 0000000..ef5d059
--- /dev/null
+++ b/t/t0062-narrow-pathspec.sh
@@ -0,0 +1,150 @@
+#!/bin/sh
+
+test_description='Narrow pathspec rewrite tests'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	mkdir a b c &&
+	mkdir a/aa a/ab a/ac &&
+	mkdir b/ba b/bb b/bc &&
+	mkdir a/aa/aaa a/aa/aab a/aa/aac &&
+	mkdir a/ab/aba a/ab/abb a/ab/abc
+'
+
+test_expect_success '() no pathspec' '
+	test-get-pathspec >result &&
+	: >expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a] no pathspec' '
+	echo a >.git/narrow &&
+	test-get-pathspec >result &&
+	echo a >expected &&
+	test_cmp expected result
+'
+
+# Because narrow prefix is "a". put a/ to check that the prefix is
+# actually from command line not from narrow prefix
+test_expect_success '() [a] a/' '
+	echo a >.git/narrow &&
+	test-get-pathspec a/ >result &&
+	echo a/ >expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a] a/aa' '
+	echo a >.git/narrow &&
+	test-get-pathspec a/aa >result &&
+	echo a/aa >expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a] b' '
+	echo a >.git/narrow &&
+	test_must_fail test-get-pathspec b
+'
+
+test_expect_success '() [a/aa] a' '
+	echo a/aa >.git/narrow &&
+	test-get-pathspec a >result &&
+	echo a/aa >expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a/aa] a/ab' '
+	echo a/aa >.git/narrow &&
+	test_must_fail test-get-pathspec a/ab
+'
+
+test_expect_success '() [a/aa a/ab] a' '
+	echo a/aa >.git/narrow &&
+	echo a/ab >>.git/narrow &&
+	test-get-pathspec a >result &&
+	echo a/aa >expected &&
+	echo a/ab >>expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a/aa a/ab] a a/aa/aab' '
+	echo a/aa >.git/narrow &&
+	echo a/ab >>.git/narrow &&
+	test-get-pathspec a a/aa/aab >result &&
+	echo a/aa >expected &&
+	echo a/ab >>expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a/aa a/ab] a/aa a/ab/abc' '
+	echo a/aa >.git/narrow &&
+	echo a/ab >>.git/narrow &&
+	test-get-pathspec a/aa a/ab/abc >result &&
+	echo a/ab/abc >expected &&
+	echo a/aa >>expected &&
+	test_cmp expected result
+'
+
+# a/aa is replaced by a/aa/aaa and a/aa/aab
+# reallocation must be done
+test_expect_success '() [a/aa/aaa a/aa/aab a/ab] a/aa a/ab/abc' '
+	echo a/aa/aaa >.git/narrow &&
+	echo a/aa/aab >>.git/narrow &&
+	echo a/ab >>.git/narrow &&
+	test-get-pathspec a/aa a/ab/abc >result &&
+	echo a/ab/abc >expected &&
+	echo a/aa/aaa >>expected &&
+	echo a/aa/aab >>expected &&
+	test_cmp expected result
+'
+
+test_expect_success '() [a b] no pathspec' '
+	echo a >.git/narrow &&
+	echo b >>.git/narrow &&
+	test-get-pathspec >result &&
+	echo a >expected &&
+	echo b >>expected &&
+	test_cmp expected result
+'
+
+test_expect_success '(a) no pathspec' '
+	: >.git/narrow
+	(
+	cd a
+	test-get-pathspec >result &&
+	echo a/ >expected &&
+	test_cmp expected result
+	)
+'
+
+test_expect_success '(a) [a] no pathspec' '
+	echo a >.git/narrow &&
+	(
+	cd a
+	test-get-pathspec >result &&
+	echo a/ >expected &&
+	test_cmp expected result
+	)
+'
+
+test_expect_success '(a) [a] aa' '
+	echo a >.git/narrow &&
+	(
+	cd a
+	test-get-pathspec aa >result &&
+	echo a/aa >expected &&
+	test_cmp expected result
+	)
+'
+
+test_expect_success '(b) [a] no pathspec' '
+	echo a >.git/narrow &&
+	(
+	cd b
+	test-get-pathspec >result &&
+	echo a >expected &&
+	test_cmp expected result
+	)
+'
+
+test_done
diff --git a/test-get-pathspec.c b/test-get-pathspec.c
new file mode 100644
index 0000000..413c5b0
--- /dev/null
+++ b/test-get-pathspec.c
@@ -0,0 +1,17 @@
+#include "cache.h"
+
+int main(int argc, char **argv)
+{
+	int gitdir;
+	const char *prefix = setup_git_directory_gently(&gitdir); /* get narrow_prefix */
+	const char **p;
+
+	p = get_pathspec(prefix, (const char **)argv+1);
+	if (!p)
+		return 0;
+	while (*p) {
+		printf("%s\n", *p);
+		p++;
+	}
+	return 0;
+}
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 11/17] pathspec retrieval fix

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

In normal repos, when there is no command line argument, it's safe to
say we don't have pathspec. In narrow repos, get_pathspec() in that
case will still generate some pathspecs (the narrow prefix). Make sure
get_pathspec() is always called.

Some commands however, especially plumbings, won't want narrow prefix
to get in the way. Use get_pathspec_narrow(...., 0); in those cases to
disable narrow pathspec rewriting.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/commit.c   |    6 ++----
 builtin/grep.c     |    5 ++---
 builtin/ls-files.c |    2 +-
 builtin/ls-tree.c  |    2 +-
 builtin/reset.c    |    3 +--
 revision.c         |    5 +++++
 6 files changed, 12 insertions(+), 11 deletions(-)

diff --git a/builtin/commit.c b/builtin/commit.c
index 66fdd22..d8c5273 100644
--- a/builtin/commit.c
+++ b/builtin/commit.c
@@ -303,8 +303,7 @@ static char *prepare_index(int argc, const char **argv, const char *prefix, int
 		return get_index_file();
 	}
 
-	if (*argv)
-		pathspec = get_pathspec(prefix, argv);
+	pathspec = get_pathspec(prefix, argv);
 
 	if (read_cache_preload(pathspec) < 0)
 		die("index file corrupt");
@@ -1083,8 +1082,7 @@ int cmd_status(int argc, const char **argv, const char *prefix)
 	handle_untracked_files_arg(&s);
 	if (show_ignored_in_status)
 		s.show_ignored_files = 1;
-	if (*argv)
-		s.pathspec = get_pathspec(prefix, argv);
+	s.pathspec = get_pathspec(prefix, argv);
 
 	read_cache_preload(s.pathspec);
 	refresh_index(&the_index, REFRESH_QUIET|REFRESH_UNMERGED, s.pathspec, NULL, NULL);
diff --git a/builtin/grep.c b/builtin/grep.c
index cf6c29f..b55a0a4 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -1058,9 +1058,8 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 			verify_filename(prefix, argv[j]);
 	}
 
-	if (i < argc)
-		paths = get_pathspec(prefix, argv + i);
-	else if (prefix) {
+	paths = get_pathspec(prefix, argv + i);
+	if (prefix && !paths) {
 		paths = xcalloc(2, sizeof(const char *));
 		paths[0] = prefix;
 		paths[1] = NULL;
diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index bb4f612..27610ab 100644
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -565,7 +565,7 @@ int cmd_ls_files(int argc, const char **argv, const char *cmd_prefix)
 	if (require_work_tree && !is_inside_work_tree())
 		setup_work_tree();
 
-	pathspec = get_pathspec(prefix, argv);
+	pathspec = get_pathspec_narrow(prefix, argv, 0);
 
 	/* be nice with submodule paths ending in a slash */
 	if (pathspec)
diff --git a/builtin/ls-tree.c b/builtin/ls-tree.c
index dc86b0d..d37eaa5 100644
--- a/builtin/ls-tree.c
+++ b/builtin/ls-tree.c
@@ -164,7 +164,7 @@ int cmd_ls_tree(int argc, const char **argv, const char *prefix)
 	if (get_sha1(argv[0], sha1))
 		die("Not a valid object name %s", argv[0]);
 
-	pathspec = get_pathspec(prefix, argv + 1);
+	pathspec = get_pathspec_narrow(prefix, argv + 1, 0);
 	tree = parse_tree_indirect(sha1);
 	if (!tree)
 		die("not a tree object");
diff --git a/builtin/reset.c b/builtin/reset.c
index 1283068..ae96c8b 100644
--- a/builtin/reset.c
+++ b/builtin/reset.c
@@ -181,8 +181,7 @@ static int interactive_reset(const char *revision, const char **argv,
 {
 	const char **pathspec = NULL;
 
-	if (*argv)
-		pathspec = get_pathspec(prefix, argv);
+	pathspec = get_pathspec(prefix, argv);
 
 	return run_add_interactive(revision, "--patch=reset", pathspec);
 }
diff --git a/revision.c b/revision.c
index ea64970..73fe894 100644
--- a/revision.c
+++ b/revision.c
@@ -1625,6 +1625,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 
 	if (prune_data)
 		revs->prune_data = get_pathspec(revs->prefix, prune_data);
+	else if (get_narrow_prefix()) {
+		const char *nul = NULL;
+		prune_data = &nul;
+		revs->prune_data = get_pathspec(revs->prefix, prune_data);
+	}
 
 	if (revs->def == NULL)
 		revs->def = opt ? opt->def : NULL;
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 12/17] clone: support --narrow option

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

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

diff --git a/Documentation/git-clone.txt b/Documentation/git-clone.txt
index dc7d3d1..d9a5729 100644
--- a/Documentation/git-clone.txt
+++ b/Documentation/git-clone.txt
@@ -12,7 +12,8 @@ SYNOPSIS
 'git clone' [--template=<template_directory>]
 	  [-l] [-s] [--no-hardlinks] [-q] [-n] [--bare] [--mirror]
 	  [-o <name>] [-b <name>] [-u <upload-pack>] [--reference <repository>]
-	  [--depth <depth>] [--recursive] [--] <repository> [<directory>]
+	  [--depth <depth>] [--narrow <path>] [--recursive]
+	  [--] <repository> [<directory>]
 
 DESCRIPTION
 -----------
@@ -161,6 +162,17 @@ objects from the source repository into a pack in the cloned repository.
 	with a long history, and would want to send in fixes
 	as patches.
 
+--narrow <path>::
+	Create a 'narrow' clone with all commit trees limited to
+	the given path. A narrow repository has a number of
+	limititations (you cannot clone or fech from it, nor push
+	into it), but is adequate if you are only interested in
+	certain paths of a large repository, and would want to
+	push some fixes.
++
+Multiple --narrow can be given. This option can also be used together
+with --depth to truncate both history and path.
+
 --recursive::
 	After the clone is created, initialize all submodules within,
 	using their default settings. This is equivalent to running
diff --git a/builtin/clone.c b/builtin/clone.c
index efb1e6f..439ce8a 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:
@@ -40,11 +41,15 @@ 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 const char **option_narrow;
 static char *option_origin = NULL;
 static char *option_branch = NULL;
 static char *option_upload_pack = "git-upload-pack";
 static int option_verbosity;
 static int option_progress;
+static int narrow_nr;
+
+static int add_narrow_prefix(const struct option *opt, const char *arg, int unset);
 
 static struct option builtin_clone_options[] = {
 	OPT__VERBOSITY(&option_verbosity),
@@ -78,6 +83,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_CALLBACK(0, "narrow", NULL, "prefix", "narrow clone",
+		     add_narrow_prefix),
 
 	OPT_END()
 };
@@ -86,6 +93,22 @@ static const char *argv_submodule[] = {
 	"submodule", "update", "--init", "--recursive", NULL
 };
 
+static int add_narrow_prefix(const struct option *opt, const char *arg, int unset)
+{
+	if (unset)
+		die("--no-narrow is not supported");
+
+	narrow_nr++;
+	option_narrow = xrealloc(option_narrow, sizeof(*option_narrow)*narrow_nr);
+	option_narrow[narrow_nr-1] = arg;
+	return 0;
+}
+
+static int narrow_cmp(const void *a, const void *b)
+{
+	return strcmp(*(const char**)a, *(const char **)b);
+}
+
 static char *get_repo_path(const char *repo, int *is_bundle)
 {
 	static char *suffix[] = { "/.git", ".git", "" };
@@ -443,6 +466,14 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		git_dir = xstrdup(mkpath("%s/.git", dir));
 	}
 
+	if (option_narrow) {
+		int i;
+		qsort(option_narrow, narrow_nr, sizeof(*option_narrow), narrow_cmp);
+		for (i = 0; i < narrow_nr; i++)
+			if (!valid_narrow_prefix(option_narrow[i], i ? option_narrow[i-1] : NULL, 0))
+				die("Invalid narrow prefix");
+	}
+
 	if (!option_bare) {
 		junk_work_tree = work_tree;
 		if (safe_create_leading_directories_const(work_tree) < 0)
@@ -515,6 +546,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 +563,16 @@ 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 i;
+			FILE *fp = fopen(git_path("narrow"), "w+");
+			for (i = 0; i < narrow_nr; i++)
+				fprintf(fp, "%s\n", option_narrow[i]);
+			fclose(fp);
+			check_narrow_prefix(); /* Install the prefix */
+		}
+
 		transport_set_verbosity(transport, option_verbosity, option_progress);
 
 		if (option_upload_pack)
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 13/17] commit: add narrow's commit_tree version

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

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>
---
 Equivalence to Elijah's 07/15 and 08/15. My way generates some throw away
 trees at write_cache_as_tree(), not good.

 commit.c      |   16 +++++++++
 commit.h      |    5 +++
 narrow-tree.c |  101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h |    4 ++
 4 files changed, 126 insertions(+), 0 deletions(-)

diff --git a/commit.c b/commit.c
index 0094ec1..c7fe7fc 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,18 @@ 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 sha1[20];
+
+	if (get_narrow_prefix()) {
+		if (join_narrow_tree(sha1, narrow_base, tree, get_narrow_prefix()))
+			die("Failed to join tree");
+		tree = sha1;
+	}
+	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 */
diff --git a/narrow-tree.c b/narrow-tree.c
index 85dbab4..110fac2 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;
@@ -104,3 +114,94 @@ char *get_narrow_string()
 	}
 	return strbuf_detach(&sb, NULL);
 }
+
+/*
+ * The opposite of narrow_tree(). Put the subtree back to the original tree.
+ */
+static int join_narrow_tree_rec(unsigned char *result,
+				const unsigned char *basetree,
+				const unsigned char *newtree,
+				const char **prefix,
+				char *base,
+				int baselen)
+{
+	struct tree_desc desc;
+	struct name_entry entry;
+	struct strbuf buffer;
+	enum object_type type;
+	unsigned long size;
+	const char **p;
+	int len, found;
+	char *buf;
+
+	buf = read_sha1_file(basetree, &type, &size);
+	if (!buf || type != OBJ_TREE)
+		die("Bad tree %s", sha1_to_hex(basetree));
+
+	if (baselen)
+		base[baselen++] = '/';
+
+	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)) {
+			strbuf_add(&buffer, entry.sha1, 20);
+			continue;
+		}
+
+		p = prefix;
+		len = strlen(entry.path);
+		found = 0;
+
+		while (*p) {
+			if (!strcmp(entry.path, *p)) {
+				found = 2;
+				break;
+			}
+			if (!prefixcmp(*p, entry.path)) {
+				found = 1;
+				break;
+			}
+			p++;
+		}
+		switch (found) {
+		case 1:
+			memcpy(base+baselen, entry.path, len+1);
+			join_narrow_tree_rec(result, entry.sha1, newtree,
+					     prefix, base, baselen+len+1);
+			break;
+		case 2:
+			if (!path_to_tree_sha1(result, newtree, *p))
+				die("Could not find tree %s in the new tree", *p);
+			break;
+		case 0:
+			hashcpy(result, entry.sha1);
+			break;
+		}
+
+		/* FIXME, what if placeholder tree does not exist? */
+
+		strbuf_add(&buffer, result, 20);
+	}
+
+	free(buf);
+	if (write_sha1_file(buffer.buf, buffer.len, tree_type, result)) {
+		base[baselen] = '\0';
+		error("Could not write tree %s", base);
+		strbuf_release(&buffer);
+		return 1;
+	}
+	strbuf_release(&buffer);
+	return 0;
+}
+
+int join_narrow_tree(unsigned char *result,
+		     const unsigned char *basetree,
+		     const unsigned char *newtree,
+		     const char **prefix)
+{
+	char path[PATH_MAX];
+	return join_narrow_tree_rec(result, basetree, newtree, prefix, path, 0);
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index 2097436..e7d84c4 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -1,3 +1,7 @@
 extern int valid_narrow_prefix(const char *prefix, const char *prev_prefix, int quiet);
 extern int check_narrow_prefix();
 extern char *get_narrow_string();
+extern int join_narrow_tree(unsigned char *result,
+			    const unsigned char *base,
+			    const unsigned char *newtree,
+			    const char **prefix);
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 14/17] 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 +++++++++-
 t/t7510-commit-narrow.sh |   30 ++++++++++++++++++++++++++++++
 2 files changed, 39 insertions(+), 1 deletions(-)
 create mode 100755 t/t7510-commit-narrow.sh

diff --git a/builtin/commit.c b/builtin/commit.c
index d8c5273..2321642 100644
--- a/builtin/commit.c
+++ b/builtin/commit.c
@@ -1349,7 +1349,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();
diff --git a/t/t7510-commit-narrow.sh b/t/t7510-commit-narrow.sh
new file mode 100755
index 0000000..1232cee
--- /dev/null
+++ b/t/t7510-commit-narrow.sh
@@ -0,0 +1,30 @@
+#!/bin/sh
+
+test_description='commit in narrow repositories'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	touch a b c &&
+	mkdir x y z &&
+	touch x/a y/b z/c &&
+	git add . &&
+	git commit -q -m initial &&
+	echo x >.git/narrow &&
+	rm .git/index &&
+	git reset --hard HEAD
+'
+
+X1_TREE=496d6428b9cf92981dc9495211e6e1120fb6f2ba
+X2_TREE=4d593e935186bcc35450336864a1aad148210a14
+
+test_expect_success 'commit' '
+	git ls-tree HEAD | sed "s/$X1_TREE/$X2_TREE/" >expected &&
+	echo x >>x/a &&
+	git add x/a &&
+	git commit -m x/a &&
+	git ls-tree HEAD >result &&
+	test_cmp expected result
+'
+
+test_done
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 15/17] write-tree: requires --narrow-base in narrow repository

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

Without a base, a full tree cannot be generated, because the index
does not contain all trees.

--narrow-base is ignored if the repository is not a narrow one.

git-am is modified to "test" write-tree, which makes git-rebase works
in simple cases.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/write-tree.c |   25 +++++++++++++++++++++++++
 git-am.sh            |    2 +-
 2 files changed, 26 insertions(+), 1 deletions(-)

diff --git a/builtin/write-tree.c b/builtin/write-tree.c
index b223af4..5da3cb3 100644
--- a/builtin/write-tree.c
+++ b/builtin/write-tree.c
@@ -8,6 +8,7 @@
 #include "tree.h"
 #include "cache-tree.h"
 #include "parse-options.h"
+#include "narrow-tree.h"
 
 static const char * const write_tree_usage[] = {
 	"git write-tree [--missing-ok] [--prefix=<prefix>/]",
@@ -18,6 +19,7 @@ int cmd_write_tree(int argc, const char **argv, const char *unused_prefix)
 {
 	int flags = 0, ret;
 	const char *prefix = NULL;
+	const char *narrow_str = NULL;
 	unsigned char sha1[20];
 	const char *me = "git-write-tree";
 	struct option write_tree_options[] = {
@@ -26,6 +28,9 @@ int cmd_write_tree(int argc, const char **argv, const char *unused_prefix)
 		{ OPTION_STRING, 0, "prefix", &prefix, "<prefix>/",
 		  "write tree object for a subdirectory <prefix>" ,
 		  PARSE_OPT_LITERAL_ARGHELP },
+		{ OPTION_STRING, 0, "narrow-base", &narrow_str, "base tree",
+		  "base tree in narrow index" ,
+		  PARSE_OPT_LITERAL_ARGHELP },
 		{ OPTION_BIT, 0, "ignore-cache-tree", &flags, NULL,
 		  "only useful for debugging",
 		  PARSE_OPT_HIDDEN | PARSE_OPT_NOARG, NULL,
@@ -40,6 +45,26 @@ int cmd_write_tree(int argc, const char **argv, const char *unused_prefix)
 	ret = write_cache_as_tree(sha1, flags, prefix);
 	switch (ret) {
 	case 0:
+		if (get_narrow_prefix()) {
+			unsigned char sha1_param[20];
+			unsigned char narrow_base[20];
+			unsigned char old_sha1[20];
+			unsigned long size;
+			void *buf;
+
+			if (!narrow_str)
+				die("write-tree in narrow repo requires --narrow-base");
+
+			if (get_sha1(narrow_str, sha1_param))
+				die("Invalid SHA1 %s", narrow_str);
+			buf = read_object_with_reference(sha1_param, tree_type, &size, narrow_base);
+			if (!buf)
+				die("Bad treeish %s", sha1_to_hex(sha1));
+			free(buf);
+			hashcpy(old_sha1, sha1);
+			if (join_narrow_tree(sha1, narrow_base, old_sha1, get_narrow_prefix()))
+				die("Failed to join tree");
+		}
 		printf("%s\n", sha1_to_hex(sha1));
 		break;
 	case WRITE_TREE_UNREADABLE_INDEX:
diff --git a/git-am.sh b/git-am.sh
index e7f008c..6adda43 100755
--- a/git-am.sh
+++ b/git-am.sh
@@ -783,7 +783,7 @@ do
 		"$GIT_DIR"/hooks/pre-applypatch || stop_here $this
 	fi
 
-	tree=$(git write-tree) &&
+	tree=$(git write-tree --narrow-base=HEAD) &&
 	commit=$(
 		if test -n "$ignore_date"
 		then
-- 
1.7.1.rc1.69.g24c2f7

[PATCH 16/17] merge: try to do local merge if possible in narrow repo

[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 because we do not have enough trees
to peform a trivial merge outside narrow tree. A merge in such case
will need server support.

Some simple cases though can be handled local. One of such cases are
where the narrow base of head and ancestor are exactly the same (IOW
we don't change anything outside narrow tree) we can just use remote
as narrow base. This case happens when we work on narrow repo then do
a pull.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 Documentation/git-merge.txt |   16 +++++++++
 builtin/merge.c             |   60 ++++++++++++++++++++++++++++++---
 narrow-tree.c               |   78 +++++++++++++++++++++++++++++++++++++++++++
 narrow-tree.h               |    1 +
 4 files changed, 150 insertions(+), 5 deletions(-)

diff --git a/Documentation/git-merge.txt b/Documentation/git-merge.txt
index 84043cc..4285f18 100644
--- a/Documentation/git-merge.txt
+++ b/Documentation/git-merge.txt
@@ -239,6 +239,22 @@ You can work through the conflict with a number of tools:
    version.
 
 
+MERGE IN NARROW REPOSITORIES
+----------------------------
+
+Because narrow repositories do not have all tree objects, abitrary
+merge may not work in these repositories. A merge can only be
+performed local in such a repository if
+
+ * There are two commits given
+
+ * A single common commit is found
+
+ * The commit content outside narrow area must be the same as in the
+   other commit, or in the common commit
+
+Merges that do not meet these requirements cannot be done locally.
+
 EXAMPLES
 --------
 
diff --git a/builtin/merge.c b/builtin/merge.c
index 47e705b..c6dfb44 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)
@@ -56,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 },
@@ -781,7 +783,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;
@@ -810,7 +813,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);
@@ -886,6 +890,48 @@ static int evaluate_result(void)
 	return cnt;
 }
 
+static struct commit_list *find_narrow_base(struct commit *head, struct commit_list *remoteheads)
+{
+	struct commit_list *remote = remoteheads;
+	const char **narrow_prefix = get_narrow_prefix();
+
+	if (!narrow_prefix)
+		return NULL;
+
+	parse_commit(head);
+	while (remote) {
+		parse_commit(remote->item);
+		if (!same_narrow_base(head->tree->object.sha1,
+				      remote->item->tree->object.sha1,
+				      narrow_prefix))
+			break;
+		remote = remote->next;
+	}
+
+	if (!remote) {		/* all same narrow base */
+		hashcpy(narrow_base, head->tree->object.sha1);
+		return NULL;
+	}
+
+	/*
+	 * If it's three-way merge and head has the same narrow base
+	 * as in common, then we could just use remote as the base
+	 * because we haven't changed anything outside narrow tree.
+	 */
+	if (remoteheads && !remoteheads->next) {
+		struct commit_list *common;
+		common = get_merge_bases(head, remoteheads->item, 1);
+		if (common && !common->next &&
+		    same_narrow_base(head->object.sha1,
+				     common->item->object.sha1,
+				     narrow_prefix)) {
+			hashcpy(narrow_base, remoteheads->item->tree->object.sha1);
+			return common;
+		}
+	}
+	die("Different narrow base, couldn't do merge (yet)");
+}
+
 int cmd_merge(int argc, const char **argv, const char *prefix)
 {
 	unsigned char result_tree[20];
@@ -1050,9 +1096,13 @@ int cmd_merge(int argc, const char **argv, const char *prefix)
 			allow_trivial = 0;
 	}
 
-	if (!remoteheads->next)
-		common = get_merge_bases(lookup_commit(head),
-				remoteheads->item, 1);
+	common = find_narrow_base(lookup_commit(head), remoteheads);
+
+	if (!remoteheads->next) {
+		if (!common) /* might have been calculated in find_narrow_base */
+			common = get_merge_bases(lookup_commit(head),
+						 remoteheads->item, 1);
+	}
 	else {
 		struct commit_list *list = remoteheads;
 		commit_list_insert(lookup_commit(head), &list);
diff --git a/narrow-tree.c b/narrow-tree.c
index 110fac2..76581f2 100644
--- a/narrow-tree.c
+++ b/narrow-tree.c
@@ -205,3 +205,81 @@ int join_narrow_tree(unsigned char *result,
 	char path[PATH_MAX];
 	return join_narrow_tree_rec(result, basetree, newtree, prefix, path, 0);
 }
+
+static int same_narrow_base_rec(const unsigned char *t1,
+				const unsigned char *t2,
+				const char **prefix,
+				char *base, int baselen)
+{
+	struct tree_desc desc1, desc2;
+	struct name_entry entry1, entry2;
+	char *buf1, *buf2;
+	enum object_type type;
+	unsigned long size;
+
+	if (baselen)
+		base[baselen++] = '/';
+
+	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)) {
+			int len = strlen(entry1.path);
+			const char **p = prefix;
+			int found = 0;
+			while (*p) {
+				if (!strcmp(entry1.path, *p)) {
+					found = 2;
+					break;
+				}
+				if (!prefixcmp(*p, entry1.path)) {
+					found = 1;
+					break;
+				}
+				p++;
+			}
+
+			if (found == 2) /* narrow area */
+				continue;
+			else if (found == 1) {
+				memcpy(base+baselen, entry1.path, len+1);
+				if (same_narrow_base_rec(entry1.sha1, entry2.sha1,
+							 prefix, base, baselen+len))
+					continue;
+			}
+		}
+
+		free(buf1);
+		free(buf2);
+		return 0;
+	}
+	free(buf1);
+	free(buf2);
+	return !desc1.size && !desc2.size;
+}
+
+int same_narrow_base(const unsigned char *t1,
+		     const unsigned char *t2,
+		     const char **prefix)
+{
+	char path[PATH_MAX];
+	return same_narrow_base_rec(t1, t2, prefix, path, 0);
+}
diff --git a/narrow-tree.h b/narrow-tree.h
index e7d84c4..c574227 100644
--- a/narrow-tree.h
+++ b/narrow-tree.h
@@ -5,3 +5,4 @@ extern int join_narrow_tree(unsigned char *result,
 			    const unsigned char *base,
 			    const unsigned char *newtree,
 			    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 17/17] Add narrow clone demonstration test

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t9999-narrow.sh |   87 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 87 insertions(+), 0 deletions(-)
 create mode 100755 t/t9999-narrow.sh

diff --git a/t/t9999-narrow.sh b/t/t9999-narrow.sh
new file mode 100755
index 0000000..2974ddc
--- /dev/null
+++ b/t/t9999-narrow.sh
@@ -0,0 +1,87 @@
+#!/bin/sh
+
+test_description='narrow misc tests'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	git clone --mirror ../../.git src.git
+'
+
+test_expect_success clone '
+	git clone --depth=50 --narrow=Documentation --narrow=block-sha1 file://"`pwd`"/src.git dst &&
+	test -f dst/Documentation/git.txt &&
+	test -f dst/block-sha1/sha1.c &&
+	! test -f git.c
+'
+
+test_expect_success 'into dst' '
+	cd dst
+'
+
+#test_expect_failure 'fsck' 'git fsck'
+
+test_expect_success 'checkout -b ' '
+	git checkout -b mybranch
+'
+
+test_expect_success 'log' '
+	git log --stat HEAD~20.. >/dev/null
+'
+
+test_expect_success 'modify worktree' '
+	echo 1 >>Documentation/git.txt
+'
+
+test_expect_success 'diff' '
+	git diff
+'
+
+test_expect_success 'diff HEAD' '
+	git diff HEAD
+'
+
+test_expect_success 'diff --cached' '
+	git add Documentation/git.txt &&
+	git diff --cached
+'
+
+test_expect_success 'commit' '
+	git commit -a -m 1 &&
+	git tag branch0 &&
+	echo 2 >>block-sha1/sha1.c &&
+	git commit -a -m 2 &&
+	echo 3 >>Documentation/git.txt &&
+	echo 3 >>block-sha1/sha1.c &&
+	git commit -a -m 3 &&
+	git tag branch1
+'
+
+test_expect_success 'internal merge' '
+	git checkout branch0 &&
+	echo 4 >>block-sha1/sha1.h &&
+	git commit -a -m 4 && false
+	git tag branch2 &&
+	git merge branch1 &&
+	grep "^2$" block-sha1/sha1.c &&
+	git tag merge1.2
+'
+
+test_expect_success 'rebase' '
+	git checkout branch1 &&
+	git rebase --onto branch2 branch0
+'
+
+test_expect_success 'push' '
+	git push ../src.git +merge1.2:refs/heads/mybranch &&
+	git rev-parse merge1.2 >../expected &&
+	(
+		cd ../src.git &&
+		git rev-parse mybranch >result &&
+		test_cmp ../expected result &&
+		echo fscking... &&
+		git fsck --no-full
+	)
+'
+
+test_done
-- 
1.7.1.rc1.69.g24c2f7

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Sverre Rabbelier]

Heya,

2010/9/5 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> Tree generating from index, Elijah merges the base tree inside
> write_cache_as_tree() while it does it inside commit_tree(). Again the
> principle is pretty much the same. I'll see if I can resist from
> stealing some more :)

Why don't you two combine your series instead? :)

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Nguyen Thai Ngoc Duy]

2010/9/5 Sverre Rabbelier <srabbelier@gmail.com>:
> Heya,
>
> 2010/9/5 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> Tree generating from index, Elijah merges the base tree inside
>> write_cache_as_tree() while it does it inside commit_tree(). Again the
>> principle is pretty much the same. I'll see if I can resist from
>> stealing some more :)
>
> Why don't you two combine your series instead? :)

Hm.. the two series have different, conflicting goals. I think we'll
end up sharing a lot though.
-- 
Duy

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Elijah Newren]

On Sun, Sep 5, 2010 at 1:13 AM, Nguyen Thai Ngoc Duy <pclouds@gmail.com> wrote:
> 2010/9/5 Sverre Rabbelier <srabbelier@gmail.com>:
>> 2010/9/5 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>>> Tree generating from index, Elijah merges the base tree inside
>>> write_cache_as_tree() while it does it inside commit_tree(). Again the
>>> principle is pretty much the same. I'll see if I can resist from
>>> stealing some more :)
>>
>> Why don't you two combine your series instead? :)
>
> Hm.. the two series have different, conflicting goals. I think we'll
> end up sharing a lot though.

I think we'll probably eventually converge, and have been some
already.  For example, Nguyen dropped his tree-rewriting and
remote-merge; and I'm going to drop my passing of arguments to upload
pack on the command line, and my setup_revisions changes.  I'll
replace them with some of his patches, because his changes are a lot
better there.  Since he's planning to work on fsck next (it was down a
ways on my list), I should be able to just adopt that too (especially
if he does it by making it use rev-list).  Finally, we've also adopted
ideas in our discussions from each other.  Even if we don't converge
all the way, if we keep cherry-picking good stuff from each other and
giving each other feedback, we'll get close and then others on the git
list can chime in on what they'd prefer for any remaining differences
between us.

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Elijah Newren]

Hi,

2010/9/5 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> I'll describe differences between this series and Elijah's one [1].
> I think it's more interesting. Changes from v2 [2] will follow later.

So, I downloaded your patches and even made sure to sort them
appropriately to fix the order, but I'm getting conflicts trying to
apply them (on top of current pu).  What version did you base them on?

> In short I think the two series are converging. The outstanding
> difference is Elijah drops shallow clone in favor of more flexible
> history cutting while I only focus on tree cutting.
>
> Two other differences are tree traversal and tree generating. I admit
> that changing traverse_trees() the way Elijah does is more flexible
> and is probably the only way to support negative pathspec. And I think
> his sparse clone supports even cloning a single file. Mine does not
> support that. I'm going to steal some of his patches at some point.

Yes, I can clone a single file.

> Tree generating from index, Elijah merges the base tree inside
> write_cache_as_tree() while it does it inside commit_tree(). Again the
> principle is pretty much the same. I'll see if I can resist from
> stealing some more :)

You're too modest; your comparison simply omitted some of the areas
where your series shines, such as the get_pathspec fixes (my stuff was
broken and much less complete), merge support, and nicer
fetch/push/clone support.  You also had some other nice touches
(documentation updates, new rev-parse flag) that may not have been a
big deal, but they're still nice.  I'm going to be cherry-picking a
lot of that stuff, and replacing the relevant bits of my series.  Who
knows, maybe we're converging quicker than it looked at first glance?
:-)

> Things that won't work:
>
>  - Shell scripts that use "git write-tree"

Yeah, write-tree didn't work in mine either; I had to make it throw an
error.  But wouldn't your idea to make a tree object (referenced for
sha1sums outside the sparse/narrow paths) part of the index allow even
write-tree to work?

>  - only send commits that have changes in narrow area and graft it at
>   client side

After reviewing more of your changes, and replacing various patches of
mine with yours, this is fairly high on my priority list as well
(whereas fsck & prune are a bit lower).  Maybe we can discuss ideas on
tackling this when we start working on it.  I've got some rough
initial ideas (though I have no idea if they'll pan out); I'll see if
I can write some of them up in the next day or two.

Elijah

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Nguyen Thai Ngoc Duy]

2010/9/6 Elijah Newren <newren@gmail.com>:
> Hi,
>
> 2010/9/5 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> I'll describe differences between this series and Elijah's one [1].
>> I think it's more interesting. Changes from v2 [2] will follow later.
>
> So, I downloaded your patches and even made sure to sort them
> appropriately to fix the order, but I'm getting conflicts trying to
> apply them (on top of current pu).  What version did you base them on?

b5442ca (was master in Aug 24) with en/object-list-with-pathspec
applied on top. Sorry I don't want to change my base too often so it's
quite old.

>> Things that won't work:
>>
>>  - Shell scripts that use "git write-tree"
>
> Yeah, write-tree didn't work in mine either; I had to make it throw an
> error.  But wouldn't your idea to make a tree object (referenced for
> sha1sums outside the sparse/narrow paths) part of the index allow even
> write-tree to work?

Definitely.

>>  - only send commits that have changes in narrow area and graft it at
>>   client side
>
> After reviewing more of your changes, and replacing various patches of
> mine with yours, this is fairly high on my priority list as well
> (whereas fsck & prune are a bit lower).  Maybe we can discuss ideas on
> tackling this when we start working on it.  I've got some rough
> initial ideas (though I have no idea if they'll pan out); I'll see if
> I can write some of them up in the next day or two.

Well, looking forward to your fake commit implementation. I think it's
more or less the same as graft.
-- 
Duy

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Sverre Rabbelier]

Heya,

2010/9/6 Elijah Newren <newren@gmail.com>:
> So, I downloaded your patches and even made sure to sort them
> appropriately to fix the order, but I'm getting conflicts trying to
> apply them (on top of current pu).  What version did you base them on?

It's considered best practice to base your patches on master if
possible. You should only base them on next if you rely on a
particular series that has already landed there. You should never base
your patches on pu itself, on a topic in pu perhaps, but never on pu.

-- 
Cheers,

Sverre Rabbelier

Re: [PATCH 00/17] Narrow clone v3 (was subtree clone)

[Elijah Newren]

2010/9/6 Sverre Rabbelier <srabbelier@gmail.com>:
> Heya,
>
> 2010/9/6 Elijah Newren <newren@gmail.com>:
>> So, I downloaded your patches and even made sure to sort them
>> appropriately to fix the order, but I'm getting conflicts trying to
>> apply them (on top of current pu).  What version did you base them on?
>
> It's considered best practice to base your patches on master if
> possible. You should only base them on next if you rely on a
> particular series that has already landed there. You should never base
> your patches on pu itself, on a topic in pu perhaps, but never on pu.

Ah, thanks for the reminder.  I probably should have mentioned that I
tried master and next too and had similar conflicts (I believe from
some of AEvar's testing changes in master modifying the makefile in
nearby locations, among other things).  But in any event, I'm in good
shape now.

I might have been able to make progress too, if I weren't being
distracted from sparse clones by this rename+D/F conflict problem
(though I think I've got it licked now...)

Elijah