[clang-tidy][NFC] Tweak GlobList to iterate backwards

[njames93]

Summary

By iterating backwards over the globs we can exit the loop as soon as we find a match.

While we're here:

• Regex doesn't need to be mutable.
• We can reserve the amount of Globs needed ahead of time.
• Using a SmallVector with size 0 is slightly more space efficient than a std::vector.

[aaron.ballman]

LGTM with a request to add a comment.

clang-tools-extra/clang-tidy/GlobList.cpp

56–58

I'd appreciate a comment here that mentions *why* reversing backwards means we can early return. It took me a few tries to remember that glob patterns can undo earlier glob patterns, so that the last pattern is the one that matters.

[njames93]

clang-tools-extra/clang-tidy/GlobList.cpp

56–58

It does list that fact in the documentation for the function, but I'll put it in here too.

[aaron.ballman]

clang-tools-extra/clang-tidy/GlobList.cpp

56–58

Oh, I missed that from the header -- nevermind, it's your call if you want to add the comment or not. :-)

clang-tools-extra/clang-tidy/GlobList.h

 //===--- GlobList.h ---------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GLOBLIST_H
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GLOBLIST_H
 
 #include "clang/Basic/LLVM.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Regex.h"
-#include <vector>
 
 namespace clang {
 namespace tidy {
 
 /// Read-only set of strings represented as a list of positive and negative
 /// globs.
 ///
 /// Positive globs add all matched strings to the set, negative globs remove
public:
   /// Returns \c true if the pattern matches \p S. The result is the last
   /// matching glob's Positive flag.
   bool contains(StringRef S);
 
 private:
 
   struct GlobListItem {
     bool IsPositive;
-    mutable llvm::Regex Regex;
+    llvm::Regex Regex;
   };
-  std::vector<GlobListItem> Items;
+  SmallVector<GlobListItem, 0> Items;
 };
 
 } // end namespace tidy
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GLOBLIST_H

clang-tools-extra/clang-tidy/GlobList.cpp

static llvm::Regex ConsumeGlob(StringRef &GlobList) {
   StringRef UntrimmedGlob = GlobList.substr(0, GlobList.find(','));
   StringRef Glob = UntrimmedGlob.trim(' ');
   GlobList = GlobList.substr(UntrimmedGlob.size() + 1);
   SmallString<128> RegexText("^");
   StringRef MetaChars("()^$|*+?.[]\\{}");
   for (char C : Glob) {
     if (C == '*')
       RegexText.push_back('.');
-    else if (MetaChars.find(C) != StringRef::npos)
+    else if (MetaChars.contains(C))
       RegexText.push_back('\\');
     RegexText.push_back(C);
   }
   RegexText.push_back('$');
   return llvm::Regex(RegexText);
 }
 
 GlobList::GlobList(StringRef Globs) {
+  Items.reserve(Globs.count(',') + 1);
   do {
     GlobListItem Item;
     Item.IsPositive = !ConsumeNegativeIndicator(Globs);
     Item.Regex = ConsumeGlob(Globs);
     Items.push_back(std::move(Item));
   } while (!Globs.empty());
 }
 
 bool GlobList::contains(StringRef S) {
-  bool Contains = false;
-  for (const GlobListItem &Item : Items) {
+  // Iterating the container backwards as the last match determins if S is in
+  // the list.
+  for (const GlobListItem &Item : llvm::reverse(Items)) {
     if (Item.Regex.match(S))
-      Contains = Item.IsPositive;
+      return Item.IsPositive;
   }
-  return Contains;
+  return false;
 }