[PATCH 0/6] Introduce pathspec struct

[PATCH 0/6] Introduce pathspec struct

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

This is base series for en/object-list-with-pathspec, the upcoming
wildcard support in diff family (i.e. tree_entry_interesting()) and
negative pathspec farther in future.

Nguyễn Thái Ngọc Duy (6):
  Add struct pathspec
  diff-no-index: use diff_tree_setup_paths()
  pathspec: cache string length when initialize pathspec
  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

 builtin/diff-files.c |    2 +-
 builtin/diff.c       |    4 +-
 builtin/log.c        |    2 +-
 cache.h              |   10 +++
 diff-lib.c           |    2 +-
 diff-no-index.c      |   13 ++--
 diff.h               |    4 +-
 dir.c                |   27 +++++++++
 revision.c           |    6 +--
 tree-diff.c          |  157 +++-----------------------------------------------
 tree-walk.c          |  111 +++++++++++++++++++++++++++++++++++
 tree-walk.h          |    2 +
 12 files changed, 173 insertions(+), 167 deletions(-)

[PATCH 1/6] Add struct pathspec

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

This struct for now is just a wrapper for the current pathspec form:
const char **. It is intended to be extended with more useful
pathspec-related information over time.

The data structure for passing pathspec around remains const char **,
struct pathspec will be initialized locally to be used and destroyed.
Hopefully all pathspec related code will be gradually migrated to pass
this struct instead.

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

diff --git a/cache.h b/cache.h
index eb77e1d..6227ddb 100644
--- a/cache.h
+++ b/cache.h
@@ -492,6 +492,13 @@ 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;
+	int nr;
+};
+
+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..5815b64 100644
--- a/dir.c
+++ b/dir.c
@@ -1071,3 +1071,21 @@ int remove_path(const char *name)
 	return 0;
 }
 
+int init_pathspec(struct pathspec *pathspec, const char **paths)
+{
+	const char **p = paths;
+
+	memset(pathspec, 0, sizeof(*pathspec));
+	if (!p)
+		return 0;
+	while (*p)
+		p++;
+	pathspec->raw = paths;
+	pathspec->nr = p - paths;
+	return 0;
+}
+
+void free_pathspec(struct pathspec *pathspec)
+{
+	/* do nothing */
+}
-- 
1.7.1.rc1.70.g788ca

[PATCH 2/6] diff-no-index: use diff_tree_setup_paths()

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

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

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

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

[PATCH 3/6] pathspec: cache string length when initialize pathspec

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

This field will be used when tree_entry_interesting() is converted to
use struct pathspec. Currently it uses pathlens[] in struct
diff_options to avoid calculating string over and over again.

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

diff --git a/cache.h b/cache.h
index 6227ddb..045c9fc 100644
--- a/cache.h
+++ b/cache.h
@@ -495,6 +495,9 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
 struct pathspec {
 	const char **raw;
 	int nr;
+	struct pathspec_item {
+		int len;
+	} *items;
 };
 
 extern int init_pathspec(struct pathspec *,const char **);
diff --git a/dir.c b/dir.c
index 5815b64..80b2df2 100644
--- a/dir.c
+++ b/dir.c
@@ -1074,6 +1074,7 @@ int remove_path(const char *name)
 int init_pathspec(struct pathspec *pathspec, const char **paths)
 {
 	const char **p = paths;
+	int i;
 
 	memset(pathspec, 0, sizeof(*pathspec));
 	if (!p)
@@ -1082,10 +1083,18 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)
 		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++) {
+		pathspec->items[i].len = strlen(paths[i]);
+	}
 	return 0;
 }
 
 void free_pathspec(struct pathspec *pathspec)
 {
-	/* do nothing */
+	free(pathspec->items);
+	pathspec->items = NULL;
 }
-- 
1.7.1.rc1.70.g788ca

[PATCH 4/6] 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          |   46 +++++++++++-----------------------------------
 8 files changed, 20 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 08b8722..d78744f 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -89,7 +89,7 @@ static void cmd_log_init(int argc, const char **argv, const char *prefix,
 		rev->always_show_header = 0;
 	if (DIFF_OPT_TST(&rev->diffopt, FOLLOW_RENAMES)) {
 		rev->always_show_header = 0;
-		if (rev->diffopt.nr_paths != 1)
+		if (rev->diffopt.pathspec.nr != 1)
 			usage("git logs can only follow renames on one pathname at a time");
 	}
 	for (i = 1; i < argc; i++) {
diff --git a/diff-lib.c b/diff-lib.c
index 392ce2b..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..986c0f4 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -100,16 +100,16 @@ static int tree_entry_interesting(struct tree_desc *desc, const char *base, int
 	int pathlen;
 	int never_interesting = -1;
 
-	if (!opt->nr_paths)
+	if (!opt->pathspec.nr)
 		return 1;
 
 	sha1 = tree_entry_extract(desc, &path, &mode);
 
 	pathlen = tree_entry_len(path, sha1);
 
-	for (i = 0; i < opt->nr_paths; i++) {
-		const char *match = opt->paths[i];
-		int matchlen = opt->pathlens[i];
+	for (i = 0; i < opt->pathspec.nr; i++) {
+		const char *match = opt->pathspec.raw[i];
+		int matchlen = opt->pathspec.items[i].len;
 		int m = -1; /* signals that we haven't called strncmp() */
 
 		if (baselen >= matchlen) {
@@ -289,7 +289,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru
 		if (DIFF_OPT_TST(opt, QUICK) &&
 		    DIFF_OPT_TST(opt, HAS_CHANGES))
 			break;
-		if (opt->nr_paths) {
+		if (opt->pathspec.nr) {
 			skip_uninteresting(t1, base, baselen, opt);
 			skip_uninteresting(t2, base, baselen, opt);
 		}
@@ -348,7 +348,7 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 	DIFF_OPT_SET(&diff_opts, RECURSIVE);
 	DIFF_OPT_SET(&diff_opts, FIND_COPIES_HARDER);
 	diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;
-	diff_opts.single_follow = opt->paths[0];
+	diff_opts.single_follow = opt->pathspec.raw[0];
 	diff_opts.break_opt = opt->break_opt;
 	paths[0] = NULL;
 	diff_tree_setup_paths(paths, &diff_opts);
@@ -368,15 +368,15 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 		 * diff_queued_diff, we will also use that as the path in
 		 * the future!
 		 */
-		if ((p->status == 'R' || p->status == 'C') && !strcmp(p->two->path, opt->paths[0])) {
+		if ((p->status == 'R' || p->status == 'C') && !strcmp(p->two->path, opt->pathspec.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 +451,12 @@ int diff_root_tree_sha1(const unsigned char *new, const char *base, struct diff_
 	return retval;
 }
 
-static int count_paths(const char **paths)
-{
-	int i = 0;
-	while (*paths++)
-		i++;
-	return i;
-}
-
 void diff_tree_release_paths(struct diff_options *opt)
 {
-	free(opt->pathlens);
+	free_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.1.rc1.70.g788ca

[PATCH 5/6] 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().

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

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

[PATCH 6/6] 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 |  109 ---------------------------------------------------------
 tree-walk.c |  111 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 tree-walk.h |    2 +
 3 files changed, 113 insertions(+), 109 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 822d45e..50d7e6d 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -82,115 +82,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
 	return 0;
 }
 
-/*
- * Is a tree entry interesting given the pathspec we have?
- *
- * Return:
- *  - 2 for "yes, and all subsequent entries will be"
- *  - 1 for yes
- *  - zero for no
- *  - negative for "no, and no subsequent entries will be either"
- */
-static int tree_entry_interesting(const struct name_entry *entry, const char *base, int baselen, const struct 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 char *match = ps->raw[i];
-		int matchlen = ps->items[i].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..01168ea 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -455,3 +455,114 @@ 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 char *match = ps->raw[i];
+		int matchlen = ps->items[i].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 88ea7e9..c3d0684 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -57,4 +57,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.1.rc1.70.g788ca

Re: [PATCH 0/6] Introduce pathspec struct

[Elijah Newren]

2010/9/19 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
> This is base series for en/object-list-with-pathspec, the upcoming
> wildcard support in diff family (i.e. tree_entry_interesting()) and
> negative pathspec farther in future.

I briefly looked over the series.  If I understand correctly, it's
pretty much the same as your previous series, except that it uses a
new data structure instead of exclude_list, and doesn't include my
two-patch series anymore or negated pathspecs.  Is that correct?  If
so, it looks good to me.

I'll try to test it soon, and resubmit my "Nuke match_tree_entry()"
(which duplicates code from tree_entry_interesting()) patch on top of
it.


Thanks,
Elijah

Re: [PATCH 0/6] Introduce pathspec struct

[Nguyen Thai Ngoc Duy]

2010/9/20 Elijah Newren <newren@gmail.com>:
> 2010/9/19 Nguyễn Thái Ngọc Duy <pclouds@gmail.com>:
>> This is base series for en/object-list-with-pathspec, the upcoming
>> wildcard support in diff family (i.e. tree_entry_interesting()) and
>> negative pathspec farther in future.
>
> I briefly looked over the series.  If I understand correctly, it's
> pretty much the same as your previous series, except that it uses a
> new data structure instead of exclude_list, and doesn't include my
> two-patch series anymore or negated pathspecs.  Is that correct?  If
> so, it looks good to me.

Correct. The globbing series is in place of negated pathspecs now.
Your two patch series are also resent elsewhere.
-- 
Duy

Re: [PATCH 1/6] Add struct pathspec

[Junio C Hamano]

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

> This struct for now is just a wrapper for the current pathspec form:
> const char **. It is intended to be extended with more useful
> pathspec-related information over time.
>
> The data structure for passing pathspec around remains const char **,
> struct pathspec will be initialized locally to be used and destroyed.
> Hopefully all pathspec related code will be gradually migrated to pass
> this struct instead.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  cache.h |    7 +++++++
>  dir.c   |   18 ++++++++++++++++++
>  2 files changed, 25 insertions(+), 0 deletions(-)
>
> diff --git a/cache.h b/cache.h
> index eb77e1d..6227ddb 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -492,6 +492,13 @@ extern int index_name_is_oth
> ...
> +struct pathspec {
> +	const char **raw;
> +	int nr;
> +};
> +
> +extern int init_pathspec(struct pathspec *,const char **);

s/,/, /;

> +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..5815b64 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -1071,3 +1071,21 @@ int remove_path(const char *name)
> ...
> +void free_pathspec(struct pathspec *pathspec)
> +{
> +	/* do nothing */
> +}

I'd prefer making this more explicit by saying

	{
        	; /* do nothing */
	}

Re: [PATCH 3/6] pathspec: cache string length when initialize pathspec

[Junio C Hamano]

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

> Subject: Re: [PATCH 3/6] pathspec: cache string length when initialize pathspec

s/initialize/initializing/;

> This field will be used when tree_entry_interesting() is converted to
> use struct pathspec. Currently it uses pathlens[] in struct
> diff_options to avoid calculating string over and over again.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  cache.h |    3 +++
>  dir.c   |   11 ++++++++++-
>  2 files changed, 13 insertions(+), 1 deletions(-)
>
> diff --git a/cache.h b/cache.h
> index 6227ddb..045c9fc 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -495,6 +495,9 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
>  struct pathspec {
>  	const char **raw;
>  	int nr;
> +	struct pathspec_item {
> +		int len;
> +	} *items;

Hmm... I would have expected to see

        struct pathspec_item {
                const char *pattern;
                int len;
        };
	struct pathspec {
        	struct pathspec_item *items;
		int nr;
	};

as you would be allocating a structure anyway, but persumably many places
take their input as a NULL terminated "char **" array, and keeping such an
array around as the "raw" field may be easier in refactoring.

Re: [PATCH 4/6] Convert struct diff_options to use struct pathspec

[Junio C Hamano]

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

> 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;

Just a mental note; we need to be careful not to destroy this structure
(i.e. freeing ids.diffopts.pathspec.items) when we are done with ids.

Nice code reduction ;-)

Re: [PATCH 5/6] tree_entry_interesting(): remove dependency on struct diff_options

[Junio C Hamano]

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

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

This does a bit more than that; it does not call tree_entry_extract()
anymore, and instead uses the knowledge of its underlying implementation.
The mode of the entry that is passed to S_ISDIR() check is not cleansed
with canon_mode() anymore.

I do not think these are necessarily bad changes, but they should be
documented.

Re: [PATCH 3/6] pathspec: cache string length when initialize pathspec

[Nguyen Thai Ngoc Duy]

2010/9/28 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> Subject: Re: [PATCH 3/6] pathspec: cache string length when initialize pathspec
>
> s/initialize/initializing/;
>
>> This field will be used when tree_entry_interesting() is converted to
>> use struct pathspec. Currently it uses pathlens[] in struct
>> diff_options to avoid calculating string over and over again.
>>
>> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
>> ---
>>  cache.h |    3 +++
>>  dir.c   |   11 ++++++++++-
>>  2 files changed, 13 insertions(+), 1 deletions(-)
>>
>> diff --git a/cache.h b/cache.h
>> index 6227ddb..045c9fc 100644
>> --- a/cache.h
>> +++ b/cache.h
>> @@ -495,6 +495,9 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
>>  struct pathspec {
>>       const char **raw;
>>       int nr;
>> +     struct pathspec_item {
>> +             int len;
>> +     } *items;
>
> Hmm... I would have expected to see
>
>        struct pathspec_item {
>                const char *pattern;
>                int len;
>        };
>        struct pathspec {
>                struct pathspec_item *items;
>                int nr;
>        };
>
> as you would be allocating a structure anyway, but persumably many places
> take their input as a NULL terminated "char **" array, and keeping such an
> array around as the "raw" field may be easier in refactoring.

pathspec_item.pattern is added later on when I implement negative
pathspec so it's not too different from your expectation. "raw"
however is kept. The reason (again in my WIP negative pathspec) is
that I use "!" alone to denote a negative pathspec. So if user gives {
"foo", "!", "foo/bar", NULL }, "raw" will contain exactly that, but
there are only two pathspec_item for "foo" and "foo/bar" (with
negative flag set).
-- 
Duy

Re: [PATCH 0/6] Introduce pathspec struct

[Junio C Hamano]

Just a couple of quick notes.

 - I had to eject Bo's "log -L range path" series in order to push this
   out on 'pu' as the range stuff adds new callsites to the old pathspec
   API.

   This is tentative and does not mean Bo's series is getting rejected;
   I'd want to get its command line parsing around the pathnames fixed
   anyway but I suspect the affected codepath would overlap between the
   two series.  Help is appreciated.

 - I do not think either !pattern nor ^pattern is particularly a good way
   to express negative pathspecs.  My gut feeling is (I have not thought
   this through nor clearly enough; note the time of this message) that it
   would be the cleanest at the UI level to introduce negative patterns as
   arguments to a separate command line flag, e.g.

   $ git log --exclude "Doc*" master..pu -- '*.txt'
   $ git grep --exclude "t/" -e 'test .*-L' -- '*.sh'

 - David's "git grep --exclude-dir D" topic should be able to internally
   use the same negative pathspec mechanism.  At the command line level,
   it allows (and needs to allow) only the leading prefix (which is how
   GNU grep's --exclude-dir works), but it makes tons of sense for us to
   allow "--exclude $pattern" from the command line, and share the
   mechanism internally between the two.

[PATCH 2/6] diff-no-index: use diff_tree_setup_paths()

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

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

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

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

Re: [PATCH 0/6] Introduce pathspec struct

[Bo Yang]

2010/9/28 Junio C Hamano <gitster@pobox.com>:
> Just a couple of quick notes.
>
>  - I had to eject Bo's "log -L range path" series in order to push this
>   out on 'pu' as the range stuff adds new callsites to the old pathspec
>   API.
>
>   This is tentative and does not mean Bo's series is getting rejected;
>   I'd want to get its command line parsing around the pathnames fixed
>   anyway but I suspect the affected codepath would overlap between the
>   two series.  Help is appreciated.

Ah, it is not very astonished to see this series put into 'pu' since I
am not active these days. :)

Hmm, let me make a summary about the requirement for the pathname
command line options:
1. The syntax now 'git log <rev> -L l:m path1 -L l:m path2' got clash
with current git command line style 'git subcommand dash-option <rev>
path'. Since we support multiple paths with multiple ranges, I think
the best way to comply with git command line style is to change it to
'git log -L l:m path1 -L l:m path2 <rev>'.

2. The way I parse the command line should make a little change, that
in '-L' in callback to parse both range and path arguments.

That's it?

-- 
Regards!
Bo
----------------------------
My blog: http://blog.morebits.org
Why Git: http://www.whygitisbetterthanx.com/

Re: [PATCH 5/6] tree_entry_interesting(): remove dependency on struct diff_options

[Nguyen Thai Ngoc Duy]

On Tue, Sep 28, 2010 at 8:20 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> This function can be potentially used in more places than just
>> tree-diff.c. "struct diff_options" does not make much sense outside
>> diff_tree_sha1().
>
> This does a bit more than that; it does not call tree_entry_extract()
> anymore, and instead uses the knowledge of its underlying implementation.
> The mode of the entry that is passed to S_ISDIR() check is not cleansed
> with canon_mode() anymore.

Hmm.. missed that. Thanks for catching.
-- 
Duy

Re: [PATCH 0/6] Introduce pathspec struct

[Nguyen Thai Ngoc Duy]

2010/9/28 Junio C Hamano <gitster@pobox.com>:
> Just a couple of quick notes.
>
>  - I had to eject Bo's "log -L range path" series in order to push this
>   out on 'pu' as the range stuff adds new callsites to the old pathspec
>   API.
>
>   This is tentative and does not mean Bo's series is getting rejected;
>   I'd want to get its command line parsing around the pathnames fixed
>   anyway but I suspect the affected codepath would overlap between the
>   two series.  Help is appreciated.

I'll have a look.

>  - I do not think either !pattern nor ^pattern is particularly a good way
>   to express negative pathspecs.  My gut feeling is (I have not thought
>   this through nor clearly enough; note the time of this message) that it
>   would be the cleanest at the UI level to introduce negative patterns as
>   arguments to a separate command line flag, e.g.
>
>   $ git log --exclude "Doc*" master..pu -- '*.txt'
>   $ git grep --exclude "t/" -e 'test .*-L' -- '*.sh'

I was writing "but you would lose the ability to mix negative and
positive pathspecs together, something like 'exclude Documentation
except Documentation/technical'", but then we can have negative
excludes too:

$ git log --exclude Documentation --exclude "!Documentation/technical"
master..pu -- '*.txt'

does not sound too twisted to understand (I hope).

>  - David's "git grep --exclude-dir D" topic should be able to internally
>   use the same negative pathspec mechanism.  At the command line level,
>   it allows (and needs to allow) only the leading prefix (which is how
>   GNU grep's --exclude-dir works), but it makes tons of sense for us to
>   allow "--exclude $pattern" from the command line, and share the
>   mechanism internally between the two.

Yes, eventually. But
 - tree_entry_interesting() needs (a bit complex) rework to have
wildcard matching capability
 - then I am still not sure how negative pathspecs should be done properly

Both may take me weeks to come up with something sensible. If David
needs "git grep --exclude-dir" now, he should keep working on
builtin/grep.c as he's doing now (maybe change --exclude-dir to
--exclude). If my work on negative pathspec has a result, sure I will
remove pathspec_matches() from builtin/grep.c, but his work on the
command line interface _and tests_ won't be wasted.
-- 
Duy

Re: [PATCH 0/6] Introduce pathspec struct

[David Ripton]

On 09/28/10 04:37, Junio C Hamano wrote:

>   - David's "git grep --exclude-dir D" topic should be able to internally
>     use the same negative pathspec mechanism.  At the command line level,
>     it allows (and needs to allow) only the leading prefix (which is how
>     GNU grep's --exclude-dir works), but it makes tons of sense for us to
>     allow "--exclude $pattern" from the command line, and share the
>     mechanism internally between the two.

I don't think GNU grep's --exclude-dir only allows the leading prefix. 
Here the data directory is a level below the top, but --exclude-dir=data 
effectively excludes it:

$ grep -R behemoth_green *
Binary file slugathon/util/colors.pyc matches
slugathon/util/colors.py:    "behemoth_green": (2, 129, 2),
Binary file slugathon/data/creaturedata.pyc matches
slugathon/data/creaturedata.py:"Behemoth": ("Behemoths", 8, 3, 0, 0, 
"creature", 0, 0, 18, "behemoth_green"),
slugathon/data/creaturedata.py:"Cyclops": ("Cyclopes", 9, 2, 0, 0, 
"creature", 0, 0, 28, "behemoth_green"),

grep -R --exclude-dir=data behemoth_green *
Binary file slugathon/util/colors.pyc matches
slugathon/util/colors.py:    "behemoth_green": (2, 129, 2),

IMO it's useful to allow excluding directories below the top like it 
currently does, because some projects might have a bunch of noise 
directories with the same name, and having --exclude-dir exclude them 
all would be handy.

That said, if consistency with other exclude patterns is more important 
than this use case, fine with me.

-- 
David Ripton    dripton@ripton.net

Re: [PATCH 0/6] Introduce pathspec struct

[Junio C Hamano]

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

>>  $ git log --exclude "Doc*" master..pu -- '*.txt'
>>  $ git grep --exclude "t/" -e 'test .*-L' -- '*.sh'
>
> I was writing "but you would lose the ability to mix negative and
> positive pathspecs together, something like 'exclude Documentation
> except Documentation/technical'",...

I think that is way overengineered.  We _could_ make the expressions
arbitrarily complex and hard to use by using irregular syntax tricks, but
let's not go there.  Let's just keep things simple and usable instead.

 * Without pathspec, everything is included;
 * pathspecs will filter everything that do not match;
 * --exclude also filters what matches them from the remainder.

So...

> $ git log --exclude Documentation --exclude "!Documentation/technical"
> master..pu -- '*.txt'
>
> does not sound too twisted to understand (I hope).

...I would not vote for this.

> ... If David
> needs "git grep --exclude-dir" now, he should keep working on
> builtin/grep.c as he's doing now (maybe change --exclude-dir to
> --exclude).

That's not what I am saying.

Because --exclude-dir is a special case of --exclude, it would be an
efficient solution _if_ we can externally keep the command line option
compatible with GNU grep as a syntax sugar, and turn it into something
else internally that can be passed to your "pathspec with negative"
engine.


> ..., but his work on the
> command line interface _and tests_ won't be wasted.

Yup.

Re: [PATCH 0/6] Introduce pathspec struct

[Junio C Hamano]

David Ripton <dripton@ripton.net> writes:

> On 09/28/10 04:37, Junio C Hamano wrote:
>
>>   - David's "git grep --exclude-dir D" topic should be able to internally
>>     use the same negative pathspec mechanism.  At the command line level,
>>     it allows (and needs to allow) only the leading prefix (which is how
>>     GNU grep's --exclude-dir works), but it makes tons of sense for us to
>>     allow "--exclude $pattern" from the command line, and share the
>>     mechanism internally between the two.
>
> I don't think GNU grep's --exclude-dir only allows the leading
> prefix.

Heh, I was half expecting to hear that after I wrote it ;-) What I meant
was "pattern matches against the leading path, excluding the basename
part" (as the option is exclude-DIR, that is more or less by definition).

Re: [PATCH 1/6] Add struct pathspec

[yj2133011]

This struct for now is just a wrapper for the current pathspec form:
const char **. It is intended to be extended with more useful
pathspec-related information over time.

The data structure for passing pathspec around remains const char **,
struct pathspec will be initialized locally to be used and destroyed.
Hopefully all pathspec related code will be gradually migrated to pass
this struct instead.


-----
The voice input and output is very good in this 
http://www.tomtop.com/black-ps3-wireless-bluetooth-headset-for-playstation-3.html?aid=z
Wireless PS3 Headset . It is compatible with all PS3 games.Buy from Reliable 
http://www.tomtop.com/google-android-7-notebook-3g-tablet-pc-umpc-wifi-mid-pda.html?aid=z
Google Android PC  apad Wholesalers.
-- 
View this message in context: http://git.661346.n2.nabble.com/PATCH-0-6-Introduce-pathspec-struct-tp5548679p5582619.html
Sent from the git mailing list archive at Nabble.com.