Re: [PATCH nd/attr-match-optim-more 2/2] attr: more matching optimizations from .gitignore

Nguyễn Thái Ngọc Duy  [off-list ref] writes:

.gitattributes and .gitignore share the same pattern syntax but
has separate matching implementation. Over the years, ignore's
implementation accumulates more optimizations while attr's stays
the same.

This patch adds those optimizations to attr. Basically it tries to
avoid fnmatch as much as possible in favor of strncmp.

A few notes from this work is put in the documentation:

* "!pattern" syntax is not supported in .gitattributes. Negative
  patterns may work well for a single attribute like .gitignore. It's
  confusing in .gitattributes are many attributes can be
  set/unset/undefined at using the same pattern.

I think the above misses the point.

Imagine if we allowed only one attribute per line, instead of
multiple attributes on one line.
    
 - If you want to unset the attribute, you would write "path -attr".

 - If you want to reset the attribute to unspecified, you would
   write "path !attr".

Both are used in conjunction with some other (typically more
generic) pattern that sets, sets to a value, and/or unsets the
attribute, to countermand its effect.

If you were to allow "!path attr", what does it mean?  It obviously
is not about setting the attr to true or to a string value, but is
it countermanding an earlier set and telling us to unset the attr,
or make the attr unspecified?

That is the ambiguity issue "!pattern" syntax would introduce if it
were to be allowed in the attributes.  I think "multiple attributes
on the same line" is a red herring.

* we support attaching attributes to directories at the syntax
  level, but we do not really attach attributes on directory or use
  them.

I would say "... but we do not currently use attributes on
directories."

Symbolic links?

I would strongly suggest dropping "Only ... can be...".  You can
specify attributes to anything and check with "check-attr".  It is
just that core part does not have anything that pays attention to
attributes given to directories in the current codebase.

OK (I am debating myself if it helps the readers if we said why it
is forbidden to write such).

This is inherited from the original code, but *res is calloc(3)ed
so the above memcpy() automatically NUL terminates this string.

At some point, we should rename strcmp_icase and strncmp_icase to
make it clear that

 (1) they are not about "strings"; and
 (2) icase is not always in effect.

They are about comparing pathnames and that is the reason why
depending on core.ignorecase settings we sometimes do _icase()
comparison.  The same issue is shared with fnmatch_icase() but
"fnmatch_" prefix hints that the helper is not about matching
general strings so it is with lessor problem compared with other
two.

+		if (pat->flags & EXC_FLAG_ENDSWITH &&
+		    pat->patternlen - 1 <= pathlen &&
+		    !strcmp_icase(pattern + 1, pathname +
+				  pathlen - pat->patternlen + 1))
+			return 1;
+
 		return (fnmatch_icase(pattern, basename, 0) == 0);
 	}
 	/*
 	 * match with FNM_PATHNAME; the pattern has base implicitly
 	 * in front of it.
 	 */
-	if (*pattern == '/')
+	if (*pattern == '/') {
 		pattern++;
+		prefix--;
+	}
+
+	/*
+	 * note: unlike excluded_from_list, baselen here does not
+	 * contain the trailing slash
+	 */
+
 	if (pathlen < baselen ||
 	    (baselen && pathname[baselen] != '/') ||
 	    strncmp(pathname, base, baselen))

This is probably strncmp_icase(), which is to be renamed to
something more sensible.

 		return 0;
-	if (baselen != 0)
-		baselen++;
-	return fnmatch_icase(pattern, pathname + baselen, FNM_PATHNAME) == 0;
+
+	namelen = baselen ? pathlen - baselen - 1 : pathlen;

I think this "- 1" is what the above "note: unlike excluded_from..."
refers to, but then isn't a same adjustment necessary to the "if"
condition we see above that compares pathlen and baselen???

+	name = pathname + pathlen - namelen;
+
+	/* if the non-wildcard part is longer than the remaining
+	   pathname, surely it cannot match */

Style.

+	if (!namelen || prefix > namelen)
+		return 0;
+
+	return fnmatch_icase(pattern, name, FNM_PATHNAME) == 0;
 }

Am 10/9/2012 7:08, schrieb Junio C Hamano:

Imagine if we allowed only one attribute per line, instead of
multiple attributes on one line.
    
 - If you want to unset the attribute, you would write "path -attr".

 - If you want to reset the attribute to unspecified, you would
   write "path !attr".

Both are used in conjunction with some other (typically more
generic) pattern that sets, sets to a value, and/or unsets the
attribute, to countermand its effect.

If you were to allow "!path attr", what does it mean?  It obviously
is not about setting the attr to true or to a string value, but is
it countermanding an earlier set and telling us to unset the attr,
or make the attr unspecified?

If I have at the toplevel:

  *.txt  whitespace=tabwidth=4

and in a subdirectory

  *.txt  whitespace=tabwidth=8
  !README.txt

it could be interpreted as "do not apply *.txt to REAME.txt in this
subdirectory". That is, it does not countermand some _particular_
attribute setting, but says "use the attributes collected elsewhere".

-- Hannes

.gitattributes and .gitignore share the same pattern syntax but has
separate matching implementation. Over the years, ignore's
implementation accumulates more optimizations while attr's stays the
same.

This patch adds those optimizations to attr. Basically it tries to
avoid fnmatch as much as possible in favor of strncmp.

A few notes from this work is put in the documentation:

* "!pattern" syntax is not supported in .gitattributes as it's not
  clear what it means (e.g. "!path attr" is about unsetting attr, or
  undefining it..)

* patterns applying to directories

Signed-off-by: Nguyễn Thái Ngọc Duy <redacted>
---
 How about this? Diff from the previous version:

   diff --git a/Documentation/gitattributes.txt b/Documentation/gitattributes.txt
   index cc2ff1d..9a0ed19 100644
   --- a/Documentation/gitattributes.txt
   +++ b/Documentation/gitattributes.txt
   @@ -23,7 +23,7 @@ Each line in `gitattributes` file is of form:
    That is, a pattern followed by an attributes list,
    separated by whitespaces.  When the pattern matches the
    path in question, the attributes listed on the line are given to
   -the path. Only files can be attached attributes to.
   +the path.
    
    Each attribute can be in one of these states for a given path:
    
   @@ -58,6 +58,13 @@ attribute.  The rules how the pattern matches paths are the
    same as in `.gitignore` files; see linkgit:gitignore[5].
    Unlike `.gitignore`, negative patterns are not supported.
    
   +Note that if a .gitignore rule matches a directory, the directory
   +is ignored, which may be seen as assigning "ignore" attribute the
   +directory and all files and directories inside. However, if a
   +.gitattributes rule matches a directory, it manipulates
   +attributes on that directory only, not files and directories
   +inside.
   +
    When deciding what attributes are assigned to a path, git
    consults `$GIT_DIR/info/attributes` file (which has the highest
    precedence), `.gitattributes` file in the same directory as the
   diff --git a/attr.c b/attr.c
   index 7e85f82..4faf1ff 100644
   --- a/attr.c
   +++ b/attr.c
   @@ -250,7 +250,6 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,
    	else {
    		char *p = (char *)&(res->state[num_attr]);
    		memcpy(p, name, namelen);
   -		p[namelen] = 0;
    		res->u.pat.pattern = p;
    		parse_exclude_pattern(&res->u.pat.pattern,
    				      &res->u.pat.patternlen,
   @@ -690,16 +689,18 @@ static int path_matches(const char *pathname, int pathlen,
    	 * contain the trailing slash
    	 */
    
   -	if (pathlen < baselen ||
   +	if (pathlen < baselen + 1 ||
    	    (baselen && pathname[baselen] != '/') ||
   -	    strncmp(pathname, base, baselen))
   +	    strncmp_icase(pathname, base, baselen))
    		return 0;
    
    	namelen = baselen ? pathlen - baselen - 1 : pathlen;
    	name = pathname + pathlen - namelen;
    
   -	/* if the non-wildcard part is longer than the remaining
   -	   pathname, surely it cannot match */
   +	/*
   +	 * if the non-wildcard part is longer than the remaining
   +	 * pathname, surely it cannot match
   +	 */
    	if (!namelen || prefix > namelen)
    		return 0;
 

 Documentation/gitattributes.txt |  8 +++++
 attr.c                          | 72 +++++++++++++++++++++++++++++++++--------
 dir.c                           |  8 ++---
 dir.h                           |  1 +
 t/t0003-attributes.sh           | 14 ++++++++
 5 files changed, 86 insertions(+), 17 deletions(-)

diff --git a/Documentation/gitattributes.txt b/Documentation/gitattributes.txt
index 80120ea..9a0ed19 100644
--- a/Documentation/gitattributes.txt
+++ b/Documentation/gitattributes.txt

@@ -56,6 +56,14 @@ When more than one pattern matches the path, a later line
 overrides an earlier line.  This overriding is done per
 attribute.  The rules how the pattern matches paths are the
 same as in `.gitignore` files; see linkgit:gitignore[5].
+Unlike `.gitignore`, negative patterns are not supported.
+
+Note that if a .gitignore rule matches a directory, the directory
+is ignored, which may be seen as assigning "ignore" attribute the
+directory and all files and directories inside. However, if a
+.gitattributes rule matches a directory, it manipulates
+attributes on that directory only, not files and directories
+inside.
 
 When deciding what attributes are assigned to a path, git
 consults `$GIT_DIR/info/attributes` file (which has the highest

diff --git a/attr.c b/attr.c
index e7caee4..4faf1ff 100644
--- a/attr.c
+++ b/attr.c

@@ -115,6 +115,13 @@ struct attr_state {
 	const char *setto;
 };
 
+struct pattern {
+	const char *pattern;
+	int patternlen;
+	int nowildcardlen;
+	int flags;		/* EXC_FLAG_* */
+};
+
 /*
  * One rule, as from a .gitattributes file.
  *

@@ -131,7 +138,7 @@ struct attr_state {
  */
 struct match_attr {
 	union {
-		char *pattern;
+		struct pattern pat;
 		struct git_attr *attr;
 	} u;
 	char is_macro;

@@ -241,9 +248,16 @@ static struct match_attr *parse_attr_line(const char *line, const char *src,
 	if (is_macro)
 		res->u.attr = git_attr_internal(name, namelen);
 	else {
-		res->u.pattern = (char *)&(res->state[num_attr]);
-		memcpy(res->u.pattern, name, namelen);
-		res->u.pattern[namelen] = 0;
+		char *p = (char *)&(res->state[num_attr]);
+		memcpy(p, name, namelen);
+		res->u.pat.pattern = p;
+		parse_exclude_pattern(&res->u.pat.pattern,
+				      &res->u.pat.patternlen,
+				      &res->u.pat.flags,
+				      &res->u.pat.nowildcardlen);
+		if (res->u.pat.flags & EXC_FLAG_NEGATIVE)
+			die(_("Negative patterns are forbidden in git attributes\n"
+			      "Use '\\!' for literal leading exclamation."));
 	}
 	res->is_macro = is_macro;
 	res->num_attr = num_attr;

@@ -640,25 +654,57 @@ static void prepare_attr_stack(const char *path)
 
 static int path_matches(const char *pathname, int pathlen,
 			const char *basename,
-			const char *pattern,
+			const struct pattern *pat,
 			const char *base, int baselen)
 {
-	if (!strchr(pattern, '/')) {
+	const char *pattern = pat->pattern;
+	int prefix = pat->nowildcardlen;
+	const char *name;
+	int namelen;
+
+	if (pat->flags & EXC_FLAG_NODIR) {
+		if (prefix == pat->patternlen &&
+		    !strcmp_icase(pattern, basename))
+			return 1;
+
+		if (pat->flags & EXC_FLAG_ENDSWITH &&
+		    pat->patternlen - 1 <= pathlen &&
+		    !strcmp_icase(pattern + 1, pathname +
+				  pathlen - pat->patternlen + 1))
+			return 1;
+
 		return (fnmatch_icase(pattern, basename, 0) == 0);
 	}
 	/*
 	 * match with FNM_PATHNAME; the pattern has base implicitly
 	 * in front of it.
 	 */
-	if (*pattern == '/')
+	if (*pattern == '/') {
 		pattern++;
-	if (pathlen < baselen ||
+		prefix--;
+	}
+
+	/*
+	 * note: unlike excluded_from_list, baselen here does not
+	 * contain the trailing slash
+	 */
+
+	if (pathlen < baselen + 1 ||
 	    (baselen && pathname[baselen] != '/') ||
-	    strncmp(pathname, base, baselen))
+	    strncmp_icase(pathname, base, baselen))
+		return 0;
+
+	namelen = baselen ? pathlen - baselen - 1 : pathlen;
+	name = pathname + pathlen - namelen;
+
+	/*
+	 * if the non-wildcard part is longer than the remaining
+	 * pathname, surely it cannot match
+	 */
+	if (!namelen || prefix > namelen)
 		return 0;
-	if (baselen != 0)
-		baselen++;
-	return fnmatch_icase(pattern, pathname + baselen, FNM_PATHNAME) == 0;
+
+	return fnmatch_icase(pattern, name, FNM_PATHNAME) == 0;
 }
 
 static int macroexpand_one(int attr_nr, int rem);

@@ -696,7 +742,7 @@ static int fill(const char *path, int pathlen, const char *basename,
 		if (a->is_macro)
 			continue;
 		if (path_matches(path, pathlen, basename,
-				 a->u.pattern, base, stk->originlen))
+				 &a->u.pat, base, stk->originlen))
 			rem = fill_one("fill", a, rem);
 	}
 	return rem;

diff --git a/dir.c b/dir.c
index 48aed85..cddf043 100644
--- a/dir.c
+++ b/dir.c

@@ -308,10 +308,10 @@ static int no_wildcard(const char *string)
 	return string[simple_length(string)] == '\0';
 }
 
-static void parse_exclude_pattern(const char **pattern,
-				  int *patternlen,
-				  int *flags,
-				  int *nowildcardlen)
+void parse_exclude_pattern(const char **pattern,
+			   int *patternlen,
+			   int *flags,
+			   int *nowildcardlen)
 {
 	const char *p = *pattern;
 	size_t i, len;

diff --git a/dir.h b/dir.h
index 41ea32d..fd5c2aa 100644
--- a/dir.h
+++ b/dir.h

@@ -97,6 +97,7 @@ extern int path_excluded(struct path_exclude_check *, const char *, int namelen,
 extern int add_excludes_from_file_to_list(const char *fname, const char *base, int baselen,
 					  char **buf_p, struct exclude_list *which, int check_index);
 extern void add_excludes_from_file(struct dir_struct *, const char *fname);
+extern void parse_exclude_pattern(const char **string, int *patternlen, int *flags, int *nowildcardlen);
 extern void add_exclude(const char *string, const char *base,
 			int baselen, struct exclude_list *which);
 extern void free_excludes(struct exclude_list *el);

diff --git a/t/t0003-attributes.sh b/t/t0003-attributes.sh
index 51f3045..4a1402f 100755
--- a/t/t0003-attributes.sh
+++ b/t/t0003-attributes.sh

@@ -242,4 +242,18 @@ test_expect_success 'bare repository: test info/attributes' '
 	attr_check subdir/a/i unspecified
 '
 
+test_expect_success 'leave bare' '
+	cd ..
+'
+
+test_expect_success 'negative patterns' '
+	echo "!f test=bar" >.gitattributes &&
+	test_must_fail git check-attr test -- f
+'
+
+test_expect_success 'patterns starting with exclamation' '
+	echo "\!f test=foo" >.gitattributes &&
+	attr_check "!f" foo
+'
+
 test_done

-- 
1.7.12.1.406.g6ab07c4