https://github.com/njames93 updated
https://github.com/llvm/llvm-project/pull/99917
>From d0cf6a5250f78d03eaf793035c58e3afc37e0788 Mon Sep 17 00:00:00 2001
From: Nathan James <n.jame...@hotmail.co.uk>
Date: Tue, 23 Jul 2024 10:59:45 +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 | 1214 +++++++++++++++++
.../bugprone/IncorrectIteratorsCheck.h | 45 +
clang-tools-extra/docs/ReleaseNotes.rst | 6 +
.../checks/bugprone/incorrect-iterators.rst | 144 ++
.../docs/clang-tidy/checks/list.rst | 1 +
.../checkers/bugprone/incorrect-iterators.cpp | 437 ++++++
8 files changed, 1851 insertions(+)
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..611fb70728eda
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.cpp
@@ -0,0 +1,1214 @@
+//===--- 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/ASTContext.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/ASTMatchersInternal.h"
+#include "clang/ASTMatchers/ASTMatchersMacros.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/Basic/LangOptions.h"
+#include "clang/Basic/SourceLocation.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"
+#include "llvm/Support/ErrorHandling.h"
+#include <functional>
+#include <optional>
+
+using namespace clang::ast_matchers;
+
+namespace clang::tidy::bugprone {
+
+namespace {
+using SVU = llvm::SmallVector<unsigned, 3>;
+/// Checks to see if a all the parameters of a template function with a given
+/// index refer to the same type.
+AST_MATCHER_P(FunctionDecl, areParametersSameTemplateType, SVU, Indexes) {
+ const FunctionTemplateDecl *TemplateDecl = Node.getPrimaryTemplate();
+ if (!TemplateDecl)
+ return false;
+ const FunctionDecl *FuncDecl = TemplateDecl->getTemplatedDecl();
+ if (!FuncDecl)
+ return false;
+ assert(!Indexes.empty());
+ if (llvm::any_of(Indexes, [Count(FuncDecl->getNumParams())](unsigned Index) {
+ return Index >= Count;
+ }))
+ return false;
+ const ParmVarDecl *FirstParam = FuncDecl->getParamDecl(Indexes.front());
+ if (!FirstParam)
+ return false;
+ QualType Type = FirstParam->getOriginalType();
+ for (auto Item : llvm::drop_begin(Indexes)) {
+ const ParmVarDecl *Param = FuncDecl->getParamDecl(Item);
+ if (!Param)
+ return false;
+ if (Param->getOriginalType() != Type)
+ return false;
+ }
+ return true;
+}
+
+AST_MATCHER_P(FunctionDecl, isParameterTypeUnique, unsigned, Index) {
+ const FunctionTemplateDecl *TemplateDecl = Node.getPrimaryTemplate();
+ if (!TemplateDecl)
+ return false;
+ const FunctionDecl *FuncDecl = TemplateDecl->getTemplatedDecl();
+ if (!FuncDecl)
+ return false;
+ if (Index >= FuncDecl->getNumParams())
+ return false;
+ const ParmVarDecl *MainParam = FuncDecl->getParamDecl(Index);
+ if (!MainParam)
+ return false;
+ QualType Type = MainParam->getOriginalType();
+ for (unsigned I = 0, E = FuncDecl->getNumParams(); I != E; ++I) {
+ if (I == Index)
+ continue;
+ const ParmVarDecl *Param = FuncDecl->getParamDecl(I);
+ if (!Param)
+ continue;
+ if (Param->getOriginalType() == Type)
+ return false;
+ }
+ return true;
+}
+
+AST_MATCHER(Expr, isNegativeIntegerConstant) {
+ if (auto Res = Node.getIntegerConstantExpr(Finder->getASTContext()))
+ return Res->isNegative();
+ return false;
+}
+
+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;
+};
+
+struct PairOverload {
+ unsigned Begin;
+ unsigned End;
+ bool IsActive = true;
+};
+
+struct PairMethods {
+
+ StringRef Name;
+ SmallVector<PairOverload, 1> Indexes;
+};
+
+struct InternalMethods {
+ struct Indexes {
+ unsigned Index;
+ bool IsActive = true;
+ };
+ StringRef Name;
+ SmallVector<Indexes, 2> Indexes;
+};
+
+struct Descriptor {
+ SmallVector<PairMethods> Ranges;
+ SmallVector<InternalMethods> Internal;
+ SmallVector<PairOverload, 1> Constructor;
+};
+
+struct AllowedContainer {
+ StringRef Name;
+ bool IsActive = true;
+};
+} // 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 constexpr char OutputRangeEnd[] = "OutputRangeEnd";
+static constexpr char OutputRangeBegin[] = "OutputRangeBegin";
+static constexpr char UnexpectedDec[] = "UndexpectedDec";
+static constexpr char UnexpectedInc[] = "UnexpectedInc";
+static constexpr char UnexpectedIncDecExpr[] = "UnexpectedIncDecExpr";
+static constexpr char TriRangeArgBegin[] = "TriRangeArgBegin";
+static constexpr char TriRangeArgEnd[] = "TriRangeArgEnd";
+static constexpr char TriRangeArgExpr[] = "TriRangeArgExpr";
+
+static auto
+makeExprMatcher(ast_matchers::internal::Matcher<Expr> ArgumentMatcher,
+ const NameMatchers &Names, ArrayRef<StringRef> MakeReverse,
+ const NameMatchers &RevNames, StringRef RevBind) {
+ auto MakeMatcher = [&ArgumentMatcher](const NameMatchers &Names) {
+ return anyOf(
+ cxxMemberCallExpr(argumentCountIs(0),
+ callee(cxxMethodDecl(hasAnyName(Names.MethodNames))),
+ on(ArgumentMatcher)),
+ callExpr(argumentCountIs(1),
+ hasDeclaration(functionDecl(hasAnyName(Names.FreeNames))),
+ hasArgument(0, ArgumentMatcher)));
+ };
+ return expr(anyOf(MakeMatcher(Names),
+ callExpr(argumentCountIs(1),
+ callee(functionDecl(hasAnyName(MakeReverse))),
+ hasArgument(0, MakeMatcher(RevNames)))
+ .bind(RevBind)));
+}
+
+/// Detects a range function where the argument for the begin call differs from
+/// the end call
+/// @code
+/// std::find(I.begin(), J.end());
+/// @endcode
+static auto makeRangeArgMismatch(unsigned BeginExpected, unsigned EndExpected,
+ NamePairs Forward, NamePairs Reverse,
+ ArrayRef<StringRef> MakeReverse) {
+
+ auto MakeMatcher = [&MakeReverse, &BeginExpected,
+ &EndExpected](auto Primary, auto Backwards) {
+ return allOf(
+ 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 allOf(
+ argumentCountAtLeast(std::max(BeginExpected, EndExpected) + 1),
+ anyOf(MakeMatcher(Forward, Reverse), MakeMatcher(Reverse, Forward)));
+}
+
+/// Detects a range function where we expect a call to begin but get a call to
+/// end or vice versa
+/// @code
+/// std::find(X.end(), X.end());
+/// @endcode
+/// First argument likely should be begin
+static auto makeUnexpectedBeginEndMatcher(unsigned Index, StringRef BindTo,
+ NameMatchers Names,
+ ArrayRef<StringRef> MakeReverse,
+ const NameMatchers &RevNames) {
+ return 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 eachOf(makeUnexpectedBeginEndMatcher(
+ BeginExpected, ArgMismatchBegin, BeginEndPairs.EndNames,
+ MakeReverse, BeginEndPairs.BeginNames),
+ makeUnexpectedBeginEndMatcher(
+ EndExpected, ArgMismatchEnd, BeginEndPairs.BeginNames,
+ MakeReverse, BeginEndPairs.EndNames));
+}
+
+static auto makePairRangeMatcherInternal(
+ ast_matchers::internal::Matcher<NamedDecl> NameMatcher,
+ unsigned BeginExpected, unsigned EndExpected, const FullState &State) {
+ return callExpr(
+ callee(functionDecl(
+ areParametersSameTemplateType({BeginExpected, EndExpected}),
+ std::move(NameMatcher))),
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected, State.Forward,
+ State.Reversed, State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator)));
+}
+
+static auto make3RangeMatcherInternal(ArrayRef<StringRef> FuncNames,
+ unsigned BeginExpected,
+ unsigned MiddleExpected,
+ unsigned EndExpected,
+ const FullState &State) {
+ return callExpr(
+ callee(
+ functionDecl(areParametersSameTemplateType(
+ {BeginExpected, EndExpected,
MiddleExpected}),
+ hasAnyName(FuncNames))),
+ eachOf(
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected,
+ State.Forward, State.Reversed,
+ State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator)),
+ anyOf(allOf(hasArgument(
+ MiddleExpected,
+ makeExprMatcher(expr().bind(TriRangeArgExpr),
+ State.Forward.BeginNames,
+ State.MakeReverseIterator,
+ State.Reversed.EndNames,
+ ArgMismatchRevBind)
+ .bind(TriRangeArgBegin)),
+ hasArgument(
+ EndExpected,
+ makeExprMatcher(
+ matchers::isStatementIdenticalToBoundNode(
+ TriRangeArgExpr),
+ State.Forward.EndNames,
+ State.MakeReverseIterator,
+ State.Reversed.BeginNames, ""))),
+ allOf(hasArgument(
+ MiddleExpected,
+ makeExprMatcher(expr().bind(TriRangeArgExpr),
+ State.Forward.EndNames,
+ State.MakeReverseIterator,
+ State.Reversed.BeginNames,
+ ArgMismatchRevBind)
+ .bind(TriRangeArgEnd)),
+ hasArgument(
+ BeginExpected,
+ makeExprMatcher(
+ matchers::isStatementIdenticalToBoundNode(
+ TriRangeArgExpr),
+ State.Forward.BeginNames,
+ State.MakeReverseIterator,
+ State.Reversed.EndNames, ""))))))
+ .bind(Callee);
+}
+
+/// The full matcher for functions that take a range with 2 arguments
+static auto makePairRangeMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned BeginExpected, unsigned EndExpected,
+ const FullState &State) {
+ return makePairRangeMatcherInternal(hasAnyName(FuncNames), BeginExpected,
+ EndExpected, State)
+ .bind(Callee);
+}
+
+static auto makeHalfOpenMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned BeginExpected, unsigned PotentialEnd,
+ const FullState &State) {
+ auto NameMatcher = hasAnyName(FuncNames);
+ return callExpr(
+ anyOf(makePairRangeMatcherInternal(NameMatcher, BeginExpected,
+ PotentialEnd, State),
+ allOf(callee(functionDecl(NameMatcher,
isParameterTypeUnique(
+ BeginExpected))),
+ makeUnexpectedBeginEndMatcher(
+ BeginExpected, ArgMismatchBegin,
+ State.Combined.EndNames,
State.MakeReverseIterator,
+ State.Combined.BeginNames))))
+ .bind(Callee);
+}
+
+/// Detects if a function has a policy for the first argument.
+/// If no policy detected, runs @param F matcher with the expected index,
+/// otherwise rungs @param F matcher with expected index + 1 to account for the
+/// the policy argument
+template <typename Func, typename... Args>
+auto runWithPolicy1(ArrayRef<StringRef> FuncNames, unsigned Expected, Func F,
+ Args &&...A) {
+ return callExpr(anyOf(
+ allOf(callee(functionDecl(areParametersSameTemplateType({0, 1}))),
+ F(FuncNames, Expected, std::forward<Args>(A)...)),
+ allOf(callee(functionDecl(unless(areParametersSameTemplateType({0,
1})))),
+ F(FuncNames, Expected + 1, std::forward<Args>(A)...))));
+}
+
+/// Like @c runWithPolicy1 only it handles 2 arguments
+template <typename Func, typename... Args>
+auto runWithPolicy2(ArrayRef<StringRef> FuncNames, unsigned BeginExpected,
+ unsigned EndExpected, Func F, Args &&...A) {
+ return callExpr(anyOf(
+ allOf(callee(functionDecl(areParametersSameTemplateType({0, 1}))),
+ F(FuncNames, BeginExpected, EndExpected,
std::forward<Args>(A)...)),
+ allOf(callee(functionDecl(unless(areParametersSameTemplateType({0,
1})))),
+ F(FuncNames, BeginExpected + 1, EndExpected + 1,
+ std::forward<Args>(A)...))));
+}
+
+/// Like @c runWithPolicy1 only it handles 2 arguments
+template <typename Func, typename... Args>
+auto runWithPolicy3(ArrayRef<StringRef> FuncNames, unsigned BeginExpected,
+ unsigned MiddleExpected, unsigned EndExpected, Func F,
+ Args &&...A) {
+ return callExpr(anyOf(
+ allOf(callee(functionDecl(areParametersSameTemplateType({0, 1}))),
+ F(FuncNames, BeginExpected, MiddleExpected, EndExpected,
+ std::forward<Args>(A)...)),
+ allOf(callee(functionDecl(unless(areParametersSameTemplateType({0,
1})))),
+ F(FuncNames, BeginExpected + 1, MiddleExpected + 1, EndExpected +
1,
+ std::forward<Args>(A)...))));
+}
+
+static auto makeNamedExpectedBeginFullMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned ExpectedIndex,
+ const FullState &State,
+ StringRef BindTo) {
+ return callExpr(argumentCountAtLeast(ExpectedIndex + 1),
+ callee(functionDecl(isParameterTypeUnique(ExpectedIndex),
+ hasAnyName(FuncNames))),
+ makeUnexpectedBeginEndMatcher(
+ ExpectedIndex, BindTo, State.Combined.EndNames,
+ State.MakeReverseIterator, State.Combined.BeginNames))
+ .bind(Callee);
+}
+
+/// Detects calls where a single output iterator is expected, yet an end of
+/// container input is supplied Usually these arguments would be supplied with
+/// things like `std::back_inserter`
+static auto makeExpectedOutputFullMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned ExpectedIndex,
+ const FullState &State) {
+ return makeNamedExpectedBeginFullMatcher(FuncNames, ExpectedIndex, State,
+ OutputRangeEnd);
+}
+
+/// Detects calls where a begin iterator is expected, yet an end of container
is
+/// supplied.
+static auto makeExpectedBeginFullMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned ExpectedIndex,
+ const FullState &State) {
+ return makeNamedExpectedBeginFullMatcher(FuncNames, ExpectedIndex, State,
+ ArgMismatchBegin);
+}
+
+/// Detects calls where an end iterator is expected, yet a begin of container
is
+/// supplied.
+static auto makeExpectedEndFullMatcher(ArrayRef<StringRef> FuncNames,
+ unsigned ExpectedIndex,
+ const FullState &State) {
+ return callExpr(argumentCountAtLeast(ExpectedIndex + 1),
+ callee(functionDecl(isParameterTypeUnique(ExpectedIndex),
+ hasAnyName(FuncNames))),
+ makeUnexpectedBeginEndMatcher(ExpectedIndex,
OutputRangeBegin,
+ State.Combined.BeginNames,
+ State.MakeReverseIterator,
+ State.Combined.EndNames))
+ .bind(Callee);
+}
+
+/// Handles the mess of overloads that is std::transform
+static auto makeTransformArgsMatcher(ArrayRef<StringRef> FuncNames,
+ const FullState &State) {
+ auto FnMatch = callee(functionDecl(hasAnyName(FuncNames)));
+ auto MakeSubMatch = [&](bool IsPolicy) {
+ auto Offset = IsPolicy ? 1 : 0;
+ return anyOf(
+ allOf(argumentCountIs(4 + Offset), FnMatch,
+ makeUnexpectedBeginEndMatcher(
+ 2 + Offset, OutputRangeEnd, State.Combined.EndNames,
+ State.MakeReverseIterator, State.Combined.BeginNames)),
+ allOf(
+ argumentCountIs(5 + Offset), FnMatch,
+ eachOf(makeUnexpectedBeginEndMatcher(
+ 2 + Offset, ArgMismatchBegin, State.Combined.EndNames,
+ State.MakeReverseIterator, State.Combined.BeginNames),
+ makeUnexpectedBeginEndMatcher(
+ 3 + Offset, OutputRangeEnd, State.Combined.EndNames,
+ State.MakeReverseIterator,
State.Combined.BeginNames))));
+ };
+ return callExpr(anyOf(allOf(callee(functionDecl(
+ areParametersSameTemplateType({0, 1}))),
+ MakeSubMatch(false)),
+ allOf(callee(functionDecl(unless(
+ areParametersSameTemplateType({0, 1})))),
+ MakeSubMatch(true))))
+ .bind(Callee);
+}
+
+template <typename T>
+static std::optional<ast_matchers::internal::Matcher<T>>
+combineAnyOf(std::vector<ast_matchers::internal::DynTypedMatcher> &&Items) {
+ if (Items.empty())
+ return std::nullopt;
+ if (Items.size() == 1) {
+ return Items.front().convertTo<T>();
+ }
+ return ast_matchers::internal::DynTypedMatcher::constructVariadic(
+ ast_matchers::internal::DynTypedMatcher::VO_AnyOf,
+ ASTNodeKind::getFromNodeKind<T>(), std::move(Items))
+ .template convertTo<T>();
+}
+
+template <typename T>
+static std::optional<ast_matchers::internal::Matcher<T>>
+combineEachOf(std::vector<ast_matchers::internal::DynTypedMatcher> &&Items) {
+ if (Items.empty())
+ return std::nullopt;
+ if (Items.size() == 1) {
+ return Items.front().convertTo<T>();
+ }
+ return ast_matchers::internal::DynTypedMatcher::constructVariadic(
+ ast_matchers::internal::DynTypedMatcher::VO_EachOf,
+ ASTNodeKind::getFromNodeKind<T>(), std::move(Items))
+ .template convertTo<T>();
+}
+
+static std::optional<ast_matchers::internal::Matcher<CXXMemberCallExpr>>
+getContainerRangeMatchers(ArrayRef<PairMethods> Methods,
+ const FullState &State) {
+ std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+ for (auto [Name, Ranges] : Methods) {
+ for (auto [BeginExpected, EndExpected, IsActive] : Ranges) {
+ if (!IsActive)
+ continue;
+ Matchers.emplace_back(cxxMemberCallExpr(
+ callee(cxxMethodDecl(
+ areParametersSameTemplateType({BeginExpected, EndExpected}),
+ hasName(Name))),
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected, State.Forward,
+ State.Reversed,
State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator))));
+ }
+ }
+ return combineAnyOf<CXXMemberCallExpr>(std::move(Matchers));
+}
+
+static std::optional<ast_matchers::internal::Matcher<CXXMemberCallExpr>>
+getContainerInternalMatcher(InternalMethods Method, const FullState &State) {
+ std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+ for (auto [InternalExpected, IsActive] : Method.Indexes) {
+ if (!IsActive)
+ continue;
+ Matchers.emplace_back(cxxMemberCallExpr(
+ callee(cxxMethodDecl(hasParameter(
+ InternalExpected,
+ parmVarDecl(hasType(
+ elaboratedType(namesType(typedefType(hasDeclaration(namedDecl(
+ hasAnyName("const_iterator", "iterator"))))))))))),
+ hasArgument(InternalExpected,
+ makeExprMatcher(
+ expr(unless(matchers::isStatementIdenticalToBoundNode(
+ Internal)))
+ .bind(InternalOther),
+ State.All, State.MakeReverseIterator, State.All,
+ ArgMismatchRevBind)
+ .bind(InternalArgument))));
+ }
+ if (auto Combined = combineEachOf<CXXMemberCallExpr>(std::move(Matchers)))
+ return cxxMemberCallExpr(callee(cxxMethodDecl(hasName(Method.Name))),
+ std::move(*Combined));
+ return std::nullopt;
+}
+
+static std::optional<ast_matchers::internal::Matcher<CXXMemberCallExpr>>
+getContainerInternalMatchers(ArrayRef<InternalMethods> Methods,
+ const FullState &State) {
+ std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+ for (auto Method : Methods) {
+ if (auto Matcher = getContainerInternalMatcher(Method, State)) {
+ Matchers.push_back(std::move(*Matcher));
+ }
+ }
+ return combineAnyOf<CXXMemberCallExpr>(std::move(Matchers));
+}
+
+static std::optional<ast_matchers::internal::Matcher<CXXConstructExpr>>
+getContainerConstructorMatchers(ArrayRef<PairOverload> Constructors,
+ const FullState &State) {
+ std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
+ for (auto [BeginExpected, EndExpected, IsActive] : Constructors) {
+ if (!IsActive)
+ continue;
+ Matchers.emplace_back(cxxConstructExpr(
+ hasDeclaration(cxxConstructorDecl(
+ areParametersSameTemplateType({BeginExpected, EndExpected}))),
+ anyOf(makeRangeArgMismatch(BeginExpected, EndExpected, State.Forward,
+ State.Reversed, State.MakeReverseIterator),
+ makeUnexpectedBeginEndPair(BeginExpected, EndExpected,
+ State.Combined,
+ State.MakeReverseIterator))));
+ }
+ return combineAnyOf<CXXConstructExpr>(std::move(Matchers));
+}
+
+static auto registerContainerDescriptor(MatchFinder *Finder,
+ ClangTidyCheck *Check,
+ ArrayRef<AllowedContainer> Container,
+ const Descriptor &D,
+ const FullState &State) {
+ auto ContainerNames = llvm::to_vector(
+ llvm::map_range(llvm::make_filter_range(
+ Container, [](auto &Item) { return Item.IsActive; }),
+ [](auto &Item) { return Item.Name; }));
+ if (ContainerNames.empty())
+ return;
+ auto RangeMatcher = getContainerRangeMatchers(D.Ranges, State);
+ auto InternalMatcher = getContainerInternalMatchers(D.Internal, State);
+ if (RangeMatcher || InternalMatcher)
+ Finder->addMatcher(
+ cxxMemberCallExpr(
+ thisPointerType(cxxRecordDecl(hasAnyName(ContainerNames))),
+ on(expr().bind(Internal)),
+ (RangeMatcher && InternalMatcher)
+ ? eachOf(std::move(*RangeMatcher), std::move(*InternalMatcher))
+ : (RangeMatcher ? std::move(*RangeMatcher)
+ : std::move(*InternalMatcher)))
+ .bind(Callee),
+ Check);
+ if (auto Ctor = getContainerConstructorMatchers(D.Constructor, State)) {
+ Finder->addMatcher(
+ cxxConstructExpr(hasDeclaration(cxxConstructorDecl(
+ ofClass(hasAnyName(ContainerNames)))),
+ std::move(*Ctor))
+ .bind(Callee),
+ Check);
+ }
+}
+
+/// Looks for calls that advance past the end of a range or before the start of
+/// a range.
+static auto makeUnexpectedIncDecMatcher(const FullState &State, bool IsInc) {
+ auto Arg =
+ makeExprMatcher(
+ expr(), IsInc ? State.Combined.EndNames : State.Combined.BeginNames,
+ State.MakeReverseIterator,
+ IsInc ? State.Combined.BeginNames : State.Combined.EndNames,
+ ArgMismatchRevBind)
+ .bind(UnexpectedIncDecExpr);
+ return expr(
+ anyOf(
+ callExpr(
+ argumentCountAtLeast(1),
+ anyOf(
+ allOf(
+ anyOf(unless(hasArgument(1, anything())),
+ hasArgument(
+ 1,
unless(isNegativeIntegerConstant()))),
+ callee(functionDecl(hasName(
+ IsInc ? "::std::next" : "::std::prev")))),
+ allOf(hasArgument(1, isNegativeIntegerConstant()),
+ callee(functionDecl(hasName(
+ IsInc ? "::std::prev" : "::std::next"))))),
+ hasArgument(0, Arg)),
+ mapAnyOf(binaryOperator, cxxOperatorCallExpr)
+ .with(anyOf(
+ allOf(hasOperatorName(IsInc ? "+" : "-"), hasLHS(Arg),
+ hasRHS(
+ allOf(hasType(isInteger()),
+
unless(isNegativeIntegerConstant())))),
+ allOf(hasOperatorName(IsInc ? "-" : "+"), hasLHS(Arg),
+ hasRHS(allOf(hasType(isInteger()),
+ isNegativeIntegerConstant()))))),
+ cxxMemberCallExpr(
+ anyOf(
+ allOf(
+ hasArgument(
+ 0, allOf(hasType(isInteger()),
+
unless(isNegativeIntegerConstant()))),
+ callee(cxxMethodDecl(
+ hasName(IsInc ? "operator+" : "operator-")))),
+ allOf(
+ hasArgument(0, allOf(hasType(isInteger()),
+
isNegativeIntegerConstant())),
+ callee(cxxMethodDecl(
+ hasName(IsInc ? "operator-" :
"operator+"))))),
+ on(Arg))))
+ .bind(IsInc ? UnexpectedInc : UnexpectedDec);
+}
+
+void prependStdPrefix(llvm::MutableArrayRef<std::string> Items) {
+ static constexpr llvm::StringLiteral Prefix = "::std::";
+ llvm::for_each(Items, [](std::string &Item) {
+ Item.insert(0, Prefix.data(), Prefix.size());
+ });
+}
+
+/// Gets functions that a range and an output iterator to the end of another
+/// range
+static std::vector<std::string>
+getSingleRangeWithRevOutputIterator(const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{"copy_backward"});
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result, std::array{"move_backward"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
+getSingleRangeWithHalfOpen(const LangOptions & /* LangOpts */) {
+ std::vector<std::string> Result{{"inner_product"}};
+ prependStdPrefix(Result);
+ return Result;
+}
+
+/// Gets functions that take 2 whole ranges and optionally start with a policy
+static std::vector<std::string>
+getMultiRangePolicyFunctors(const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{"find_end", "find_first_of", "search",
+ "includes",
"lexicographical_compare"});
+ if (LangOpts.CPlusPlus20)
+ llvm::append_range(Result,
std::array{"lexicographical_compare_three_way"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+/// Gets a function that takes 2 ranges where the second may be specified by
+/// just a start iterator or a start/end pair, The range may optionally start
+/// with a policy
+static std::vector<std::string> getMultiRangePolicyPotentiallyHalfOpenFunctors(
+ const LangOptions & /* LangOpts */) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{"mismatch", "equal"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
+getMultiRangePotentiallyHalfOpenFunctors(const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result, std::array{"is_permutation"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string> getMultiRangePolicyWithSingleOutputIterator(
+ const LangOptions & /* LangOpts */) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{"set_union", "set_intersection",
+ "set_difference",
+ "set_symmetric_difference", "merge"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+// Returns a vector of function that take a range in the first and second
+// arguments
+static std::vector<std::string>
+getSingleRangeFunctors(const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ if (LangOpts.CPlusPlus17)
+ llvm::append_range(Result, std::array{"sample"});
+ else
+ llvm::append_range(Result, std::array{"random_shuffle"});
+
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result,
+ std::array{"shuffle", "partition_point", "iota"});
+
+ llvm::append_range(Result, std::array{
+ "lower_bound",
+ "upper_bound",
+ "equal_range",
+ "binary_search",
+ "push_heap",
+ "pop_heap",
+ "make_heap",
+ "sort_heap",
+ "next_permutation",
+ "prev_permutation",
+ "accumulate",
+ });
+ prependStdPrefix(Result);
+ return Result;
+}
+
+// Returns a vector of function that take a range in the first and second or
+// second and third arguments
+static std::vector<std::string>
+getSingleRangePolicyFunctors(const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result, std::array{
+ "all_of",
+ "any_of",
+ "none_of",
+ "is_partitioned",
+ "is_sorted",
+ "is_sorted_until",
+ "is_heap",
+ "is_heap_until",
+ "minmax_element",
+ });
+
+ if (LangOpts.CPlusPlus17)
+ llvm::append_range(Result,
+ std::array{"reduce", "uninitialized_default_construct",
+ "uninitialized_value_construct", "destroy"});
+ if (LangOpts.CPlusPlus20)
+ llvm::append_range(Result, std::array{"shift_left", "shift_right"});
+
+ llvm::append_range(Result, std::array{
+ "find",
+ "find_if",
+ "find_if_not",
+ "adjacent_find",
+ "count",
+ "count_if",
+ "search_n",
+ "replace",
+ "replace_if",
+ "fill",
+ "generate",
+ "remove_if",
+ "unique",
+ "reverse",
+ "partition",
+ "stable_partition",
+ "sort",
+ "stable_sort",
+ "max_element",
+ "min_element",
+ "uninitialized_fill",
+ });
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
+getSingleRangePolicyWithSingleOutputIteratorFunctions(
+ const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result,
+ std::array{"copy", "copy_if", "move", "swap_ranges"});
+ if (LangOpts.CPlusPlus17)
+ llvm::append_range(
+ Result, std::array{"exclusive_scan", "inclusive_scan",
+ "transform_reduce", "transform_exclusive_scan",
+ "transform_inclusive_scan", "uninitialized_move"});
+ llvm::append_range(Result,
+ std::array{"replace_copy", "replace_copy_if",
+ "remove_copy_if", "unique_copy",
"reverse_copy",
+ "adjacent_difference", "uninitialized_copy"
+
+ });
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
+getSingleRangePolicyWithTwoOutputIteratorFunctions(
+ const LangOptions &LangOpts) {
+ std::vector<std::string> Result;
+ if (LangOpts.CPlusPlus11)
+ llvm::append_range(Result, std::array{"partition_copy"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
getSingleRangeWithSingleOutputIteratorFunctions(
+ const LangOptions & /* LangOpts */) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{
+ "partial_sum",
+ });
+ prependStdPrefix(Result);
+ return Result;
+}
+
+static std::vector<std::string>
+getTriRangePolicyFunctions(const LangOptions & /* LangOpts */) {
+ std::vector<std::string> Result;
+ llvm::append_range(Result, std::array{"rotate", "nth_element",
+ "inplace_merge", "partial_sort"});
+ prependStdPrefix(Result);
+ return Result;
+}
+
+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};
+ auto SingleRange = getSingleRangeFunctors(getLangOpts());
+ auto SingleRangePolicy = getSingleRangePolicyFunctors(getLangOpts());
+ auto SingleRangePolicyOutput =
+ getSingleRangePolicyWithSingleOutputIteratorFunctions(getLangOpts());
+ auto SingleRangePolicyTwoOutput =
+ getSingleRangePolicyWithTwoOutputIteratorFunctions(getLangOpts());
+ auto SingleRangeWithOutput =
+ getSingleRangeWithSingleOutputIteratorFunctions(getLangOpts());
+ auto SingleRangeHalfOpen = getSingleRangeWithHalfOpen(getLangOpts());
+ auto SingleRangeBackwardsHalf =
+ getSingleRangeWithRevOutputIterator(getLangOpts());
+ auto MultiRangePolicy = getMultiRangePolicyFunctors(getLangOpts());
+ auto MultiRangePolicyPotentiallyHalfOpen =
+ getMultiRangePolicyPotentiallyHalfOpenFunctors(getLangOpts());
+ auto MultiRangePotentiallyHalfOpen =
+ getMultiRangePotentiallyHalfOpenFunctors(getLangOpts());
+ auto MultiRangePolicySingleOutputIterator =
+ getMultiRangePolicyWithSingleOutputIterator(getLangOpts());
+
+ auto TriRangePolicy = getTriRangePolicyFunctions(getLangOpts());
+
+ std::vector<std::string> TriRangePolicyOutput = {{"::std::rotate_copy"}};
+
+ // Doesn't really fit into any of the other categories.
+ // Can be ran under a polict and takes a full range with an output iterator,
+ // or a full range, range begin and output iterator.
+ std::vector<std::string> Transform = {{"::std::transform"}};
+
+ static const auto ToRefs =
+
[](std::initializer_list<std::reference_wrapper<std::vector<std::string>>>
+ Items) {
+ std::vector<StringRef> Result;
+ for (const auto &Item : Items)
+ llvm::append_range(Result, Item.get());
+ return Result;
+ };
+
+ Finder->addMatcher(
+ makePairRangeMatcher(
+ ToRefs({SingleRange, SingleRangeWithOutput, SingleRangeHalfOpen,
+ SingleRangeBackwardsHalf, MultiRangePotentiallyHalfOpen
+
+ }),
+ 0, 1, State),
+ this);
+
+ Finder->addMatcher(
+ runWithPolicy2(ToRefs({SingleRangePolicy, SingleRangePolicyOutput,
+ SingleRangePolicyTwoOutput, MultiRangePolicy,
+ MultiRangePolicyPotentiallyHalfOpen, Transform,
+ MultiRangePolicySingleOutputIterator}),
+ 0, 1, makePairRangeMatcher, State),
+ this);
+
+ Finder->addMatcher(
+ makeExpectedBeginFullMatcher(ToRefs({SingleRangeHalfOpen}), 2, State),
+ this);
+
+ Finder->addMatcher(
+ makeExpectedOutputFullMatcher(ToRefs({SingleRangeWithOutput}), 2, State),
+ this);
+ Finder->addMatcher(runWithPolicy1(ToRefs({SingleRangePolicyOutput,
+ SingleRangePolicyTwoOutput}),
+ 2, makeExpectedOutputFullMatcher, State),
+ this);
+ Finder->addMatcher(
+ runWithPolicy1(ToRefs({SingleRangePolicyTwoOutput,
TriRangePolicyOutput}),
+ 3, makeExpectedOutputFullMatcher, State),
+ this);
+ Finder->addMatcher(
+ makeExpectedEndFullMatcher(ToRefs({SingleRangeBackwardsHalf}), 2, State),
+ this);
+ Finder->addMatcher(runWithPolicy2(ToRefs({MultiRangePolicy}), 2, 3,
+ makePairRangeMatcher, State),
+ this);
+ Finder->addMatcher(
+ makeHalfOpenMatcher(ToRefs({MultiRangePotentiallyHalfOpen}), 2, 3,
State),
+ this);
+ Finder->addMatcher(
+ runWithPolicy2(ToRefs({MultiRangePolicyPotentiallyHalfOpen,
+ MultiRangePolicySingleOutputIterator}),
+ 2, 3, makeHalfOpenMatcher, State),
+ this);
+
+ Finder->addMatcher(
+ runWithPolicy1(ToRefs({MultiRangePolicySingleOutputIterator}), 4,
+ makeExpectedOutputFullMatcher, State),
+ this);
+
+ Finder->addMatcher(makeTransformArgsMatcher(ToRefs({Transform}), State),
+ this);
+
+ for (bool IsInc : {true, false})
+ Finder->addMatcher(makeUnexpectedIncDecMatcher(State, IsInc), this);
+
+ Finder->addMatcher(
+ runWithPolicy3(ToRefs({TriRangePolicy, TriRangePolicyOutput}), 0, 1, 2,
+ &make3RangeMatcherInternal, State),
+ this);
+
+ registerContainerDescriptor(
+ Finder, this, {{"::std::vector"}, {"::std::list"}, {"::std::deque"}},
+ Descriptor{
+ {
+ {"insert", {{1, 2}}},
+ {"assign", {{0, 1}}},
+ },
+ {{
+ {"insert", {{0}}},
+ {"emplace", {{0, static_cast<bool>(getLangOpts().CPlusPlus11)}}},
+ {"erase", {{0}, {1}}},
+ {"insert_range",
+ {{0, static_cast<bool>(getLangOpts().CPlusPlus23)}}},
+ }},
+ {{0, 1}}},
+ State);
+
+ registerContainerDescriptor(
+ Finder, this,
+ {{"::std:::forward_list", static_cast<bool>(getLangOpts().CPlusPlus11)}},
+ Descriptor{{
+ {"insert_after", {{1, 2}}},
+ {"assign", {{0, 1}}},
+
+ // FIXME: We should be enforcing that the container arg
+ // for these is the same as the second arg for the call
+ {"splice_after", {{2, 3}}},
+ },
+ {{
+ {"insert_after", {{0}}},
+ {"emplace_after", {{0}}},
+ {"erase_after", {{0}, {1}}},
+ {"splice_after", {{0}}},
+ {"insert_range_after",
+ {{0, static_cast<bool>(getLangOpts().CPlusPlus23)}}},
+ }},
+ {{0, 1}}},
+ State);
+
+ registerContainerDescriptor(
+ Finder, this, {{"::std::basic_string"}},
+ Descriptor{{
+ {"insert", {{1, 2}}},
+ {"append", {{0, 1}}},
+ {"assign", {{0, 1}}},
+ },
+ {{
+ {"insert", {{0}}},
+ {"erase", {{0}, {1}}},
+ {"insert_range",
+ {{0, static_cast<bool>(getLangOpts().CPlusPlus23)}}},
+ }},
+ {{0, 1}}},
+ State);
+
+ registerContainerDescriptor(
+ Finder, this,
+ {{"::std::set"},
+ {"::std::multiset"},
+ {"::std::unordered_set", static_cast<bool>(getLangOpts().CPlusPlus11)},
+ {"::std::unordered_multiset",
+ static_cast<bool>(getLangOpts().CPlusPlus11)},
+ {"::std::multimap"},
+ {"::std::unordered_multimap",
+ static_cast<bool>(getLangOpts().CPlusPlus11)}},
+ {{{"insert", {{0, 1}}}},
+ {{"insert", {{0}}},
+ {"emplace_hint", {{0, static_cast<bool>(getLangOpts().CPlusPlus11)}}},
+ {"erase", {{0}, {1}}},
+ {"extract", {{0, static_cast<bool>(getLangOpts().CPlusPlus17)}}}},
+ {{0, 1}}},
+ State);
+
+ registerContainerDescriptor(
+ Finder, this,
+ {{"::std::map"},
+ {"::std::unordered_map", static_cast<bool>(getLangOpts().CPlusPlus11)}},
+ {{{"insert", {{0, 1}}}},
+ {{"insert", {{0}}},
+ {"insert_or_assign",
+ {{0, static_cast<bool>(getLangOpts().CPlusPlus17)}}},
+ {"emplace_hint", {{0, static_cast<bool>(getLangOpts().CPlusPlus11)}}},
+ {"try_emplace", {{0, static_cast<bool>(getLangOpts().CPlusPlus17)}}},
+ {"erase", {{0}, {1}}},
+ {"extract", {{0, static_cast<bool>(getLangOpts().CPlusPlus17)}}}},
+ {{0, 1}}},
+ State);
+
+ registerContainerDescriptor(
+ Finder, this,
+ {{"::std::stack"}, {"::std::queue"}, {"::std::priority_queue"}},
+ {{}, {}, {{0, 1}}}, State);
+}
+
+static constexpr char MismatchedRangeNote[] =
+ "%select{|different }0range passed as the %select{begin|end}0 iterator";
+
+void IncorrectIteratorsCheck::check(const MatchFinder::MatchResult &Result) {
+ auto AddRevNote = [&Result, this](bool IsBegin) {
+ if (const auto *Rev =
+ Result.Nodes.getNodeAs<CallExpr>(ArgMismatchRevBind)) {
+ diag(Rev->getBeginLoc(),
+ "%0 changes '%select{end|begin}1' into %select{a 'begin|an 'end}1' "
+ "iterator",
+ DiagnosticIDs::Note)
+ << Rev->getSourceRange() << Rev->getDirectCallee() << IsBegin;
+ }
+ };
+
+ for (auto [Name, Idx] :
+ {std::pair{ArgMismatchBegin, 1}, std::pair{ArgMismatchEnd, 0},
+ std::pair{OutputRangeBegin, 0}, std::pair{OutputRangeEnd, 2}}) {
+ if (const auto *Node = Result.Nodes.getNodeAs<Expr>(Name)) {
+ diag(Node->getBeginLoc(),
+ "'%select{begin|end|end}0' iterator supplied where %select{an "
+ "'end'|a 'begin'|an output}0 iterator is expected")
+ << Idx
+ << Result.Nodes.getNodeAs<Expr>(ArgMismatchExpr)->getSourceRange();
+ AddRevNote(Idx != 0);
+ return;
+ }
+ }
+
+ if (const auto *InternalArg =
+ Result.Nodes.getNodeAs<Expr>(InternalArgument)) {
+ diag(InternalArg->getBeginLoc(),
+ "%0 called with an iterator for a different container")
+ << Result.Nodes.getNodeAs<CallExpr>(Callee)->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();
+ return;
+ }
+
+ if (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");
+ const auto *Call = Result.Nodes.getNodeAs<Expr>(Callee);
+ const auto Func = isa<CallExpr>(Call) ? cast<CallExpr>(Call)
+ ->getDirectCallee()
+ ->getQualifiedNameAsString()
+ : cast<CXXConstructExpr>(Call)
+ ->getConstructor()
+ ->getQualifiedNameAsString();
+ diag(Call->getBeginLoc(), "mismatched ranges supplied to '%0'")
+ << Func << FullRange1->getSourceRange() <<
FullRange2->getSourceRange();
+ diag(Range1->getBeginLoc(), MismatchedRangeNote, DiagnosticIDs::Note)
+ << false << FullRange1->getSourceRange();
+ diag(Range2->getBeginLoc(), MismatchedRangeNote, DiagnosticIDs::Note)
+ << true << FullRange2->getSourceRange();
+ return;
+ }
+
+ for (auto [Name, IsInc] :
+ {std::pair{UnexpectedInc, true}, std::pair{UnexpectedDec, false}}) {
+ if (const auto *Node = Result.Nodes.getNodeAs<Expr>(Name)) {
+ diag(Node->getExprLoc(), "trying to %select{decrement before the "
+ "start|increment past the end}0 of a range")
+ << IsInc
+ << Result.Nodes.getNodeAs<Expr>(UnexpectedIncDecExpr)
+ ->getSourceRange();
+ AddRevNote(IsInc);
+ return;
+ }
+ }
+ for (auto [Name, IsBegin] :
+ {std::pair{TriRangeArgBegin, true}, std::pair{TriRangeArgEnd, false}}) {
+ if (const auto *Node = Result.Nodes.getNodeAs<Expr>(Name)) {
+ diag(Node->getBeginLoc(),
+ "'%select{end|begin}0' iterator passed as the middle iterator")
+ << IsBegin << Node->getSourceRange();
+ AddRevNote(IsBegin);
+ return;
+ }
+ }
+ llvm_unreachable("Unhandled matches");
+}
+
+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;
+}
+
+bool IncorrectIteratorsCheck::isLanguageVersionSupported(
+ const LangOptions &LangOpts) const {
+ return LangOpts.CPlusPlus;
+}
+
+} // 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..a57e486dc60b9
--- /dev/null
+++ b/clang-tools-extra/clang-tidy/bugprone/IncorrectIteratorsCheck.h
@@ -0,0 +1,45 @@
+//===--- 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 that 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;
+ bool isLanguageVersionSupported(const LangOptions &LangOpts) 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 642ad39cc0c1c..6b9f6c12696f3 100644
--- a/clang-tools-extra/docs/ReleaseNotes.rst
+++ b/clang-tools-extra/docs/ReleaseNotes.rst
@@ -98,6 +98,12 @@ Improvements to clang-tidy
New checks
^^^^^^^^^^
+- New :doc:`bugprone-incorrect-iterators
+ <clang-tidy/checks/bugprone/incorrect-iterators>` check.
+
+ Detects calls to iterator algorithms that are called with potentially
+ invalid arguments.
+
New check aliases
^^^^^^^^^^^^^^^^^
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..796ea62130c27
--- /dev/null
+++ b/clang-tools-extra/docs/clang-tidy/checks/bugprone/incorrect-iterators.rst
@@ -0,0 +1,144 @@
+.. 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 as 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().
+
+3 argument ranges
+=================
+
+Looks for calls which accept a range defined by [first, middle, last] and
+ensures correct arguments are supplied.
+
+.. code-block:: c++
+
+ std::rotate(a.begin(), a.end(), pivot); // a.end() likely should be 3rd
argument.
+ std::rotate(a.bgein(), pivot(), b.end()) // different range past to
begin/end.
+
+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.begin(), 5); // The iterator is invalid for this container.
+ std::vector<int> Vec{a.begin(), a.begin()}; // Second argument should be
a.end().
+ vec.assign(a.begin(), a.begin()) // Second argument should be a.end().
+
+Output Iterators
+================
+
+Looks for calls which accept a single output iterator but are passed the end of
+a container.
+
+.. code-block:: c++
+
+ std::copy(correct.begin(), correct.end(), incorrect.end());
+
+Iterator Advancing
+==================
+
+Looks for calls that advance an iterator outside its range.
+
+.. code-block:: c++
+
+ auto Iter = std::next(Cont.end());
+
+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);
+
+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 a931ebf025a10..749a5454575d5 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>`,
:doc:`bugprone-incorrect-roundings <bugprone/incorrect-roundings>`,
:doc:`bugprone-infinite-loop <bugprone/infinite-loop>`,
:doc:`bugprone-integer-division <bugprone/integer-division>`,
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..ad1767d04ebf1
--- /dev/null
+++
b/clang-tools-extra/test/clang-tidy/checkers/bugprone/incorrect-iterators.cpp
@@ -0,0 +1,437 @@
+// RUN: %check_clang_tidy -std=c++14 %s bugprone-incorrect-iterators %t
+
+namespace std {
+
+template <class U, class V> struct pair {};
+
+namespace execution {
+
+class parallel_policy {};
+
+constexpr parallel_policy par;
+
+} // namespace execution
+
+template <typename BiDirIter> class reverse_iterator {
+public:
+ constexpr explicit reverse_iterator(BiDirIter Iter);
+ reverse_iterator operator+(int) const;
+ reverse_iterator operator-(int) const;
+};
+
+template <typename InputIt> InputIt next(InputIt Iter, int n = 1);
+template <typename BidirIt> BidirIt prev(BidirIt Iter, int n = 1);
+
+template <typename BiDirIter>
+reverse_iterator<BiDirIter> make_reverse_iterator(BiDirIter Iter);
+
+template <typename T> class allocator {};
+
+template <typename T, typename Allocator = allocator<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>;
+
+ vector() = default;
+ vector(const vector &);
+ vector(vector &&);
+ template <typename InputIt>
+ vector(InputIt first, InputIt last, const Allocator &alloc = Allocator());
+ ~vector();
+
+ 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 T> struct less {};
+
+template <typename T> class __set_const_iterator {};
+
+template <typename T> class __set_iterator : public __set_const_iterator<T> {};
+
+template <typename Key, typename Compare = less<Key>,
+ typename Allocator = allocator<Key>>
+class set {
+public:
+ using iterator = __set_iterator<Key>;
+ using const_iterator = __set_const_iterator<Key>;
+ using reverse_iterator = std::reverse_iterator<iterator>;
+ using reverse_const_iterator = std::reverse_iterator<const_iterator>;
+ using value_type = Key;
+
+ set();
+ template <class InputIt>
+ set(InputIt first, InputIt last, const Compare &comp = Compare(),
+ const Allocator &alloc = Allocator());
+ ~set();
+
+ 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();
+
+ iterator insert(const_iterator pos, value_type &&value);
+ template <class InputIt> void insert(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);
+
+template <class InputIt1, class InputIt2, class OutputIt>
+OutputIt set_union(InputIt1 first1, InputIt1 last1, InputIt2 first2,
+ InputIt2 last2, OutputIt d_first);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class ForwardIt3>
+ForwardIt3 set_union(ExecutionPolicy &&policy, ForwardIt1 first1,
+ ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2,
+ ForwardIt3 d_first);
+
+template <class RandomIt> void push_heap(RandomIt first, RandomIt last);
+
+template <class BidirIt1, class BidirIt2>
+BidirIt2 copy_backward(BidirIt1 first, BidirIt1 last, BidirIt2 d_last);
+
+template <class ForwardIt1, class ForwardIt2>
+ForwardIt1 find_end(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first,
+ ForwardIt2 s_last);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+ForwardIt1 find_end(ExecutionPolicy &&policy, ForwardIt1 first, ForwardIt1
last,
+ ForwardIt2 s_first, ForwardIt2 s_last);
+
+template <class InputIt1, class InputIt2>
+bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1,
+ ForwardIt2 first2);
+
+template <class InputIt1, class InputIt2>
+bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+bool equal(ExecutionPolicy &&policy, ForwardIt1 first1, ForwardIt1 last1,
+ ForwardIt2 first2, ForwardIt2 last2);
+
+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);
+
+template <class InputIt, class NoThrowForwardIt>
+NoThrowForwardIt uninitialized_copy(InputIt first, InputIt last,
+ NoThrowForwardIt d_first);
+
+template <class ExecutionPolicy, class ForwardIt, class NoThrowForwardIt>
+NoThrowForwardIt uninitialized_copy(ExecutionPolicy &&policy, ForwardIt first,
+ ForwardIt last, NoThrowForwardIt d_first);
+
+template <class InputIt1, class InputIt2, class T>
+T inner_product(InputIt1 first1, InputIt1 last1, InputIt2 first2, T init);
+
+template <class InputIt, class OutputIt>
+OutputIt partial_sum(InputIt first, InputIt last, OutputIt d_first);
+
+template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPred>
+pair<OutputIt1, OutputIt2> partition_copy(InputIt first, InputIt last,
+ OutputIt1 d_first_true,
+ OutputIt2 d_first_false, UnaryPred
p);
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class ForwardIt3, class UnaryPred>
+pair<ForwardIt2, ForwardIt3>
+partition_copy(ExecutionPolicy &&policy, ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 d_first_true, ForwardIt3 d_first_false, UnaryPred p);
+
+template <class InputIt, class OutputIt, class UnaryOp>
+OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first,
+ UnaryOp unary_op);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class UnaryOp>
+ForwardIt2 transform(ExecutionPolicy &&policy, ForwardIt1 first1,
+ ForwardIt1 last1, ForwardIt2 d_first, UnaryOp unary_op);
+
+template <class InputIt1, class InputIt2, class OutputIt, class BinaryOp>
+OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2,
+ OutputIt d_first, BinaryOp binary_op);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class ForwardIt3, class BinaryOp>
+ForwardIt3 transform(ExecutionPolicy &&policy, ForwardIt1 first1,
+ ForwardIt1 last1, ForwardIt2 first2, ForwardIt3 d_first,
+ BinaryOp binary_op);
+
+template <class ForwardIt, class OutputIt>
+OutputIt rotate_copy(ForwardIt first, ForwardIt n_first, ForwardIt last,
+ OutputIt d_first);
+
+template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+ForwardIt2 rotate_copy(ExecutionPolicy &&policy, ForwardIt1 first,
+ ForwardIt1 n_first, ForwardIt1 last, ForwardIt2
d_first);
+
+} // namespace std
+
+template <typename T = int> static bool dummyUnary(const T &);
+template <typename T = int, typename U = T>
+static bool dummyBinary(const T &, const U &);
+
+void Test() {
+ std::vector<int> I;
+ std::vector<int> J{I.begin(), I.begin()};
+ // CHECK-NOTES: :[[@LINE-1]]:33: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ std::vector<int> K{I.begin(), J.end()};
+ // CHECK-NOTES: [[@LINE-1]]:20: warning: mismatched ranges supplied to
'std::vector<int>::vector'
+ // CHECK-NOTES: :[[@LINE-2]]:22: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:33: note: different range passed as the end
iterator
+ delete (new std::vector<int>(I.end(), I.end()));
+ // CHECK-NOTES: :[[@LINE-1]]:32: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ auto RandomIIter = std::find(I.end(), I.begin(), 0);
+ // CHECK-NOTES: :[[@LINE-1]]:32: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:41: 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 supplied to
'std::find'
+ // CHECK-NOTES: :[[@LINE-2]]:34: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:45: note: different range passed as the end
iterator
+ 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 supplied to
'std::find'
+ // CHECK-NOTES: :[[@LINE-2]]:13: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:52: note: different range passed as the end
iterator
+
+ 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
+
+ std::set_union(I.begin(), I.begin(), J.end(), J.end(), K.end());
+ // CHECK-NOTES: :[[@LINE-1]]:29: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:40: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:58: warning: 'end' iterator supplied where an
output iterator is expected
+ std::set_union(std::execution::par, I.begin(), I.begin(), J.end(), J.end(),
+ K.end());
+ // CHECK-NOTES: :[[@LINE-2]]:50: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:61: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:18: warning: 'end' iterator supplied where an
output iterator is expected
+
+ std::push_heap(std::begin(I), std::end(J));
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::push_heap'
+ // CHECK-NOTES: :[[@LINE-2]]:29: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:42: note: different range passed as the end
iterator
+
+ std::copy_backward(I.begin(), J.end(), K.begin());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::copy_backward'
+ // CHECK-NOTES: :[[@LINE-2]]:22: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:33: note: different range passed as the end
iterator
+ // CHECK-NOTES: :[[@LINE-4]]:42: warning: 'begin' iterator supplied where an
'end' iterator is expected
+
+ std::find_end(I.rbegin(), I.rbegin(), J.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:29: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:41: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ std::find_end(std::execution::par, I.rbegin(), I.rbegin(), J.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:50: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:62: warning: 'end' iterator supplied where a
'begin' iterator is expected
+
+ std::equal(I.begin(), I.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:34: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ std::equal(std::execution::par, I.begin(), I.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:55: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ std::equal(I.begin(), I.end(), J.rbegin(), K.rend());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::equal'
+ // CHECK-NOTES: :[[@LINE-2]]:34: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:46: note: different range passed as the end
iterator
+ std::equal(std::execution::par, I.begin(), I.end(), J.begin(), K.end());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::equal'
+ // CHECK-NOTES: :[[@LINE-2]]:55: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:66: note: different range passed as the end
iterator
+
+ std::is_permutation(I.begin(), J.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::is_permutation'
+ // CHECK-NOTES: :[[@LINE-2]]:23: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:34: note: different range passed as the end
iterator
+ // CHECK-NOTES: :[[@LINE-4]]:43: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ std::is_permutation(I.begin(), I.end(), J.begin(), K.end());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: mismatched ranges supplied to
'std::is_permutation'
+ // CHECK-NOTES: :[[@LINE-2]]:43: note: range passed as the begin iterator
+ // CHECK-NOTES: :[[@LINE-3]]:54: note: different range passed as the end
iterator
+
+ std::uninitialized_copy(I.begin(), I.end(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:47: warning: 'end' iterator supplied where an
output iterator is expected
+ std::uninitialized_copy(std::execution::par, I.begin(), I.begin(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:59: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:70: warning: 'end' iterator supplied where an
output iterator is expected
+
+ std::inner_product(std::make_reverse_iterator(I.begin()),
+ std::make_reverse_iterator(I.end()), J.end(), 0);
+ // CHECK-NOTES: :[[@LINE-2]]:49: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:22: note: 'make_reverse_iterator<int *>'
changes 'begin' into an 'end' iterator
+ // CHECK-NOTES: :[[@LINE-3]]:49: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-4]]:22: note: 'make_reverse_iterator<int *>'
changes 'end' into a 'begin' iterator
+ // CHECK-NOTES: :[[@LINE-5]]:59: warning: 'end' iterator supplied where a
'begin' iterator is expected
+
+ std::partial_sum(I.begin(), I.begin(), J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:31: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:42: warning: 'end' iterator supplied where an
output iterator is expected
+
+ std::partition_copy(I.begin(), I.begin(), J.end(), K.end(), &dummyUnary<>);
+ // CHECK-NOTES: :[[@LINE-1]]:34: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:45: warning: 'end' iterator supplied where an
output iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:54: warning: 'end' iterator supplied where an
output iterator is expected
+ std::partition_copy(std::execution::par, I.begin(), I.end(), J.end(),
K.end(),
+ &dummyUnary<>);
+ // CHECK-NOTES: :[[@LINE-2]]:64: warning: 'end' iterator supplied where an
output iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:73: warning: 'end' iterator supplied where an
output iterator is expected
+
+ std::transform(I.begin(), I.begin(), J.end(), &dummyUnary<>);
+ // CHECK-NOTES: :[[@LINE-1]]:29: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:40: warning: 'end' iterator supplied where an
output iterator is expected
+ std::transform(std::execution::par, I.begin(), I.begin(), J.end(),
+ &dummyUnary<>);
+ // CHECK-NOTES: :[[@LINE-2]]:50: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:61: warning: 'end' iterator supplied where an
output iterator is expected
+ std::transform(I.begin(), I.begin(), J.rend(), K.end(), &dummyBinary<>);
+ // CHECK-NOTES: :[[@LINE-1]]:29: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-2]]:40: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:50: warning: 'end' iterator supplied where an
output iterator is expected
+ std::transform(std::execution::par, I.begin(), I.begin(), J.end(), K.end(),
+ &dummyBinary<>);
+ // CHECK-NOTES: :[[@LINE-2]]:50: warning: 'begin' iterator supplied where an
'end' iterator is expected
+ // CHECK-NOTES: :[[@LINE-3]]:61: warning: 'end' iterator supplied where a
'begin' iterator is expected
+ // CHECK-NOTES: :[[@LINE-4]]:70: warning: 'end' iterator supplied where an
output iterator is expected
+
+ std::rotate_copy(I.begin(), I.end(), RandomIIter, J.end());
+ // CHECK-NOTES: :[[@LINE-1]]:31: warning: 'end' iterator passed as the
middle iterator
+ // CHECK-NOTES: :[[@LINE-2]]:53: warning: 'end' iterator supplied where an
output iterator is expected
+ std::rotate_copy(I.begin(), RandomIIter, I.end(), J.begin()); // OK
+ std::rotate_copy(std::execution::par, I.begin(), I.end(), I.end(),
J.begin());
+ // CHECK-NOTES: :[[@LINE-1]]:52: warning: 'end' iterator passed as the
middle iterator
+
+ std::next(I.end());
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: trying to increment past the end of
a range
+ std::prev(I.end()); // OK
+ I.end() + 1;
+ // CHECK-NOTES: :[[@LINE-1]]:11: warning: trying to increment past the end
of a range
+ I.end() - 1; // OK
+ I.rbegin() - 1;
+ // CHECK-NOTES: :[[@LINE-1]]:14: warning: trying to decrement before the
start of a range
+ I.rbegin() + 1; // OK
+ I.rbegin().operator-(1);
+ // CHECK-NOTES: :[[@LINE-1]]:14: warning: trying to decrement before the
start of a range
+
+ std::next(I.end(),
+ -1); // Technically OK, getting the previous is a weird way.
+ std::next(I.end(), 1);
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: trying to increment past the end of
a range
+ std::next(I.begin(), 1); // OK
+ std::next(I.begin(), -1);
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: trying to decrement before the
start of a range
+ std::prev(I.end(), -1);
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: trying to increment past the end of
a range
+ std::prev(I.end(), 1); // OK
+ std::prev(I.begin(), -1); // Technially OK, getting next in a weird way.
+ std::prev(I.begin(), 1);
+ // CHECK-NOTES: :[[@LINE-1]]:3: warning: trying to decrement before the
start of a range
+
+ I.end() - -1;
+ // CHECK-NOTES: :[[@LINE-1]]:11: warning: trying to increment past the end
of a range
+ I.begin() + -1;
+ // CHECK-NOTES: :[[@LINE-1]]:13: warning: trying to decrement before the
start of a range
+
+ std::make_reverse_iterator(I.begin()) - -1;
+ // CHECK-NOTES: :[[@LINE-1]]:41: warning: trying to increment past the end
of a range
+ // CHECK-NOTES: :[[@LINE-2]]:3: note: 'make_reverse_iterator<int *>' changes
'begin' into an 'end' iterator
+ std::make_reverse_iterator(I.end()) + -1;
+ // CHECK-NOTES: :[[@LINE-1]]:39: warning: trying to decrement before the
start of a range
+ // CHECK-NOTES: :[[@LINE-2]]:3: note: 'make_reverse_iterator<int *>' changes
'end' into a 'begin' iterator
+
+ std::set<int> Items{I.end(), I.end()};
+ // CHECK-NOTES: :[[@LINE-1]]:23: warning: 'end' iterator supplied where a
'begin' iterator is expected [bugprone-incorrect-iterators]
+ std::set<int> Other;
+ Items.insert(Other.begin(), 5);
+ // CHECK-NOTES: :[[@LINE-1]]:16: warning: 'insert' called with an iterator
for a different container [bugprone-incorrect-iterators]
+ // CHECK-NOTES: :[[@LINE-2]]:3: note: container is specified here
+ // CHECK-NOTES: :[[@LINE-3]]:16: note: different container provided here
+ Items.insert(Other.begin(), Other.begin());
+ // CHECK-NOTES: :[[@LINE-1]]:31: 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
