[PATCH 0/5] Globbing support in diff family

[PATCH 0/5] Globbing support in diff family

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

This is on top of the pathspec struct series

http://mid.gmane.org/1284938514-16663-1-git-send-email-pclouds@gmail.com

One question to document experts: where to document "pathspec", git.txt?

Nguyễn Thái Ngọc Duy (5):
  pathspec: mark wildcard pathspecs from the beginning
  pathspec: add tree_recursive_diff parameter
  tree_entry_interesting: turn to match_pathspec if wildcard is present
  Convert ce_path_match() to use struct pathspec
  ce_path_match: drop prefix matching in favor of match_pathspec

 builtin/update-index.c   |    8 ++++++--
 cache.h                  |    5 ++++-
 diff-lib.c               |   10 ++++++++--
 dir.c                    |    7 ++++++-
 preload-index.c          |    5 ++++-
 read-cache.c             |   25 ++-----------------------
 revision.c               |    5 ++++-
 t/t4010-diff-pathspec.sh |   23 +++++++++++++++++++++++
 tree-diff.c              |    1 +
 tree-walk.c              |   18 ++++++++++++++++++
 wt-status.c              |    5 ++++-
 11 files changed, 80 insertions(+), 32 deletions(-)

[PATCH 1/5] pathspec: mark wildcard pathspecs from the beginning

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

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 match_pathspec() should be converted to use this as well. Not now
 though.

 cache.h |    2 ++
 dir.c   |    7 ++++++-
 2 files changed, 8 insertions(+), 1 deletions(-)

diff --git a/cache.h b/cache.h
index 045c9fc..7a3e0a0 100644
--- a/cache.h
+++ b/cache.h
@@ -495,8 +495,10 @@ extern int ie_modified(const struct index_state *, struct cache_entry *, struct
 struct pathspec {
 	const char **raw;
 	int nr;
+	int has_wildcard:1;
 	struct pathspec_item {
 		int len;
+		int has_wildcard:1;
 	} *items;
 };
 
diff --git a/dir.c b/dir.c
index 80b2df2..a44c7b3 100644
--- a/dir.c
+++ b/dir.c
@@ -1088,7 +1088,12 @@ int init_pathspec(struct pathspec *pathspec, const char **paths)
 
 	pathspec->items = xmalloc(sizeof(struct pathspec_item)*pathspec->nr);
 	for (i = 0; i < pathspec->nr; i++) {
-		pathspec->items[i].len = strlen(paths[i]);
+		struct pathspec_item *item = pathspec->items+i;
+
+		item->len = strlen(paths[i]);
+		item->has_wildcard = !no_wildcard(paths[i]);
+		if (item->has_wildcard)
+			pathspec->has_wildcard = 1;
 	}
 	return 0;
 }
-- 
1.7.1.rc1.70.g788ca

[PATCH 2/5] pathspec: add tree_recursive_diff parameter

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

When wildcard match is implemented, a full path is needed to do final
match. What type of diff_tree is performed determines how to treat
directories:

 - If it's recursive diff, directories are just an intermediate step.
   All path must end with a file name. Thus, directories will be
   unconditionally matched.

 - If it's non-recursive, directories are treated like files and is
   matched against pathspect as full path.

Strictly speaking, this should be a new parameter to
tree_entry_interesting(). But I don't feel like chaning
tree_entry_interesting() too often.

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

diff --git a/cache.h b/cache.h
index 7a3e0a0..dc54d16 100644
--- a/cache.h
+++ b/cache.h
@@ -496,6 +496,7 @@ struct pathspec {
 	const char **raw;
 	int nr;
 	int has_wildcard:1;
+	int tree_recursive_diff:1;
 	struct pathspec_item {
 		int len;
 		int has_wildcard:1;
diff --git a/tree-diff.c b/tree-diff.c
index 50d7e6d..7e58f54 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -170,6 +170,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2, const char *base, stru
 {
 	int baselen = strlen(base);
 
+	opt->pathspec.tree_recursive_diff = DIFF_OPT_TST(opt, RECURSIVE);
 	for (;;) {
 		if (DIFF_OPT_TST(opt, QUICK) &&
 		    DIFF_OPT_TST(opt, HAS_CHANGES))
-- 
1.7.1.rc1.70.g788ca

[PATCH 3/5] tree_entry_interesting: turn to match_pathspec if wildcard is present

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

A pathspec with wildcard usually requires full path to do
matching. When full path is found, match_pathspec() can do the job
pretty well (actually it can utilize pathspec_item.has_wildcard, but
that's another matter).

So if tree_entry_interesting() finds that there is wildcard in any
pathspec, it just skips all of its optimizations, tries to make full
path and pass to match_pathspec().

The implementation is pretty naive. Maybe with some pattern analysis,
we can do some early tree cutting.

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

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 01168ea..bc8c9bd 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -2,6 +2,7 @@
 #include "tree-walk.h"
 #include "unpack-trees.h"
 #include "tree.h"
+#include "dir.h"
 
 static const char *get_mode(const char *str, unsigned int *modep)
 {
@@ -478,6 +479,23 @@ int tree_entry_interesting(const struct name_entry *entry,
 
 	pathlen = tree_entry_len(entry->path, entry->sha1);
 
+	if (ps->has_wildcard) {
+		static char full_path[PATH_MAX];
+
+		/*
+		 * If it's recursive diff, directories are
+		 * intermediate step before ending up to a file.
+		 * Let it pass and we can match the files within
+		 * later.
+		 */
+		if (ps->tree_recursive_diff && S_ISDIR(entry->mode))
+			return 1;
+
+		memcpy(full_path, base, baselen);
+		memcpy(full_path+baselen, entry->path, pathlen+1);
+		return match_pathspec(ps->raw, full_path, baselen+pathlen, 0, NULL) > 0;
+	}
+
 	for (i = 0; i < ps->nr; i++) {
 		const char *match = ps->raw[i];
 		int matchlen = ps->items[i].len;
-- 
1.7.1.rc1.70.g788ca

[PATCH 4/5] 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           |    8 +++++---
 revision.c             |    5 ++++-
 wt-status.c            |    5 ++++-
 7 files changed, 32 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 dc54d16..bf50603 100644
--- a/cache.h
+++ b/cache.h
@@ -505,7 +505,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..918a90c 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -683,17 +683,19 @@ 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 **p;
 	int len;
 
-	if (!pathspec)
+	if (!pathspec || !pathspec->nr)
 		return 1;
 
 	len = ce_namelen(ce);
 	name = ce->name;
-	while ((match = *pathspec++) != NULL) {
+	p = pathspec->raw;
+	while ((match = *p++) != 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.1.rc1.70.g788ca

[PATCH 5/5] ce_path_match: drop prefix matching in favor of match_pathspec

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

ce_path_match() and tree_entry_interesting() are two functions that do
entry filtering when traversing trees. Now that
tree_entry_interesting() understands wildcard, ce_path_match() can
just use match_pathspec() to also understand wildcard.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 read-cache.c             |   25 +------------------------
 t/t4010-diff-pathspec.sh |    9 +++++++++
 2 files changed, 10 insertions(+), 24 deletions(-)

diff --git a/read-cache.c b/read-cache.c
index 918a90c..c67d9e0 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -685,30 +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 **p;
-	int len;
-
-	if (!pathspec || !pathspec->nr)
-		return 1;
-
-	len = ce_namelen(ce);
-	name = ce->name;
-	p = pathspec->raw;
-	while ((match = *p++) != 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(pathspec->raw, ce->name, ce_namelen(ce), 0, NULL) > 0;
 }
 
 /*
diff --git a/t/t4010-diff-pathspec.sh b/t/t4010-diff-pathspec.sh
index 4b120f8..d50fd2d 100755
--- a/t/t4010-diff-pathspec.sh
+++ b/t/t4010-diff-pathspec.sh
@@ -55,6 +55,15 @@ test_expect_success \
     'git diff-index --cached $tree -- file0 >current &&
      compare_diff_raw current expected'
 
+cat >expected.template <<\EOF
+:100644 100644 766498d93a4b06057a8e49d23f4068f1170ff38f 0a41e115ab61be0328a19b29f18cdcb49338d516 M	path1/file1
+EOF
+test_expect_success 'diff-index with wildcard' '
+	git diff-index --cached $tree -- "*1" >current &&
+	cp expected.template expected &&
+	compare_diff_raw current expected
+'
+
 cat >expected <<\EOF
 EOF
 test_expect_success \
-- 
1.7.1.rc1.70.g788ca

Re: [PATCH 2/5] pathspec: add tree_recursive_diff parameter

[Junio C Hamano]

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

> When wildcard match is implemented, a full path is needed to do final
> match. What type of diff_tree is performed determines how to treat
> directories:
>
>  - If it's recursive diff, directories are just an intermediate step.
>    All path must end with a file name. Thus, directories will be
>    unconditionally matched.

Hmm, I am not sure what you mean by this.  If the pathspec says a/b*/c,
you are in "a" and are deciding if you should descend to its subdirectory,
then you would surely want to be able to say:

 (1) Ah, the subdirectory I am looking at is "bar" and it does match "b*".
     It might contain "c"; I should descend into it.

 (2) Nope, the subdirectory I am looking at is "frotz" and it can never
     match "b*", so there is no point recursing into it.

Re: [PATCH 2/5] pathspec: add tree_recursive_diff parameter

[Nguyen Thai Ngoc Duy]

2010/9/28 Junio C Hamano <gitster@pobox.com>:
> Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:
>
>> When wildcard match is implemented, a full path is needed to do final
>> match. What type of diff_tree is performed determines how to treat
>> directories:
>>
>>  - If it's recursive diff, directories are just an intermediate step.
>>    All path must end with a file name. Thus, directories will be
>>    unconditionally matched.
>
> Hmm, I am not sure what you mean by this.  If the pathspec says a/b*/c,
> you are in "a" and are deciding if you should descend to its subdirectory,
> then you would surely want to be able to say:
>
>  (1) Ah, the subdirectory I am looking at is "bar" and it does match "b*".
>     It might contain "c"; I should descend into it.
>
>  (2) Nope, the subdirectory I am looking at is "frotz" and it can never
>     match "b*", so there is no point recursing into it.
>

I did not go that far, trying to analyse the pattern. When I wrote
"immediate step" I was thinking of "*foo" pattern, which effectively
means descending to any reachable directories because '*' matches
slashes too. I think that's the worst case.

Anyway I did not know that I could borrow some optimizations from
pathspec_matches() in builtin/grep.c.
-- 
Duy

Re: [PATCH 2/5] pathspec: add tree_recursive_diff parameter

[Junio C Hamano]

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

> 2010/9/28 Junio C Hamano <gitster@pobox.com>:
>> Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:
>> ...
>>>  - If it's recursive diff, directories are just an intermediate step.
>>>    All path must end with a file name. Thus, directories will be
>>>    unconditionally matched.
>>
>> Hmm, I am not sure what you mean by this.  If the pathspec says a/b*/c,
>> you are in "a" and are deciding if you should descend to its subdirectory,
>> then you would surely want to be able to say:
>>
>>  (1) Ah, the subdirectory I am looking at is "bar" and it does match "b*".
>>      It might contain "c"; I should descend into it.
>>
>>  (2) Nope, the subdirectory I am looking at is "frotz" and it can never
>>      match "b*", so there is no point recursing into it.
>
> I did not go that far, trying to analyse the pattern. When I wrote
> "immediate step" I was thinking of "*foo" pattern, which effectively
> means descending to any reachable directories because '*' matches
> slashes too. I think that's the worst case.
>
> Anyway I did not know that I could borrow some optimizations from
> pathspec_matches() in builtin/grep.c.

As you noticed, over time we have polished our re-implementations of the
pathspec logic to avoid needlessly descending into subdirectories, and the
one in the grep may be the latest incarnation of it.  The logic that uses
the path_simplify structure in dir.c may also offer you some inspirations.

Note that the worst case will fall out as a natural consequence of doing
the fallback in the dumb and simple way, so you do not have to worry too
much about it ;-)  I would prefer to see the new, consolidated logic to at
least know the easy optimizations we already have.

Thanks.