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

21 ↗

(On Diff #51543)

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.

57 ↗

(On Diff #51543)

nit: no space needed before the question mark.

101 ↗

(On Diff #51543)

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

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

17 ↗

(On Diff #51543)

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

24 ↗

(On Diff #51543)

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

21 ↗

(On Diff #51543)

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?

23 ↗

(On Diff #51543)

Should elide the braces (here and elsewhere).

43 ↗

(On Diff #51543)

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).

79 ↗

(On Diff #51543)

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.
}
}

118 ↗

(On Diff #51543)

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

21 ↗

(On Diff #51543)

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.

21 ↗

(On Diff #51543)

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

79 ↗

(On Diff #51543)

Added a test, thanks for the catch !

[alexfh]

clang-tidy/misc/FoldInitTypeCheck.cpp

23 ↗

(On Diff #54045)

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

39 ↗

(On Diff #54045)

Use the more effective hasAnyName matcher.

52 ↗

(On Diff #54045)

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")));

89 ↗

(On Diff #54045)

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

89 ↗

(On Diff #54045)

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 ↗

(On Diff #54833)

Doesn't .. code node need new line?

[alexfh]

A few nits.

clang-tidy/misc/FoldInitTypeCheck.cpp

90 ↗

(On Diff #54833)

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 ↗

(On Diff #54833)

s/a initial value/an initial value/

16–17 ↗

(On Diff #54833)

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 ↗

(On Diff #54833)

Thanks for the catch.

16–17 ↗

(On Diff #54833)

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-tools-extra/trunk/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-tools-extra/trunk/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-tools-extra/trunk/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-tools-extra/trunk/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");

clang-tools-extra/trunk/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

clang-tools-extra/trunk/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 <https://en.wikipedia.org/wiki/Fold_(higher-order_function)>`_
+like `std::accumulate` that might result in loss of precision.
+`std::accumulate` folds an input range into an 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);

clang-tools-extra/trunk/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);
+}
+}