[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
This revision was automatically updated to reflect the committed changes.
Closed by commit rL358695: [analyzer][NFC] Prefer binary searches in
CheckerRegistry (authored by Szelethus, committed by ).
Herald added a project: LLVM.
Herald added a subscriber: llvm-commits.
Changed prior to commit:
https://reviews.llvm.org/D59459?vs=195358=195781#toc
Repository:
rL LLVM
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59459/new/
https://reviews.llvm.org/D59459
Files:
cfe/trunk/include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
cfe/trunk/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
Index: cfe/trunk/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
===
--- cfe/trunk/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
+++ cfe/trunk/lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
@@ -48,6 +48,28 @@
using CheckerNameLT = FullNameLT;
} // end of anonymous namespace
+template
+static
+typename std::conditional::value,
+ typename CheckerOrPackageInfoList::const_iterator,
+ typename CheckerOrPackageInfoList::iterator>::type
+binaryFind(CheckerOrPackageInfoList , StringRef FullName) {
+
+ using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
+ using CheckerOrPackageFullNameLT = FullNameLT;
+
+ 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{});
+}
+
static constexpr char PackageSeparator = '.';
static bool isInPackage(const CheckerRegistry::CheckerInfo ,
@@ -69,16 +91,7 @@
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()};
@@ -268,24 +281,18 @@
}
}
-void CheckerRegistry::addDependency(StringRef FullName, StringRef dependency) {
- auto CheckerThatNeedsDeps = [](const CheckerInfo ) {
-return Chk.FullName == FullName;
- };
- auto Dependency = [](const CheckerInfo ) {
-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 ) const {
Index: cfe/trunk/include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
===
--- cfe/trunk/include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
+++ cfe/trunk/include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
@@ -108,8 +108,8 @@
State_Enabled
};
-InitializationFunction Initialize;
-ShouldRegisterFunction ShouldRegister;
+InitializationFunction Initialize = nullptr;
+ShouldRegisterFunction ShouldRegister = nullptr;
StringRef FullName;
StringRef Desc;
StringRef DocumentationUri;
@@ -129,6 +129,9 @@
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;
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
baloghadamsoftware accepted this revision. baloghadamsoftware added a comment. This revision is now accepted and ready to land. LGTM! CHANGES SINCE LAST ACTION https://reviews.llvm.org/D59459/new/ https://reviews.llvm.org/D59459 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
Szelethus updated this revision to Diff 195358.
Szelethus added a comment.
Avoid past-the-end iterator dereference, add it to the assert.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59459/new/
https://reviews.llvm.org/D59459
Files:
include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
Index: lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
===
--- lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
+++ lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
@@ -48,6 +48,28 @@
using CheckerNameLT = FullNameLT;
} // end of anonymous namespace
+template
+static
+typename std::conditional::value,
+ typename CheckerOrPackageInfoList::const_iterator,
+ typename CheckerOrPackageInfoList::iterator>::type
+binaryFind(CheckerOrPackageInfoList , StringRef FullName) {
+
+ using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
+ using CheckerOrPackageFullNameLT = FullNameLT;
+
+ 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{});
+}
+
static constexpr char PackageSeparator = '.';
static bool isInPackage(const CheckerRegistry::CheckerInfo ,
@@ -69,16 +91,7 @@
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()};
@@ -268,24 +281,17 @@
}
}
-void CheckerRegistry::addDependency(StringRef FullName, StringRef dependency) {
- auto CheckerThatNeedsDeps = [](const CheckerInfo ) {
-return Chk.FullName == FullName;
- };
- auto Dependency = [](const CheckerInfo ) {
-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);
- assert(DependencyIt != Checkers.end() &&
+ 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 ) const {
Index: include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
===
--- include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
+++ include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
@@ -108,8 +108,8 @@
State_Enabled
};
-InitializationFunction Initialize;
-ShouldRegisterFunction ShouldRegister;
+InitializationFunction Initialize = nullptr;
+ShouldRegisterFunction ShouldRegister = nullptr;
StringRef FullName;
StringRef Desc;
StringRef DocumentationUri;
@@ -129,6 +129,9 @@
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;
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
Szelethus marked an inline comment as done.
Szelethus added inline comments.
Comment at: lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp:70
+ Collection, Info,
+ FullNameLT{});
+}
baloghadamsoftware wrote:
> 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`.
Yup, nice catch!
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59459/new/
https://reviews.llvm.org/D59459
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
Szelethus updated this revision to Diff 194768.
Szelethus added a comment.
Change asserts according to reviewer feedback.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59459/new/
https://reviews.llvm.org/D59459
Files:
include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
Index: lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
===
--- lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
+++ lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
@@ -48,6 +48,28 @@
using CheckerNameLT = FullNameLT;
} // end of anonymous namespace
+template
+static
+typename std::conditional::value,
+ typename CheckerOrPackageInfoList::const_iterator,
+ typename CheckerOrPackageInfoList::iterator>::type
+binaryFind(CheckerOrPackageInfoList , StringRef FullName) {
+
+ using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
+ using CheckerOrPackageFullNameLT = FullNameLT;
+
+ 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{});
+}
+
static constexpr char PackageSeparator = '.';
static bool isInPackage(const CheckerRegistry::CheckerInfo ,
@@ -69,16 +91,7 @@
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()};
@@ -268,24 +281,17 @@
}
}
-void CheckerRegistry::addDependency(StringRef FullName, StringRef dependency) {
- auto CheckerThatNeedsDeps = [](const CheckerInfo ) {
-return Chk.FullName == FullName;
- };
- auto Dependency = [](const CheckerInfo ) {
-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->FullName == FullName &&
"Failed to find the checker while attempting to set up its "
"dependencies!");
- auto DependencyIt = llvm::find_if(Checkers, Dependency);
- assert(DependencyIt != Checkers.end() &&
+ auto DependencyIt = binaryFind(Checkers, Dependency);
+ assert(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 ) const {
Index: include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
===
--- include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
+++ include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
@@ -108,8 +108,8 @@
State_Enabled
};
-InitializationFunction Initialize;
-ShouldRegisterFunction ShouldRegister;
+InitializationFunction Initialize = nullptr;
+ShouldRegisterFunction ShouldRegister = nullptr;
StringRef FullName;
StringRef Desc;
StringRef DocumentationUri;
@@ -129,6 +129,9 @@
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;
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
baloghadamsoftware requested changes to this revision.
baloghadamsoftware added inline comments.
This revision now requires changes to proceed.
Comment at: lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp:70
+ Collection, Info,
+ FullNameLT{});
+}
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`.
Repository:
rC Clang
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D59459/new/
https://reviews.llvm.org/D59459
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D59459: [analyzer][NFC] Prefer binary searches in CheckerRegistry
Szelethus created this revision.
Szelethus added reviewers: xazax.hun, NoQ, baloghadamsoftware, rnkovacs.
Szelethus added a project: clang.
Herald added subscribers: cfe-commits, Charusso, gamesh411, dkrupp, donat.nagy,
mikhail.ramalho, a.sidorin, szepet, whisperity.
Szelethus added a parent revision: D59458: [analyzer][NFC] Clang-format
CheckerRegistry.
Repository:
rC Clang
https://reviews.llvm.org/D59459
Files:
include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
Index: lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
===
--- lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
+++ lib/StaticAnalyzer/Frontend/CheckerRegistry.cpp
@@ -48,6 +48,28 @@
using CheckerNameLT = FullNameLT;
} // end of anonymous namespace
+template
+static
+typename std::conditional::value,
+ typename CheckerOrPackageInfoList::const_iterator,
+ typename CheckerOrPackageInfoList::iterator>::type
+binaryFind(CheckerOrPackageInfoList , StringRef FullName) {
+
+ using CheckerOrPackage = typename CheckerOrPackageInfoList::value_type;
+ using CheckerOrPackageFullNameLT = FullNameLT;
+
+ 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{});
+}
+
static constexpr char PackageSeparator = '.';
static bool isInPackage(const CheckerRegistry::CheckerInfo ,
@@ -69,16 +91,7 @@
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()};
@@ -268,24 +281,17 @@
}
}
-void CheckerRegistry::addDependency(StringRef FullName, StringRef dependency) {
- auto CheckerThatNeedsDeps = [](const CheckerInfo ) {
-return Chk.FullName == FullName;
- };
- auto Dependency = [](const CheckerInfo ) {
-return Chk.FullName == dependency;
- };
-
- auto CheckerIt = llvm::find_if(Checkers, CheckerThatNeedsDeps);
+void CheckerRegistry::addDependency(StringRef FullName, StringRef Dependency) {
+ auto CheckerIt = binaryFind(Checkers, FullName);
assert(CheckerIt != Checkers.end() &&
"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() &&
"Failed to find the dependency of a checker!");
- CheckerIt->Dependencies.push_back(&*DependencyIt);
+ CheckerIt->Dependencies.emplace_back(&*DependencyIt);
}
void CheckerRegistry::initializeManager(CheckerManager ) const {
Index: include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
===
--- include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
+++ include/clang/StaticAnalyzer/Frontend/CheckerRegistry.h
@@ -108,8 +108,8 @@
State_Enabled
};
-InitializationFunction Initialize;
-ShouldRegisterFunction ShouldRegister;
+InitializationFunction Initialize = nullptr;
+ShouldRegisterFunction ShouldRegister = nullptr;
StringRef FullName;
StringRef Desc;
StringRef DocumentationUri;
@@ -129,6 +129,9 @@
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;
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
