baloghadamsoftware updated this revision to Diff 241364.
baloghadamsoftware added a comment.
Rebased.
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D70818/new/
https://reviews.llvm.org/D70818
Files:
clang/include/clang/StaticAnalyzer/Checkers/Checkers.td
clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
clang/lib/StaticAnalyzer/Checkers/Iterator.h
clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp
clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
clang/test/Analysis/Inputs/system-header-simulator-cxx.h
clang/test/Analysis/stl-algorithm-modeling.cpp
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 <typename Iterator>
+long clang_analyzer_iterator_position(const Iterator&);
+
+template <typename Iter> Iter return_any_iterator(const Iter &It);
+
+void test_find1(std::vector<int> 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<int> 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<int> 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<int> 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<int> 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<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> 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<int> 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<int> 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<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> V1, std::vector<int> 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<int> 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<int> 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<int> 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<int> 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}}
+ }
+}
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 <class InputIterator, class T>
- InputIterator find(InputIterator first, InputIterator last, const T &val);
-
- template <class ForwardIterator1, class ForwardIterator2>
- ForwardIterator1 find_first_of(ForwardIterator1 first1,
- ForwardIterator1 last1,
- ForwardIterator2 first2,
- ForwardIterator2 last2);
+ template <class InputIt, class T>
+ InputIt find(InputIt first, InputIt last, const T& value);
+
+ template <class ExecutionPolicy, class ForwardIt, class T>
+ ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
+ const T& value);
+
+ template <class InputIt, class UnaryPredicate>
+ InputIt find_if (InputIt first, InputIt last, UnaryPredicate p);
+
+ template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>
+ ForwardIt find_if (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
+ UnaryPredicate p);
+
+ template <class InputIt, class UnaryPredicate>
+ InputIt find_if_not (InputIt first, InputIt last, UnaryPredicate q);
+
+ template <class ExecutionPolicy, class ForwardIt, class UnaryPredicate>
+ ForwardIt find_if_not (ExecutionPolicy&& policy, ForwardIt first,
+ ForwardIt last, UnaryPredicate q);
+
+ template <class InputIt, class ForwardIt>
+ InputIt find_first_of(InputIt first, InputIt last,
+ ForwardIt s_first, ForwardIt s_last);
+
+ template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+ ForwardIt1 find_first_of (ExecutionPolicy&& policy,
+ ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last);
+
+ template <class InputIt, class ForwardIt, class BinaryPredicate>
+ InputIt find_first_of (InputIt first, InputIt last,
+ ForwardIt s_first, ForwardIt s_last,
+ BinaryPredicate p );
+
+ template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class BinaryPredicate>
+ ForwardIt1 find_first_of (ExecutionPolicy&& policy,
+ ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last,
+ BinaryPredicate p );
+
+ template <class InputIt, class ForwardIt>
+ InputIt find_end(InputIt first, InputIt last,
+ ForwardIt s_first, ForwardIt 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 InputIt, class ForwardIt, class BinaryPredicate>
+ InputIt find_end (InputIt first, InputIt last,
+ ForwardIt s_first, ForwardIt s_last,
+ BinaryPredicate p );
+
+ template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class BinaryPredicate>
+ ForwardIt1 find_end (ExecutionPolicy&& policy,
+ ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last,
+ BinaryPredicate p );
+
+ template <class ForwardIt, class T>
+ ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value);
+
+ template <class ForwardIt, class T, class Compare>
+ ForwardIt lower_bound (ForwardIt first, ForwardIt last, const T& value,
+ Compare comp);
+
+ template <class ForwardIt, class T>
+ ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value);
+
+ template <class ForwardIt, class T, class Compare>
+ ForwardIt upper_bound (ForwardIt first, ForwardIt last, const T& value,
+ Compare comp);
+
+ template <class ForwardIt1, class ForwardIt2>
+ ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last);
+
+ template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
+ ForwardIt1 search (ExecutionPolicy&& policy,
+ ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last);
+
+ template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>
+ ForwardIt1 search (ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);
+
+ template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
+ class BinaryPredicate >
+ ForwardIt1 search (ExecutionPolicy&& policy,
+ ForwardIt1 first, ForwardIt1 last,
+ ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);
+
+ template <class ForwardIt, class Searcher>
+ ForwardIt search (ForwardIt first, ForwardIt last, const Searcher& searcher);
+
+ template <class ForwardIt, class Size, class T>
+ ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,
+ const T& value);
+
+ template <class ExecutionPolicy, class ForwardIt, class Size, class T>
+ ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
+ Size count, const T& value);
+
+ template <class ForwardIt, class Size, class T, class BinaryPredicate>
+ ForwardIt search_n (ForwardIt first, ForwardIt last, Size count,
+ const T& value, BinaryPredicate p);
+
+ template <class ExecutionPolicy, class ForwardIt, class Size, class T,
+ class BinaryPredicate>
+ ForwardIt search_n (ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
+ Size count, const T& value, BinaryPredicate p);
template <class InputIterator, class OutputIterator>
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 <class T = void> struct equal_to {};
+
+template <class ForwardIt, class BinaryPredicate = std::equal_to<> >
+class default_searcher {
+public:
+ default_searcher (ForwardIt pat_first,
+ ForwardIt pat_last,
+ BinaryPredicate pred = BinaryPredicate());
+ template <class ForwardIt2>
+ std::pair <ForwardIt2, ForwardIt2>
+ operator()( ForwardIt2 first, ForwardIt2 last ) const;
+};
+
}
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<eval::Call> {
+ 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<FnCheck> 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<CallExpr>(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<DefinedSVal>() &&
+ "Symbol comparison must be a `DefinedSVal`");
+ StateFound = StateFound->assume(Less.castAs<DefinedSVal>(), true);
+ }
+
+ auto StateNotFound = State->BindExpr(CE, LCtx, SecondParam);
+
+ C.addTransition(StateFound);
+ C.addTransition(StateNotFound);
+}
+
+} // namespace
+
+void ento::registerSTLAlgorithmModeling(CheckerManager &mgr) {
+ mgr.registerChecker<STLAlgorithmModeling>();
+}
+
+bool ento::shouldRegisterSTLAlgorithmModeling(const LangOptions &LO) {
+ return true;
+}
+
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/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/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/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<HasDocumentation>;
} // end: "cplusplus"
+let ParentPackage = CplusplusAlpha in {
+
+def ContainerModeling : Checker<"ContainerModeling">,
+ HelpText<"Models C++ containers">,
+ Documentation<NotDocumented>,
+ Hidden;
+
+def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">,
+ HelpText<"Reports destructions of polymorphic objects with a non-virtual "
+ "destructor in their base class">,
+ Documentation<HasAlphaDocumentation>;
+
+def EnumCastOutOfRangeChecker : Checker<"EnumCastOutOfRange">,
+ HelpText<"Check integer to enumeration casts for out of range values">,
+ Documentation<HasAlphaDocumentation>;
+
+def IteratorModeling : Checker<"IteratorModeling">,
+ HelpText<"Models iterators of C++ containers">,
+ Dependencies<[ContainerModeling]>,
+ Documentation<NotDocumented>,
+ Hidden;
+
+def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
+ HelpText<"Check for use of invalidated iterators">,
+ Dependencies<[IteratorModeling]>,
+ Documentation<HasAlphaDocumentation>;
+
+def IteratorRangeChecker : Checker<"IteratorRange">,
+ HelpText<"Check for iterators used outside their valid ranges">,
+ Dependencies<[IteratorModeling]>,
+ Documentation<HasAlphaDocumentation>;
+
+def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
+ HelpText<"Check for use of iterators of different containers where iterators "
+ "of the same container are expected">,
+ Dependencies<[IteratorModeling]>,
+ Documentation<HasAlphaDocumentation>;
+
+} // end: "alpha.cplusplus"
+
let ParentPackage = CplusplusOptIn in {
def UninitializedObjectChecker: Checker<"UninitializedObject">,
@@ -598,48 +638,12 @@
Dependencies<[VirtualCallModeling]>,
Documentation<HasDocumentation>;
-} // end: "optin.cplusplus"
-
-let ParentPackage = CplusplusAlpha in {
-
-def ContainerModeling : Checker<"ContainerModeling">,
- HelpText<"Models C++ containers">,
- Documentation<NotDocumented>,
- Hidden;
-
-def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">,
- HelpText<"Reports destructions of polymorphic objects with a non-virtual "
- "destructor in their base class">,
- Documentation<HasAlphaDocumentation>;
-
-def EnumCastOutOfRangeChecker : Checker<"EnumCastOutOfRange">,
- HelpText<"Check integer to enumeration casts for out of range values">,
- Documentation<HasAlphaDocumentation>;
-
-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<NotDocumented>,
- Hidden;
-
-def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">,
- HelpText<"Check for use of invalidated iterators">,
- Dependencies<[IteratorModeling]>,
- Documentation<HasAlphaDocumentation>;
-
-def IteratorRangeChecker : Checker<"IteratorRange">,
- HelpText<"Check for iterators used outside their valid ranges">,
- Dependencies<[IteratorModeling]>,
- Documentation<HasAlphaDocumentation>;
-
-def MismatchedIteratorChecker : Checker<"MismatchedIterator">,
- HelpText<"Check for use of iterators of different containers where iterators "
- "of the same container are expected">,
- Dependencies<[IteratorModeling]>,
- Documentation<HasAlphaDocumentation>;
-
-} // end: "alpha.cplusplus"
+ Documentation<NotDocumented>;
+} // end: "optin.cplusplus"
//===----------------------------------------------------------------------===//
// Valist checkers.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
