[PATCH 0/8] en/object-list-with-pathspec v4

[PATCH 0/8] en/object-list-with-pathspec v4

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

OK it's good enough now. I no longer use struct exclude_list.
Its name does not really match the semantics.

The last two patches implement tree exclusion and are not meant
for submission to en/object-list-with-pathspec. I wanted to see
if the new struct was extensible. And I need tree exclusion anyway
in my narrow clone.

Elijah Newren (2):
  Add testcases showing how pathspecs are ignored with rev-list --objects
  Make rev-list --objects work together with pathspecs

Nguyễn Thái Ngọc Duy (6):
  diff-no-index: use diff_tree_setup_paths()
  Introduce struct tree_pathspec_list
  tree_entry_interesting(): remove dependency on struct diff_options
  tree-walk: move tree_entry_interesting() from tree-diff.c
  setup_tree_pathspec(): interpret '^' as negative pathspec
  tree_entry_interesting(): support negative pathspec

 builtin/diff-files.c     |    2 +-
 builtin/diff.c           |    4 +-
 builtin/log.c            |    2 +-
 diff-lib.c               |    2 +-
 diff-no-index.c          |   13 ++--
 diff.h                   |    4 +-
 list-objects.c           |   23 ++++++
 revision.c               |   14 ++--
 revision.h               |    3 +-
 t/t6000-rev-list-misc.sh |   51 ++++++++++++
 t/t9999-test.sh          |   44 +++++++++++
 tree-diff.c              |  157 ++-----------------------------------
 tree-walk.c              |  191 ++++++++++++++++++++++++++++++++++++++++++++++
 tree-walk.h              |   16 ++++
 14 files changed, 356 insertions(+), 170 deletions(-)
 create mode 100755 t/t6000-rev-list-misc.sh
 create mode 100755 t/t9999-test.sh

[PATCH 1/8] diff-no-index: use diff_tree_setup_paths()

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

diff_options.{paths,nr_paths} will be removed later. Do not
modify them directly.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 diff-no-index.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/diff-no-index.c b/diff-no-index.c
index ce9e783..e48ab92 100644
--- a/diff-no-index.c
+++ b/diff-no-index.c
@@ -231,8 +231,9 @@ void diff_no_index(struct rev_info *revs,
 
 	if (prefix) {
 		int len = strlen(prefix);
+		const char *paths[3];
+		memset(paths, 0, sizeof(paths));
 
-		revs->diffopt.paths = xcalloc(2, sizeof(char *));
 		for (i = 0; i < 2; i++) {
 			const char *p = argv[argc - 2 + i];
 			/*
@@ -242,12 +243,12 @@ void diff_no_index(struct rev_info *revs,
 			p = (strcmp(p, "-")
 			     ? xstrdup(prefix_filename(prefix, len, p))
 			     : p);
-			revs->diffopt.paths[i] = p;
+			paths[i] = p;
 		}
+		diff_tree_setup_paths(paths, &revs->diffopt);
 	}
 	else
-		revs->diffopt.paths = argv + argc - 2;
-	revs->diffopt.nr_paths = 2;
+		diff_tree_setup_paths(argv + argc - 2, &revs->diffopt);
 	revs->diffopt.skip_stat_unmatch = 1;
 	if (!revs->diffopt.output_format)
 		revs->diffopt.output_format = DIFF_FORMAT_PATCH;
-- 
1.7.1.rc1.70.g13aff

[PATCH 2/8] Introduce struct tree_pathspec_list

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

This struct replaces paths, nr_paths and pathlens fields in struct
diff_options. Actually diff_options.paths is still kept, now as
tree_pathspec_list.paths because a lot of places depend on a
continuous list of pathspecs.

tree_entry_interesting() is going to be updated to use these instead.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/diff-files.c |    2 +-
 builtin/diff.c       |    4 ++--
 builtin/log.c        |    2 +-
 diff-lib.c           |    2 +-
 diff-no-index.c      |    4 ++--
 diff.h               |    4 +---
 revision.c           |    6 +-----
 tree-diff.c          |   46 +++++++++++-----------------------------------
 tree-walk.c          |   28 ++++++++++++++++++++++++++++
 tree-walk.h          |   11 +++++++++++
 10 files changed, 59 insertions(+), 50 deletions(-)

diff --git a/builtin/diff-files.c b/builtin/diff-files.c
index 951c7c8..e740b77 100644
--- a/builtin/diff-files.c
+++ b/builtin/diff-files.c
@@ -61,7 +61,7 @@ int cmd_diff_files(int argc, const char **argv, const char *prefix)
 	    (rev.diffopt.output_format & DIFF_FORMAT_PATCH))
 		rev.combine_merges = rev.dense_combined_merges = 1;
 
-	if (read_cache_preload(rev.diffopt.paths) < 0) {
+	if (read_cache_preload(rev.diffopt.pathspec.paths) < 0) {
 		perror("read_cache_preload");
 		return -1;
 	}
diff --git a/builtin/diff.c b/builtin/diff.c
index a43d326..4247377 100644
--- a/builtin/diff.c
+++ b/builtin/diff.c
@@ -135,7 +135,7 @@ static int builtin_diff_index(struct rev_info *revs,
 	    revs->max_count != -1 || revs->min_age != -1 ||
 	    revs->max_age != -1)
 		usage(builtin_diff_usage);
-	if (read_cache_preload(revs->diffopt.paths) < 0) {
+	if (read_cache_preload(revs->diffopt.pathspec.paths) < 0) {
 		perror("read_cache_preload");
 		return -1;
 	}
@@ -237,7 +237,7 @@ static int builtin_diff_files(struct rev_info *revs, int argc, const char **argv
 		revs->combine_merges = revs->dense_combined_merges = 1;
 
 	setup_work_tree();
-	if (read_cache_preload(revs->diffopt.paths) < 0) {
+	if (read_cache_preload(revs->diffopt.pathspec.paths) < 0) {
 		perror("read_cache_preload");
 		return -1;
 	}
diff --git a/builtin/log.c b/builtin/log.c
index 08b8722..d78744f 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -89,7 +89,7 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 		rev->always_show_header = 0;
 	if (DIFF_OPT_TST(&rev->diffopt, FOLLOW_RENAMES)) {
 		rev->always_show_header = 0;
-		if (rev->diffopt.nr_paths != 1)
+		if (rev->diffopt.pathspec.nr != 1)
 			usage("git logs can only follow renames on one pathname at a time");
 	}
 	for (i = 1; i < argc; i++) {
diff --git a/diff-lib.c b/diff-lib.c
index 392ce2b..0107e23 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -501,7 +501,7 @@ int do_diff_cache(const unsigned char *tree_sha1, struct diff_options *opt)
 	active_nr = dst - active_cache;
 
 	init_revisions(&revs, NULL);
-	revs.prune_data = opt->paths;
+	revs.prune_data = opt->pathspec.paths;
 	tree = parse_tree_indirect(tree_sha1);
 	if (!tree)
 		die("bad tree object %s", sha1_to_hex(tree_sha1));
diff --git a/diff-no-index.c b/diff-no-index.c
index e48ab92..832d692 100644
--- a/diff-no-index.c
+++ b/diff-no-index.c
@@ -260,8 +260,8 @@ void diff_no_index(struct rev_info *revs,
 	if (diff_setup_done(&revs->diffopt) < 0)
 		die("diff_setup_done failed");
 
-	if (queue_diff(&revs->diffopt, revs->diffopt.paths[0],
-		       revs->diffopt.paths[1]))
+	if (queue_diff(&revs->diffopt, revs->diffopt.pathspec.paths[0],
+		       revs->diffopt.pathspec.paths[1]))
 		exit(1);
 	diff_set_mnemonic_prefix(&revs->diffopt, "1/", "2/");
 	diffcore_std(&revs->diffopt);
diff --git a/diff.h b/diff.h
index bf2f44d..aaa2983 100644
--- a/diff.h
+++ b/diff.h
@@ -133,9 +133,7 @@ struct diff_options {
 	FILE *file;
 	int close_file;
 
-	int nr_paths;
-	const char **paths;
-	int *pathlens;
+	struct tree_pathspec_list pathspec;
 	change_fn_t change;
 	add_remove_fn_t add_remove;
 	diff_format_fn_t format_callback;
diff --git a/revision.c b/revision.c
index b1c1890..b2a5867 100644
--- a/revision.c
+++ b/revision.c
@@ -553,11 +553,7 @@ static void cherry_pick_list(struct commit_list *list, struct rev_info *revs)
 
 	left_first = left_count < right_count;
 	init_patch_ids(&ids);
-	if (revs->diffopt.nr_paths) {
-		ids.diffopts.nr_paths = revs->diffopt.nr_paths;
-		ids.diffopts.paths = revs->diffopt.paths;
-		ids.diffopts.pathlens = revs->diffopt.pathlens;
-	}
+	ids.diffopts.pathspec = revs->diffopt.pathspec;
 
 	/* Compute patch-ids for one side */
 	for (p = list; p; p = p->next) {
diff --git a/tree-diff.c b/tree-diff.c
index cd659c6..270dea0 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -100,16 +100,16 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
 	int pathlen;
 	int never_interesting = -1;
 
-	if (!opt->nr_paths)
+	if (!opt->pathspec.nr)
 		return 1;
 
 	sha1 = tree_entry_extract(desc, &path, &mode);
 
 	pathlen = tree_entry_len(path, sha1);
 
-	for (i = 0; i < opt->nr_paths; i++) {
-		const char *match = opt->paths[i];
-		int matchlen = opt->pathlens[i];
+	for (i = 0; i < opt->pathspec.nr; i++) {
+		const char *match = opt->pathspec.paths[i];
+		int matchlen = opt->pathspec.info[i].pathlen;
 		int m = -1; /* signals that we haven't called strncmp() */
 
 		if (baselen >= matchlen) {
@@ -289,7 +289,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru
 		if (DIFF_OPT_TST(opt, QUICK) &&
 		    DIFF_OPT_TST(opt, HAS_CHANGES))
 			break;
-		if (opt->nr_paths) {
+		if (opt->pathspec.nr) {
 			skip_uninteresting(t1, base, baselen, opt);
 			skip_uninteresting(t2, base, baselen, opt);
 		}
@@ -348,7 +348,7 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 	DIFF_OPT_SET(&diff_opts, RECURSIVE);
 	DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
-	diff_opts.single_follow = opt->paths[0];
+	diff_opts.single_follow = opt->pathspec.paths[0];
 	diff_opts.break_opt = opt->break_opt;
 	paths[0] = NULL;
 	diff_tree_setup_paths(paths, &diff_opts);
@@ -368,15 +368,15 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 		 * diff_queued_diff, we will also use that as the path in
 		 * the future!
 		 */
-		if ((p->status == 'R' || p->status == 'C') && !strcmp(p->two->path, opt->paths[0])) {
+		if ((p->status == 'R' || p->status == 'C') && !strcmp(p->two->path, opt->pathspec.paths[0])) {
 			/* Switch the file-pairs around */
 			q->queue[i] = choice;
 			choice = p;
 
 			/* Update the path we use from now on.. */
 			diff_tree_release_paths(opt);
-			opt->paths[0] = xstrdup(p->one->path);
-			diff_tree_setup_paths(opt->paths, opt);
+			opt->pathspec.paths[0] = xstrdup(p->one->path);
+			diff_tree_setup_paths(opt->pathspec.paths, opt);
 
 			/*
 			 * The caller expects us to return a set of vanilla
@@ -451,36 +451,12 @@ int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_
 	return retval;
 }
 
-static int count_paths(const char **paths)
-{
-	int i = 0;
-	while (*paths++)
-		i++;
-	return i;
-}
-
 void diff_tree_release_paths(struct diff_options *opt)
 {
-	free(opt->pathlens);
+	free(opt->pathspec.info);
 }
 
 void diff_tree_setup_paths(const char **p, struct diff_options *opt)
 {
-	opt->nr_paths = 0;
-	opt->pathlens = NULL;
-	opt->paths = NULL;
-
-	if (p) {
-		int i;
-
-		opt->paths = p;
-		opt->nr_paths = count_paths(p);
-		if (opt->nr_paths == 0) {
-			opt->pathlens = NULL;
-			return;
-		}
-		opt->pathlens = xmalloc(opt->nr_paths * sizeof(int));
-		for (i=0; i < opt->nr_paths; i++)
-			opt->pathlens[i] = strlen(p[i]);
-	}
+	setup_tree_pathspec(p, &opt->pathspec);
 }
diff --git a/tree-walk.c b/tree-walk.c
index a9bbf4e..30c2aa1 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -455,3 +455,31 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 	free(tree);
 	return retval;
 }
+
+static int count_paths(const char **paths)
+{
+	int i = 0;
+	while (*paths++)
+		i++;
+	return i;
+}
+
+int setup_tree_pathspec(const char **paths, struct tree_pathspec_list *ps)
+{
+	int i;
+
+	memset(ps, 0, sizeof(*ps));
+	ps->nr = count_paths(paths);
+	if (!ps->nr)
+		return 0;
+
+	ps->paths = paths;
+	ps->info = xmalloc(ps->nr * sizeof(struct tree_pathspec));
+	memset(ps->info, 0, ps->nr * sizeof(struct tree_pathspec));
+	for (i=0; i < ps->nr; i++) {
+		struct tree_pathspec *exc = ps->info+i;
+		exc->path = ps->paths[i];
+		exc->pathlen = strlen(exc->path);
+	}
+	return 0;
+}
diff --git a/tree-walk.h b/tree-walk.h
index 88ea7e9..2d09b7c 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -13,6 +13,15 @@ struct tree_desc {
 	unsigned int size;
 };
 
+struct tree_pathspec_list {
+	const char **paths;
+	int nr;
+	struct tree_pathspec {
+		const char *path;
+		int pathlen;
+	} *info;
+};
+
 static inline const unsigned char *tree_entry_extract(struct tree_desc *desc, const char **pathp, unsigned int *modep)
 {
 	*pathp = desc->entry.path;
@@ -57,4 +66,6 @@ static inline int traverse_path_len(const struct traverse_info *info, const stru
 	return info->pathlen + tree_entry_len(n->path, n->sha1);
 }
 
+extern int setup_tree_pathspec(const char **paths, struct tree_pathspec_list *ps);
+
 #endif
-- 
1.7.1.rc1.70.g13aff

[PATCH 3/8] tree_entry_interesting(): remove dependency on struct diff_options

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

This function can be potentially used in more places than just
tree-diff.c. "struct diff_options" does not make much sense outside
diff_tree_sha1().

Moreover people seem to be agree that diff machinery should learn
proper pathspecs too (i.e. globbing, negative pathspecs...), not just
treating pathspecs as tree prefix.

So tree_entry_interesting() now uses struct tree_pathspec_list, which
can be easily extended later on.

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

diff --git a/tree-diff.c b/tree-diff.c
index 270dea0..b0aa3a0 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -91,25 +91,20 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
  *  - zero for no
  *  - negative for "no, and no subsequent entries will be either"
  */
-static int tree_entry_interesting(struct tree_desc *desc, const char *base, int baselen, struct diff_options *opt)
+static int tree_entry_interesting(const struct name_entry *entry, const char *base, int baselen, const struct tree_pathspec_list *ps)
 {
-	const char *path;
-	const unsigned char *sha1;
-	unsigned mode;
 	int i;
 	int pathlen;
 	int never_interesting = -1;
 
-	if (!opt->pathspec.nr)
+	if (!ps->nr)
 		return 1;
 
-	sha1 = tree_entry_extract(desc, &path, &mode);
-
-	pathlen = tree_entry_len(path, sha1);
+	pathlen = tree_entry_len(entry->path, entry->sha1);
 
-	for (i = 0; i < opt->pathspec.nr; i++) {
-		const char *match = opt->pathspec.paths[i];
-		int matchlen = opt->pathspec.info[i].pathlen;
+	for (i = 0; i < ps->nr; i++) {
+		const char *match = ps->info[i].path;
+		int matchlen = ps->info[i].pathlen;
 		int m = -1; /* signals that we haven't called strncmp() */
 
 		if (baselen >= matchlen) {
@@ -147,7 +142,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
 			 * Does match sort strictly earlier than path
 			 * with their common parts?
 			 */
-			m = strncmp(match, path,
+			m = strncmp(match, entry->path,
 				    (matchlen < pathlen) ? matchlen : pathlen);
 			if (m < 0)
 				continue;
@@ -174,7 +169,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
 		if (matchlen > pathlen) {
 			if (match[pathlen] != '/')
 				continue;
-			if (!S_ISDIR(mode))
+			if (!S_ISDIR(entry->mode))
 				continue;
 		}
 
@@ -183,7 +178,7 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
 			 * we cheated and did not do strncmp(), so we do
 			 * that here.
 			 */
-			m = strncmp(match, path, pathlen);
+			m = strncmp(match, entry->path, pathlen);
 
 		/*
 		 * If common part matched earlier then it is a hit,
@@ -206,8 +201,7 @@ static void show_tree(struct diff_options *opt, const char *prefix, struct tree_
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(desc, base, baselen,
-						      opt);
+			show = tree_entry_interesting(&desc->entry, base, baselen, &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
 		}
@@ -266,7 +260,7 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int basele
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(t, base, baselen, opt);
+			show = tree_entry_interesting(&t->entry, base, baselen, &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
 		}
-- 
1.7.1.rc1.70.g13aff

[PATCH 4/8] tree-walk: move tree_entry_interesting() from tree-diff.c

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

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

diff --git a/tree-diff.c b/tree-diff.c
index b0aa3a0..4b9d551 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -82,115 +82,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	return 0;
 }
 
-/*
- * Is a tree entry interesting given the pathspec we have?
- *
- * Return:
- *  - 2 for "yes, and all subsequent entries will be"
- *  - 1 for yes
- *  - zero for no
- *  - negative for "no, and no subsequent entries will be either"
- */
-static int tree_entry_interesting(const struct name_entry *entry, const char *base, int baselen, const struct tree_pathspec_list *ps)
-{
-	int i;
-	int pathlen;
-	int never_interesting = -1;
-
-	if (!ps->nr)
-		return 1;
-
-	pathlen = tree_entry_len(entry->path, entry->sha1);
-
-	for (i = 0; i < ps->nr; i++) {
-		const char *match = ps->info[i].path;
-		int matchlen = ps->info[i].pathlen;
-		int m = -1; /* signals that we haven't called strncmp() */
-
-		if (baselen >= matchlen) {
-			/* If it doesn't match, move along... */
-			if (strncmp(base, match, matchlen))
-				continue;
-
-			/*
-			 * If the base is a subdirectory of a path which
-			 * was specified, all of them are interesting.
-			 */
-			if (!matchlen ||
-			    base[matchlen] == '/' ||
-			    match[matchlen - 1] == '/')
-				return 2;
-
-			/* Just a random prefix match */
-			continue;
-		}
-
-		/* Does the base match? */
-		if (strncmp(base, match, baselen))
-			continue;
-
-		match += baselen;
-		matchlen -= baselen;
-
-		if (never_interesting) {
-			/*
-			 * We have not seen any match that sorts later
-			 * than the current path.
-			 */
-
-			/*
-			 * Does match sort strictly earlier than path
-			 * with their common parts?
-			 */
-			m = strncmp(match, entry->path,
-				    (matchlen < pathlen) ? matchlen : pathlen);
-			if (m < 0)
-				continue;
-
-			/*
-			 * If we come here even once, that means there is at
-			 * least one pathspec that would sort equal to or
-			 * later than the path we are currently looking at.
-			 * In other words, if we have never reached this point
-			 * after iterating all pathspecs, it means all
-			 * pathspecs are either outside of base, or inside the
-			 * base but sorts strictly earlier than the current
-			 * one.  In either case, they will never match the
-			 * subsequent entries.  In such a case, we initialized
-			 * the variable to -1 and that is what will be
-			 * returned, allowing the caller to terminate early.
-			 */
-			never_interesting = 0;
-		}
-
-		if (pathlen > matchlen)
-			continue;
-
-		if (matchlen > pathlen) {
-			if (match[pathlen] != '/')
-				continue;
-			if (!S_ISDIR(entry->mode))
-				continue;
-		}
-
-		if (m == -1)
-			/*
-			 * we cheated and did not do strncmp(), so we do
-			 * that here.
-			 */
-			m = strncmp(match, entry->path, pathlen);
-
-		/*
-		 * If common part matched earlier then it is a hit,
-		 * because we rejected the case where path is not a
-		 * leading directory and is shorter than match.
-		 */
-		if (!m)
-			return 1;
-	}
-	return never_interesting; /* No matches */
-}
-
 /* A whole sub-tree went away or appeared */
 static void show_tree(struct diff_options *opt, const char *prefix, struct tree_desc *desc, const char *base, int baselen)
 {
diff --git a/tree-walk.c b/tree-walk.c
index 30c2aa1..e7041d7 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -483,3 +483,112 @@ int setup_tree_pathspec(const char **paths, struct tree_pathspec_list *ps)
 	}
 	return 0;
 }
+
+/*
+ * Is a tree entry interesting given the pathspec we have?
+ *
+ * Return:
+ *  - 2 for "yes, and all subsequent entries will be"
+ *  - 1 for yes
+ *  - zero for no
+ *  - negative for "no, and no subsequent entries will be either"
+ */
+int tree_entry_interesting(const struct name_entry *entry, const char *base, int baselen, const struct tree_pathspec_list *ps)
+{
+	int i;
+	int pathlen;
+	int never_interesting = -1;
+
+	if (!ps->nr)
+		return 1;
+
+	pathlen = tree_entry_len(entry->path, entry->sha1);
+
+	for (i = 0; i < ps->nr; i++) {
+		const char *match = ps->info[i].path;
+		int matchlen = ps->info[i].pathlen;
+		int m = -1; /* signals that we haven't called strncmp() */
+
+		if (baselen >= matchlen) {
+			/* If it doesn't match, move along... */
+			if (strncmp(base, match, matchlen))
+				continue;
+
+			/*
+			 * If the base is a subdirectory of a path which
+			 * was specified, all of them are interesting.
+			 */
+			if (!matchlen ||
+			    base[matchlen] == '/' ||
+			    match[matchlen - 1] == '/')
+				return 2;
+
+			/* Just a random prefix match */
+			continue;
+		}
+
+		/* Does the base match? */
+		if (strncmp(base, match, baselen))
+			continue;
+
+		match += baselen;
+		matchlen -= baselen;
+
+		if (never_interesting) {
+			/*
+			 * We have not seen any match that sorts later
+			 * than the current path.
+			 */
+
+			/*
+			 * Does match sort strictly earlier than path
+			 * with their common parts?
+			 */
+			m = strncmp(match, entry->path,
+				    (matchlen < pathlen) ? matchlen : pathlen);
+			if (m < 0)
+				continue;
+
+			/*
+			 * If we come here even once, that means there is at
+			 * least one pathspec that would sort equal to or
+			 * later than the path we are currently looking at.
+			 * In other words, if we have never reached this point
+			 * after iterating all pathspecs, it means all
+			 * pathspecs are either outside of base, or inside the
+			 * base but sorts strictly earlier than the current
+			 * one.  In either case, they will never match the
+			 * subsequent entries.  In such a case, we initialized
+			 * the variable to -1 and that is what will be
+			 * returned, allowing the caller to terminate early.
+			 */
+			never_interesting = 0;
+		}
+
+		if (pathlen > matchlen)
+			continue;
+
+		if (matchlen > pathlen) {
+			if (match[pathlen] != '/')
+				continue;
+			if (!S_ISDIR(entry->mode))
+				continue;
+		}
+
+		if (m == -1)
+			/*
+			 * we cheated and did not do strncmp(), so we do
+			 * that here.
+			 */
+			m = strncmp(match, entry->path, pathlen);
+
+		/*
+		 * If common part matched earlier then it is a hit,
+		 * because we rejected the case where path is not a
+		 * leading directory and is shorter than match.
+		 */
+		if (!m)
+			return 1;
+	}
+	return never_interesting; /* No matches */
+}
diff --git a/tree-walk.h b/tree-walk.h
index 2d09b7c..bb55656 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -67,5 +67,7 @@ static inline int traverse_path_len(const struct traverse_info *info, const stru
 }
 
 extern int setup_tree_pathspec(const char **paths, struct tree_pathspec_list *ps);
+extern int tree_entry_interesting(const struct name_entry *entry, const char *base, int baselen,
+				  const struct tree_pathspec_list *ps);
 
 #endif
-- 
1.7.1.rc1.70.g13aff

[PATCH 5/8] Add testcases showing how pathspecs are ignored with rev-list --objects

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

From: Elijah Newren <newren@gmail.com>

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t6000-rev-list-misc.sh |   51 ++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 51 insertions(+), 0 deletions(-)
 create mode 100755 t/t6000-rev-list-misc.sh

diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
new file mode 100755
index 0000000..b3c1dd8
--- /dev/null
+++ b/t/t6000-rev-list-misc.sh
@@ -0,0 +1,51 @@
+#!/bin/sh
+
+test_description='miscellaneous rev-list tests'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	echo content1 >wanted_file &&
+	echo content2 >unwanted_file &&
+	git add wanted_file unwanted_file &&
+	git commit -m one
+'
+
+test_expect_failure 'rev-list --objects heeds pathspecs' '
+	git rev-list --objects HEAD -- wanted_file >output &&
+	grep wanted_file output &&
+	! grep unwanted_file output
+'
+
+test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '
+	mkdir foo &&
+	>foo/file &&
+	git add foo/file &&
+	git commit -m two &&
+
+	git rev-list --objects HEAD -- foo >output &&
+	grep foo/file output &&
+
+	git rev-list --objects HEAD -- foo/file >output &&
+	grep foo/file output &&
+	! grep unwanted_file output
+'
+
+test_expect_failure 'rev-list --objects with pathspecs and copied files' '
+	git checkout --orphan junio-testcase &&
+	git rm -rf . &&
+
+	mkdir two &&
+	echo frotz >one &&
+	cp one two/three &&
+	git add one two/three &&
+	test_tick &&
+	git commit -m that &&
+
+	ONE=$(git rev-parse HEAD:one)
+	git rev-list --objects HEAD two >output &&
+	grep "$ONE two/three" output &&
+	! grep one output
+'
+
+test_done
-- 
1.7.1.rc1.70.g13aff

[PATCH 6/8] Make rev-list --objects work together with pathspecs

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

From: Elijah Newren <newren@gmail.com>

When traversing commits, the selection of commits would heed the list of
pathspecs passed, but subsequent walking of the trees of those commits
would not.  This resulted in 'rev-list --objects HEAD -- <paths>'
displaying objects at unwanted paths.

Have process_tree() call tree_entry_interesting() to determine which paths
are interesting and should be walked.

Naturally, this change can provide a large speedup when paths are specified
together with --objects, since many tree entries are now correctly ignored.
Interestingly, though, this change also gives me a small (~1%) but
repeatable speedup even when no paths are specified with --objects.

Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 list-objects.c           |   23 +++++++++++++++++++++++
 revision.c               |    8 ++++++--
 revision.h               |    3 ++-
 t/t6000-rev-list-misc.sh |    6 +++---
 4 files changed, 34 insertions(+), 6 deletions(-)

diff --git a/list-objects.c b/list-objects.c
index 8953548..be4cf9f 100644
--- a/list-objects.c
+++ b/list-objects.c
@@ -67,6 +67,9 @@ static void process_tree(struct rev_info *revs,
 	struct tree_desc desc;
 	struct name_entry entry;
 	struct name_path me;
+	int all_interesting = (revs->diffopt.pathspec.nr == 0);
+	char *full_prefix = NULL;
+	int full_prefix_len = 0;
 
 	if (!revs->tree_objects)
 		return;
@@ -82,9 +85,28 @@ static void process_tree(struct rev_info *revs,
 	me.elem = name;
 	me.elem_len = strlen(name);
 
+	if (!all_interesting) {
+		full_prefix = path_name_impl(path, name, 1);
+		full_prefix_len = strlen(full_prefix);
+	}
+
 	init_tree_desc(&desc, tree->buffer, tree->size);
 
 	while (tree_entry(&desc, &entry)) {
+		if (!all_interesting) {
+			int showit = tree_entry_interesting(&entry,
+							    full_prefix,
+							    full_prefix_len,
+							    &revs->diffopt.pathspec);
+
+			if (showit < 0)
+				break;
+			else if (!showit)
+				continue;
+			else if (showit == 2)
+				all_interesting = 1;
+		}
+
 		if (S_ISDIR(entry.mode))
 			process_tree(revs,
 				     lookup_tree(entry.sha1),
@@ -97,6 +119,7 @@ static void process_tree(struct rev_info *revs,
 				     lookup_blob(entry.sha1),
 				     show, &me, entry.path);
 	}
+	free(full_prefix);
 	free(tree->buffer);
 	tree->buffer = NULL;
 }
diff --git a/revision.c b/revision.c
index b2a5867..4d7dc4b 100644
--- a/revision.c
+++ b/revision.c
@@ -16,7 +16,7 @@
 
 volatile show_early_output_fn_t show_early_output;
 
-char *path_name(const struct name_path *path, const char *name)
+char *path_name_impl(const struct name_path *path, const char *name, int isdir)
 {
 	const struct name_path *p;
 	char *n, *m;
@@ -27,7 +27,7 @@ char *path_name(const struct name_path *path, const char *name)
 		if (p->elem_len)
 			len += p->elem_len + 1;
 	}
-	n = xmalloc(len);
+	n = xmalloc(len + !!isdir);
 	m = n + len - (nlen + 1);
 	strcpy(m, name);
 	for (p = path; p; p = p->up) {
@@ -37,6 +37,10 @@ char *path_name(const struct name_path *path, const char *name)
 			m[p->elem_len] = '/';
 		}
 	}
+	if (isdir && len > 1) {
+		n[len-1] = '/';
+		n[len] = '\0';
+	}
 	return n;
 }
 
diff --git a/revision.h b/revision.h
index 05659c6..92f4feb 100644
--- a/revision.h
+++ b/revision.h
@@ -173,7 +173,8 @@ struct name_path {
 	const char *elem;
 };
 
-char *path_name(const struct name_path *path, const char *name);
+char *path_name_impl(const struct name_path *path, const char *name, int isdir);
+#define path_name(path, name) path_name_impl(path, name, 0)
 
 extern void add_object(struct object *obj,
 		       struct object_array *p,
diff --git a/t/t6000-rev-list-misc.sh b/t/t6000-rev-list-misc.sh
index b3c1dd8..b10685a 100755
--- a/t/t6000-rev-list-misc.sh
+++ b/t/t6000-rev-list-misc.sh
@@ -11,13 +11,13 @@ test_expect_success setup '
 	git commit -m one
 '
 
-test_expect_failure 'rev-list --objects heeds pathspecs' '
+test_expect_success 'rev-list --objects heeds pathspecs' '
 	git rev-list --objects HEAD -- wanted_file >output &&
 	grep wanted_file output &&
 	! grep unwanted_file output
 '
 
-test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '
+test_expect_success 'rev-list --objects with pathspecs and deeper paths' '
 	mkdir foo &&
 	>foo/file &&
 	git add foo/file &&
@@ -31,7 +31,7 @@ test_expect_failure 'rev-list --objects with pathspecs and deeper paths' '
 	! grep unwanted_file output
 '
 
-test_expect_failure 'rev-list --objects with pathspecs and copied files' '
+test_expect_success 'rev-list --objects with pathspecs and copied files' '
 	git checkout --orphan junio-testcase &&
 	git rm -rf . &&
 
-- 
1.7.1.rc1.70.g13aff

[PATCH 7/8] setup_tree_pathspec(): interpret '^' as negative pathspec

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

This patch does preparation work for tree exclusion in
tree_entry_interesting(). '^' has similar meaning to '!' in
gitexcludes. '!' is not used because bash does not like arguments with
a leading '!'.

Eventually, "git diff -- foo ^foo/bar" should show differences in foo,
except foo/bar. If "git diff -- ^foo" is given, then it implies
everything except foo, which could surprise users that
"bar" in "git diff -- bar ^foo" has no effect at all.

NOTE: pathspec in diff machinery is also used by ce_path_match() and
read_index_preload(), which currently do not understand '^' at all.

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

diff --git a/tree-walk.c b/tree-walk.c
index e7041d7..a2f4a00 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -479,7 +479,35 @@ int setup_tree_pathspec(const char **paths, struct tree_pathspec_list *ps)
 	for (i=0; i < ps->nr; i++) {
 		struct tree_pathspec *exc = ps->info+i;
 		exc->path = ps->paths[i];
+		if (*exc->path == '^') {
+			exc->path++;
+			exc->to_exclude = 1;
+		}
 		exc->pathlen = strlen(exc->path);
+		if (exc->to_exclude) {
+			int j, found = 0;
+
+			for (j = i-1; j >= 0; j--) {
+				int len = strlen(ps->info[j].path);
+				if (len < exc->pathlen &&
+				    !strncmp(ps->info[j].path, exc->path, len) &&
+				    exc->path[len] == '/') {
+					ps->info[j].has_sub_pathspec = 1;
+					found = 1;
+				}
+			}
+
+			/*
+			 * If a negative pathspec has nothing to
+			 * negate from, include everything so it can
+			 * negate from that.  This way is not
+			 * perfect. You may be surprised to find out
+			 * "^Documentation t" does not take "t" into
+			 * account at all
+			 */
+			if (!found)
+				ps->include_by_default = 1;
+		}
 	}
 	return 0;
 }
diff --git a/tree-walk.h b/tree-walk.h
index bb55656..6be1e6c 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -16,9 +16,12 @@ struct tree_desc {
 struct tree_pathspec_list {
 	const char **paths;
 	int nr;
+	int include_by_default:1;
 	struct tree_pathspec {
 		const char *path;
 		int pathlen;
+		int to_exclude:1;
+		int has_sub_pathspec:1;
 	} *info;
 };
 
-- 
1.7.1.rc1.70.g13aff

[PATCH 8/8] tree_entry_interesting(): support negative pathspec

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t9999-test.sh |   44 ++++++++++++++++++++++++++++++++++++++++++++
 tree-walk.c     |   36 +++++++++++++++++++++++++++++++-----
 2 files changed, 75 insertions(+), 5 deletions(-)
 create mode 100755 t/t9999-test.sh

diff --git a/t/t9999-test.sh b/t/t9999-test.sh
new file mode 100755
index 0000000..535386e
--- /dev/null
+++ b/t/t9999-test.sh
@@ -0,0 +1,44 @@
+#!/bin/sh
+test_description=f
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	mkdir one one/two &&
+	touch file one/file one/two/file one/zoo &&
+	git add . &&
+	git commit -m 1 &&
+	for i in file one/file one/two/file one/zoo; do echo 1 >>$i;done &&
+	git add . && git commit -m 2
+'
+
+test_expect_success 'diff' '
+	cat >expected <<-\EOF &&
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/file
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/two/file
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/zoo
+EOF
+	git diff-tree -r HEAD^ HEAD -- one >result &&
+	test_cmp expected result
+'
+
+test_expect_success 'diff one ^one/two' '
+	cat >expected <<-\EOF &&
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/file
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/zoo
+EOF
+	git diff-tree -r HEAD^ HEAD -- one ^one/two >result &&
+	test_cmp expected result
+'
+
+test_expect_success 'diff ^one/two' '
+	cat >expected <<-\EOF &&
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	file
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/file
+:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/zoo
+EOF
+	git diff-tree -r HEAD^ HEAD -- ^one/two >result &&
+	test_cmp expected result
+'
+
+test_done
diff --git a/tree-walk.c b/tree-walk.c
index a2f4a00..fd19681 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -532,7 +532,7 @@ int tree_entry_interesting(const struct name_entry *entry, const char *base, int
 
 	pathlen = tree_entry_len(entry->path, entry->sha1);
 
-	for (i = 0; i < ps->nr; i++) {
+	for (i = ps->nr-1; i >= 0; i--) {
 		const char *match = ps->info[i].path;
 		int matchlen = ps->info[i].pathlen;
 		int m = -1; /* signals that we haven't called strncmp() */
@@ -548,8 +548,18 @@ int tree_entry_interesting(const struct name_entry *entry, const char *base, int
 			 */
 			if (!matchlen ||
 			    base[matchlen] == '/' ||
-			    match[matchlen - 1] == '/')
-				return 2;
+			    match[matchlen - 1] == '/') {
+				if (!ps->info[i].has_sub_pathspec &&
+				    ps->info[i].to_exclude)
+					return -1;
+				/*
+				 * If has_sub_pathspec is 1, there is
+				 * another sub pathspec that will
+				 * negate the result. Don't return "2"
+				 * in that case.
+				 */
+				return ps->info[i].has_sub_pathspec ? 1 : 2;
+			}
 
 			/* Just a random prefix match */
 			continue;
@@ -615,8 +625,24 @@ int tree_entry_interesting(const struct name_entry *entry, const char *base, int
 		 * because we rejected the case where path is not a
 		 * leading directory and is shorter than match.
 		 */
-		if (!m)
+		if (!m) {
+			/*
+			 * If this is negative pathspec, we exclude
+			 * the path only if it's a perfect
+			 * match. Otherwise assume it's in, because
+			 * there could be a positive subpathspec,
+			 * which includes some trees again.
+			 */
+			if (ps->info[i].to_exclude)
+				return matchlen == pathlen ? 0 : 1;
 			return 1;
+		}
 	}
-	return never_interesting; /* No matches */
+
+	/*
+	 * if include_by_default is 1, all items should be included by
+	 * default, because some of them will be excluded later on by
+	 * negative pathspecs.
+	 */
+	return ps->include_by_default ? 1 : never_interesting; /* No matches */
 }
-- 
1.7.1.rc1.70.g13aff

Re: [PATCH 0/8] en/object-list-with-pathspec v4

[Elijah Newren]

Hi,

2010/9/8 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> OK it's good enough now. I no longer use struct exclude_list.
> Its name does not really match the semantics.
>
> The last two patches implement tree exclusion and are not meant
> for submission to en/object-list-with-pathspec. I wanted to see
> if the new struct was extensible. And I need tree exclusion anyway
> in my narrow clone.

Perhaps the last two patches should be split off and submitted
separately?  I really like your work here to add negated pathspecs;
they'll be really helpful for me.  However, as you say, they are
really moving into a different topic.

I've reviewed and tested patches 1-4 of this series, and they look
good to me.  (Am I supposed to add a Reviewed-by and Tested-by or an
Acked-by for these?  Still not sure what the rules are there).
Patches 5-6 are already part of pu (modulo the return of tree_entry(),
which is nice) and already have my signoff, so I don't need to comment
on those further.

I've got some comments for patches 7 & 8, which I think may need a
little more work; I'll add them to the individual emails.


Elijah

Re: [PATCH 7/8] setup_tree_pathspec(): interpret '^' as negative pathspec

[Elijah Newren]

2010/9/8 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> This patch does preparation work for tree exclusion in
> tree_entry_interesting(). '^' has similar meaning to '!' in
> gitexcludes. '!' is not used because bash does not like arguments with
> a leading '!'.
>
> Eventually, "git diff -- foo ^foo/bar" should show differences in foo,
> except foo/bar. If "git diff -- ^foo" is given, then it implies
> everything except foo, which could surprise users that
> "bar" in "git diff -- bar ^foo" has no effect at all.

I really like the work here.  There are just two things that I think
are missing:
  * It doesn't handle files with leading carats in their name
  * It handles some nested include/exclude cases (e.g. dir
^dir/subdir) but not more complicated ones.

You could add these three testcases (on top of your 8/8 patch) to see
what I mean:


test_expect_failure 'diff ^one one/two' '
	printf "file\none/two/file\n" >expected &&
	git diff --name-only HEAD^ HEAD -- ^one one/two >result &&
	test_cmp expected result
'

test_expect_failure 'diff ^funny-filename' '
	touch ^funny-filename &&
	git add ^funny-filename &&
	git commit -m "Add a filename with a leading carat" &&

	git ls-files >expected &&
	git diff --name-only HEAD^^ HEAD -- ^funny-filename >result &&
	test_cmp expected result &&

	echo ^funny-filename >expected &&
	git diff --name-only HEAD^^ HEAD -- ^^funny-filename >result &&
	test_cmp expected result &&

	git ls-files | grep -v funny-filename >expected &&
	git diff --name-only HEAD^^ HEAD -- ^^^funny-filename >result &&
	test_cmp expected result
'

test_expect_failure 'deeper nested exclude/include' '
	touch one/two/zoo &&
	for i in one/file one/zoo one/two/file; do echo 2 >>$i; done &&
	git add one &&
	git commit -m 4 &&

	printf "one/file\none/two/file\none/zoo\n" > expected &&
	git diff --name-only HEAD^ HEAD -- one ^one/two one/two/file >result &&
	test_cmp expected result &&

	printf "one/two/zoo\n" > expected &&
	git diff --name-only HEAD^ HEAD -- ^one one/two ^one/two/file >result &&
	test_cmp expected result
'

Note: In the second test, I used:
 * "^funny" to search for all files EXCEPT "funny"
 * "^^funny" to search for a file named "^funny"
 * "^^^funny" to search for all files EXCEPT "^funny"
I'm not sure if that's really the syntax we want to adopt, but it
should be easy to change if we decide on some other syntax.

Re: [PATCH 8/8] tree_entry_interesting(): support negative pathspec

[Elijah Newren]

Hi,

2010/9/8 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> +
> +test_expect_success 'diff' '
> +       cat >expected <<-\EOF &&
> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M     one/file
> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M     one/two/file
> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M     one/zoo
> +EOF
> +       git diff-tree -r HEAD^ HEAD -- one >result &&
> +       test_cmp expected result
> +'

Having the full mode & sha1sum seems to make the test harder to read
than necessary.  Perhaps you could use printf or git ls-files together
with --name-only to simplify and shorten these a bit?  Example
alternative versions for three of your testcases:

test_expect_success 'diff' '
	git ls-files one >expected &&
	git diff --name-only HEAD^ HEAD -- one >result &&
	test_cmp expected result
'

test_expect_success 'diff one ^one/two' '
	git ls-files one | grep -v one/two >expected &&
	git diff --name-only HEAD^ HEAD -- one ^one/two >result &&
	test_cmp expected result
'

test_expect_success 'diff ^one/two' '
	printf "file\none/file\none/zoo\n" >expected &&
	git diff --name-only HEAD^ HEAD -- ^one/two >result &&
	test_cmp expected result
'

Thoughts?

Re: [PATCH 7/8] setup_tree_pathspec(): interpret '^' as negative pathspec

[Nguyen Thai Ngoc Duy]

2010/9/12 Elijah Newren <newren@gmail.com>:
> 2010/9/8 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> This patch does preparation work for tree exclusion in
>> tree_entry_interesting(). '^' has similar meaning to '!' in
>> gitexcludes. '!' is not used because bash does not like arguments with
>> a leading '!'.
>>
>> Eventually, "git diff -- foo ^foo/bar" should show differences in foo,
>> except foo/bar. If "git diff -- ^foo" is given, then it implies
>> everything except foo, which could surprise users that
>> "bar" in "git diff -- bar ^foo" has no effect at all.
>
> I really like the work here.  There are just two things that I think
> are missing:
>  * It doesn't handle files with leading carats in their name
>  * It handles some nested include/exclude cases (e.g. dir
> ^dir/subdir) but not more complicated ones.

Yeah. I originally needed it to compare trees outside narrow area
(i.e. negating all pathspecs). But I would need a more robust
implementation soon when I implement tree widening.

> Note: In the second test, I used:
>  * "^funny" to search for all files EXCEPT "funny"
>  * "^^funny" to search for a file named "^funny"
>  * "^^^funny" to search for all files EXCEPT "^funny"
> I'm not sure if that's really the syntax we want to adopt, but it
> should be easy to change if we decide on some other syntax.

Another way is always treat the leading ^ as negative pathspec. If you
have file "^foo", specify it with ./^foo. There's still problem with
top level entries this way.
-- 
Duy

Re: [PATCH 3/8] tree_entry_interesting(): remove dependency on struct diff_options

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> This function can be potentially used in more places than just
> tree-diff.c. "struct diff_options" does not make much sense outside
> diff_tree_sha1().
>
> Moreover people seem to be agree that diff machinery should learn
> proper pathspecs too (i.e. globbing, negative pathspecs...), not just
> treating pathspecs as tree prefix.

There is nothing improper about the prefix match.  Perhaps "richer"?
I am not so sure about the need/desirability of negative match, but we
will see. 

About naming.  Where else other than "tree" (in the "hierarchical
namespace" sense) context do you see pathspec?  Does the struct really
need to be called TREE_pathspec_list?

Re: [PATCH 5/8] Add testcases showing how pathspecs are ignored with rev-list --objects

[Junio C Hamano]

As I hinted in the earlier round, no need to "demonstrate" the breakage
and then flip them with s/failure/success/ in this series, as --objects
were not designed to be used with pathspecs to begin with.  Just add the
pathspec limiting feature and protect it with a new test.

Re: [PATCH 7/8] setup_tree_pathspec(): interpret '^' as negative pathspec

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> This patch does preparation work for tree exclusion in
> tree_entry_interesting(). '^' has similar meaning to '!' in
> gitexcludes. '!' is not used because bash does not like arguments with
> a leading '!'.

Do not even mention gitexcludes as you have to make awkward excuse like
this.

Instead say something like

    '^' works exactly like prefix '^' for revs (e.g. "log ^maint master")
    to mark what is prefixed is excluded.

Re: [PATCH 8/8] tree_entry_interesting(): support negative pathspec

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  t/t9999-test.sh |   44 ++++++++++++++++++++++++++++++++++++++++++++

If this is about the basic tree traversal logic, that belongs somewhere in
2xxx series.  You seem to be testing only diff-tree and nothing else, so I
suspect that you shouldn't even consume a new test number but just adding
a new test or two to 4013 should suffice.

> +test_expect_success 'diff' '
> +	cat >expected <<-\EOF &&

What's the point of the dash in "<<-\EOF" if you are not going to indent
the here doc?

> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/file
> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/two/file
> +:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 d00491fd7e5bb6fa28c517a0bb32b8b506539d4d M	one/zoo
> +EOF

Outside t0xxx series please avoid making the test depend on absolute
object names like this.  Since you are using only two blobs, you could
run two hash-objects to learn the hash for "" and "1\n" and say

	cat >expected <<-EOF &&
	:100644 100644 $none $one M	one/file
        ...
	EOF

Better yet, think if you even need the raw output here?  Perhaps using
output formats like --name-only or --name-status is more appropriate and
make the test more readable?

> diff --git a/tree-walk.c b/tree-walk.c
> index a2f4a00..fd19681 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -532,7 +532,7 @@ int tree_entry_interesting(const struct name_entry *entry, const char *base, int
>  
>  	pathlen = tree_entry_len(entry->path, entry->sha1);
>  
> -	for (i = 0; i < ps->nr; i++) {
> +	for (i = ps->nr-1; i >= 0; i--) {

No explanation in the commit log message why.  Besides, spell binary "-"
operator with a SP each on both ends, please.

Also the code seems to use a new term subpathspec without defining nor
explaining.  Not good.

Re: [PATCH 3/8] tree_entry_interesting(): remove dependency on struct diff_options

[Nguyen Thai Ngoc Duy]

2010/9/15 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> This function can be potentially used in more places than just
>> tree-diff.c. "struct diff_options" does not make much sense outside
>> diff_tree_sha1().
>>
>> Moreover people seem to be agree that diff machinery should learn
>> proper pathspecs too (i.e. globbing, negative pathspecs...), not just
>> treating pathspecs as tree prefix.
>
> There is nothing improper about the prefix match.  Perhaps "richer"?
> I am not so sure about the need/desirability of negative match, but we
> will see.

Negative match has been mentioned twice recently, once in Elijah's
sparse clone [1] and once by a user [2].

[1] http://mid.gmane.org/AANLkTikJhSVJw2hXkp0j6XA+k-J-AtSYzKWumjnqqsgz@mail.gmail.com

[2] http://mid.gmane.org/AANLkTikUadS+tj3ARdRqo=PSBVhTsJaUxaJv+=4hMf4s@mail.gmail.com

>
> About naming.  Where else other than "tree" (in the "hierarchical
> namespace" sense) context do you see pathspec?  Does the struct really
> need to be called TREE_pathspec_list?

Pathspecs are usually stored in a list, const char ** and I don't want
to take the generic name "pathspec_list", unless we convert all to use
this struct. Any suggestions of other names?
-- 
Duy

Re: [PATCH 7/8] setup_tree_pathspec(): interpret '^' as negative pathspec

[Nguyen Thai Ngoc Duy]

2010/9/15 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> This patch does preparation work for tree exclusion in
>> tree_entry_interesting(). '^' has similar meaning to '!' in
>> gitexcludes. '!' is not used because bash does not like arguments with
>> a leading '!'.
>
> Do not even mention gitexcludes as you have to make awkward excuse like
> this.
>
> Instead say something like
>
>    '^' works exactly like prefix '^' for revs (e.g. "log ^maint master")
>    to mark what is prefixed is excluded.

It was not thought through. The way this patch does means
get_pathspec() will need to be updated to handle the case "(in
subdir)$ git diff ^foo", which has to be turned to "(in toplevel)$ git
diff ^subdir/foo", not "(in toplevel)$ git diff subdir/^foo".

A better approach would be separate "^" out as an argument by itself,
i.e. "git diff ^ foo". Less work in get_pathspec(), and tab-comletion
on path also works. But now as '^' stands alone, '!' can be used too
(no more bash history expansion). And I think '!' is more intuitive
than '^'.
-- 
Duy

Re: [PATCH 8/8] tree_entry_interesting(): support negative pathspec

[Nguyen Thai Ngoc Duy]

2010/9/15 Junio C Hamano <gitster@pobox.com>:
>> diff --git a/tree-walk.c b/tree-walk.c
>> index a2f4a00..fd19681 100644
>> --- a/tree-walk.c
>> +++ b/tree-walk.c
>> @@ -532,7 +532,7 @@ int tree_entry_interesting(const struct name_entry *entry, const char *base, int
>>
>>       pathlen = tree_entry_len(entry->path, entry->sha1);
>>
>> -     for (i = 0; i < ps->nr; i++) {
>> +     for (i = ps->nr-1; i >= 0; i--) {
>
> No explanation in the commit log message why.  Besides, spell binary "-"
> operator with a SP each on both ends, please.
>
> Also the code seems to use a new term subpathspec without defining nor
> explaining.  Not good.

No, not good. It also has bugs as Elijah pointed out. I'm going to
submit these last two patches as a separate series that will make
negative match work on (hopefully) all commands.

Thanks for your comments.
-- 
Duy

Re: [PATCH 3/8] tree_entry_interesting(): remove dependency on struct diff_options

[Junio C Hamano]

Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:

>> About naming.  Where else other than "tree" (in the "hierarchical
>> namespace" sense) context do you see pathspec?  Does the struct really
>> need to be called TREE_pathspec_list?
>
> Pathspecs are usually stored in a list, const char ** and I don't want
> to take the generic name "pathspec_list", unless we convert all to use
> this struct. Any suggestions of other names?

I was hoping [*1*] that in the longer term we would have a unified
machinery to handle pathspecs across ls-tree, ls-files, diff-tree,
diff-files and grep.  These commands more or less share the same idea of
what purpose a pathspec serves, but take quite different codepaths, and
the biggest problem is that some know globbing while others don't.

The problem arising from the two semantics [*2*] is visible when you run
"git add" with pathspec where add_files_to_cache() updates the index only
at changed paths (found using diff-files machinery, that implements "diff"
family of pathspec semantics to match only directory prefix) and then
add_files() adds the paths that are untracked (found using the ls-files
machinery, that knows about globbing).

Once we have a unified machinery to handle pathspec, the data structure
that holds the pathspec should naturally be called "struct pathspec",
while an element on that list would be "struct pathspec_elem" or perhaps
"struct pathspec_pattern" [*3*].

I would imagine that "struct exclude" (in dir.[ch]) that is contained in
"struct exclude_list" might be a good place to start from, in the sense
that it shows how a match pattern can be pre-parsed to optimize the
matching operation [*4*].  It however may not know about one particular
kind of optimization that is essential when dealing with tree objects: the
ability to ask "is this subtree worth descending into?".  That logic is
necessary to avoid opening unnecessary tree objects in diff-tree and grep.


[Footnote]

*1* https://git.wiki.kernel.org/index.php/SoC2010Ideas#Unify_Pathspec_Semantics

*2* As the maintainer, I do consider it also is a problem that each
of these semantics has multiple codepaths to implement it, but that is a
secondary issue.  Having two semantics is visible to the end user and is a
bigger problem.

*3* I personally tend to consider the whole set as _a_ "path specification"
even when you give more than one patterns to match on the command line,
but it may be just me.  I am Ok with "struct pathspec_set" that holds a
set of "struct pathspec", too.  Unlike exclude-list where the order of
elements in it has a meaning, the matching patterns in a pathspec are
unordered, so even if we may end up implementing it as a list, it would be
incorrect to call that "struct pathspec_list".

*4* "struct exclude_list" is somewhat special in that it is a dynamic data
source where you learn more matching rules as you dig deeper.  We do not
need that aspect of the dir.[ch] codepath for unified pathspec handling.