Page MenuHomePhabricator

[Analyzer] Add new visitor to the iterator checkers
Needs ReviewPublic

Authored by baloghadamsoftware on May 28 2019, 7:10 AM.

Details

Reviewers
NoQ
Szelethus
Summary

Iterator bugs such as dereference of out-of-range or any access of invalidated iterators are difficult to understand. A BugReporterVisitor that marks the place where the iterator reached to past-the-end or the first position, became invalidated and marks the execution path with a message about the emptiness of the container helps much in understanding the actual bug. It also helps deciding whether the finding is a true or a false positive. This patch adds such a visitor to the iterator checkers.

Diff Detail

Event Timeline

Before someone asks: NoteTags are not applicable here since invalidation and reaching one end of the range happens in many different places. This is also true for container emptiness.

NoQ added a comment.May 28 2019, 12:48 PM

Before someone asks: NoteTags are not applicable here since invalidation and reaching one end of the range happens in many different places. This is also true for container emptiness.

Mm, what's wrong with many different places? If you're worried about code duplication, just put tag construction into a function (?)

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
281–282

I don't think we should stop here. I think it's worth it to highlight *all* increments and decrements of the interesting iterator, so that it was clear how come that it has the given value.

Additionally, because iterators are copied around, it makes sense to "recursively" apply the visitor to the original object when the iterator is obtained as a copy (similarly to how trackExpressionValue works).

In D62525#1519868, @NoQ wrote:

Before someone asks: NoteTags are not applicable here since invalidation and reaching one end of the range happens in many different places. This is also true for container emptiness.

Mm, what's wrong with many different places? If you're worried about code duplication, just put tag construction into a function (?)

It is not about code duplication. Of course, that can be handled by a function.

The problem is that the transition is added in the top level function but iterator position adjustments happen in the lower level ones. Data flow is one-way, top-down. For example, an insertion happens into a vector that invalidates all the iterators at and after the position where it is inserted. In this case handleInsert() calls a function that iterates all the active iterator positions and calls other one that invalidates the ones affected by the insertion. To propagate back the list of iterators invalidated would be too complex. Increments and decrements are even worse. Thus here the correct way seems to find the relevant transitions in a visitor instead of trying to figure out what note tags to add at each transition.

baloghadamsoftware marked an inline comment as done.May 30 2019, 7:59 AM
baloghadamsoftware added inline comments.
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
281–282

This can be done but an iterator can reach the past-the-end or the first position by changing the container's size as well, not only by incrementing or decrementing the iterator itself.

Visitors now track increments and decrements.

Szelethus added inline comments.Mon, Jul 15, 1:29 PM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1099

/*PastTheEnd=*/ false

1277–1292

I'm confused, are these changes related to this patch? It doesn't seem to be.

baloghadamsoftware marked an inline comment as done.Thu, Jul 18, 2:16 AM
baloghadamsoftware added inline comments.
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1277–1292

Yes, they are. Since we want to track the iterator positions upwards along the bugpath as far a possible I had to reverse one of my decisions. When I first decided it was really like a coin thrown up, but now it turned out I took the wrong choice considering the visitor. The change is that upon move assignment of a container the iterators are transferred to the new container, except the past-the-end iterator. However we also have iterator positions relative to the past-the-end iterator (thus using the same symbol) which must be transferred. So I had to separate them from the past-the-end positions by generating a new end symbol. I originally used this new symbol for the positions to be transferred and kept the old symbol for the past-the-end positions. However this makes tracking of the non past-the-end positions very difficult so I reversed it and now I transfer the old symbol and use the new for the past-the-end positions.