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.
Mm, what's wrong with many different places? If you're worried about code duplication, just put tag construction into a function (?)
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).
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.
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.
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.
I don't see obvious red flags here, @NoQ?
Mhm, I personally find this reasoning sufficient.
Maybe in a followup patch, but I'd love to see a trackIterator function!
Sometimes I just need a reality check to realize how absurdly difficult the problem is that you're solving... Wow. I mentioned this elsewhere, but do we not need a debug checker to validate that we argue about all of these correctly?
Is this actually correct?
Hey, but it is done now, in the updated patch! See lines 1782-1803.
All iterators, including the past-the-end iterator, are invalidated.
I think I speak here about insert(), not about push_back() and push_front().
Since we use a conservative approach we always assume that vectors and double-end queues do not change capacities.
Ok, so is it problematic to define a lambda that checks whether an interesting iterator is invalidated? Or is it difficult to return the note tag from many stack frames in order to finally squeeze it into the transition?