[clang-tidy] add new check readability-use-anyofallof

[mgehre]

Summary

Finds range-based for loops that can be replaced by a call to std::any_of` or
std::all_of. In C++ 20 mode, suggests std::ranges::any_of or
std::ranges::all_of.
For now, no fixits are produced.

[Eugene.Zelenko]

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

26

Please don't use auto unless type is spelled in same statement or iterator.

55

Must be in isLanguageVersionSupported() method.

110

Unnecessary empty line.

clang-tools-extra/docs/ReleaseNotes.rst

135

Please enclose std::any_of and std::all_of in double back-ticks.

[njames93]

As no FixIts are made the IncludeInserter can be removed.

I'm struggling to see the value of this check though. If it was reworked to check for loop in the middle of a function it would have a lot more value.

bool all_of = true;
for (auto X : V) {
  if (!X) {
    all_of = false;
    break;
  }
}

Being able to identify those and possibly even transform them would have much more value

bool all_of = std::all_of(std::begin(V), std::end(V), [](const auto &X) { return static_cast<bool>(X) });

I'm guessing you'd want to check for compound statements that have a bool VarDecl with an init just before the range for loop and a condition in the loop that flips the value and then breaks after.

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

21–41

This should be in an anonymous namespace as it doesn't need external linkage. Probably shouldn't be in the ast_matchers namespace either

34

nit: const auto *I = llvm::find(C->body(), &Node);

[Eugene.Zelenko]

See also suggestion for more generic loop-to-algorithm transformations.

[mgehre]

In D77572#1965143, @njames93 wrote:

I'm struggling to see the value of this check though. If it was reworked to check for loop in the middle of a function it would have a lot more value.

This is (just) a first step. The next step is to detect the local variable case as you also described it. Note that this also catches functions
that do some preprocessing and end with a any_of-style loop.
I also have a local branch that generates fixits, but they add quite some code, so I wanted to put them in a separate PR.

In LLVM & clang, the check in this PR already emits 370 unique warnings.

readability-use-anyofallof.log3 MBDownload

[mgehre]

Review comments

[mgehre]

Review comments

[njames93]

In D77572#1967956, @mgehre wrote:

In D77572#1965143, @njames93 wrote:

I'm struggling to see the value of this check though. If it was reworked to check for loop in the middle of a function it would have a lot more value.

This is (just) a first step. The next step is to detect the local variable case as you also described it. Note that this also catches functions
that do some preprocessing and end with a any_of-style loop.
I also have a local branch that generates fixits, but they add quite some code, so I wanted to put them in a separate PR.

In LLVM & clang, the check in this PR already emits 370 unique warnings.

Take this example from TableGen/Record.cpp:

bool CondOpInit::isConcrete() const {
  for (const Init *Case : getConds())
    if (!Case->isConcrete())
      return false;

  for (const Init *Val : getVals())
    if (!Val->isConcrete())
      return false;

  return true;
}

Firstly, the warning is only emitted on the second loop.
Secondly how does your fix it code handle temporaries?
Would it transform to

bool CondOpInit::isConcrete() const {
  for (const Init *Case : getConds())
    if (!Case->isConcrete())
      return false;

  return std::all_of(getVals().begin(), getVals().end(),
                     [](const Init *Val) { return Val->isConcrete(); });
}

I'd argue that it actually makes the code less readable as there are 2 different constructs for the same thing.

[mgehre]

Thanks @njames93, this is a good examples which I did not consider yet. I agree that only transforming
the second loop would make the code worse.

I would argue that a human seeing a warning on the second loop might also realize
that the first loop can be transformed in a similar way, and possibly combine them into

return llvm::all_of(getConds(), [](const Init *Cond) { return Val->isConcrete(); }) && llvm::all_of(getVals(), [](const Init *Val) { return Val->isConcrete(); });

or

auto IsConcrete = [](auto Init* I) { return I->isConcrete(); };
return llvm::all_of(getConds(), IsConcrete) && llvm::all_of(getVals(), IsConcrete);

(I was wondering whether the check should have an option to suggest llvm::all_of (or boost::algorithm::all_of, ...) instead of std::all_of, but
I thought that this could go into another PR.)

I have the feeling that extracting code into algorithms is generally a hard topic,
and automatic fixits would possible give a false sense of automatism (at least at the current point).
Your example is a good reminder of that.

Personally, clang-tidy has been a good source of learning C++ best practices. And I hope that this clang-tidy check would help
me and my coworkers to remember using those algorithms.

Are you saying that this check should not land unless its scope is extended? What would be the minimal scope making this check
worth-while to land?

[njames93]

Right now it would be a great candidate for this - http://lists.llvm.org/pipermail/cfe-dev/2020-March/064980.html, however in its current state I wouldn't say its ready to get the green light right now.
No point worrying about the fix-its yet, but when it is time, could add options for RangeAllOfName, RangeAnyOfName, RangeNoneOfName, AlgorithmHeader.
Gonna throw it out there that generating that templated lambda automatically... just don't :)

[mgehre]

Thanks for the comments so far.
I'm a bit lost now. Which changes that cannot wait for the next PR do you see necessary to get this check merged?

[mgehre]

Ping :-)
I'm looking for directions on what the next steps are.

[aaron.ballman]

In D77572#1981871, @mgehre wrote:

Thanks for the comments so far.
I'm a bit lost now. Which changes that cannot wait for the next PR do you see necessary to get this check merged?

I'd be curious to know what @njames93 thinks -- I spot-checked the diagnostics you attached earlier (thank you for those!) and all of them seemed reasonable to me, which suggests there's not an extraordinary amount of false positives. The functionality seems useful in its current state, though as you point out, there are improvements you want to make in follow-up patches. That seems reasonable to me.

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

22–24

It looks like these comments got formatted a bit strangely -- probably should re-flow them.

36

I think the comment should turn into a string literal that's part of the assertion.

61

Should we reject other ways to break out of the loop, like goto or throw?

98

clang-tidy diagnostics don't start with a capital letter, and I'd probably drop the from <algorithm> part under the assumption the user can figure out the header pretty easily from the diagnostic wording. Also, you should put single quotes around the std%0::any_of(). Similar below.

[mgehre]

Aaron, thank you very much for taking the time to review this PR.

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

61

I think throw statements still can be transformed. We cannot transform break because the loop is gone and we cannot transform goto because we cannot jump from the lambda into its caller.
But we can keep throw statements because exceptions can propagate from the lambda through the algorithm back into the original caller. If we could not allow throw statements, we would also have to disallow any other kind of call statements.

[mgehre]

Fix comments

[aaron.ballman]

LGTM, though please wait a bit for @njames93 to speak up if they still have concerns.

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

61

Ah, good point on throw, thank you!

[njames93]

LGMT, just a few minor nits though.

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

15–16

Fairly certain these headers aren't used

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.h

30

std::all_of, std::any_of and std::none_of were only introduced in c++11, maybe CPlusPlus11 should be the minimum requirement.

clang-tools-extra/docs/ReleaseNotes.rst

207

This removed line in unrelated and should be added back

[mgehre]

Implemented njames93's comments

[gribozavr2]

This change broke the build: http://lab.llvm.org:8011/builders/clang-x86_64-debian-fast/builds/29716. The build is already fixed by https://github.com/llvm/llvm-project/commit/fd2740143e626ca32432aac0b51b2880a3b1e0bc.

Please always run ninja check-all before pushing commits. Thanks!

[RKSimon]

@mgehre Please can you take at the remaining buildbot failures here : http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/68662

[njames93]

In D77572#2071045, @RKSimon wrote:

@mgehre Please can you take at the remaining buildbot failures here : http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-ubuntu-fast/builds/68662

Pushed a fix for that too. https://github.com/llvm/llvm-project/commit/6780be4c63e582466a35d7644c35e09ba85d4f67

[mgehre]

Sorry for breaking the build and thanks for the fixes!

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.h

 //===--- UseAnyOfAllOfCheck.h - clang-tidy-----------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//

 
 /// Finds ranged-based for loops that can be replaced by a call to std::any_of
 /// or std::all_of.
 ///
 /// For the user-facing documentation see:
 /// http://clang.llvm.org/extra/clang-tidy/checks/readability-use-anyofallof.html
 class UseAnyOfAllOfCheck : public ClangTidyCheck {
 public:
-  UseAnyOfAllOfCheck(StringRef Name, ClangTidyContext *Context)
-      : ClangTidyCheck(Name, Context),
-        IncludeStyle(utils::IncludeSorter::parseIncludeStyle(
-            Options.getLocalOrGlobal("IncludeStyle", "llvm"))) {}
+  using ClangTidyCheck::ClangTidyCheck;
+
+  bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
+    return LangOpts.CPlusPlus;
+  }
 
-  void registerPPCallbacks(const SourceManager &SM, Preprocessor *PP,
-                           Preprocessor *ModuleExpanderPP) override;
   void registerMatchers(ast_matchers::MatchFinder *Finder) override;
   void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
-
-private:
-  std::unique_ptr<utils::IncludeInserter> IncludeInserter;
-  const utils::IncludeSorter::IncludeStyle IncludeStyle;
 };
 
 } // namespace readability
 } // namespace tidy
 } // namespace clang
 
 #endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_READABILITY_USEALGORITHMCHECK_H

clang-tools-extra/clang-tidy/readability/UseAnyOfAllOfCheck.cpp

 //===--- UseAnyOfAllOfCheck.cpp - clang-tidy-------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "UseAnyOfAllOfCheck.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/Analysis/Analyses/ExprMutationAnalyzer.h"
 #include "clang/Frontend/CompilerInstance.h"
 #include <algorithm>
 #include <string>
 
 using namespace clang::ast_matchers;
 
 namespace clang {
-namespace ast_matchers {
+namespace {
 /// Matches a Stmt whose parent is a CompoundStmt,
 /// and which is directly followed by
 /// a Stmt matching the inner matcher.
-AST_MATCHER_P(Stmt, nextStmt, internal::Matcher<Stmt>, InnerMatcher) {
-  const auto &Parents = Finder->getASTContext().getParents(Node);
+AST_MATCHER_P(Stmt, nextStmt, ast_matchers::internal::Matcher<Stmt>,
+              InnerMatcher) {
+  DynTypedNodeList Parents = Finder->getASTContext().getParents(Node);
   if (Parents.size() != 1)
     return false;
 
   auto *C = Parents[0].get<CompoundStmt>();
   if (!C)
     return false;
 
-  const auto *I = std::find(C->body_begin(), C->body_end(), &Node);
+  const auto *I = llvm::find(C->body(), &Node);
   assert(I != C->body_end()); // C is parent of Node.
   if (++I == C->body_end())
     return false; // Node is last statement.
 
   return InnerMatcher.matches(**I, Finder, Builder);
 }
-} // namespace ast_matchers
+} // namespace
 
 namespace tidy {
 namespace readability {
 
-void UseAnyOfAllOfCheck::registerPPCallbacks(const SourceManager &SM,
-                                             Preprocessor *PP,
-                                             Preprocessor *ModuleExpanderPP) {
-  IncludeInserter =
-      std::make_unique<utils::IncludeInserter>(SM, getLangOpts(), IncludeStyle);
-  PP->addPPCallbacks(IncludeInserter->CreatePPCallbacks());
-}
-
 void UseAnyOfAllOfCheck::registerMatchers(MatchFinder *Finder) {
-  if (!getLangOpts().CPlusPlus)
-    return;
-
   auto returns = [](bool V) {
     return returnStmt(hasReturnValue(cxxBoolLiteral(equals(V))));
   };
 
   auto returnsButNotTrue =
       returnStmt(hasReturnValue(unless(cxxBoolLiteral(equals(true)))));
   auto returnsButNotFalse =
       returnStmt(hasReturnValue(unless(cxxBoolLiteral(equals(false)))));
 
   Finder->addMatcher(
       cxxForRangeStmt(
           nextStmt(returns(false).bind("final_return")),
           hasBody(allOf(hasDescendant(returns(true)),
                         unless(anyOf(hasDescendant(breakStmt()),
                                      hasDescendant(returnsButNotTrue))))))
           .bind("any_of_loop"),
       this);
 
   Finder->addMatcher(
       cxxForRangeStmt(
           nextStmt(returns(true).bind("final_return")),
           hasBody(allOf(hasDescendant(returns(false)),

 
 void UseAnyOfAllOfCheck::check(const MatchFinder::MatchResult &Result) {
   StringRef Ranges = getLangOpts().CPlusPlus2a ? "::ranges" : "";
 
   if (const auto *S = Result.Nodes.getNodeAs<CXXForRangeStmt>("any_of_loop")) {
     if (!isViableLoop(*S, *Result.Context))
       return;
 
     diag(S->getForLoc(), "Replace loop by std%0::any_of() from <algorithm>")
         << Ranges;
-
   } else if (const auto *S =
                  Result.Nodes.getNodeAs<CXXForRangeStmt>("all_of_loop")) {
     if (!isViableLoop(*S, *Result.Context))
       return;
 
     diag(S->getForLoc(), "Replace loop by std%0::all_of() from <algorithm>")
         << Ranges;
   }
 }
 
 } // namespace readability
 } // namespace tidy
 } // namespace clang

clang-tools-extra/docs/ReleaseNotes.rst

 - New :doc:`misc-no-recursion
   <clang-tidy/checks/misc-no-recursion>` check.
 
   Finds recursive functions and diagnoses them.
 
 - New :doc:`readability-use-anyofallof
   <clang-tidy/checks/readability-use-anyofallof>` check.
 
-  Finds range-based for loops that can be replaced by a call to std::any_of or
-  std::all_of.
+  Finds range-based for loops that can be replaced by a call to ``std::any_of``
+  or ``std::all_of``.
 
 New check aliases
 ^^^^^^^^^^^^^^^^^
 
 - New alias :doc:`cert-con36-c
   <clang-tidy/checks/cert-con36-c>` to
   :doc:`bugprone-spuriously-wake-up-functions
   <clang-tidy/checks/bugprone-spuriously-wake-up-functions>` was added.

 The improvements are...
 
 Improvements to pp-trace
 ------------------------
 
 The improvements are...
 
 Clang-tidy visual studio plugin
 -------------------------------