[clang-tidy][NFC] Move CachedGlobList to GlobList.h

[carlosgalvezp]

Summary

Currently it's hidden inside ClangTidyDiagnosticConsumer,
so it's hard to know it exists.

Given that there are multiple uses of globs in clang-tidy,
it makes sense to have these classes publicly available
for other use cases that might benefit from it.

Also, add unit test by converting the existing tests
for GlobList into typed tests.

[carlosgalvezp]

Kind ping @aaron.ballman @whisperity

[whisperity]

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

50–52

If CachedGlobList is-a GlobList, wouldn't it be better to express the inheritance relationship?

61

(considering the logically first data member is the conceptual base class)

[carlosgalvezp]

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

50–52

Yes, that makes total sense to me. I wasn't sure if it was OK to do the move + change the code itself in the same patch. Will fix!

[carlosgalvezp]

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

50–52

On the other hand, do we intend to use the class polymorphically? I wonder if private inheritance would be a better choice. Otherwise I'll need to start making the functions virtual and so on.

[carlosgalvezp]

• Replace composition with private inheritance.
• Fix namespaces.

Public inheritance is not possible due to the base class' function being const-qualified; the derived class cannot be const since it updates state (unless we go into mutable territory, which I think goes in detriment of readability). What do you think?

[carlosgalvezp]

Kind ping to reviewers.

[carlosgalvezp]

Switch to public inheritance + mutable cached data. This seems to be a valid use case for mutable, even though I'm not sure if there's anything against it in the LLVM coding guidelines. Looking forward to your feedback!

[salman-javed-nz]

Will aim to review and come back to you in a couple of days.

[salman-javed-nz]

LGTM. The use of mutable with public inheritence is all over the clang-tools-extra code. See class SwapIndex : public SymbolIndex. I don't see why your use would be against the norm.

[carlosgalvezp]

Thanks a lot for the review!

[njames93]

Was there any real use case for making this polymorphic, The overhead for a virtual function call seems a little unnecessary IMO?

[carlosgalvezp]

In D113422#3333748, @njames93 wrote:

Was there any real use case for making this polymorphic, The overhead for a virtual function call seems a little unnecessary IMO?

Nothing other than readability, CachedGlobList is a GlobList so it made sense to implement it with standard, by-the-book inheritance. But no, it's not used polymorphically at the moment so technically virtual could be removed, even though it would probably go against developer expectations and might cause confusion for the above reasons in the future. Perhaps doing private instead of public inheritance (is implemented in terms of) would communicate the design better in that case?

Do you have profiling data that shows how much overhead the virtual function call actually adds in this particular case? In the projects I've worked with this has typically been a micro-optimization done prematurely without profiling data that supported the need for it, so the benefit was negligible. It did cause a lot of headache to developers reading the code though.

[njames93]

In D113422#3333992, @carlosgalvezp wrote:

Nothing other than readability, CachedGlobList is a GlobList so it made sense to implement it with standard, by-the-book inheritance. But no, it's not used polymorphically at the moment so technically virtual could be removed, even though it would probably go against developer expectations and might cause confusion for the above reasons in the future. Perhaps doing private instead of public inheritance (is implemented in terms of) would communicate the design better in that case?

Do you have profiling data that shows how much overhead the virtual function call actually adds in this particular case? In the projects I've worked with this has typically been a micro-optimization done prematurely without profiling data that supported the need for it, so the benefit was negligible. It did cause a lot of headache to developers reading the code though.

It's definitely negligible as reading globs isn't exactly a hot path, was more just an irk when i was looking over the code.

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

 namespace ast_matchers {
 class MatchFinder;
 } // namespace ast_matchers
 namespace tooling {
 class CompilationDatabase;
 } // namespace tooling
 
 namespace tidy {
+class CachedGlobList;
 
 /// A detected error complete with information to display diagnostic and
 /// automatic fix.
 ///
 /// This is used as an intermediate format to transport Diagnostics without a
 /// dependency on a SourceManager.
 ///
 /// FIXME: Make Diagnostics flexible enough to support this directly.
private:
   // Writes to Stats.
   friend class ClangTidyDiagnosticConsumer;
 
   DiagnosticsEngine *DiagEngine;
   std::unique_ptr<ClangTidyOptionsProvider> OptionsProvider;
 
   std::string CurrentFile;
   ClangTidyOptions CurrentOptions;
-  class CachedGlobList;
+
   std::unique_ptr<CachedGlobList> CheckFilter;
   std::unique_ptr<CachedGlobList> WarningAsErrorFilter;
 
   LangOptions LangOpts;
 
   ClangTidyStats Stats;
 
   std::string CurrentBuildDirectory;

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

 } // end anonymous namespace
 
 ClangTidyError::ClangTidyError(StringRef CheckName,
                                ClangTidyError::Level DiagLevel,
                                StringRef BuildDirectory, bool IsWarningAsError)
     : tooling::Diagnostic(CheckName, DiagLevel, BuildDirectory),
       IsWarningAsError(IsWarningAsError) {}
 
-class ClangTidyContext::CachedGlobList {
-public:
-  CachedGlobList(StringRef Globs) : Globs(Globs) {}
-
-  bool contains(StringRef S) {
-    switch (auto &Result = Cache[S]) {
-    case Yes:
-      return true;
-    case No:
-      return false;
-    case None:
-      Result = Globs.contains(S) ? Yes : No;
-      return Result == Yes;
-    }
-    llvm_unreachable("invalid enum");
-  }
-
-private:
-  GlobList Globs;
-  enum Tristate { None, Yes, No };
-  llvm::StringMap<Tristate> Cache;
-};
-
 ClangTidyContext::ClangTidyContext(
     std::unique_ptr<ClangTidyOptionsProvider> OptionsProvider,
     bool AllowEnablingAnalyzerAlphaCheckers)
     : DiagEngine(nullptr), OptionsProvider(std::move(OptionsProvider)),
       Profile(false),
       AllowEnablingAnalyzerAlphaCheckers(AllowEnablingAnalyzerAlphaCheckers) {
   // Before the first translation unit we can get errors related to command-line
   // parsing, use empty string for the file name in this case.

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/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Regex.h"
 
 namespace clang {
 namespace tidy {
 
 /// Read-only set of strings represented as a list of positive and negative
 /// globs.
public:
   /// globs from \p Globs or not. When false, negative globs are simply ignored.
   GlobList(StringRef Globs, bool KeepNegativeGlobs = true);
 
   /// Returns \c true if the pattern matches \p S. The result is the last
   /// matching glob's Positive flag.
   bool contains(StringRef S) const;
 
 private:
-
   struct GlobListItem {
     bool IsPositive;
     llvm::Regex Regex;
   };
   SmallVector<GlobListItem, 0> Items;
 };
 
+/// A \p GlobList that caches search results, so that search is performed only
+/// once for the same query.
+class CachedGlobList {
+public:
+  /// \see GlobList::GlobList
+  CachedGlobList(StringRef Globs, bool KeepNegativeGlobs = true);
+
+  /// \see GlobList::contains
+  bool contains(StringRef S);
+
+private:
+  GlobList Globs;
+  enum Tristate { None, Yes, No };
+  llvm::StringMap<Tristate> Cache;
+};
+
 } // end namespace tidy
 } // end namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_GLOBLIST_H

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

bool GlobList::contains(StringRef S) const {
   // 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))
       return Item.IsPositive;
   }
   return false;
 }
+
+CachedGlobList::CachedGlobList(StringRef Globs, bool KeepNegativeGlobs)
+    : Globs(Globs, KeepNegativeGlobs) {}
+
+bool CachedGlobList::contains(StringRef S) {
+  switch (auto &Result = Cache[S]) {
+  case Yes:
+    return true;
+  case No:
+    return false;
+  case None:
+    Result = Globs.contains(S) ? Yes : No;
+    return Result == Yes;
+  }
+  llvm_unreachable("invalid enum");
+}

clang-tools-extra/unittests/clang-tidy/GlobListTest.cpp

 #include "GlobList.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace tidy {
 
-TEST(GlobList, Empty) {
-  GlobList Filter("");
+template <typename GlobListT> struct GlobListTest : public ::testing::Test {};
+
+using GlobListTypes = ::testing::Types<GlobList, CachedGlobList>;
+TYPED_TEST_SUITE(GlobListTest, GlobListTypes);
+
+TYPED_TEST(GlobListTest, Empty) {
+  TypeParam Filter("");
 
   EXPECT_TRUE(Filter.contains(""));
   EXPECT_FALSE(Filter.contains("aaa"));
 }
 
-TEST(GlobList, Nothing) {
-  GlobList Filter("-*");
+TYPED_TEST(GlobListTest, Nothing) {
+  TypeParam Filter("-*");
 
   EXPECT_FALSE(Filter.contains(""));
   EXPECT_FALSE(Filter.contains("a"));
   EXPECT_FALSE(Filter.contains("-*"));
   EXPECT_FALSE(Filter.contains("-"));
   EXPECT_FALSE(Filter.contains("*"));
 }
 
-TEST(GlobList, Everything) {
-  GlobList Filter("*");
+TYPED_TEST(GlobListTest, Everything) {
+  TypeParam Filter("*");
 
   EXPECT_TRUE(Filter.contains(""));
   EXPECT_TRUE(Filter.contains("aaaa"));
   EXPECT_TRUE(Filter.contains("-*"));
   EXPECT_TRUE(Filter.contains("-"));
   EXPECT_TRUE(Filter.contains("*"));
 }
 
-TEST(GlobList, OneSimplePattern) {
-  GlobList Filter("aaa");
+TYPED_TEST(GlobListTest, OneSimplePattern) {
+  TypeParam Filter("aaa");
 
   EXPECT_TRUE(Filter.contains("aaa"));
   EXPECT_FALSE(Filter.contains(""));
   EXPECT_FALSE(Filter.contains("aa"));
   EXPECT_FALSE(Filter.contains("aaaa"));
   EXPECT_FALSE(Filter.contains("bbb"));
 }
 
-TEST(GlobList, TwoSimplePatterns) {
-  GlobList Filter("aaa,bbb");
+TYPED_TEST(GlobListTest, TwoSimplePatterns) {
+  TypeParam Filter("aaa,bbb");
 
   EXPECT_TRUE(Filter.contains("aaa"));
   EXPECT_TRUE(Filter.contains("bbb"));
   EXPECT_FALSE(Filter.contains(""));
   EXPECT_FALSE(Filter.contains("aa"));
   EXPECT_FALSE(Filter.contains("aaaa"));
   EXPECT_FALSE(Filter.contains("bbbb"));
 }
 
-TEST(GlobList, PatternPriority) {
+TYPED_TEST(GlobListTest, PatternPriority) {
   // The last glob that matches the string decides whether that string is
   // included or excluded.
   {
-    GlobList Filter("a*,-aaa");
+    TypeParam Filter("a*,-aaa");
 
     EXPECT_FALSE(Filter.contains(""));
     EXPECT_TRUE(Filter.contains("a"));
     EXPECT_TRUE(Filter.contains("aa"));
     EXPECT_FALSE(Filter.contains("aaa"));
     EXPECT_TRUE(Filter.contains("aaaa"));
   }
   {
-    GlobList Filter("-aaa,a*");
+    TypeParam Filter("-aaa,a*");
 
     EXPECT_FALSE(Filter.contains(""));
     EXPECT_TRUE(Filter.contains("a"));
     EXPECT_TRUE(Filter.contains("aa"));
     EXPECT_TRUE(Filter.contains("aaa"));
     EXPECT_TRUE(Filter.contains("aaaa"));
   }
 }
 
-TEST(GlobList, WhitespacesAtBegin) {
-  GlobList Filter("-*,   a.b.*");
+TYPED_TEST(GlobListTest, WhitespacesAtBegin) {
+  TypeParam Filter("-*,   a.b.*");
 
   EXPECT_TRUE(Filter.contains("a.b.c"));
   EXPECT_FALSE(Filter.contains("b.c"));
 }
 
-TEST(GlobList, Complex) {
-  GlobList Filter("*,-a.*, -b.*, \r  \n  a.1.* ,-a.1.A.*,-..,-...,-..+,-*$, -*qwe* ");
+TYPED_TEST(GlobListTest, Complex) {
+  TypeParam Filter(
+      "*,-a.*, -b.*, \r  \n  a.1.* ,-a.1.A.*,-..,-...,-..+,-*$, -*qwe* ");
 
   EXPECT_TRUE(Filter.contains("aaa"));
   EXPECT_TRUE(Filter.contains("qqq"));
   EXPECT_FALSE(Filter.contains("a."));
   EXPECT_FALSE(Filter.contains("a.b"));
   EXPECT_FALSE(Filter.contains("b."));
   EXPECT_FALSE(Filter.contains("b.b"));
   EXPECT_TRUE(Filter.contains("a.1.b"));
   EXPECT_FALSE(Filter.contains("a.1.A.a"));
   EXPECT_FALSE(Filter.contains("qwe"));
   EXPECT_FALSE(Filter.contains("asdfqweasdf"));
   EXPECT_TRUE(Filter.contains("asdfqwEasdf"));
 }
 
 } // namespace tidy
 } // namespace clang