Existing glob is optimized with prefix for "src:/dir1/dir2/*",
but I notices we often use patterns like "src:*dir1/dir2/file.h".

So suffix will help.

It will be hard to notice in most cases, but I use ignore list to bisect
some falures.
E.g. put 100k entries in the file, and build/test as needed.

On one of hard compilation units glob matching was 400s, after the
change 20s.

Still, there is higher level inefficiency in ignore list matching, which
I will
address in followup patches and remove 20s above.

This fixes a build error introduced by https://reviews.llvm.org/D153587
when using an old version of GCC. See
https://reviews.llvm.org/D153587#4644735 for details.

This fixes a build error introduced by https://reviews.llvm.org/D153587

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.

Reviewed By: MaskRay

Differential Revision: https://reviews.llvm.org/D153587

Update this diagnostic to mention the reason (unmatched '['), matching
the other diagnostic about stray '\'. The original pattern is omitted,
as some users may mention the original pattern in another position, not
repeating it.

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.

Differential Revision: https://reviews.llvm.org/D156046

With C++17 there is no Clang pedantic warning or MSVC C5051.

Causes lld build errors

Use forward declarations (BitVector already had one) and an headers to source file that were implicitly using them.