diff options
| -rw-r--r-- | clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp | 21 | ||||
| -rw-r--r-- | clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp | 43 |
2 files changed, 59 insertions, 5 deletions
diff --git a/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp b/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp index 906140db54e..16401b7d475 100644 --- a/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp +++ b/clang-tools-extra/clang-tidy/misc/InefficientAlgorithmCheck.cpp @@ -17,9 +17,18 @@ using namespace clang::ast_matchers; namespace clang { namespace tidy { +static bool areTypesCompatible(QualType Left, QualType Right) { + if (const auto *LeftRefType = Left->getAs<ReferenceType>()) + Left = LeftRefType->getPointeeType(); + if (const auto *RightRefType = Right->getAs<ReferenceType>()) + Right = RightRefType->getPointeeType(); + return Left->getCanonicalTypeUnqualified() == + Right->getCanonicalTypeUnqualified(); +} + void InefficientAlgorithmCheck::registerMatchers(MatchFinder *Finder) { const std::string Algorithms = - "^::std::(find|count|equal_range|lower_blound|upper_bound)$"; + "^::std::(find|count|equal_range|lower_bound|upper_bound)$"; const auto ContainerMatcher = classTemplateSpecializationDecl( matchesName("^::std::(unordered_)?(multi)?(set|map)$")); const auto Matcher = @@ -57,6 +66,14 @@ void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) { const llvm::StringRef IneffContName = IneffCont->getName(); const bool Unordered = IneffContName.find("unordered") != llvm::StringRef::npos; + const bool Maplike = IneffContName.find("map") != llvm::StringRef::npos; + + // Store if the key type of the container is compatible with the value + // that is searched for. + QualType ValueType = AlgCall->getArg(2)->getType(); + QualType KeyType = + IneffCont->getTemplateArgs()[0].getAsType().getCanonicalType(); + const bool CompatibleTypes = areTypesCompatible(KeyType, ValueType); // Check if the comparison type for the algorithm and the container matches. if (AlgCall->getNumArgs() == 4 && !Unordered) { @@ -87,7 +104,7 @@ void InefficientAlgorithmCheck::check(const MatchFinder::MatchResult &Result) { const auto *IneffContExpr = Result.Nodes.getNodeAs<Expr>("IneffContExpr"); FixItHint Hint; - if (!AlgCall->getLocStart().isMacroID()) { + if (!AlgCall->getLocStart().isMacroID() && !Maplike && CompatibleTypes) { std::string ReplacementText = (llvm::Twine(Lexer::getSourceText( CharSourceRange::getTokenRange(IneffContExpr->getSourceRange()), diff --git a/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp b/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp index 4ed2fb25c9c..ea668c2bedd 100644 --- a/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp +++ b/clang-tools-extra/test/clang-tidy/misc-inefficient-algorithm.cpp @@ -23,6 +23,19 @@ template <typename K, typename Cmp = less<K>> struct set { iterator end() const; }; +struct other_iterator_type {}; + +template <typename K, typename V, typename Cmp = less<K>> struct map { + typedef other_iterator_type iterator; + iterator find(const K &k); + unsigned count(const K &k); + + iterator begin(); + iterator end(); + iterator begin() const; + iterator end() const; +}; + template <typename K> struct unordered_set : set<K> {}; template <typename K, typename Cmp = less<K>> struct multiset : set<K, Cmp> {}; @@ -32,15 +45,17 @@ template <typename FwIt, typename K> FwIt find(FwIt, FwIt, const K &); template <typename FwIt, typename K, typename Cmp> FwIt find(FwIt, FwIt, const K &, Cmp); -template <typename FwIt, typename Pred> -FwIt find_if(FwIt, FwIt, Pred); +template <typename FwIt, typename Pred> FwIt find_if(FwIt, FwIt, Pred); template <typename FwIt, typename K> FwIt count(FwIt, FwIt, const K &); template <typename FwIt, typename K> FwIt lower_bound(FwIt, FwIt, const K &); + +template <typename FwIt, typename K, typename Ord> +FwIt lower_bound(FwIt, FwIt, const K &, Ord); } -#define FIND_IN_SET(x) find(x.begin(), x.end(), 10) +#define FIND_IN_SET(x) find(x.begin(), x.end(), 10) // CHECK-FIXES: #define FIND_IN_SET(x) find(x.begin(), x.end(), 10) template <typename T> void f(const T &t) { @@ -93,4 +108,26 @@ int main() { find(us.begin(), us.end(), 10); // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be // CHECK-FIXES: {{^ }}us.find(10);{{$}} + + std::map<int, int> intmap; + find(intmap.begin(), intmap.end(), 46); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be + // CHECK-FIXES: {{^ }}find(intmap.begin(), intmap.end(), 46);{{$}} +} + +struct Value { + int value; +}; + +struct Ordering { + bool operator()(const Value &lhs, const Value &rhs) const { + return lhs.value < rhs.value; + } + bool operator()(int lhs, const Value &rhs) const { return lhs < rhs.value; } +}; + +void g(std::set<Value, Ordering> container, int value) { + lower_bound(container.begin(), container.end(), value, Ordering()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: this STL algorithm call should be + // CHECK-FIXES: {{^ }}lower_bound(container.begin(), container.end(), value, Ordering());{{$}} } |
