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