Refactor GlobList from an ad-hoc linked list to a vector

[gribozavr]

Summary

I think it makes method implementations more obvious.

[ilya-biryukov]

LGTM

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

46 ↗

(On Diff #217322)

NIT: I suggest using for (;!Globs.empty();) {} to make the stop condition stand out more.
Not a big deal, though, feel free to keep as is

[gribozavr]

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

46 ↗

(On Diff #217322)

It is actually important for the algorithm to use a do-while loop... The linked-list-based code always parsed at least one glob, even if the input string is empty. Therefore, new loop-based code should also parse at least one glob.

I added a doc comment:

+  /// An empty \p Globs string is interpreted as one glob that matches an empty
+  /// string.
   GlobList(StringRef Globs);

Please let me know if that is not sufficient. There are also tests for this behavior.

clang-tools-extra/trunk/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/StringRef.h"
 #include "llvm/Support/Regex.h"
-#include <memory>
+#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 them in the order of appearance in the list.
+/// 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
+/// them in the order of appearance in the list.
 class GlobList {
 public:
-  /// \p GlobList is a comma-separated list of globs (only '*'
-  /// metacharacter is supported) with optional '-' prefix to denote exclusion.
+  /// \p Globs is a comma-separated list of globs (only the '*' metacharacter is
+  /// supported) with an optional '-' prefix to denote exclusion.
+  ///
+  /// An empty \p Globs string is interpreted as one glob that matches an empty
+  /// string.
   GlobList(StringRef Globs);
 
   /// Returns \c true if the pattern matches \p S. The result is the last
   /// matching glob's Positive flag.
-  bool contains(StringRef S) { return contains(S, false); }
+  bool contains(StringRef S);
 
 private:
-  bool contains(StringRef S, bool Contains);
 
-  bool Positive;
-  llvm::Regex Regex;
-  std::unique_ptr<GlobList> NextGlob;
+  struct GlobListItem {
+    bool IsPositive;
+    mutable llvm::Regex Regex;
+  };
+  std::vector<GlobListItem> Items;
 };
 
 } // end namespace tidy
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GLOBLIST_H

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

for (char C : Glob) {
     else if (MetaChars.find(C) != StringRef::npos)
       RegexText.push_back('\\');
     RegexText.push_back(C);
   }
   RegexText.push_back('$');
   return llvm::Regex(RegexText);
 }
 
-GlobList::GlobList(StringRef Globs)
-    : Positive(!ConsumeNegativeIndicator(Globs)), Regex(ConsumeGlob(Globs)),
-      NextGlob(Globs.empty() ? nullptr : new GlobList(Globs)) {}
-
-bool GlobList::contains(StringRef S, bool Contains) {
-  if (Regex.match(S))
-    Contains = Positive;
+GlobList::GlobList(StringRef Globs) {
+  do {
+    GlobListItem Item;
+    Item.IsPositive = !ConsumeNegativeIndicator(Globs);
+    Item.Regex = ConsumeGlob(Globs);
+    Items.push_back(std::move(Item));
+  } while (!Globs.empty());
+}
 
-  if (NextGlob)
-    Contains = NextGlob->contains(S, Contains);
+bool GlobList::contains(StringRef S) {
+  bool Contains = false;
+  for (const GlobListItem &Item : Items) {
+    if (Item.Regex.match(S))
+      Contains = Item.IsPositive;
+  }
   return Contains;
 }