[analyzer][NFC] Prefer binary searches in CheckerRegistry

[baloghadamsoftware]

lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp

70 ↗

(On Diff #190974)

Please note that llvm::lower_bound() uses std::lower_bound() which returns an iterator pointing to the first element that is not less than the sought value, or last if no such element is found. So it is mandatory to check the return value whether it is equal to sought value or greater. In latter case you should return Collection.end() to keep up compatibility with find_if.

[Szelethus]

Change asserts according to reviewer feedback.

[Szelethus]

lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp

70 ↗

(On Diff #190974)

Yup, nice catch!

[Szelethus]

Avoid past-the-end iterator dereference, add it to the assert.

[baloghadamsoftware]

LGTM!

cfe/trunk/include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h

enum class StateFromCmdLine {
       // This checker wasn't explicitly enabled or disabled.
       State_Unspecified,
       // This checker was explicitly disabled.
       State_Disabled,
       // This checker was explicitly enabled.
       State_Enabled
     };
 
-    InitializationFunction Initialize;
-    ShouldRegisterFunction ShouldRegister;
+    InitializationFunction Initialize = nullptr;
+    ShouldRegisterFunction ShouldRegister = nullptr;
     StringRef FullName;
     StringRef Desc;
     StringRef DocumentationUri;
     StateFromCmdLine State = StateFromCmdLine::State_Unspecified;
 
     ConstCheckerInfoList Dependencies;
 
     bool isEnabled(const LangOptions &LO) const {
       return State == StateFromCmdLine::State_Enabled && ShouldRegister(LO);
     }
 
     bool isDisabled(const LangOptions &LO) const {
       return State == StateFromCmdLine::State_Disabled && ShouldRegister(LO);
     }
 
     CheckerInfo(InitializationFunction Fn, ShouldRegisterFunction sfn,
                 StringRef Name, StringRef Desc, StringRef DocsUri)
         : Initialize(Fn), ShouldRegister(sfn), FullName(Name), Desc(Desc),
           DocumentationUri(DocsUri) {}
+
+    // Used for lower_bound.
+    explicit CheckerInfo(StringRef FullName) : FullName(FullName) {}
   };
 
   using StateFromCmdLine = CheckerInfo::StateFromCmdLine;
 
 private:
   template <typename T> static void initializeManager(CheckerManager &mgr) {
     mgr.registerChecker<T>();
   }

cfe/trunk/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp

template <class T> struct FullNameLT {
   bool operator()(const T &Lhs, const T &Rhs) {
     return Lhs.FullName < Rhs.FullName;
   }
 };
 
 using CheckerNameLT = FullNameLT<CheckerRegistry::CheckerInfo>;
 } // end of anonymous namespace
 
+template <class CheckerOrPackageInfoList>
+static
+    typename std::conditional<std::is_const<CheckerOrPackageInfoList>::value,
+                              typename CheckerOrPackageInfoList::const_iterator,
+                              typename CheckerOrPackageInfoList::iterator>::type
+    binaryFind(CheckerOrPackageInfoList &Collection, StringRef FullName) {
+
+  using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
+  using CheckerOrPackageFullNameLT = FullNameLT<CheckerOrPackage>;
+
+  assert(std::is_sorted(Collection.begin(), Collection.end(),
+                        CheckerOrPackageFullNameLT{}) &&
+         "In order to efficiently gather checkers/packages, this function "
+         "expects them to be already sorted!");
+
+  typename CheckerOrPackageInfoList::value_type Info(FullName);
+
+  return llvm::lower_bound(
+      Collection, Info,
+      FullNameLT<typename CheckerOrPackageInfoList::value_type>{});
+}
+
 static constexpr char PackageSeparator = '.';
 
 static bool isInPackage(const CheckerRegistry::CheckerInfo &Checker,
                         StringRef PackageName) {
   // Does the checker's full name have the package as a prefix?
   if (!Checker.FullName.startswith(PackageName))
     return false;
 
   // Is the package actually just the name of a specific checker?
   if (Checker.FullName.size() == PackageName.size())
     return true;
 
   // Is the checker in the package (or a subpackage)?
   if (Checker.FullName[PackageName.size()] == PackageSeparator)
     return true;
 
   return false;
 }
 
 CheckerRegistry::CheckerInfoListRange
 CheckerRegistry::getMutableCheckersForCmdLineArg(StringRef CmdLineArg) {
-
-  assert(std::is_sorted(Checkers.begin(), Checkers.end(), CheckerNameLT{}) &&
-         "In order to efficiently gather checkers, this function expects them "
-         "to be already sorted!");
-
-  // Use a binary search to find the possible start of the package.
-  CheckerRegistry::CheckerInfo PackageInfo(nullptr, nullptr, CmdLineArg, "",
-                                           "");
-  auto It = std::lower_bound(Checkers.begin(), Checkers.end(), PackageInfo,
-                             CheckerNameLT{});
+  auto It = binaryFind(Checkers, CmdLineArg);
 
   if (!isInPackage(*It, CmdLineArg))
     return {Checkers.end(), Checkers.end()};
 
   // See how large the package is.
   // If the package doesn't exist, assume the option refers to a single
   // checker.
   size_t Size = 1;
void CheckerRegistry::addChecker(InitializationFunction Rfn,
   StringRef PackageName, LeafName;
   std::tie(PackageName, LeafName) = Name.rsplit(PackageSeparator);
   while (!LeafName.empty()) {
     PackageSizes[PackageName] += 1;
     std::tie(PackageName, LeafName) = PackageName.rsplit(PackageSeparator);
   }
 }
 
-void CheckerRegistry::addDependency(StringRef FullName, StringRef dependency) {
-  auto CheckerThatNeedsDeps = [&FullName](const CheckerInfo &Chk) {
-    return Chk.FullName == FullName;
-  };
-  auto Dependency = [&dependency](const CheckerInfo &Chk) {
-    return Chk.FullName == dependency;
-  };
-
-  auto CheckerIt = llvm::find_if(Checkers, CheckerThatNeedsDeps);
-  assert(CheckerIt != Checkers.end() &&
+void CheckerRegistry::addDependency(StringRef FullName, StringRef Dependency) {
+  auto CheckerIt = binaryFind(Checkers, FullName);
+  assert(CheckerIt != Checkers.end() && CheckerIt->FullName == FullName &&
          "Failed to find the checker while attempting to set up its "
          "dependencies!");
 
-  auto DependencyIt = llvm::find_if(Checkers, Dependency);
+  auto DependencyIt = binaryFind(Checkers, Dependency);
   assert(DependencyIt != Checkers.end() &&
+         DependencyIt->FullName == Dependency &&
          "Failed to find the dependency of a checker!");
 
-  CheckerIt->Dependencies.push_back(&*DependencyIt);
+  CheckerIt->Dependencies.emplace_back(&*DependencyIt);
 }
 
 void CheckerRegistry::initializeManager(CheckerManager &CheckerMgr) const {
   // Collect checkers enabled by the options.
   CheckerInfoSet enabledCheckers = getEnabledCheckers();
 
   // Initialize the CheckerManager with all enabled checkers.
   for (const auto *Checker : enabledCheckers) {