[Support] Add GlobPattern::isTrivialMatchAll()

[andrewng]

Summary

GlobPattern::isTrivialMatchAll() returns true for the GlobPattern "*"
which will match all inputs.

This can be used to avoid performing expensive preparation of the input
for match() when the result of the match will always be true.

[andrewng]

This is a prerequisite of D87469.

[MaskRay]

GlobPattern::matchOne has a fast path for '*'. Isn't it fast enough?

llvm/include/llvm/Support/GlobPattern.h

35

This is not correct (*foo). Suffix may be non-empty.

[andrewng]

In D87468#2266228, @MaskRay wrote:

GlobPattern::matchOne has a fast path for '*'. Isn't it fast enough?

As mentioned in the summary, this is to avoid cost in preparing/acquiring the input, i.e. not the speed of the match but overhead related to the input.

llvm/include/llvm/Support/GlobPattern.h

35

Prefix has priority over Suffix in the GlobPattern creation code, which is why this code works. The current code doesn't support both a Prefix and a Suffix.

[MaskRay]

In D87468#2266262, @andrewng wrote:

In D87468#2266228, @MaskRay wrote:

GlobPattern::matchOne has a fast path for '*'. Isn't it fast enough?

As mentioned in the summary, this is to avoid cost in preparing/acquiring the input, i.e. not the speed of the match but overhead related to the input.

Can you demonstrate how the old code has overhead related to the input?

[andrewng]

In D87468#2266310, @MaskRay wrote:

Can you demonstrate how the old code has overhead related to the input?

This new function enables the user of the GlobPattern to avoid overhead, see D87469 for an example.

[grimar]

llvm/include/llvm/Support/GlobPattern.h

35

I think this needs a comment, saying that this member can be used "to avoid cost in preparing/acquiring the input"
when it is expensive. Otherwise it is probably not clear why it is exist/needed.

Not strong suggestions/thoughts:

1. Perhaps, worth to add assert(!Suffix);` to emphasize we don't expect it?

if (Prefix && Prefix->empty()) {
  assert(!Suffix);
  return true;
}

return false;

2. Instead of having isTrivialMatchAll, we could add a member (+ getPatternString getter) to store the

original pattern string and just check it is equal to the * on the callers side. It can be a bit more generic API then.

[andrewng]

Updated to address review comments and suggestions.

[andrewng]

llvm/include/llvm/Support/GlobPattern.h

35

Added comment and adopted suggestion of the assertion on Suffix, thanks. Generally, I don't think it would be worthwhile storing the original pattern just for this use case.

[MaskRay]

I've checked the dependent patch. This looks reasonable. Please wait for @grimar as well.

[grimar]

LGTM

[MaskRay]

llvm/unittests/Support/GlobPatternTest.cpp

141

Most patterns are expected to return false.

The negative patterns can be organized as a const char * array to improve readability

141

You don't need EXPECT_TRUE((bool)Pat2); because it is implied by the following Pat2->

[andrewng]

Update for review comments.

[andrewng]

llvm/unittests/Support/GlobPatternTest.cpp

141

Although it is implied by the -> operator, it feels better to keep the check separate and this is the pattern followed by the other tests in this file.

[MaskRay]

llvm/unittests/Support/GlobPatternTest.cpp

143

You can use a range-based for here.

[andrewng]

Update for review suggestion.

[andrewng]

llvm/unittests/Support/GlobPatternTest.cpp

143

Thanks for spotting that one!

llvm/include/llvm/Support/GlobPattern.h

 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;
+  }
+
 private:
   bool matchOne(ArrayRef<BitVector> Pat, StringRef S) const;
 
   // Parsed glob pattern.
   std::vector<BitVector> Tokens;
 
   // The following members are for optimization.
   Optional<StringRef> Exact;
   Optional<StringRef> Prefix;
   Optional<StringRef> Suffix;
 };
 }
 
 #endif // LLVM_SUPPORT_GLOB_PATTERN_H

llvm/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"));
 }
+
+TEST_F(GlobPatternTest, IsTrivialMatchAll) {
+  Expected<GlobPattern> Pat1 = GlobPattern::create("*");
+  EXPECT_TRUE((bool)Pat1);
+  EXPECT_TRUE(Pat1->isTrivialMatchAll());
+
+  const char *NegativeCases[] = {"a*", "*a", "?*", "*?", "**", "\\*"};
+  for (unsigned i = 0; i < array_lengthof(NegativeCases); ++i) {
+    Expected<GlobPattern> Pat2 = GlobPattern::create(NegativeCases[i]);
+    EXPECT_TRUE((bool)Pat2);
+    EXPECT_FALSE(Pat2->isTrivialMatchAll());
+  }
+}
 }