[clang-tidy] Add obvious-invalid-range

[Prazek]

Summary

Warns if algorithm is used with `.begin() and .end()` from
different variables.

[malcolm.parsons]

clang-tidy/ClangTidy.cpp

296 ↗

(On Diff #81578)

Is this intentional?

clang-tidy/misc/InvalidRangeCheck.cpp

40 ↗

(On Diff #81578)

Extra ; in string here or on line 36?

docs/ReleaseNotes.rst

84

"invalid" < "use"

docs/clang-tidy/checks/misc-invalid-range.rst

12 ↗

(On Diff #81578)

What about the parallel versions of algorithms?

[Prazek]

clang-tidy/ClangTidy.cpp

296 ↗

(On Diff #81578)

actually not, good catch. I was testing alpha checks

docs/clang-tidy/checks/misc-invalid-range.rst

12 ↗

(On Diff #81578)

parallel version won't take iterator as first argument, so it won't gonna match.
I don't think it makes sense to support parallel algorithms now because they don't have that many users yet.

[Prazek]

• Moved to obvious

[Prazek]

docs/ReleaseNotes.rst

84

You mean to change "invalid" to "use"?
It is not about using range, it is about finding broken range.

[Prazek]

• Small fixes

[malcolm.parsons]

What about arguments 3 and 4 of std::list::splice(It, list, It, It)?

clang-tidy/obvious/ObviousTidyModule.cpp

24

misc?

docs/ReleaseNotes.rst

84

The release notes should be in alphabetical order.

[Prazek]

docs/ReleaseNotes.rst

84

oh sure, fixed that.

[Prazek]

• Small fixes

[Prazek]

In D27806#623838, @malcolm.parsons wrote:

What about arguments 3 and 4 of std::list::splice(It, list, It, It)?

I am aware of that, but I wanted to make a bunch of simple checks to fill obvious module without taking too much time.
So does FIXIT comment satisfies you for this patch?

[Prazek]

• Small fixes

[malcolm.parsons]

In D27806#623856, @Prazek wrote:

So does FIXIT comment satisfies you for this patch?

Yes.

clang-tidy/obvious/InvalidRangeCheck.cpp

81

blank line at start of function.

docs/clang-tidy/checks/misc-invalid-range.rst

1 ↗

(On Diff #81604)

misc.

test/clang-tidy/misc-invalid-range.cpp

1 ↗

(On Diff #81604)

misc

[malcolm.parsons]

test/clang-tidy/misc-invalid-range.cpp

41 ↗

(On Diff #81604)

They're the same object...

[Prazek]

• Small fixes

[Prazek]

test/clang-tidy/misc-invalid-range.cpp

41 ↗

(On Diff #81604)

Yep, but this type of code stinks, so it is probably a bug

[malcolm.parsons]

docs/clang-tidy/checks/list.rst

68

misc.
add_new_check.py can fix it.

[Prazek]

docs/clang-tidy/checks/list.rst

68

How? I added new check with this script, but unfortunatelly rename_check doesn't move check from module to module, so I have to make all the changes by hand.

[Eugene.Zelenko]

clang-tidy/misc/InvalidRangeCheck.cpp

78 ↗

(On Diff #81578)

Please remove empty line.

docs/ReleaseNotes.rst

88

Probably container will be better word. Same for documentation.

test/clang-tidy/misc-invalid-range.cpp

28 ↗

(On Diff #81578)

Please add closing namespace comment and empty line bfore.

[Prazek]

• removed misc

[Prazek]

• Small fixes

[Prazek]

Also please review https://reviews.llvm.org/D27815 to make it happen

[malcolm.parsons]

docs/clang-tidy/checks/list.rst

68

add_new_check.py --update-docs

[Prazek]

docs/clang-tidy/checks/list.rst

68

Didn't know about it, cool

[Eugene.Zelenko]

It may be good idea to create LLVM check which will suggest to use STLExtras.h wrappers instead of STL algorithms.

[Prazek]

In D27806#624675, @Eugene.Zelenko wrote:

It may be good idea to create LLVM check which will suggest to use STLExtras.h wrappers instead of STL algorithms.

Sure, I actually didn't know about STLExtras, but anyway it would be something LLVM specific, where I want these checks to be non specific and usefull for every day use

[staronj]

clang-tidy/misc/InvalidRangeCheck.cpp

19 ↗

(On Diff #81578)

Remove std::fill_n (http://en.cppreference.com/w/cpp/algorithm/fill_n) - doesn't take two iterators.
Remove std::generate_n (http://en.cppreference.com/w/cpp/algorithm/generate_n) - as above
Remove std::max (http://en.cppreference.com/w/cpp/algorithm/max) - as above
Remove std::min (http://en.cppreference.com/w/cpp/algorithm/min) - as above

Add std::search_n (http://en.cppreference.com/w/cpp/algorithm/search_n)
What about std::accumulate (http://en.cppreference.com/w/cpp/algorithm/accumulate)?
What about std::inner_product (http://en.cppreference.com/w/cpp/algorithm/inner_product)?
What about std::adjacent_difference (http://en.cppreference.com/w/cpp/algorithm/adjacent_difference)?
What about std::partial_sum (http://en.cppreference.com/w/cpp/algorithm/partial_sum)?

38 ↗

(On Diff #81578)

Remove std::copy_n (http://en.cppreference.com/w/cpp/algorithm/copy_n) - it doesn't take range.
Remove std::minmax (http://en.cppreference.com/w/cpp/algorithm/minmax) - as above

What about std::iota (http://en.cppreference.com/w/cpp/algorithm/iota)?

[sbarzowski]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

I would go with one per line. It will be much more diff-friendly this way. And also much easier to add stuff in the middle and maybe keep it sorted.

41–46

Same here.

[Prazek]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

I don't expect this list to change in any way in the future, and it already take more than 20 lines. I don't want to put about 80 lines only to define the names

[sbarzowski]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

Ok, I don't think it's important enough to argue about it if it was your deliberate decision.

But I still think your argument is invalid :-). If anything that calls for putting it in a separate file.

[Prazek]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

By moving it to another file I would expose it to other checks, which is not my intention.
I also want to keep this simple and short, and by making this list less readable (which is not something that some next developer should care about) I make the whole file more readable, because it is shorter.

[Prazek]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

ok I think I will remove the list and instead will check if the name starts with std::, because if someone calls std::.

[aaron.ballman]

clang-tidy/obvious/InvalidRangeCheck.cpp

21–37

You should check if the canonical name starts with ::std::, otherwise you may run into issues with:

namespace my {
namespace std {
 // bad code goes here
}
}

[alexfh]

clang-tidy/obvious/InvalidRangeCheck.cpp

39

No global auto variables, please. In this case auto just isn't buying you anything, but in other cases it may be highly misleading.

59

Two nits here:

1. 80 is hardly "small" and this code is run once per analyzed file, so you're not saving much. Consider just using std::vector.
2. I think, SmallVector<...> Names(AlgorithmNames.begin(), AlgorithmNames.end()); would be much easier to read.

63

Does this check make sense without the names whitelist? What will is the use case?

68

Why should this be a declRefExpr? This will miss cases with a more complex expression, e.g. std::count(x.y().begin(), x.z().end(), ...). Considering y() and z() are simple getters, this might be a quite common code.

83

Is there a less wasteful way of doing this? E.g. compare pointers to canonical declarations?

docs/ReleaseNotes.rst

120

The idea of the obvious module is interesting, but I'm not sure this check belongs here. At least, I would like to run it on our code and see whether it finds anything before calling this "obvious" ;)

[Prazek]

clang-tidy/obvious/InvalidRangeCheck.cpp

63

I would guess most of the functions that would be called like
foo(v.begin(), v2.end(), ...) would take range as 2 first arguments. at least I never saw code that this would be valid
(other case is something like foo(v.begin(), v2.begin(), ...), but I look only for ranges [begin, end())

68

good point

83

maybe there is. I firstly wanted to make it simple and working and see what people think about these kind of checks.

docs/ReleaseNotes.rst

120

I runned it on LLVM and clang and as expected it didn't find anything (the code would crash or would be dead)

[• Quuxplusone]

clang-tidy/obvious/InvalidRangeCheck.cpp

63

I wonder if there is any hope that STL implementations might one day carry source-level annotations as to what is expected to be a range and what isn't. That is, something like

template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
    __attribute__((__expect_range__(__first, __last)))

similar to how we have __attribute__((__format__)) for printf-style format strings, and __attribute__((__sentinel__)) for null sentinels, and so on. Then you could eliminate the heuristics concerned with detecting "what formal parameters expect a range" and just work on the heuristics for "what actual arguments are a range". (E.g., v.end() and v.begin() are unlikely to make a valid range in that order. v.begin() and v2.end() are unlikely to make a valid range together. And so on.)

docs/ReleaseNotes.rst

120

As discussed more thoroughly in https://reviews.llvm.org/D27815 — I continue to think that this is a misuse of the word "obvious". Particularly, the phrase "while looking for an obvious bug" is an oxymoron: if the bug were obvious, you wouldn't need the compiler to help you look for it.
I'll pick the thread back up in D27815 rather than reopen it here.

test/clang-tidy/obvious-invalid-range.cpp

36

I would expect this same check to warn on

std::copy(v.begin(), v.begin(), v2.begin());
std::copy(v.end(), v.begin(), v2.begin());

Mind you, I'm not sure *any* of these three warnings will come up in practice enough to be useful to anyone; for all the code it takes to implement them, it might be higher ROI to invest in a general-purpose common-subexpression-detector and/or trying to track "rangeness" through a dataflow analysis.

46

I would expect a warning on this line, in that the result of std::move() is unused.

clang-tidy/obvious/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS support)
 
 add_clang_library(clangTidyObviousModule
   ObviousTidyModule.cpp
+  InvalidRangeCheck.cpp
 
   LINK_LIBS
   clangAST
   clangASTMatchers
   clangBasic
   clangLex
   clangTidy
   clangTidyUtils
   )

clang-tidy/obvious/InvalidRangeCheck.h

+//===--- InvalidRangeCheck.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_OBVIOUS_INVALID_RANGE_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OBVIOUS_INVALID_RANGE_H
+
+#include "../ClangTidy.h"
+#include <string>
+#include <vector>
+
+namespace clang {
+namespace tidy {
+namespace obvious {
+
+/// Find invalid call to algorithm with obviously invalid range of iterators.
+///
+/// For the user-facing documentation see:
+/// http://clang.llvm.org/extra/clang-tidy/checks/misc-invalid-range.html
+class InvalidRangeCheck : public ClangTidyCheck {
+public:
+  InvalidRangeCheck(StringRef Name, ClangTidyContext *Context);
+  void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+  void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+  void storeOptions(ClangTidyOptions::OptionMap &Opts) override;
+
+private:
+  std::vector<std::string> AlgorithmNames;
+};
+
+} // namespace obvious
+} // namespace tidy
+} // namespace clang
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_OBVIOUS_INVALID_RANGE_H

clang-tidy/obvious/InvalidRangeCheck.cpp

+//===--- InvalidRangeCheck.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 "InvalidRangeCheck.h"
+#include "../utils/OptionsUtils.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang {
+namespace tidy {
+namespace obvious {
+
+const std::string CXX_AlgorithmNames =
+    "std::for_each; std::find; std::find_if; std::find_end; "
+    "std::find_first_of; std::adjacent_find; std::count; std::count_if;"
+    "std::mismatch; std::equal; std::search; std::copy; "
+    "std::copy_backward; std::swap_ranges; std::transform; std::replace"
+    "std::replace_if; std::replace_copy; std::replace_copy_if; std::fill; "
+    "std::fill_n; std::generate; std::generate_n; std::remove; std::remove_if"
+    "std::remove_copy; std::remove_copy_if; std::unique; std::unique_copy;"
+    "std::reverse; std::reverse_copy; std::rotate; std::rotate_copy; "
+    "std::random_shuffle; std::partition; std::stable_partition; std::sort;"
+    "std::stable_sort; std::partial_sort; std::partial_sort_copy; "
+    "std::nth_element; std::lower_bound; std::upper_bound; std::equal_range;"
+    "std::binary_search; std::merge; std::inplace_merge; std::includes; "
+    "std::set_union; std::set_intersection; std::set_difference; "
+    "std::set_symetric_difference; std::push_heap; std::pop_heap"
+    "std::make_heap; std::sort_heap; std::min; std::max; std::min_element; "
+    "std::max_element; std::lexicographical_compare; std::next_permutation; "
+    "std::prev_permutation";
+
+const auto CXX11_AlgorithmNames =
+    CXX_AlgorithmNames + "; "
+    "std::all_of; std::any_of; std::none_of; std::find_if_not; "
+    "std::is_permutation; std::copy_n; std::copy_if; std::move; "
+    "std::move_backward; std::shuffle; std::is_partitioned;"
+    "std::partition_copy; std::partition_point; std::is_sorted"
+    "std::is_sorted_until; std::is_heap; std::is_heap_until; std::minmax; "
+    "std::minmax_element";
+
+InvalidRangeCheck::InvalidRangeCheck(StringRef Name, ClangTidyContext *Context)
+    : ClangTidyCheck(Name, Context),
+      AlgorithmNames(utils::options::parseStringList(Options.get(
+          "AlgorithmNames", getLangOpts().CPlusPlus11 ? CXX11_AlgorithmNames
+                                                      : CXX_AlgorithmNames))) {}
+
+void InvalidRangeCheck::registerMatchers(MatchFinder *Finder) {
+  if (!getLangOpts().CPlusPlus)
+    return;
+
+  // Not so small vector. 80 because there are about that many algorithms.
+  const auto Names =
+      SmallVector<StringRef, 80>(AlgorithmNames.begin(), AlgorithmNames.end());
+
+  auto CallsAlgorithm = hasDeclaration(
+      functionDecl(Names.size() > 0 ? hasAnyName(Names) : anything()));
+
+  auto MemberCallWithName = [](StringRef MethodName, StringRef BindThisName) {
+    return cxxMemberCallExpr(
+        hasDeclaration(cxxMethodDecl(hasName(MethodName))),
+        onImplicitObjectArgument(declRefExpr().bind(BindThisName)));
+  };
+  // FIXME: match for std::begin(arg) and std::end(arg2)
+  // FIXME: some algorithms like std::list::splice(It, list, It, It) take
+  // range as 3rd and 4th argument.
+  Finder->addMatcher(
+      callExpr(hasArgument(0, MemberCallWithName("begin", "first_arg")),
+               hasArgument(1, MemberCallWithName("end", "second_arg")),
+               CallsAlgorithm),
+      this);
+}
+
+void InvalidRangeCheck::check(const MatchFinder::MatchResult &Result) {
+  const auto *FirstArg = Result.Nodes.getNodeAs<DeclRefExpr>("first_arg");
+  const auto *SecondArg = Result.Nodes.getNodeAs<DeclRefExpr>("second_arg");
+  if (FirstArg->getNameInfo().getAsString() ==
+      SecondArg->getNameInfo().getAsString())
+    return;
+
+  diag(FirstArg->getExprLoc(),
+       "call to algorithm with begin and end from different objects");
+}
+
+void InvalidRangeCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+  Options.store(Opts, "AlgorithmNames",
+                utils::options::serializeStringList(AlgorithmNames));
+}
+
+} // namespace obvious
+} // namespace tidy
+} // namespace clang

clang-tidy/obvious/ObviousTidyModule.cpp

 //===------- ObviousTidyModule.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 "../ClangTidy.h"
 #include "../ClangTidyModule.h"
 #include "../ClangTidyModuleRegistry.h"
 
+#include "InvalidRangeCheck.h"
 using namespace clang::ast_matchers;
 
 namespace clang {
 namespace tidy {
 namespace obvious {
 
 class ObviousModule : public ClangTidyModule {
 public:
   void addCheckFactories(ClangTidyCheckFactories &CheckFactories) override {
-    // Add obvious checks here.
+    CheckFactories.registerCheck<InvalidRangeCheck>("obvious-invalid-range");
   }
 };
 
 // Register the ObviousModule using this statically initialized variable.
 static ClangTidyModuleRegistry::Add<ObviousModule> X("obvious-module",
                                                      "Add obvious checks.");
 
 } // namespace obvious
 
 // This anchor is used to force the linker to link in the generated object file
 // and thus register the ObviousModule.
 volatile int ObviousModuleAnchorSource = 0;
 
 } // namespace tidy
 } // namespace clang

docs/ReleaseNotes.rst

 - `misc-pointer-and-integral-operation` check was removed.
 
 - New `misc-use-after-move
   <http://clang.llvm.org/extra/clang-tidy/checks/misc-use-after-move.html>`_ check
 
   Warns if an object is used after it has been moved, without an intervening
   reinitialization.
 
 - `modernize-make-unique
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-make-unique.html>`_
   and `modernize-make-shared
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-make-shared.html>`_
   now handle calls to the smart pointer's ``reset()`` method.
 
 - The `modernize-use-auto
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-use-auto.html>`_ check
   now warns about variable declarations that are initialized with a cast.
 
 - The modernize-use-default check has been renamed to `modernize-use-equals-default
   <http://clang.llvm.org/extra/clang-tidy/checks/modernize-use-equals-default.html>`_.
 
- New `mpi-buffer-deref
 
   Flags buffers which are insufficiently dereferenced when passed to an MPI function call.
 
 - New `mpi-type-mismatch
   <http://clang.llvm.org/extra/clang-tidy/checks/mpi-type-mismatch.html>`_ check
 
   Flags MPI function calls with a buffer type and MPI data type mismatch.
 
+- New obvious module with checks for obvious bugs that probably won't be found
+  in working code, but can be found while looking for an obvious bug in broken
+  code.
+- New `obvious-invalid-range
+  <http://clang.llvm.org/extra/clang-tidy/checks/misc-invalid-range.html>`_ check
+
+  Warns if algorithm is used with ``.begin()`` and ``.end()`` from different
+  variables.
+
 - New `performance-inefficient-string-concatenation
   <http://clang.llvm.org/extra/clang-tidy/checks/performance-inefficient-string-concatenation.html>`_ check
 
   Warns about the performance overhead arising from concatenating strings using
   the ``operator+``, instead of ``operator+=``.
 
 - `readability-container-size-empty
   <http://clang.llvm.org/extra/clang-tidy/checks/readability-container-size-empty.html>`_ check

docs/clang-tidy/checks/list.rst

.. toctree::
    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-invalid-range
    misc-macro-parentheses
    misc-macro-repeated-side-effects
    misc-misplaced-const
    misc-misplaced-widening-cast
    misc-move-const-arg
    misc-move-constructor-init
    misc-move-forwarding-reference
    misc-multiple-statement-macro

docs/clang-tidy/checks/obvious-invalid-range.rst

+.. title:: clang-tidy - obvious-invalid-range
+
+obvious-invalid-range
+=====================
+
+This check finds invalid calls to algorithms with obviously invalid range of
+iterators like:
+
+.. code-block:: c++
+    std::fill(v.begin(), v2.end(), it);
+
+It checks if first and second argument of call is call to ``begin()``
+and ``end()``, but on different objects (having different name).
+
+By default it looks for all algorithms from ``<algorithm>``. This can be
+changed by using ``AlgorithmNames`` option, where empty list means that any
+function name will be accepted.
 No newline at end of file

test/clang-tidy/obvious-invalid-range.cpp

+// RUN: %check_clang_tidy %s obvious-invalid-range %t
+
+namespace std {
+
+template <class InputIterator, class OutputIterator>
+OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {
+  return result;
+}
+
+template <class InputIterator, class OutputIterator>
+OutputIterator move(InputIterator first, InputIterator last, OutputIterator result) {
+  return result;
+}
+
+template <typename T>
+T move(T &&) { return T(); }
+
+template <class InputIterator, typename Val>
+void fill(InputIterator first, InputIterator last, const Val &v) {
+}
+
+template <typename T>
+class vector {
+public:
+  T *begin();
+  T *end();
+};
+}
+
+void test_copy() {
+  std::vector<int> v, v2;
+  std::copy(v.begin(), v2.end(), v2.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: call to algorithm with begin and end from different objects [obvious-invalid-range]
+
+  std::copy(v.begin(), v.end(), v2.begin());
+}
+
+void test_move() {
+  std::vector<int> v;
+  auto &v2 = v;
+  std::move(v.begin(), v2.end(), v2.begin());
+  // CHECK-MESSAGES: :[[@LINE-1]]:13: warning: call to algorithm with begin and end from different objects
+
+  std::move(v.begin(), v.end(), v2.begin());
+  std::move(v.begin());
+  test_copy();
+}