[clang-tidy] add check to suggest replacement of nested std::min or std::max with initializer lists

[sopyb]

closes #25340

Identifies cases where std::min or std::max is used to find the minimum or maximum value among more than two items through repeated calls. The check replaces these calls with a single call to std::min or std::max that uses an initializer list. This makes the code slightly more efficient.

[github-actions[bot]]

Thank you for submitting a Pull Request (PR) to the LLVM Project!

This PR will be automatically labeled and the relevant teams will be notified.

If you wish to, you can add reviewers by using the "Reviewers" section on this page.

If this is not working for you, it is probably because you do not have write permissions for the repository. In which case you can instead tag reviewers by name in a comment by using @ followed by their GitHub username.

If you have received no comments on your PR for a week, you can request a review by "ping"ing the PR by adding a comment “Ping”. The common courtesy "ping" rate is once a week. Please remember that you are asking for valuable time from other developers.

If you have further questions, they may be answered by the LLVM GitHub User Guide.

You can also ask questions in a comment on this PR, on the LLVM Discord or on the forums.

[llvmbot]

@llvm/pr-subscribers-clang-tools-extra

@llvm/pr-subscribers-clang-tidy

Author: Sopy (sopyb)

Changes

closes #25340

Identifies cases where std::min or std::max is used to find the minimum or maximum value among more than two items through repeated calls. The check replaces these calls with a single call to std::min or std::max that uses an initializer list. This makes the code slightly more efficient.

---

Full diff: https://github.com/llvm/llvm-project/pull/85572.diff

6 Files Affected:

• (modified) clang-tools-extra/clang-tidy/modernize/CMakeLists.txt (+1)
• (added) clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.cpp (+138)
• (added) clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.h (+58)
• (modified) clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp (+3)
• (modified) clang-tools-extra/docs/ReleaseNotes.rst (+6)
• (modified) clang-tools-extra/docs/clang-tidy/checks/list.rst (+2)

diff --git a/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt b/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt
index 6852db6c2ee311..8005d6e91c060c 100644
--- a/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt
+++ b/clang-tools-extra/clang-tidy/modernize/CMakeLists.txt
@@ -16,6 +16,7 @@ add_clang_library(clangTidyModernizeModule
   MakeSharedCheck.cpp
   MakeSmartPtrCheck.cpp
   MakeUniqueCheck.cpp
+  MinMaxUseInitializerListCheck.cpp
   ModernizeTidyModule.cpp
   PassByValueCheck.cpp
   RawStringLiteralCheck.cpp
diff --git a/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.cpp b/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.cpp
new file mode 100644
index 00000000000000..b7dc3ff436f6e3
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.cpp
@@ -0,0 +1,138 @@
+//===--- MinMaxUseInitializerListCheck.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 "MinMaxUseInitializerListCheck.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/Frontend/CompilerInstance.h"
+#include "clang/Lex/Lexer.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang::tidy::modernize {
+
+MinMaxUseInitializerListCheck::MinMaxUseInitializerListCheck(
+    StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      Inserter(Options.getLocalOrGlobal("IncludeStyle",
+                                        utils::IncludeSorter::IS_LLVM),
+               areDiagsSelfContained()) {}
+
+void MinMaxUseInitializerListCheck::storeOptions(
+    ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "IncludeStyle", Inserter.getStyle());
+}
+
+void MinMaxUseInitializerListCheck::registerMatchers(MatchFinder *Finder) {
+  Finder->addMatcher(
+      callExpr(
+          callee(functionDecl(hasName("::std::max"))),
+          hasAnyArgument(callExpr(callee(functionDecl(hasName("::std::max"))))),
+          unless(
+              hasParent(callExpr(callee(functionDecl(hasName("::std::max")))))))
+          .bind("maxCall"),
+      this);
+
+  Finder->addMatcher(
+      callExpr(
+          callee(functionDecl(hasName("::std::min"))),
+          hasAnyArgument(callExpr(callee(functionDecl(hasName("::std::min"))))),
+          unless(
+              hasParent(callExpr(callee(functionDecl(hasName("::std::min")))))))
+          .bind("minCall"),
+      this);
+}
+
+void MinMaxUseInitializerListCheck::registerPPCallbacks(
+    const SourceManager &SM, Preprocessor *PP, Preprocessor *ModuleExpanderPP) {
+  Inserter.registerPreprocessor(PP);
+}
+
+void MinMaxUseInitializerListCheck::check(
+    const MatchFinder::MatchResult &Result) {
+  const auto *MaxCall = Result.Nodes.getNodeAs<CallExpr>("maxCall");
+  const auto *MinCall = Result.Nodes.getNodeAs<CallExpr>("minCall");
+
+  const CallExpr *TopCall = MaxCall ? MaxCall : MinCall;
+  if (!TopCall) {
+    return;
+  }
+  const QualType ResultType =
+      TopCall->getDirectCallee()->getReturnType().getNonReferenceType();
+
+  const Expr *FirstArg = nullptr;
+  const Expr *LastArg = nullptr;
+  std::vector<const Expr *> Args;
+  findArgs(TopCall, &FirstArg, &LastArg, Args);
+
+  if (!FirstArg || !LastArg || Args.size() <= 2) {
+    return;
+  }
+
+  std::string ReplacementText = "{";
+  for (const Expr *Arg : Args) {
+    QualType ArgType = Arg->getType();
+    bool CastNeeded =
+        ArgType.getCanonicalType() != ResultType.getCanonicalType();
+
+    if (CastNeeded)
+      ReplacementText += "static_cast<" + ResultType.getAsString() + ">(";
+
+    ReplacementText += Lexer::getSourceText(
+        CharSourceRange::getTokenRange(Arg->getSourceRange()),
+        *Result.SourceManager, Result.Context->getLangOpts());
+
+    if (CastNeeded)
+      ReplacementText += ")";
+    ReplacementText += ", ";
+  }
+  ReplacementText = ReplacementText.substr(0, ReplacementText.size() - 2) + "}";
+
+  diag(TopCall->getBeginLoc(),
+       "do not use nested std::%0 calls, use %1 instead")
+      << TopCall->getDirectCallee()->getName() << ReplacementText
+      << FixItHint::CreateReplacement(
+             CharSourceRange::getTokenRange(
+                 FirstArg->getBeginLoc(),
+                 Lexer::getLocForEndOfToken(TopCall->getEndLoc(), 0,
+                                            Result.Context->getSourceManager(),
+                                            Result.Context->getLangOpts())
+                     .getLocWithOffset(-2)),
+             ReplacementText)
+      << Inserter.createMainFileIncludeInsertion("<algorithm>");
+}
+
+void MinMaxUseInitializerListCheck::findArgs(const CallExpr *Call,
+                                             const Expr **First,
+                                             const Expr **Last,
+                                             std::vector<const Expr *> &Args) {
+  if (!Call) {
+    return;
+  }
+
+  const FunctionDecl *Callee = Call->getDirectCallee();
+  if (!Callee) {
+    return;
+  }
+
+  for (const Expr *Arg : Call->arguments()) {
+    if (!*First)
+      *First = Arg;
+
+    const CallExpr *InnerCall = dyn_cast<CallExpr>(Arg);
+    if (InnerCall && InnerCall->getDirectCallee() &&
+        InnerCall->getDirectCallee()->getNameAsString() ==
+            Call->getDirectCallee()->getNameAsString()) {
+      findArgs(InnerCall, First, Last, Args);
+    } else
+      Args.push_back(Arg);
+
+    *Last = Arg;
+  }
+}
+
+} // namespace clang::tidy::modernize
diff --git a/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.h b/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.h
new file mode 100644
index 00000000000000..dc111d4ce7800e
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/modernize/MinMaxUseInitializerListCheck.h
@@ -0,0 +1,58 @@
+//===--- MinMaxUseInitializerListCheck.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_MINMAXUSEINITIALIZERLISTCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_MINMAXUSEINITIALIZERLISTCHECK_H
+
+#include "../ClangTidyCheck.h"
+#include "../utils/IncludeInserter.h"
+
+namespace clang::tidy::modernize {
+
+/// Transforms the repeated calls to `std::min` and `std::max` into a single
+/// call using initializer lists.
+///
+/// It identifies cases where `std::min` or `std::max` is used to find the
+/// minimum or maximum value among more than two items through repeated calls.
+/// The check replaces these calls with a single call to `std::min` or
+/// `std::max` that uses an initializer list. This makes the code slightly more
+/// efficient.
+/// \n\n
+/// For example:
+///
+/// \code
+///   int a = std::max(std::max(i, j), k);
+/// \endcode
+///
+/// This code is transformed to:
+///
+/// \code
+///   int a = std::max({i, j, k});
+/// \endcode
+class MinMaxUseInitializerListCheck : public ClangTidyCheck {
+public:
+  MinMaxUseInitializerListCheck(StringRef Name, ClangTidyContext *Context);
+
+  bool isLanguageVersionSupported(const LangOptions &LangOpts) const override {
+    return LangOpts.CPlusPlus11;
+  }
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void registerPPCallbacks(const SourceManager &SM, Preprocessor *PP,
+                           Preprocessor *ModuleExpanderPP) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  utils::IncludeInserter Inserter;
+  void findArgs(const CallExpr *call, const Expr **first, const Expr **last,
+                std::vector<const Expr *> &args);
+};
+
+} // namespace clang::tidy::modernize
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MODERNIZE_MINMAXUSEINITIALIZERLISTCHECK_H
diff --git a/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp b/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp
index e96cf274f58cfe..776558433c5baa 100644
--- a/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp
+++ b/clang-tools-extra/clang-tidy/modernize/ModernizeTidyModule.cpp
@@ -18,6 +18,7 @@
 #include "MacroToEnumCheck.h"
 #include "MakeSharedCheck.h"
 #include "MakeUniqueCheck.h"
+#include "MinMaxUseInitializerListCheck.h"
 #include "PassByValueCheck.h"
 #include "RawStringLiteralCheck.h"
 #include "RedundantVoidArgCheck.h"
@@ -68,6 +69,8 @@ class ModernizeModule : public ClangTidyModule {
     CheckFactories.registerCheck<MacroToEnumCheck>("modernize-macro-to-enum");
     CheckFactories.registerCheck<MakeSharedCheck>("modernize-make-shared");
     CheckFactories.registerCheck<MakeUniqueCheck>("modernize-make-unique");
+    CheckFactories.registerCheck<MinMaxUseInitializerListCheck>(
+        "modernize-min-max-use-initializer-list");
     CheckFactories.registerCheck<PassByValueCheck>("modernize-pass-by-value");
     CheckFactories.registerCheck<UseDesignatedInitializersCheck>(
         "modernize-use-designated-initializers");
diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst
index 44680f79de6f54..098a924a3b1527 100644
--- a/clang-tools-extra/docs/ReleaseNotes.rst
+++ b/clang-tools-extra/docs/ReleaseNotes.rst
@@ -110,6 +110,12 @@ New checks
   Detects error-prone Curiously Recurring Template Pattern usage, when the CRTP
   can be constructed outside itself and the derived class.
 
+- New :doc:`modernize-min-max-use-initializer-list
+  <clang-tidy/checks/modernize/min-max-use-initializer-list>` check.
+
+  Replaces chained ``std::min`` and ``std::max`` calls that can be written as
+  initializer lists.
+
 - New :doc:`modernize-use-designated-initializers
   <clang-tidy/checks/modernize/use-designated-initializers>` check.
 
diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst b/clang-tools-extra/docs/clang-tidy/checks/list.rst
index d03e7af688f007..029c339037880e 100644
--- a/clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -274,6 +274,7 @@ Clang-Tidy Checks
    :doc:`modernize-macro-to-enum <modernize/macro-to-enum>`, "Yes"
    :doc:`modernize-make-shared <modernize/make-shared>`, "Yes"
    :doc:`modernize-make-unique <modernize/make-unique>`, "Yes"
+   :doc:`modernize-min-max-use-initializer-list <modernize/min-max-use-initializer-list>`, "Yes"
    :doc:`modernize-pass-by-value <modernize/pass-by-value>`, "Yes"
    :doc:`modernize-raw-string-literal <modernize/raw-string-literal>`, "Yes"
    :doc:`modernize-redundant-void-arg <modernize/redundant-void-arg>`, "Yes"
@@ -324,6 +325,7 @@ Clang-Tidy Checks
    :doc:`performance-inefficient-algorithm <performance/inefficient-algorithm>`, "Yes"
    :doc:`performance-inefficient-string-concatenation <performance/inefficient-string-concatenation>`,
    :doc:`performance-inefficient-vector-operation <performance/inefficient-vector-operation>`, "Yes"
+   :doc:`performance-modernize-min-max-use-initializer-list <performance/modernize-min-max-use-initializer-list>`,
    :doc:`performance-move-const-arg <performance/move-const-arg>`, "Yes"
    :doc:`performance-move-constructor-init <performance/move-constructor-init>`,
    :doc:`performance-no-automatic-move <performance/no-automatic-move>`,

[sopyb]

Since I don't have permission to assign reviewers I will just ping @njames93

[github-actions[bot]]

:white_check_mark: With the latest revision this PR passed the C/C++ code formatter.

[sopyb]

It should be ready for review now. Sorry for requesting while my code was broken. I modified a line and committed it without checking if the code still works.

So there aren't a bunch of "Apply Clang format fixes" I also squished those into a single commit.

[sopyb]

Ping

[sopyb]

Hey there, I've hit a bit of a wall. I'm trying to figure out if a location is inside a comment. The check generates faulty diagnostics, as it is now, if there are comments including '(', '{', '}', and ','. If I could check if the match is inside a comment this issue could be fixed in a few lines of code. I spent all day looking around doxygen and trying out stuff but nothing seems to work. I could go through the tokens 1 by one and figure out if I am inside a comment but I don't think that'd be such a great idea. Here's an example of faulty code:

std::min(
  std::min/*some comment containing (*/(
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    // comment containing {
                          ~
    {
      4,
      5 
    // some comment containing }
                               ~
    },
    // some comment containing ,
                               ~
    CmpFunc
    ~~~~~~~ (as intended)
  ),
  ~
  1, 
CmpFunc);

so the output is

std::min(
  */(
    // comment containing
    {
      {4,
      5 
    // some comment containing 
    },
    // some comment containing 
  ,
  1}, 
CmpFunc);

[sopyb]

I tried to figure it out today as well, but I couldn't. I just ended up going through the source code figuring out the comment ranges and checking if the characters are contained between those. Let me know if there was a better way to do it and I will go ahead and make more changes.

[sopyb]

I am really sorry for the absolute dumpster fire that this PR has been. I had a hard time getting adjusted to the project structure. I genuinely appreciate the feedback and help provided. This was the first time I ever coded in C++ outside small university projects.

I'm pretty sure it is good to go now, but if any issues arise I will come back with the appropriate changes.

[sopyb]

Please let me know if I should rebase and squash the commits down into a single commit.

[sopyb]

std::initializer_list version std::min/std::max will reduce performance in some cases. Please ignore the check for

1. non-trivial class: https://godbolt.org/z/77ooaGzh6
2. large object: https://godbolt.org/z/14xoz8dnK

Thank you for your feedback! I'm grateful for your attention to potential performance impacts related to the use of std::initializer_list with std::min/std::max.

I think the aim of a moderniser check is to enhance code readability and adhere to modern C++ standards, so by default I think modernizing the codebase should be the priority. I'd like to explore the possibility of incorporating performance considerations as an option within the check.

@PiotrZSL, your expertise has been incredibly helpful throughout the process of making my first contribution. I value your perspective on whether we should provide an option within the check to skip addressing code with potential performance implications or have it as the default behavior. This way, users can choose if to prioritize performance or focus solely on code modernization.

I'd love to hear your thoughts on how I should proceed. Thank you once again for your valuable input.

[PiotrZSL]

@sopyb Check is for modernize, not performance, so:

• Add entry in documentation that due to need of copy object into initialization list check may cause performance degradation, add entry that using std::ref, std::cref is recommended in such case: b = std::max({std::ref(i), std::ref(j), std::ref(k)});
• Add option - IgnoreNonTrivialTypes - set by default to true
• Add option - IgnoreTrivialTypesOfSizeAbove - set by default to 32 bytes Options should be easy to add, check other checks. If you want quickly deliver version 1.0, then just limit check to built-in types.

As for copies of large types, that's more a thing for new performance check.

[sopyb]

Sorry for taking so long to come back with the changes. I have changed my environment last week and didn't have time to properly setup everything to make the required changes until now.

[sopyb]

Ping

[github-actions[bot]]

@sopyb Congratulations on having your first Pull Request (PR) merged into the LLVM Project!

Your changes will be combined with recent changes from other authors, then tested by our build bots. If there is a problem with a build, you may receive a report in an email or a comment on this PR.

Please check whether problems have been caused by your change specifically, as the builds can include changes from many authors. It is not uncommon for your change to be included in a build that fails due to someone else's changes, or infrastructure issues.

How to do this, and the rest of the post-merge process, is covered in detail here.

If your change does cause a problem, it may be reverted, or you can revert it yourself. This is a normal part of LLVM development. You can fix your changes and open a new PR to merge them again.

If you don't get any reports, no action is required from you. Your changes are working as expected, well done!

[VReichelt]

Unfortunately, I get a crash in some circumstances: #91982