This is an archive of the discontinued LLVM Phabricator instance.

[Analyzer] Iterator Checker - Part 3: Invalidation check, first for (copy) assignments
ClosedPublic

Authored by baloghadamsoftware on May 2 2017, 6:59 AM.

Diff Detail

Event Timeline

baloghadamsoftware retitled this revision from [Analyzer] Iterator Checker - Part3: Invalidation check, first for (copy) assignments to [Analyzer] Iterator Checker - Part 3: Invalidation check, first for (copy) assignments.May 4 2017, 5:30 AM
takuto.ikuta added inline comments.
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
325

OK to use make_unique here?

NoQ added inline comments.Dec 14 2017, 3:58 PM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

This needs investigation, because it may be nasty.

generateNonFatalErrorNode() returns null when the exact same non-fatal error node, also produced by the iterator checker with the exact same program state and exact same program point and exact same tag on the program point already exists. As far as i understand, the only difference your tag makes is that the tag is now different, so it is not merged with the existing node. However, it is worth it to try to find out why the node gets merged at all.

This may be caused by an accidental state split. For example, if you are calling generateNonFatalErrorNode() twice in the same checker callback without chaining them together (passing node returned by one as an argument to another), this in fact splits states. I'm not immediately seeing such places in the code - you seem to be aware of this problem and avoiding it well. But still, looking at the topology of the exploded graph in the failing test should help finding out what is going on.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

I made some more investigation this time. Unfortunately the case is not what you suggest. Only one non-fatal error node is produced. I tested it with a common tag (a global static so the tag is exactly the same at every generateNonFatalErrorNode(), but the tests still pass. I printed out the exploded graph and I found that there are indeed two nodes with the same state ID. The tag is the default tag automatically generated from the name of the checker. The first state is created in function checkPreStatement() for CXXOperatorCallExpr where I copy the state of the iterator from the formal to the actual this parameter. All the test fails happen at the dereference operator call (*) of another operator call (++ or --). After this copy, when I call generateNonFatalErrorNode() I get nullptr because at some point under the hood (I debugged it when I created it originally) the error node is considered as "not new". If I use a custom tag here, the state ID remains, not the node ID changes.

Rebased to current Part 2.

Hello Adam. I have a nit inline.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1300

Updating ProgramState is usually considered as an expensive operation. Instead, we can update maps (RegionMap and SymbolMap) and then, if they have any updates, create a state containing these maps. What do you think?

Thanks you for your comments! I have one question:

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1300

How to update ImmutableMap?

a.sidorin added inline comments.Jan 17 2018, 1:44 AM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
1300

You can create a new Immutable map from existing with factory methods:

auto Factory = State->get_context<IteratorRegionMap>();
auto Map = State->get<RegionMap>();
Map = Factory.add(Map, Key, Value);
Map = Factory.add(Map, Key2, Value2);
State = State->set<IteratorRegionMap>(Map);

Updated according to the comments.

baloghadamsoftware edited reviewers, added: dcoughlin; removed: zaks.anna.Jan 17 2018, 5:34 AM
george.karpenkov resigned from this revision.Jul 3 2018, 11:39 AM
george.karpenkov added a subscriber: george.karpenkov.
whisperity added inline comments.Jul 5 2018, 2:43 AM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
92

Seeing that in line 106 you consider this record immutable, you might want to add a const on this field too.

test/Analysis/invalidated-iterator.cpp
33

This might not be applicable here, but isn't there a test case for copy operations where the iterator isn't invalidated? Something of a positive test to be added here. My only idea is something with weird reference-to-pointer magic. Might not worth the hassle.

Updated according to the comments.

baloghadamsoftware marked 2 inline comments as done.

Re-upload because of a mistake.

baloghadamsoftware marked an inline comment as not done.Jul 5 2018, 11:31 PM
baloghadamsoftware added inline comments.
test/Analysis/invalidated-iterator.cpp
33

Accoring to the rules (on STL containers) if a container is overwritten using a copy assignment, all its iterators become invalidated. So I cannot imagine a positive test case here.

NoQ added inline comments.Jul 25 2018, 5:29 PM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

I think i see the problem. The checker subscribes to both PreCall and PreStmt<CallExpr> (to be exact, CXXOperatorCallExpr) and adds transitions in both cases. It results with a predecessor node in CheckerContext that's already tagged by the checker. Apparently this never worked, but nobody tried that.

Ideally, we should make sure those callbacks use different program points, eg. introduce PreCall/PostCall program point kinds and use them.

Also i wonder why are you using pre- rather than post-statement callback. You model all other operators in PostCall, why did those end up here? Maybe merge them? It is generally better to model pre-conditions and look for bugs in PreStmt/PreCall (before we don't care what happens within the call), and model effects in PostStmt/PostCall (because effects don't take effect until the call happens).

baloghadamsoftware marked an inline comment as not done.Jul 30 2018, 11:58 PM
baloghadamsoftware added inline comments.
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

That is what I am trying to to: Post* for modelling and Pre* for checking. However, this PreStmt<CXXOperatorCallExpr>() is special since I have to move the arguments to the context of the called operator before the call.

NoQ added inline comments.Jul 31 2018, 12:05 PM
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

Ah, it's that thing, PreCall then?

Pre-statement check of CXXOperatorCallExpr merged into pre-call check.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
646

Yes! It seems to be working. Thank you for your help!

NoQ added a comment.Aug 1 2018, 5:24 PM

I suspect that with rC338135 your operator this-argument re-assignment mechanism is no longer necessary. Due to the combination of support for materializing temporaries that i added previously and the change in the AST that turns the operator this-argument into a simple temporary, i believe that the memory region should no longer change and you don't need to move your metadata. Could you check this?

Copying iterator position for the this pointer of C++ operators from the caller's context to the callee's context is no longer needed.

Yes, it is working now without the hack.

NoQ accepted this revision.Aug 14 2018, 2:50 PM

Looks great, let's land this!

This revision is now accepted and ready to land.Aug 14 2018, 2:50 PM
This revision was automatically updated to reflect the committed changes.