Branch data     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                 :      17316 : 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                 :      17316 :         char const *back_pat = NULL, *back_str = 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                 :      17628 :         for (;;) {
      56                 :      17628 :                 unsigned char c = *str++;
      57                 :      17628 :                 unsigned char d = *pat++;
      58                 :            : 
      59   [ -  -  -  -  :      17628 :                 switch (d) {
                      + ]
      60                 :          0 :                 case '?':       /* Wildcard: anything but nul */
      61         [ #  # ]:          0 :                         if (c == '\0')
      62                 :            :                                 return false;
      63                 :            :                         break;
      64                 :          0 :                 case '*':       /* Any-length wildcard */
      65         [ #  # ]:          0 :                         if (*pat == '\0')       /* Optimize trailing * case */
      66                 :            :                                 return true;
      67                 :            :                         back_pat = pat;
      68                 :            :                         back_str = --str;       /* Allow zero-length match */
      69                 :            :                         break;
      70                 :          0 :                 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                 :          0 :                         do {
      81                 :          0 :                                 unsigned char b = a;
      82                 :            : 
      83         [ #  # ]:          0 :                                 if (a == '\0')  /* Malformed */
      84                 :          0 :                                         goto literal;
      85                 :            : 
      86   [ #  #  #  # ]:          0 :                                 if (class[0] == '-' && class[1] != ']') {
      87                 :          0 :                                         b = class[1];
      88                 :            : 
      89         [ #  # ]:          0 :                                         if (b == '\0')
      90                 :          0 :                                                 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                 :          0 :                                 goto backtrack;
     100                 :            :                         pat = class;
     101                 :            :                         }
     102                 :            :                         break;
     103                 :          0 :                 case '\\':
     104                 :          0 :                         d = *pat++;
     105                 :            :                         /*FALLTHROUGH*/
     106                 :            :                 default:        /* Literal character */
     107                 :      17628 : literal:
     108         [ +  + ]:      17628 :                         if (c == d) {
     109         [ +  - ]:        312 :                                 if (d == '\0')
     110                 :            :                                         return true;
     111                 :            :                                 break;
     112                 :            :                         }
     113                 :      17316 : backtrack:
     114         [ -  + ]:      17316 :                         if (c == '\0' || !back_pat)
     115                 :            :                                 return false;   /* No point continuing */
     116                 :            :                         /* Try again from last *, one character later in str. */
     117                 :          0 :                         pat = back_pat;
     118                 :          0 :                         str = ++back_str;
     119                 :          0 :                         break;
     120                 :            :                 }
     121                 :            :         }
     122                 :            : }
     123                 :            : EXPORT_SYMBOL(glob_match);