[Support] Rewrite GlobPattern

[MaskRay]

Summary

The current implementation has two primary issues:

• Matching a*a*a*b against aaaaaa has exponential complexity.
• BitVector harms data cache and is inefficient for literal matching.

and a minor issue that \ at the end may cause an out of bounds access
in StringRef::operator[].

Switch to an O(|S|*|P|) greedy algorithm instead: factor the pattern
into segments split by '*'. The segment is matched sequentianlly by
finding the first occurrence past the end of the previous match. This
algorithm is used by lots of fnmatch implementations, including musl and
NetBSD's.

In addition, optional<StringRef> Exact, Suffix, Prefix wastes space.
Instead, match the non-metacharacter prefix against the haystack, then
match the pattern with the rest.

In practice *suffix style patterns are less common and our new
algorithm is fast enough, so don't bother storing the non-metacharacter
suffix.

Note: brace expansions (D153587) can leverage the matchOne function.

[ellis]

llvm/lib/Support/GlobPattern.cpp

64–65

Will this fail for the pattern abc\\ (ending with an escaped backslash)?

70

From line 77:

// ']' is allowed as the first character of a character class. '[]' is
// invalid. So, just skip the first character.
size_t End = S.find(']', 2);

I would expect this to break the BracketFrontOfCharacterClass test

72

Can we add something like expected ']' to this error message?

110–111

Since you are storing P, PEnd and S, End anyway, why not store these as StringRefs so there are fewer variables to keep track of?

145

To me it's confusing that Star would hold the index after the *. Could we make this P = Star + 1 and make line 114 Star = P++ (or separate it into two lines)?

[MaskRay]

fix []] bug
address comments
add more tests (when tests are in a good shape, they should be committed separately)

[MaskRay]

llvm/lib/Support/GlobPattern.cpp

64–65

Thanks for catching this. We need to handle this when scanning the pattern.

72

I'd like to do that, but 6 lld/test/ELF tests rely on the particular error message. The change should probably be made in the future...

I think we should drop + S from GlobPattern.cpp diagnostics. The clients can add + S as needed.

110–111

Below we are going to increment various variables, mainly P, S, and B.
If we save P, PEnd as a StringRef, the increment and backtracking will be more cumbersome...

145

Thank's for the question. I renamed Star to SegmentBegin, hopefully it is clearer.

Using P = SegmentBegin; will be slightly more efficient than P = LastStar + 1; as backtracking has one less variable to increment...

[ellis]

LGTM thanks for cleaning this up!

[MaskRay]

rebase
fix [*] matching ]

[MaskRay]

fix IWYU issue

llvm/include/llvm/Support/GlobPattern.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GLOBPATTERN_H
 #define LLVM_SUPPORT_GLOBPATTERN_H
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/Support/Error.h"
 #include <optional>
+#include <string>
 #include <vector>
 
 // This class represents a glob pattern. Supported metacharacters
 // are "*", "?", "\", "[<chars>]", "[^<chars>]", and "[!<chars>]".
 namespace llvm {
 
 template <typename T> class ArrayRef;
 class StringRef;
 
 class GlobPattern {
 public:
   static Expected<GlobPattern> create(StringRef Pat);
   bool match(StringRef S) const;
 
   // Returns true for glob pattern "*". Can be used to avoid expensive
   // preparation/acquisition of the input for match().
-  bool isTrivialMatchAll() const {
-    if (Prefix && Prefix->empty()) {
-      assert(!Suffix);
-      return true;
-    }
-    return false;
-  }
+  bool isTrivialMatchAll() const { return Prefix.empty() && Pat == "*"; }
 
 private:
-  bool matchOne(ArrayRef<BitVector> Pat, StringRef S) const;
+  bool matchOne(StringRef Str) const;
 
-  // Parsed glob pattern.
-  std::vector<BitVector> Tokens;
+  // Brackets with their end position and matched bytes.
+  struct Bracket {
+    const char *Next;
+    BitVector Bytes;
+  };
+  SmallVector<Bracket, 0> Brackets;
 
-  // The following members are for optimization.
-  std::optional<StringRef> Exact;
-  std::optional<StringRef> Prefix;
-  std::optional<StringRef> Suffix;
+  StringRef Prefix, Pat;
 };
 }
 
 #endif // LLVM_SUPPORT_GLOBPATTERN_H

llvm/lib/Support/GlobPattern.cpp

 
 #include "llvm/Support/GlobPattern.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 
 using namespace llvm;
 
-static bool hasWildcard(StringRef S) {
-  return S.find_first_of("?*[\\") != StringRef::npos;
-}
-
 // Expands character ranges and returns a bitmap.
 // For example, "a-cf-hz" is expanded to "abcfghz".
 static Expected<BitVector> expand(StringRef S, StringRef Original) {
   BitVector BV(256, false);
 
   // Expand X-Y.
   for (;;) {
     if (S.size() < 3)
for (;;) {
     S = S.substr(3);
   }
 
   for (char C : S)
     BV[(uint8_t)C] = true;
   return BV;
 }
 
-// This is a scanner for the glob pattern.
-// A glob pattern token is one of "*", "?", "\", "[<chars>]", "[^<chars>]"
-// (which is a negative form of "[<chars>]"), "[!<chars>]" (which is
-// equivalent to "[^<chars>]"), or a non-meta character.
-// This function returns the first token in S.
-static Expected<BitVector> scan(StringRef &S, StringRef Original) {
-  switch (S[0]) {
-  case '*':
-    S = S.substr(1);
-    // '*' is represented by an empty bitvector.
-    // All other bitvectors are 256-bit long.
-    return BitVector();
-  case '?':
-    S = S.substr(1);
-    return BitVector(256, true);
-  case '[': {
+Expected<GlobPattern> GlobPattern::create(StringRef S) {
+  GlobPattern Pat;
+
+  // Store the prefix that does not contain any metacharacter.
+  size_t PrefixSize = S.find_first_of("?*[\\");
+  Pat.Prefix = S.substr(0, PrefixSize);
+  if (PrefixSize == std::string::npos)
+    return Pat;
+  StringRef Original = S;
+  S = S.substr(PrefixSize);
+
+  // Parse brackets.
+  Pat.Pat = S;
+  for (size_t I = 0, E = S.size(); I != E; ++I) {
+    if (S[I] == '[') {
       // ']' is allowed as the first character of a character class. '[]' is
       // invalid. So, just skip the first character.
-    size_t End = S.find(']', 2);
-    if (End == StringRef::npos)
+      ++I;
+      size_t J = S.find(']', I + 1);
+      if (J == StringRef::npos)
         return make_error<StringError>("invalid glob pattern: " + Original,
                                        errc::invalid_argument);
-
-    StringRef Chars = S.substr(1, End - 1);
-    S = S.substr(End + 1);
-    if (Chars.startswith("^") || Chars.startswith("!")) {
-      Expected<BitVector> BV = expand(Chars.substr(1), Original);
+      StringRef Chars = S.substr(I, J);
+      bool Invert = S[I] == '^' || S[I] == '!';
+      Expected<BitVector> BV =
+          Invert ? expand(Chars.substr(1), S) : expand(Chars, S);
       if (!BV)
         return BV.takeError();
-      return BV->flip();
-    }
-    return expand(Chars, Original);
-  }
-  case '\\':
-    // Eat this character and fall through below to treat it like a non-meta
-    // character.
-    S = S.substr(1);
-    [[fallthrough]];
-  default:
-    BitVector BV(256, false);
-    BV[(uint8_t)S[0]] = true;
-    S = S.substr(1);
-    return BV;
-  }
+      if (Invert)
+        BV->flip();
+      Pat.Brackets.push_back(Bracket{S.data() + J + 1, std::move(*BV)});
+      I = J;
+    } else if (S[I] == '\\') {
+      if (I + 1 == E)
+        return make_error<StringError>("invalid glob pattern, stray '\\'",
+                                       errc::invalid_argument);
+      ++I;
     }
-
-Expected<GlobPattern> GlobPattern::create(StringRef S) {
-  GlobPattern Pat;
-
-  // S doesn't contain any metacharacter,
-  // so the regular string comparison should work.
-  if (!hasWildcard(S)) {
-    Pat.Exact = S;
-    return Pat;
   }
-
-  // S is something like "foo*", and the "* is not escaped. We can use
-  // startswith().
-  if (S.endswith("*") && !S.endswith("\\*") && !hasWildcard(S.drop_back())) {
-    Pat.Prefix = S.drop_back();
-    return Pat;
-  }
 
-  // S is something like "*foo". We can use endswith().
-  if (S.startswith("*") && !hasWildcard(S.drop_front())) {
-    Pat.Suffix = S.drop_front();
-    return Pat;
-  }
+bool GlobPattern::match(StringRef S) const {
+  if (!S.startswith(Prefix))
+    return false;
+  S = S.substr(Prefix.size());
+  return matchOne(S);
 
-  // Otherwise, we need to do real glob pattern matching.
-  // Parse the pattern now.
-  StringRef Original = S;
-  while (!S.empty()) {
-    Expected<BitVector> BV = scan(S, Original);
-    if (!BV)
-      return BV.takeError();
-    Pat.Tokens.push_back(*BV);
-  }
-  return Pat;
+// Factor the pattern into segments split by '*'. The segment is matched
+// sequentianlly by finding the first occurrence past the end of the previous
+// match.
+bool GlobPattern::matchOne(StringRef Str) const {
+  const char *P = Pat.data(), *SegmentBegin = nullptr, *S = Str.data(),
+             *SavedS = S;
+  const char *const PEnd = P + Pat.size(), *const End = S + Str.size();
+  size_t B = 0, SavedB = 0;
+  while (S != End) {
+    if (P == PEnd)
+      ;
+    else if (*P == '*') {
+      // The non-* substring on the left of '*' matches the tail of S. Save the
+      // positions to be used by backtracking if we see a mismatch later.
+      SegmentBegin = ++P;
+      SavedS = S;
+      SavedB = B;
+      continue;
+    } else if (*P == '[') {
+      if (Brackets[B].Bytes[uint8_t(*S)]) {
+        P = Brackets[B++].Next;
+        ++S;
+        continue;
       }
-
-bool GlobPattern::match(StringRef S) const {
-  if (Exact)
-    return S == *Exact;
-  if (Prefix)
-    return S.startswith(*Prefix);
-  if (Suffix)
-    return S.endswith(*Suffix);
-  return matchOne(Tokens, S);
+    } else if (*P == '\\') {
+      if (*++P == *S) {
+        ++P;
+        ++S;
+        continue;
       }
-
-// Runs glob pattern Pats against string S.
-bool GlobPattern::matchOne(ArrayRef<BitVector> Pats, StringRef S) const {
-  for (;;) {
-    if (Pats.empty())
-      return S.empty();
-
-    // If Pats[0] is '*', try to match Pats[1..] against all possible
-    // tail strings of S to see at least one pattern succeeds.
-    if (Pats[0].size() == 0) {
-      Pats = Pats.slice(1);
-      if (Pats.empty())
-        // Fast path. If a pattern is '*', it matches anything.
-        return true;
-      for (size_t I = 0, E = S.size(); I < E; ++I)
-        if (matchOne(Pats, S.substr(I)))
-          return true;
-      return false;
+    } else if (*P == *S || *P == '?') {
+      ++P;
+      ++S;
+      continue;
     }
-
-    // If Pats[0] is not '*', it must consume one character.
-    if (S.empty() || !Pats[0][(uint8_t)S[0]])
+    if (!SegmentBegin)
       return false;
-    Pats = Pats.slice(1);
-    S = S.substr(1);
-  }
+    // We have seen a '*'. Backtrack to the saved positions. Shift the S
+    // position to probe the next starting position after the last '*'.
+    P = SegmentBegin;
+    S = ++SavedS;
+    B = SavedB;
+  }
+  // All bytes in Str have been matched. Return true if the rest part of Pat is
+  // empty or contains only '*'.
+  return Pat.find_first_not_of('*', P - Pat.data()) == std::string::npos;
 }

llvm/unittests/Support/GlobPatternTest.cpp

TEST_F(GlobPatternTest, Escape) {
   EXPECT_FALSE(Pat1->match("\\*"));
   EXPECT_FALSE(Pat1->match("a"));
 
   Expected<GlobPattern> Pat2 = GlobPattern::create("a?\\?c");
   EXPECT_TRUE((bool)Pat2);
   EXPECT_TRUE(Pat2->match("ax?c"));
   EXPECT_FALSE(Pat2->match("axxc"));
   EXPECT_FALSE(Pat2->match(""));
+
+  for (size_t I = 0; I != 4; ++I) {
+    std::string S(I, '\\');
+    Expected<GlobPattern> Pat = GlobPattern::create(S);
+    if (I % 2) {
+      EXPECT_FALSE((bool)Pat);
+      handleAllErrors(Pat.takeError(), [&](ErrorInfoBase &) {});
+    } else {
+      EXPECT_TRUE((bool)Pat);
+    }
+  }
 }
 
 TEST_F(GlobPatternTest, BasicCharacterClass) {
   Expected<GlobPattern> Pat1 = GlobPattern::create("[abc-fy-z]");
   EXPECT_TRUE((bool)Pat1);
   EXPECT_TRUE(Pat1->match("a"));
   EXPECT_TRUE(Pat1->match("b"));
   EXPECT_TRUE(Pat1->match("c"));
   EXPECT_TRUE(Pat1->match("d"));
   EXPECT_TRUE(Pat1->match("e"));
   EXPECT_TRUE(Pat1->match("f"));
   EXPECT_TRUE(Pat1->match("y"));
   EXPECT_TRUE(Pat1->match("z"));
   EXPECT_FALSE(Pat1->match("g"));
   EXPECT_FALSE(Pat1->match(""));
+
+  Expected<GlobPattern> Pat2 = GlobPattern::create("[ab]*[cd]?**[ef]");
+  ASSERT_TRUE((bool)Pat2);
+  EXPECT_TRUE(Pat2->match("aecde"));
+  EXPECT_FALSE(Pat2->match("aecdg"));
 }
 
 TEST_F(GlobPatternTest, NegatedCharacterClass) {
   Expected<GlobPattern> Pat1 = GlobPattern::create("[^abc-fy-z]");
   EXPECT_TRUE((bool)Pat1);
   EXPECT_TRUE(Pat1->match("g"));
   EXPECT_FALSE(Pat1->match("a"));
   EXPECT_FALSE(Pat1->match("b"));
TEST_F(GlobPatternTest, IsTrivialMatchAll) {
 
   const char *NegativeCases[] = {"a*", "*a", "?*", "*?", "**", "\\*"};
   for (auto *P : NegativeCases) {
     Expected<GlobPattern> Pat2 = GlobPattern::create(P);
     EXPECT_TRUE((bool)Pat2);
     EXPECT_FALSE(Pat2->isTrivialMatchAll());
   }
 }
+
+TEST_F(GlobPatternTest, NUL) {
+  for (char C : "?*{") {
+    std::string S(1, C);
+    Expected<GlobPattern> Pat = GlobPattern::create(S);
+    ASSERT_TRUE((bool)Pat);
+    EXPECT_TRUE(Pat->match(S));
+    if (C == '*') {
+      EXPECT_TRUE(Pat->match(S + '\0'));
+    } else {
+      EXPECT_FALSE(Pat->match(S + '\0'));
+      handleAllErrors(Pat.takeError(), [&](ErrorInfoBase &) {});
+    }
+  }
+}
+
+TEST_F(GlobPatternTest, Pathological) {
+  std::string P, S(40, 'a');
+  for (int I = 0; I != 30; ++I)
+    P += I % 2 ? "a*" : "[ba]*";
+  Expected<GlobPattern> Pat = GlobPattern::create(P);
+  ASSERT_TRUE((bool)Pat);
+  EXPECT_TRUE(Pat->match(S));
+  P += 'b';
+  Pat = GlobPattern::create(P);
+  ASSERT_TRUE((bool)Pat);
+  EXPECT_FALSE(Pat->match(S));
+  EXPECT_TRUE(Pat->match(S + 'b'));
+}
 }