Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -534,6 +534,46 @@ Documentation; } // end: "cplusplus" +let ParentPackage = CplusplusAlpha in { + +def ContainerModeling : Checker<"ContainerModeling">, + HelpText<"Models C++ containers">, + Documentation, + Hidden; + +def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">, + HelpText<"Reports destructions of polymorphic objects with a non-virtual " + "destructor in their base class">, + Documentation; + +def EnumCastOutOfRangeChecker : Checker<"EnumCastOutOfRange">, + HelpText<"Check integer to enumeration casts for out of range values">, + Documentation; + +def IteratorModeling : Checker<"IteratorModeling">, + HelpText<"Models iterators of C++ containers">, + Dependencies<[ContainerModeling]>, + Documentation, + Hidden; + +def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, + HelpText<"Check for use of invalidated iterators">, + Dependencies<[IteratorModeling]>, + Documentation; + +def IteratorRangeChecker : Checker<"IteratorRange">, + HelpText<"Check for iterators used outside their valid ranges">, + Dependencies<[IteratorModeling]>, + Documentation; + +def MismatchedIteratorChecker : Checker<"MismatchedIterator">, + HelpText<"Check for use of iterators of different containers where iterators " + "of the same container are expected">, + Dependencies<[IteratorModeling]>, + Documentation; + +} // end: "alpha.cplusplus" + let ParentPackage = CplusplusOptIn in { def UninitializedObjectChecker: Checker<"UninitializedObject">, @@ -598,48 +638,12 @@ Dependencies<[VirtualCallModeling]>, Documentation; -} // end: "optin.cplusplus" - -let ParentPackage = CplusplusAlpha in { - -def ContainerModeling : Checker<"ContainerModeling">, - HelpText<"Models C++ containers">, - Documentation, - Hidden; - -def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">, - HelpText<"Reports destructions of polymorphic objects with a non-virtual " - "destructor in their base class">, - Documentation; - -def EnumCastOutOfRangeChecker : Checker<"EnumCastOutOfRange">, - HelpText<"Check integer to enumeration casts for out of range values">, - Documentation; - -def IteratorModeling : Checker<"IteratorModeling">, - HelpText<"Models iterators of C++ containers">, +def STLAlgorithmModeling : Checker<"STLAlgorithmModeling">, + HelpText<"Models the algorithm library of the C++ STL.">, Dependencies<[ContainerModeling]>, - Documentation, - Hidden; - -def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, - HelpText<"Check for use of invalidated iterators">, - Dependencies<[IteratorModeling]>, - Documentation; - -def IteratorRangeChecker : Checker<"IteratorRange">, - HelpText<"Check for iterators used outside their valid ranges">, - Dependencies<[IteratorModeling]>, - Documentation; - -def MismatchedIteratorChecker : Checker<"MismatchedIterator">, - HelpText<"Check for use of iterators of different containers where iterators " - "of the same container are expected">, - Dependencies<[IteratorModeling]>, - Documentation; - -} // end: "alpha.cplusplus" + Documentation; +} // end: "optin.cplusplus" //===----------------------------------------------------------------------===// // Valist checkers. Index: clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -99,6 +99,7 @@ SmartPtrModeling.cpp StackAddrEscapeChecker.cpp StdLibraryFunctionsChecker.cpp + STLAlgorithmModeling.cpp StreamChecker.cpp Taint.cpp TaintTesterChecker.cpp Index: clang/lib/StaticAnalyzer/Checkers/Iterator.h =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.h +++ clang/lib/StaticAnalyzer/Checkers/Iterator.h @@ -159,6 +159,10 @@ const SVal &Val); ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos); +ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, + const MemRegion *Cont, const Stmt* S, + const LocationContext *LCtx, + unsigned blockCount); ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, Index: clang/lib/StaticAnalyzer/Checkers/Iterator.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.cpp +++ clang/lib/StaticAnalyzer/Checkers/Iterator.cpp @@ -177,6 +177,20 @@ return nullptr; } +ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, + const MemRegion *Cont, const Stmt* S, + const LocationContext *LCtx, + unsigned blockCount) { + auto &StateMgr = State->getStateManager(); + auto &SymMgr = StateMgr.getSymbolManager(); + auto &ACtx = StateMgr.getContext(); + + auto Sym = SymMgr.conjureSymbol(S, LCtx, ACtx.LongTy, blockCount); + State = assumeNoOverflow(State, Sym, 4); + return setIteratorPosition(State, Val, + IteratorPosition::getPosition(Cont, Sym)); +} + ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance) { Index: clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -487,12 +487,9 @@ Cont = Cont->getMostDerivedObjectRegion(); auto State = C.getState(); - auto &SymMgr = C.getSymbolManager(); - auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, Sym, 4); - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(Cont, Sym)); + const auto *LCtx = C.getLocationContext(); + State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount()); + C.addTransition(State); } Index: clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp =================================================================== --- /dev/null +++ clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp @@ -0,0 +1,158 @@ +//===-- STLAlgorithmModeling.cpp -----------------------------------*- 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 +// +//===----------------------------------------------------------------------===// +// +// Models STL algorithms. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +#include "Iterator.h" + +using namespace clang; +using namespace ento; +using namespace iterator; + +namespace { + +class STLAlgorithmModeling : public Checker { + mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr, + *II_find_first_of = nullptr, *II_find_if = nullptr, + *II_find_if_not = nullptr, *II_lower_bound = nullptr, + *II_upper_bound = nullptr, *II_search = nullptr, + *II_search_n = nullptr; + + bool evalFind(CheckerContext &C, const CallExpr *CE) const; + + void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const; + + typedef bool (STLAlgorithmModeling::*FnCheck)(CheckerContext &, + const CallExpr *) const; + + const CallDescriptionMap Callbacks = { + {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_if"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_if"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_if_not"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_if_not"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_first_of"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_first_of"}, 5}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_first_of"}, 6}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_end"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_end"}, 5}, &STLAlgorithmModeling::evalFind}, + {{{"std", "find_end"}, 6}, &STLAlgorithmModeling::evalFind}, + {{{"std", "lower_bound"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "lower_bound"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "upper_bound"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "upper_bound"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search"}, 3}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search"}, 5}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search"}, 6}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search_n"}, 4}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search_n"}, 5}, &STLAlgorithmModeling::evalFind}, + {{{"std", "search_n"}, 6}, &STLAlgorithmModeling::evalFind}, + }; + +public: + STLAlgorithmModeling() {} + + bool evalCall(const CallEvent &Call, CheckerContext &C) const; +}; // + +bool STLAlgorithmModeling::evalCall(const CallEvent &Call, + CheckerContext &C) const { + const auto *CE = dyn_cast_or_null(Call.getOriginExpr()); + if (!CE) + return false; + + const FnCheck *Handler = Callbacks.lookup(Call); + if (!Handler) + return false; + + return (this->**Handler)(C, CE); +} + +bool STLAlgorithmModeling::evalFind(CheckerContext &C, + const CallExpr *CE) const { + // std::find()-like functions either take their primary range in the first + // two parameters, or iff the first parameter is "execution policy" then in + // the second and third. This means that the second parameter must always be + // an iterator. + if (!isIteratorType(CE->getArg(1)->getType())) + return false; + + // If no "execution policy" parameter is used then the first argument is the + // beginning of the range, thus it must also be an iterator. In this case the + // end of the range is the second parameter. + if (isIteratorType(CE->getArg(0)->getType())) { + Find(C, CE, 1); + return true; + } + + // If "execution policy" parameter is used then the second argument is the + // beginning of the range and the third argument is the end of the range, + // thus it must also also be an iterator. + if (isIteratorType(CE->getArg(2)->getType())) { + Find(C, CE, 2); + return true; + } + + return false; +} + +void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE, + unsigned paramNum) const { + auto State = C.getState(); + auto &SVB = C.getSValBuilder(); + const auto *LCtx = C.getLocationContext(); + + SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); + SVal SecondParam = State->getSVal(CE->getArg(paramNum), LCtx); + + auto StateFound = State->BindExpr(CE, LCtx, RetVal); + + // If we have an iterator position for the range-end argument then we can + // assume that in case of successful search the position of the found element + // is ahed of it. + const auto *Pos = getIteratorPosition(State, SecondParam); + if (Pos) { + StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(), + CE, LCtx, C.blockCount()); + const auto *NewPos = getIteratorPosition(StateFound, RetVal); + assert(NewPos && "Failed to create new iterator position."); + + SVal Less = SVB.evalBinOp(StateFound, BO_LT, + nonloc::SymbolVal(NewPos->getOffset()), + nonloc::SymbolVal(Pos->getOffset()), + SVB.getConditionType()); + assert(Less.getAs() && + "Symbol comparison must be a `DefinedSVal`"); + StateFound = StateFound->assume(Less.castAs(), true); + } + + auto StateNotFound = State->BindExpr(CE, LCtx, SecondParam); + + C.addTransition(StateFound); + C.addTransition(StateNotFound); +} + +} // namespace + +void ento::registerSTLAlgorithmModeling(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterSTLAlgorithmModeling(const LangOptions &LO) { + return true; +} + Index: clang/test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- clang/test/Analysis/Inputs/system-header-simulator-cxx.h +++ clang/test/Analysis/Inputs/system-header-simulator-cxx.h @@ -783,14 +783,121 @@ return it; } - template - InputIterator find(InputIterator first, InputIterator last, const T &val); - - template - ForwardIterator1 find_first_of(ForwardIterator1 first1, - ForwardIterator1 last1, - ForwardIterator2 first2, - ForwardIterator2 last2); + template + InputIt find(InputIt first, InputIt last, const T& value); + + template + ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, + const T& value); + + template + InputIt find_if (InputIt first, InputIt last, UnaryPredicate p); + + template + ForwardIt find_if (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, + UnaryPredicate p); + + template + InputIt find_if_not (InputIt first, InputIt last, UnaryPredicate q); + + template + ForwardIt find_if_not (ExecutionPolicy&& policy, ForwardIt first, + ForwardIt last, UnaryPredicate q); + + template + InputIt find_first_of(InputIt first, InputIt last, + ForwardIt s_first, ForwardIt s_last); + + template + ForwardIt1 find_first_of (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last); + + template + InputIt find_first_of (InputIt first, InputIt last, + ForwardIt s_first, ForwardIt s_last, + BinaryPredicate p ); + + template + ForwardIt1 find_first_of (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last, + BinaryPredicate p ); + + template + InputIt find_end(InputIt first, InputIt last, + ForwardIt s_first, ForwardIt s_last); + + template + ForwardIt1 find_end (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last); + + template + InputIt find_end (InputIt first, InputIt last, + ForwardIt s_first, ForwardIt s_last, + BinaryPredicate p ); + + template + ForwardIt1 find_end (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last, + BinaryPredicate p ); + + template + ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value); + + template + ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value, + Compare comp); + + template + ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value); + + template + ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value, + Compare comp); + + template + ForwardIt1 search (ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last); + + template + ForwardIt1 search (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last); + + template + ForwardIt1 search (ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p); + + template + ForwardIt1 search (ExecutionPolicy&& policy, + ForwardIt1 first, ForwardIt1 last, + ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p); + + template + ForwardIt search (ForwardIt first, ForwardIt last, const Searcher& searcher); + + template + ForwardIt search_n (ForwardIt first, ForwardIt last, Size count, + const T& value); + + template + ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, + Size count, const T& value); + + template + ForwardIt search_n (ForwardIt first, ForwardIt last, Size count, + const T& value, BinaryPredicate p); + + template + ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last, + Size count, const T& value, BinaryPredicate p); template OutputIterator copy(InputIterator first, InputIterator last, @@ -927,4 +1034,22 @@ iterator begin() const { return iterator(val); } iterator end() const { return iterator(val + 1); } }; + +namespace execution { +class sequenced_policy {}; +} + +template struct equal_to {}; + +template > +class default_searcher { +public: + default_searcher (ForwardIt pat_first, + ForwardIt pat_last, + BinaryPredicate pred = BinaryPredicate()); + template + std::pair + operator()( ForwardIt2 first, ForwardIt2 last ) const; +}; + } Index: clang/test/Analysis/stl-algorithm-modeling.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/stl-algorithm-modeling.cpp @@ -0,0 +1,481 @@ +// RUN: %clang_analyze_cc1 -std=c++17 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorModeling,debug.DebugIteratorModeling,optin.cplusplus.STLAlgorithmModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void clang_analyzer_eval(bool); + +template +long clang_analyzer_iterator_position(const Iterator&); + +template Iter return_any_iterator(const Iter &It); + +void test_find1(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find(i1, i2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find2(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find(std::execution::sequenced_policy(), i1, i2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +bool odd(int i) { return i % 2; } + +void test_find_if1(std::vector V) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find_if(i1, i2, odd); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_if2(std::vector V) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find_if(std::execution::sequenced_policy(), i1, i2, odd); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_if_not1(std::vector V) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find_if_not(i1, i2, odd); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_if_not2(std::vector V) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::find_if_not(std::execution::sequenced_policy(), i1, i2, + odd); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_first_of1(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_first_of(i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_first_of2(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_first_of(std::execution::sequenced_policy(), + i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_first_of3(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_first_of(i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_first_of4(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_first_of(std::execution::sequenced_policy(), + i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_end1(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_end(i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_end2(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_end(std::execution::sequenced_policy(), + i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_end3(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_end(i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_find_end4(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::find_end(std::execution::sequenced_policy(), + i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +bool compare(int, int); + +void test_lower_bound1(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::lower_bound(i1, i2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_lower_bound2(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::lower_bound(i1, i2, n, compare); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_upper_bound1(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::upper_bound(i1, i2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_upper_bound2(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::upper_bound(i1, i2, n, compare); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search1(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::search(i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search2(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::search(std::execution::sequenced_policy(), + i1, i2, i3, i4); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search3(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::search(i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search4(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::search(std::execution::sequenced_policy(), + i1, i2, i3, i4, odd); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search5(std::vector V1, std::vector V2) { + const auto i1 = return_any_iterator(V1.begin()); + const auto i2 = return_any_iterator(V1.begin()); + const auto i3 = return_any_iterator(V2.begin()); + const auto i4 = return_any_iterator(V2.begin()); + + const auto i5 = std::search(i1, i2, std::default_searcher(i3, i4)); + + clang_analyzer_eval(i5 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i5 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i5) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i5) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search_n1(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::search_n(i1, i2, 2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search_n2(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::search_n(std::execution::sequenced_policy(), + i1, i2, 2, n); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search_n3(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::search_n(i1, i2, 2, n, compare); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +} + +void test_search_n4(std::vector V, int n) { + const auto i1 = return_any_iterator(V.begin()); + const auto i2 = return_any_iterator(V.begin()); + + const auto i3 = std::search_n(std::execution::sequenced_policy(), + i1, i2, 2, n, compare); + + clang_analyzer_eval(i3 == i2); // expected-warning{{TRUE}} expected-warning{{FALSE}} + + if (i3 != i2) { + clang_analyzer_eval(clang_analyzer_iterator_position(i3) < + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{TRUE}} + clang_analyzer_eval(clang_analyzer_iterator_position(i3) >= + clang_analyzer_iterator_position(i2)); // expected-warning@-1{{FALSE}} + } +}