Page MenuHomePhabricator

[Analyzer][NFC] Avoid handling of LazyCompundVals in IteratorModeling
Needs ReviewPublic

Authored by baloghadamsoftware on Apr 1 2020, 10:17 AM.

Details

Summary

Since accessing the region of LazyCompoundVals is an undocumented and unreliable feature, try to find the region of the return value directly, skipping both the LazyCompoundVal and its later materialization.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
NoQ added inline comments.Apr 27 2020, 12:57 PM
clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
601–603 ↗(On Diff #260387)

I implemented the basic isLive() and getBinding() functions which reduced the number of failing tests by 0.

This line in particular is very incorrect. In fact, most of the time the result will be false.

In D77229#2006106, @NoQ wrote:

If your change causes a crash, please debug it. That's a completely normal thing that programmers do every day. Unfortunately, I can't afford to spoon-feed you the solution step-by-step.

As I wrote, I debugged and analyzed it and I am facing a problem for which I need help. Operator calls are very poorly implemented in the AST.

As I wrote, I debugged and analyzed it and I am facing a problem for which I need help. Operator calls are very poorly implemented in the AST.

Yes, indeed very poorly. A C++ operator call is either implemented as CXXOperatorCall or CXXMethodCall randomly. In the former case the this parameter is explicit at the beginning, in the latter case it is implicit. I managed to solve it using this piece of code:

const auto *Call = cast<Expr>(CallSite);
unsigned Index = PVD->getFunctionScopeIndex();
// For `CallExpr` of C++ member operators we must shift the index by 1
if (isa<CXXOperatorCallExpr>(Call)) {
  if (const auto *CMD = dyn_cast<CXXMethodDecl>(SFC->getDecl())) {
    if (CMD->isOverloadedOperator())
      ++Index;
  }
}

But this is not the only problem with indices. I have no solution for the following call (is it really a call?) resulting in an assertion because overindexing in nullability.mm:

Dummy *_Nonnull (^myblock)(void) = ^Dummy *_Nonnull(void) {

Even if I try to get the FunctionDecl it still says that it has 0 parameters, exactly what CallExpr says, but we have a parameter here with index of 0. How can it be? How should I handle this strange case? I only have very basic Objective-C knowledge.

In D77229#2006106, @NoQ wrote:

If your change causes a crash, please debug it. That's a completely normal thing that programmers do every day. Unfortunately, I can't afford to spoon-feed you the solution step-by-step.

I do not require it, but I noticed to you at the very beginning that I need assistance. I work on the analyzer for less than 5 years, and not full time, because I also create Tidy checkers sometimes, I also have our internal stuff (most of which I would like to upstream). As far as I know, you have more than 10 years experience in the Analyzer. I am already have deep knowledge in some parts (e.g. constraint handling, AST), I am somewhat familiar with others (SValBuilder, ExprEngine, BugReporter etc.) but I never touched regions and store.

NoQ added a comment.Apr 28 2020, 12:50 AM

Yes, indeed very poorly. A C++ operator call is either implemented as CXXOperatorCall or CXXMethodCall randomly. In the former case the this parameter is explicit at the beginning, in the latter case it is implicit.

We have methods on CallEvent to handle this, namely getAdjustedParameterIndex() and getASTArgumentIndex(). They were added in D49443.

But this is not the only problem with indices. I have no solution for the following call (is it really a call?) resulting in an assertion because overindexing in nullability.mm:

Dummy *_Nonnull (^myblock)(void) = ^Dummy *_Nonnull(void) {

Even if I try to get the FunctionDecl it still says that it has 0 parameters, exactly what CallExpr says, but we have a parameter here with index of 0. How can it be? How should I handle this strange case? I only have very basic Objective-C knowledge.

These are blocks. They are like lambdas, just different syntax. They aren't part of Objective-C; they're a non-standard extension to C supported by both gcc and clang.

The line you quoted is not a call, it only defines a block and assigns it into a variable of block pointer type. Here's the full code of the test:

358 void testNilReturnWithBlock(Dummy *p) {
359   p = 0;
360   Dummy *_Nonnull (^myblock)(void) = ^Dummy *_Nonnull(void) {
361     return p; // TODO: We should warn in blocks.
362   };
363   myblock();
364 }

The block is invoked on line 363. Parameter p of the surrounding function is accessible from the block because it was captured; it is not a parameter of the block itself.

As far as I know, you have more than 10 years experience in the Analyzer. I work on the analyzer for less than 5 years, and not full time, because I also create Tidy checkers sometimes, I also have our internal stuff (most of which I would like to upstream).

I started in mid-2014. I too am regularly distracted to stuff that isn't particularly educational about the analyzer.

Oh, it is not only Objective-C. I have been programming in C for 25+ years and teaching it for 15+ years, but I never met such syntactical construction:

dispatch_sync(queue, ^(void){

Here it is worse than at the Objective-C code above, because the index is 1, but the number of args is 0. Thus this is an overindexing by 2. What are these strange constructions and how to get parameter type if they have no arguments? (Even if I get the function declaration from the stack frame, they have no parameters.) How can we have a parameter for them? How to handle them, how to return the type for a parameter that should not exist but it does?

In D77229#2007125, @NoQ wrote:

Yes, indeed very poorly. A C++ operator call is either implemented as CXXOperatorCall or CXXMethodCall randomly. In the former case the this parameter is explicit at the beginning, in the latter case it is implicit.

We have methods on CallEvent to handle this, namely getAdjustedParameterIndex() and getASTArgumentIndex(). They were added in D49443.

Unfortunately, in ExprEngine::VisitCommonDeclRefExpr we do not have CallEvent, only CallExpr.

These are blocks. They are like lambdas, just different syntax. They aren't part of Objective-C; they're a non-standard extension to C supported by both gcc and clang.

The line you quoted is not a call, it only defines a block and assigns it into a variable of block pointer type. Here's the full code of the test:

358 void testNilReturnWithBlock(Dummy *p) {
359   p = 0;
360   Dummy *_Nonnull (^myblock)(void) = ^Dummy *_Nonnull(void) {
361     return p; // TODO: We should warn in blocks.
362   };
363   myblock();
364 }

The block is invoked on line 363. Parameter p of the surrounding function is accessible from the block because it was captured; it is not a parameter of the block itself.

Sorry, all my studies were about standard things only. Everything else was banned. This is the philosophy of my university, it seems.

What do you suggest, how to retrieve the type for them? We stored the CallExpr as OriginExpr for the region. Should we store something else in case of blocks, or should we handle this in getType()? How to distinguish parameters of the block from the captured parameters of the function? This case sounds very complicated to handle.

baloghadamsoftware marked an inline comment as done.Apr 28 2020, 1:12 AM
baloghadamsoftware added inline comments.
clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
601–603 ↗(On Diff #260387)

OK, but what should I check for liveness here? We do not have a Decl. We could retrieve the Expr for the Arg, except for CXXNewOperator because there the size argument cannot be retrieved.

Getting the type of parameter regions has no crashes on the test suite.

Wrong diff uploaded previously.

baloghadamsoftware marked 5 inline comments as done.Apr 28 2020, 9:02 AM

Very slow progress, but lots of open questions. @NoQ, please try to answer them.

clang/lib/StaticAnalyzer/Core/CallEvent.cpp
614 ↗(On Diff #260659)

Is this the correct handling of this kind of calls?

clang/lib/StaticAnalyzer/Core/ExprEngine.cpp
2466 ↗(On Diff #260659)

What to do with function parameters captured by a block? I tried to search for the owner function backwards in the chain of stack frames, but I did not find it.

2474 ↗(On Diff #260659)

Here we have no CallEvent so no better came to my mind.

clang/lib/StaticAnalyzer/Core/MemRegion.cpp
204 ↗(On Diff #260659)

This whole branch should be moved to a separate function called e.g. getArgExpr(). But what to do with param 0 of CXXNewExpr()? It is the size parameter for which we do not have an Expr. For the greater indices we subtract 1 from the Index.

clang/lib/StaticAnalyzer/Core/SymbolManager.cpp
601–603 ↗(On Diff #260387)

Here could help the function getArgExpr() of ParamRegion, I suppose. We should put it into the place of getOriginExpr(). Is this correct?

Now I made some good progress, thank you @NoQ for your suggestions. Not all of them are implemented yet (currently the +-1 with the indices seem to be working, thus I will fix that part later), but now I managed to reduce failing tests from 340 to 19. Most of these tests are about missing notes, so the next task is handling the new ParamRegion in the bug reporter visitors. I already made some progress there too.

Bug reporter visitors updated, failing tests reduced from 19 to 6.

NoQ added inline comments.May 3 2020, 2:06 PM
clang/lib/StaticAnalyzer/Core/CallEvent.cpp
614 ↗(On Diff #260659)

It's not ideal because we're producing a different region for the inherited constructor whereas in reality it's the same region as in the inheriting constructor.

Let's not dig too deeply into this though; i'll be perfectly happy with doing whatever doesn't crash and adding a FIXME for later. I'm pretty sure my previous patch is also incorrect for the same reason.

A few tests won't hurt though, and they might help you find the right approach as well. After all, the analyzer is a C++ interpreter; all questions about "is this the correct handling...?" can be answered by comparing the behavior of the analyzer with the behavior of the actual program at run-time.

Only 4 tests failing, but still lot to do.

Fixed and error in call_once.cpp but stuck with debugging of objc-radar17039661.m.

Wrong diff uploaded.

baloghadamsoftware marked an inline comment as done.May 6 2020, 11:53 AM

See the difference between the correct (master branch) and the incorrect (my attempt) outputs.

clang/lib/StaticAnalyzer/Core/Store.cpp
472 ↗(On Diff #262431)

Probably this loop could be written better, without break at the end, but for now it des what it should do. For captured parameters of functions and blocks we must look for the original CallExpr and LocationContext. If it does not exist (we analyze the block of the lambda top-level) we revert to VarRegion since the captured parameters are simple variales for the block or lambda. However, we cannot do this if the block or lambda is not analyzed top-level, thus the approach I use above seems to be the correct one. However, this completely breaks the test objc-radar17039661.m. Even order of the postCall() hooks is changed and the test fails because it cannot find the bug. I try to attach the two different outputs annotated by debug printouts. @NoQ, do you have an idea what could be wrong here? First I thought on BlockDataRegions where it seems I have to duplicate lots of code and also change the capture interface to also enable ParamRegions for the captures. However, in this case it does not seem to play a role.

I also tried to compare the exploded graphs, but unfortunately the rewriter Python script crashed on them.

baloghadamsoftware marked an inline comment as done.May 6 2020, 10:47 PM
baloghadamsoftware added inline comments.
clang/lib/StaticAnalyzer/Core/Store.cpp
472 ↗(On Diff #262431)

The really strange thing is that I originally used a recoursive approach here, instead of the loop, which I still believe is the right one. However, in that case the test failed even if I removed all creations of ParamRegions. The only difference then was that the LocationContext of the captured region was the top-level LocationContext. This alone changed the calling order of the checker hooks and this happens here as well. It is not the VarRegion vs ParamRegion problem but the LocationContext of the region. I still do not see why this influences the calling order of these hooks. I am already debugging it for almost 15 hours without any clue.

Added support for ParamRegions as original region for captured variables by blocks and lambdas. Only 2 failing tests left.

baloghadamsoftware marked an inline comment as done.May 8 2020, 2:52 AM
baloghadamsoftware added inline comments.
clang/lib/StaticAnalyzer/Core/Store.cpp
472 ↗(On Diff #262431)

Problem solved. Captured variables are always variables, even if they were paramseters originally. I added support for binding the old values to the new regions upon capture for ParamRegions as well. This solved the failing test.

baloghadamsoftware retitled this revision from [Analyzer][WIP] Avoid handling of LazyCompundVals in IteratorModeling to [Analyzer] Avoid handling of LazyCompundVals in IteratorModeling.
baloghadamsoftware edited the summary of this revision. (Show Details)

Rebased to previous patches and updated according to them.

No new functions in CallEvent needed, instead new functions in the iterator library.

Rebased on master which now contains the handling of pointers as iterators. All tests passed.

Crash Fix: do not retrieve first iterator argument in advance. (It may happen that although argument count is more than zero, there is no argument at all.)

else branch merged with inner if.

Aside from infrastructural questions which I am not qualified ( nor particularly knowledgeable :3 ) to address, this looks good to me.

clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
77

999 seems a bit arbitrary here, consider using std::numeric_limits<unsigned>::max(), or llvm::Optional<unsigned>.

Updated according to the latest comment.

baloghadamsoftware marked an inline comment as done.Aug 13 2020, 4:06 AM
baloghadamsoftware added inline comments.
clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp
77

I refactored this part. The earlier approach was very ugly and non-standard. I just intended to make it work as quickly as possible, but I forgot to refactor after that. Thank you for noticing it!

gamesh411 accepted this revision.Aug 14 2020, 12:36 AM

Thanks! LGTM now.

This revision is now accepted and ready to land.Aug 14 2020, 12:36 AM
NoQ added inline comments.Sep 21 2020, 11:38 PM
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

I still believe you have not addressed the problem while moving the functions from D81718 to this patch. The caller of this function has no way of knowing whether the return value is the prvalue of the iterator or the glvalue of the iterator.

Looks like most callers are safe because they expect the object of interest to also be already tracked. But it's quite possible that both are tracked, say:

Container1<T> container1 = ...;
Container2<Container1::iterator> container2 = { container1.begin() };
container2.begin(); // ???

Suppose Container1::iterator is implemented as an object and Container2::iterator is implemented as a pointer. In this case getIteratorPosition(getReturnIterator()) would yield the position of container1.begin() whereas the correct answer is the position of container2.begin().

This problem may seem artificial but it is trivial to avoid if you simply stop defending your convoluted solution of looking at value classes instead of AST types.

clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp
661–662

When does this happen?

NoQ requested changes to this revision.Sep 22 2020, 12:59 AM
NoQ added inline comments.
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

Ugh, the problem is much worse. D82185 is entirely broken for the exact reason i described above and you only didn't notice it because you wrote almost no tests.

Consider the test you've added in D82185:

void begin_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
  auto i = c.begin();

  clang_analyzer_eval(clang_analyzer_iterator_container(i) == &c); // expected-warning{{TRUE}}
}

It breaks very easily if you modify it slightly:

void begin_ptr_iterator(const cont_with_ptr_iterator<int> &c) {
  auto i = c.begin();
  ++i; // <==

  clang_analyzer_eval(clang_analyzer_iterator_container(i) == &c); // Says FALSE!
}

The iterator obviously still points to the same container, so why does the test fail? Because you're tracking the wrong iterator: you treated your &SymRegion{conj_$3} as a glvalue whereas you should have treated it as a prvalue. In other words, your checker thinks that &SymRegion{conj_$3} is the location of an iterator object rather than the iterator itself, and after you increment the pointer it thinks that it's a completely unrelated iterator.

There's a separate concern about why does it say FALSE (should be UNKNOWN) but you get the point.

This revision now requires changes to proceed.Sep 22 2020, 12:59 AM
NoQ added inline comments.Sep 22 2020, 1:08 AM
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

The better way to test D82185 would be to make all existing tests with iterator objects pass with iterator pointers as well. Like, make existing container mocks use either iterator objects or iterator pointers depending on a macro and make two run-lines in each test file, one with -D and one without it. Most of the old tests should have worked out of the box if you did it right; the few that don't pass would be hidden under #ifdef for future investigation.

baloghadamsoftware marked an inline comment as done.Sep 22 2020, 9:51 AM
baloghadamsoftware added inline comments.
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

Thank you for your review and especially for this tip! It is really a good idea. I changed it now and it indeed shows the problem you reported. It seems that my checker mixes up the region of the pointer-typed variable (&i and &j) with the region they point to (&SymRegion{reg_$1<int * SymRegion{reg_$0<const std::vector<int> & v>}._start>} for i before the increment and &Element{SymRegion{reg_$1<int * SymRegion{reg_$0<const std::vector<int> & v>}._start>},1 S64b,int} for both i and j after the increment).

What I fail to see and I am asking you help in it is that the relation between this problem and the getReturnIterator() function. This function retrieves the object from the construction context if there is one, but for plain pointers there is never one. Thus this function is always Call.getReturnValue() like before this patch.

NoQ added inline comments.Sep 22 2020, 1:24 PM
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

I am asking you help

I spent way more time on that already than i find reasonable. Please figure this out on your own by fixing the bug.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

I do not see why I got so a rude answer. I was just asking help in seeing the relation between the bug and this function. Because I do not see any. I think the bug is somewhere in handling unary and binary operators for pointers. I struggled with that part for this same reason and I thought I solved it but now I see that I did not. However, this function just looks for object under construction in the construction context of the function. If the function returns an object by value, then there will be one. In other cases there will be none. I do not see how this relates to pointers and glvalues and prvalues. For parameters you were fully right and I fixed that.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

OK. I tested it now on master. It is exactly the same bug. It is no wonder, because for non-objects such as pointers this function is exactly the same as Call.getReturnValue() since there are no objects under construction at all in this case. I will debug and fix the bug now and rebase this patch on that fix.

NoQ added inline comments.Sep 23 2020, 9:45 PM
clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

seeing the relation between the bug and this function

The bug is in the feature that provides additional test coverage for the function. Due to the bug we're still at zero test coverage for the issue under discussion. Because my previous attempts at productive discussion have so far failed due to you arguing that "all tests are passing", i'm asking you for two months already to present an actual concrete test to cover the issue. That's it. That's the relation.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

Sorry, if you feel that your attempts at productive discussion have so far failed. Actually, I try to do everything you suggest just to push this my patches forward. I try to implement the test cases you suggest with my best effort and if they fail, then I fix them. However, this far I have seen no test cases which pass before and fail after this particular patch. I understood your concern with the arguments and I changed the code. However, I still do not understand it for return values. Is it OK if I check the AST return type for CXXRecordType? It does not seem to solve anything (it does not solve the bug you described), but if you require that, then I will do it. I worked months to establish an infrastructure to be able to replace my previous solution which was based on LazyCompundVals. This patch is just what you wanted before continuing my other patches: use this new infrastructure instead of reaching the region behind LazyCompoundVals. All my patches are stopped because of this one. The checkers give false positives, there are no note tags for iterator changes. All I want is to fix these issues, but if you cannot explain me what is actually wrong with this one, then these checkers remain unusable. Our company is committed to develop in upstream, but I feel that my efforts are in vain to upstream my work.

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

Now I created D88216 and here I got a few failures. I will look up at them, of course.

Sorry, if you think that it is an ignorance and arrogance on my side that I say that "all tests are passing". *It is not!* I am just struggling to understand you what is wrong in my approach. Our technical background about the C++ language and the analyzer are very different. Also, as I mentioned I am not a good tester. You claim that I included *zero* test cases when I really thought that I implemented a *full coverage*. That is the purpose of the review: if I forgot something, then you notice politely that I forgot to test it for some cases and it will not work. There is no need to be harsh and aggressive with someone who did not offend you. I feel that I am still learning the Analyzer. There are more and more parts that became clearer during the years, but I am still very far from a fully understanding. I do not think that I deserve this tone just because of that.

Even after rereading you comments I am not sure what do you mean I am missing here. Should I check for the AST type of the return value? Or should I check whether it is really an iterator? To me the return value seems "binary" in the sense that either the return value is a LazyCompoundVal *and* we have az object under construction *or* the return value is something else (A symbol, a region or an Unknown) *and* we do not have any object under construction. Is this incorrect then?

clang/lib/StaticAnalyzer/Checkers/Iterator.cpp
330–336

To me the return value seems "binary" in the sense that either the return value is a LazyCompoundVal *and* we have az object under construction *or* the return value is something else (A symbol, a region or an Unknown) *and* we do not have any object under construction. Is this incorrect then?

Yes, it is. In some cases the return value is Unknown. Not much more use for us than LazyCompoundVal. (I still not fully understand in which cases we get Unknown.)

Test coverage was hugely increased by rebasing this patch to D88216. Two kind of tests failed. This last update addreses them:

  1. Handle the assignment operator of iterator objects. This is necessary for assignments more complex than an assignment to a variable (which is handled by checkBind()), such as an assignment to a structure/class member.
  1. Put back post-checking of MaterializeTemporaryExpr. This special kind of expression is not only used to materialize temporary expressions from LazyCompoundVals but also for temporaries as return values.

Furthermore I added some comments explaining the functions which retrieve an iterator argument and iterator return value.

Now all tests pass again with the increased coverage. @NoQ if you are still in doubt, please suggest me further test cases to explore. I understand your concerns but cannot address them without some suggestions where my solution could fail.

baloghadamsoftware retitled this revision from [Analyzer] Avoid handling of LazyCompundVals in IteratorModeling to [Analyzer][NFC] Avoid handling of LazyCompundVals in IteratorModeling.Sep 24 2020, 11:29 PM

Oh, I think now what do you mean: iterators stored in containers, thus iterators iterating over iterators. Yes, the current working of the checker does not support it because it stores iterator positions for both the prvalues and the glvalues. This is so from the beginning and this patch does not change anything about this behavior. Of course, this design concept is questionable, we can change it in the future. But not in this patch, this one is purely an NFC: it has exactly the same functionality as the previous versions, the only difference is that it does not hamper anymore with LazyCompoundVals but reaches the real region of the objects (and only in case of objects by value, I check the AST type for paramters), exactly as you requested.

Anyway, to me storing iterators in containers sounds dangerous. Iterators are like lighted matches which you use and then extinguish. You do not put them into the drawer on into a paper box. If you store iterators in a container, how can you track which one of them is invalidated? This sounds a very bad practice to me.

Anyway, we can change the whole iterator modeling and checking in the future to support even this bad practice, but in their current state it is much more beneficial for the users to reduce the huge number of false positives and add note tags for the reported bugs, I think. Maybe we could better explain the current working in the comments at the beginning, and put FIXME-s there. Eventually we can also add such test cases, but with the current functionality even that cannot be done, because we currently do not keep track the content of the containers.

@gamesh411, @whisperity, @martong and others, please suggest me new test cases if you think the current ones are not enough.

Now I completely know what the source of our misunderstanding is. You thought that this patch will fix an issue, namely that we store iterator positions for both the iterator values and the locations of the iterator variables. While this is definitely a wrong approach, it could not be fixed until we got rid from the hack with LazyCompoundVals. These functions keep this existing issue unfixed. However, I could not understand you because I was completely focusing on how these functions could introduce a new issue and I could not find it. No wonder. Thus all my efforts were focused on finding a test cases which passed in the earlier versions but fail in this one because of these functions. Of course I could not find any and I was continuously proving that my patch is correct in the sense that it does not make things worse than they were. That is why I implemented the pointer-based iterators (it would have been better after this patch and a subsequent one that fixes this issue) where I was facing problems because of this wrong approach. In the same time you continuously came with new examples which tried to prove the issue, but I could not understand it because all these new test cases failed in the master version as well. We talked about two very different things because we had very different perceptions about the goal of this patch. That was all.