Line data    Source code

       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          16 : 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          16 :         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         352 :                 unsigned char c = *str++;
      57         352 :                 unsigned char d = *pat++;
      58             : 
      59         352 :                 switch (d) {
      60             :                 case '?':       /* Wildcard: anything but nul */
      61           0 :                         if (c == '\0')
      62             :                                 return false;
      63             :                         break;
      64             :                 case '*':       /* Any-length wildcard */
      65          17 :                         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           0 :                         bool match = false, inverted = (*pat == '!');
      72           0 :                         char const *class = pat + inverted;
      73           0 :                         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           0 :                                 unsigned char b = a;
      82             : 
      83           0 :                                 if (a == '\0')  /* Malformed */
      84             :                                         goto literal;
      85             : 
      86           0 :                                 if (class[0] == '-' && class[1] != ']') {
      87           0 :                                         b = class[1];
      88             : 
      89           0 :                                         if (b == '\0')
      90             :                                                 goto literal;
      91             : 
      92           0 :                                         class += 2;
      93             :                                         /* Any special action if a > b? */
      94             :                                 }
      95           0 :                                 match |= (a <= c && c <= b);
      96           0 :                         } while ((a = *class++) != ']');
      97             : 
      98           0 :                         if (match == inverted)
      99             :                                 goto backtrack;
     100             :                         pat = class;
     101             :                         }
     102             :                         break;
     103             :                 case '\\':
     104           0 :                         d = *pat++;
     105             :                         fallthrough;
     106             :                 default:        /* Literal character */
     107             : literal:
     108         335 :                         if (c == d) {
     109          93 :                                 if (d == '\0')
     110             :                                         return true;
     111             :                                 break;
     112             :                         }
     113             : backtrack:
     114         242 :                         if (c == '\0' || !back_pat)
     115             :                                 return false;   /* No point continuing */
     116             :                         /* Try again from last *, one character later in str. */
     117         227 :                         pat = back_pat;
     118         227 :                         str = ++back_str;
     119         227 :                         break;
     120             :                 }
     121             :         }
     122             : }
     123             : EXPORT_SYMBOL(glob_match);