[PATCH v3] grep: Add --max-depth option.

[PATCH v3] grep: Add --max-depth option.

[Michał Kiedrowicz]

Sometimes it is useful to grep directories non-recursive. E.g. if one
wants to look for all files in main directory, but not in any subdirectory.
Or in Documentation/, but not in Documentation/technical/ and so on.

This patch adds support for --max-depth <depth> option to git-grep. If it is
set, git-grep descends at most <depth> levels of directories below paths
specified on command line.

Note that if path specified on command line contains wildcards, option
--max-depth makes no sense, i.e.

$ git grep -l --max-depth 0 GNU -- 'contrib/*'

(note the quotes) will search all files in contrib/, even in
subdirectories, because '*' matches all files.

Documentation updates, bash-completion and simple test cases are also
provided.

Signed-off-by: Michał Kiedrowicz <michal.kiedrowicz@gmail.com>
---
 Documentation/git-grep.txt             |    5 +++
 builtin-grep.c                         |   55 ++++++++++++++++++++++++++------
 contrib/completion/git-completion.bash |    1 +
 grep.h                                 |    1 +
 t/t7002-grep.sh                        |   51 +++++++++++++++++++++++++++++-
 5 files changed, 102 insertions(+), 11 deletions(-)

diff --git a/Documentation/git-grep.txt b/Documentation/git-grep.txt
index b753c9d..faa92d1 100644
--- a/Documentation/git-grep.txt
+++ b/Documentation/git-grep.txt
@@ -17,6 +17,7 @@ SYNOPSIS
 	   [-l | --files-with-matches] [-L | --files-without-match]
 	   [-z | --null]
 	   [-c | --count] [--all-match]
+	   [--max-depth <depth>]
 	   [--color | --no-color]
 	   [-A <post-context>] [-B <pre-context>] [-C <context>]
 	   [-f <file>] [-e] <pattern>
@@ -47,6 +48,10 @@ OPTIONS
 -I::
 	Don't match the pattern in binary files.
 
+--max-depth <depth>::
+	Descend at most <depth> levels of directories below paths specified on
+	command line. Negative value means no limit.
+
 -w::
 --word-regexp::
 	Match the pattern only at word boundary (either begin at the
diff --git a/builtin-grep.c b/builtin-grep.c
index f477659..2ed2507 100644
--- a/builtin-grep.c
+++ b/builtin-grep.c
@@ -52,26 +52,58 @@ static int grep_config(const char *var, const char *value, void *cb)
 	return git_color_default_config(var, value, cb);
 }
 
+static inline int count_chars(const char *str, char c)
+{
+	int num = 0;
+
+	if (!str)
+		return 0;
+
+	for (; *str; str++)
+		if (*str == c)
+			num++;
+	return num;
+}
+
+static inline int accept_subdir(const char *path, int max_depth)
+{
+	return max_depth < 0 || count_chars(path, '/') <= max_depth;
+}
+
+/*
+ * Return non-zero if name is a subdirectory of match and is not too deep.
+ */
+static inline 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)
+static int pathspec_matches(const char **paths, const char *name, int max_depth)
 {
 	int namelen, i;
 	if (!paths || !*paths)
-		return 1;
+		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 (!matchlen ||
-		    ((matchlen <= namelen) &&
-		     !strncmp(name, match, matchlen) &&
-		     (match[matchlen-1] == '/' ||
-		      name[matchlen] == '\0' || name[matchlen] == '/')))
+		if (is_subdir(name, namelen, match, matchlen, max_depth))
 			return 1;
 		if (!fnmatch(match, name, 0))
 			return 1;
@@ -421,7 +453,7 @@ static int external_grep(struct grep_opt *opt, const char **paths, int cached)
 		int kept;
 		if (!S_ISREG(ce->ce_mode))
 			continue;
-		if (!pathspec_matches(paths, ce->name))
+		if (!pathspec_matches(paths, ce->name, opt->max_depth))
 			continue;
 		name = ce->name;
 		if (name[0] == '-') {
@@ -478,7 +510,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))
+		if (!pathspec_matches(paths, ce->name, opt->max_depth))
 			continue;
 		/*
 		 * If CE_VALID is on, we assume worktree file and its cache entry
@@ -538,7 +570,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))
+		if (!pathspec_matches(paths, down, opt->max_depth))
 			;
 		else if (S_ISREG(entry.mode))
 			hit |= grep_sha1(opt, entry.sha1, pathbuf.buf, tn_len);
@@ -692,6 +724,8 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 		OPT_SET_INT('I', NULL, &opt.binary,
 			"don't match patterns in binary files",
 			GREP_BINARY_NOMATCH),
+		OPT_INTEGER(0, "max-depth", &opt.max_depth,
+				"descend at most <n> levels"),
 		OPT_GROUP(""),
 		OPT_BIT('E', "extended-regexp", &opt.regflags,
 			"use extended POSIX regular expressions", REG_EXTENDED),
@@ -768,6 +802,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
 	opt.pathname = 1;
 	opt.pattern_tail = &opt.pattern_list;
 	opt.regflags = REG_NEWLINE;
+	opt.max_depth = -1;
 
 	strcpy(opt.color_match, GIT_COLOR_RED GIT_COLOR_BOLD);
 	opt.color = -1;
diff --git a/contrib/completion/git-completion.bash b/contrib/completion/git-completion.bash
index 887731e..fb05c48 100755
--- a/contrib/completion/git-completion.bash
+++ b/contrib/completion/git-completion.bash
@@ -1036,6 +1036,7 @@ _git_grep ()
 			--extended-regexp --basic-regexp --fixed-strings
 			--files-with-matches --name-only
 			--files-without-match
+			--max-depth
 			--count
 			--and --or --not --all-match
 			"
diff --git a/grep.h b/grep.h
index f00db0e..28e6b2a 100644
--- a/grep.h
+++ b/grep.h
@@ -79,6 +79,7 @@ struct grep_opt {
 	int pathname;
 	int null_following_name;
 	int color;
+	int max_depth;
 	int funcname;
 	char color_match[COLOR_MAXLEN];
 	const char *color_external;
diff --git a/t/t7002-grep.sh b/t/t7002-grep.sh
index b13aa7e..b4709e2 100755
--- a/t/t7002-grep.sh
+++ b/t/t7002-grep.sh
@@ -25,13 +25,17 @@ test_expect_success setup '
 		echo foo mmap bar_mmap
 		echo foo_mmap bar mmap baz
 	} >file &&
+	echo vvv >v &&
 	echo ww w >w &&
 	echo x x xx x >x &&
 	echo y yy >y &&
 	echo zzz > z &&
 	mkdir t &&
 	echo test >t/t &&
-	git add file w x y z t/t hello.c &&
+	echo vvv >t/v &&
+	mkdir t/a &&
+	echo vvv >t/a/v &&
+	git add . &&
 	test_tick &&
 	git commit -m initial
 '
@@ -132,6 +136,51 @@ do
 		! git grep -c test $H | grep /dev/null
         '
 
+	test_expect_success "grep --max-depth -1 $L" '
+		{
+			echo ${HC}t/a/v:1:vvv
+			echo ${HC}t/v:1:vvv
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth -1 -n -e vvv $H >actual &&
+		test_cmp expected actual
+	'
+
+	test_expect_success "grep --max-depth 0 $L" '
+		{
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth 0 -n -e vvv $H >actual &&
+		test_cmp expected actual
+	'
+
+	test_expect_success "grep --max-depth 0 -- '*' $L" '
+		{
+			echo ${HC}t/a/v:1:vvv
+			echo ${HC}t/v:1:vvv
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth 0 -n -e vvv $H -- "*" >actual &&
+		test_cmp expected actual
+	'
+
+	test_expect_success "grep --max-depth 1 $L" '
+		{
+			echo ${HC}t/v:1:vvv
+			echo ${HC}v:1:vvv
+		} >expected &&
+		git grep --max-depth 1 -n -e vvv $H >actual &&
+		test_cmp expected actual
+	'
+
+	test_expect_success "grep --max-depth 0 -- t $L" '
+		{
+			echo ${HC}t/v:1:vvv
+		} >expected &&
+		git grep --max-depth 0 -n -e vvv $H -- t >actual &&
+		test_cmp expected actual
+	'
+
 done
 
 cat >expected <<EOF
-- 
1.6.3.3

Re: [PATCH v3] grep: Add --max-depth option.

[Stephen Boyd]

Michał Kiedrowicz wrote:
>
> Signed-off-by: Michał Kiedrowicz <michal.kiedrowicz@gmail.com>
> ---

Would have been nice to see a comment here saying what's changed since
v2. Looks like you renamed it to --max-depth, added some new inline
functions, and fixed up the test style issues?

>
> diff --git a/builtin-grep.c b/builtin-grep.c
> index f477659..2ed2507 100644
> --- a/builtin-grep.c
> +++ b/builtin-grep.c
> @@ -52,26 +52,58 @@ static int grep_config(const char *var, const char *value, void *cb)
>  	return git_color_default_config(var, value, cb);
>  }
>  
> +static inline int count_chars(const char *str, char c)
> +{
> +	int num = 0;
> +
> +	if (!str)
> +		return 0;
> +
> +	for (; *str; str++)
> +		if (*str == c)
> +			num++;
> +	return num;
> +}
> +
> +static inline int accept_subdir(const char *path, int max_depth)
> +{
> +	return max_depth < 0 || count_chars(path, '/') <= max_depth;
> +}
> +

If count_chars() is only used by accept_subdir() why not just manually
inline the loop in accept_subdir()? Plus, you rightly return early if
max_depth is -1, but what if max_depth is something small like 1? Then
you still count all the slashes when you could return upon seeing the
second slash.

>
> @@ -692,6 +724,8 @@ int cmd_grep(int argc, const char **argv, const char *prefix)
>  		OPT_SET_INT('I', NULL, &opt.binary,
>  			"don't match patterns in binary files",
>  			GREP_BINARY_NOMATCH),
> +		OPT_INTEGER(0, "max-depth", &opt.max_depth,
> +				"descend at most <n> levels"),

Please use OPTION_INTEGER here so you can use "<depth>" instead of
"<n>". This will make it more consistent with the documentation.

Re: [PATCH v3] grep: Add --max-depth option.

[Michał Kiedrowicz]

Stephen Boyd <bebarino@gmail.com> wrote:

> Michał Kiedrowicz wrote:
> >
> > Signed-off-by: Michał Kiedrowicz <michal.kiedrowicz@gmail.com>
> > ---
> 
> Would have been nice to see a comment here saying what's changed since
> v2. 

Sorry, I did that when I sent v2, but this time when I remembered about
ti, it was already too late :)

> Looks like you renamed it to --max-depth, added some new inline
> functions, and fixed up the test style issues?
> 

Yes, I followed your and René's suggestions and added ability to
specify max number of levels.

> >
> > diff --git a/builtin-grep.c b/builtin-grep.c
> > index f477659..2ed2507 100644
> > --- a/builtin-grep.c
> > +++ b/builtin-grep.c
> > @@ -52,26 +52,58 @@ static int grep_config(const char *var, const
> > char *value, void *cb) return git_color_default_config(var, value,
> > cb); }
> >  
> > +static inline int count_chars(const char *str, char c)
> > +{
> > +	int num = 0;
> > +
> > +	if (!str)
> > +		return 0;
> > +
> > +	for (; *str; str++)
> > +		if (*str == c)
> > +			num++;
> > +	return num;
> > +}
> > +
> > +static inline int accept_subdir(const char *path, int max_depth)
> > +{
> > +	return max_depth < 0 || count_chars(path, '/') <=
> > max_depth; +}
> > +
> 
> If count_chars() is only used by accept_subdir() why not just manually
> inline the loop in accept_subdir()? Plus, you rightly return early if
> max_depth is -1, but what if max_depth is something small like 1? Then
> you still count all the slashes when you could return upon seeing the
> second slash.

Yep, that's true. My primary reason for writing two functions was to
split logic in accept_subdir() from dull counting in count_chars().
Also, count_chars() is a generic function and may be used anywhere.

> 
> >
> > @@ -692,6 +724,8 @@ int cmd_grep(int argc, const char **argv, const
> > char *prefix) OPT_SET_INT('I', NULL, &opt.binary,
> >  			"don't match patterns in binary files",
> >  			GREP_BINARY_NOMATCH),
> > +		OPT_INTEGER(0, "max-depth", &opt.max_depth,
> > +				"descend at most <n> levels"),
> 
> Please use OPTION_INTEGER here so you can use "<depth>" instead of
> "<n>". This will make it more consistent with the documentation.

I can do that.

Thanks for your comments.

Michał Kiedrowicz

Re: [PATCH v3] grep: Add --max-depth option.

[Junio C Hamano]

Thanks for a review.  With the suggested changes the patch looks better.

I had to wonder what would happen when you give an input like this,
though:

    $ git grep --max-depth=1 t Documentation/howto

If you look at the way the loop in pathspec_matches() is structured, it
becomes clear that the depth limit is applied independently to each of the
pathspecs given on the command line, and re-reading the description of the
option in the documentation _with_ that knowledge it becomes obvious what
should happen, but I couldn't figure it out before looking at the code.
Perhaps the documentation needs a bit more verbosity?  I dunno.