[Support/GlobPattern] - Treat multiple stars('*') as single.

[grimar]

Summary

Found that when fuzzed LLD's linkerscripts.
Next one takes long time to run for me (several seconds), causing
fuzzer to treat test as 'hang':

SECTIONS {    .foo : { *(********************************************boo) }   }

That happens because complexity grows too fast when there are multiple
stars in pattern, though I believe we can just convert all ** to *`.

Testcase is provided. With patch it runs instantly, without - takes huge time,

[ruiu]

You don't want to "fix" this because there are a lot of other pathetic patterns that can hangs up the matcher. There is no reason to handle this specially.

[ruiu]

I mean, I believe you can still hang this up by passing the following inputs (or something like that, I didn't test this):

Pattern: a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*z
Input: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

This is a fundamental limitation of the current algorithm because it's based on backtracking, which is exponential in the worst case. There are better algorithms, but I don't think we need that complexity here. In this test case, you are intentionally trying to break the linker, and it breaks as you wish. You simply shouldn't do that. I don't think we need to "fix" this.

[grimar]

In D36307#832783, @ruiu wrote:

I mean, I believe you can still hang this up by passing the following inputs (or something like that, I didn't test this):

Pattern: a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*z
Input: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

This is a fundamental limitation of the current algorithm because it's based on backtracking, which is exponential in the worst case. There are better algorithms, but I don't think we need that complexity here. In this test case, you are intentionally trying to break the linker, and it breaks as you wish. You simply shouldn't do that. I don't think we need to "fix" this.

I see. Closing it. Thanks for looking at this one.

lib/Support/GlobPattern.cpp

 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) {
+      // '**' is efficiency the same as '*', skip them to optimize.
+      while (!Pats.empty() && Pats.front().empty())
         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;
     }
 
     // If Pats[0] is not '*', it must consume one character.
     if (S.empty() || !Pats[0][(uint8_t)S[0]])
       return false;
     Pats = Pats.slice(1);
     S = S.substr(1);
   }
 }

unittests/Support/GlobPatternTest.cpp

 TEST_F(GlobPatternTest, ExtSym) {
   Expected<GlobPattern> Pat1 = GlobPattern::create("a*\xFF");
   EXPECT_TRUE((bool)Pat1);
   EXPECT_TRUE(Pat1->match("axxx\xFF"));
   Expected<GlobPattern> Pat2 = GlobPattern::create("[\xFF-\xFF]");
   EXPECT_TRUE((bool)Pat2);
   EXPECT_TRUE(Pat2->match("\xFF"));
 }
+
+// Check this test does not take ages to complete.
+TEST_F(GlobPatternTest, MultipleStarts) {
+  std::string Stars(1024, '*');
+  Stars += 'X';
+  std::string Stars2(1024, 'A');
+
+  Expected<GlobPattern> Pat = GlobPattern::create(Stars);
+  EXPECT_TRUE((bool)Pat);
+  EXPECT_FALSE(Pat->match(Stars2));
+}
 }