Merge branch 'nd/wildmatch'
authorJunio C Hamano <gitster@pobox.com>
Thu, 10 Jan 2013 21:47:15 +0000 (13:47 -0800)
committerJunio C Hamano <gitster@pobox.com>
Thu, 10 Jan 2013 21:47:20 +0000 (13:47 -0800)
Allows pathname patterns in .gitignore and .gitattributes files
with double-asterisks "foo/**/bar" to match any number of directory
hierarchies.

* nd/wildmatch:
wildmatch: replace variable 'special' with better named ones
compat/fnmatch: respect NO_FNMATCH* even on glibc
wildmatch: fix "**" special case
t3070: Disable some failing fnmatch tests
test-wildmatch: avoid Windows path mangling
Support "**" wildcard in .gitignore and .gitattributes
wildmatch: make /**/ match zero or more directories
wildmatch: adjust "**" behavior
wildmatch: fix case-insensitive matching
wildmatch: remove static variable force_lower_case
wildmatch: make wildmatch's return value compatible with fnmatch
t3070: disable unreliable fnmatch tests
Integrate wildmatch to git
wildmatch: follow Git's coding convention
wildmatch: remove unnecessary functions
Import wildmatch from rsync
ctype: support iscntrl, ispunct, isxdigit and isprint
ctype: make sane_ctype[] const array

Conflicts:
Makefile

13 files changed:
.gitignore
Documentation/gitignore.txt
Makefile
compat/fnmatch/fnmatch.c
ctype.c
dir.c
git-compat-util.h
t/t0003-attributes.sh
t/t3001-ls-files-others-exclude.sh
t/t3070-wildmatch.sh [new file with mode: 0755]
test-wildmatch.c [new file with mode: 0644]
wildmatch.c [new file with mode: 0644]
wildmatch.h [new file with mode: 0644]
index 8e8dc275db9bcc1155e42daea5a6589b4802bc9c..aa258a6bcfe105cdb872c6d77cd9bd19c84e8dc5 100644 (file)
 /test-string-list
 /test-subprocess
 /test-svn-fe
+/test-wildmatch
 /common-cmds.h
 *.tar.gz
 *.dsc
index 1b82fe1969ed1cf965d946178a423771dd3cfe5f..91a6438031949d83600abc791676bbf0397a0ddc 100644 (file)
@@ -108,6 +108,25 @@ PATTERN FORMAT
    For example, "/{asterisk}.c" matches "cat-file.c" but not
    "mozilla-sha1/sha1.c".
 
+Two consecutive asterisks ("`**`") in patterns matched against
+full pathname may have special meaning:
+
+ - A leading "`**`" followed by a slash means match in all
+   directories. For example, "`**/foo`" matches file or directory
+   "`foo`" anywhere, the same as pattern "`foo`". "**/foo/bar"
+   matches file or directory "`bar`" anywhere that is directly
+   under directory "`foo`".
+
+ - A trailing "/**" matches everything inside. For example,
+   "abc/**" matches all files inside directory "abc", relative
+   to the location of the `.gitignore` file, with infinite depth.
+
+ - A slash followed by two consecutive asterisks then a slash
+   matches zero or more directories. For example, "`a/**/b`"
+   matches "`a/b`", "`a/x/b`", "`a/x/y/b`" and so on.
+
+ - Other consecutive asterisks are considered invalid.
+
 NOTES
 -----
 
index cd0664accb3c862354042de3b719b2ab925cd053..f37fb240cc11a7dc22b423cb2e09571035e237c9 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -532,6 +532,7 @@ TEST_PROGRAMS_NEED_X += test-sigchain
 TEST_PROGRAMS_NEED_X += test-string-list
 TEST_PROGRAMS_NEED_X += test-subprocess
 TEST_PROGRAMS_NEED_X += test-svn-fe
+TEST_PROGRAMS_NEED_X += test-wildmatch
 
 TEST_PROGRAMS = $(patsubst %,%$X,$(TEST_PROGRAMS_NEED_X))
 
@@ -704,6 +705,7 @@ LIB_H += userdiff.h
 LIB_H += utf8.h
 LIB_H += varint.h
 LIB_H += walker.h
+LIB_H += wildmatch.h
 LIB_H += wt-status.h
 LIB_H += xdiff-interface.h
 LIB_H += xdiff/xdiff.h
@@ -838,6 +840,7 @@ LIB_OBJS += utf8.o
 LIB_OBJS += varint.o
 LIB_OBJS += version.o
 LIB_OBJS += walker.o
+LIB_OBJS += wildmatch.o
 LIB_OBJS += wrapper.o
 LIB_OBJS += write_or_die.o
 LIB_OBJS += ws.o
index b8b7dc254373fb0f7b2a7b16163fa72e1e8c5f7b..5ef0685135662e3cefc80eed5c5ae030fe1a5d49 100644 (file)
@@ -55,7 +55,8 @@
    program understand `configure --with-gnu-libc' and omit the object files,
    it is simpler to just do this in the source for each such file.  */
 
-#if defined _LIBC || !defined __GNU_LIBRARY__
+#if defined NO_FNMATCH || defined NO_FNMATCH_CASEFOLD || \
+    defined _LIBC || !defined __GNU_LIBRARY__
 
 
 # if defined STDC_HEADERS || !defined isascii
diff --git a/ctype.c b/ctype.c
index 935327164b1066ad011d11fdcd3fd1dc1a936c58..0bfebb4e75866ba0e97713fab5394490290831c0 100644 (file)
--- a/ctype.c
+++ b/ctype.c
@@ -11,18 +11,21 @@ enum {
        D = GIT_DIGIT,
        G = GIT_GLOB_SPECIAL,   /* *, ?, [, \\ */
        R = GIT_REGEX_SPECIAL,  /* $, (, ), +, ., ^, {, | */
-       P = GIT_PATHSPEC_MAGIC  /* other non-alnum, except for ] and } */
+       P = GIT_PATHSPEC_MAGIC, /* other non-alnum, except for ] and } */
+       X = GIT_CNTRL,
+       U = GIT_PUNCT,
+       Z = GIT_CNTRL | GIT_SPACE
 };
 
-unsigned char sane_ctype[256] = {
-       0, 0, 0, 0, 0, 0, 0, 0, 0, S, S, 0, 0, S, 0, 0,         /*   0.. 15 */
-       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,         /*  16.. 31 */
+const unsigned char sane_ctype[256] = {
+       X, X, X, X, X, X, X, X, X, Z, Z, X, X, Z, X, X,         /*   0.. 15 */
+       X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,         /*  16.. 31 */
        S, P, P, P, R, P, P, P, R, R, G, R, P, P, R, P,         /*  32.. 47 */
        D, D, D, D, D, D, D, D, D, D, P, P, P, P, P, G,         /*  48.. 63 */
        P, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,         /*  64.. 79 */
-       A, A, A, A, A, A, A, A, A, A, A, G, G, 0, R, P,         /*  80.. 95 */
+       A, A, A, A, A, A, A, A, A, A, A, G, G, U, R, P,         /*  80.. 95 */
        P, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,         /*  96..111 */
-       A, A, A, A, A, A, A, A, A, A, A, R, R, 0, P, 0,         /* 112..127 */
+       A, A, A, A, A, A, A, A, A, A, A, R, R, U, P, X,         /* 112..127 */
        /* Nothing in the 128.. range */
 };
 
diff --git a/dir.c b/dir.c
index 095ea7ebabfa25f1ff1aba199c09daaac984dbaa..37807550475cf488b60187872f698cbc6171dcb1 100644 (file)
--- a/dir.c
+++ b/dir.c
@@ -8,6 +8,7 @@
 #include "cache.h"
 #include "dir.h"
 #include "refs.h"
+#include "wildmatch.h"
 
 struct path_simplify {
        int len;
@@ -624,7 +625,8 @@ int match_pathname(const char *pathname, int pathlen,
                namelen -= prefix;
        }
 
-       return fnmatch_icase(pattern, name, FNM_PATHNAME) == 0;
+       return wildmatch(pattern, name,
+                        ignore_case ? FNM_CASEFOLD : 0) == 0;
 }
 
 /* Scan the list and let the last match determine the fate.
index 2cecf56eb367ccd866250b7634c738187d6e2261..e5a4b7450bfa7a700ce1c76f597266a9724a19f5 100644 (file)
@@ -528,13 +528,19 @@ extern const char tolower_trans_tbl[256];
 #undef isupper
 #undef tolower
 #undef toupper
-extern unsigned char sane_ctype[256];
+#undef iscntrl
+#undef ispunct
+#undef isxdigit
+
+extern const unsigned char sane_ctype[256];
 #define GIT_SPACE 0x01
 #define GIT_DIGIT 0x02
 #define GIT_ALPHA 0x04
 #define GIT_GLOB_SPECIAL 0x08
 #define GIT_REGEX_SPECIAL 0x10
 #define GIT_PATHSPEC_MAGIC 0x20
+#define GIT_CNTRL 0x40
+#define GIT_PUNCT 0x80
 #define sane_istest(x,mask) ((sane_ctype[(unsigned char)(x)] & (mask)) != 0)
 #define isascii(x) (((x) & ~0x7f) == 0)
 #define isspace(x) sane_istest(x,GIT_SPACE)
@@ -546,6 +552,10 @@ extern unsigned char sane_ctype[256];
 #define isupper(x) sane_iscase(x, 0)
 #define is_glob_special(x) sane_istest(x,GIT_GLOB_SPECIAL)
 #define is_regex_special(x) sane_istest(x,GIT_GLOB_SPECIAL | GIT_REGEX_SPECIAL)
+#define iscntrl(x) (sane_istest(x,GIT_CNTRL))
+#define ispunct(x) sane_istest(x, GIT_PUNCT | GIT_REGEX_SPECIAL | \
+               GIT_GLOB_SPECIAL | GIT_PATHSPEC_MAGIC)
+#define isxdigit(x) (hexval_table[x] != -1)
 #define tolower(x) sane_case((unsigned char)(x), 0x20)
 #define toupper(x) sane_case((unsigned char)(x), 0)
 #define is_pathspec_magic(x) sane_istest(x,GIT_PATHSPEC_MAGIC)
index 807b8b88e215df5ce39504b1858be8694499727d..43b25137e9878e41557fd7d095cc991c27efdfc7 100755 (executable)
@@ -206,6 +206,43 @@ test_expect_success 'patterns starting with exclamation' '
        attr_check "!f" foo
 '
 
+test_expect_success '"**" test' '
+       echo "**/f foo=bar" >.gitattributes &&
+       cat <<\EOF >expect &&
+f: foo: bar
+a/f: foo: bar
+a/b/f: foo: bar
+a/b/c/f: foo: bar
+EOF
+       git check-attr foo -- "f" >actual 2>err &&
+       git check-attr foo -- "a/f" >>actual 2>>err &&
+       git check-attr foo -- "a/b/f" >>actual 2>>err &&
+       git check-attr foo -- "a/b/c/f" >>actual 2>>err &&
+       test_cmp expect actual &&
+       test_line_count = 0 err
+'
+
+test_expect_success '"**" with no slashes test' '
+       echo "a**f foo=bar" >.gitattributes &&
+       git check-attr foo -- "f" >actual &&
+       cat <<\EOF >expect &&
+f: foo: unspecified
+af: foo: bar
+axf: foo: bar
+a/f: foo: unspecified
+a/b/f: foo: unspecified
+a/b/c/f: foo: unspecified
+EOF
+       git check-attr foo -- "f" >actual 2>err &&
+       git check-attr foo -- "af" >>actual 2>err &&
+       git check-attr foo -- "axf" >>actual 2>err &&
+       git check-attr foo -- "a/f" >>actual 2>>err &&
+       git check-attr foo -- "a/b/f" >>actual 2>>err &&
+       git check-attr foo -- "a/b/c/f" >>actual 2>>err &&
+       test_cmp expect actual &&
+       test_line_count = 0 err
+'
+
 test_expect_success 'setup bare' '
        git clone --bare . bare.git &&
        cd bare.git
index dc2f0458fd0e74a3dcb4769517f5cde2606eb6f2..efb7ebc91f2f46b38e0c02f4dd11e2224678baea 100755 (executable)
@@ -220,4 +220,22 @@ test_expect_success 'pattern matches prefix completely' '
        test_cmp expect actual
 '
 
+test_expect_success 'ls-files with "**" patterns' '
+       cat <<\EOF >expect &&
+a.1
+one/a.1
+one/two/a.1
+three/a.1
+EOF
+       git ls-files -o -i --exclude "**/a.1" >actual
+       test_cmp expect actual
+'
+
+
+test_expect_success 'ls-files with "**" patterns and no slashes' '
+       : >expect &&
+       git ls-files -o -i --exclude "one**a.1" >actual &&
+       test_cmp expect actual
+'
+
 test_done
diff --git a/t/t3070-wildmatch.sh b/t/t3070-wildmatch.sh
new file mode 100755 (executable)
index 0000000..af54c83
--- /dev/null
@@ -0,0 +1,195 @@
+#!/bin/sh
+
+test_description='wildmatch tests'
+
+. ./test-lib.sh
+
+match() {
+    if [ $1 = 1 ]; then
+       test_expect_success "wildmatch:    match '$3' '$4'" "
+           test-wildmatch wildmatch '$3' '$4'
+       "
+    else
+       test_expect_success "wildmatch: no match '$3' '$4'" "
+           ! test-wildmatch wildmatch '$3' '$4'
+       "
+    fi
+    if [ $2 = 1 ]; then
+       test_expect_success "fnmatch:      match '$3' '$4'" "
+           test-wildmatch fnmatch '$3' '$4'
+       "
+    elif [ $2 = 0 ]; then
+       test_expect_success "fnmatch:   no match '$3' '$4'" "
+           ! test-wildmatch fnmatch '$3' '$4'
+       "
+#    else
+#      test_expect_success BROKEN_FNMATCH "fnmatch:       '$3' '$4'" "
+#          ! test-wildmatch fnmatch '$3' '$4'
+#      "
+    fi
+}
+
+# Basic wildmat features
+match 1 1 foo foo
+match 0 0 foo bar
+match 1 1 '' ""
+match 1 1 foo '???'
+match 0 0 foo '??'
+match 1 1 foo '*'
+match 1 1 foo 'f*'
+match 0 0 foo '*f'
+match 1 1 foo '*foo*'
+match 1 1 foobar '*ob*a*r*'
+match 1 1 aaaaaaabababab '*ab'
+match 1 1 'foo*' 'foo\*'
+match 0 0 foobar 'foo\*bar'
+match 1 1 'f\oo' 'f\\oo'
+match 1 1 ball '*[al]?'
+match 0 0 ten '[ten]'
+match 0 1 ten '**[!te]'
+match 0 0 ten '**[!ten]'
+match 1 1 ten 't[a-g]n'
+match 0 0 ten 't[!a-g]n'
+match 1 1 ton 't[!a-g]n'
+match 1 1 ton 't[^a-g]n'
+match 1 x 'a]b' 'a[]]b'
+match 1 x a-b 'a[]-]b'
+match 1 x 'a]b' 'a[]-]b'
+match 0 x aab 'a[]-]b'
+match 1 x aab 'a[]a-]b'
+match 1 1 ']' ']'
+
+# Extended slash-matching features
+match 0 0 'foo/baz/bar' 'foo*bar'
+match 0 0 'foo/baz/bar' 'foo**bar'
+match 0 1 'foobazbar' 'foo**bar'
+match 1 1 'foo/baz/bar' 'foo/**/bar'
+match 1 0 'foo/baz/bar' 'foo/**/**/bar'
+match 1 0 'foo/b/a/z/bar' 'foo/**/bar'
+match 1 0 'foo/b/a/z/bar' 'foo/**/**/bar'
+match 1 0 'foo/bar' 'foo/**/bar'
+match 1 0 'foo/bar' 'foo/**/**/bar'
+match 0 0 'foo/bar' 'foo?bar'
+match 0 0 'foo/bar' 'foo[/]bar'
+match 0 0 'foo/bar' 'f[^eiu][^eiu][^eiu][^eiu][^eiu]r'
+match 1 1 'foo-bar' 'f[^eiu][^eiu][^eiu][^eiu][^eiu]r'
+match 1 0 'foo' '**/foo'
+match 1 x 'XXX/foo' '**/foo'
+match 1 0 'bar/baz/foo' '**/foo'
+match 0 0 'bar/baz/foo' '*/foo'
+match 0 0 'foo/bar/baz' '**/bar*'
+match 1 0 'deep/foo/bar/baz' '**/bar/*'
+match 0 0 'deep/foo/bar/baz/' '**/bar/*'
+match 1 0 'deep/foo/bar/baz/' '**/bar/**'
+match 0 0 'deep/foo/bar' '**/bar/*'
+match 1 0 'deep/foo/bar/' '**/bar/**'
+match 0 0 'foo/bar/baz' '**/bar**'
+match 1 0 'foo/bar/baz/x' '*/bar/**'
+match 0 0 'deep/foo/bar/baz/x' '*/bar/**'
+match 1 0 'deep/foo/bar/baz/x' '**/bar/*/*'
+
+# Various additional tests
+match 0 0 'acrt' 'a[c-c]st'
+match 1 1 'acrt' 'a[c-c]rt'
+match 0 0 ']' '[!]-]'
+match 1 x 'a' '[!]-]'
+match 0 0 '' '\'
+match 0 x '\' '\'
+match 0 x 'XXX/\' '*/\'
+match 1 x 'XXX/\' '*/\\'
+match 1 1 'foo' 'foo'
+match 1 1 '@foo' '@foo'
+match 0 0 'foo' '@foo'
+match 1 1 '[ab]' '\[ab]'
+match 1 1 '[ab]' '[[]ab]'
+match 1 x '[ab]' '[[:]ab]'
+match 0 x '[ab]' '[[::]ab]'
+match 1 x '[ab]' '[[:digit]ab]'
+match 1 x '[ab]' '[\[:]ab]'
+match 1 1 '?a?b' '\??\?b'
+match 1 1 'abc' '\a\b\c'
+match 0 0 'foo' ''
+match 1 0 'foo/bar/baz/to' '**/t[o]'
+
+# Character class tests
+match 1 x 'a1B' '[[:alpha:]][[:digit:]][[:upper:]]'
+match 0 x 'a' '[[:digit:][:upper:][:space:]]'
+match 1 x 'A' '[[:digit:][:upper:][:space:]]'
+match 1 x '1' '[[:digit:][:upper:][:space:]]'
+match 0 x '1' '[[:digit:][:upper:][:spaci:]]'
+match 1 x ' ' '[[:digit:][:upper:][:space:]]'
+match 0 x '.' '[[:digit:][:upper:][:space:]]'
+match 1 x '.' '[[:digit:][:punct:][:space:]]'
+match 1 x '5' '[[:xdigit:]]'
+match 1 x 'f' '[[:xdigit:]]'
+match 1 x 'D' '[[:xdigit:]]'
+match 1 x '_' '[[:alnum:][:alpha:][:blank:][:cntrl:][:digit:][:graph:][:lower:][:print:][:punct:][:space:][:upper:][:xdigit:]]'
+match 1 x '_' '[[:alnum:][:alpha:][:blank:][:cntrl:][:digit:][:graph:][:lower:][:print:][:punct:][:space:][:upper:][:xdigit:]]'
+match 1 x '.' '[^[:alnum:][:alpha:][:blank:][:cntrl:][:digit:][:lower:][:space:][:upper:][:xdigit:]]'
+match 1 x '5' '[a-c[:digit:]x-z]'
+match 1 x 'b' '[a-c[:digit:]x-z]'
+match 1 x 'y' '[a-c[:digit:]x-z]'
+match 0 x 'q' '[a-c[:digit:]x-z]'
+
+# Additional tests, including some malformed wildmats
+match 1 x ']' '[\\-^]'
+match 0 0 '[' '[\\-^]'
+match 1 x '-' '[\-_]'
+match 1 x ']' '[\]]'
+match 0 0 '\]' '[\]]'
+match 0 0 '\' '[\]]'
+match 0 0 'ab' 'a[]b'
+match 0 x 'a[]b' 'a[]b'
+match 0 x 'ab[' 'ab['
+match 0 0 'ab' '[!'
+match 0 0 'ab' '[-'
+match 1 1 '-' '[-]'
+match 0 0 '-' '[a-'
+match 0 0 '-' '[!a-'
+match 1 x '-' '[--A]'
+match 1 x '5' '[--A]'
+match 1 1 ' ' '[ --]'
+match 1 1 '$' '[ --]'
+match 1 1 '-' '[ --]'
+match 0 0 '0' '[ --]'
+match 1 x '-' '[---]'
+match 1 x '-' '[------]'
+match 0 0 'j' '[a-e-n]'
+match 1 x '-' '[a-e-n]'
+match 1 x 'a' '[!------]'
+match 0 0 '[' '[]-a]'
+match 1 x '^' '[]-a]'
+match 0 0 '^' '[!]-a]'
+match 1 x '[' '[!]-a]'
+match 1 1 '^' '[a^bc]'
+match 1 x '-b]' '[a-]b]'
+match 0 0 '\' '[\]'
+match 1 1 '\' '[\\]'
+match 0 0 '\' '[!\\]'
+match 1 1 'G' '[A-\\]'
+match 0 0 'aaabbb' 'b*a'
+match 0 0 'aabcaa' '*ba*'
+match 1 1 ',' '[,]'
+match 1 1 ',' '[\\,]'
+match 1 1 '\' '[\\,]'
+match 1 1 '-' '[,-.]'
+match 0 0 '+' '[,-.]'
+match 0 0 '-.]' '[,-.]'
+match 1 1 '2' '[\1-\3]'
+match 1 1 '3' '[\1-\3]'
+match 0 0 '4' '[\1-\3]'
+match 1 1 '\' '[[-\]]'
+match 1 1 '[' '[[-\]]'
+match 1 1 ']' '[[-\]]'
+match 0 0 '-' '[[-\]]'
+
+# Test recursion and the abort code (use "wildtest -i" to see iteration counts)
+match 1 1 '-adobe-courier-bold-o-normal--12-120-75-75-m-70-iso8859-1' '-*-*-*-*-*-*-12-*-*-*-m-*-*-*'
+match 0 0 '-adobe-courier-bold-o-normal--12-120-75-75-X-70-iso8859-1' '-*-*-*-*-*-*-12-*-*-*-m-*-*-*'
+match 0 0 '-adobe-courier-bold-o-normal--12-120-75-75-/-70-iso8859-1' '-*-*-*-*-*-*-12-*-*-*-m-*-*-*'
+match 1 1 'XXX/adobe/courier/bold/o/normal//12/120/75/75/m/70/iso8859/1' 'XXX/*/*/*/*/*/*/12/*/*/*/m/*/*/*'
+match 0 0 'XXX/adobe/courier/bold/o/normal//12/120/75/75/X/70/iso8859/1' 'XXX/*/*/*/*/*/*/12/*/*/*/m/*/*/*'
+match 1 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txt' '**/*a*b*g*n*t'
+match 0 0 'abcd/abcdefg/abcdefghijk/abcdefghijklmnop.txtz' '**/*a*b*g*n*t'
+
+test_done
diff --git a/test-wildmatch.c b/test-wildmatch.c
new file mode 100644 (file)
index 0000000..e384c8e
--- /dev/null
@@ -0,0 +1,22 @@
+#include "cache.h"
+#include "wildmatch.h"
+
+int main(int argc, char **argv)
+{
+       int i;
+       for (i = 2; i < argc; i++) {
+               if (argv[i][0] == '/')
+                       die("Forward slash is not allowed at the beginning of the\n"
+                           "pattern because Windows does not like it. Use `XXX/' instead.");
+               else if (!strncmp(argv[i], "XXX/", 4))
+                       argv[i] += 3;
+       }
+       if (!strcmp(argv[1], "wildmatch"))
+               return !!wildmatch(argv[3], argv[2], 0);
+       else if (!strcmp(argv[1], "iwildmatch"))
+               return !!wildmatch(argv[3], argv[2], FNM_CASEFOLD);
+       else if (!strcmp(argv[1], "fnmatch"))
+               return !!fnmatch(argv[3], argv[2], FNM_PATHNAME);
+       else
+               return 1;
+}
diff --git a/wildmatch.c b/wildmatch.c
new file mode 100644 (file)
index 0000000..2d3ed84
--- /dev/null
@@ -0,0 +1,235 @@
+/*
+**  Do shell-style pattern matching for ?, \, [], and * characters.
+**  It is 8bit clean.
+**
+**  Written by Rich $alz, mirror!rs, Wed Nov 26 19:03:17 EST 1986.
+**  Rich $alz is now <rsalz@bbn.com>.
+**
+**  Modified by Wayne Davison to special-case '/' matching, to make '**'
+**  work differently than '*', and to fix the character-class code.
+*/
+
+#include "cache.h"
+#include "wildmatch.h"
+
+typedef unsigned char uchar;
+
+/* What character marks an inverted character class? */
+#define NEGATE_CLASS   '!'
+#define NEGATE_CLASS2  '^'
+
+#define FALSE 0
+#define TRUE 1
+
+#define CC_EQ(class, len, litmatch) ((len) == sizeof (litmatch)-1 \
+                                   && *(class) == *(litmatch) \
+                                   && strncmp((char*)class, litmatch, len) == 0)
+
+#if defined STDC_HEADERS || !defined isascii
+# define ISASCII(c) 1
+#else
+# define ISASCII(c) isascii(c)
+#endif
+
+#ifdef isblank
+# define ISBLANK(c) (ISASCII(c) && isblank(c))
+#else
+# define ISBLANK(c) ((c) == ' ' || (c) == '\t')
+#endif
+
+#ifdef isgraph
+# define ISGRAPH(c) (ISASCII(c) && isgraph(c))
+#else
+# define ISGRAPH(c) (ISASCII(c) && isprint(c) && !isspace(c))
+#endif
+
+#define ISPRINT(c) (ISASCII(c) && isprint(c))
+#define ISDIGIT(c) (ISASCII(c) && isdigit(c))
+#define ISALNUM(c) (ISASCII(c) && isalnum(c))
+#define ISALPHA(c) (ISASCII(c) && isalpha(c))
+#define ISCNTRL(c) (ISASCII(c) && iscntrl(c))
+#define ISLOWER(c) (ISASCII(c) && islower(c))
+#define ISPUNCT(c) (ISASCII(c) && ispunct(c))
+#define ISSPACE(c) (ISASCII(c) && isspace(c))
+#define ISUPPER(c) (ISASCII(c) && isupper(c))
+#define ISXDIGIT(c) (ISASCII(c) && isxdigit(c))
+
+/* Match pattern "p" against "text" */
+static int dowild(const uchar *p, const uchar *text, int force_lower_case)
+{
+       uchar p_ch;
+       const uchar *pattern = p;
+
+       for ( ; (p_ch = *p) != '\0'; text++, p++) {
+               int matched, match_slash, negated;
+               uchar t_ch, prev_ch;
+               if ((t_ch = *text) == '\0' && p_ch != '*')
+                       return ABORT_ALL;
+               if (force_lower_case && ISUPPER(t_ch))
+                       t_ch = tolower(t_ch);
+               if (force_lower_case && ISUPPER(p_ch))
+                       p_ch = tolower(p_ch);
+               switch (p_ch) {
+               case '\\':
+                       /* Literal match with following character.  Note that the test
+                        * in "default" handles the p[1] == '\0' failure case. */
+                       p_ch = *++p;
+                       /* FALLTHROUGH */
+               default:
+                       if (t_ch != p_ch)
+                               return NOMATCH;
+                       continue;
+               case '?':
+                       /* Match anything but '/'. */
+                       if (t_ch == '/')
+                               return NOMATCH;
+                       continue;
+               case '*':
+                       if (*++p == '*') {
+                               const uchar *prev_p = p - 2;
+                               while (*++p == '*') {}
+                               if ((prev_p < pattern || *prev_p == '/') &&
+                                   (*p == '\0' || *p == '/' ||
+                                    (p[0] == '\\' && p[1] == '/'))) {
+                                       /*
+                                        * Assuming we already match 'foo/' and are at
+                                        * <star star slash>, just assume it matches
+                                        * nothing and go ahead match the rest of the
+                                        * pattern with the remaining string. This
+                                        * helps make foo/<*><*>/bar (<> because
+                                        * otherwise it breaks C comment syntax) match
+                                        * both foo/bar and foo/a/bar.
+                                        */
+                                       if (p[0] == '/' &&
+                                           dowild(p + 1, text, force_lower_case) == MATCH)
+                                               return MATCH;
+                                       match_slash = TRUE;
+                               } else
+                                       return ABORT_MALFORMED;
+                       } else
+                               match_slash = FALSE;
+                       if (*p == '\0') {
+                               /* Trailing "**" matches everything.  Trailing "*" matches
+                                * only if there are no more slash characters. */
+                               if (!match_slash) {
+                                       if (strchr((char*)text, '/') != NULL)
+                                               return NOMATCH;
+                               }
+                               return MATCH;
+                       }
+                       while (1) {
+                               if (t_ch == '\0')
+                                       break;
+                               if ((matched = dowild(p, text,  force_lower_case)) != NOMATCH) {
+                                       if (!match_slash || matched != ABORT_TO_STARSTAR)
+                                               return matched;
+                               } else if (!match_slash && t_ch == '/')
+                                       return ABORT_TO_STARSTAR;
+                               t_ch = *++text;
+                       }
+                       return ABORT_ALL;
+               case '[':
+                       p_ch = *++p;
+#ifdef NEGATE_CLASS2
+                       if (p_ch == NEGATE_CLASS2)
+                               p_ch = NEGATE_CLASS;
+#endif
+                       /* Assign literal TRUE/FALSE because of "matched" comparison. */
+                       negated = p_ch == NEGATE_CLASS? TRUE : FALSE;
+                       if (negated) {
+                               /* Inverted character class. */
+                               p_ch = *++p;
+                       }
+                       prev_ch = 0;
+                       matched = FALSE;
+                       do {
+                               if (!p_ch)
+                                       return ABORT_ALL;
+                               if (p_ch == '\\') {
+                                       p_ch = *++p;
+                                       if (!p_ch)
+                                               return ABORT_ALL;
+                                       if (t_ch == p_ch)
+                                               matched = TRUE;
+                               } else if (p_ch == '-' && prev_ch && p[1] && p[1] != ']') {
+                                       p_ch = *++p;
+                                       if (p_ch == '\\') {
+                                               p_ch = *++p;
+                                               if (!p_ch)
+                                                       return ABORT_ALL;
+                                       }
+                                       if (t_ch <= p_ch && t_ch >= prev_ch)
+                                               matched = TRUE;
+                                       p_ch = 0; /* This makes "prev_ch" get set to 0. */
+                               } else if (p_ch == '[' && p[1] == ':') {
+                                       const uchar *s;
+                                       int i;
+                                       for (s = p += 2; (p_ch = *p) && p_ch != ']'; p++) {} /*SHARED ITERATOR*/
+                                       if (!p_ch)
+                                               return ABORT_ALL;
+                                       i = p - s - 1;
+                                       if (i < 0 || p[-1] != ':') {
+                                               /* Didn't find ":]", so treat like a normal set. */
+                                               p = s - 2;
+                                               p_ch = '[';
+                                               if (t_ch == p_ch)
+                                                       matched = TRUE;
+                                               continue;
+                                       }
+                                       if (CC_EQ(s,i, "alnum")) {
+                                               if (ISALNUM(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "alpha")) {
+                                               if (ISALPHA(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "blank")) {
+                                               if (ISBLANK(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "cntrl")) {
+                                               if (ISCNTRL(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "digit")) {
+                                               if (ISDIGIT(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "graph")) {
+                                               if (ISGRAPH(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "lower")) {
+                                               if (ISLOWER(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "print")) {
+                                               if (ISPRINT(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "punct")) {
+                                               if (ISPUNCT(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "space")) {
+                                               if (ISSPACE(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "upper")) {
+                                               if (ISUPPER(t_ch))
+                                                       matched = TRUE;
+                                       } else if (CC_EQ(s,i, "xdigit")) {
+                                               if (ISXDIGIT(t_ch))
+                                                       matched = TRUE;
+                                       } else /* malformed [:class:] string */
+                                               return ABORT_ALL;
+                                       p_ch = 0; /* This makes "prev_ch" get set to 0. */
+                               } else if (t_ch == p_ch)
+                                       matched = TRUE;
+                       } while (prev_ch = p_ch, (p_ch = *++p) != ']');
+                       if (matched == negated || t_ch == '/')
+                               return NOMATCH;
+                       continue;
+               }
+       }
+
+       return *text ? NOMATCH : MATCH;
+}
+
+/* Match the "pattern" against the "text" string. */
+int wildmatch(const char *pattern, const char *text, int flags)
+{
+       return dowild((const uchar*)pattern, (const uchar*)text,
+                     flags & FNM_CASEFOLD ? 1 :0);
+}
diff --git a/wildmatch.h b/wildmatch.h
new file mode 100644 (file)
index 0000000..984a38c
--- /dev/null
@@ -0,0 +1,9 @@
+/* wildmatch.h */
+
+#define ABORT_MALFORMED 2
+#define NOMATCH 1
+#define MATCH 0
+#define ABORT_ALL -1
+#define ABORT_TO_STARSTAR -2
+
+int wildmatch(const char *pattern, const char *text, int flags);