baloghadamsoftware created this revision.
baloghadamsoftware added reviewers: NoQ, Szelethus.
baloghadamsoftware added a project: clang.
Herald added subscribers: Charusso, donat.nagy, mikhail.ramalho, a.sidorin,
rnkovacs, szepet, xazax.hun, whisperity, mgorny.
baloghadamsoftware added a parent revision: D70320: [Analyzer] [NFC] Iterator
Checkers - Separate iterator modeling and the actual checkers.
STL Algorithms are usually implemented in a tricky for performance reasons
which is too complicated for the analyzer. Furthermore inlining them is costly.
Instead of inlining we should model their behavior according to the
specifications.
This patch is the first step towards STL Algorithm modeling. It models all the
`find()`-like functions in a simple way: the result is either found or not. In
the future it can be extended to only return success if container modeling is
also extended in a way the it keeps track of trivial insertions and deletions.
Repository:
rC Clang
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
@@ -162,8 +162,6 @@
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
const ContainerData &CData);
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val);
-ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
- long Scale);
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
const MemRegion *Cont);
ProgramStateRef
@@ -706,12 +704,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);
}
@@ -1316,47 +1311,6 @@
return nullptr;
}
-// This function tells the analyzer's engine that symbols produced by our
-// checker, most notably iterator positions, are relatively small.
-// A distance between items in the container should not be very large.
-// By assuming that it is within around 1/8 of the address space,
-// we can help the analyzer perform operations on these symbols
-// without being afraid of integer overflows.
-// FIXME: Should we provide it as an API, so that all checkers could use it?
-ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
- long Scale) {
- SValBuilder &SVB = State->getStateManager().getSValBuilder();
- BasicValueFactory &BV = SVB.getBasicValueFactory();
-
- QualType T = Sym->getType();
- assert(T->isSignedIntegerOrEnumerationType());
- APSIntType AT = BV.getAPSIntType(T);
-
- ProgramStateRef NewState = State;
-
- llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
- SVal IsCappedFromAbove =
- SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
- nonloc::ConcreteInt(Max), SVB.getConditionType());
- if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
- NewState = NewState->assume(*DV, true);
- if (!NewState)
- return State;
- }
-
- llvm::APSInt Min = -Max;
- SVal IsCappedFromBelow =
- SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
- nonloc::ConcreteInt(Min), SVB.getConditionType());
- if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
- NewState = NewState->assume(*DV, true);
- if (!NewState)
- return State;
- }
-
- return NewState;
-}
-
ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
SymbolRef Sym2, bool Equal) {
auto &SVB = State->getStateManager().getSValBuilder();
Index: clang/lib/StaticAnalyzer/Checkers/Iterator.h
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/Iterator.h
+++ clang/lib/StaticAnalyzer/Checkers/Iterator.h
@@ -159,10 +159,16 @@
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,
const SVal &Distance);
+ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
+ long Scale);
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
BinaryOperator::Opcode Opc);
bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
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) {
@@ -204,6 +218,47 @@
return nullptr;
}
+// This function tells the analyzer's engine that symbols produced by our
+// checker, most notably iterator positions, are relatively small.
+// A distance between items in the container should not be very large.
+// By assuming that it is within around 1/8 of the address space,
+// we can help the analyzer perform operations on these symbols
+// without being afraid of integer overflows.
+// FIXME: Should we provide it as an API, so that all checkers could use it?
+ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
+ long Scale) {
+ SValBuilder &SVB = State->getStateManager().getSValBuilder();
+ BasicValueFactory &BV = SVB.getBasicValueFactory();
+
+ QualType T = Sym->getType();
+ assert(T->isSignedIntegerOrEnumerationType());
+ APSIntType AT = BV.getAPSIntType(T);
+
+ ProgramStateRef NewState = State;
+
+ llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
+ SVal IsCappedFromAbove =
+ SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
+ nonloc::ConcreteInt(Max), SVB.getConditionType());
+ if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
+ NewState = NewState->assume(*DV, true);
+ if (!NewState)
+ return State;
+ }
+
+ llvm::APSInt Min = -Max;
+ SVal IsCappedFromBelow =
+ SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
+ nonloc::ConcreteInt(Min), SVB.getConditionType());
+ if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
+ NewState = NewState->assume(*DV, true);
+ if (!NewState)
+ return State;
+ }
+
+ return NewState;
+}
+
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
BinaryOperator::Opcode Opc) {
return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
Index: clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
===================================================================
--- clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
+++ clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt
@@ -95,6 +95,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
@@ -579,6 +579,11 @@
Dependencies<[VirtualCallModeling]>,
Documentation<HasDocumentation>;
+def STLAlgorithmModeling : Checker<"STLAlgorithmModeling">,
+ HelpText<"Models the algorithm library of the C++ STL.">,
+ Dependencies<[IteratorModeling]>,
+ Documentation<NotDocumented>;
+
} // end: "optin.cplusplus"
let ParentPackage = CplusplusAlpha in {
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
