1*4882a593Smuzhiyun #include <linux/module.h>
2*4882a593Smuzhiyun #include <linux/glob.h>
3*4882a593Smuzhiyun
4*4882a593Smuzhiyun /*
5*4882a593Smuzhiyun * The only reason this code can be compiled as a module is because the
6*4882a593Smuzhiyun * ATA code that depends on it can be as well. In practice, they're
7*4882a593Smuzhiyun * both usually compiled in and the module overhead goes away.
8*4882a593Smuzhiyun */
9*4882a593Smuzhiyun MODULE_DESCRIPTION("glob(7) matching");
10*4882a593Smuzhiyun MODULE_LICENSE("Dual MIT/GPL");
11*4882a593Smuzhiyun
12*4882a593Smuzhiyun /**
13*4882a593Smuzhiyun * glob_match - Shell-style pattern matching, like !fnmatch(pat, str, 0)
14*4882a593Smuzhiyun * @pat: Shell-style pattern to match, e.g. "*.[ch]".
15*4882a593Smuzhiyun * @str: String to match. The pattern must match the entire string.
16*4882a593Smuzhiyun *
17*4882a593Smuzhiyun * Perform shell-style glob matching, returning true (1) if the match
18*4882a593Smuzhiyun * succeeds, or false (0) if it fails. Equivalent to !fnmatch(@pat, @str, 0).
19*4882a593Smuzhiyun *
20*4882a593Smuzhiyun * Pattern metacharacters are ?, *, [ and \.
21*4882a593Smuzhiyun * (And, inside character classes, !, - and ].)
22*4882a593Smuzhiyun *
23*4882a593Smuzhiyun * This is small and simple implementation intended for device blacklists
24*4882a593Smuzhiyun * where a string is matched against a number of patterns. Thus, it
25*4882a593Smuzhiyun * does not preprocess the patterns. It is non-recursive, and run-time
26*4882a593Smuzhiyun * is at most quadratic: strlen(@str)*strlen(@pat).
27*4882a593Smuzhiyun *
28*4882a593Smuzhiyun * An example of the worst case is glob_match("*aaaaa", "aaaaaaaaaa");
29*4882a593Smuzhiyun * it takes 6 passes over the pattern before matching the string.
30*4882a593Smuzhiyun *
31*4882a593Smuzhiyun * Like !fnmatch(@pat, @str, 0) and unlike the shell, this does NOT
32*4882a593Smuzhiyun * treat / or leading . specially; it isn't actually used for pathnames.
33*4882a593Smuzhiyun *
34*4882a593Smuzhiyun * Note that according to glob(7) (and unlike bash), character classes
35*4882a593Smuzhiyun * are complemented by a leading !; this does not support the regex-style
36*4882a593Smuzhiyun * [^a-z] syntax.
37*4882a593Smuzhiyun *
38*4882a593Smuzhiyun * An opening bracket without a matching close is matched literally.
39*4882a593Smuzhiyun */
glob_match(char const * pat,char const * str)40*4882a593Smuzhiyun bool __pure glob_match(char const *pat, char const *str)
41*4882a593Smuzhiyun {
42*4882a593Smuzhiyun /*
43*4882a593Smuzhiyun * Backtrack to previous * on mismatch and retry starting one
44*4882a593Smuzhiyun * character later in the string. Because * matches all characters
45*4882a593Smuzhiyun * (no exception for /), it can be easily proved that there's
46*4882a593Smuzhiyun * never a need to backtrack multiple levels.
47*4882a593Smuzhiyun */
48*4882a593Smuzhiyun char const *back_pat = NULL, *back_str = back_str;
49*4882a593Smuzhiyun
50*4882a593Smuzhiyun /*
51*4882a593Smuzhiyun * Loop over each token (character or class) in pat, matching
52*4882a593Smuzhiyun * it against the remaining unmatched tail of str. Return false
53*4882a593Smuzhiyun * on mismatch, or true after matching the trailing nul bytes.
54*4882a593Smuzhiyun */
55*4882a593Smuzhiyun for (;;) {
56*4882a593Smuzhiyun unsigned char c = *str++;
57*4882a593Smuzhiyun unsigned char d = *pat++;
58*4882a593Smuzhiyun
59*4882a593Smuzhiyun switch (d) {
60*4882a593Smuzhiyun case '?': /* Wildcard: anything but nul */
61*4882a593Smuzhiyun if (c == '\0')
62*4882a593Smuzhiyun return false;
63*4882a593Smuzhiyun break;
64*4882a593Smuzhiyun case '*': /* Any-length wildcard */
65*4882a593Smuzhiyun if (*pat == '\0') /* Optimize trailing * case */
66*4882a593Smuzhiyun return true;
67*4882a593Smuzhiyun back_pat = pat;
68*4882a593Smuzhiyun back_str = --str; /* Allow zero-length match */
69*4882a593Smuzhiyun break;
70*4882a593Smuzhiyun case '[': { /* Character class */
71*4882a593Smuzhiyun bool match = false, inverted = (*pat == '!');
72*4882a593Smuzhiyun char const *class = pat + inverted;
73*4882a593Smuzhiyun unsigned char a = *class++;
74*4882a593Smuzhiyun
75*4882a593Smuzhiyun /*
76*4882a593Smuzhiyun * Iterate over each span in the character class.
77*4882a593Smuzhiyun * A span is either a single character a, or a
78*4882a593Smuzhiyun * range a-b. The first span may begin with ']'.
79*4882a593Smuzhiyun */
80*4882a593Smuzhiyun do {
81*4882a593Smuzhiyun unsigned char b = a;
82*4882a593Smuzhiyun
83*4882a593Smuzhiyun if (a == '\0') /* Malformed */
84*4882a593Smuzhiyun goto literal;
85*4882a593Smuzhiyun
86*4882a593Smuzhiyun if (class[0] == '-' && class[1] != ']') {
87*4882a593Smuzhiyun b = class[1];
88*4882a593Smuzhiyun
89*4882a593Smuzhiyun if (b == '\0')
90*4882a593Smuzhiyun goto literal;
91*4882a593Smuzhiyun
92*4882a593Smuzhiyun class += 2;
93*4882a593Smuzhiyun /* Any special action if a > b? */
94*4882a593Smuzhiyun }
95*4882a593Smuzhiyun match |= (a <= c && c <= b);
96*4882a593Smuzhiyun } while ((a = *class++) != ']');
97*4882a593Smuzhiyun
98*4882a593Smuzhiyun if (match == inverted)
99*4882a593Smuzhiyun goto backtrack;
100*4882a593Smuzhiyun pat = class;
101*4882a593Smuzhiyun }
102*4882a593Smuzhiyun break;
103*4882a593Smuzhiyun case '\\':
104*4882a593Smuzhiyun d = *pat++;
105*4882a593Smuzhiyun /* fall through */
106*4882a593Smuzhiyun default: /* Literal character */
107*4882a593Smuzhiyun literal:
108*4882a593Smuzhiyun if (c == d) {
109*4882a593Smuzhiyun if (d == '\0')
110*4882a593Smuzhiyun return true;
111*4882a593Smuzhiyun break;
112*4882a593Smuzhiyun }
113*4882a593Smuzhiyun backtrack:
114*4882a593Smuzhiyun if (c == '\0' || !back_pat)
115*4882a593Smuzhiyun return false; /* No point continuing */
116*4882a593Smuzhiyun /* Try again from last *, one character later in str. */
117*4882a593Smuzhiyun pat = back_pat;
118*4882a593Smuzhiyun str = ++back_str;
119*4882a593Smuzhiyun break;
120*4882a593Smuzhiyun }
121*4882a593Smuzhiyun }
122*4882a593Smuzhiyun }
123*4882a593Smuzhiyun EXPORT_SYMBOL(glob_match);
124