Merge branch 'nd/negative-pathspec'

Introduce "negative pathspec" magic, to allow "git log -- . ':!dir'" to
tell us "I am interested in everything but 'dir' directory".

* nd/negative-pathspec:
  pathspec.c: support adding prefix magic to a pathspec with mnemonic magic
  Support pathspec magic :(exclude) and its short form :!
  glossary-content.txt: rephrase magic signature part

7 files changed, 354 insertions, 40 deletions

diff --git a/Documentation/glossary-content.txt b/Documentation/glossary-content.txt
index aa1c8880dd..378306f581 100644
--- a/Documentation/glossary-content.txt
+++ b/Documentation/glossary-content.txt
@@ -323,24 +323,26 @@ including Documentation/chapter_1/figure_1.jpg.
 A pathspec that begins with a colon `:` has special meaning.  In the
 short form, the leading colon `:` is followed by zero or more "magic
 signature" letters (which optionally is terminated by another colon `:`),
-and the remainder is the pattern to match against the path. The optional
-colon that terminates the "magic signature" can be omitted if the pattern
-begins with a character that cannot be a "magic signature" and is not a
-colon.
+and the remainder is the pattern to match against the path.
+The "magic signature" consists of ASCII symbols that are neither
+alphanumeric, glob, regex special charaters nor colon.
+The optional colon that terminates the "magic signature" can be
+omitted if the pattern begins with a character that does not belong to
+"magic signature" symbol set and is not a colon.
 +
 In the long form, the leading colon `:` is followed by a open
 parenthesis `(`, a comma-separated list of zero or more "magic words",
 and a close parentheses `)`, and the remainder is the pattern to match
 against the path.
 +
-The "magic signature" consists of an ASCII symbol that is not
-alphanumeric.
+A pathspec with only a colon means "there is no pathspec". This form
+should not be combined with other pathspec.
 +
 --
-top `/`;;
-	The magic word `top` (mnemonic: `/`) makes the pattern match
-	from the root of the working tree, even when you are running
-	the command from inside a subdirectory.
+top;;
+	The magic word `top` (magic signature: `/`) makes the pattern
+	match from the root of the working tree, even when you are
+	running the command from inside a subdirectory.
 
 literal;;
 	Wildcards in the pattern such as `*` or `?` are treated
@@ -377,14 +379,12 @@ full pathname may have special meaning:
  - Other consecutive asterisks are considered invalid.
 +
 Glob magic is incompatible with literal magic.
+
+exclude;;
+	After a path matches any non-exclude pathspec, it will be run
+	through all exclude pathspec (magic signature: `!`). If it
+	matches, the path is ignored.
 --
-+
-Currently only the slash `/` is recognized as the "magic signature",
-but it is envisioned that we will support more types of magic in later
-versions of Git.
-+
-A pathspec with only a colon means "there is no pathspec". This form
-should not be combined with other pathspec.
 
 [[def_parent]]parent::
 	A <<def_commit_object,commit object>> contains a (possibly empty) list
diff --git a/builtin/add.c b/builtin/add.c
index 226f758869..0df73ae735 100644
--- a/builtin/add.c
+++ b/builtin/add.c
@@ -540,10 +540,13 @@ int cmd_add(int argc, const char **argv, const char *prefix)
 			       PATHSPEC_FROMTOP |
 			       PATHSPEC_LITERAL |
 			       PATHSPEC_GLOB |
-			       PATHSPEC_ICASE);
+			       PATHSPEC_ICASE |
+			       PATHSPEC_EXCLUDE);
 
 		for (i = 0; i < pathspec.nr; i++) {
 			const char *path = pathspec.items[i].match;
+			if (pathspec.items[i].magic & PATHSPEC_EXCLUDE)
+				continue;
 			if (!seen[i] &&
 			    ((pathspec.items[i].magic &
 			      (PATHSPEC_GLOB | PATHSPEC_ICASE)) ||
diff --git a/dir.c b/dir.c
index 23b6de4703..d10a63f731 100644
--- a/dir.c
+++ b/dir.c
@@ -126,10 +126,13 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 		       PATHSPEC_MAXDEPTH |
 		       PATHSPEC_LITERAL |
 		       PATHSPEC_GLOB |
-		       PATHSPEC_ICASE);
+		       PATHSPEC_ICASE |
+		       PATHSPEC_EXCLUDE);
 
 	for (n = 0; n < pathspec->nr; n++) {
 		size_t i = 0, len = 0, item_len;
+		if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
+			continue;
 		if (pathspec->items[n].magic & PATHSPEC_ICASE)
 			item_len = pathspec->items[n].prefix;
 		else
@@ -279,9 +282,10 @@ static int match_pathspec_item(const struct pathspec_item *item, int prefix,
  * pathspec did not match any names, which could indicate that the
  * user mistyped the nth pathspec.
  */
-int match_pathspec_depth(const struct pathspec *ps,
-			 const char *name, int namelen,
-			 int prefix, char *seen)
+static int match_pathspec_depth_1(const struct pathspec *ps,
+				  const char *name, int namelen,
+				  int prefix, char *seen,
+				  int exclude)
 {
 	int i, retval = 0;
 
@@ -290,7 +294,8 @@ int match_pathspec_depth(const struct pathspec *ps,
 		       PATHSPEC_MAXDEPTH |
 		       PATHSPEC_LITERAL |
 		       PATHSPEC_GLOB |
-		       PATHSPEC_ICASE);
+		       PATHSPEC_ICASE |
+		       PATHSPEC_EXCLUDE);
 
 	if (!ps->nr) {
 		if (!ps->recursive ||
@@ -309,8 +314,19 @@ int match_pathspec_depth(const struct pathspec *ps,
 
 	for (i = ps->nr - 1; i >= 0; i--) {
 		int how;
+
+		if ((!exclude &&   ps->items[i].magic & PATHSPEC_EXCLUDE) ||
+		    ( exclude && !(ps->items[i].magic & PATHSPEC_EXCLUDE)))
+			continue;
+
 		if (seen && seen[i] == MATCHED_EXACTLY)
 			continue;
+		/*
+		 * Make exclude patterns optional and never report
+		 * "pathspec ':(exclude)foo' matches no files"
+		 */
+		if (seen && ps->items[i].magic & PATHSPEC_EXCLUDE)
+			seen[i] = MATCHED_FNMATCH;
 		how = match_pathspec_item(ps->items+i, prefix, name, namelen);
 		if (ps->recursive &&
 		    (ps->magic & PATHSPEC_MAXDEPTH) &&
@@ -334,6 +350,18 @@ int match_pathspec_depth(const struct pathspec *ps,
 	return retval;
 }
 
+int match_pathspec_depth(const struct pathspec *ps,
+			 const char *name, int namelen,
+			 int prefix, char *seen)
+{
+	int positive, negative;
+	positive = match_pathspec_depth_1(ps, name, namelen, prefix, seen, 0);
+	if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
+		return positive;
+	negative = match_pathspec_depth_1(ps, name, namelen, prefix, seen, 1);
+	return negative ? 0 : positive;
+}
+
 /*
  * Return the length of the "simple" part of a path match limiter.
  */
@@ -1375,11 +1403,18 @@ int read_directory(struct dir_struct *dir, const char *path, int len, const stru
 			       PATHSPEC_MAXDEPTH |
 			       PATHSPEC_LITERAL |
 			       PATHSPEC_GLOB |
-			       PATHSPEC_ICASE);
+			       PATHSPEC_ICASE |
+			       PATHSPEC_EXCLUDE);
 
 	if (has_symlink_leading_path(path, len))
 		return dir->nr;
 
+	/*
+	 * exclude patterns are treated like positive ones in
+	 * create_simplify. Usually exclude patterns should be a
+	 * subset of positive ones, which has no impacts on
+	 * create_simplify().
+	 */
 	simplify = create_simplify(pathspec ? pathspec->_raw : NULL);
 	if (!len || treat_leading_path(dir, path, len, simplify))
 		read_directory_recursive(dir, path, len, 0, simplify);
diff --git a/pathspec.c b/pathspec.c
index 52d38a4b4f..6cb9fd3014 100644
--- a/pathspec.c
+++ b/pathspec.c
@@ -71,8 +71,23 @@ static struct pathspec_magic {
 	{ PATHSPEC_LITERAL,   0, "literal" },
 	{ PATHSPEC_GLOB,   '\0', "glob" },
 	{ PATHSPEC_ICASE,  '\0', "icase" },
+	{ PATHSPEC_EXCLUDE, '!', "exclude" },
 };
 
+static void prefix_short_magic(struct strbuf *sb, int prefixlen,
+			       unsigned short_magic)
+{
+	int i;
+	strbuf_addstr(sb, ":(");
+	for (i = 0; i < ARRAY_SIZE(pathspec_magic); i++)
+		if (short_magic & pathspec_magic[i].bit) {
+			if (sb->buf[sb->len - 1] != '(')
+				strbuf_addch(sb, ',');
+			strbuf_addstr(sb, pathspec_magic[i].name);
+		}
+	strbuf_addf(sb, ",prefix:%d)", prefixlen);
+}
+
 /*
  * Take an element of a pathspec and check for magic signatures.
  * Append the result to the prefix. Return the magic bitmap.
@@ -232,22 +247,16 @@ static unsigned prefix_pathspec(struct pathspec_item *item,
 	 */
 	if (flags & PATHSPEC_PREFIX_ORIGIN) {
 		struct strbuf sb = STRBUF_INIT;
-		const char *start = elt;
 		if (prefixlen && !literal_global) {
 			/* Preserve the actual prefix length of each pattern */
 			if (short_magic)
-				die("BUG: prefixing on short magic is not supported");
+				prefix_short_magic(&sb, prefixlen, short_magic);
 			else if (long_magic_end) {
-				strbuf_add(&sb, start, long_magic_end - start);
-				strbuf_addf(&sb, ",prefix:%d", prefixlen);
-				start = long_magic_end;
-			} else {
-				if (*start == ':')
-					start++;
+				strbuf_add(&sb, elt, long_magic_end - elt);
+				strbuf_addf(&sb, ",prefix:%d)", prefixlen);
+			} else
 				strbuf_addf(&sb, ":(prefix:%d)", prefixlen);
-			}
 		}
-		strbuf_add(&sb, start, copyfrom - start);
 		strbuf_addstr(&sb, match);
 		item->original = strbuf_detach(&sb, NULL);
 	} else
@@ -355,7 +364,7 @@ void parse_pathspec(struct pathspec *pathspec,
 {
 	struct pathspec_item *item;
 	const char *entry = argv ? *argv : NULL;
-	int i, n, prefixlen;
+	int i, n, prefixlen, nr_exclude = 0;
 
 	memset(pathspec, 0, sizeof(*pathspec));
 
@@ -412,6 +421,8 @@ void parse_pathspec(struct pathspec *pathspec,
 		if ((flags & PATHSPEC_LITERAL_PATH) &&
 		    !(magic_mask & PATHSPEC_LITERAL))
 			item[i].magic |= PATHSPEC_LITERAL;
+		if (item[i].magic & PATHSPEC_EXCLUDE)
+			nr_exclude++;
 		if (item[i].magic & magic_mask)
 			unsupported_magic(entry,
 					  item[i].magic & magic_mask,
@@ -427,6 +438,10 @@ void parse_pathspec(struct pathspec *pathspec,
 		pathspec->magic |= item[i].magic;
 	}
 
+	if (nr_exclude == n)
+		die(_("There is nothing to exclude from by :(exclude) patterns.\n"
+		      "Perhaps you forgot to add either ':/' or '.' ?"));
+
 
 	if (pathspec->magic & PATHSPEC_MAXDEPTH) {
 		if (flags & PATHSPEC_KEEP_ORDER)
diff --git a/pathspec.h b/pathspec.h
index a75e9242d1..0c1126264a 100644
--- a/pathspec.h
+++ b/pathspec.h
@@ -7,12 +7,14 @@
 #define PATHSPEC_LITERAL	(1<<2)
 #define PATHSPEC_GLOB		(1<<3)
 #define PATHSPEC_ICASE		(1<<4)
+#define PATHSPEC_EXCLUDE	(1<<5)
 #define PATHSPEC_ALL_MAGIC	  \
 	(PATHSPEC_FROMTOP	| \
 	 PATHSPEC_MAXDEPTH	| \
 	 PATHSPEC_LITERAL	| \
 	 PATHSPEC_GLOB		| \
-	 PATHSPEC_ICASE)
+	 PATHSPEC_ICASE		| \
+	 PATHSPEC_EXCLUDE)
 
 #define PATHSPEC_ONESTAR 1	/* the pathspec pattern satisfies GFNM_ONESTAR */
 
diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
new file mode 100755
index 0000000000..62049be0c7
--- /dev/null
+++ b/t/t6132-pathspec-exclude.sh
@@ -0,0 +1,184 @@
+#!/bin/sh
+
+test_description='test case exclude pathspec'
+
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	for p in file sub/file sub/sub/file sub/file2 sub/sub/sub/file sub2/file; do
+		if echo $p | grep /; then
+			mkdir -p `dirname $p`
+		fi &&
+		: >$p &&
+		git add $p &&
+		git commit -m $p
+	done &&
+	git log --oneline --format=%s >actual &&
+	cat <<EOF >expect &&
+sub2/file
+sub/sub/sub/file
+sub/file2
+sub/sub/file
+sub/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'exclude only should error out' '
+	test_must_fail git log --oneline --format=%s -- ":(exclude)sub"
+'
+
+test_expect_success 't_e_i() exclude sub' '
+	git log --oneline --format=%s -- . ":(exclude)sub" >actual
+	cat <<EOF >expect &&
+sub2/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 't_e_i() exclude sub/sub/file' '
+	git log --oneline --format=%s -- . ":(exclude)sub/sub/file" >actual
+	cat <<EOF >expect &&
+sub2/file
+sub/sub/sub/file
+sub/file2
+sub/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 't_e_i() exclude sub using mnemonic' '
+	git log --oneline --format=%s -- . ":!sub" >actual
+	cat <<EOF >expect &&
+sub2/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 't_e_i() exclude :(icase)SUB' '
+	git log --oneline --format=%s -- . ":(exclude,icase)SUB" >actual
+	cat <<EOF >expect &&
+sub2/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 't_e_i() exclude sub2 from sub' '
+	(
+	cd sub &&
+	git log --oneline --format=%s -- :/ ":/!sub2" >actual
+	cat <<EOF >expect &&
+sub/sub/sub/file
+sub/file2
+sub/sub/file
+sub/file
+file
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 't_e_i() exclude sub/*file' '
+	git log --oneline --format=%s -- . ":(exclude)sub/*file" >actual
+	cat <<EOF >expect &&
+sub2/file
+sub/file2
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 't_e_i() exclude :(glob)sub/*/file' '
+	git log --oneline --format=%s -- . ":(exclude,glob)sub/*/file" >actual
+	cat <<EOF >expect &&
+sub2/file
+sub/sub/sub/file
+sub/file2
+sub/file
+file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude sub' '
+	git ls-files -- . ":(exclude)sub" >actual
+	cat <<EOF >expect &&
+file
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude sub/sub/file' '
+	git ls-files -- . ":(exclude)sub/sub/file" >actual
+	cat <<EOF >expect &&
+file
+sub/file
+sub/file2
+sub/sub/sub/file
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude sub using mnemonic' '
+	git ls-files -- . ":!sub" >actual
+	cat <<EOF >expect &&
+file
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude :(icase)SUB' '
+	git ls-files -- . ":(exclude,icase)SUB" >actual
+	cat <<EOF >expect &&
+file
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude sub2 from sub' '
+	(
+	cd sub &&
+	git ls-files -- :/ ":/!sub2" >actual
+	cat <<EOF >expect &&
+../file
+file
+file2
+sub/file
+sub/sub/file
+EOF
+	test_cmp expect actual
+	)
+'
+
+test_expect_success 'm_p_d() exclude sub/*file' '
+	git ls-files -- . ":(exclude)sub/*file" >actual
+	cat <<EOF >expect &&
+file
+sub/file2
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'm_p_d() exclude :(glob)sub/*/file' '
+	git ls-files -- . ":(exclude,glob)sub/*/file" >actual
+	cat <<EOF >expect &&
+file
+sub/file
+sub/file2
+sub/sub/sub/file
+sub2/file
+EOF
+	test_cmp expect actual
+'
+
+test_done
diff --git a/tree-walk.c b/tree-walk.c
index 5ece8c3477..680afda060 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -662,9 +662,10 @@ static int match_wildcard_base(const struct pathspec_item *item,
  * Pre-condition: either baselen == base_offset (i.e. empty path)
  * or base[baselen-1] == '/' (i.e. with trailing slash).
  */
-enum interesting tree_entry_interesting(const struct name_entry *entry,
-					struct strbuf *base, int base_offset,
-					const struct pathspec *ps)
+static enum interesting do_match(const struct name_entry *entry,
+				 struct strbuf *base, int base_offset,
+				 const struct pathspec *ps,
+				 int exclude)
 {
 	int i;
 	int pathlen, baselen = base->len - base_offset;
@@ -676,7 +677,8 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 		       PATHSPEC_MAXDEPTH |
 		       PATHSPEC_LITERAL |
 		       PATHSPEC_GLOB |
-		       PATHSPEC_ICASE);
+		       PATHSPEC_ICASE |
+		       PATHSPEC_EXCLUDE);
 
 	if (!ps->nr) {
 		if (!ps->recursive ||
@@ -697,6 +699,10 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 		const char *base_str = base->buf + base_offset;
 		int matchlen = item->len, matched = 0;
 
+		if ((!exclude &&   item->magic & PATHSPEC_EXCLUDE) ||
+		    ( exclude && !(item->magic & PATHSPEC_EXCLUDE)))
+			continue;
+
 		if (baselen >= matchlen) {
 			/* If it doesn't match, move along... */
 			if (!match_dir_prefix(item, base_str, match, matchlen))
@@ -782,3 +788,72 @@ match_wildcards:
 	}
 	return never_interesting; /* No matches */
 }
+
+/*
+ * Is a tree entry interesting given the pathspec we have?
+ *
+ * Pre-condition: either baselen == base_offset (i.e. empty path)
+ * or base[baselen-1] == '/' (i.e. with trailing slash).
+ */
+enum interesting tree_entry_interesting(const struct name_entry *entry,
+					struct strbuf *base, int base_offset,
+					const struct pathspec *ps)
+{
+	enum interesting positive, negative;
+	positive = do_match(entry, base, base_offset, ps, 0);
+
+	/*
+	 * case | entry | positive | negative | result
+	 * -----+-------+----------+----------+-------
+	 *   1  |  file |   -1     |  -1..2   |  -1
+	 *   2  |  file |    0     |  -1..2   |   0
+	 *   3  |  file |    1     |   -1     |   1
+	 *   4  |  file |    1     |    0     |   1
+	 *   5  |  file |    1     |    1     |   0
+	 *   6  |  file |    1     |    2     |   0
+	 *   7  |  file |    2     |   -1     |   2
+	 *   8  |  file |    2     |    0     |   2
+	 *   9  |  file |    2     |    1     |   0
+	 *  10  |  file |    2     |    2     |  -1
+	 * -----+-------+----------+----------+-------
+	 *  11  |  dir  |   -1     |  -1..2   |  -1
+	 *  12  |  dir  |    0     |  -1..2   |   0
+	 *  13  |  dir  |    1     |   -1     |   1
+	 *  14  |  dir  |    1     |    0     |   1
+	 *  15  |  dir  |    1     |    1     |   1 (*)
+	 *  16  |  dir  |    1     |    2     |   0
+	 *  17  |  dir  |    2     |   -1     |   2
+	 *  18  |  dir  |    2     |    0     |   2
+	 *  19  |  dir  |    2     |    1     |   1 (*)
+	 *  20  |  dir  |    2     |    2     |  -1
+	 *
+	 * (*) An exclude pattern interested in a directory does not
+	 * necessarily mean it will exclude all of the directory. In
+	 * wildcard case, it can't decide until looking at individual
+	 * files inside. So don't write such directories off yet.
+	 */
+
+	if (!(ps->magic & PATHSPEC_EXCLUDE) ||
+	    positive <= entry_not_interesting) /* #1, #2, #11, #12 */
+		return positive;
+
+	negative = do_match(entry, base, base_offset, ps, 1);
+
+	/* #3, #4, #7, #8, #13, #14, #17, #18 */
+	if (negative <= entry_not_interesting)
+		return positive;
+
+	/* #15, #19 */
+	if (S_ISDIR(entry->mode) &&
+	    positive >= entry_interesting &&
+	    negative == entry_interesting)
+		return entry_interesting;
+
+	if ((positive == entry_interesting &&
+	     negative >= entry_interesting) || /* #5, #6, #16 */
+	    (positive == all_entries_interesting &&
+	     negative == entry_interesting)) /* #9 */
+		return entry_not_interesting;
+
+	return all_entries_not_interesting; /* #10, #20 */
+}