diff --git a/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt b/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt --- a/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt +++ b/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt @@ -34,6 +34,7 @@ UseNoexceptCheck.cpp UseNullptrCheck.cpp UseOverrideCheck.cpp + UseRangesCheck.cpp UseTrailingReturnTypeCheck.cpp UseTransparentFunctorsCheck.cpp UseUncaughtExceptionsCheck.cpp diff --git a/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp b/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp --- a/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp +++ b/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp @@ -36,6 +36,7 @@ #include "UseNoexceptCheck.h" #include "UseNullptrCheck.h" #include "UseOverrideCheck.h" +#include "UseRangesCheck.h" #include "UseTrailingReturnTypeCheck.h" #include "UseTransparentFunctorsCheck.h" #include "UseUncaughtExceptionsCheck.h" @@ -91,6 +92,7 @@ CheckFactories.registerCheck("modernize-use-noexcept"); CheckFactories.registerCheck("modernize-use-nullptr"); CheckFactories.registerCheck("modernize-use-override"); + CheckFactories.registerCheck("modernize-use-ranges"); CheckFactories.registerCheck( "modernize-use-trailing-return-type"); CheckFactories.registerCheck( diff --git a/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.h b/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.h new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.h @@ -0,0 +1,40 @@ +//===--- UseRangesCheck.h - clang-tidy --------------------------*- 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_MODERNIZE_USERANGESCHECK_H +#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_USERANGESCHECK_H + +#include "../ClangTidyCheck.h" +#include "clang/Basic/LangOptions.h" + +namespace clang { +namespace tidy { +namespace modernize { + +/// Converts calls to standard library algorithms that take a pair of iterators +/// and replaces them with the equivalent function from the C++20 `std::ranges` +/// library. +/// +/// For the user-facing documentation see: +/// http://clang.llvm.org/extra/clang-tidy/checks/modernize-use-ranges.html +class UseRangesCheck : public ClangTidyCheck { +public: + UseRangesCheck(StringRef Name, ClangTidyContext *Context) + : ClangTidyCheck(Name, Context) {} + bool isLanguageVersionSupported(const LangOptions &LangOpts) const override { + return LangOpts.CPlusPlus20; + } + void registerMatchers(ast_matchers::MatchFinder *Finder) override; + void check(const ast_matchers::MatchFinder::MatchResult &Result) override; +}; + +} // namespace modernize +} // namespace tidy +} // namespace clang + +#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_USERANGESCHECK_H diff --git a/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.cpp b/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/clang-tidy/modernize/UseRangesCheck.cpp @@ -0,0 +1,143 @@ +//===--- UseRangesCheck.cpp - clang-tidy ----------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include "UseRangesCheck.h" +#include "clang/ASTMatchers/ASTMatchers.h" + +using namespace clang::ast_matchers; + +namespace clang { +namespace tidy { +namespace modernize { + +// Functions that take a single iterator pair: +// void func(Iter Begin, Iter End, AnyOtherArgs); +// void func(ExecutionPolicy&&, Iter Begin, Iter End, AnyOtherArgs); +static constexpr StringRef SingleRangeFunctions[] = { + "::std::any_of", "::std::all_of", "::std::none_of", + "::std::for_each", "::std::count", "::std::count_if", + "::std::find", "::std::find_if", "::std::find_if_not", + "::std::adjacent_find", "::std::copy", "::std::copy_if", + "::std::fill", "::std::is_heap", "::std::is_heap_until", + "::std::make_heap", "::std::push_heap", "::std::pop_heap", + "::std::sort_heap", "::std::remove", "::std::remove_if", + "::std::reverse", "::std::unique", "::std::lower_bound", + "::std::upper_bound", "::std::binary_search", "::std::equal_range", + "::std::max_element", "::std::min_element", "::std::minmax_element", +}; + +// Functions that can take one or two iterator pairs: +// void func(Iter Begin, Iter End, AnyOtherArgs); +// void func(Iter Begin, Iter End, Iter2 Begin2, Iter2 End2, AnyOtherArgs); +// void func(ExecutionPolicy&&, Iter Begin, Iter End, AnyOtherArgs); +// void func(ExecutionPolicy&&, Iter Begin, Iter End, Iter2 Begin2, Iter2 End2, +// AnyOtherArgs); +static constexpr StringRef MaybeDualRangeFunctions[] = { + "::std::search", + "::std::equal", +}; + +// Functions that take two iterator pairs: +// void func(Iter Begin, Iter End, Iter2 Begin2, Iter2 End2, AnyOtherArgs); +// void func(ExecutionPolicy&&, Iter Begin, Iter End, Iter2 Begin2, Iter2 End2, +// AnyOtherArgs); +static constexpr StringRef DualRangeFunctions[] = { + "::std::merge", + "::std::includes", + "::std::set_difference", + "::std::set_intesection", + "::std::set_symmetric_difference", + "::std::set_union", +}; + +static internal::Matcher matchBeginAndEndCall(unsigned ArgIndex, + StringRef ID = "") { + std::string Range = (ID + "Range").str(); + + auto MatchCallTo = [](std::string BindName, DeclarationMatcher DeclMatcher, + auto NameMatcher, auto MethodMatcher) { + auto Container = anyOf(declRefExpr(to(DeclMatcher)), + memberExpr(hasDeclaration(DeclMatcher))); + return expr(ignoringParenImpCasts(anyOf( + callExpr( + callee(functionDecl(NameMatcher, parameterCountIs(1))), + hasArgument(0, Container)), + cxxMemberCallExpr(on(Container), + callee(cxxMethodDecl(MethodMatcher)))))) + .bind(BindName); + }; + return allOf( + hasArgument(ArgIndex, + MatchCallTo((ID + "Begin").str(), namedDecl().bind(Range), + hasAnyName("::std::begin", "::std::cbegin"), + hasAnyName("begin", "cbegin"))), + hasArgument(ArgIndex + 1, + MatchCallTo((ID + "End").str(), equalsBoundNode(Range), + hasAnyName("::std::end", "::std::cend"), + hasAnyName("end", "cend")))); +} + +void UseRangesCheck::registerMatchers(MatchFinder *Finder) { + // Match at first or second arg incase there is an ExecutionPolicy at first + // arg. + Finder->addMatcher( + callExpr( + callee( + functionDecl(hasAnyName(SingleRangeFunctions)).bind("Function")), + anyOf(matchBeginAndEndCall(0), matchBeginAndEndCall(1))) + .bind("Call"), + this); + Finder->addMatcher( + callExpr( + callee(functionDecl(hasAnyName(DualRangeFunctions)).bind("Function")), + anyOf( + allOf(matchBeginAndEndCall(0), matchBeginAndEndCall(2, "Second")), + allOf(matchBeginAndEndCall(1), + matchBeginAndEndCall(3, "Second")))) + .bind("Call"), + this); + Finder->addMatcher( + callExpr(callee(functionDecl(hasAnyName(MaybeDualRangeFunctions)) + .bind("Function")), + anyOf(matchBeginAndEndCall(0), matchBeginAndEndCall(1)), + optionally(anyOf(matchBeginAndEndCall(2, "Second"), + matchBeginAndEndCall(3, "Second")))) + .bind("Call"), + this); +} + +void UseRangesCheck::check(const MatchFinder::MatchResult &Result) { + const auto *Target = Result.Nodes.getNodeAs("Range"); + const auto *Begin = Result.Nodes.getNodeAs("Begin"); + const auto *End = Result.Nodes.getNodeAs("End"); + const auto *Function = Result.Nodes.getNodeAs("Function"); + const auto *Call = Result.Nodes.getNodeAs("Call"); + assert(Target && Begin && End && Function && Call && "Missing bound node"); + + const auto *Target2 = Result.Nodes.getNodeAs("SecondRange"); + const auto *Begin2 = Result.Nodes.getNodeAs("SecondBegin"); + const auto *End2 = Result.Nodes.getNodeAs("SecondEnd"); + assert(((Target2 && Begin2 && End2) || (!Target2 && !Begin2 && !End2)) && + "Missing secondary bound nodes"); + + DiagnosticBuilder Diag = + diag(Call->getBeginLoc(), "replace %0 with std::ranges::%0"); + Diag << Function->getName() + << FixItHint::CreateReplacement( + {Call->getBeginLoc(), Call->getCallee()->getEndLoc()}, + ("std::ranges::" + Function->getName()).str()) + << FixItHint::CreateReplacement({Begin->getBeginLoc(), End->getEndLoc()}, + Target->getName()); + if (Target2) // Two ranges argument function. + Diag << FixItHint::CreateReplacement( + {Begin2->getBeginLoc(), End2->getEndLoc()}, Target2->getName()); +} + +} // namespace modernize +} // namespace tidy +} // namespace clang diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst --- a/clang-tools-extra/docs/ReleaseNotes.rst +++ b/clang-tools-extra/docs/ReleaseNotes.rst @@ -142,6 +142,13 @@ Finds macro expansions of ``DISALLOW_COPY_AND_ASSIGN`` and replaces them with a deleted copy constructor and a deleted assignment operator. +- New :doc:`modernize-use-ranges + ` check. + + Converts calls to standard library algorithms that take a pair of iterators + and replaces them with the equivalent function from the C++20 ``std::ranges`` + library. + - New :doc:`objc-dealloc-in-category ` check. diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst --- a/clang-tools-extra/docs/clang-tidy/checks/list.rst +++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst @@ -233,6 +233,7 @@ `modernize-use-noexcept `_, "Yes" `modernize-use-nullptr `_, "Yes" `modernize-use-override `_, "Yes" + `modernize-use-ranges `_, "Yes" `modernize-use-trailing-return-type `_, "Yes" `modernize-use-transparent-functors `_, "Yes" `modernize-use-uncaught-exceptions `_, "Yes" diff --git a/clang-tools-extra/docs/clang-tidy/checks/modernize-use-ranges.rst b/clang-tools-extra/docs/clang-tidy/checks/modernize-use-ranges.rst new file mode 100644 --- /dev/null +++ b/clang-tools-extra/docs/clang-tidy/checks/modernize-use-ranges.rst @@ -0,0 +1,39 @@ +.. title:: clang-tidy - modernize-use-ranges + +modernize-use-ranges +==================== + +Converts calls to standard library algorithms that take a pair of iterators and +replaces them with the equivalent function from the C++20 ``std::ranges`` +library. + +The check is only applicable for C++20 and later code. + +The iterators must be attained using either: + - ``std::begin(Container)`` + - ``std::cbegin(Container)`` + - ``Container.begin()`` + - ``Container.cbegin()`` +and: + - ``std::end(Container)`` + - ``std::cend(Container)`` + - ``Container.end()`` + - ``Container.cend()`` + +Example +------- + +.. code-block:: c++ + + auto It = std::find(Vec.cbegin(), Vec.cend(), 1); + bool B1 = std::includes(std::begin(Set1), std::end(Set1), Set2.begin(), Set2.end()); + bool B2 = std::equal(std::cbegin(Vec1), std::cend(Vec1), OtherIter); + +transforms to: + +.. code-block:: c++ + + auto It = std::ranges::find(Vec, 1); + bool B1 = std::ranges::includes(Set1, Set2); + bool B2 = std::ranges::equal(Vec1, OtherIter); + diff --git a/clang-tools-extra/test/clang-tidy/checkers/modernize-use-ranges.cpp b/clang-tools-extra/test/clang-tidy/checkers/modernize-use-ranges.cpp new file mode 100644 --- /dev/null +++ b/clang-tools-extra/test/clang-tidy/checkers/modernize-use-ranges.cpp @@ -0,0 +1,156 @@ +// RUN: %check_clang_tidy -std=c++20 %s modernize-use-ranges %t + +// Ensure no warnings are generated when not in c++20 mode +// RUN: clang-tidy %s -checks=-*,modernize-use-ranges --warnings-as-errors=modernize-use-ranges --extra-arg=-std=c++17 + +namespace std { + +class sequenced_policy {}; +class parallel_policy {}; +class parallel_unsequenced_policy {}; +class unsequenced_policy {}; + +template +auto begin(Container &C) -> decltype(C.begin()); +template +auto cbegin(Container &C) -> decltype(C.cbegin()); + +template +auto end(Container &C) -> decltype(C.end()); +template +auto cend(Container &C) -> decltype(C.cend()); + +template +T *begin(T (&Array)[N]) noexcept; + +template +T *end(T (&Array)[N]) noexcept; + +template +class vector { +public: + using iterator = T *; + using const_iterator = const T *; + + iterator begin(); + const_iterator begin() const; + const_iterator cbegin() const; + + iterator end(); + const_iterator end() const; + const_iterator cend() const; +}; + +template +InputIt find(InputIt First, InputIt Last, const T &Value); + +template +ForwardIt find(ExecutionPolicy &&Policy, ForwardIt First, ForwardIt Last, const T &Value); + +template +bool equal(InputIt1 First1, InputIt1 Last1, + InputIt2 First2); +template +bool equal(ExecutionPolicy &&Policy, ForwardIt1 First1, ForwardIt1 Last1, + ForwardIt2 First2); +template +bool equal(InputIt1 First1, InputIt1 Last1, + InputIt2 First2, InputIt2 Last2); +template +bool equal(ExecutionPolicy &&Policy, ForwardIt1 First1, ForwardIt1 Last1, + ForwardIt2 First2, ForwardIt2 Last2); + +template +bool includes(InputIt1 First1, InputIt1 Last1, + InputIt2 First2, InputIt2 Last2); +template +bool includes(ExecutionPolicy &&Policy, ForwardIt1 First1, ForwardIt1 Last1, + ForwardIt2 First2, ForwardIt2 Last2); + +} // namespace std + +void goodBeginEndCalls(const std::vector &Vec) { + std::find(Vec.begin(), Vec.end(), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + std::find(Vec.cbegin(), Vec.cend(), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + std::find(std::begin(Vec), std::end(Vec), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + std::find(std::cbegin(Vec), std::cend(Vec), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + std::find(std::parallel_policy(), Vec.begin(), Vec.end(), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + + // CHECK-FIXES: std::ranges::find(Vec, 1); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::find(Vec, 1); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::find(Vec, 1); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::find(Vec, 1); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::find(std::parallel_policy(), Vec, 1); + // CHECK-FIXES-NEXT: // +} + +void badBeginEndCalls(const std::vector &Vec, + const std::vector &Vec2) { + // end, begin. + std::find(Vec.end(), Vec.begin(), 1); + std::find(Vec.cend(), Vec.cbegin(), 1); + std::find(std::end(Vec), std::begin(Vec), 1); + std::find(std::cend(Vec), std::cbegin(Vec), 1); + + // begin, begin. + std::find(Vec.begin(), Vec.begin(), 1); + // end, end. + std::find(Vec.end(), Vec.end(), 1); + + // Different containers, definitely bad, but not what this check is for. + std::find(Vec.begin(), Vec2.end(), 1); +} + +void maybeDualArg(const std::vector &Vec1, std::vector &Vec2) { + std::equal(Vec1.begin(), Vec1.end(), Vec2.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace equal with std::ranges::equal + std::equal(Vec1.begin(), Vec1.end(), Vec2.begin(), Vec2.end()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace equal with std::ranges::equal + std::equal(std::sequenced_policy(), Vec1.begin(), Vec1.end(), Vec2.begin()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace equal with std::ranges::equal + std::equal(std::unsequenced_policy(), Vec1.begin(), Vec1.end(), Vec2.begin(), Vec2.end()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace equal with std::ranges::equal + + // CHECK-FIXES: std::ranges::equal(Vec1, Vec2.begin()); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::equal(Vec1, Vec2); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::equal(std::sequenced_policy(), Vec1, Vec2.begin()); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::equal(std::unsequenced_policy(), Vec1, Vec2); + // CHECK-FIXES-NEXT: // +} + +void dualArg(const std::vector &Vec1, const std::vector &Vec2) { + std::includes(Vec1.begin(), Vec1.end(), Vec2.begin(), Vec2.end()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace includes with std::ranges::includes + std::includes(std::parallel_unsequenced_policy(), Vec1.begin(), Vec1.end(), Vec2.begin(), Vec2.end()); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace includes with std::ranges::includes + + // CHECK-FIXES: std::ranges::includes(Vec1, Vec2); + // CHECK-FIXES-NEXT: // + // CHECK-FIXES-NEXT: std::ranges::includes(std::parallel_unsequenced_policy(), Vec1, Vec2); + // CHECK-FIXES-NEXT: // + + // begin,begin,end,end - no warning. + std::includes(Vec1.begin(), Vec2.begin(), Vec1.end(), Vec2.end()); + // container mismatch - no warnings. + std::includes(Vec1.begin(), Vec2.end(), Vec2.begin(), Vec1.end()); +} + +void checkArray() { + // Arrays can be passed to ranges functions. + int Array[] = {1, 2, 3}; + std::find(std::begin(Array), std::end(Array), 1); + // CHECK-MESSAGES: :[[@LINE-1]]:3: warning: replace find with std::ranges::find + // CHECK-FIXES: std::ranges::find(Array, 1); +}