[Analyzer] Iterator Checker - Part 10: Support for iterators passed as parameter

[baloghadamsoftware]

Summary

check::Bind() is not invoked for parameter passing. We use a trick instead: in checkBeginFunction we copy the positions of iterator parameters from the arguments to the parameters.

[takuto.ikuta]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

711 ↗

(On Diff #97946)

Can we use const CheckerContext &C here?

730 ↗

(On Diff #97946)

const auto *P?

731 ↗

(On Diff #97946)

Can we declare this after L735?

[takuto.ikuta]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

711 ↗

(On Diff #97946)

I didn't see C.addTransition, sorry.

[NoQ]

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

711 ↗

(On Diff #97946)

That's a checker callback called by the engine, not much we can change in its signature. Additionally, the addTransition method we use is sufficiently non-const, and that's the whole point of passing the checker context in every callback.

Anyway, CheckerContext is mostly a utility and is short-lived, and it doesn't make much sense to think of it as const.

[NoQ]

I really hope that i'd be able to do something about pass-by-copy in C++, because there's a lot of mess there. I approve this trick unless i actually do something about it.

[baloghadamsoftware]

Rebased, and minor modifications done according to the comments.

[NoQ]

Let's see if this is still necessary after D49443. Iterators will be constructed directly into the argument region, so i suspect that the manual copy is no longer necessary.

[baloghadamsoftware]

Modification of the checker not needed anymore. Only tests added.

[baloghadamsoftware]

Your are right, it is not necessary anymore. Should I keep this patch to add the tests only or should I abandon it completely?

[NoQ]

Just add tests, i guess!

Also i'll have a look at whether the checker is in a good shape to be enabled by default. I suspect that mismatched iterators might be very safe to enable. With all these solver and rearrangement issues, if they only cause false negatives, it's not blocking enabling the checker by default. The same applies to the debate around find.

One thing that's most likely necessary to do before enabling the checker by default is to add a bug report visitor, so that it added notes when iterators appear for the first time or change their state. Without such notes it's usually very hard to understand warnings. Especially because we're dropping the path within inlined functions that have no interesting events, but when the iterator originates from or gets updated within such function, this information becomes crucial. The visitor might have to hop from one object to another similarly to trackNullOrUndefValue() (i.e., by adding more instances of itself that track objects that are being copied or moved into the object of interest at the program point that is currently being visited).

test/Analysis/mismatched-iterator.cpp

157

Maybe use @-8 instead, so that we only had to update it when *this* test changes?

[baloghadamsoftware]

Closed by commits in the previous comments, just URLs misspelled.

[baloghadamsoftware]

In D32906#1257140, @NoQ wrote:

Also i'll have a look at whether the checker is in a good shape to be enabled by default. I suspect that mismatched iterators might be very safe to enable. With all these solver and rearrangement issues, if they only cause false negatives, it's not blocking enabling the checker by default. The same applies to the debate around find.

Unfortunately, we are at the beginning of a long road. I will post several new patches that we already test internally. However the only checker with acceptable false-positive rate is the invalidated-iterator checker. The mismatched-iterator still has high false-positive rate for iterator-iterator mismatches. For iterator-container mismatches it is acceptable. The iterator-range checker also has still too many false positives.

One thing that's most likely necessary to do before enabling the checker by default is to add a bug report visitor, so that it added notes when iterators appear for the first time or change their state. Without such notes it's usually very hard to understand warnings. Especially because we're dropping the path within inlined functions that have no interesting events, but when the iterator originates from or gets updated within such function, this information becomes crucial. The visitor might have to hop from one object to another similarly to trackNullOrUndefValue() (i.e., by adding more instances of itself that track objects that are being copied or moved into the object of interest at the program point that is currently being visited).

Good idea, I will try to create such a visitor. However the next step should be replacing the unaccepted part 9 by a function-summary based solution in a separate checker (std-c++-library-functions).

test/Analysis/iterator-range.cpp

 }
 
 void good_non_std_find(std::vector<int> &V, int e) {
   auto first = nonStdFind(V.begin(), V.end(), e);
   if (V.end() != first)
     *first; // no-warning
 }
 
+void bad_non_std_find(std::vector<int> &V, int e) {
+  auto first = nonStdFind(V.begin(), V.end(), e);
+  *first; // expected-warning{{Iterator accessed outside of its range}}
+}
+
 void tricky(std::vector<int> &V, int e) {
   const auto first = V.begin();
   const auto comp1 = (first != V.end()), comp2 = (first == V.end());
   if (comp1)
     *first;
 }
 
 void loop(std::vector<int> &V, int e) {

test/Analysis/mismatched-iterator.cpp

 }
 
 void bad_overwrite(std::vector<int> &v1, std::vector<int> &v2, int n) {
   auto i = v1.cbegin();
   i = v2.cbegin();
   v1.insert(i, n); // expected-warning{{Container accessed using foreign iterator argument}}
 }
 
+template<typename Container, typename Iterator>
+bool is_cend(Container cont, Iterator it) {
+  return it == cont.cend();
+}
+
+void good_empty(std::vector<int> &v) {
+  is_cend(v, v.cbegin()); // no-warning
+}
+
+void bad_empty(std::vector<int> &v1, std::vector<int> &v2) {
+  is_cend(v1, v2.cbegin()); // expected-warning@149{{Iterators of different containers used where the same container is expected}}
+}
+
 void good_move(std::vector<int> &v1, std::vector<int> &v2) {
   const auto i0 = ++v2.cbegin();
   v1 = std::move(v2);
   v1.erase(i0); // no-warning
 }
 
 void bad_move(std::vector<int> &v1, std::vector<int> &v2) {
   const auto i0 = ++v2.cbegin();