https://github.com/njames93 created
https://github.com/llvm/llvm-project/pull/99917
Looks for various patterns of functions that take arguments calling begin/end
or similar for common mistakes.
Still needs a bit of work, but open to suggestions of how this check could be
improved
>From a8eb65dd46e9fff572963cc980bf5ea582085ef1 Mon Sep 17 00:00:00 2001
From: Nathan James <n.jame...@hotmail.co.uk>
Date: Mon, 22 Jul 2024 20:00:53 +0100
Subject: [PATCH] Create a new check to look for mis-use in calls that take
iterators
Looks for various patterns of functions that take arguments calling
begin/end or similar for common mistakes
---
.../bugprone/BugproneTidyModule.cpp | 3 +
.../clang-tidy/bugprone/CMakeLists.txt | 1 +
.../bugprone/IncorrectIteratorsCheck.cpp | 362 ++++++++++++++++++
.../bugprone/IncorrectIteratorsCheck.h | 44 +++
clang-tools-extra/docs/ReleaseNotes.rst | 6 +
.../checks/bugprone/incorrect-iterators.rst | 111 ++++++
.../docs/clang-tidy/checks/list.rst | 10 +-
.../checkers/bugprone/incorrect-iterators.cpp | 156 ++++++++
8 files changed, 688 insertions(+), 5 deletions(-)
create mode 100644
clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.cpp
create mode 100644
clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.h
create mode 100644
clang-tools-extra/docs/clang-tidy/checks/bugprone/incorrect-iterators.rst
create mode 100644
clang-tools-extra/test/clang-tidy/checkers/bugprone/incorrect-iterators.cpp
diff --git a/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp
b/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp
index 689eb92a3d8d1..cea040b81878a 100644
--- a/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp
+++ b/clang-tools-extra/clang-tidy/bugprone/BugproneTidyModule.cpp
@@ -33,6 +33,7 @@
#include "InaccurateEraseCheck.h"
#include "IncDecInConditionsCheck.h"
#include "IncorrectEnableIfCheck.h"
+#include "IncorrectIteratorsCheck.h"
#include "IncorrectRoundingsCheck.h"
#include "InfiniteLoopCheck.h"
#include "IntegerDivisionCheck.h"
@@ -139,6 +140,8 @@ class BugproneModule : public ClangTidyModule {
"bugprone-inaccurate-erase");
CheckFactories.registerCheck<IncorrectEnableIfCheck>(
"bugprone-incorrect-enable-if");
+ CheckFactories.registerCheck<IncorrectIteratorsCheck>(
+ "bugprone-incorrect-iterators");
CheckFactories.registerCheck<ReturnConstRefFromParameterCheck>(
"bugprone-return-const-ref-from-parameter");
CheckFactories.registerCheck<SwitchMissingDefaultCaseCheck>(
diff --git a/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt
b/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt
index cb0d8ae98bac5..8425dbed0505a 100644
--- a/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt
+++ b/clang-tools-extra/clang-tidy/bugprone/CMakeLists.txt
@@ -26,6 +26,7 @@ add_clang_library(clangTidyBugproneModule
ImplicitWideningOfMultiplicationResultCheck.cpp
InaccurateEraseCheck.cpp
IncorrectEnableIfCheck.cpp
+ IncorrectIteratorsCheck.cpp
ReturnConstRefFromParameterCheck.cpp
SuspiciousStringviewDataUsageCheck.cpp
SwitchMissingDefaultCaseCheck.cpp
diff --git a/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.cpp
b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.cpp
new file mode 100644
index 0000000000000..56429b9100146
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.cpp
@@ -0,0 +1,362 @@
+//===--- IncorrectIteratorsCheck.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 "IncorrectIteratorsCheck.h"
+#include "../utils/Matchers.h"
+#include "../utils/OptionsUtils.h"
+#include "clang/AST/ASTTypeTraits.h"
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/ASTMatchers/ASTMatchersMacros.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/iterator_range.h"
+
+using namespace clang::ast_matchers;
+
+namespace clang::tidy::bugprone {
+
+namespace {
+using SVU = llvm::SmallVector<unsigned, 3>;
+/// Checks to see if a function a
+AST_MATCHER_P(FunctionDecl, areParametersSameTemplateType, SVU, Indexes) {
+ const auto *TemplateDecl = Node.getPrimaryTemplate();
+ if (!TemplateDecl)
+ return false;
+ const auto *FuncDecl = TemplateDecl->getTemplatedDecl();
+ if (!FuncDecl)
+ return false;
+ assert(!Indexes.empty());
+ const auto *FirstParam = FuncDecl->getParamDecl(Indexes.front());
+ if (!FirstParam)
+ return false;
+ auto Type = FirstParam->getOriginalType();
+ for (auto Item : llvm::drop_begin(Indexes)) {
+ const auto *Param = FuncDecl->getParamDecl(Item);
+ if (!Param)
+ return false;
+ if (Param->getOriginalType() != Type)
+ return false;
+ }
+ return true;
+}
+struct NameMatchers {
+ ArrayRef<StringRef> FreeNames;
+ ArrayRef<StringRef> MethodNames;
+};
+
+struct NamePairs {
+ NameMatchers BeginNames;
+ NameMatchers EndNames;
+};
+
+struct FullState {
+ NamePairs Forward;
+ NamePairs Reversed;
+ NamePairs Combined;
+ NameMatchers All;
+ ArrayRef<StringRef> MakeReverseIterator;
+};
+
+} // namespace
+
+static constexpr char FirstRangeArg[] = "FirstRangeArg";
+static constexpr char FirstRangeArgExpr[] = "FirstRangeArgExpr";
+static constexpr char ReverseBeginBind[] = "ReverseBeginBind";
+static constexpr char ReverseEndBind[] = "ReverseEndBind";
+static constexpr char SecondRangeArg[] = "SecondRangeArg";
+static constexpr char SecondRangeArgExpr[] = "SecondRangeArgExpr";
+static constexpr char ArgMismatchBegin[] = "ArgMismatchBegin";
+static constexpr char ArgMismatchEnd[] = "ArgMismatchEnd";
+static constexpr char ArgMismatchExpr[] = "ArgMismatchExpr";
+static constexpr char ArgMismatchRevBind[] = "ArgMismatchRevBind";
+static constexpr char Callee[] = "Callee";
+static constexpr char Internal[] = "Internal";
+static constexpr char InternalOther[] = "InternalOther";
+static constexpr char InternalArgument[] = "InternalArgument";
+
+static auto
+makeExprMatcher(ast_matchers::internal::Matcher<Expr> ArgumentMatcher,
+ const NameMatchers &Names, ArrayRef<StringRef> MakeReverse,
+ const NameMatchers &RevNames, StringRef RevBind) {
+ return expr(anyOf(
+ cxxMemberCallExpr(argumentCountIs(0),
+ callee(cxxMethodDecl(hasAnyName(Names.MethodNames))),
+ on(ArgumentMatcher)),
+ callExpr(argumentCountIs(1),
+ hasDeclaration(functionDecl(hasAnyName(Names.FreeNames))),
+ hasArgument(0, ArgumentMatcher)),
+ callExpr(
+ callee(functionDecl(hasAnyName(MakeReverse))), argumentCountIs(1),
+ hasArgument(
+ 0, expr(anyOf(cxxMemberCallExpr(argumentCountIs(0),
+ callee(cxxMethodDecl(hasAnyName(
+ RevNames.MethodNames))),
+ on(ArgumentMatcher)),
+ callExpr(argumentCountIs(1),
+ hasDeclaration(functionDecl(
+ hasAnyName(RevNames.FreeNames))),
+ hasArgument(0, ArgumentMatcher))))))
+ .bind(RevBind)));
+}
+
+// Detects a range function where the argument for the begin call differs from
+// the end call std::find(I.begin(), J.end())
+static auto makeRangeArgMismatch(unsigned BeginExpected, unsigned EndExpected,
+ NamePairs Forward, NamePairs Reverse,
+ ArrayRef<StringRef> MakeReverse) {
+ std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+
+ for (const auto &[Primary, Backwards] :
+ {std::pair{Forward, Reverse}, std::pair{Reverse, Forward}}) {
+ Matchers.push_back(callExpr(
+ hasArgument(BeginExpected,
+ makeExprMatcher(expr().bind(FirstRangeArg),
+ Primary.BeginNames, MakeReverse,
+ Backwards.EndNames, ReverseBeginBind)
+ .bind(FirstRangeArgExpr)),
+ hasArgument(EndExpected,
+ makeExprMatcher(
+ expr(unless(matchers::isStatementIdenticalToBoundNode(
+ FirstRangeArg)))
+ .bind(SecondRangeArg),
+ Primary.EndNames, MakeReverse, Backwards.BeginNames,
+ ReverseEndBind)
+ .bind(SecondRangeArgExpr))));
+ }
+
+ return callExpr(
+ argumentCountAtLeast(std::max(BeginExpected, EndExpected) + 1),
+ ast_matchers::internal::DynTypedMatcher::constructVariadic(
+ ast_matchers::internal::DynTypedMatcher::VO_AnyOf,
+ ASTNodeKind::getFromNodeKind<CallExpr>(), std::move(Matchers))
+ .convertTo<CallExpr>());
+}
+
+// Detects a range function where we expect a call to begin but get a call to
+// end or vice versa std::find(X.end(), X.end()) // Here we would warn on the
+// first argument that it should be begin
+static auto makeUnexpectedBeginEndMatcher(unsigned Index, StringRef BindTo,
+ NameMatchers Names,
+ ArrayRef<StringRef> MakeReverse,
+ const NameMatchers &RevNames) {
+ return callExpr(hasArgument(Index, makeExprMatcher(expr().bind(BindTo),
Names,
+ MakeReverse, RevNames,
+ ArgMismatchRevBind)
+ .bind(ArgMismatchExpr)));
+}
+
+static auto makeUnexpectedBeginEndPair(unsigned BeginExpected,
+ unsigned EndExpected,
+ NamePairs BeginEndPairs,
+ ArrayRef<StringRef> MakeReverse) {
+ // return expr(unless(anything()));
+ return eachOf(makeUnexpectedBeginEndMatcher(
+ BeginExpected, ArgMismatchBegin, BeginEndPairs.EndNames,
+ MakeReverse, BeginEndPairs.BeginNames),
+ makeUnexpectedBeginEndMatcher(
+ EndExpected, ArgMismatchEnd, BeginEndPairs.BeginNames,
+ MakeReverse, BeginEndPairs.EndNames));
+}
+
+/// The full matcher for functions that take a range with 2 arguments
+static auto makePairRangeMatcher(std::vector<StringRef> FuncNames,
+ unsigned BeginExpected, unsigned EndExpected,
+ const FullState &State) {
+
+ return callExpr(callee(functionDecl(hasAnyName(std::move(FuncNames)),
+ areParametersSameTemplateType(
+ {BeginExpected, EndExpected}))),
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected,
+ State.Forward, State.Reversed,
+ State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator)))
+ .bind(Callee);
+}
+
+static auto makeContainerInternalMatcher(std::vector<StringRef> ClassNames,
+ std::vector<StringRef> ClassMethods,
+ unsigned InternalExpected,
+ const FullState &State) {
+ return cxxMemberCallExpr(
+ thisPointerType(cxxRecordDecl(hasAnyName(std::move(ClassNames)))),
+ callee(cxxMethodDecl(hasAnyName(std::move(ClassMethods)))),
+ on(expr().bind(Internal)),
+ hasArgument(
+ InternalExpected,
+ makeExprMatcher(
+ expr(unless(matchers::isStatementIdenticalToBoundNode(Internal)))
+ .bind(InternalOther),
+ State.All, State.MakeReverseIterator, State.All,
+ ArgMismatchRevBind)
+ .bind(InternalArgument))).bind(Callee);
+}
+
+/// Full matcher for class methods that take a range with 2 arguments
+static auto makeContainerPairRangeMatcher(std::vector<StringRef> ClassNames,
+ std::vector<StringRef> ClassMethods,
+ unsigned BeginExpected,
+ unsigned EndExpected,
+ const FullState &State) {
+ return cxxMemberCallExpr(
+ thisPointerType(cxxRecordDecl(hasAnyName(std::move(ClassNames)))),
+ callee(cxxMethodDecl(
+ hasAnyName(std::move(ClassMethods)),
+ areParametersSameTemplateType({BeginExpected, EndExpected}))),
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected,
+ State.Forward, State.Reversed,
+ State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator)))
+ .bind(Callee);
+}
+
+void IncorrectIteratorsCheck::registerMatchers(MatchFinder *Finder) {
+ NamePairs Forward{NameMatchers{BeginFree, BeginMethod},
+ NameMatchers{EndFree, EndMethod}};
+ NamePairs Reverse{NameMatchers{RBeginFree, RBeginMethod},
+ NameMatchers{REndFree, REndMethod}};
+ llvm::SmallVector<StringRef, 8> CombinedFreeBegin{
+ llvm::iterator_range{llvm::concat<StringRef>(BeginFree, RBeginFree)}};
+ llvm::SmallVector<StringRef, 8> CombinedFreeEnd{
+ llvm::iterator_range{llvm::concat<StringRef>(EndFree, REndFree)}};
+ llvm::SmallVector<StringRef, 8> CombinedMethodBegin{
+ llvm::iterator_range{llvm::concat<StringRef>(BeginMethod,
RBeginMethod)}};
+ llvm::SmallVector<StringRef, 8> CombinedMethodEnd{
+ llvm::iterator_range{llvm::concat<StringRef>(EndMethod, REndMethod)}};
+ llvm::SmallVector<StringRef, 16> AllFree{llvm::iterator_range{
+ llvm::concat<StringRef>(CombinedFreeBegin, CombinedFreeEnd)}};
+ llvm::SmallVector<StringRef, 16> AllMethod{llvm::iterator_range{
+ llvm::concat<StringRef>(CombinedMethodBegin, CombinedMethodEnd)}};
+ NamePairs Combined{NameMatchers{CombinedFreeBegin, CombinedMethodBegin},
+ NameMatchers{CombinedFreeEnd, CombinedMethodEnd}};
+ FullState State{
+ Forward, Reverse, Combined, {AllFree, AllMethod}, MakeReverseIterator};
+ Finder->addMatcher(makePairRangeMatcher({"::std::find"}, 1, 2, State), this);
+ Finder->addMatcher(makePairRangeMatcher({"::std::find"}, 0, 1, State), this);
+ Finder->addMatcher(
+ makeContainerPairRangeMatcher({"::std::vector", "::std::list"},
+ {"insert"}, 1, 2, State),
+ this);
+ Finder->addMatcher(
+ makeContainerInternalMatcher({"::std::vector", "::std::list"},
+ {"insert", "erase", "emplace"}, 0, State),
+ this);
+}
+
+void IncorrectIteratorsCheck::check(const MatchFinder::MatchResult &Result) {
+ const auto *Call = Result.Nodes.getNodeAs<CallExpr>(Callee);
+ if (const auto *BeginMismatch =
+ Result.Nodes.getNodeAs<Expr>(ArgMismatchBegin)) {
+ diag(BeginMismatch->getBeginLoc(),
+ "'end' iterator supplied where a 'begin' iterator is expected")
+ << Result.Nodes.getNodeAs<Expr>(ArgMismatchExpr)->getSourceRange();
+ if (const auto *Rev =
+ Result.Nodes.getNodeAs<CallExpr>(ArgMismatchRevBind)) {
+ diag(Rev->getBeginLoc(), "%0 changes 'begin' into a 'end' iterator",
+ DiagnosticIDs::Note)
+ << Rev->getSourceRange() << Rev->getDirectCallee();
+ }
+ } else if (const auto *EndMismatch =
+ Result.Nodes.getNodeAs<Expr>(ArgMismatchEnd)) {
+ diag(EndMismatch->getBeginLoc(),
+ "'begin' iterator supplied where an 'end' iterator is expected")
+ << Result.Nodes.getNodeAs<Expr>(ArgMismatchExpr)->getSourceRange();
+ if (const auto *Rev =
+ Result.Nodes.getNodeAs<CallExpr>(ArgMismatchRevBind)) {
+ diag(Rev->getBeginLoc(), "%0 changes 'end' into a 'begin' iterator",
+ DiagnosticIDs::Note)
+ << Rev->getSourceRange() << Rev->getDirectCallee();
+ }
+ } else if (const auto *InternalArg =
+ Result.Nodes.getNodeAs<Expr>(InternalArgument)) {
+ diag(InternalArg->getBeginLoc(),
+ "%0 called with an iterator for a different container")
+ << Call->getDirectCallee();
+ const auto *Object = Result.Nodes.getNodeAs<Expr>(Internal);
+ diag(Object->getBeginLoc(), "container is specified here",
+ DiagnosticIDs::Note)
+ << Object->getSourceRange();
+ const auto *Other = Result.Nodes.getNodeAs<Expr>(InternalOther);
+ diag(Other->getBeginLoc(), "different container provided here",
+ DiagnosticIDs::Note)
+ << Other->getSourceRange();
+ } else {
+ const auto *Range1 = Result.Nodes.getNodeAs<Expr>(FirstRangeArg);
+ const auto *Range2 = Result.Nodes.getNodeAs<Expr>(SecondRangeArg);
+ const auto *FullRange1 = Result.Nodes.getNodeAs<Expr>(FirstRangeArgExpr);
+ const auto *FullRange2 = Result.Nodes.getNodeAs<Expr>(SecondRangeArgExpr);
+ assert(Range1 && Range2 && FullRange1 && FullRange2 && "Unexpected match");
+ diag(Call->getBeginLoc(), "mismatched ranges pass to function")
+ << FullRange1->getSourceRange() << FullRange2->getSourceRange();
+ diag(Range1->getBeginLoc(), "first range passed here to begin",
+ DiagnosticIDs::Note)
+ << FullRange1->getSourceRange();
+ diag(Range2->getBeginLoc(), "different range passed here to end",
+ DiagnosticIDs::Note)
+ << FullRange2->getSourceRange();
+ }
+}
+
+IncorrectIteratorsCheck::IncorrectIteratorsCheck(StringRef Name,
+ ClangTidyContext *Context)
+ : ClangTidyCheck(Name, Context),
+ BeginFree(utils::options::parseStringList(
+ Options.get("BeginFree", "::std::begin;::std::cbegin"))),
+ EndFree(utils::options::parseStringList(
+ Options.get("EndFree", "::std::end;::std::cend"))),
+ BeginMethod(utils::options::parseStringList(
+ Options.get("BeginMethod", "begin;cbegin"))),
+ EndMethod(utils::options::parseStringList(
+ Options.get("EndMethod", "end;cend"))),
+ RBeginFree(utils::options::parseStringList(
+ Options.get("RBeginFree", "::std::rbegin;::std::crbegin"))),
+ REndFree(utils::options::parseStringList(
+ Options.get("REndFree", "::std::rend;::std::crend"))),
+ RBeginMethod(utils::options::parseStringList(
+ Options.get("RBeginMethod", "rbegin;crbegin"))),
+ REndMethod(utils::options::parseStringList(
+ Options.get("REndMethod", "rend;crend"))),
+ MakeReverseIterator(utils::options::parseStringList(
+ Options.get("MakeReverseIterator", "::std::make_reverse_iterator")))
{
+}
+
+void IncorrectIteratorsCheck::storeOptions(ClangTidyOptions::OptionMap &Opts) {
+ Options.store(Opts, "BeginFree",
+ utils::options::serializeStringList(BeginFree));
+ Options.store(Opts, "EndFree", utils::options::serializeStringList(EndFree));
+ Options.store(Opts, "BeginMethod",
+ utils::options::serializeStringList(BeginMethod));
+ Options.store(Opts, "EndMethod",
+ utils::options::serializeStringList(EndMethod));
+ Options.store(Opts, "RBeginFree",
+ utils::options::serializeStringList(RBeginFree));
+ Options.store(Opts, "REndFree",
+ utils::options::serializeStringList(REndFree));
+ Options.store(Opts, "RBeginMethod",
+ utils::options::serializeStringList(RBeginMethod));
+ Options.store(Opts, "REndMethod",
+ utils::options::serializeStringList(REndMethod));
+ Options.store(Opts, "MakeReverseIterator",
+ utils::options::serializeStringList(MakeReverseIterator));
+}
+std::optional<TraversalKind>
+IncorrectIteratorsCheck::getCheckTraversalKind() const {
+ return TK_IgnoreUnlessSpelledInSource;
+}
+} // namespace clang::tidy::bugprone
diff --git a/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.h
b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.h
new file mode 100644
index 0000000000000..9f33b61c5a981
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.h
@@ -0,0 +1,44 @@
+//===--- IncorrectIteratorsCheck.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_BUGPRONE_INCORRECTITERATORSCHECK_H
+#define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INCORRECTITERATORSCHECK_H
+
+#include "../ClangTidyCheck.h"
+#include "llvm/ADT/StringRef.h"
+
+namespace clang::tidy::bugprone {
+
+/// Detects calls to iterator algorithms where they are called with potentially
+/// invalid arguments.
+///
+/// For the user-facing documentation see:
+///
http://clang.llvm.org/extra/clang-tidy/checks/bugprone/incorrect-iterators.html
+class IncorrectIteratorsCheck : public ClangTidyCheck {
+public:
+ IncorrectIteratorsCheck(StringRef Name, ClangTidyContext *Context);
+ void registerMatchers(ast_matchers::MatchFinder *Finder) override;
+ void check(const ast_matchers::MatchFinder::MatchResult &Result) override;
+ void storeOptions(ClangTidyOptions::OptionMap &Options) override;
+ std::optional<TraversalKind> getCheckTraversalKind() const override;
+
+private:
+ std::vector<StringRef> BeginFree;
+ std::vector<StringRef> EndFree;
+ std::vector<StringRef> BeginMethod;
+ std::vector<StringRef> EndMethod;
+ std::vector<StringRef> RBeginFree;
+ std::vector<StringRef> REndFree;
+ std::vector<StringRef> RBeginMethod;
+ std::vector<StringRef> REndMethod;
+ std::vector<StringRef> MakeReverseIterator;
+};
+
+} // namespace clang::tidy::bugprone
+
+#endif // LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_BUGPRONE_INCORRECTITERATORSCHECK_H
diff --git a/clang-tools-extra/docs/ReleaseNotes.rst
b/clang-tools-extra/docs/ReleaseNotes.rst
index a23483e6df6d2..4e15dc22e3a95 100644
--- a/clang-tools-extra/docs/ReleaseNotes.rst
+++ b/clang-tools-extra/docs/ReleaseNotes.rst
@@ -147,6 +147,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:`bugprone-incorrect-iterators
+ <clang-tidy/checks/bugprone/incorrect-iterators>` check.
+
+ Detects calls to iterator algorithms where they are called with potentially
+ invalid arguments.
+
- New :doc:`bugprone-pointer-arithmetic-on-polymorphic-object
<clang-tidy/checks/bugprone/pointer-arithmetic-on-polymorphic-object>` check.
diff --git
a/clang-tools-extra/docs/clang-tidy/checks/bugprone/incorrect-iterators.rst
b/clang-tools-extra/docs/clang-tidy/checks/bugprone/incorrect-iterators.rst
new file mode 100644
index 0000000000000..f6f6540d2bdd1
--- /dev/null
+++ b/clang-tools-extra/docs/clang-tidy/checks/bugprone/incorrect-iterators.rst
@@ -0,0 +1,111 @@
+.. title:: clang-tidy - bugprone-incorrect-iterators
+
+bugprone-incorrect-iterators
+============================
+
+Detects calls to iterator algorithms where they are called with potentially
+invalid arguments.
+
+Different ranges
+================
+
+Looks for calls where the range for the `begin` argument is different to the
+`end` argument
+
+.. code-block:: c++
+
+ std::find(a.begin(), b.end(), 0);
+ std::find(std::begin(a), std::end(b));
+
+Mismatched Begin/end
+====================
+
+Looks for calls where the `begin` parameter is passed an `end` argument or vice
+versa
+
+.. code-block:: c++
+
+ std::find(a.begin(), a.begin(), 0); // Second argument should be a.end().
+ std::find(a.end(), a.end(), 0); // First argument should be a.begin().
+
+Reverse Iteration
+=================
+
+The check understands `rbegin` and `rend` and ensures they are in the correct
places.
+
+.. code-block:: c++
+
+ std::find(a.rbegin(), a.rend(), 0); // OK.
+ std::find(a.rend(), a.rbegin(), 0); // Arguments are swapped.
+
+Manually creating a reverse iterator using the ``std::make_reverse_iterator``
is
+also supported, In this case the check looks for calls to `end` for the `begin`
+parameter and vice versa. The name of functions for creating reverse iterator
+can be configured with the option :option:`MakeReverseIterator`
+
+.. code-block:: c++
+
+ std::find(std::make_reverse_iterator(a.begin()),
+ std::make_reverse_iterator(a.end()), 0); // Arguments are swapped
+ std::find(std::make_reverse_iterator(a.end()),
+ std::make_reverse_iterator(a.begin()), 0); // OK
+ // Understands this spaghetti looking code is actually doing the correct
thing
+ std::find(a.rbegin(), std::make_reverse_iterator(a.begin()), 0);
+
+Container Methods
+=================
+
+Looks for calls to methods on containers that expect an iterator inside the
+container but are given a different container
+
+.. code-block:: c++
+
+ vec.insert(other_vec.begin(), 5); // The iterator is invalid for this
container
+
+Options
+-------
+
+.. option:: BeginFree
+
+ A semi-colon seperated list of free function names that return an iterator to
+ the start of a range. Default value is `::std::begin;std::cbegin`.
+
+.. option:: EndFree
+
+ A semi-colon seperated list of free function names that return an iterator to
+ the end of a range. Default value is `::std::end;std::cend`.
+
+.. option:: BeginMethod
+
+ A semi-colon seperated list of method names that return an iterator to
+ the start of a range. Default value is `begin;cbegin`.
+
+.. option:: EndMethod
+
+ A semi-colon seperated list of method names that return an iterator to
+ the end of a range. Default value is `end;cend`.
+
+.. option:: RBeginFree
+
+ A semi-colon seperated list of free function names that return a reverse
+ iterator to the start of a range. Default value is
`::std::rbegin;std::crbegin`.
+
+.. option:: REndFree
+
+ A semi-colon seperated list of free function names that return a reverse
+ iterator to the end of a range. Default value is `::std::rend;std::crend`.
+
+.. option:: RBeginMethod
+
+ A semi-colon seperated list of method names that return a reverse
+ iterator to the start of a range. Default value is `rbegin;crbegin`.
+
+.. option:: REndMethod
+
+ A semi-colon seperated list of method names that return a reverse
+ iterator to the end of a range. Default value is `rend;crend`.
+
+.. option:: MakeReverseIterator
+
+ A semi-colon seperated list of free functions that convert an interator into
a
+ reverse iterator. Default value is `::std::make_reverse_iterator`
diff --git a/clang-tools-extra/docs/clang-tidy/checks/list.rst
b/clang-tools-extra/docs/clang-tidy/checks/list.rst
index dd2887edb0f8d..2e22dc5b6824f 100644
--- a/clang-tools-extra/docs/clang-tidy/checks/list.rst
+++ b/clang-tools-extra/docs/clang-tidy/checks/list.rst
@@ -100,6 +100,7 @@ Clang-Tidy Checks
:doc:`bugprone-inaccurate-erase <bugprone/inaccurate-erase>`, "Yes"
:doc:`bugprone-inc-dec-in-conditions <bugprone/inc-dec-in-conditions>`,
:doc:`bugprone-incorrect-enable-if <bugprone/incorrect-enable-if>`, "Yes"
+ :doc:`bugprone-incorrect-iterators <bugprone/incorrect-iterators>`, "Yes"
:doc:`bugprone-incorrect-roundings <bugprone/incorrect-roundings>`,
:doc:`bugprone-infinite-loop <bugprone/infinite-loop>`,
:doc:`bugprone-integer-division <bugprone/integer-division>`,
@@ -118,6 +119,7 @@ Clang-Tidy Checks
:doc:`bugprone-not-null-terminated-result
<bugprone/not-null-terminated-result>`, "Yes"
:doc:`bugprone-optional-value-conversion
<bugprone/optional-value-conversion>`, "Yes"
:doc:`bugprone-parent-virtual-call <bugprone/parent-virtual-call>`, "Yes"
+ :doc:`bugprone-pointer-arithmetic-on-polymorphic-object
<bugprone/pointer-arithmetic-on-polymorphic-object>`,
:doc:`bugprone-posix-return <bugprone/posix-return>`, "Yes"
:doc:`bugprone-redundant-branch-condition
<bugprone/redundant-branch-condition>`, "Yes"
:doc:`bugprone-reserved-identifier <bugprone/reserved-identifier>`, "Yes"
@@ -158,7 +160,6 @@ Clang-Tidy Checks
:doc:`bugprone-unused-raii <bugprone/unused-raii>`, "Yes"
:doc:`bugprone-unused-return-value <bugprone/unused-return-value>`,
:doc:`bugprone-use-after-move <bugprone/use-after-move>`,
- :doc:`bugprone-pointer-arithmetic-on-polymorphic-object
<bugprone/pointer-arithmetic-on-polymorphic-object>`,
:doc:`bugprone-virtual-near-miss <bugprone/virtual-near-miss>`, "Yes"
:doc:`cert-dcl50-cpp <cert/dcl50-cpp>`,
:doc:`cert-dcl58-cpp <cert/dcl58-cpp>`,
@@ -269,7 +270,7 @@ Clang-Tidy Checks
:doc:`misc-unused-parameters <misc/unused-parameters>`, "Yes"
:doc:`misc-unused-using-decls <misc/unused-using-decls>`, "Yes"
:doc:`misc-use-anonymous-namespace <misc/use-anonymous-namespace>`,
- :doc:`misc-use-internal-linkage <misc/use-internal-linkage>`,
+ :doc:`misc-use-internal-linkage <misc/use-internal-linkage>`, "Yes"
:doc:`modernize-avoid-bind <modernize/avoid-bind>`, "Yes"
:doc:`modernize-avoid-c-arrays <modernize/avoid-c-arrays>`,
:doc:`modernize-concat-nested-namespaces
<modernize/concat-nested-namespaces>`, "Yes"
@@ -400,15 +401,14 @@ Clang-Tidy Checks
:doc:`readability-use-std-min-max <readability/use-std-min-max>`, "Yes"
:doc:`zircon-temporary-objects <zircon/temporary-objects>`,
-Check aliases
--------------
-.. csv-table::
+.. csv-table:: Aliases..
:header: "Name", "Redirect", "Offers fixes"
:doc:`bugprone-narrowing-conversions <bugprone/narrowing-conversions>`,
:doc:`cppcoreguidelines-narrowing-conversions
<cppcoreguidelines/narrowing-conversions>`,
:doc:`cert-con36-c <cert/con36-c>`,
:doc:`bugprone-spuriously-wake-up-functions
<bugprone/spuriously-wake-up-functions>`,
:doc:`cert-con54-cpp <cert/con54-cpp>`,
:doc:`bugprone-spuriously-wake-up-functions
<bugprone/spuriously-wake-up-functions>`,
+ :doc:`cert-ctr56-cpp <cert/ctr56-cpp>`,
:doc:`bugprone-pointer-arithmetic-on-polymorphic-object
<bugprone/pointer-arithmetic-on-polymorphic-object>`,
:doc:`cert-dcl03-c <cert/dcl03-c>`, :doc:`misc-static-assert
<misc/static-assert>`, "Yes"
:doc:`cert-dcl16-c <cert/dcl16-c>`,
:doc:`readability-uppercase-literal-suffix
<readability/uppercase-literal-suffix>`, "Yes"
:doc:`cert-dcl37-c <cert/dcl37-c>`, :doc:`bugprone-reserved-identifier
<bugprone/reserved-identifier>`, "Yes"
diff --git
a/clang-tools-extra/test/clang-tidy/checkers/bugprone/incorrect-iterators.cpp
b/clang-tools-extra/test/clang-tidy/checkers/bugprone/incorrect-iterators.cpp
new file mode 100644
index 0000000000000..6a0b3700ff127
--- /dev/null
+++
b/clang-tools-extra/test/clang-tidy/checkers/bugprone/incorrect-iterators.cpp
@@ -0,0 +1,156 @@
+// RUN: %check_clang_tidy -std=c++14 %s bugprone-incorrect-iterators %t
+
+namespace std {
+namespace execution {
+class parallel_policy {};
+constexpr parallel_policy par;
+} // namespace execution
+
+template <typename BiDirIter> class reverse_iterator {
+ constexpr explicit reverse_iterator(BiDirIter Iter);
+};
+
+template <typename BiDirIter>
+reverse_iterator<BiDirIter> make_reverse_iterator(BiDirIter Iter);
+
+template <typename T> class vector {
+public:
+ using iterator = T *;
+ using const_iterator = const T *;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using reverse_const_iterator = std::reverse_iterator<const_iterator>;
+
+ constexpr const_iterator begin() const;
+ constexpr const_iterator end() const;
+ constexpr const_iterator cbegin() const;
+ constexpr const_iterator cend() const;
+ constexpr iterator begin();
+ constexpr iterator end();
+ constexpr reverse_const_iterator rbegin() const;
+ constexpr reverse_const_iterator rend() const;
+ constexpr reverse_const_iterator crbegin() const;
+ constexpr reverse_const_iterator crend() const;
+ constexpr reverse_iterator rbegin();
+ constexpr reverse_iterator rend();
+
+ template <class InputIt>
+ iterator insert(const_iterator pos, InputIt first, InputIt last);
+};
+
+template <typename Container> constexpr auto begin(const Container &Cont) {
+ return Cont.begin();
+}
+
+template <typename Container> constexpr auto begin(Container &Cont) {
+ return Cont.begin();
+}
+
+template <typename Container> constexpr auto end(const Container &Cont) {
+ return Cont.end();
+}
+
+template <typename Container> constexpr auto end(Container &Cont) {
+ return Cont.end();
+}
+
+template <typename Container> constexpr auto cbegin(const Container &Cont) {
+ return Cont.cbegin();
+}
+
+template <typename Container> constexpr auto cend(const Container &Cont) {
+ return Cont.cend();
+}
+
+template <typename Container> constexpr auto rbegin(const Container &Cont) {
+ return Cont.rbegin();
+}
+
+template <typename Container> constexpr auto rbegin(Container &Cont) {
+ return Cont.rbegin();
+}
+
+template <typename Container> constexpr auto rend(const Container &Cont) {
+ return Cont.rend();
+}
+
+template <typename Container> constexpr auto rend(Container &Cont) {
+ return Cont.rend();
+}
+
+template <typename Container> constexpr auto crbegin(const Container &Cont) {
+ return Cont.crbegin();
+}
+
+template <typename Container> constexpr auto crend(const Container &Cont) {
+ return Cont.crend();
+}
+// Find
+template <class InputIt, class T>
+InputIt find(InputIt first, InputIt last, const T &value);
+
+template <class Policy, class InputIt, class T>
+InputIt find(Policy &&policy, InputIt first, InputIt last, const T &value);
+
+// Reverse
+template <typename Iter> void reverse(Iter begin, Iter end);
+
+// Includes
+template <class InputIt1, class InputIt2>
+bool includes(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2
last2);
+
+// IsPermutation
+template <class ForwardIt1, class ForwardIt2>
+bool is_permutation(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2);
+template <class ForwardIt1, class ForwardIt2>
+bool is_permutation(ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2,
+ ForwardIt2 last2);
+
+// Equal
+template <class InputIt1, class InputIt2>
+bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2);
+
+template <class InputIt1, class InputIt2>
+bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2);
+
+template <class InputIt1, class InputIt2, class BinaryPred>
+bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
+ BinaryPred p) {
+ // Need a definition to suppress undefined_internal_type when invoked with
+ // lambda
+ return true;
+}
+
+template <class ForwardIt, class T>
+void iota(ForwardIt first, ForwardIt last, T value);
+
+template <class ForwardIt>
+ForwardIt rotate(ForwardIt first, ForwardIt middle, ForwardIt last);
+
+} // namespace std
+
+void Test() {
+ std::vector<int> I;
+ std::vector<int> J;
+ std::find(I.end(), I.begin(), 0);
+ // CHECK-NOTES: [[@LINE-1]]:13: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: [[@LINE-2]]:22: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ std::find(std::execution::par, I.begin(), J.end(), 0);
+ // CHECK-NOTES: [[@LINE-1]]:3: warning: mismatched ranges pass to function
+ // CHECK-NOTES: [[@LINE-2]]:34: note: first range passed here to begin
+ // CHECK-NOTES: [[@LINE-3]]:45: note: different range passed here to end
+ std::find(std::make_reverse_iterator(I.end()),
+ std::make_reverse_iterator(I.end()), 0);
+ // CHECK-NOTES: [[@LINE-1]]:40: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: [[@LINE-2]]:13: note: 'make_reverse_iterator<int *>' changes
'end' into a 'begin' iterator
+ std::find(I.rbegin(), std::make_reverse_iterator(J.begin()), 0);
+ // CHECK-NOTES: [[@LINE-1]]:3: warning: mismatched ranges pass to function
+ // CHECK-NOTES: [[@LINE-2]]:13: note: first range passed here to begin
+ // CHECK-NOTES: [[@LINE-3]]:52: note: different range passed here to end
+
+ I.insert(J.begin(), J.end(), J.begin());
+ // CHECK-NOTES: [[@LINE-1]]:12: warning: 'insert<int *>' called with an
iterator for a different container
+ // CHECK-NOTES: [[@LINE-2]]:3: note: container is specified here
+ // CHECK-NOTES: [[@LINE-3]]:12: note: different container provided here
+ // CHECK-NOTES: [[@LINE-4]]:23: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: [[@LINE-5]]:32: warning: 'begin' iterator supplied where an
'end' iterator is expected
+}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
