A clang-tidy check for std:accumulate.

[courbet]

Summary

For folds (e.g. std::accumulate), check matches between the provided init value and the range's value_type. A typical error is "std::accumulate(begin, end, 0);", where begin and end have float value_type. See the documentation for more examples.

For now we check std::accumulate, std::reduce and std::inner_product.

[courbet]

ping ?

[alexfh]

Sorry for the delay (mostly due to the holidays here).

The check looks very useful, at least, the pattern is hard to spot by manual inspection. A few comments though, mostly style-related.

clang-tidy/misc/FoldInitTypeCheck.cpp

22

I suspect, a significant part of this could be done in the matcher. I might be wrong, but it seems worth trying. The resulting code is usually much shorter and cleaner.

58

nit: no space needed before the question mark.

102

nit: No braces needed for one line if bodies. Here and elsewhere.

test/clang-tidy/misc-fold-init-type.cpp

18

The CHECK lines shouldn't be broken. Looks like your clang-format doesn't use -style=file by default.

25

We usually specify each unique message completely once and truncate static parts of all other patterns to a make the test more readable. E.g. here I would remove everything after 'int'.

[aaron.ballman]

clang-tidy/misc/FoldInitTypeCheck.cpp

22

I kind of wonder if it would be generally useful as a matcher helper utility -- expose everything from std::iterator_traits with a nice AST matcher interface. Something that can be used like: iteratorTrait(hasValueType(<blah>), hasPointerType(<yada>)) Or is that overkill?

24

Should elide the braces (here and elsewhere).

44

s/allwed/allowed.

Also, may want to clarify what "fold" means in this context (can be confusing because there are fold expressions as well as constant folding).

80

Are there plans to apply this to other STL algorithms, like inner_product, reduce, etc? If so, it may be good to add a chunk of those up front.

Also, the name we should check should be ::std::accumulate. May want to include a test like:

namespace blah {
namespace std {
template <typename Iter, typename T>
T accumulate(Iter, Iter, T); // We should not care about this one.
}
}

119

You should be able to just pass the type directly into the diagnostic engine instead of mucking about with the printing policy directly.

[courbet]

• Use matchers for most of the check logic,
• Implement checking for reduce and inner_product,
• more tests.

[courbet]

Thanks, PTAL.

clang-tidy/misc/FoldInitTypeCheck.cpp

22

That would be cool, but I'm afraid it would give the false sense of covering all cases. Unfortunately the user can specialize iterator_traits for their iterator type, which would not be easy to cover.

22

Done, and that's indeed much nicer to read.

80

Added a test, thanks for the catch !

[alexfh]

clang-tidy/misc/FoldInitTypeCheck.cpp

24

s/id/ID/g
http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

40

Use the more effective hasAnyName matcher.

53

You can pull a few common parts to local variables to make the code slightly shorter and easier to read:

auto IteratorParam = parmVarDecl(hasType(hasCanonicalType(IteratorWithValueType("IterValueType"))));
auto Iterator2Param = parmVarDecl(hasType(hasCanonicalType(IteratorWithValueType("Iter2ValueType"))));
auto InitParam = parmVarDecl(hasType(BuiltinTypeWithId("InitType")));

90

Is "fold" a commonly used term in this context? At least, it's not a language standard jargon and not something I heard of frequently. Maybe we should try to find a more clear word?

[courbet]

Refactoring matchers & cosmetics.

clang-tidy/misc/FoldInitTypeCheck.cpp

90

The terminology is from functional programming (https://en.wikipedia.org/wiki/Fold_(higher-order_function)), I don't really have a better name for these. Do you have anything to suggest ?

[Prazek]

docs/clang-tidy/checks/misc-fold-init-type.rst

16–17

Doesn't .. code node need new line?

[alexfh]

A few nits.

clang-tidy/misc/FoldInitTypeCheck.cpp

90

No, I don't have a better name. The fp reference fixes my confusion ;) Maybe add this link to the user-facing documentation to tune the readers on the right frequency?

docs/clang-tidy/checks/misc-fold-init-type.rst

8

s/a initial value/an initial value/

16–17

Yes, it needs a new-line. Also, please verify the documentation actually builds with sphinx. On Ubuntu it should boil down to these commands:

$ sudo apt-get install python-sphinx
$ mkdir -p /some/build/directory && cd /some/build/directory
$ cmake /path/to/llvm/ -DLLVM_ENABLE_SPHINX=ON
$ make docs-clang-tools-html

[courbet]

Fix doc formatting and add more doc.

docs/clang-tidy/checks/misc-fold-init-type.rst

16–17

Thanks for the catch.

16–17

Thanks.

[alexfh]

Looks good now. Thank you for the new check!

Do you need me to submit the patch for you?

[courbet]

In D18442#411785, @alexfh wrote:

Looks good now. Thank you for the new check!

Thanks for the review.

Do you need me to submit the patch for you?

Yes, please.

clang-tidy/misc/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyMiscModule
   ArgumentCommentCheck.cpp
   AssertSideEffectCheck.cpp
   AssignOperatorSignatureCheck.cpp
   BoolPointerImplicitConversionCheck.cpp
   DanglingHandleCheck.cpp
   DefinitionsInHeadersCheck.cpp
+  FoldInitTypeCheck.cpp
   ForwardDeclarationNamespaceCheck.cpp
   InaccurateEraseCheck.cpp
   IncorrectRoundings.cpp
   InefficientAlgorithmCheck.cpp
   MacroParenthesesCheck.cpp
   MacroRepeatedSideEffectsCheck.cpp
   MiscTidyModule.cpp
   MisplacedWideningCastCheck.cpp

clang-tidy/misc/FoldInitTypeCheck.h

+//===--- FoldInitTypeCheck.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.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOLD_INIT_TYPE_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOLD_INIT_TYPE_H
+
+#include "../ClangTidy.h"
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+/// Find and flag invalid initializer values in folds, e.g. std::accumulate.
+/// Example:
+/// \code
+///   auto v = {65536L * 65536 * 65536};
+///   std::accumulate(begin(v), end(v), 0 /* int type is too small */);
+/// \endcode
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-fold-init-type.html
+class FoldInitTypeCheck : public ClangTidyCheck {
+public:
+  FoldInitTypeCheck(StringRef Name, ClangTidyContext *Context)
+      : ClangTidyCheck(Name, Context) {}
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+
+private:
+  void doCheck(const BuiltinType &IterValueType, const BuiltinType &InitType,
+               const ASTContext &Context, const CallExpr &CallNode);
+};
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_MISC_FOLD_INIT_TYPE_H

clang-tidy/misc/FoldInitTypeCheck.cpp

+//===--- FoldInitTypeCheck.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 "FoldInitTypeCheck.h"
+#include "clang/AST/ASTContext.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace misc {
+
+void FoldInitTypeCheck::registerMatchers(MatchFinder *Finder) {
+  // We match functions of interest and bind the iterator and init value types.
+  // Note: Right now we check only builtin types.
+  const auto BuiltinTypeWithId = [](const char *ID) {
+    return hasCanonicalType(builtinType().bind(ID));
+  };
+  const auto IteratorWithValueType = [&BuiltinTypeWithId](const char *ID) {
+    return anyOf(
+        // Pointer types.
+        pointsTo(BuiltinTypeWithId(ID)),
+        // Iterator types.
+        recordType(hasDeclaration(has(typedefNameDecl(
+            hasName("value_type"), hasType(BuiltinTypeWithId(ID)))))));
+  };
+
+  const auto IteratorParam = parmVarDecl(
+      hasType(hasCanonicalType(IteratorWithValueType("IterValueType"))));
+  const auto Iterator2Param = parmVarDecl(
+      hasType(hasCanonicalType(IteratorWithValueType("Iter2ValueType"))));
+  const auto InitParam = parmVarDecl(hasType(BuiltinTypeWithId("InitType")));
+
+  // std::accumulate, std::reduce.
+  Finder->addMatcher(
+      callExpr(callee(functionDecl(
+                   hasAnyName("::std::accumulate", "::std::reduce"),
+                   hasParameter(0, IteratorParam), hasParameter(2, InitParam))),
+               argumentCountIs(3))
+          .bind("Call"),
+      this);
+  // std::inner_product.
+  Finder->addMatcher(
+      callExpr(callee(functionDecl(hasName("::std::inner_product"),
+                                   hasParameter(0, IteratorParam),
+                                   hasParameter(2, Iterator2Param),
+                                   hasParameter(3, InitParam))),
+               argumentCountIs(4))
+          .bind("Call"),
+      this);
+  // std::reduce with a policy.
+  Finder->addMatcher(
+      callExpr(callee(functionDecl(hasName("::std::reduce"),
+                                   hasParameter(1, IteratorParam),
+                                   hasParameter(3, InitParam))),
+               argumentCountIs(4))
+          .bind("Call"),
+      this);
+  // std::inner_product with a policy.
+  Finder->addMatcher(
+      callExpr(callee(functionDecl(hasName("::std::inner_product"),
+                                   hasParameter(1, IteratorParam),
+                                   hasParameter(3, Iterator2Param),
+                                   hasParameter(4, InitParam))),
+               argumentCountIs(5))
+          .bind("Call"),
+      this);
+}
+
+/// Returns true if ValueType is allowed to fold into InitType, i.e. if:
+///   static_cast<InitType>(ValueType{some_value})
+/// does not result in trucation.
+static bool isValidBuiltinFold(const BuiltinType &ValueType,
+                               const BuiltinType &InitType,
+                               const ASTContext &Context) {
+  const auto ValueTypeSize = Context.getTypeSize(&ValueType);
+  const auto InitTypeSize = Context.getTypeSize(&InitType);
+  // It's OK to fold a float into a float of bigger or equal size, but not OK to
+  // fold into an int.
+  if (ValueType.isFloatingPoint())
+    return InitType.isFloatingPoint() && InitTypeSize >= ValueTypeSize;
+  // It's OK to fold an int into:
+  //  - an int of the same size and signedness.
+  //  - a bigger int, regardless of signedness.
+  //  - FIXME: should it be a warning to fold into floating point?
+  if (ValueType.isInteger()) {
+    if (InitType.isInteger()) {
+      if (InitType.isSignedInteger() == ValueType.isSignedInteger())
+        return InitTypeSize >= ValueTypeSize;
+      return InitTypeSize > ValueTypeSize;
+    }
+    if (InitType.isFloatingPoint())
+      return InitTypeSize >= ValueTypeSize;
+  }
+  return false;
+}
+
+/// Prints a diagnostic if IterValueType doe snot fold into IterValueType (see
+// isValidBuiltinFold for details).
+void FoldInitTypeCheck::doCheck(const BuiltinType &IterValueType,
+                                const BuiltinType &InitType,
+                                const ASTContext &Context,
+                                const CallExpr &CallNode) {
+  if (!isValidBuiltinFold(IterValueType, InitType, Context)) {
+    diag(CallNode.getExprLoc(), "folding type %0 into type %1 might result in "
+                                "loss of precision")
+        << IterValueType.desugar() << InitType.desugar();
+  }
+}
+
+void FoldInitTypeCheck::check(const MatchFinder::MatchResult &Result) {
+  // Given the iterator and init value type retreived by the matchers,
+  // we check that the ::value_type of the iterator is compatible with
+  // the init value type.
+  const auto *InitType = Result.Nodes.getNodeAs<BuiltinType>("InitType");
+  const auto *IterValueType =
+      Result.Nodes.getNodeAs<BuiltinType>("IterValueType");
+  assert(InitType != nullptr);
+  assert(IterValueType != nullptr);
+
+  const auto *CallNode = Result.Nodes.getNodeAs<CallExpr>("Call");
+  assert(CallNode != nullptr);
+
+  doCheck(*IterValueType, *InitType, *Result.Context, *CallNode);
+
+  if (const auto *Iter2ValueType =
+          Result.Nodes.getNodeAs<BuiltinType>("Iter2ValueType"))
+    doCheck(*Iter2ValueType, *InitType, *Result.Context, *CallNode);
+}
+
+} // namespace misc
+} // namespace tidy
+} // namespace clang

clang-tidy/misc/MiscTidyModule.cpp

 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 #include "ArgumentCommentCheck.h"
 #include "AssertSideEffectCheck.h"
 #include "AssignOperatorSignatureCheck.h"
 #include "BoolPointerImplicitConversionCheck.h"
 #include "DanglingHandleCheck.h"
 #include "DefinitionsInHeadersCheck.h"
+#include "FoldInitTypeCheck.h"
 #include "ForwardDeclarationNamespaceCheck.h"
 #include "InaccurateEraseCheck.h"
 #include "IncorrectRoundings.h"
 #include "InefficientAlgorithmCheck.h"
 #include "MacroParenthesesCheck.h"
 #include "MacroRepeatedSideEffectsCheck.h"
 #include "MisplacedWideningCastCheck.h"
 #include "MoveConstantArgumentCheck.h"
void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
     CheckFactories.registerCheck<AssignOperatorSignatureCheck>(
         "misc-assign-operator-signature");
     CheckFactories.registerCheck<BoolPointerImplicitConversionCheck>(
         "misc-bool-pointer-implicit-conversion");
     CheckFactories.registerCheck<DanglingHandleCheck>(
         "misc-dangling-handle");
     CheckFactories.registerCheck<DefinitionsInHeadersCheck>(
         "misc-definitions-in-headers");
+    CheckFactories.registerCheck<FoldInitTypeCheck>(
+        "misc-fold-init-type");
     CheckFactories.registerCheck<ForwardDeclarationNamespaceCheck>(
         "misc-forward-declaration-namespace");
     CheckFactories.registerCheck<InaccurateEraseCheck>(
         "misc-inaccurate-erase");
     CheckFactories.registerCheck<IncorrectRoundings>(
         "misc-incorrect-roundings");
     CheckFactories.registerCheck<InefficientAlgorithmCheck>(
         "misc-inefficient-algorithm");

docs/clang-tidy/checks/list.rst

.. toctree::
    llvm-namespace-comment
    llvm-twine-local
    misc-argument-comment
    misc-assert-side-effect
    misc-assign-operator-signature
    misc-bool-pointer-implicit-conversion
    misc-dangling-handle
    misc-definitions-in-headers
+   misc-fold-init-type
    misc-forward-declaration-namespace
    misc-inaccurate-erase
    misc-incorrect-roundings
    misc-inefficient-algorithm
    misc-macro-parentheses
    misc-macro-repeated-side-effects
    misc-misplaced-widening-cast
    misc-move-constructor-init

docs/clang-tidy/checks/misc-fold-init-type.rst

+.. title:: clang-tidy - misc-fold-init-type
+
+misc-fold-init-type
+===================
+
+The check flags type mismatches in folds like `std::accumulate` that might
+result in loss of precision.
+`std::accumulate` folds an input range into a initial value using the type of
+the latter, with `operator+` by default. This can cause loss of precision
+through:
+
+ - Truncation: The following code uses a floating point range and an int
+   initial value, so trucation wil happen at every application of `operator+`
+   and the result will be `0`, which might not be what the user expected.
+
+.. code:: c++
+  auto a = {0.5f, 0.5f, 0.5f, 0.5f};
+  return std::accumulate(std::begin(a), std::end(a), 0);
+
+ - Overflow: The following code also returns `0`.
+
+
+.. code:: c++
+  auto a = {65536LL * 65536 * 65536};
+  return std::accumulate(std::begin(a), std::end(a), 0);

test/clang-tidy/misc-fold-init-type.cpp

+// RUN: %check_clang_tidy %s misc-fold-init-type %t
+
+namespace std {
+template <class InputIt, class T>
+T accumulate(InputIt first, InputIt last, T init);
+
+template <class InputIt, class T>
+T reduce(InputIt first, InputIt last, T init);
+template <class ExecutionPolicy, class InputIt, class T>
+T reduce(ExecutionPolicy &&policy,
+         InputIt first, InputIt last, T init);
+
+struct parallel_execution_policy {};
+constexpr parallel_execution_policy par{};
+
+template <class InputIt1, class InputIt2, class T>
+T inner_product(InputIt1 first1, InputIt1 last1,
+                InputIt2 first2, T value);
+
+template <class ExecutionPolicy, class InputIt1, class InputIt2, class T>
+T inner_product(ExecutionPolicy &&policy, InputIt1 first1, InputIt1 last1,
+                InputIt2 first2, T value);
+
+} // namespace std
+
+struct FloatIterator {
+  typedef float value_type;
+};
+template <typename ValueType>
+struct TypedefTemplateIterator { typedef ValueType value_type; };
+template <typename ValueType>
+struct UsingTemplateIterator { using value_type = ValueType; };
+template <typename ValueType>
+struct DependentTypedefTemplateIterator { typedef typename ValueType::value_type value_type; };
+template <typename ValueType>
+struct DependentUsingTemplateIterator : public TypedefTemplateIterator<ValueType> { using typename TypedefTemplateIterator<ValueType>::value_type; };
+using TypedeffedIterator = FloatIterator;
+
+// Positives.
+
+int accumulatePositive1() {
+  float a[1] = {0.5f};
+  return std::accumulate(a, a + 1, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int accumulatePositive2() {
+  FloatIterator it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int accumulatePositive3() {
+  double a[1] = {0.0};
+  return std::accumulate(a, a + 1, 0.0f);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'double' into type 'float'
+}
+
+int accumulatePositive4() {
+  TypedefTemplateIterator<unsigned> it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
+}
+
+int accumulatePositive5() {
+  UsingTemplateIterator<unsigned> it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
+}
+
+int accumulatePositive6() {
+  DependentTypedefTemplateIterator<UsingTemplateIterator<unsigned>> it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
+}
+
+int accumulatePositive7() {
+  TypedeffedIterator it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int accumulatePositive8() {
+  DependentUsingTemplateIterator<unsigned> it;
+  return std::accumulate(it, it, 0);
+  // FIXME: this one should trigger too.
+}
+
+int reducePositive1() {
+  float a[1] = {0.5f};
+  return std::reduce(a, a + 1, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int reducePositive2() {
+  float a[1] = {0.5f};
+  return std::reduce(std::par, a, a + 1, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int innerProductPositive1() {
+  float a[1] = {0.5f};
+  int b[1] = {1};
+  return std::inner_product(std::par, a, a + 1, b, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int innerProductPositive2() {
+  float a[1] = {0.5f};
+  int b[1] = {1};
+  return std::inner_product(std::par, a, a + 1, b, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+// Negatives.
+
+int negative1() {
+  float a[1] = {0.5f};
+  // This is OK because types match.
+  return std::accumulate(a, a + 1, 0.0);
+}
+
+int negative2() {
+  float a[1] = {0.5f};
+  // This is OK because double is bigger than float.
+  return std::accumulate(a, a + 1, 0.0);
+}
+
+int negative3() {
+  float a[1] = {0.5f};
+  // This is OK because the user explicitly specified T.
+  return std::accumulate<float *, float>(a, a + 1, 0);
+}
+
+int negative4() {
+  TypedefTemplateIterator<unsigned> it;
+  // For now this is OK.
+  return std::accumulate(it, it, 0.0);
+}
+
+int negative5() {
+  float a[1] = {0.5f};
+  float b[1] = {1.0f};
+  return std::inner_product(std::par, a, a + 1, b, 0.0f);
+}
+
+namespace blah {
+namespace std {
+template <class InputIt, class T>
+T accumulate(InputIt, InputIt, T); // We should not care about this one.
+}
+
+int negative5() {
+  float a[1] = {0.5f};
+  // Note that this is using blah::std::accumulate.
+  return std::accumulate(a, a + 1, 0);
+}
+}