glob.c 3.5 KB

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