[PATCH 00/21] nd/struct-pathspec v2

[PATCH 00/21] nd/struct-pathspec v2

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

Changes from previous version [1]

 - fixes depth limit and overlapping pathspecs, by checking deepest
   pathspecs first. struct pathspec is now sorted (raw[] untouched)

 - match_pathspec_depth depends on new match_pathspec_item() (a
   clone of match_one(), but takes advantage of struct pathspec)

 - ce_path_match uses struct pathspec

 - strbuf is used instead of fixed length "base" buffer. This
   introduces the weird strbuf_offset() function.

 - never_interesting is disabled if any wildcards is present

 - struct pathspec * == NULL is unacceptable, callers must pass
   non-NULL.

 - a bit more tests

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

Jonathan Nieder (1):
  glossary: define pathspec

Nguyễn Thái Ngọc Duy (20):
  Add struct pathspec
  diff-no-index: use diff_tree_setup_paths()
  Convert struct diff_options to use struct pathspec
  tree_entry_interesting(): remove dependency on struct diff_options
  Move tree_entry_interesting() to tree-walk.c and export it
  diff-tree: convert base+baselen to writable strbuf
  tree_entry_interesting(): refactor into separate smaller functions
  tree_entry_interesting(): support depth limit
  tree_entry_interesting(): fix depth limit with overlapping pathspecs
  tree_entry_interesting(): support wildcard matching
  tree_entry_interesting(): optimize wildcard matching when base is matched
  pathspec: add match_pathspec_depth()
  Convert ce_path_match() to use struct pathspec
  Convert ce_path_match() to use match_pathspec_depth()
  grep: convert to use struct pathspec
  grep: use match_pathspec_depth() for cache/worktree grepping
  strbuf: allow "buf" to point to the middle of the allocated buffer
  grep: use writable strbuf from caller for grep_tree()
  grep: drop pathspec_matches() in favor of tree_entry_interesting()
  t7810: overlapping pathspecs and depth limit

 Documentation/glossary-content.txt |   23 +++
 builtin/diff-files.c               |    2 +-
 builtin/diff.c                     |    4 +-
 builtin/grep.c                     |  197 +++++++-------------------
 builtin/log.c                      |    2 +-
 builtin/update-index.c             |    8 +-
 cache.h                            |   17 ++-
 diff-lib.c                         |   12 ++-
 diff-no-index.c                    |   13 +-
 diff.h                             |    4 +-
 dir.c                              |  151 ++++++++++++++++++++
 dir.h                              |    4 +
 preload-index.c                    |    5 +-
 read-cache.c                       |   25 +---
 revision.c                         |   11 +-
 strbuf.c                           |   36 ++++--
 strbuf.h                           |   10 +-
 t/t4010-diff-pathspec.sh           |   32 ++++
 t/t7810-grep.sh                    |   18 +++
 tree-diff.c                        |  277 +++++++++---------------------------
 tree-walk.c                        |  180 +++++++++++++++++++++++
 tree-walk.h                        |    2 +
 wt-status.c                        |    5 +-
 23 files changed, 615 insertions(+), 423 deletions(-)

-- 
1.7.3.3.476.g10a82

[PATCH 01/21] Add struct pathspec

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

The old pathspec structure remains as pathspec.raw[]. New things are
stored in pathspec.items[]. There's no guarantee that the pathspec
order in raw[] is exactly as in items[].

raw[] is external (source) data and is untouched by pathspec
manipulation functions. It eases migration from old const char ** to
this new struct.

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

diff --git a/cache.h b/cache.h
index 2ef2fa3..9eeecc2 100644
--- a/cache.h
+++ b/cache.h
@@ -493,6 +493,17 @@ extern int index_name_is_other(const struct index_state *, const char *, int);
 extern int ie_match_stat(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);
 extern int ie_modified(const struct index_state *, struct cache_entry *, struct stat *, unsigned int);
 
+struct pathspec {
+	const char **raw; /* get_pathspec() result, not freed by free_pathspec() */
+	int nr;
+	struct pathspec_item {
+		const char *match;
+		int len;
+	} *items;
+};
+
+extern int init_pathspec(struct pathspec *, const char **);
+extern void free_pathspec(struct pathspec *);
 extern int ce_path_match(const struct cache_entry *ce, const char **pathspec);
 extern int index_fd(unsigned char *sha1, int fd, struct stat *st, int write_object, enum object_type type, const char *path);
 extern int index_path(unsigned char *sha1, const char *path, struct stat *st, int write_object);
diff --git a/dir.c b/dir.c
index 133f472..a88f2ef 100644
--- a/dir.c
+++ b/dir.c
@@ -1071,3 +1071,34 @@ int remove_path(const char *name)
 	return 0;
 }
 
+int init_pathspec(struct pathspec *pathspec, const char **paths)
+{
+	const char **p = paths;
+	int i;
+
+	memset(pathspec, 0, sizeof(*pathspec));
+	if (!p)
+		return 0;
+	while (*p)
+		p++;
+	pathspec->raw = paths;
+	pathspec->nr = p - paths;
+	if (!pathspec->nr)
+		return 0;
+
+	pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
+	for (i = 0; i < pathspec->nr; i++) {
+		struct pathspec_item *item = pathspec->items+i;
+		const char *path = paths[i];
+
+		item->match = path;
+		item->len = strlen(path);
+	}
+	return 0;
+}
+
+void free_pathspec(struct pathspec *pathspec)
+{
+	free(pathspec->items);
+	pathspec->items = NULL;
+}
-- 
1.7.3.3.476.g10a82

[PATCH 02/21] 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.3.3.476.g10a82

[PATCH 03/21] Convert struct diff_options to use struct pathspec

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

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          |   48 +++++++++++++-----------------------------------
 8 files changed, 22 insertions(+), 50 deletions(-)

diff --git a/builtin/diff-files.c b/builtin/diff-files.c
index 951c7c8..46085f8 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.raw) < 0) {
 		perror("read_cache_preload");
 		return -1;
 	}
diff --git a/builtin/diff.c b/builtin/diff.c
index a43d326..76c42d8 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.raw) < 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.raw) < 0) {
 		perror("read_cache_preload");
 		return -1;
 	}
diff --git a/builtin/log.c b/builtin/log.c
index eaa1ee0..92779a5 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..3b809f2 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.raw;
 	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..3a36144 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.raw[0],
+		       revs->diffopt.pathspec.raw[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..6497b71 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 pathspec 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..7a4cc4b 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -100,16 +100,17 @@ 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 struct pathspec_item *item = opt->pathspec.items+i;
+		const char *match = item->match;
+		int matchlen = item->len;
 		int m = -1; /* signals that we haven't called strncmp() */
 
 		if (baselen >= matchlen) {
@@ -289,7 +290,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 +349,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.raw[0];
 	diff_opts.break_opt = opt->break_opt;
 	paths[0] = NULL;
 	diff_tree_setup_paths(paths, &diff_opts);
@@ -368,15 +369,16 @@ 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.raw[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.raw[0] = xstrdup(p->one->path);
+			diff_tree_setup_paths(opt->pathspec.raw, opt);
 
 			/*
 			 * The caller expects us to return a set of vanilla
@@ -451,36 +453,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_pathspec(&opt->pathspec);
 }
 
 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]);
-	}
+	init_pathspec(&opt->pathspec, p);
 }
-- 
1.7.3.3.476.g10a82

[PATCH 04/21] 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().

While removing the use of diff_options, it also removes
tree_entry_extract() call, which means S_ISDIR() uses the entry->mode
directly, without being filtered by canon_mode() (called internally
inside tree_entry_extract).

The only use of the mode information in this function is to check the
type of the entry by giving it to S_ISDIR() macro, and the result does
not change with or without canon_mode(), so it is ok to bypass
tree_entry_extract().

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

diff --git a/tree-diff.c b/tree-diff.c
index 7a4cc4b..57e8909 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -91,24 +91,19 @@ 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 pathspec *ps)
 {
-	const char *path;
-	const unsigned char *sha1;
-	unsigned mode;
 	int i;
 	int pathlen;
 	int never_interesting = -1;
 
-	if (!opt->pathspec.nr)
+	if (!ps || !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 struct pathspec_item *item = opt->pathspec.items+i;
+	for (i = 0; i < ps->nr; i++) {
+		const struct pathspec_item *item = ps->items+i;
 		const char *match = item->match;
 		int matchlen = item->len;
 		int m = -1; /* signals that we haven't called strncmp() */
@@ -148,7 +143,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;
@@ -175,7 +170,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;
 		}
 
@@ -184,7 +179,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,
@@ -207,8 +202,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;
 		}
@@ -267,7 +261,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.3.3.476.g10a82

[PATCH 05/21] Move tree_entry_interesting() to tree-walk.c and export it

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

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

diff --git a/tree-diff.c b/tree-diff.c
index 57e8909..28a69dc 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -82,116 +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 pathspec *ps)
-{
-	int i;
-	int pathlen;
-	int never_interesting = -1;
-
-	if (!ps || !ps->nr)
-		return 1;
-
-	pathlen = tree_entry_len(entry->path, entry->sha1);
-
-	for (i = 0; i < ps->nr; i++) {
-		const struct pathspec_item *item = ps->items+i;
-		const char *match = item->match;
-		int matchlen = item->len;
-		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 a9bbf4e..a2e2a99 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -455,3 +455,115 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 	free(tree);
 	return retval;
 }
+
+/*
+ * 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 pathspec *ps)
+{
+	int i;
+	int pathlen;
+	int never_interesting = -1;
+
+	if (!ps || !ps->nr)
+		return 1;
+
+	pathlen = tree_entry_len(entry->path, entry->sha1);
+
+	for (i = 0; i < ps->nr; i++) {
+		const struct pathspec_item *item = ps->items+i;
+		const char *match = item->match;
+		int matchlen = item->len;
+		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 7e3e0b5..c12f0a2 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -60,4 +60,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 tree_entry_interesting(const struct name_entry *, const char *, int, const struct pathspec *ps);
+
 #endif
-- 
1.7.3.3.476.g10a82

[PATCH 06/21] glossary: define pathspec

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

From: Jonathan Nieder <jrnieder@gmail.com>


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

diff --git a/Documentation/glossary-content.txt b/Documentation/glossary-content.txt
index 1f029f8..4ed2a28 100644
--- a/Documentation/glossary-content.txt
+++ b/Documentation/glossary-content.txt
@@ -273,6 +273,29 @@ This commit is referred to as a "merge commit", or sometimes just a
 	<<def_pack,pack>>, to assist in efficiently accessing the contents of a
 	pack.
 
+[[def_pathspec]]pathspec::
+       Pattern used to specify paths.
++
+Pathspecs are used on the command line of "git ls-files", "git
+ls-tree", "git grep", "git checkout", and many other commands to
+limit the scope of operations to some subset of the tree or
+worktree.  See the documentation of each command for whether
+paths are relative to the current directory or toplevel.  The
+pathspec syntax is as follows:
+
+* any path matches itself
+* the pathspec up to the last slash represents a
+  directory prefix.  The scope of that pathspec is
+  limited to that subtree.
+* the rest of the pathspec is a pattern for the remainder
+  of the pathname.  Paths relative to the directory
+  prefix will be matched against that pattern using fnmatch(3);
+  in particular, '*' and '?' _can_ match directory separators.
++
+For example, Documentation/*.jpg will match all .jpg files
+in the Documentation subtree,
+including Documentation/chapter_1/figure_1.jpg.
+
 [[def_parent]]parent::
 	A <<def_commit_object,commit object>> contains a (possibly empty) list
 	of the logical predecessor(s) in the line of development, i.e. its
-- 
1.7.3.3.476.g10a82

[PATCH 07/21] diff-tree: convert base+baselen to writable strbuf

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

In traversing trees, a full path is splitted into two parts: base
directory and entry. They are however quite often concatenated
whenever a full path is needed. Current code allocates a new buffer,
do two memcpy(), use it, then release.

Instead this patch turns "base" to a writable, extendable buffer. When
a concatenation is needed, the callee only needs to append "entry" to
base, use it, then truncate the entry out again. "base" must remain
unchanged before and after entering a function.

This avoids quite a bit of malloc() and memcpy().

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

diff --git a/tree-diff.c b/tree-diff.c
index 28a69dc..67fa6c4 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -6,34 +6,18 @@
 #include "diffcore.h"
 #include "tree.h"
 
-static char *malloc_base(const char *base, int baselen, const char *path, int pathlen)
-{
-	char *newbase = xmalloc(baselen + pathlen + 2);
-	memcpy(newbase, base, baselen);
-	memcpy(newbase + baselen, path, pathlen);
-	memcpy(newbase + baselen + pathlen, "/", 2);
-	return newbase;
-}
-
-static char *malloc_fullname(const char *base, int baselen, const char *path, int pathlen)
-{
-	char *fullname = xmalloc(baselen + pathlen + 1);
-	memcpy(fullname, base, baselen);
-	memcpy(fullname + baselen, path, pathlen);
-	fullname[baselen + pathlen] = 0;
-	return fullname;
-}
-
-static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
-		       const char *base, int baselen);
+static void show_entry(struct diff_options *opt, const char *prefix,
+		       struct tree_desc *desc, struct strbuf *base);
 
-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const char *base, int baselen, struct diff_options *opt)
+static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
+			      struct strbuf *base, struct diff_options *opt)
 {
 	unsigned mode1, mode2;
 	const char *path1, *path2;
 	const unsigned char *sha1, *sha2;
 	int cmp, pathlen1, pathlen2;
-	char *fullname;
+	int old_baselen = base->len;
+	int retval = 0;
 
 	sha1 = tree_entry_extract(t1, &path1, &mode1);
 	sha2 = tree_entry_extract(t2, &path2, &mode2);
@@ -42,11 +26,11 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	pathlen2 = tree_entry_len(path2, sha2);
 	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
 	if (cmp < 0) {
-		show_entry(opt, "-", t1, base, baselen);
+		show_entry(opt, "-", t1, base);
 		return -1;
 	}
 	if (cmp > 0) {
-		show_entry(opt, "+", t2, base, baselen);
+		show_entry(opt, "+", t2, base);
 		return 1;
 	}
 	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
@@ -57,33 +41,29 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	 * file, we need to consider it a remove and an add.
 	 */
 	if (S_ISDIR(mode1) != S_ISDIR(mode2)) {
-		show_entry(opt, "-", t1, base, baselen);
-		show_entry(opt, "+", t2, base, baselen);
+		show_entry(opt, "-", t1, base);
+		show_entry(opt, "+", t2, base);
 		return 0;
 	}
 
+	strbuf_add(base, path1, pathlen1);
 	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
-		int retval;
-		char *newbase = malloc_base(base, baselen, path1, pathlen1);
 		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
-			newbase[baselen + pathlen1] = 0;
 			opt->change(opt, mode1, mode2,
-				    sha1, sha2, newbase, 0, 0);
-			newbase[baselen + pathlen1] = '/';
+				    sha1, sha2, base->buf, 0, 0);
 		}
-		retval = diff_tree_sha1(sha1, sha2, newbase, opt);
-		free(newbase);
-		return retval;
+		strbuf_addch(base, '/');
+		retval = diff_tree_sha1(sha1, sha2, base->buf, opt);
 	}
-
-	fullname = malloc_fullname(base, baselen, path1, pathlen1);
-	opt->change(opt, mode1, mode2, sha1, sha2, fullname, 0, 0);
-	free(fullname);
+	else
+		opt->change(opt, mode1, mode2, sha1, sha2, base->buf, 0, 0);
+	strbuf_setlen(base, old_baselen);
 	return 0;
 }
 
 /* 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)
+static void show_tree(struct diff_options *opt, const char *prefix,
+		      struct tree_desc *desc, struct strbuf *base)
 {
 	int all_interesting = 0;
 	while (desc->size) {
@@ -92,30 +72,32 @@ static void show_tree(struct diff_options *opt, const char *prefix, struct tree_
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(&desc->entry, base, baselen, &opt->pathspec);
+			show = tree_entry_interesting(&desc->entry, base,
+						      &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
 		}
 		if (show < 0)
 			break;
 		if (show)
-			show_entry(opt, prefix, desc, base, baselen);
+			show_entry(opt, prefix, desc, base);
 		update_tree_entry(desc);
 	}
 }
 
 /* A file entry went away or appeared */
-static void show_entry(struct diff_options *opt, const char *prefix, struct tree_desc *desc,
-		       const char *base, int baselen)
+static void show_entry(struct diff_options *opt, const char *prefix,
+		       struct tree_desc *desc, struct strbuf *base)
 {
 	unsigned mode;
 	const char *path;
 	const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
 	int pathlen = tree_entry_len(path, sha1);
+	int old_baselen = base->len;
 
+	strbuf_add(base, path, pathlen);
 	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
 		enum object_type type;
-		char *newbase = malloc_base(base, baselen, path, pathlen);
 		struct tree_desc inner;
 		void *tree;
 		unsigned long size;
@@ -124,25 +106,22 @@ static void show_entry(struct diff_options *opt, const char *prefix, struct tree
 		if (!tree || type != OBJ_TREE)
 			die("corrupt tree sha %s", sha1_to_hex(sha1));
 
-		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
-			newbase[baselen + pathlen] = 0;
-			opt->add_remove(opt, *prefix, mode, sha1, newbase, 0);
-			newbase[baselen + pathlen] = '/';
-		}
+		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
+			opt->add_remove(opt, *prefix, mode, sha1, base->buf, 0);
 
-		init_tree_desc(&inner, tree, size);
-		show_tree(opt, prefix, &inner, newbase, baselen + 1 + pathlen);
+		strbuf_addch(base, '/');
 
+		init_tree_desc(&inner, tree, size);
+		show_tree(opt, prefix, &inner, base);
 		free(tree);
-		free(newbase);
-	} else {
-		char *fullname = malloc_fullname(base, baselen, path, pathlen);
-		opt->add_remove(opt, prefix[0], mode, sha1, fullname, 0);
-		free(fullname);
-	}
+	} else
+		opt->add_remove(opt, prefix[0], mode, sha1, base->buf, 0);
+
+	strbuf_setlen(base, old_baselen);
 }
 
-static void skip_uninteresting(struct tree_desc *t, const char *base, int baselen, struct diff_options *opt)
+static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
+			       struct diff_options *opt)
 {
 	int all_interesting = 0;
 	while (t->size) {
@@ -151,7 +130,8 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int basele
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(&t->entry, base, baselen, &opt->pathspec);
+			show = tree_entry_interesting(&t->entry, base,
+						      &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
 		}
@@ -166,31 +146,36 @@ static void skip_uninteresting(struct tree_desc *t, const char *base, int basele
 	}
 }
 
-int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
+int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
+	      const char *base_str, struct diff_options *opt)
 {
-	int baselen = strlen(base);
+	struct strbuf base;
+	int baselen = strlen(base_str);
+
+	strbuf_init(&base, PATH_MAX);
+	strbuf_add(&base, base_str, baselen);
 
 	for (;;) {
 		if (DIFF_OPT_TST(opt, QUICK) &&
 		    DIFF_OPT_TST(opt, HAS_CHANGES))
 			break;
 		if (opt->pathspec.nr) {
-			skip_uninteresting(t1, base, baselen, opt);
-			skip_uninteresting(t2, base, baselen, opt);
+			skip_uninteresting(t1, &base, opt);
+			skip_uninteresting(t2, &base, opt);
 		}
 		if (!t1->size) {
 			if (!t2->size)
 				break;
-			show_entry(opt, "+", t2, base, baselen);
+			show_entry(opt, "+", t2, &base);
 			update_tree_entry(t2);
 			continue;
 		}
 		if (!t2->size) {
-			show_entry(opt, "-", t1, base, baselen);
+			show_entry(opt, "-", t1, &base);
 			update_tree_entry(t1);
 			continue;
 		}
-		switch (compare_tree_entry(t1, t2, base, baselen, opt)) {
+		switch (compare_tree_entry(t1, t2, &base, opt)) {
 		case -1:
 			update_tree_entry(t1);
 			continue;
@@ -203,6 +188,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru
 		}
 		die("git diff-tree: internal error");
 	}
+
+	strbuf_release(&base);
 	return 0;
 }
 
diff --git a/tree-walk.c b/tree-walk.c
index a2e2a99..0830676 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -466,12 +466,13 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
  *  - 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 strbuf *base_buf,
 			   const struct pathspec *ps)
 {
 	int i;
-	int pathlen;
+	int pathlen, baselen = base_buf->len;
 	int never_interesting = -1;
+	const char *base = base_buf->buf;
 
 	if (!ps || !ps->nr)
 		return 1;
diff --git a/tree-walk.h b/tree-walk.h
index c12f0a2..f81c232 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -60,6 +60,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 tree_entry_interesting(const struct name_entry *, const char *, int, const struct pathspec *ps);
+extern int tree_entry_interesting(const struct name_entry *, const struct strbuf *, const struct pathspec *ps);
 
 #endif
-- 
1.7.3.3.476.g10a82

[PATCH 08/21] tree_entry_interesting(): refactor into separate smaller functions

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

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

diff --git a/tree-walk.c b/tree-walk.c
index 0830676..5012705 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -456,6 +456,90 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
 	return retval;
 }
 
+static int match_entry(const struct name_entry *entry, int pathlen,
+		       const char *match, int matchlen,
+		       int *never_interesting)
+{
+	int m = -1; /* signals that we haven't called strncmp() */
+
+	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)
+			return 0;
+
+		/*
+		 * 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)
+		return 0;
+
+	if (matchlen > pathlen) {
+		if (match[pathlen] != '/')
+			return 0;
+		if (!S_ISDIR(entry->mode))
+			return 0;
+	}
+
+	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 0;
+}
+
+static int match_dir_prefix(const char *base, int baselen,
+			    const char *match, int matchlen)
+{
+	if (strncmp(base, match, matchlen))
+		return 0;
+
+	/*
+	 * 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 1;
+
+	/* Just a random prefix match */
+	return 0;
+}
+
 /*
  * Is a tree entry interesting given the pathspec we have?
  *
@@ -466,13 +550,12 @@ int get_tree_entry(const unsigned char *tree_sha1, const char *name, unsigned ch
  *  - negative for "no, and no subsequent entries will be either"
  */
 int tree_entry_interesting(const struct name_entry *entry,
-			   const struct strbuf *base_buf,
+			   const struct strbuf *base,
 			   const struct pathspec *ps)
 {
 	int i;
-	int pathlen, baselen = base_buf->len;
+	int pathlen, baselen = base->len;
 	int never_interesting = -1;
-	const char *base = base_buf->buf;
 
 	if (!ps || !ps->nr)
 		return 1;
@@ -483,88 +566,21 @@ int tree_entry_interesting(const struct name_entry *entry,
 		const struct pathspec_item *item = ps->items+i;
 		const char *match = item->match;
 		int matchlen = item->len;
-		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))
+			if (!match_dir_prefix(base->buf, baselen, 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;
+			return 2;
 		}
 
 		/* 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 (!strncmp(base->buf, match, baselen)) {
+			if (match_entry(entry, pathlen,
+					match + baselen, matchlen - baselen,
+					&never_interesting))
+				return 1;
 		}
-
-		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 */
 }
-- 
1.7.3.3.476.g10a82

[PATCH 09/21] tree_entry_interesting(): support depth limit

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

This is needed to replace pathspec_matches() in builtin/grep.c.

max_depth == -1 means infinite depth. Depth limit is only effective
when pathspec.recursive == 1. When pathspec.recursive == 0, the
behavior depends on match functions: non-recursive for
tree_entry_interesting() and recursive for match_pathspec{,_depth}

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h     |    2 ++
 dir.c       |   15 +++++++++++++++
 dir.h       |    1 +
 tree-diff.c |    4 ++++
 tree-walk.c |   19 ++++++++++++++++---
 5 files changed, 38 insertions(+), 3 deletions(-)

diff --git a/cache.h b/cache.h
index 9eeecc2..b110775 100644
--- a/cache.h
+++ b/cache.h
@@ -496,6 +496,8 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
 struct pathspec {
 	const char **raw; /* get_pathspec() result, not freed by free_pathspec() */
 	int nr;
+	int recursive:1;
+	int max_depth;
 	struct pathspec_item {
 		const char *match;
 		int len;
diff --git a/dir.c b/dir.c
index a88f2ef..79e88f6 100644
--- a/dir.c
+++ b/dir.c
@@ -71,6 +71,21 @@ int fill_directory(struct dir_struct *dir, const char **pathspec)
 	return len;
 }
 
+int within_depth(const char *name, int namelen,
+			int depth, int max_depth)
+{
+	const char *cp = name, *cpe = name + namelen;
+
+	while (cp < cpe) {
+		if (*cp++ != '/')
+			continue;
+		depth++;
+		if (depth > max_depth)
+			return 0;
+	}
+	return 1;
+}
+
 /*
  * Does 'match' match the given name?
  * A match is found if
diff --git a/dir.h b/dir.h
index 278d84c..c71de08 100644
--- a/dir.h
+++ b/dir.h
@@ -65,6 +65,7 @@ struct dir_struct {
 #define MATCHED_FNMATCH 2
 #define MATCHED_EXACTLY 3
 extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);
+extern int within_depth(const char *name, int namelen, int depth, int max_depth);
 
 extern int fill_directory(struct dir_struct *dir, const char **pathspec);
 extern int read_directory(struct dir_struct *, const char *path, int len, const char **pathspec);
diff --git a/tree-diff.c b/tree-diff.c
index 67fa6c4..bde2c52 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -152,6 +152,10 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 	struct strbuf base;
 	int baselen = strlen(base_str);
 
+	/* Enable recursion indefinitely */
+	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
+	opt->pathspec.max_depth = -1;
+
 	strbuf_init(&base, PATH_MAX);
 	strbuf_add(&base, base_str, baselen);
 
diff --git a/tree-walk.c b/tree-walk.c
index 5012705..91d7b36 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "tree-walk.h"
 #include "unpack-trees.h"
+#include "dir.h"
 #include "tree.h"
 
 static const char *get_mode(const char *str, unsigned int *modep)
@@ -557,8 +558,13 @@ int tree_entry_interesting(const struct name_entry *entry,
 	int pathlen, baselen = base->len;
 	int never_interesting = -1;
 
-	if (!ps || !ps->nr)
-		return 1;
+	if (!ps->nr) {
+		if (!ps->recursive || ps->max_depth == -1)
+			return 1;
+		return !!within_depth(base->buf, baselen,
+				      !!S_ISDIR(entry->mode),
+				      ps->max_depth);
+	}
 
 	pathlen = tree_entry_len(entry->path, entry->sha1);
 
@@ -571,7 +577,14 @@ int tree_entry_interesting(const struct name_entry *entry,
 			/* If it doesn't match, move along... */
 			if (!match_dir_prefix(base->buf, baselen, match, matchlen))
 				continue;
-			return 2;
+
+			if (!ps->recursive || ps->max_depth == -1)
+				return 2;
+
+			return !!within_depth(base->buf + matchlen + 1,
+					      baselen - matchlen - 1,
+					      !!S_ISDIR(entry->mode),
+					      ps->max_depth);
 		}
 
 		/* Does the base match? */
-- 
1.7.3.3.476.g10a82

[PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

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

Suppose we have two pathspecs 'a' and 'a/b' (both are dirs) and depth
limit 1. In current code, pathspecs are checked in input order. When
'a/b' is checked against pathspec 'a', it fails depth limit and
therefore is excluded, although it should match 'a/b' pathspec.

This patch reorders all pathspecs alphabetically, then teaches
tree_entry_interesting() to check against the deepest pathspec first,
so depth limit of a shallower pathspec won't affect a deeper one.

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

diff --git a/dir.c b/dir.c
index 79e88f6..aa0522d 100644
--- a/dir.c
+++ b/dir.c
@@ -1086,6 +1086,15 @@ int remove_path(const char *name)
 	return 0;
 }
 
+static int pathspec_item_cmp(const void *a_, const void *b_)
+{
+	struct pathspec_item *a, *b;
+
+	a = (struct pathspec_item *)a_;
+	b = (struct pathspec_item *)b_;
+	return strcmp(a->match, b->match);
+}
+
 int init_pathspec(struct pathspec *pathspec, const char **paths)
 {
 	const char **p = paths;
@@ -1109,6 +1118,10 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)
 		item->match = path;
 		item->len = strlen(path);
 	}
+
+	qsort(pathspec->items, pathspec->nr,
+	      sizeof(struct pathspec_item), pathspec_item_cmp);
+
 	return 0;
 }
 
diff --git a/tree-walk.c b/tree-walk.c
index 91d7b36..93b05a7 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -568,7 +568,7 @@ int tree_entry_interesting(const struct name_entry *entry,
 
 	pathlen = tree_entry_len(entry->path, entry->sha1);
 
-	for (i = 0; i < ps->nr; i++) {
+	for (i = ps->nr-1; i >= 0; i--) {
 		const struct pathspec_item *item = ps->items+i;
 		const char *match = item->match;
 		int matchlen = item->len;
-- 
1.7.3.3.476.g10a82

[PATCH 11/21] tree_entry_interesting(): support wildcard matching

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

never_interesting optimization is disabled if there is any wildcard
pathspec, even if it only matches exactly on trees.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 cache.h                  |    2 ++
 dir.c                    |    3 +++
 t/t4010-diff-pathspec.sh |   14 ++++++++++++++
 tree-walk.c              |   30 +++++++++++++++++++++++++++---
 tree-walk.h              |    2 +-
 5 files changed, 47 insertions(+), 4 deletions(-)

diff --git a/cache.h b/cache.h
index b110775..dc0bfb4 100644
--- a/cache.h
+++ b/cache.h
@@ -496,11 +496,13 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
 struct pathspec {
 	const char **raw; /* get_pathspec() result, not freed by free_pathspec() */
 	int nr;
+	int has_wildcard:1;
 	int recursive:1;
 	int max_depth;
 	struct pathspec_item {
 		const char *match;
 		int len;
+		int has_wildcard:1;
 	} *items;
 };
 
diff --git a/dir.c b/dir.c
index aa0522d..66c163f 100644
--- a/dir.c
+++ b/dir.c
@@ -1117,6 +1117,9 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)
 
 		item->match = path;
 		item->len = strlen(path);
+		item->has_wildcard = !no_wildcard(path);
+		if (item->has_wildcard)
+			pathspec->has_wildcard = 1;
 	}
 
 	qsort(pathspec->items, pathspec->nr,
diff --git a/t/t4010-diff-pathspec.sh b/t/t4010-diff-pathspec.sh
index 94df7ae..4b120f8 100755
--- a/t/t4010-diff-pathspec.sh
+++ b/t/t4010-diff-pathspec.sh
@@ -70,4 +70,18 @@ test_expect_success 'diff-tree pathspec' '
 	test_cmp expected current
 '
 
+EMPTY_TREE=4b825dc642cb6eb9a060e54bf8d69288fbee4904
+
+test_expect_success 'diff-tree with wildcard shows dir also matches' '
+	git diff-tree --name-only $EMPTY_TREE $tree -- "f*" >result &&
+	echo file0 >expected &&
+	test_cmp expected result
+'
+
+test_expect_success 'diff-tree -r with wildcard' '
+	git diff-tree -r --name-only $EMPTY_TREE $tree -- "*file1" >result &&
+	echo path1/file1 >expected &&
+	test_cmp expected result
+'
+
 test_done
diff --git a/tree-walk.c b/tree-walk.c
index 93b05a7..cc5a4e1 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -551,12 +551,12 @@ static int match_dir_prefix(const char *base, int baselen,
  *  - negative for "no, and no subsequent entries will be either"
  */
 int tree_entry_interesting(const struct name_entry *entry,
-			   const struct strbuf *base,
+			   struct strbuf *base,
 			   const struct pathspec *ps)
 {
 	int i;
 	int pathlen, baselen = base->len;
-	int never_interesting = -1;
+	int never_interesting = ps->has_wildcard ? 0 : -1;
 
 	if (!ps->nr) {
 		if (!ps->recursive || ps->max_depth == -1)
@@ -576,7 +576,7 @@ int tree_entry_interesting(const struct name_entry *entry,
 		if (baselen >= matchlen) {
 			/* If it doesn't match, move along... */
 			if (!match_dir_prefix(base->buf, baselen, match, matchlen))
-				continue;
+				goto match_wildcards;
 
 			if (!ps->recursive || ps->max_depth == -1)
 				return 2;
@@ -594,6 +594,30 @@ int tree_entry_interesting(const struct name_entry *entry,
 					&never_interesting))
 				return 1;
 		}
+
+match_wildcards:
+		if (!ps->items[i].has_wildcard)
+			continue;
+
+		/*
+		 * Concatenate base and entry->path into one and do
+		 * fnmatch() on it.
+		 */
+
+		strbuf_add(base, entry->path, pathlen);
+
+		if (!fnmatch(match, base->buf, 0)) {
+			strbuf_setlen(base, baselen);
+			return 1;
+		}
+		strbuf_setlen(base, baselen);
+
+		/*
+		 * Match all directories. We'll try to match files
+		 * later on.
+		 */
+		if (ps->recursive && S_ISDIR(entry->mode))
+			return 1;
 	}
 	return never_interesting; /* No matches */
 }
diff --git a/tree-walk.h b/tree-walk.h
index f81c232..6589ee2 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -60,6 +60,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 tree_entry_interesting(const struct name_entry *, const struct strbuf *, const struct pathspec *ps);
+extern int tree_entry_interesting(const struct name_entry *, struct strbuf *, const struct pathspec *ps);
 
 #endif
-- 
1.7.3.3.476.g10a82

[PATCH 12/21] tree_entry_interesting(): optimize wildcard matching when base is matched

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

If base is already matched, skip that part when calling
fnmatch(). This happens quite often if users start a command from
worktree's subdirectory and prefix is usually prepended to all
pathspecs.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t4010-diff-pathspec.sh |   18 ++++++++++++++++++
 tree-walk.c              |   14 ++++++++++++++
 2 files changed, 32 insertions(+), 0 deletions(-)

diff --git a/t/t4010-diff-pathspec.sh b/t/t4010-diff-pathspec.sh
index 4b120f8..fbc8cd8 100755
--- a/t/t4010-diff-pathspec.sh
+++ b/t/t4010-diff-pathspec.sh
@@ -84,4 +84,22 @@ test_expect_success 'diff-tree -r with wildcard' '
 	test_cmp expected result
 '
 
+test_expect_success 'diff-tree with wildcard shows dir also matches' '
+	git diff-tree --name-only $tree $tree2 -- "path1/f*" >result &&
+	echo path1 >expected &&
+	test_cmp expected result
+'
+
+test_expect_success 'diff-tree -r with wildcard from beginning' '
+	git diff-tree -r --name-only $tree $tree2 -- "path1/*file1" >result &&
+	echo path1/file1 >expected &&
+	test_cmp expected result
+'
+
+test_expect_success 'diff-tree -r with wildcard' '
+	git diff-tree -r --name-only $tree $tree2 -- "path1/f*" >result &&
+	echo path1/file1 >expected &&
+	test_cmp expected result
+'
+
 test_done
diff --git a/tree-walk.c b/tree-walk.c
index cc5a4e1..99413b3 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -593,6 +593,20 @@ int tree_entry_interesting(const struct name_entry *entry,
 					match + baselen, matchlen - baselen,
 					&never_interesting))
 				return 1;
+
+			if (ps->items[i].has_wildcard) {
+				if (!fnmatch(match + baselen, entry->path, 0))
+					return 1;
+
+				/*
+				 * Match all directories. We'll try to
+				 * match files later on.
+				 */
+				if (ps->recursive && S_ISDIR(entry->mode))
+					return 1;
+			}
+
+			continue;
 		}
 
 match_wildcards:
-- 
1.7.3.3.476.g10a82

[PATCH 13/21] pathspec: add match_pathspec_depth()

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

match_pathspec_depth() is a clone of match_pathspec() except that it
can take depth limit. Computation is a bit lighter compared to
match_pathspec() because it's usually precomputed and stored in struct
pathspec.

In long term, match_pathspec() and match_one() should be removed in
favor of this function.

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

diff --git a/dir.c b/dir.c
index 66c163f..b1407a5 100644
--- a/dir.c
+++ b/dir.c
@@ -169,6 +169,95 @@ int match_pathspec(const char **pathspec, const char *name, int namelen,
 	return retval;
 }
 
+/*
+ * Does 'match' match the given name?
+ * A match is found if
+ *
+ * (1) the 'match' string is leading directory of 'name', or
+ * (2) the 'match' string is a wildcard and matches 'name', or
+ * (3) the 'match' string is exactly the same as 'name'.
+ *
+ * and the return value tells which case it was.
+ *
+ * It returns 0 when there is no match.
+ */
+static int match_pathspec_item(const struct pathspec_item *item, int prefix,
+			       const char *name, int namelen)
+{
+	/* name/namelen has prefix cut off by caller */
+	const char *match = item->match + prefix;
+	int matchlen = item->len - prefix;
+
+	/* If the match was just the prefix, we matched */
+	if (!*match)
+		return MATCHED_RECURSIVELY;
+
+	if (matchlen <= namelen && !strncmp(match, name, matchlen)) {
+		if (matchlen == namelen)
+			return MATCHED_EXACTLY;
+
+		if (match[matchlen-1] == '/' || name[matchlen] == '/')
+			return MATCHED_RECURSIVELY;
+	}
+
+	if (item->has_wildcard && !fnmatch(match, name, 0))
+		return MATCHED_FNMATCH;
+
+	return 0;
+}
+
+/*
+ * Given a name and a list of pathspecs, see if the name matches
+ * any of the pathspecs.  The caller is also interested in seeing
+ * all pathspec matches some names it calls this function with
+ * (otherwise the user could have mistyped the unmatched pathspec),
+ * and a mark is left in seen[] array for pathspec element that
+ * actually matched anything.
+ */
+int match_pathspec_depth(const struct pathspec *ps,
+			 const char *name, int namelen,
+			 int prefix, char *seen)
+{
+	int i, retval = 0;
+
+	if (!ps->nr) {
+		if (!ps->recursive || ps->max_depth == -1)
+			return MATCHED_RECURSIVELY;
+
+		if (within_depth(name, namelen, 0, ps->max_depth))
+			return MATCHED_EXACTLY;
+		else
+			return 0;
+	}
+
+	name += prefix;
+	namelen -= prefix;
+
+	for (i = ps->nr - 1; i >= 0; i--) {
+		int how;
+		if (seen && seen[i] == MATCHED_EXACTLY)
+			continue;
+		how = match_pathspec_item(ps->items+i, prefix, name, namelen);
+		if (ps->recursive && ps->max_depth != -1 &&
+		    how && how != MATCHED_FNMATCH) {
+			int len = ps->items[i].len;
+			if (name[len] == '/')
+				len++;
+			if (within_depth(name+len, namelen-len, 0, ps->max_depth))
+				how = MATCHED_EXACTLY;
+			else
+				how = 0;
+		}
+		if (how) {
+			if (retval < how)
+				retval = how;
+			if (seen && seen[i] < how)
+				seen[i] = how;
+		}
+	}
+	return retval;
+}
+
 static int no_wildcard(const char *string)
 {
 	return string[strcspn(string, "*?[{\\")] == '\0';
diff --git a/dir.h b/dir.h
index c71de08..ddb4147 100644
--- a/dir.h
+++ b/dir.h
@@ -65,6 +65,9 @@ struct dir_struct {
 #define MATCHED_FNMATCH 2
 #define MATCHED_EXACTLY 3
 extern int match_pathspec(const char **pathspec, const char *name, int namelen, int prefix, char *seen);
+extern int match_pathspec_depth(const struct pathspec *pathspec,
+				const char *name, int namelen,
+				int prefix, char *seen);
 extern int within_depth(const char *name, int namelen, int depth, int max_depth);
 
 extern int fill_directory(struct dir_struct *dir, const char **pathspec);
-- 
1.7.3.3.476.g10a82

[PATCH 14/21] Convert ce_path_match() to use struct pathspec

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/update-index.c |    8 ++++++--
 cache.h                |    2 +-
 diff-lib.c             |   10 ++++++++--
 preload-index.c        |    5 ++++-
 read-cache.c           |    7 ++++---
 revision.c             |    5 ++++-
 wt-status.c            |    5 ++++-
 7 files changed, 31 insertions(+), 11 deletions(-)

diff --git a/builtin/update-index.c b/builtin/update-index.c
index 3ab214d..9d1f67e 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -543,7 +543,10 @@ static int do_reupdate(int ac, const char **av,
 	 */
 	int pos;
 	int has_head = 1;
-	const char **pathspec = get_pathspec(prefix, av + 1);
+	const char **paths = get_pathspec(prefix, av + 1);
+	struct pathspec pathspec;
+
+	init_pathspec(&pathspec, paths);
 
 	if (read_ref("HEAD", head_sha1))
 		/* If there is no HEAD, that means it is an initial
@@ -556,7 +559,7 @@ static int do_reupdate(int ac, const char **av,
 		struct cache_entry *old = NULL;
 		int save_nr;
 
-		if (ce_stage(ce) || !ce_path_match(ce, pathspec))
+		if (ce_stage(ce) || !ce_path_match(ce, &pathspec))
 			continue;
 		if (has_head)
 			old = read_one_ent(NULL, head_sha1,
@@ -575,6 +578,7 @@ static int do_reupdate(int ac, const char **av,
 		if (save_nr != active_nr)
 			goto redo;
 	}
+	free_pathspec(&pathspec);
 	return 0;
 }
 
diff --git a/cache.h b/cache.h
index dc0bfb4..b5cd61c 100644
--- a/cache.h
+++ b/cache.h
@@ -508,7 +508,7 @@ struct pathspec {
 
 extern int init_pathspec(struct pathspec *, const char **);
 extern void free_pathspec(struct pathspec *);
-extern int ce_path_match(const struct cache_entry *ce, const char **pathspec);
+extern int ce_path_match(const struct cache_entry *ce, const struct pathspec *pathspec);
 extern int index_fd(unsigned char *sha1, int fd, struct stat *st, int write_object, enum object_type type, const char *path);
 extern int index_path(unsigned char *sha1, const char *path, struct stat *st, int write_object);
 extern void fill_stat_cache_info(struct cache_entry *ce, struct stat *st);
diff --git a/diff-lib.c b/diff-lib.c
index 3b809f2..63db7f4 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -89,9 +89,11 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 	int silent_on_removed = option & DIFF_SILENT_ON_REMOVED;
 	unsigned ce_option = ((option & DIFF_RACY_IS_MODIFIED)
 			      ? CE_MATCH_RACY_IS_DIRTY : 0);
+	struct pathspec pathspec;
 
 	diff_set_mnemonic_prefix(&revs->diffopt, "i/", "w/");
 
+	init_pathspec(&pathspec, revs->prune_data);
 	if (diff_unmerged_stage < 0)
 		diff_unmerged_stage = 2;
 	entries = active_nr;
@@ -106,7 +108,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			DIFF_OPT_TST(&revs->diffopt, HAS_CHANGES))
 			break;
 
-		if (!ce_path_match(ce, revs->prune_data))
+		if (!ce_path_match(ce, &pathspec))
 			continue;
 
 		if (ce_stage(ce)) {
@@ -218,6 +220,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			    ce->name, 0, dirty_submodule);
 
 	}
+	free_pathspec(&pathspec);
 	diffcore_std(&revs->diffopt);
 	diff_flush(&revs->diffopt);
 	return 0;
@@ -417,6 +420,7 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)
 	struct cache_entry *idx = src[0];
 	struct cache_entry *tree = src[1];
 	struct rev_info *revs = o->unpack_data;
+	struct pathspec pathspec;
 
 	/*
 	 * Unpack-trees generates a DF/conflict entry if
@@ -427,8 +431,10 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)
 	if (tree == o->df_conflict_entry)
 		tree = NULL;
 
-	if (ce_path_match(idx ? idx : tree, revs->prune_data))
+	init_pathspec(&pathspec, revs->prune_data);
+	if (ce_path_match(idx ? idx : tree, &pathspec))
 		do_oneway_diff(o, idx, tree);
+	free_pathspec(&pathspec);
 
 	return 0;
 }
diff --git a/preload-index.c b/preload-index.c
index e3d0bda..49cb08d 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -35,7 +35,9 @@ static void *preload_thread(void *_data)
 	struct index_state *index = p->index;
 	struct cache_entry **cep = index->cache + p->offset;
 	struct cache_def cache;
+	struct pathspec pathspec;
 
+	init_pathspec(&pathspec, p->pathspec);
 	memset(&cache, 0, sizeof(cache));
 	nr = p->nr;
 	if (nr + p->offset > index->cache_nr)
@@ -51,7 +53,7 @@ static void *preload_thread(void *_data)
 			continue;
 		if (ce_uptodate(ce))
 			continue;
-		if (!ce_path_match(ce, p->pathspec))
+		if (!ce_path_match(ce, &pathspec))
 			continue;
 		if (threaded_has_symlink_leading_path(&cache, ce->name, ce_namelen(ce)))
 			continue;
@@ -61,6 +63,7 @@ static void *preload_thread(void *_data)
 			continue;
 		ce_mark_uptodate(ce);
 	} while (--nr > 0);
+	free_pathspec(&pathspec);
 	return NULL;
 }
 
diff --git a/read-cache.c b/read-cache.c
index 1f42473..f1141a3 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -683,17 +683,18 @@ int ce_same_name(struct cache_entry *a, struct cache_entry *b)
 	return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
 }
 
-int ce_path_match(const struct cache_entry *ce, const char **pathspec)
+int ce_path_match(const struct cache_entry *ce, const struct pathspec *pathspec)
 {
 	const char *match, *name;
+	const char **ps = pathspec->raw;
 	int len;
 
-	if (!pathspec)
+	if (!pathspec->nr)
 		return 1;
 
 	len = ce_namelen(ce);
 	name = ce->name;
-	while ((match = *pathspec++) != NULL) {
+	while ((match = *ps++) != NULL) {
 		int matchlen = strlen(match);
 		if (matchlen > len)
 			continue;
diff --git a/revision.c b/revision.c
index b2a5867..e77184a 100644
--- a/revision.c
+++ b/revision.c
@@ -951,6 +951,7 @@ static void prepare_show_merge(struct rev_info *revs)
 	unsigned char sha1[20];
 	const char **prune = NULL;
 	int i, prune_num = 1; /* counting terminating NULL */
+	struct pathspec pathspec;
 
 	if (get_sha1("HEAD", sha1) || !(head = lookup_commit(sha1)))
 		die("--merge without HEAD?");
@@ -965,11 +966,12 @@ static void prepare_show_merge(struct rev_info *revs)
 
 	if (!active_nr)
 		read_cache();
+	init_pathspec(&pathspec, revs->prune_data);
 	for (i = 0; i < active_nr; i++) {
 		struct cache_entry *ce = active_cache[i];
 		if (!ce_stage(ce))
 			continue;
-		if (ce_path_match(ce, revs->prune_data)) {
+		if (ce_path_match(ce, &pathspec)) {
 			prune_num++;
 			prune = xrealloc(prune, sizeof(*prune) * prune_num);
 			prune[prune_num-2] = ce->name;
@@ -979,6 +981,7 @@ static void prepare_show_merge(struct rev_info *revs)
 		       ce_same_name(ce, active_cache[i+1]))
 			i++;
 	}
+	free_pathspec(&pathspec);
 	revs->prune_data = prune;
 	revs->limited = 1;
 }
diff --git a/wt-status.c b/wt-status.c
index 54b6b03..70bd378 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -350,14 +350,16 @@ static void wt_status_collect_changes_index(struct wt_status *s)
 
 static void wt_status_collect_changes_initial(struct wt_status *s)
 {
+	struct pathspec pathspec;
 	int i;
 
+	init_pathspec(&pathspec, s->pathspec);
 	for (i = 0; i < active_nr; i++) {
 		struct string_list_item *it;
 		struct wt_status_change_data *d;
 		struct cache_entry *ce = active_cache[i];
 
-		if (!ce_path_match(ce, s->pathspec))
+		if (!ce_path_match(ce, &pathspec))
 			continue;
 		it = string_list_insert(&s->change, ce->name);
 		d = it->util;
@@ -372,6 +374,7 @@ static void wt_status_collect_changes_initial(struct wt_status *s)
 		else
 			d->index_status = DIFF_STATUS_ADDED;
 	}
+	free_pathspec(&pathspec);
 }
 
 static void wt_status_collect_untracked(struct wt_status *s)
-- 
1.7.3.3.476.g10a82

[PATCH 15/21] Convert ce_path_match() to use match_pathspec_depth()

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

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

diff --git a/read-cache.c b/read-cache.c
index f1141a3..7f51cd6 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -685,29 +685,7 @@ int ce_same_name(struct cache_entry *a, struct cache_entry *b)
 
 int ce_path_match(const struct cache_entry *ce, const struct pathspec *pathspec)
 {
-	const char *match, *name;
-	const char **ps = pathspec->raw;
-	int len;
-
-	if (!pathspec->nr)
-		return 1;
-
-	len = ce_namelen(ce);
-	name = ce->name;
-	while ((match = *ps++) != NULL) {
-		int matchlen = strlen(match);
-		if (matchlen > len)
-			continue;
-		if (memcmp(name, match, matchlen))
-			continue;
-		if (matchlen && name[matchlen-1] == '/')
-			return 1;
-		if (name[matchlen] == '/' || !name[matchlen])
-			return 1;
-		if (!matchlen)
-			return 1;
-	}
-	return 0;
+	return match_pathspec_depth(pathspec, ce->name, ce_namelen(ce), 0, NULL);
 }
 
 /*
-- 
1.7.3.3.476.g10a82

[PATCH 16/21] grep: convert to use struct pathspec

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

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

diff --git a/builtin/grep.c b/builtin/grep.c
index da32f3d..4179af8 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -585,7 +585,7 @@ static void run_pager(struct grep_opt *opt, const char *prefix)
 	free(argv);
 }
 
-static int grep_cache(struct grep_opt *opt, const char **paths, int cached)
+static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int cached)
 {
 	int hit = 0;
 	int nr;
@@ -595,7 +595,7 @@ static int grep_cache(struct grep_opt *opt, const char **paths, int cached)
 		struct cache_entry *ce = active_cache[nr];
 		if (!S_ISREG(ce->ce_mode))
 			continue;
-		if (!pathspec_matches(paths, ce->name, opt->max_depth))
+		if (!pathspec_matches(pathspec->raw, ce->name, opt->max_depth))
 			continue;
 		/*
 		 * If CE_VALID is on, we assume worktree file and its cache entry
@@ -622,7 +622,7 @@ static int grep_cache(struct grep_opt *opt, const char **paths, int cached)
 	return hit;
 }
 
-static int grep_tree(struct grep_opt *opt, const char **paths,
+static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 		     struct tree_desc *tree,
 		     const char *tree_name, const char *base)
 {
@@ -656,7 +656,7 @@ static int grep_tree(struct grep_opt *opt, const char **paths,
 			strbuf_addch(&pathbuf, '/');
 
 		down = pathbuf.buf + tn_len;
-		if (!pathspec_matches(paths, down, opt->max_depth))
+		if (!pathspec_matches(pathspec->raw, down, opt->max_depth))
 			;
 		else if (S_ISREG(entry.mode))
 			hit |= grep_sha1(opt, entry.sha1, pathbuf.buf, tn_len);
@@ -671,7 +671,7 @@ static int grep_tree(struct grep_opt *opt, const char **paths,
 				die("unable to read tree (%s)",
 				    sha1_to_hex(entry.sha1));
 			init_tree_desc(&sub, data, size);
-			hit |= grep_tree(opt, paths, &sub, tree_name, down);
+			hit |= grep_tree(opt, pathspec, &sub, tree_name, down);
 			free(data);
 		}
 		if (hit && opt->status_only)
@@ -681,7 +681,7 @@ static int grep_tree(struct grep_opt *opt, const char **paths,
 	return hit;
 }
 
-static int grep_object(struct grep_opt *opt, const char **paths,
+static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,
 		       struct object *obj, const char *name)
 {
 	if (obj->type == OBJ_BLOB)
@@ -696,14 +696,14 @@ static int grep_object(struct grep_opt *opt, const char **paths,
 		if (!data)
 			die("unable to read tree (%s)", sha1_to_hex(obj->sha1));
 		init_tree_desc(&tree, data, size);
-		hit = grep_tree(opt, paths, &tree, name, "");
+		hit = grep_tree(opt, pathspec, &tree, name, "");
 		free(data);
 		return hit;
 	}
 	die("unable to grep from object of type %s", typename(obj->type));
 }
 
-static int grep_objects(struct grep_opt *opt, const char **paths,
+static int grep_objects(struct grep_opt *opt, const struct pathspec *pathspec,
 			const struct object_array *list)
 {
 	unsigned int i;
@@ -713,7 +713,7 @@ static int grep_objects(struct grep_opt *opt, const char **paths,
 	for (i = 0; i < nr; i++) {
 		struct object *real_obj;
 		real_obj = deref_tag(list->objects[i].item, NULL, 0);
-		if (grep_object(opt, paths, real_obj, list->objects[i].name)) {
+		if (grep_object(opt, pathspec, real_obj, list->objects[i].name)) {
 			hit = 1;
 			if (opt->status_only)
 				break;
@@ -722,7 +722,7 @@ static int grep_objects(struct grep_opt *opt, const char **paths,
 	return hit;
 }
 
-static int grep_directory(struct grep_opt *opt, const char **paths)
+static int grep_directory(struct grep_opt *opt, const struct pathspec *pathspec)
 {
 	struct dir_struct dir;
 	int i, hit = 0;
@@ -730,7 +730,7 @@ static int grep_directory(struct grep_opt *opt, const char **paths)
 	memset(&dir, 0, sizeof(dir));
 	setup_standard_excludes(&dir);
 
-	fill_directory(&dir, paths);
+	fill_directory(&dir, pathspec->raw);
 	for (i = 0; i < dir.nr; i++) {
 		hit |= grep_file(opt, dir.entries[i]->name);
 		if (hit && opt->status_only)
@@ -836,6 +836,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 	struct grep_opt opt;
 	struct object_array list = OBJECT_ARRAY_INIT;
 	const char **paths = NULL;
+	struct pathspec pathspec;
 	struct string_list path_list = STRING_LIST_INIT_NODUP;
 	int i;
 	int dummy;
@@ -1063,6 +1064,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 		paths[0] = prefix;
 		paths[1] = NULL;
 	}
+	init_pathspec(&pathspec, paths);
 
 	if (show_in_pager && (cached || list.nr))
 		die("--open-files-in-pager only works on the worktree");
@@ -1093,16 +1095,16 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 			die("--cached cannot be used with --no-index.");
 		if (list.nr)
 			die("--no-index cannot be used with revs.");
-		hit = grep_directory(&opt, paths);
+		hit = grep_directory(&opt, &pathspec);
 	} else if (!list.nr) {
 		if (!cached)
 			setup_work_tree();
 
-		hit = grep_cache(&opt, paths, cached);
+		hit = grep_cache(&opt, &pathspec, cached);
 	} else {
 		if (cached)
 			die("both --cached and trees are given.");
-		hit = grep_objects(&opt, paths, &list);
+		hit = grep_objects(&opt, &pathspec, &list);
 	}
 
 	if (use_threads)
-- 
1.7.3.3.476.g10a82

[PATCH 17/21] grep: use match_pathspec_depth() for cache/worktree grepping

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

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

diff --git a/builtin/grep.c b/builtin/grep.c
index 4179af8..fbc7d02 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -595,7 +595,7 @@ static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int
 		struct cache_entry *ce = active_cache[nr];
 		if (!S_ISREG(ce->ce_mode))
 			continue;
-		if (!pathspec_matches(pathspec->raw, ce->name, opt->max_depth))
+		if (!match_pathspec_depth(pathspec, ce->name, ce_namelen(ce), 0, NULL))
 			continue;
 		/*
 		 * If CE_VALID is on, we assume worktree file and its cache entry
-- 
1.7.3.3.476.g10a82

[PATCH 18/21] strbuf: allow "buf" to point to the middle of the allocated buffer

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

This allows offseting buf forward by neglen bytes. This patch makes
sure that reallocation works even when buf is not at the top of
allocated region.

Many functions are not aware that there could be data before buf. Use
with care.

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

diff --git a/strbuf.c b/strbuf.c
index bc3a080..12cda6f 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -28,8 +28,10 @@ char strbuf_slopbuf[1];
 
 void strbuf_init(struct strbuf *sb, size_t hint)
 {
-	sb->alloc = sb->len = 0;
-	sb->buf = strbuf_slopbuf;
+	sb->alloc  = 0;
+	sb->len	   = 0;
+	sb->neglen = 0;
+	sb->buf	   = strbuf_slopbuf;
 	if (hint)
 		strbuf_grow(sb, hint);
 }
@@ -37,7 +39,7 @@ void strbuf_init(struct strbuf *sb, size_t hint)
 void strbuf_release(struct strbuf *sb)
 {
 	if (sb->alloc) {
-		free(sb->buf);
+		free(sb->buf - sb->neglen);
 		strbuf_init(sb, 0);
 	}
 }
@@ -45,6 +47,8 @@ void strbuf_release(struct strbuf *sb)
 char *strbuf_detach(struct strbuf *sb, size_t *sz)
 {
 	char *res = sb->alloc ? sb->buf : NULL;
+	if (sb->neglen)
+		die("shift buf back before detaching");
 	if (sz)
 		*sz = sb->len;
 	strbuf_init(sb, 0);
@@ -54,20 +58,23 @@ char *strbuf_detach(struct strbuf *sb, size_t *sz)
 void strbuf_attach(struct strbuf *sb, void *buf, size_t len, size_t alloc)
 {
 	strbuf_release(sb);
-	sb->buf   = buf;
-	sb->len   = len;
-	sb->alloc = alloc;
+	sb->buf    = buf;
+	sb->len    = len;
+	sb->neglen = 0;
+	sb->alloc  = alloc;
 	strbuf_grow(sb, 0);
 	sb->buf[sb->len] = '\0';
 }
 
 void strbuf_grow(struct strbuf *sb, size_t extra)
 {
-	if (sb->len + extra + 1 <= sb->len)
+	char *buf = !sb->alloc ? NULL : sb->buf - sb->neglen;
+	int len = sb->neglen + sb->len;
+
+	if (len + extra + 1 <= len)
 		die("you want to use way too much memory");
-	if (!sb->alloc)
-		sb->buf = NULL;
-	ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
+	ALLOC_GROW(buf, len + extra + 1, sb->alloc);
+	sb->buf = buf + sb->neglen;
 }
 
 void strbuf_trim(struct strbuf *sb)
@@ -402,3 +409,12 @@ int strbuf_check_branch_ref(struct strbuf *sb, const char *name)
 	strbuf_splice(sb, 0, 0, "refs/heads/", 11);
 	return check_ref_format(sb->buf);
 }
+
+void strbuf_offset(struct strbuf *sb, int offset)
+{
+	if (offset > sb->len || offset < sb->neglen)
+		die("you cannot offset out of allocated buffer");
+	sb->buf	   += offset;
+	sb->neglen += offset;
+	sb->len	   -= offset;
+}
diff --git a/strbuf.h b/strbuf.h
index fac2dbc..3c3b146 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -43,11 +43,11 @@
 extern char strbuf_slopbuf[];
 struct strbuf {
 	size_t alloc;
-	size_t len;
+	size_t len, neglen;
 	char *buf;
 };
 
-#define STRBUF_INIT  { 0, 0, strbuf_slopbuf }
+#define STRBUF_INIT  { 0, 0, 0, strbuf_slopbuf }
 
 /*----- strbuf life cycle -----*/
 extern void strbuf_init(struct strbuf *, size_t);
@@ -62,7 +62,7 @@ static inline void strbuf_swap(struct strbuf *a, struct strbuf *b) {
 
 /*----- strbuf size related -----*/
 static inline size_t strbuf_avail(const struct strbuf *sb) {
-	return sb->alloc ? sb->alloc - sb->len - 1 : 0;
+	return sb->alloc ? sb->alloc - sb->len - sb->neglen - 1 : 0;
 }
 
 extern void strbuf_grow(struct strbuf *, size_t);
@@ -70,7 +70,7 @@ extern void strbuf_grow(struct strbuf *, size_t);
 static inline void strbuf_setlen(struct strbuf *sb, size_t len) {
 	if (!sb->alloc)
 		strbuf_grow(sb, 0);
-	assert(len < sb->alloc);
+	assert(sb->neglen + len < sb->alloc);
 	sb->len = len;
 	sb->buf[len] = '\0';
 }
@@ -136,4 +136,6 @@ extern int launch_editor(const char *path, struct strbuf *buffer, const char *co
 extern int strbuf_branchname(struct strbuf *sb, const char *name);
 extern int strbuf_check_branch_ref(struct strbuf *sb, const char *name);
 
+extern void strbuf_offset(struct strbuf *sb, int offset);
+
 #endif /* STRBUF_H */
-- 
1.7.3.3.476.g10a82

[PATCH 19/21] grep: use writable strbuf from caller in grep_tree()

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

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

diff --git a/builtin/grep.c b/builtin/grep.c
index fbc7d02..5ecbbf8 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -623,43 +623,29 @@ static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int
 }
 
 static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
-		     struct tree_desc *tree,
-		     const char *tree_name, const char *base)
+		     struct tree_desc *tree, struct strbuf *base, int tn_len)
 {
-	int len;
 	int hit = 0;
 	struct name_entry entry;
-	char *down;
-	int tn_len = strlen(tree_name);
-	struct strbuf pathbuf;
-
-	strbuf_init(&pathbuf, PATH_MAX + tn_len);
-
-	if (tn_len) {
-		strbuf_add(&pathbuf, tree_name, tn_len);
-		strbuf_addch(&pathbuf, ':');
-		tn_len = pathbuf.len;
-	}
-	strbuf_addstr(&pathbuf, base);
-	len = pathbuf.len;
+	int old_baselen = base->len;
 
 	while (tree_entry(tree, &entry)) {
 		int te_len = tree_entry_len(entry.path, entry.sha1);
-		pathbuf.len = len;
-		strbuf_add(&pathbuf, entry.path, te_len);
+
+		strbuf_add(base, entry.path, te_len);
 
 		if (S_ISDIR(entry.mode))
 			/* Match "abc/" against pathspec to
 			 * decide if we want to descend into "abc"
 			 * directory.
 			 */
-			strbuf_addch(&pathbuf, '/');
+			strbuf_addch(base, '/');
 
-		down = pathbuf.buf + tn_len;
-		if (!pathspec_matches(pathspec->raw, down, opt->max_depth))
+		if (!pathspec_matches(pathspec->raw, base->buf, opt->max_depth))
 			;
-		else if (S_ISREG(entry.mode))
-			hit |= grep_sha1(opt, entry.sha1, pathbuf.buf, tn_len);
+		else if (S_ISREG(entry.mode)) {
+			hit |= grep_sha1(opt, entry.sha1, base->buf - tn_len, tn_len);
+		}
 		else if (S_ISDIR(entry.mode)) {
 			enum object_type type;
 			struct tree_desc sub;
@@ -671,13 +657,14 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 				die("unable to read tree (%s)",
 				    sha1_to_hex(entry.sha1));
 			init_tree_desc(&sub, data, size);
-			hit |= grep_tree(opt, pathspec, &sub, tree_name, down);
+			hit |= grep_tree(opt, pathspec, &sub, base, tn_len);
 			free(data);
 		}
+		strbuf_setlen(base, old_baselen);
+
 		if (hit && opt->status_only)
 			break;
 	}
-	strbuf_release(&pathbuf);
 	return hit;
 }
 
@@ -690,13 +677,24 @@ static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,
 		struct tree_desc tree;
 		void *data;
 		unsigned long size;
-		int hit;
+		struct strbuf base;
+		int hit, len;
+
 		data = read_object_with_reference(obj->sha1, tree_type,
 						  &size, NULL);
 		if (!data)
 			die("unable to read tree (%s)", sha1_to_hex(obj->sha1));
+
+		len = name ? strlen(name) : 0;
+		strbuf_init(&base, PATH_MAX + len + 1);
+		if (len) {
+			strbuf_add(&base, name, len);
+			strbuf_addch(&base, ':');
+			strbuf_offset(&base, base.len);
+		}
 		init_tree_desc(&tree, data, size);
-		hit = grep_tree(opt, pathspec, &tree, name, "");
+		hit = grep_tree(opt, pathspec, &tree, &base, base.neglen);
+		strbuf_release(&base);
 		free(data);
 		return hit;
 	}
-- 
1.7.3.3.476.g10a82

[PATCH 20/21] grep: drop pathspec_matches() in favor of tree_entry_interesting()

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

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

diff --git a/builtin/grep.c b/builtin/grep.c
index 5ecbbf8..3cd66b1 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -333,106 +333,6 @@ static int grep_config(const char *var, const char *value, void *cb)
 	return 0;
 }
 
-/*
- * Return non-zero if max_depth is negative or path has no more then max_depth
- * slashes.
- */
-static int accept_subdir(const char *path, int max_depth)
-{
-	if (max_depth < 0)
-		return 1;
-
-	while ((path = strchr(path, '/')) != NULL) {
-		max_depth--;
-		if (max_depth < 0)
-			return 0;
-		path++;
-	}
-	return 1;
-}
-
-/*
- * Return non-zero if name is a subdirectory of match and is not too deep.
- */
-static int is_subdir(const char *name, int namelen,
-		const char *match, int matchlen, int max_depth)
-{
-	if (matchlen > namelen || strncmp(name, match, matchlen))
-		return 0;
-
-	if (name[matchlen] == '\0') /* exact match */
-		return 1;
-
-	if (!matchlen || match[matchlen-1] == '/' || name[matchlen] == '/')
-		return accept_subdir(name + matchlen + 1, max_depth);
-
-	return 0;
-}
-
-/*
- * git grep pathspecs are somewhat different from diff-tree pathspecs;
- * pathname wildcards are allowed.
- */
-static int pathspec_matches(const char **paths, const char *name, int max_depth)
-{
-	int namelen, i;
-	if (!paths || !*paths)
-		return accept_subdir(name, max_depth);
-	namelen = strlen(name);
-	for (i = 0; paths[i]; i++) {
-		const char *match = paths[i];
-		int matchlen = strlen(match);
-		const char *cp, *meta;
-
-		if (is_subdir(name, namelen, match, matchlen, max_depth))
-			return 1;
-		if (!fnmatch(match, name, 0))
-			return 1;
-		if (name[namelen-1] != '/')
-			continue;
-
-		/* We are being asked if the directory ("name") is worth
-		 * descending into.
-		 *
-		 * Find the longest leading directory name that does
-		 * not have metacharacter in the pathspec; the name
-		 * we are looking at must overlap with that directory.
-		 */
-		for (cp = match, meta = NULL; cp - match < matchlen; cp++) {
-			char ch = *cp;
-			if (ch == '*' || ch == '[' || ch == '?') {
-				meta = cp;
-				break;
-			}
-		}
-		if (!meta)
-			meta = cp; /* fully literal */
-
-		if (namelen <= meta - match) {
-			/* Looking at "Documentation/" and
-			 * the pattern says "Documentation/howto/", or
-			 * "Documentation/diff*.txt".  The name we
-			 * have should match prefix.
-			 */
-			if (!memcmp(match, name, namelen))
-				return 1;
-			continue;
-		}
-
-		if (meta - match < namelen) {
-			/* Looking at "Documentation/howto/" and
-			 * the pattern says "Documentation/h*";
-			 * match up to "Do.../h"; this avoids descending
-			 * into "Documentation/technical/".
-			 */
-			if (!memcmp(match, name, meta - match))
-				return 1;
-			continue;
-		}
-	}
-	return 0;
-}
-
 static void *lock_and_read_sha1_file(const unsigned char *sha1, enum object_type *type, unsigned long *size)
 {
 	void *data;
@@ -625,25 +525,24 @@ static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int
 static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 		     struct tree_desc *tree, struct strbuf *base, int tn_len)
 {
-	int hit = 0;
+	int hit = 0, matched = 0;
 	struct name_entry entry;
 	int old_baselen = base->len;
 
 	while (tree_entry(tree, &entry)) {
 		int te_len = tree_entry_len(entry.path, entry.sha1);
 
-		strbuf_add(base, entry.path, te_len);
+		if (matched != 2) {
+			matched = tree_entry_interesting(&entry, base, pathspec);
+			if (matched == -1)
+				break; /* no more matches */
+			if (!matched)
+				continue;
+		}
 
-		if (S_ISDIR(entry.mode))
-			/* Match "abc/" against pathspec to
-			 * decide if we want to descend into "abc"
-			 * directory.
-			 */
-			strbuf_addch(base, '/');
+		strbuf_add(base, entry.path, te_len);
 
-		if (!pathspec_matches(pathspec->raw, base->buf, opt->max_depth))
-			;
-		else if (S_ISREG(entry.mode)) {
+		if (S_ISREG(entry.mode)) {
 			hit |= grep_sha1(opt, entry.sha1, base->buf - tn_len, tn_len);
 		}
 		else if (S_ISDIR(entry.mode)) {
@@ -656,6 +555,8 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 			if (!data)
 				die("unable to read tree (%s)",
 				    sha1_to_hex(entry.sha1));
+
+			strbuf_addch(base, '/');
 			init_tree_desc(&sub, data, size);
 			hit |= grep_tree(opt, pathspec, &sub, base, tn_len);
 			free(data);
@@ -1063,6 +964,8 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 		paths[1] = NULL;
 	}
 	init_pathspec(&pathspec, paths);
+	pathspec.max_depth = opt.max_depth;
+	pathspec.recursive = 1;
 
 	if (show_in_pager && (cached || list.nr))
 		die("--open-files-in-pager only works on the worktree");
-- 
1.7.3.3.476.g10a82

[PATCH 21/21] t7810: overlapping pathspecs and depth limit

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

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

diff --git a/t/t7810-grep.sh b/t/t7810-grep.sh
index 023f225..d89faee 100755
--- a/t/t7810-grep.sh
+++ b/t/t7810-grep.sh
@@ -182,6 +182,24 @@ do
 		test_cmp expected actual
 	'
 
+	test_expect_success "grep --max-depth 0 -- . t $L" '
+		{
+			echo ${HC}t/v:1:vvv
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth 0 -n -e vvv $H -- . t >actual &&
+		test_cmp expected actual
+	'
+
+	test_expect_success "grep --max-depth 0 -- t . $L" '
+		{
+			echo ${HC}t/v:1:vvv
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth 0 -n -e vvv $H -- t . >actual &&
+		test_cmp expected actual
+	'
+
 done
 
 cat >expected <<EOF
-- 
1.7.3.3.476.g10a82

Re: [PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

[Junio C Hamano]

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

> Suppose we have two pathspecs 'a' and 'a/b' (both are dirs) and depth
> limit 1. In current code, pathspecs are checked in input order. When
> 'a/b' is checked against pathspec 'a', it fails depth limit and
> therefore is excluded, although it should match 'a/b' pathspec.
>
> This patch reorders all pathspecs alphabetically, then teaches
> tree_entry_interesting() to check against the deepest pathspec first,
> so depth limit of a shallower pathspec won't affect a deeper one.

I am quite happy to see where this new round of this series is going so
far.  I however doubt this patch is a right approach for the problem you
are solving, especially because your longer-term (i.e. toward the rest of
the series to patch 21) plan is to allow wildcards [*1*].

One thing I am not clear is what it means to limit the recursion level
when you have wildcards.

One possible definition of interaction between limit and wildcard may be
to count the number of slashes in the part of the path that matches the
wildcarded part of the pathspec, add the number of path components
appended due to the leading directory match, and then subtract the number
of literal slashes in the wildcarded part of the pattern from the above,
and declare that a match is found if the difference is less than the
limit.

E.g. a pathspec element "a/*/x" would match "a/b/c/x", "a/b/c/d/e/x",
"a/b/x/y" and "a/b/x/y/z" without limit, and with the limit of 1:

    a/b/c/x        matches ('*' expands to "b/c")
    a/b/c/d/e/x    no ('*' has to expand to "c/d/e" and needs 2 levels)
    a/b/x/y        matches ('*' expands to "b" costing zero, "/y" needs 1)
    a/b/x/y/z      does not match

Another definition could be to count _only_ the part that is appended by
recursion (i.e. we do not count how many slashes has to match '*' in the
above examples), and as the option is called --depth, it might make more
sense.

In either case, I am not sure if "if it matches the longest pathspec, we
have the answer without looking at shorter ones" would be a good rule to
use.


[Footnote]

*1* In addition, perhaps you may later want to introduce some "negative"
match operators to pathspecs; while I am not particularly fond of that
direction at this moment, I would like to leave the door open for that
possibility, in case it turns out to be a good thing to have.

Re: [PATCH 14/21] Convert ce_path_match() to use struct pathspec

[Junio C Hamano]

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

> diff --git a/diff-lib.c b/diff-lib.c
> index 3b809f2..63db7f4 100644
> --- a/diff-lib.c
> +++ b/diff-lib.c
> @@ -89,9 +89,11 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
>  	int silent_on_removed = option & DIFF_SILENT_ON_REMOVED;
>  	unsigned ce_option = ((option & DIFF_RACY_IS_MODIFIED)
>  			      ? CE_MATCH_RACY_IS_DIRTY : 0);
> +	struct pathspec pathspec;
>  
>  	diff_set_mnemonic_prefix(&revs->diffopt, "i/", "w/");
>  
> +	init_pathspec(&pathspec, revs->prune_data);

I wonder if it makes more sense to change the type of revs->prune_data
from an array of pointers to strings to a pointer to struct pathspec.
Is there a downside?

> diff --git a/preload-index.c b/preload-index.c
> index e3d0bda..49cb08d 100644
> --- a/preload-index.c
> +++ b/preload-index.c
> @@ -35,7 +35,9 @@ static void *preload_thread(void *_data)
>  	struct index_state *index = p->index;
>  	struct cache_entry **cep = index->cache + p->offset;
>  	struct cache_def cache;
> +	struct pathspec pathspec;
>  
> +	init_pathspec(&pathspec, p->pathspec);

Likewise; would it make the API cleaner to make read_cache_preload() and
read_index_preload() take "const struct pathspec *" instead of the
traditional "const char **"?

Re: [PATCH 19/21] grep: use writable strbuf from caller in grep_tree()

[Junio C Hamano]

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

> +		hit = grep_tree(opt, pathspec, &tree, &base, base.neglen);

If you are going to let the users of strbuf API to refer directly to the
field, I think "neglen" should be renamed to something more reasonable,
say, "offset".

I am still debating myself if this strbuf_offset is anugly hack merely to
allow the implementation of "grep" not to carry one extra offset around
throughout its callchain, or if it is generic enough that other/future
callers would benefit from.  I am leaning toward to think this is an ugly
hack, as a new caller that wants to carry _two_ offsets into a strbuf
wouldn't get much benefit from this new API.  But I may be missreading
your code.

Re: [PATCH 19/21] grep: use writable strbuf from caller in grep_tree()

[Nguyen Thai Ngoc Duy]

2010/12/17 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> +             hit = grep_tree(opt, pathspec, &tree, &base, base.neglen);
>
> If you are going to let the users of strbuf API to refer directly to the
> field, I think "neglen" should be renamed to something more reasonable,
> say, "offset".
>
> I am still debating myself if this strbuf_offset is anugly hack merely to
> allow the implementation of "grep" not to carry one extra offset around
> throughout its callchain, or if it is generic enough that other/future
> callers would benefit from.  I am leaning toward to think this is an ugly
> hack, as a new caller that wants to carry _two_ offsets into a strbuf
> wouldn't get much benefit from this new API.  But I may be missreading
> your code.
>

I did not want to another offset to tree_entry_interesting. But an
extra argument would be less ugly than an extra API.
-- 
Duy

Re: [PATCH 14/21] Convert ce_path_match() to use struct pathspec

[Nguyen Thai Ngoc Duy]

2010/12/17 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> diff --git a/diff-lib.c b/diff-lib.c
>> index 3b809f2..63db7f4 100644
>> --- a/diff-lib.c
>> +++ b/diff-lib.c
>> @@ -89,9 +89,11 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
>>       int silent_on_removed = option & DIFF_SILENT_ON_REMOVED;
>>       unsigned ce_option = ((option & DIFF_RACY_IS_MODIFIED)
>>                             ? CE_MATCH_RACY_IS_DIRTY : 0);
>> +     struct pathspec pathspec;
>>
>>       diff_set_mnemonic_prefix(&revs->diffopt, "i/", "w/");
>>
>> +     init_pathspec(&pathspec, revs->prune_data);
>
> I wonder if it makes more sense to change the type of revs->prune_data
> from an array of pointers to strings to a pointer to struct pathspec.
> Is there a downside?

Converting a pointer to another pointer means mis typecasting can
happen and the compiler won't help catching them. I thinking of
changing prune_data to simply struct pathspec. Looks like it breaks
thing.. hm...
-- 
Duy

Re: [PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

[Nguyen Thai Ngoc Duy]

2010/12/17 Junio C Hamano <gitster@pobox.com>:
> One thing I am not clear is what it means to limit the recursion level
> when you have wildcards.

Recursion level does not affect wildcards at all. That was original
design, a91f453 (grep: Add --max-depth option. - 2009-07-22). I think
current git-grep still follows that.

> [Footnote]
>
> *1* In addition, perhaps you may later want to introduce some "negative"
> match operators to pathspecs; while I am not particularly fond of that
> direction at this moment, I would like to leave the door open for that
> possibility, in case it turns out to be a good thing to have.

It's a essential thing for narrow clone, otherwise I can't widen a
narrow clone. But narrow clone must prove it's a good thing to have
first..
-- 
Duy

[PATCH 14/21] struct rev_info: convert prune_data to struct pathspec

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 New patch. rev_info->pathspec is now struct pathspec.

 builtin/add.c         |    2 +-
 builtin/diff.c        |   12 ++++--------
 builtin/fast-export.c |    2 +-
 diff-lib.c            |    6 +++---
 revision.c            |   15 ++++++++-------
 revision.h            |    2 +-
 wt-status.c           |    4 ++--
 7 files changed, 20 insertions(+), 23 deletions(-)

diff --git a/builtin/add.c b/builtin/add.c
index 56a4e0a..3fc79a5 100644
--- a/builtin/add.c
+++ b/builtin/add.c
@@ -86,7 +86,7 @@ int add_files_to_cache(const char *prefix, const char **pathspec, int flags)
 	struct rev_info rev;
 	init_revisions(&rev, prefix);
 	setup_revisions(0, NULL, &rev, NULL);
-	rev.prune_data = pathspec;
+	init_pathspec(&rev.prune_data, pathspec);
 	rev.diffopt.output_format = DIFF_FORMAT_CALLBACK;
 	rev.diffopt.format_callback = update_callback;
 	data.flags = flags;
diff --git a/builtin/diff.c b/builtin/diff.c
index 76c42d8..4ebb1b6 100644
--- a/builtin/diff.c
+++ b/builtin/diff.c
@@ -371,14 +371,10 @@ int cmd_diff(int argc, const char **argv, const char *prefix)
 		}
 		die("unhandled object '%s' given.", name);
 	}
-	if (rev.prune_data) {
-		const char **pathspec = rev.prune_data;
-		while (*pathspec) {
-			if (!path)
-				path = *pathspec;
-			paths++;
-			pathspec++;
-		}
+	if (rev.prune_data.nr) {
+		if (!path)
+			path = rev.prune_data.items[0].match;
+		paths += rev.prune_data.nr;
 	}
 
 	/*
diff --git a/builtin/fast-export.c b/builtin/fast-export.c
index c8fd46b..ba57457 100644
--- a/builtin/fast-export.c
+++ b/builtin/fast-export.c
@@ -651,7 +651,7 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
 	if (import_filename)
 		import_marks(import_filename);
 
-	if (import_filename && revs.prune_data)
+	if (import_filename && revs.prune_data.nr)
 		full_tree = 1;
 
 	get_tags_and_duplicates(&revs.pending, &extra_refs);
diff --git a/diff-lib.c b/diff-lib.c
index 3b809f2..2251f3d 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -106,7 +106,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			DIFF_OPT_TST(&revs->diffopt, HAS_CHANGES))
 			break;
 
-		if (!ce_path_match(ce, revs->prune_data))
+		if (!ce_path_match(ce, revs->prune_data.raw))
 			continue;
 
 		if (ce_stage(ce)) {
@@ -427,7 +427,7 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)
 	if (tree == o->df_conflict_entry)
 		tree = NULL;
 
-	if (ce_path_match(idx ? idx : tree, revs->prune_data))
+	if (ce_path_match(idx ? idx : tree, revs->prune_data.raw))
 		do_oneway_diff(o, idx, tree);
 
 	return 0;
@@ -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->pathspec.raw;
+	init_pathspec(&revs.prune_data, opt->pathspec.raw);
 	tree = parse_tree_indirect(tree_sha1);
 	if (!tree)
 		die("bad tree object %s", sha1_to_hex(tree_sha1));
diff --git a/revision.c b/revision.c
index b2a5867..515e2dd 100644
--- a/revision.c
+++ b/revision.c
@@ -323,7 +323,7 @@ static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct
 		 * tagged commit by specifying both --simplify-by-decoration
 		 * and pathspec.
 		 */
-		if (!revs->prune_data)
+		if (!revs->prune_data.nr)
 			return REV_TREE_SAME;
 	}
 
@@ -969,7 +969,7 @@ static void prepare_show_merge(struct rev_info *revs)
 		struct cache_entry *ce = active_cache[i];
 		if (!ce_stage(ce))
 			continue;
-		if (ce_path_match(ce, revs->prune_data)) {
+		if (ce_path_match(ce, revs->prune_data.raw)) {
 			prune_num++;
 			prune = xrealloc(prune, sizeof(*prune) * prune_num);
 			prune[prune_num-2] = ce->name;
@@ -979,7 +979,8 @@ static void prepare_show_merge(struct rev_info *revs)
 		       ce_same_name(ce, active_cache[i+1]))
 			i++;
 	}
-	revs->prune_data = prune;
+	free_pathspec(&revs->prune_data);
+	init_pathspec(&revs->prune_data, prune);
 	revs->limited = 1;
 }
 
@@ -1616,7 +1617,7 @@ 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);
+		init_pathspec(&revs->prune_data, get_pathspec(revs->prefix, prune_data));
 
 	if (revs->def == NULL)
 		revs->def = opt ? opt->def : NULL;
@@ -1647,13 +1648,13 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 	if (revs->topo_order)
 		revs->limited = 1;
 
-	if (revs->prune_data) {
-		diff_tree_setup_paths(revs->prune_data, &revs->pruning);
+	if (revs->prune_data.nr) {
+		diff_tree_setup_paths(revs->prune_data.raw, &revs->pruning);
 		/* Can't prune commits with rename following: the paths change.. */
 		if (!DIFF_OPT_TST(&revs->diffopt, FOLLOW_RENAMES))
 			revs->prune = 1;
 		if (!revs->full_diff)
-			diff_tree_setup_paths(revs->prune_data, &revs->diffopt);
+			diff_tree_setup_paths(revs->prune_data.raw, &revs->diffopt);
 	}
 	if (revs->combine_merges)
 		revs->ignore_merges = 0;
diff --git a/revision.h b/revision.h
index 05659c6..82509dd 100644
--- a/revision.h
+++ b/revision.h
@@ -34,7 +34,7 @@ struct rev_info {
 	/* Basic information */
 	const char *prefix;
 	const char *def;
-	void *prune_data;
+	struct pathspec prune_data;
 	unsigned int early_output;
 
 	/* Traversal flags */
diff --git a/wt-status.c b/wt-status.c
index 54b6b03..5c6b118 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -319,7 +319,7 @@ static void wt_status_collect_changes_worktree(struct wt_status *s)
     }
 	rev.diffopt.format_callback = wt_status_collect_changed_cb;
 	rev.diffopt.format_callback_data = s;
-	rev.prune_data = s->pathspec;
+	init_pathspec(&rev.prune_data, s->pathspec);
 	run_diff_files(&rev, 0);
 }
 
@@ -344,7 +344,7 @@ static void wt_status_collect_changes_index(struct wt_status *s)
 	rev.diffopt.detect_rename = 1;
 	rev.diffopt.rename_limit = 200;
 	rev.diffopt.break_opt = 0;
-	rev.prune_data = s->pathspec;
+	init_pathspec(&rev.prune_data, s->pathspec);
 	run_diff_index(&rev, 1);
 }
 
-- 
1.7.3.3.476.g10a82

[PATCH 15/21] Convert ce_path_match() to use struct pathspec

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 The old 14/21. Slightly changed because of rev_info->pathspec change.

 builtin/update-index.c |    8 ++++++--
 cache.h                |    2 +-
 diff-lib.c             |    4 ++--
 preload-index.c        |    5 ++++-
 read-cache.c           |    7 ++++---
 revision.c             |    2 +-
 wt-status.c            |    5 ++++-
 7 files changed, 22 insertions(+), 11 deletions(-)

diff --git a/builtin/update-index.c b/builtin/update-index.c
index 3ab214d..9d1f67e 100644
--- a/builtin/update-index.c
+++ b/builtin/update-index.c
@@ -543,7 +543,10 @@ static int do_reupdate(int ac, const char **av,
 	 */
 	int pos;
 	int has_head = 1;
-	const char **pathspec = get_pathspec(prefix, av + 1);
+	const char **paths = get_pathspec(prefix, av + 1);
+	struct pathspec pathspec;
+
+	init_pathspec(&pathspec, paths);
 
 	if (read_ref("HEAD", head_sha1))
 		/* If there is no HEAD, that means it is an initial
@@ -556,7 +559,7 @@ static int do_reupdate(int ac, const char **av,
 		struct cache_entry *old = NULL;
 		int save_nr;
 
-		if (ce_stage(ce) || !ce_path_match(ce, pathspec))
+		if (ce_stage(ce) || !ce_path_match(ce, &pathspec))
 			continue;
 		if (has_head)
 			old = read_one_ent(NULL, head_sha1,
@@ -575,6 +578,7 @@ static int do_reupdate(int ac, const char **av,
 		if (save_nr != active_nr)
 			goto redo;
 	}
+	free_pathspec(&pathspec);
 	return 0;
 }
 
diff --git a/cache.h b/cache.h
index dc0bfb4..b5cd61c 100644
--- a/cache.h
+++ b/cache.h
@@ -508,7 +508,7 @@ struct pathspec {
 
 extern int init_pathspec(struct pathspec *, const char **);
 extern void free_pathspec(struct pathspec *);
-extern int ce_path_match(const struct cache_entry *ce, const char **pathspec);
+extern int ce_path_match(const struct cache_entry *ce, const struct pathspec *pathspec);
 extern int index_fd(unsigned char *sha1, int fd, struct stat *st, int write_object, enum object_type type, const char *path);
 extern int index_path(unsigned char *sha1, const char *path, struct stat *st, int write_object);
 extern void fill_stat_cache_info(struct cache_entry *ce, struct stat *st);
diff --git a/diff-lib.c b/diff-lib.c
index 2251f3d..1e22992 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -106,7 +106,7 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
 			DIFF_OPT_TST(&revs->diffopt, HAS_CHANGES))
 			break;
 
-		if (!ce_path_match(ce, revs->prune_data.raw))
+		if (!ce_path_match(ce, &revs->prune_data))
 			continue;
 
 		if (ce_stage(ce)) {
@@ -427,7 +427,7 @@ static int oneway_diff(struct cache_entry **src, struct unpack_trees_options *o)
 	if (tree == o->df_conflict_entry)
 		tree = NULL;
 
-	if (ce_path_match(idx ? idx : tree, revs->prune_data.raw))
+	if (ce_path_match(idx ? idx : tree, &revs->prune_data))
 		do_oneway_diff(o, idx, tree);
 
 	return 0;
diff --git a/preload-index.c b/preload-index.c
index e3d0bda..49cb08d 100644
--- a/preload-index.c
+++ b/preload-index.c
@@ -35,7 +35,9 @@ static void *preload_thread(void *_data)
 	struct index_state *index = p->index;
 	struct cache_entry **cep = index->cache + p->offset;
 	struct cache_def cache;
+	struct pathspec pathspec;
 
+	init_pathspec(&pathspec, p->pathspec);
 	memset(&cache, 0, sizeof(cache));
 	nr = p->nr;
 	if (nr + p->offset > index->cache_nr)
@@ -51,7 +53,7 @@ static void *preload_thread(void *_data)
 			continue;
 		if (ce_uptodate(ce))
 			continue;
-		if (!ce_path_match(ce, p->pathspec))
+		if (!ce_path_match(ce, &pathspec))
 			continue;
 		if (threaded_has_symlink_leading_path(&cache, ce->name, ce_namelen(ce)))
 			continue;
@@ -61,6 +63,7 @@ static void *preload_thread(void *_data)
 			continue;
 		ce_mark_uptodate(ce);
 	} while (--nr > 0);
+	free_pathspec(&pathspec);
 	return NULL;
 }
 
diff --git a/read-cache.c b/read-cache.c
index 1f42473..f1141a3 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -683,17 +683,18 @@ int ce_same_name(struct cache_entry *a, struct cache_entry *b)
 	return ce_namelen(b) == len && !memcmp(a->name, b->name, len);
 }
 
-int ce_path_match(const struct cache_entry *ce, const char **pathspec)
+int ce_path_match(const struct cache_entry *ce, const struct pathspec *pathspec)
 {
 	const char *match, *name;
+	const char **ps = pathspec->raw;
 	int len;
 
-	if (!pathspec)
+	if (!pathspec->nr)
 		return 1;
 
 	len = ce_namelen(ce);
 	name = ce->name;
-	while ((match = *pathspec++) != NULL) {
+	while ((match = *ps++) != NULL) {
 		int matchlen = strlen(match);
 		if (matchlen > len)
 			continue;
diff --git a/revision.c b/revision.c
index 515e2dd..a0d3816 100644
--- a/revision.c
+++ b/revision.c
@@ -969,7 +969,7 @@ static void prepare_show_merge(struct rev_info *revs)
 		struct cache_entry *ce = active_cache[i];
 		if (!ce_stage(ce))
 			continue;
-		if (ce_path_match(ce, revs->prune_data.raw)) {
+		if (ce_path_match(ce, &revs->prune_data)) {
 			prune_num++;
 			prune = xrealloc(prune, sizeof(*prune) * prune_num);
 			prune[prune_num-2] = ce->name;
diff --git a/wt-status.c b/wt-status.c
index 5c6b118..457d265 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -350,14 +350,16 @@ static void wt_status_collect_changes_index(struct wt_status *s)
 
 static void wt_status_collect_changes_initial(struct wt_status *s)
 {
+	struct pathspec pathspec;
 	int i;
 
+	init_pathspec(&pathspec, s->pathspec);
 	for (i = 0; i < active_nr; i++) {
 		struct string_list_item *it;
 		struct wt_status_change_data *d;
 		struct cache_entry *ce = active_cache[i];
 
-		if (!ce_path_match(ce, s->pathspec))
+		if (!ce_path_match(ce, &pathspec))
 			continue;
 		it = string_list_insert(&s->change, ce->name);
 		d = it->util;
@@ -372,6 +374,7 @@ static void wt_status_collect_changes_initial(struct wt_status *s)
 		else
 			d->index_status = DIFF_STATUS_ADDED;
 	}
+	free_pathspec(&pathspec);
 }
 
 static void wt_status_collect_untracked(struct wt_status *s)
-- 
1.7.3.3.476.g10a82

[PATCH 19/21] grep: use writable strbuf from caller for grep_tree()

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 strbuf_offset and its patch are dropped.

 builtin/grep.c |   51 ++++++++++++++++++++++++---------------------------
 1 files changed, 24 insertions(+), 27 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index fbc7d02..fa1ad28 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -623,43 +623,29 @@ static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int
 }
 
 static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
-		     struct tree_desc *tree,
-		     const char *tree_name, const char *base)
+		     struct tree_desc *tree, struct strbuf *base, int tn_len)
 {
-	int len;
 	int hit = 0;
 	struct name_entry entry;
-	char *down;
-	int tn_len = strlen(tree_name);
-	struct strbuf pathbuf;
-
-	strbuf_init(&pathbuf, PATH_MAX + tn_len);
-
-	if (tn_len) {
-		strbuf_add(&pathbuf, tree_name, tn_len);
-		strbuf_addch(&pathbuf, ':');
-		tn_len = pathbuf.len;
-	}
-	strbuf_addstr(&pathbuf, base);
-	len = pathbuf.len;
+	int old_baselen = base->len;
 
 	while (tree_entry(tree, &entry)) {
 		int te_len = tree_entry_len(entry.path, entry.sha1);
-		pathbuf.len = len;
-		strbuf_add(&pathbuf, entry.path, te_len);
+
+		strbuf_add(base, entry.path, te_len);
 
 		if (S_ISDIR(entry.mode))
 			/* Match "abc/" against pathspec to
 			 * decide if we want to descend into "abc"
 			 * directory.
 			 */
-			strbuf_addch(&pathbuf, '/');
+			strbuf_addch(base, '/');
 
-		down = pathbuf.buf + tn_len;
-		if (!pathspec_matches(pathspec->raw, down, opt->max_depth))
+		if (!pathspec_matches(pathspec->raw, base->buf + tn_len, opt->max_depth))
 			;
-		else if (S_ISREG(entry.mode))
-			hit |= grep_sha1(opt, entry.sha1, pathbuf.buf, tn_len);
+		else if (S_ISREG(entry.mode)) {
+			hit |= grep_sha1(opt, entry.sha1, base->buf, tn_len);
+		}
 		else if (S_ISDIR(entry.mode)) {
 			enum object_type type;
 			struct tree_desc sub;
@@ -671,13 +657,14 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 				die("unable to read tree (%s)",
 				    sha1_to_hex(entry.sha1));
 			init_tree_desc(&sub, data, size);
-			hit |= grep_tree(opt, pathspec, &sub, tree_name, down);
+			hit |= grep_tree(opt, pathspec, &sub, base, tn_len);
 			free(data);
 		}
+		strbuf_setlen(base, old_baselen);
+
 		if (hit && opt->status_only)
 			break;
 	}
-	strbuf_release(&pathbuf);
 	return hit;
 }
 
@@ -690,13 +677,23 @@ static int grep_object(struct grep_opt *opt, const struct pathspec *pathspec,
 		struct tree_desc tree;
 		void *data;
 		unsigned long size;
-		int hit;
+		struct strbuf base;
+		int hit, len;
+
 		data = read_object_with_reference(obj->sha1, tree_type,
 						  &size, NULL);
 		if (!data)
 			die("unable to read tree (%s)", sha1_to_hex(obj->sha1));
+
+		len = name ? strlen(name) : 0;
+		strbuf_init(&base, PATH_MAX + len + 1);
+		if (len) {
+			strbuf_add(&base, name, len);
+			strbuf_addch(&base, ':');
+		}
 		init_tree_desc(&tree, data, size);
-		hit = grep_tree(opt, pathspec, &tree, name, "");
+		hit = grep_tree(opt, pathspec, &tree, &base, base.len);
+		strbuf_release(&base);
 		free(data);
 		return hit;
 	}
-- 
1.7.3.3.476.g10a82

[PATCH 20/21] grep: drop pathspec_matches() in favor of tree_entry_interesting()

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 tree_entry_interesting now takes base_offset. The real base is
 base->buf+base_offset

 builtin/grep.c |  125 ++++++-------------------------------------------------
 tree-diff.c    |    4 +-
 tree-walk.c    |   19 ++++----
 tree-walk.h    |    2 +-
 4 files changed, 27 insertions(+), 123 deletions(-)

diff --git a/builtin/grep.c b/builtin/grep.c
index fa1ad28..7256002 100644
--- a/builtin/grep.c
+++ b/builtin/grep.c
@@ -333,106 +333,6 @@ static int grep_config(const char *var, const char *value, void *cb)
 	return 0;
 }
 
-/*
- * Return non-zero if max_depth is negative or path has no more then max_depth
- * slashes.
- */
-static int accept_subdir(const char *path, int max_depth)
-{
-	if (max_depth < 0)
-		return 1;
-
-	while ((path = strchr(path, '/')) != NULL) {
-		max_depth--;
-		if (max_depth < 0)
-			return 0;
-		path++;
-	}
-	return 1;
-}
-
-/*
- * Return non-zero if name is a subdirectory of match and is not too deep.
- */
-static int is_subdir(const char *name, int namelen,
-		const char *match, int matchlen, int max_depth)
-{
-	if (matchlen > namelen || strncmp(name, match, matchlen))
-		return 0;
-
-	if (name[matchlen] == '\0') /* exact match */
-		return 1;
-
-	if (!matchlen || match[matchlen-1] == '/' || name[matchlen] == '/')
-		return accept_subdir(name + matchlen + 1, max_depth);
-
-	return 0;
-}
-
-/*
- * git grep pathspecs are somewhat different from diff-tree pathspecs;
- * pathname wildcards are allowed.
- */
-static int pathspec_matches(const char **paths, const char *name, int max_depth)
-{
-	int namelen, i;
-	if (!paths || !*paths)
-		return accept_subdir(name, max_depth);
-	namelen = strlen(name);
-	for (i = 0; paths[i]; i++) {
-		const char *match = paths[i];
-		int matchlen = strlen(match);
-		const char *cp, *meta;
-
-		if (is_subdir(name, namelen, match, matchlen, max_depth))
-			return 1;
-		if (!fnmatch(match, name, 0))
-			return 1;
-		if (name[namelen-1] != '/')
-			continue;
-
-		/* We are being asked if the directory ("name") is worth
-		 * descending into.
-		 *
-		 * Find the longest leading directory name that does
-		 * not have metacharacter in the pathspec; the name
-		 * we are looking at must overlap with that directory.
-		 */
-		for (cp = match, meta = NULL; cp - match < matchlen; cp++) {
-			char ch = *cp;
-			if (ch == '*' || ch == '[' || ch == '?') {
-				meta = cp;
-				break;
-			}
-		}
-		if (!meta)
-			meta = cp; /* fully literal */
-
-		if (namelen <= meta - match) {
-			/* Looking at "Documentation/" and
-			 * the pattern says "Documentation/howto/", or
-			 * "Documentation/diff*.txt".  The name we
-			 * have should match prefix.
-			 */
-			if (!memcmp(match, name, namelen))
-				return 1;
-			continue;
-		}
-
-		if (meta - match < namelen) {
-			/* Looking at "Documentation/howto/" and
-			 * the pattern says "Documentation/h*";
-			 * match up to "Do.../h"; this avoids descending
-			 * into "Documentation/technical/".
-			 */
-			if (!memcmp(match, name, meta - match))
-				return 1;
-			continue;
-		}
-	}
-	return 0;
-}
-
 static void *lock_and_read_sha1_file(const unsigned char *sha1, enum object_type *type, unsigned long *size)
 {
 	void *data;
@@ -625,25 +525,24 @@ static int grep_cache(struct grep_opt *opt, const struct pathspec *pathspec, int
 static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 		     struct tree_desc *tree, struct strbuf *base, int tn_len)
 {
-	int hit = 0;
+	int hit = 0, matched = 0;
 	struct name_entry entry;
 	int old_baselen = base->len;
 
 	while (tree_entry(tree, &entry)) {
 		int te_len = tree_entry_len(entry.path, entry.sha1);
 
-		strbuf_add(base, entry.path, te_len);
+		if (matched != 2) {
+			matched = tree_entry_interesting(&entry, base, tn_len, pathspec);
+			if (matched == -1)
+				break; /* no more matches */
+			if (!matched)
+				continue;
+		}
 
-		if (S_ISDIR(entry.mode))
-			/* Match "abc/" against pathspec to
-			 * decide if we want to descend into "abc"
-			 * directory.
-			 */
-			strbuf_addch(base, '/');
+		strbuf_add(base, entry.path, te_len);
 
-		if (!pathspec_matches(pathspec->raw, base->buf + tn_len, opt->max_depth))
-			;
-		else if (S_ISREG(entry.mode)) {
+		if (S_ISREG(entry.mode)) {
 			hit |= grep_sha1(opt, entry.sha1, base->buf, tn_len);
 		}
 		else if (S_ISDIR(entry.mode)) {
@@ -656,6 +555,8 @@ static int grep_tree(struct grep_opt *opt, const struct pathspec *pathspec,
 			if (!data)
 				die("unable to read tree (%s)",
 				    sha1_to_hex(entry.sha1));
+
+			strbuf_addch(base, '/');
 			init_tree_desc(&sub, data, size);
 			hit |= grep_tree(opt, pathspec, &sub, base, tn_len);
 			free(data);
@@ -1062,6 +963,8 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 		paths[1] = NULL;
 	}
 	init_pathspec(&pathspec, paths);
+	pathspec.max_depth = opt.max_depth;
+	pathspec.recursive = 1;
 
 	if (show_in_pager && (cached || list.nr))
 		die("--open-files-in-pager only works on the worktree");
diff --git a/tree-diff.c b/tree-diff.c
index bde2c52..064233a 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -72,7 +72,7 @@ static void show_tree(struct diff_options *opt, const char *prefix,
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(&desc->entry, base,
+			show = tree_entry_interesting(&desc->entry, base, 0,
 						      &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
@@ -130,7 +130,7 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 		if (all_interesting)
 			show = 1;
 		else {
-			show = tree_entry_interesting(&t->entry, base,
+			show = tree_entry_interesting(&t->entry, base, 0,
 						      &opt->pathspec);
 			if (show == 2)
 				all_interesting = 1;
diff --git a/tree-walk.c b/tree-walk.c
index 99413b3..9b43ad5 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -551,17 +551,17 @@ static int match_dir_prefix(const char *base, int baselen,
  *  - negative for "no, and no subsequent entries will be either"
  */
 int tree_entry_interesting(const struct name_entry *entry,
-			   struct strbuf *base,
+			   struct strbuf *base, int base_offset,
 			   const struct pathspec *ps)
 {
 	int i;
-	int pathlen, baselen = base->len;
+	int pathlen, baselen = base->len - base_offset;
 	int never_interesting = ps->has_wildcard ? 0 : -1;
 
 	if (!ps->nr) {
 		if (!ps->recursive || ps->max_depth == -1)
 			return 1;
-		return !!within_depth(base->buf, baselen,
+		return !!within_depth(base->buf + base_offset, baselen,
 				      !!S_ISDIR(entry->mode),
 				      ps->max_depth);
 	}
@@ -571,24 +571,25 @@ int tree_entry_interesting(const struct name_entry *entry,
 	for (i = ps->nr-1; i >= 0; i--) {
 		const struct pathspec_item *item = ps->items+i;
 		const char *match = item->match;
+		const char *base_str = base->buf + base_offset;
 		int matchlen = item->len;
 
 		if (baselen >= matchlen) {
 			/* If it doesn't match, move along... */
-			if (!match_dir_prefix(base->buf, baselen, match, matchlen))
+			if (!match_dir_prefix(base_str, baselen, match, matchlen))
 				goto match_wildcards;
 
 			if (!ps->recursive || ps->max_depth == -1)
 				return 2;
 
-			return !!within_depth(base->buf + matchlen + 1,
+			return !!within_depth(base_str + matchlen + 1,
 					      baselen - matchlen - 1,
 					      !!S_ISDIR(entry->mode),
 					      ps->max_depth);
 		}
 
 		/* Does the base match? */
-		if (!strncmp(base->buf, match, baselen)) {
+		if (!strncmp(base_str, match, baselen)) {
 			if (match_entry(entry, pathlen,
 					match + baselen, matchlen - baselen,
 					&never_interesting))
@@ -620,11 +621,11 @@ match_wildcards:
 
 		strbuf_add(base, entry->path, pathlen);
 
-		if (!fnmatch(match, base->buf, 0)) {
-			strbuf_setlen(base, baselen);
+		if (!fnmatch(match, base->buf + base_offset, 0)) {
+			strbuf_setlen(base, base_offset + baselen);
 			return 1;
 		}
-		strbuf_setlen(base, baselen);
+		strbuf_setlen(base, base_offset + baselen);
 
 		/*
 		 * Match all directories. We'll try to match files
diff --git a/tree-walk.h b/tree-walk.h
index 6589ee2..39524b7 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -60,6 +60,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 tree_entry_interesting(const struct name_entry *, struct strbuf *, const struct pathspec *ps);
+extern int tree_entry_interesting(const struct name_entry *, struct strbuf *, int, const struct pathspec *ps);
 
 #endif
-- 
1.7.3.3.476.g10a82

Re: [PATCH 14/21] Convert ce_path_match() to use struct pathspec

[Junio C Hamano]

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

>> I wonder if it makes more sense to change the type of revs->prune_data
>> from an array of pointers to strings to a pointer to struct pathspec.
>> Is there a downside?
>
> Converting a pointer to another pointer means mis typecasting can
> happen and the compiler won't help catching them.

You can rename the field at the same time, and the compiler will catch
anything you forgot to touch, no?

Re: [PATCH 14/21] Convert ce_path_match() to use struct pathspec

[Nguyen Thai Ngoc Duy]

On Fri, Dec 17, 2010 at 10:09 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:
>
>>> I wonder if it makes more sense to change the type of revs->prune_data
>>> from an array of pointers to strings to a pointer to struct pathspec.
>>> Is there a downside?
>>
>> Converting a pointer to another pointer means mis typecasting can
>> happen and the compiler won't help catching them.
>
> You can rename the field at the same time, and the compiler will catch
> anything you forgot to touch, no?
>

Yes. I didn't think of that :(
-- 
Duy

Re: [PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

[Junio C Hamano]

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

> 2010/12/17 Junio C Hamano <gitster@pobox.com>:
>> One thing I am not clear is what it means to limit the recursion level
>> when you have wildcards.
>
> Recursion level does not affect wildcards at all. That was original
> design, a91f453 (grep: Add --max-depth option. - 2009-07-22). I think
> current git-grep still follows that.

I know what the current code does, as I remember a91f453 essentially
punted on coming up with a sane semantics.  As this series under
discussion is about coming up with a unified and sane pathspec handling
across board, it would be a good opportunity to think about it again, this
time without punting so fast.

Re: [PATCH 14/21] Convert ce_path_match() to use struct pathspec

[Junio C Hamano]

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

> On Fri, Dec 17, 2010 at 10:09 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:
>>
>>>> I wonder if it makes more sense to change the type of revs->prune_data
>>>> from an array of pointers to strings to a pointer to struct pathspec.
>>>> Is there a downside?
>>>
>>> Converting a pointer to another pointer means mis typecasting can
>>> happen and the compiler won't help catching them.
>>
>> You can rename the field at the same time, and the compiler will catch
>> anything you forgot to touch, no?
>>
> Yes. I didn't think of that :(

And it would have an added benefit that it would catch new callsites
somebody else added while being unaware of your conversion--the merge
result will not compile.

Re: [PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

[Nguyen Thai Ngoc Duy]

2010/12/17 Junio C Hamano <gitster@pobox.com>:
> One possible definition of interaction between limit and wildcard may be
> to count the number of slashes in the part of the path that matches the
> wildcarded part of the pathspec, add the number of path components
> appended due to the leading directory match, and then subtract the number
> of literal slashes in the wildcarded part of the pattern from the above,
> and declare that a match is found if the difference is less than the
> limit.
>
> E.g. a pathspec element "a/*/x" would match "a/b/c/x", "a/b/c/d/e/x",
> "a/b/x/y" and "a/b/x/y/z" without limit, and with the limit of 1:
>
>    a/b/c/x        matches ('*' expands to "b/c")
>    a/b/c/d/e/x    no ('*' has to expand to "c/d/e" and needs 2 levels)
>    a/b/x/y        matches ('*' expands to "b" costing zero, "/y" needs 1)
>    a/b/x/y/z      does not match
>
> Another definition could be to count _only_ the part that is appended by
> recursion (i.e. we do not count how many slashes has to match '*' in the
> above examples), and as the option is called --depth, it might make more
> sense.

So with the above example, "a/" won't be counted. Depth limit of 0 or
1 will result in no matches. Depth limit of 2 will result in a/b/c/x
and a/b/x/y, correct?

I prefer this definition to the former. It sounds simpler to
understand and use, also less computation. But I can implement both
:-) We can mark what matching strategy we would use in struct
pathspec.  Hmm.. I'm not much help in figuring out which one makes
more sense.

Another thing, I don't know if anybody would need it. Should we
support depth limit per pathspec, so "a/*/x" can have depth limit of
2, but "*.c" has depth limit of 1..For one thing, his may help keeping
current's git-grep depth limit behavior if depth limit can also be
applied to wildcard pathspecs by setting depth limit for wildcard
pathspecs to -1. Exposing depth limit per pathspec to users is another
matter.

> In either case, I am not sure if "if it matches the longest pathspec, we
> have the answer without looking at shorter ones" would be a good rule to
> use.

As long as the rule of matching is "if any of these pathspecs is
matched, we have a match", then pathspec order should not matter
(without depth limit). Matching decision of one pathspec does not
affect the others. Depth limit is the first one breaking the last
sentence. And because pathspec order does not matter before depth
limit introduction, it should not cause any regression when depth
limit requires pathspecs in certain order. That's how I thought when I
decided to sort pathspecs.

Wildcard pathspecs are handled in a completely different path (even
with depth limit in either way you described). Overlapping is no issue
to wildcard pathspecs, we always need full pathspec to call fnmatch()
(unless you implied some early cut optmization that I don't see).
Therefore pathspec order is no issue.

Even when I introduce negative pathspec, it would be actually negative
prefix and go the same route as current depth limit impl (it also has
the same overlapping pathspec issue). Negative wildcard pathspecs
would blow my mind.
-- 
Duy

Re: [PATCH 09/21] tree_entry_interesting(): support depth limit

[Junio C Hamano]

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

>  static const char *get_mode(const char *str, unsigned int *modep)
> @@ -557,8 +558,13 @@ int tree_entry_interesting(const struct name_entry *entry,
>  	int pathlen, baselen = base->len;
>  	int never_interesting = -1;
>  
> -	if (!ps || !ps->nr)
> -		return 1;
> +	if (!ps->nr) {
> +		if (!ps->recursive || ps->max_depth == -1)
> +			return 1;
> +		return !!within_depth(base->buf, baselen,
> +				      !!S_ISDIR(entry->mode),
> +				      ps->max_depth);
> +	}

Back in 1d848f6 (tree_entry_interesting(): allow it to say "everything is
interesting", 2007-03-21), a new return value "2" was introduced to allow
this function to tell the caller that all the remaining entries in the
tree object the caller is feeding the entries to this function _will_
match.  This was to optimize away expensive pathspec matching done by this
function.

In that version, "no pathspec" case wasn't changed to return 2 but still
returned 1 ("I tell you that this does not match; call me with the next
entry").  We could have changed it to return 2, but the overhead was only
a call to a function that checks the number of pathspecs and was not so
bad.

But shouldn't we start returning 2 by now?  It is not that returning 1 was
a more correct thing to do to begin with.

When depth check is in effect, the result depends on the mode of the
entry, so we cannot short-circuit by returning 2, but at least we should
do so when (max_depth == -1), no?

Re: [PATCH 09/21] tree_entry_interesting(): support depth limit

[Nguyen Thai Ngoc Duy]

2011/1/29 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>>  static const char *get_mode(const char *str, unsigned int *modep)
>> @@ -557,8 +558,13 @@ int tree_entry_interesting(const struct name_entry *entry,
>>       int pathlen, baselen = base->len;
>>       int never_interesting = -1;
>>
>> -     if (!ps || !ps->nr)
>> -             return 1;
>> +     if (!ps->nr) {
>> +             if (!ps->recursive || ps->max_depth == -1)
>> +                     return 1;
>> +             return !!within_depth(base->buf, baselen,
>> +                                   !!S_ISDIR(entry->mode),
>> +                                   ps->max_depth);
>> +     }
>
> Back in 1d848f6 (tree_entry_interesting(): allow it to say "everything is
> interesting", 2007-03-21), a new return value "2" was introduced to allow
> this function to tell the caller that all the remaining entries in the
> tree object the caller is feeding the entries to this function _will_
> match.  This was to optimize away expensive pathspec matching done by this
> function.
>
> In that version, "no pathspec" case wasn't changed to return 2 but still
> returned 1 ("I tell you that this does not match; call me with the next
> entry").  We could have changed it to return 2, but the overhead was only
> a call to a function that checks the number of pathspecs and was not so
> bad.
>
> But shouldn't we start returning 2 by now?  It is not that returning 1 was
> a more correct thing to do to begin with.
>
> When depth check is in effect, the result depends on the mode of the
> entry, so we cannot short-circuit by returning 2, but at least we should
> do so when (max_depth == -1), no?

Yes, should be 2.
-- 
Duy

[PATCH] tree_entry_interesting(): with no pathspecs, everything will match

[Junio C Hamano]

Hence the function should return "2" in such a case as advertised.

Note that finding a directory that busts the depth limit does not mean non
directories at the same level would also bust the limit (they don't), so
we still need to return 1, not 2 in the within_depth() codepath.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
--- 

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

  >> When depth check is in effect, the result depends on the mode of the
  >> entry, so we cannot short-circuit by returning 2, but at least we should
  >> do so when (max_depth == -1), no?
  >
  > Yes, should be 2.

  Thanks.  I'll queue this.

 tree-walk.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/tree-walk.c b/tree-walk.c
index 9b43ad5..ece8cc0 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -560,7 +560,7 @@ int tree_entry_interesting(const struct name_entry *entry,
 
 	if (!ps->nr) {
 		if (!ps->recursive || ps->max_depth == -1)
-			return 1;
+			return 2;
 		return !!within_depth(base->buf + base_offset, baselen,
 				      !!S_ISDIR(entry->mode),
 				      ps->max_depth);
-- 
1.7.4.261.g705f2

[PATCH] diff-tree doc: correct & remove wrong documentation

[Ævar Arnfjörð Bjarmason]

The documentation saying that diff-tree didn't support anything except
literal prefixes hasn't been true since
d38f28093e ("tree_entry_interesting(): support wildcard matching",
2010-12-15), but this documentation was not updated at the time.

Since this command uses pathspecs like most other commands, there's no
need to show examples of how the various "cmd <revs> <paths>"
invocations work.

Furthermore, the "git diff-tree --abbrev 5319e4" example shown here
never worked. We'd ended up with that through a combination of
62b42d3487 ("docs: fix some antique example output", 2011-05-26) and
ac4e086929 ("Adjust core-git documentation to more recent Linus GIT.",
2005-05-05), but "git diff-tree <tree>" was always invalid.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 Documentation/git-diff-tree.txt | 51 +--------------------------------
 1 file changed, 1 insertion(+), 50 deletions(-)

diff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt
index 2319b2b192..43daa7c046 100644
--- a/Documentation/git-diff-tree.txt
+++ b/Documentation/git-diff-tree.txt
@@ -31,10 +31,7 @@ include::diff-options.txt[]
 
 <path>...::
 	If provided, the results are limited to a subset of files
-	matching one of these prefix strings.
-	i.e., file matches `/^<pattern1>|<pattern2>|.../`
-	Note that this parameter does not provide any wildcard or regexp
-	features.
+	matching one of the provided pathspecs.
 
 -r::
         recurse into sub-trees
@@ -114,52 +111,6 @@ include::pretty-options.txt[]
 
 
 include::pretty-formats.txt[]
-
-
-LIMITING OUTPUT
----------------
-If you're only interested in differences in a subset of files, for
-example some architecture-specific files, you might do:
-
-	git diff-tree -r <tree-ish> <tree-ish> arch/ia64 include/asm-ia64
-
-and it will only show you what changed in those two directories.
-
-Or if you are searching for what changed in just `kernel/sched.c`, just do
-
-	git diff-tree -r <tree-ish> <tree-ish> kernel/sched.c
-
-and it will ignore all differences to other files.
-
-The pattern is always the prefix, and is matched exactly.  There are no
-wildcards.  Even stricter, it has to match a complete path component.
-I.e. "foo" does not pick up `foobar.h`.  "foo" does match `foo/bar.h`
-so it can be used to name subdirectories.
-
-An example of normal usage is:
-
-  torvalds@ppc970:~/git> git diff-tree --abbrev 5319e4
-  :100664 100664 ac348b... a01513...	git-fsck-objects.c
-
-which tells you that the last commit changed just one file (it's from
-this one:
-
------------------------------------------------------------------------------
-commit 3c6f7ca19ad4043e9e72fa94106f352897e651a8
-tree 5319e4d609cdd282069cc4dce33c1db559539b03
-parent b4e628ea30d5ab3606119d2ea5caeab141d38df7
-author Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
-committer Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
-
-Make "git-fsck-objects" print out all the root commits it finds.
-
-Once I do the reference tracking, I'll also make it print out all the
-HEAD commits it finds, which is even more interesting.
------------------------------------------------------------------------------
-
-in case you care).
-
-
 include::diff-format.txt[]
 
 GIT
-- 
2.20.1.611.gfbb209baf1

Re: [PATCH] diff-tree doc: correct & remove wrong documentation

[Duy Nguyen]

On Mon, Feb 4, 2019 at 5:36 PM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>
> The documentation saying that diff-tree didn't support anything except
> literal prefixes hasn't been true since
> d38f28093e ("tree_entry_interesting(): support wildcard matching",
> 2010-12-15), but this documentation was not updated at the time.
>
> Since this command uses pathspecs like most other commands, there's no
> need to show examples of how the various "cmd <revs> <paths>"
> invocations work.
>
> Furthermore, the "git diff-tree --abbrev 5319e4" example shown here
> never worked. We'd ended up with that through a combination of
> 62b42d3487 ("docs: fix some antique example output", 2011-05-26) and
> ac4e086929 ("Adjust core-git documentation to more recent Linus GIT.",
> 2005-05-05), but "git diff-tree <tree>" was always invalid.

Nice!

I was going to protest "but it does not work!" but I was thinking
ls-tree instead of diff-tree.

>
> Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
> ---
>  Documentation/git-diff-tree.txt | 51 +--------------------------------
>  1 file changed, 1 insertion(+), 50 deletions(-)
>
> diff --git a/Documentation/git-diff-tree.txt b/Documentation/git-diff-tree.txt
> index 2319b2b192..43daa7c046 100644
> --- a/Documentation/git-diff-tree.txt
> +++ b/Documentation/git-diff-tree.txt
> @@ -31,10 +31,7 @@ include::diff-options.txt[]
>
>  <path>...::
>         If provided, the results are limited to a subset of files
> -       matching one of these prefix strings.
> -       i.e., file matches `/^<pattern1>|<pattern2>|.../`
> -       Note that this parameter does not provide any wildcard or regexp
> -       features.
> +       matching one of the provided pathspecs.
>
>  -r::
>          recurse into sub-trees
> @@ -114,52 +111,6 @@ include::pretty-options.txt[]
>
>
>  include::pretty-formats.txt[]
> -
> -
> -LIMITING OUTPUT
> ----------------
> -If you're only interested in differences in a subset of files, for
> -example some architecture-specific files, you might do:
> -
> -       git diff-tree -r <tree-ish> <tree-ish> arch/ia64 include/asm-ia64
> -
> -and it will only show you what changed in those two directories.
> -
> -Or if you are searching for what changed in just `kernel/sched.c`, just do
> -
> -       git diff-tree -r <tree-ish> <tree-ish> kernel/sched.c
> -
> -and it will ignore all differences to other files.
> -
> -The pattern is always the prefix, and is matched exactly.  There are no
> -wildcards.  Even stricter, it has to match a complete path component.
> -I.e. "foo" does not pick up `foobar.h`.  "foo" does match `foo/bar.h`
> -so it can be used to name subdirectories.
> -
> -An example of normal usage is:
> -
> -  torvalds@ppc970:~/git> git diff-tree --abbrev 5319e4
> -  :100664 100664 ac348b... a01513...   git-fsck-objects.c
> -
> -which tells you that the last commit changed just one file (it's from
> -this one:
> -
> ------------------------------------------------------------------------------
> -commit 3c6f7ca19ad4043e9e72fa94106f352897e651a8
> -tree 5319e4d609cdd282069cc4dce33c1db559539b03
> -parent b4e628ea30d5ab3606119d2ea5caeab141d38df7
> -author Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
> -committer Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
> -
> -Make "git-fsck-objects" print out all the root commits it finds.
> -
> -Once I do the reference tracking, I'll also make it print out all the
> -HEAD commits it finds, which is even more interesting.
> ------------------------------------------------------------------------------
> -
> -in case you care).
> -
> -
>  include::diff-format.txt[]
>
>  GIT
> --
> 2.20.1.611.gfbb209baf1
>


-- 
Duy

Re: [PATCH] diff-tree doc: correct & remove wrong documentation

[Junio C Hamano]

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

>  <path>...::
>  	If provided, the results are limited to a subset of files
> -	matching one of these prefix strings.
> -	i.e., file matches `/^<pattern1>|<pattern2>|.../`
> -	Note that this parameter does not provide any wildcard or regexp
> -	features.
> +	matching one of the provided pathspecs.

Correct.

> -
> -
> -LIMITING OUTPUT
> ----------------
> -If you're only interested in differences in a subset of files, for
> -example some architecture-specific files, you might do:
> -
> -	git diff-tree -r <tree-ish> <tree-ish> arch/ia64 include/asm-ia64
> -
> -and it will only show you what changed in those two directories.
> -
> -Or if you are searching for what changed in just `kernel/sched.c`, just do
> -
> -	git diff-tree -r <tree-ish> <tree-ish> kernel/sched.c
> -
> -and it will ignore all differences to other files.

All of the above give still useful piece of information to the
readers.  I do not think it is a good idea to assume familiarilty
with pathspec limiting to all readers---a new reader must start
somewhere and diff-tree may just be a random place s/he started at.

So I do not think it is a good idea to drop this example or the
section from the page.

> -The pattern is always the prefix, and is matched exactly.  There are no
> -wildcards.  Even stricter, it has to match a complete path component.
> -I.e. "foo" does not pick up `foobar.h`.  "foo" does match `foo/bar.h`
> -so it can be used to name subdirectories.

I agree with the patch that this paragraph should go.

> -An example of normal usage is:
> -
> -  torvalds@ppc970:~/git> git diff-tree --abbrev 5319e4
> -  :100664 100664 ac348b... a01513...	git-fsck-objects.c

Interesting.  This does not work (and I do not think it has ever
worked) for a tree object 5319e4, but it works as advertised for a
commit object.

The description section has this near the top

       If there is only one <tree-ish> given, the commit is compared
       with its parents (see --stdin below).
              
I think s/given,/& it must be a commit-ish and/ would be appropriate
there; please include such a fix in a reroll.

I agree with this patch that it is a good idea to drop this example;
it is more appropriate to use "git show" on the commit-ish in the
case of the given example anyway.

> -
> -which tells you that the last commit changed just one file (it's from
> -this one:
> -
> ------------------------------------------------------------------------------
> -commit 3c6f7ca19ad4043e9e72fa94106f352897e651a8
> -tree 5319e4d609cdd282069cc4dce33c1db559539b03
> -parent b4e628ea30d5ab3606119d2ea5caeab141d38df7
> -author Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
> -committer Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
> -
> -Make "git-fsck-objects" print out all the root commits it finds.
> -
> -Once I do the reference tracking, I'll also make it print out all the
> -HEAD commits it finds, which is even more interesting.
> ------------------------------------------------------------------------------
> -
> -in case you care).
> -

Re: [PATCH] diff-tree doc: correct & remove wrong documentation

[Ævar Arnfjörð Bjarmason]

On Mon, Feb 04 2019, Junio C Hamano wrote:

> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>
>>  <path>...::
>>  	If provided, the results are limited to a subset of files
>> -	matching one of these prefix strings.
>> -	i.e., file matches `/^<pattern1>|<pattern2>|.../`
>> -	Note that this parameter does not provide any wildcard or regexp
>> -	features.
>> +	matching one of the provided pathspecs.
>
> Correct.
>
>> -
>> -
>> -LIMITING OUTPUT
>> ----------------
>> -If you're only interested in differences in a subset of files, for
>> -example some architecture-specific files, you might do:
>> -
>> -	git diff-tree -r <tree-ish> <tree-ish> arch/ia64 include/asm-ia64
>> -
>> -and it will only show you what changed in those two directories.
>> -
>> -Or if you are searching for what changed in just `kernel/sched.c`, just do
>> -
>> -	git diff-tree -r <tree-ish> <tree-ish> kernel/sched.c
>> -
>> -and it will ignore all differences to other files.
>
> All of the above give still useful piece of information to the
> readers.  I do not think it is a good idea to assume familiarilty
> with pathspec limiting to all readers---a new reader must start
> somewhere and diff-tree may just be a random place s/he started at.
>
> So I do not think it is a good idea to drop this example or the
> section from the page.

I was aiming for something like what e.g. "git-ls-files" says, which is
just:

    Files to show. If no files are given all files which match the other
    specified criteria are shown.

But yes, having an example is good, but with this removed isn't the
example we show in "RAW OUTPUT FORMAT" now just below sufficient to show
what this remove section was trying (and failing) to do, i.e.:

    git-diff-tree [-r] <tree-ish-1> <tree-ish-2> [<pattern>...]
        compares the trees named by the two arguments.

That doesn't have --abbrev, but I think it's enough to leave that
discussed in "OPTIONS" above.

>> -The pattern is always the prefix, and is matched exactly.  There are no
>> -wildcards.  Even stricter, it has to match a complete path component.
>> -I.e. "foo" does not pick up `foobar.h`.  "foo" does match `foo/bar.h`
>> -so it can be used to name subdirectories.
>
> I agree with the patch that this paragraph should go.
>
>> -An example of normal usage is:
>> -
>> -  torvalds@ppc970:~/git> git diff-tree --abbrev 5319e4
>> -  :100664 100664 ac348b... a01513...	git-fsck-objects.c
>
> Interesting.  This does not work (and I do not think it has ever
> worked) for a tree object 5319e4, but it works as advertised for a
> commit object.
>
> The description section has this near the top
>
>        If there is only one <tree-ish> given, the commit is compared
>        with its parents (see --stdin below).
>
> I think s/given,/& it must be a commit-ish and/ would be appropriate
> there; please include such a fix in a reroll.
>
> I agree with this patch that it is a good idea to drop this example;
> it is more appropriate to use "git show" on the commit-ish in the
> case of the given example anyway.
>
>> -
>> -which tells you that the last commit changed just one file (it's from
>> -this one:
>> -
>> ------------------------------------------------------------------------------
>> -commit 3c6f7ca19ad4043e9e72fa94106f352897e651a8
>> -tree 5319e4d609cdd282069cc4dce33c1db559539b03
>> -parent b4e628ea30d5ab3606119d2ea5caeab141d38df7
>> -author Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
>> -committer Linus Torvalds <torvalds@ppc970.osdl.org> Sat Apr 9 12:02:30 2005
>> -
>> -Make "git-fsck-objects" print out all the root commits it finds.
>> -
>> -Once I do the reference tracking, I'll also make it print out all the
>> -HEAD commits it finds, which is even more interesting.
>> ------------------------------------------------------------------------------
>> -
>> -in case you care).
>> -