[GlobPattern] Support brace expansions

[ellis]

Summary

Extend GlobPattern to support brace expansions, e.g., foo.{c,cpp} as discussed in https://reviews.llvm.org/D152762#4425203.

The high level change was to turn Tokens into a list that gets larger when we see a new brace expansion term. Then in GlobPattern::match() we must check against each token group.

This is a breaking change since { will no longer match a literal without escaping. However, \{ will match the literal { before and after this change. Also, from a brief survey of LLVM, it seems that GlobPattern is mostly used for symbol and path matching, which likely won't need { in their patterns.

See https://github.com/devongovett/glob-match#syntax for a nice glob reference.

[MaskRay]

There are some interesting test cases like {a,b}{1,2}. If we don't intend to support

% echo {ab\,d}
, a b d

we can probably report an error, but I suspect supporting it is easier...

[rupprecht]

LGTM, although this logic is already pretty obscure, so it's hard to follow. I wonder if we have fuzzers hooked up to this so we don't have to worry too much if this misses an edge case.

llvm/unittests/Support/GlobPatternTest.cpp

173–220

nit: const auto& should work here?

[ellis]

In D153587#4458387, @MaskRay wrote:

There are some interesting test cases like {a,b}{1,2}. If we don't intend to support

% echo {ab\,d}
, a b d

we can probably report an error, but I suspect supporting it is easier...

I've added the test case {a,b}{1,2} and it works fine. I don't understand the test case {ab\,d}. That looks like a brace expansion with one term (ab,d). If you meant to use a character class, then I also added that test ([*?^{},]).

[ellis]

In D153587#4461154, @rupprecht wrote:

LGTM, although this logic is already pretty obscure, so it's hard to follow. I wonder if we have fuzzers hooked up to this so we don't have to worry too much if this misses an edge case.

I'm not sure how we would add fuzzers to this unit test. I could generate random strings and use that to create patterns and matches, but that won't catch correctness issues, just segfaults.

[ellis]

Add test cases

[ellis]

Add more test cases

[ellis]

Rebase after https://reviews.llvm.org/D156046

[MaskRay]

{a,b}{a,b}{a,b}{a,b}... expands to an exponential number of patterns. This can be a vulnerability. Many glob(3) implementations use a similar approach under an opt-in flag GLOB_BRACE. I think we need a similar feature flag and perhaps special case SanitizerSpecialCaseList (in a separate patch) to set the feature flag.

[ellis]

In D153587#4571266, @MaskRay wrote:

{a,b}{a,b}{a,b}{a,b}... expands to an exponential number of patterns. This can be a vulnerability. Many glob(3) implementations use a similar approach under an opt-in flag GLOB_BRACE. I think we need a similar feature flag and perhaps special case SanitizerSpecialCaseList (in a separate patch) to set the feature flag.

Would it be reasonable to restrict the number of expanded patterns to say 2^10? This would allow for 10 braces with 2 terms each or 2 braces with 10 terms each, which should be plenty in practice.

[MaskRay]

In D153587#4571336, @ellis wrote:

In D153587#4571266, @MaskRay wrote:

{a,b}{a,b}{a,b}{a,b}... expands to an exponential number of patterns. This can be a vulnerability. Many glob(3) implementations use a similar approach under an opt-in flag GLOB_BRACE. I think we need a similar feature flag and perhaps special case SanitizerSpecialCaseList (in a separate patch) to set the feature flag.

Would it be reasonable to restrict the number of expanded patterns to say 2^10? This would allow for 10 braces with 2 terms each or 2 braces with 10 terms each, which should be plenty in practice.

I think existing GlobPattern users are pretty traditional and brace expansion might be a surprise for some.

Some features like SanitizerSpecialCaseList adopting brace expansion is totally fine. They will benefit from a limit (which many glob(3) implementations have as well).
10 seems reasonable. A lower number likely works, too.

[ellis]

Add a limit for the number of subpatterns created by brace expansions

[ellis]

Friendly ping for this and the stacked diff. I recently encountered another bug where I forgot to escape the $ character in a special case list which wouldn't be a problem if we were using globs.

[MaskRay]

I think we likely need to make brace expansion an opt-in feature (similar to GLOB_BRACE for glob). *BSD glob.h defines some arbitrary limits to prevent exponential time causing problems.
Using brace expansion in sanitizer ignore lists is totally fine and I fully support it, but other places may not want the feature with problematic time complexity (assuming that we don't implement NFA or use regex).

[ellis]

In D153587#4622527, @MaskRay wrote:

I think we likely need to make brace expansion an opt-in feature (similar to GLOB_BRACE for glob). *BSD glob.h defines some arbitrary limits to prevent exponential time causing problems.
Using brace expansion in sanitizer ignore lists is totally fine and I fully support it, but other places may not want the feature with problematic time complexity (assuming that we don't implement NFA or use regex).

That makes sense. I think I can implement this by making MaxSubPatterns=1 to mean that globs are disabled and have that be the default. Or did you mean we should add a compile-time variable to enable/disable globs similar to LLVM_ENABLE_THREADS?

[MaskRay]

In D153587#4622617, @ellis wrote:

In D153587#4622527, @MaskRay wrote:

I think we likely need to make brace expansion an opt-in feature (similar to GLOB_BRACE for glob). *BSD glob.h defines some arbitrary limits to prevent exponential time causing problems.
Using brace expansion in sanitizer ignore lists is totally fine and I fully support it, but other places may not want the feature with problematic time complexity (assuming that we don't implement NFA or use regex).

That makes sense. I think I can implement this by making MaxSubPatterns=1 to mean that globs are disabled and have that be the default. Or did you mean we should add a compile-time variable to enable/disable globs similar to LLVM_ENABLE_THREADS?

MaxSubPatterns=1 makes { a metacharacter so that it cannot be used in regular pattern. The parameter can probably be an optional<size_t>.

I think we don't want to introduced configure-time variables for this brace expansion...

[ellis]

Use MaxSubPatterns={} to mean brace expansion is disabled

[MaskRay]

LG! with some issues fixed

llvm/include/llvm/Support/GlobPattern.h

85

Perhaps SmallVector<, 0> to save memory. For the cases we care about performance, the pattern is typically longer than the max inlined element size in libc++/libstdc++ (15 or 23).

llvm/lib/Support/GlobPattern.cpp

75

unmatched [ with a present MaxSubPatterns will cause a crash.

111

a > std::numeric_limits<size_t>::max() / b; to catch multiplication overflow? Compilers can optimize out this division.

https://godbolt.org/z/4PxGT7ad6

llvm/unittests/Support/GlobPatternTest.cpp

56

For new tests, use ASSERT_TRUE((bool)Pat3);
If Pat3 is false, then Pat3->... below would crash.

[ellis]

Resolve comments

llvm/include/llvm/Support/GlobPattern.h

85

I'm curious, why not leave out the 0 and just have SmallVector<char> Pat?

[MaskRay]

llvm/include/llvm/Support/GlobPattern.h

85

I consider it unfortunate... Omitting the argument has been reserved to select an inline size to have about 64 bytes IIUC.

[srj]

This has injected a build break in an older-but-still-supported version of gcc (at least, I think it's supported): arm-linux-gnueabihf-gcc (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0, in which we get failures on lines 62 and 132 of the form

`GlobPattern.cpp: In function ‘llvm::Expected<llvm::SmallVector<std::__cxx11::basic_string<char>, 1> > parseBraceExpansions(llvm::StringRef, std::optional<unsigned int>)’:
GlobPattern.cpp:62:12: error: could not convert ‘SubPatterns’ from ‘llvm::SmallVector<std::__cxx11::basic_string<char> >’ to ‘llvm::Expected<llvm::SmallVector<std::__cxx11::basic_string<char>, 1> >’`

In both cases, replacing the return SubPatterns; with return std::move(SubPatterns); heals the misbehavior. Could we please get a patch to update this to unbreak our 32-bit builds?

(Yes, gcc7.5 is probably getting a bit long in the tooth here, and we're looking to upgrade; unfortunately, we are temporarily hamstrung by some ancient build infrastructure that is essentially incapable of being easily upgraded to newer builds, and it will take us a little time to figure out good replacements, unfortunately.)

UPDATE: I just realized that pull requests from GitHub are now being accepted, so I went and opened one myself to fix this: https://github.com/llvm/llvm-project/pull/66155

[ellis]

In D153587#4644735, @srj wrote:

This has injected a build break in an older-but-still-supported version of gcc (at least, I think it's supported): arm-linux-gnueabihf-gcc (Ubuntu/Linaro 7.5.0-3ubuntu1~18.04) 7.5.0, in which we get failures on lines 62 and 132 of the form

`GlobPattern.cpp: In function ‘llvm::Expected<llvm::SmallVector<std::__cxx11::basic_string<char>, 1> > parseBraceExpansions(llvm::StringRef, std::optional<unsigned int>)’:
GlobPattern.cpp:62:12: error: could not convert ‘SubPatterns’ from ‘llvm::SmallVector<std::__cxx11::basic_string<char> >’ to ‘llvm::Expected<llvm::SmallVector<std::__cxx11::basic_string<char>, 1> >’`

In both cases, replacing the return SubPatterns; with return std::move(SubPatterns); heals the misbehavior. Could we please get a patch to update this to unbreak our 32-bit builds?

(Yes, gcc7.5 is probably getting a bit long in the tooth here, and we're looking to upgrade; unfortunately, we are temporarily hamstrung by some ancient build infrastructure that is essentially incapable of being easily upgraded to newer builds, and it will take us a little time to figure out good replacements, unfortunately.)

UPDATE: I just realized that pull requests from GitHub are now being accepted, so I went and opened one myself to fix this: https://github.com/llvm/llvm-project/pull/66155

Thanks for letting me know. I've just pushed a fix at https://github.com/llvm/llvm-project/commit/dfd0cd1cc182789d351953d2c40b8ccd9fdec34f so let me know if it starts building or not

[srj]

In D153587#4644755, @ellis wrote:

Thanks for letting me know. I've just pushed a fix at https://github.com/llvm/llvm-project/commit/dfd0cd1cc182789d351953d2c40b8ccd9fdec34f so let me know if it starts building or not

Thanks! Testing now

[srj]

In D153587#4644761, @srj wrote:

In D153587#4644755, @ellis wrote:

Thanks for letting me know. I've just pushed a fix at https://github.com/llvm/llvm-project/commit/dfd0cd1cc182789d351953d2c40b8ccd9fdec34f so let me know if it starts building or not

Thanks! Testing now

Seems to have fixed it -- thanks!

llvm/include/llvm/Support/GlobPattern.h

 //===-- GlobPattern.h - glob pattern matcher implementation -*- C++ -*-----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
-// This file implements a glob pattern matcher. The glob pattern is the
-// rule used by the shell.
+// This file implements a glob pattern matcher.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GLOBPATTERN_H
 #define LLVM_SUPPORT_GLOBPATTERN_H
 
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Error.h"
 #include <optional>
 
-// This class represents a glob pattern. Supported metacharacters
-// are "*", "?", "\", "[<chars>]", "[^<chars>]", and "[!<chars>]".
 namespace llvm {
 
+/// This class implements a glob pattern matcher similar to the one found in
+/// bash, but with some key differences. Namely, that \p "*" matches all
+/// characters and does not exclude path separators.
+///
+/// * \p "?" matches a single character.
+/// * \p "*" matches zero or more characters.
+/// * \p "[<chars>]" matches one character in the bracket. Character ranges,
+///   e.g., \p "[a-z]", and negative sets via \p "[^ab]" or \p "[!ab]" are also
+///   supported.
+/// * \p "{<glob>,...}" matches one of the globs in the list. Nested brace
+///   expansions are not supported. If \p MaxSubPatterns is empty then
+///   characters \p "{,}" are treated as literals.
+/// * \p "\" escapes the next character so it is treated as a literal.
+///
+/// Some known edge cases are:
+/// * \p "]" is allowed as the first character in a character class, i.e.,
+///   \p "[]]" is valid and matches the literal \p "]".
+/// * The empty character class, i.e., \p "[]", is invalid.
+/// * Empty or singleton brace expansions, e.g., \p "{}", \p "{a}", are invalid.
+/// * \p "}" and \p "," that are not inside a brace expansion are taken as
+///   literals, e.g., \p ",}" is valid but \p "{" is not.
+///
+/// For example, \p "*[/\\]foo.{c,cpp}" will match (unix or windows) paths to
+/// all files named \p "foo.c" or \p "foo.cpp".
 class GlobPattern {
 public:
-  static Expected<GlobPattern> create(StringRef Pat);
+  /// \param Pat the pattern to match against
+  /// \param MaxSubPatterns if provided limit the number of allowed subpatterns
+  ///                       created from expanding braces otherwise disable
+  ///                       brace expansion
+  static Expected<GlobPattern>
+  create(StringRef Pat, std::optional<size_t> MaxSubPatterns = {});
+  /// \returns \p true if \p S matches this glob pattern
   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 { return Prefix.empty() && Pat == "*"; }
+  bool isTrivialMatchAll() const {
+    if (!Prefix.empty())
+      return false;
+    if (SubGlobs.size() != 1)
+      return false;
+    return SubGlobs[0].getPat() == "*";
+  }
 
 private:
-  bool matchOne(StringRef Str) const;
+  StringRef Prefix;
+
+  struct SubGlobPattern {
+    /// \param Pat the pattern to match against
+    static Expected<SubGlobPattern> create(StringRef Pat);
+    /// \returns \p true if \p S matches this glob pattern
+    bool match(StringRef S) const;
+    StringRef getPat() const { return StringRef(Pat.data(), Pat.size()); }
 
     // Brackets with their end position and matched bytes.
     struct Bracket {
-    const char *Next;
+      size_t NextOffset;
       BitVector Bytes;
     };
     SmallVector<Bracket, 0> Brackets;
-
-  StringRef Prefix, Pat;
+    SmallVector<char, 0> Pat;
+  };
+  SmallVector<SubGlobPattern, 1> SubGlobs;
 };
 }
 
 #endif // LLVM_SUPPORT_GLOBPATTERN_H

llvm/lib/Support/GlobPattern.cpp

 //===-- GlobPattern.cpp - Glob pattern matcher implementation -------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements a glob pattern matcher.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/GlobPattern.h"
-#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Errc.h"
 
 using namespace llvm;
 
 // Expands character ranges and returns a bitmap.
 // For example, "a-cf-hz" is expanded to "abcfghz".
 static Expected<BitVector> expand(StringRef S, StringRef Original) {
for (;;) {
     S = S.substr(3);
   }
 
   for (char C : S)
     BV[(uint8_t)C] = true;
   return BV;
 }
 
-Expected<GlobPattern> GlobPattern::create(StringRef S) {
+// Identify brace expansions in S and return the list of patterns they expand
+// into.
+static Expected<SmallVector<std::string, 1>>
+parseBraceExpansions(StringRef S, std::optional<size_t> MaxSubPatterns) {
+  SmallVector<std::string> SubPatterns = {S.str()};
+  if (!MaxSubPatterns || !S.contains('{'))
+    return SubPatterns;
+
+  struct BraceExpansion {
+    size_t Start;
+    size_t Length;
+    SmallVector<StringRef, 2> Terms;
+  };
+  SmallVector<BraceExpansion, 0> BraceExpansions;
+
+  BraceExpansion *CurrentBE = nullptr;
+  size_t TermBegin;
+  for (size_t I = 0, E = S.size(); I != E; ++I) {
+    if (S[I] == '[') {
+      I = S.find(']', I + 2);
+      if (I == std::string::npos)
+        return make_error<StringError>("invalid glob pattern, unmatched '['",
+                                       errc::invalid_argument);
+    } else if (S[I] == '{') {
+      if (CurrentBE)
+        return make_error<StringError>(
+            "nested brace expansions are not supported",
+            errc::invalid_argument);
+      CurrentBE = &BraceExpansions.emplace_back();
+      CurrentBE->Start = I;
+      TermBegin = I + 1;
+    } else if (S[I] == ',') {
+      if (!CurrentBE)
+        continue;
+      CurrentBE->Terms.push_back(S.substr(TermBegin, I - TermBegin));
+      TermBegin = I + 1;
+    } else if (S[I] == '}') {
+      if (!CurrentBE)
+        continue;
+      if (CurrentBE->Terms.empty())
+        return make_error<StringError>(
+            "empty or singleton brace expansions are not supported",
+            errc::invalid_argument);
+      CurrentBE->Terms.push_back(S.substr(TermBegin, I - TermBegin));
+      CurrentBE->Length = I - CurrentBE->Start + 1;
+      CurrentBE = nullptr;
+    } else if (S[I] == '\\') {
+      if (++I == E)
+        return make_error<StringError>("invalid glob pattern, stray '\\'",
+                                       errc::invalid_argument);
+    }
+  }
+  if (CurrentBE)
+    return make_error<StringError>("incomplete brace expansion",
+                                   errc::invalid_argument);
+
+  size_t NumSubPatterns = 1;
+  for (auto &BE : BraceExpansions) {
+    if (NumSubPatterns > std::numeric_limits<size_t>::max() / BE.Terms.size()) {
+      NumSubPatterns = std::numeric_limits<size_t>::max();
+      break;
+    }
+    NumSubPatterns *= BE.Terms.size();
+  }
+  if (NumSubPatterns > *MaxSubPatterns)
+    return make_error<StringError>("too many brace expansions",
+                                   errc::invalid_argument);
+  // Replace brace expansions in reverse order so that we don't invalidate
+  // earlier start indices
+  for (auto &BE : reverse(BraceExpansions)) {
+    SmallVector<std::string> OrigSubPatterns;
+    std::swap(SubPatterns, OrigSubPatterns);
+    for (StringRef Term : BE.Terms)
+      for (StringRef Orig : OrigSubPatterns)
+        SubPatterns.emplace_back(Orig).replace(BE.Start, BE.Length, Term);
+  }
+  return SubPatterns;
+}
+
+Expected<GlobPattern>
+GlobPattern::create(StringRef S, std::optional<size_t> MaxSubPatterns) {
   GlobPattern Pat;
 
   // Store the prefix that does not contain any metacharacter.
-  size_t PrefixSize = S.find_first_of("?*[\\");
+  size_t PrefixSize = S.find_first_of("?*[{\\");
   Pat.Prefix = S.substr(0, PrefixSize);
   if (PrefixSize == std::string::npos)
     return Pat;
   S = S.substr(PrefixSize);
 
+  SmallVector<std::string, 1> SubPats;
+  if (auto Err = parseBraceExpansions(S, MaxSubPatterns).moveInto(SubPats))
+    return Err;
+  for (StringRef SubPat : SubPats) {
+    auto SubGlobOrErr = SubGlobPattern::create(SubPat);
+    if (!SubGlobOrErr)
+      return SubGlobOrErr.takeError();
+    Pat.SubGlobs.push_back(*SubGlobOrErr);
+  }
+
+  return Pat;
+}
+
+Expected<GlobPattern::SubGlobPattern>
+GlobPattern::SubGlobPattern::create(StringRef S) {
+  SubGlobPattern Pat;
+
   // Parse brackets.
-  Pat.Pat = S;
+  Pat.Pat.assign(S.begin(), S.end());
   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.
       ++I;
       size_t J = S.find(']', I + 1);
       if (J == StringRef::npos)
         return make_error<StringError>("invalid glob pattern, unmatched '['",
                                        errc::invalid_argument);
       StringRef Chars = S.substr(I, J - I);
       bool Invert = S[I] == '^' || S[I] == '!';
       Expected<BitVector> BV =
           Invert ? expand(Chars.substr(1), S) : expand(Chars, S);
       if (!BV)
         return BV.takeError();
       if (Invert)
         BV->flip();
-      Pat.Brackets.push_back(Bracket{S.data() + J + 1, std::move(*BV)});
+      Pat.Brackets.push_back(Bracket{J + 1, std::move(*BV)});
       I = J;
     } else if (S[I] == '\\') {
       if (++I == E)
         return make_error<StringError>("invalid glob pattern, stray '\\'",
                                        errc::invalid_argument);
     }
   }
   return Pat;
 }
 
 bool GlobPattern::match(StringRef S) const {
-  return S.consume_front(Prefix) && matchOne(S);
+  if (!S.consume_front(Prefix))
+    return false;
+  if (SubGlobs.empty() && S.empty())
+    return true;
+  for (auto &Glob : SubGlobs)
+    if (Glob.match(S))
+      return true;
+  return false;
 }
 
 // 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 {
+bool GlobPattern::SubGlobPattern::match(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;
+        P = Pat.data() + Brackets[B++].NextOffset;
         ++S;
         continue;
       }
     } else if (*P == '\\') {
       if (*++P == *S) {
         ++P;
         ++S;
         continue;
       }
     } else if (*P == *S || *P == '?') {
       ++P;
       ++S;
       continue;
     }
     if (!SegmentBegin)
       return false;
     // We have seen a '*'. Backtrack to the saved positions. Shift the S
     // position to probe the next starting position in the segment.
     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;
+  return getPat().find_first_not_of('*', P - Pat.data()) == std::string::npos;
 }

llvm/unittests/Support/GlobPatternTest.cpp

TEST_F(GlobPatternTest, Escape) {
   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(""));
 
+  auto Pat3 = GlobPattern::create("\\{");
+  ASSERT_TRUE((bool)Pat3);
+  EXPECT_TRUE(Pat3->match("{"));
+  EXPECT_FALSE(Pat3->match("\\{"));
+  EXPECT_FALSE(Pat3->match(""));
+
+  auto Pat4 = GlobPattern::create("\\a");
+  ASSERT_TRUE((bool)Pat4);
+  EXPECT_TRUE(Pat4->match("a"));
+  EXPECT_FALSE(Pat4->match("\\a"));
+
   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, BracketFrontOfCharacterClass) {
   EXPECT_TRUE((bool)Pat1);
   EXPECT_TRUE(Pat1->match("]x"));
   EXPECT_TRUE(Pat1->match("ax"));
   EXPECT_FALSE(Pat1->match("a]x"));
   EXPECT_FALSE(Pat1->match(""));
 }
 
 TEST_F(GlobPatternTest, SpecialCharsInCharacterClass) {
-  Expected<GlobPattern> Pat1 = GlobPattern::create("[*?^]");
-  EXPECT_TRUE((bool)Pat1);
+  auto Pat1 = GlobPattern::create("[*?^{},]");
+  ASSERT_TRUE((bool)Pat1);
   EXPECT_TRUE(Pat1->match("*"));
   EXPECT_TRUE(Pat1->match("?"));
   EXPECT_TRUE(Pat1->match("^"));
-  EXPECT_FALSE(Pat1->match("*?^"));
+  EXPECT_TRUE(Pat1->match("{"));
+  EXPECT_TRUE(Pat1->match("}"));
+  EXPECT_TRUE(Pat1->match(","));
+  EXPECT_FALSE(Pat1->match("*?^{},"));
   EXPECT_FALSE(Pat1->match(""));
 
   Expected<GlobPattern> Pat2 = GlobPattern::create("[*]");
   ASSERT_TRUE((bool)Pat2);
   EXPECT_TRUE(Pat2->match("*"));
   EXPECT_FALSE(Pat2->match("]"));
 }
 
 TEST_F(GlobPatternTest, Invalid) {
-  Expected<GlobPattern> Pat1 = GlobPattern::create("[");
+  for (const auto &InvalidPattern : {"[", "[]"}) {
+    auto Pat1 = GlobPattern::create(InvalidPattern);
+    EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
+    handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
+  }
+}
+
+TEST_F(GlobPatternTest, InvalidBraceExpansion) {
+  for (const auto &InvalidPattern :
+       {"{", "{{", "{\\", "{\\}", "{}", "{a}", "[{}"}) {
+    auto Pat1 = GlobPattern::create(InvalidPattern, /*MaxSubPatterns=*/1024);
+    EXPECT_FALSE((bool)Pat1) << "Expected invalid pattern: " << InvalidPattern;
+    handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
+  }
+  auto Pat1 = GlobPattern::create("{a,b}{c,d}{e,f}", /*MaxSubPatterns=*/7);
   EXPECT_FALSE((bool)Pat1);
   handleAllErrors(Pat1.takeError(), [&](ErrorInfoBase &EIB) {});
+}
+
+TEST_F(GlobPatternTest, BraceExpansion) {
+  auto Pat1 = GlobPattern::create("{a,b}{1,2}", /*MaxSubPatterns=*/1024);
+  ASSERT_TRUE((bool)Pat1);
+  EXPECT_TRUE(Pat1->match("a1"));
+  EXPECT_TRUE(Pat1->match("a2"));
+  EXPECT_TRUE(Pat1->match("b1"));
+  EXPECT_TRUE(Pat1->match("b2"));
+  EXPECT_FALSE(Pat1->match("ab"));
 
-  Expected<GlobPattern> Pat2 = GlobPattern::create("[]");
-  EXPECT_FALSE((bool)Pat2);
-  handleAllErrors(Pat2.takeError(), [&](ErrorInfoBase &EIB) {});
+  auto Pat2 = GlobPattern::create(",}{foo,\\,\\},z*}", /*MaxSubPatterns=*/1024);
+  ASSERT_TRUE((bool)Pat2);
+  EXPECT_TRUE(Pat2->match(",}foo"));
+  EXPECT_TRUE(Pat2->match(",},}"));
+  EXPECT_TRUE(Pat2->match(",}z"));
+  EXPECT_TRUE(Pat2->match(",}zoo"));
+  EXPECT_FALSE(Pat2->match(",}fooz"));
+  EXPECT_FALSE(Pat2->match("foo"));
+  EXPECT_FALSE(Pat2->match(""));
+
+  // This test breaks if we store terms separately and attempt to match them one
+  // by one instead of using subglobs
+  auto Pat3 = GlobPattern::create("{a,ab}b", /*MaxSubPatterns=*/1024);
+  ASSERT_TRUE((bool)Pat3);
+  EXPECT_TRUE(Pat3->match("ab"));
+  EXPECT_TRUE(Pat3->match("abb"));
+}
+
+TEST_F(GlobPatternTest, NoBraceExpansion) {
+  auto Pat1 = GlobPattern::create("{a,b}{1,2}");
+  ASSERT_TRUE((bool)Pat1);
+  EXPECT_TRUE(Pat1->match("{a,b}{1,2}"));
+  EXPECT_FALSE(Pat1->match("a1"));
+
+  auto Pat2 = GlobPattern::create("{{");
+  ASSERT_TRUE((bool)Pat2);
+  EXPECT_TRUE(Pat2->match("{{"));
+}
+
+TEST_F(GlobPatternTest, BraceExpansionCharacterClass) {
+  // Matches mangled names of C++ standard library functions
+  auto Pat =
+      GlobPattern::create("_Z{N,NK,}S[tabsiod]*", /*MaxSubPatterns=*/1024);
+  ASSERT_TRUE((bool)Pat);
+  EXPECT_TRUE(Pat->match("_ZNSt6vectorIiSaIiEE9push_backEOi"));
+  EXPECT_TRUE(Pat->match("_ZNKStfoo"));
+  EXPECT_TRUE(Pat->match("_ZNSafoo"));
+  EXPECT_TRUE(Pat->match("_ZStfoo"));
+  EXPECT_FALSE(Pat->match("_Zfoo"));
 }
 
 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);
TEST_F(GlobPatternTest, IsTrivialMatchAll) {
   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 : "?*{") {
+  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');
+  StringRef Pieces[] = {"a*", "[ba]*", "{b*,a*}*"};
   for (int I = 0; I != 30; ++I)
-    P += I % 2 ? "a*" : "[ba]*";
-  Expected<GlobPattern> Pat = GlobPattern::create(P);
+    P += Pieces[I % 3];
+  Expected<GlobPattern> Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);
   ASSERT_TRUE((bool)Pat);
   EXPECT_TRUE(Pat->match(S));
   P += 'b';
-  Pat = GlobPattern::create(P);
+  Pat = GlobPattern::create(P, /*MaxSubPatterns=*/1024);
   ASSERT_TRUE((bool)Pat);
   EXPECT_FALSE(Pat->match(S));
   EXPECT_TRUE(Pat->match(S + 'b'));
 }
 }